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

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

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

这段代码种子一个带有累加器的工作谓词，种子为 0。在每次递归时，它创建一个新的累加器，其值为当前值 + 1。当到达列表末尾时，累加器的值与想要的结果。

prolog 引擎足够聪明(TRO/Tail Recursion Optimization)，可以看到它可以在每次调用时重用堆栈帧(因为在递归调用之后没有使用任何局部变量)，从而巧妙地将递归转换为迭代。