Prolog累加器。它们真的是一个“不同”的概念吗？

Question

我正在我的人工智能实验室下学习Prolog，从源码开始学习Prolog吧！

在第五章中，我们来学习累加器。作为示例，给出了这两段代码。要查找列表的长度

无累加器：

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

累加器是中间变量，是Prolog中一个重要的（阅读基本）主题，因为允许反转某些基本算法的信息流，对程序的效率有重要影响。

以反转列表为例

nrev([],[]).
nrev([H|T], R) :- nrev(T, S), append(S, [H], R).

rev(L, R) :- rev(L, [], R).
rev([], R, R).
rev([H|T], C, R) :- rev(T, [H|C], R).

nrev/2 （naïve reverse） 它是 O（N^2），其中 N 是列表长度，而 rev/2 是 O（N）。

Answer 2

TL；医生：是的。

想象一下，你要从左边的一个城市A到右边的一个城市B，你想提前知道两者之间的距离。你是如何实现这一点的？

处于这种位置的数学家使用了被称为结构递归的魔法。他对自己说，如果我将自己的副本发送到离城市B更近一步的地方，并询问它到城市的距离呢？然后，在收到我的副本后，我将在其结果中添加1，因为我已经将它发送到离城市更近一步的地方，并且无需移动一英寸即可知道我的答案！当然，如果我已经在城门，我不会将我的任何副本发送到任何地方，因为我将知道距离为0——无需移动一英寸！

我怎么知道我的复制品会成功？仅仅是因为他会遵循同样的规则，从离我们的目的地更近的地方出发。无论我的答案是什么值，他的答案都会少一个值，只有有限数量的我们会被召唤去行动——因为城市之间的距离是有限的。所以整个操作肯定会在有限的时间内完成，我会得到我的答案。因为过了无限长的时间才得到你的答案，永远也不会得到。

现在，在提前找到了答案后，我们谨慎的魔术师数学家准备开始他的保险箱（现在！）旅行

但那当然根本不是魔术——这完全是一个肮脏的把戏！他没有凭空提前找出答案——他已经把别人的整叠都发出去给他找了。艰苦的工作终究是要做的，他只是假装没有意识到。走过的距离。此外，还必须往回走一段距离，以便每个副本将结果告诉它们的主人，结果实际上是在从目的地回来的路上创建的。这一切都发生在我们的假魔术师开始行走之前。团队合作怎么样？对他来说，这似乎是一笔不错的交易。但是总的来说...

这就是魔术师数学家的想法。但是他的双重勇敢旅行者只是踏上了一段旅程，在他实际旅程的剩余部分之前，计算他沿途的步数，每一步都在当前步数计数器上加上1。不再有伪装。旅程可能是有限的，也可能是无限的——他无法预先知道。但是在他路线的每一个点，因此当他到达B城大门的时候，他就会知道他走了这么远。他当然不必一路回到路的起点来告诉自己结果。

这就是第一种递归的结构递归和第二种递归使用累加器的尾部递归模反递归的尾部递归之间的区别。第一种知识建立在从目标返回的路上；第二种知识——从起点出发，朝着目标前进的路上。旅程就是目的地。

另请参阅：

• 技术报告 TR19：将结构化递归展开为迭代。
  丹尼尔·弗里德曼和大卫·怀斯（1974年12月）。

你会问，这一切的实际意义是什么？想象一下我们的朋友魔术师数学家需要煮鸡蛋。他有一个罐子；水龙头；热板；还有一些鸡蛋。他该怎么办？

嗯，这很容易 - 他只是把鸡蛋放进锅里，从水龙头里加一些水，然后把它放在热盘子里。

如果他已经给了一个装有鸡蛋和水的罐子呢？为什么，对他来说甚至更容易--他只要把鸡蛋拿出来，把水倒掉，最后会得到他已经知道如何解决的问题！纯魔法，不是吗！

在我们嘲笑这个可怜的家伙之前，我们绝不能忘记蜈蚣的故事。有时无知是幸福。但是，当所需的知识像这里的距离一样简单且“一维”时，假装根本没有记忆就是犯罪。

Answer 3

当你给一个东西起名字时，它突然变得比以前更真实。讨论一些事情现在可以通过简单地使用概念的名称来完成。不需要更多的哲学知识，累加器没有什么特别的，但是它们很有用。

在实践中，在没有累加器的情况下浏览列表：

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

列表的头被留在后面，并且不能通过递归调用访问。在每一级递归中，您只能看到列表中剩下的内容。

使用累加器：

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

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

有些谓词(如< code>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)
    ).

希望有帮助。