recursion - Prolog 累加器。它们真的是 "different"概念吗？

Question

我正在我的人工智能实验室下学习 Prolog，来源 Learn Prolog Now! .

第五章我们来了解蓄电池 .作为示例，给出了这两个代码片段。
查找列表的长度

不带蓄能器:

len([],0).
len([_|T],N) :- len(T,X), N is X+1.

带蓄能器:

accLen([_|T],A,L) :- Anew is A+1, accLen(T,Anew,L).
accLen([],A,A).

我无法理解，这两个片段在概念上有何不同？累加器究竟有什么不同？有什么好处？

累加器听起来像中间变量。 (如果我错了，请纠正我。)而且到目前为止我已经在我的程序中使用过它们，所以它真的有那么大的概念吗？

Answer 1

当你给某物一个 姓名 ，它突然变得比以前更真实。现在可以通过简单地使用概念的名称来讨论某事。没有更多的哲学，不，累加器没有什么特别之处，但它们很有用。

在实践中，通过一个没有累加器的列表:

foo([]).
foo([H|T]) :-
    foo(T).

列表的头部被留下，不能被递归调用访问。在每个递归级别，您只能看到列表的剩余部分。

使用累加器:

bar([], _Acc).
bar([H|T], Acc) :-
    bar(T, [H|Acc]).

在每个递归步骤中，您都有剩余的列表和您经历过的所有元素。在您的 len/3例如，您只保留计数，而不保留实际元素，因为这就是您所需要的。

一些谓词(如 len/3 )可以使用累加器进行尾递归:您不需要等待输入结束(用尽列表的所有元素)来完成实际工作，而是像您一样逐步进行得到输入。 Prolog 不必在堆栈上留下值，并且可以为您进行尾调用优化。

需要知道“到目前为止的路径”(或需要具有状态的任何算法)的搜索算法使用相同技术的更一般形式，通过向递归调用提供“中间结果”。例如，游程编码器可以定义为:

rle([], []).
rle([First|Rest],Encoded):- 
    rle_1(Rest, First, 1, Encoded).               

rle_1([], Last, N, [Last-N]).
rle_1([H|T], Prev, N, Encoded) :-
    (   dif(H, Prev) 
    ->  Encoded = [Prev-N|Rest],
        rle_1(T, H, 1, Rest)
    ;   succ(N, N1),
        rle_1(T, H, N1, Encoded)
    ).

希望有帮助。