列表长度在Prolog

Question

我是Prolog编程的初学者.我写了这个程序来计算列表的长度.为什么以下程序错了？

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

这段代码

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 2

你需要使用累加器.虽然你可以做这样的事情:

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

此代码为一个带有累加器的worker谓词组成种子,接种为0.在每次递归时,它创建一个新的累加器,其值为当前值+ 1.当到达列表的末尾时,累加器的值与期望的结果.

prolog引擎足够聪明(TRO/Tail Recursion Optimization),可以看到它可以在每次调用时重用堆栈帧(因为在递归调用之后没有使用任何本地),从而将递归整齐地转换为迭代.

Answer 3

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

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