13

我正在我的人工智能实验室下学习 Prolog，来源是现在学习 Prolog！.

在第 5 章中，我们来了解累加器。作为示例，给出了这两个代码片段。 查找列表的长度

没有蓄能器：

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

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

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

4

3 回答 3

13

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

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

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

希望有帮助。

于 2013-11-13T06:27:06.017 回答
13

TL;DR：是的，他们是。

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

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

我怎么知道我的副本会成功？仅仅因为他将遵循相同的确切规则，同时从离我们目的地更近的地方开始。无论我的答案是什么价值，他的价值都会少一个，只有有限数量的我们的副本会被调用——因为城市之间的距离是有限的。所以整个操作肯定会在有限的时间内完成，我会得到我的答案。因为在无限时间过去之后得到你的答案，根本就没有得到它 - 永远。

而现在，在提前找到他的答案后，我们谨慎的魔术师数学家已经准备好踏上他的安全（现在！）旅程。

但这当然根本不是魔术——这都是一个肮脏的把戏！他不是凭空提前找到答案的——他已经派出一大堆人来给他找答案。繁重的工作终究是要完成的，他只是装作不知道而已。距离被走过。而且，回来的距离也是要走的，每一个副本都要把自己的结果告诉自己的主人，结果实际上是在从目的地回来的路上创造出来的。这一切都发生在我们的假魔术师开始自己走路之前。团队合作怎么样。对他来说，这似乎是一笔甜蜜的交易。但总的来说...

所以这就是魔术师数学家的想法。但是他的双重勇敢的旅行者只是开始了一段旅程，并沿途计算他的步数，在他的实际旅程的其余部分之前，每一步的当前步数计数器加 1。没有任何伪装了。旅程可能是有限的，也可能是无限的——他无法预先知道。但是在他的路线上的每一点，因此当他也到达城市B的大门时，他会知道他走了这么远的距离。而且他当然不用一路回到路的起点告诉自己结果。

这就是第一个结构递归与第二个使用累加器⁄尾递归模 cons ⁄ corecursion的尾递归之间的区别。第一个知识是建立在从目标回来的路上；第二个 -从起点出发，朝着目标前进。旅途就是目的地。

也可以看看：

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

好吧，这很容易——他只需将鸡蛋放入锅中，从水龙头中加入一些水，然后将其放在热板上。

如果他已经给了一个装有鸡蛋和水的锅怎么办？为什么，这对他来说更容易——他只需把鸡蛋拿出来，倒出水，最后就会遇到他已经知道如何解决的问题！纯粹的魔法，不是吗！

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

于 2013-11-13T10:39:55.577 回答
8

累加器是中间变量，并且是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（朴素反向）它是 O(N^2)，其中 N 是列表长度，而 rev/2 它是 O(N)。

于 2013-11-13T07:27:55.443 回答