Длина списка в прологе

Question

Я новичок в пролог программирования. Я написал эту программу для расчета длины списка. Почему ниже программы неправильно?

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).

Answer 1

Вам нужно использовать аккумулятор. Хотя вы могли бы сделать что-то вроде этого:

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/Tail Recursion Optimization), чтобы видеть, что он может повторно использовать кадр стека при каждом вызове (поскольку ни один из локальных элементов не используется после рекурсивного вызова), таким образом, аккуратно преобразовывая рекурсию в итерацию.

Answer 2

Этот код

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.

Answer 3

len([], LenResult):-
    LenResult is 0.

len([X|Y], LenResult):-
    len(Y, L),
    LenResult is L + 1.

Answer 4

Как намекнуло в ответе Карло, L+1 является термином Пролог с двумя аргументами, L а также 1чей функтор +, Пролог не является функциональным языком, поэтому вы не можете ввести L+1 и ожидаем, что это будет оценено до суммы. Попробуйте следовать предложению Карло и использовать is/2 Предикат для форсирования арифметической оценки. Например, назвать цель X is 3 + 4 оценит правый операнд и попытается объединить результат с левым операндом. Если левый операнд, X, это переменная, она будет объединена с 7, Также обратите внимание, что в Прологе переменные являются одним присваиванием (но могут быть созданы в дальнейшем, если назначенный термин включает в себя переменные). Т.е. вы можете назначить термин переменной только один раз. Это задание отменяется, когда вы возвращаетесь к цели, выполняя задание.

Answer 5

Другие ответы указывают на соответствующие проблемы, но я думаю, что проблема является просто необоснованной переменной. В последнем примере

length([], 0).
length([H|T], N) :- N is N1+1, length(T, N1).

Хотя у нас могут быть переменные в правой части isони должны быть созданы в целое число, чтобы Пролог мог выполнить арифметическую операцию. В приведенном выше примере N1 еще не создан, и Пролог не может применить is функтор. Тип ошибки не упоминается в вопросе, но это должно быть instantiation_error или "Аргументы недостаточно проработаны" (если в SWI-Prolog).

Когда вы инвертируете цели во втором правиле

length([], 0).
length([H|T], N) :- length(T, N1), N is N1+1.

N1 к тому времени уже создан в целое число is вызывается, и программа завершается без ошибок.

Смотрите также эту другую тему.

Answer 6

Найти длину списка в Прологе:

      list_member(X,[X|_]).

list_member(X,[_|TAIL]) :- list_member(X,TAIL).