Я новичок в программировании на Прологе. Я написал эту программу для расчета длины списка. Почему указанная ниже программа неверна?
length(0, []).
length(L+l, H|T) :- length(L, T).
Я написал ниже программу и она работает корректно.
length([], 0).
length([H|T], N) :- length(T, N1), N is N1+1.
когда я изменил заказ, у меня возникла ошибка. Почему?
length([], 0).
length([H|T], N) :- N is N1+1, length(T, N1).
Вам нужно использовать аккумулятор. Хотя можно было сделать что-то вроде этого:
list_length([] , 0 ).
list_length([_|Xs] , L ) :- list_length(Xs,N) , L is N+1 .
который будет рекурсивно проходить до конца списка, а затем, когда каждый вызов возвращается, добавляйте единицу к длине, пока он не вернется на верхний уровень с правильным результатом.
Проблема с этим подходом заключается в том, что каждая рекурсия помещает в стек новый кадр стека. Это означает, что у вас [в конечном итоге] закончится место в стеке, если список будет достаточно длинным.
Вместо этого используйте хвостовой рекурсивный посредник, например:
list_length(Xs,L) :- list_length(Xs,0,L) .
list_length( [] , L , L ) .
list_length( [_|Xs] , T , L ) :-
T1 is T+1 ,
list_length(Xs,T1,L)
.
Этот код заполняет рабочий предикат, который несет аккумулятор, заполненный нулем. При каждой рекурсии он создает новый аккумулятор, значение которого равно текущему значению +1. Когда достигается конец списка, значение аккумулятора объединяется с желаемый результат.
Механизм пролога достаточно умен (оптимизация рекурсии TRO / хвоста), чтобы видеть, что он может повторно использовать кадр стека при каждом вызове (поскольку ни один из локальных переменных не используется после рекурсивного вызова), таким образом аккуратно преобразовывая рекурсию в итерацию.
этот код
length_1(0,[]).
length_1(L+1, [H|T]) :- length_1(L,T).
работает (обратите внимание на добавленные квадратные скобки), но неожиданным образом. Он построит дерево выражений, которое можно будет оценить позже:
?- length_1(X, [1,2,3]), L is X.
X = 0+1+1+1,
L = 3.
В вашем переписанном коде (вторая версия) вы получите сообщение об ошибке, потому что N1 еще не создан в момент, когда вы вызываете / 2.
Как указано в ответе Карло, L+1 - это термин Пролога с двумя аргументами, L и 1, функтором которых является +. Пролог не является функциональным языком, поэтому вы не можете ввести L+1 и ожидать, что он будет вычислен как сумма. Постарайтесь последовать совету Карло и использовать предикат is/2 для принудительной арифметической оценки. Например, вызов цели X is 3 + 4 оценит правый операнд и попытается объединить результат с левым операндом. Если левый операнд X является переменной, он будет объединен с 7. Также обратите внимание, что в Прологе переменные являются однократными присваиваниями (но могут быть созданы в дальнейшем, если назначенный термин включает переменные). Т.е. вы можете присвоить термин переменной только один раз. Это задание отменяется, когда вы возвращаетесь к цели, выполняя задание.
В других ответах указываются соответствующие проблемы, но я думаю, что проблема просто в неустановленной переменной. В последнем примере
length([], 0).
length([H|T], N) :- N is N1+1, length(T, N1).
Хотя у нас могут быть переменные в правой части is, они должны быть преобразованы в целое число, чтобы Prolog мог выполнять арифметические операции. В приведенном выше примере N1 еще не создан, и Prolog не может применить функтор is. Тип ошибки не упоминается в вопросе, но это должно быть instantiation_error или «Аргументы недостаточно инстанциированы» (если в SWI-Prolog).
Когда вы меняете цели во втором правиле
length([], 0).
length([H|T], N) :- length(T, N1), N is N1+1.
N1 уже преобразован в целое число к моменту вызова is, и программа завершится без ошибок.
См. Также эту другую ветку.
