Prolog的蓄电池。他们是真正的“不同”的概念？ Prolog的蓄电池。他们是真正的“不

我在我的人工智能实验室学习的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:

蓄电池是中间变量，并在序言重要的（阅读基本）的话题，因为允许扭转一些基本算法的信息流，与程序的效率产生重要影响。

把扭转名单为例

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是列表长度，而转/ 2这是O（N）。

Answer 2:

当你给的东西的名称 ，突然变得比以前要更真实。谈论的内容现在可以通过简单地使用这一概念的名称来完成。没有得到任何更多的哲学，没有，没有什么特别的蓄电池，但他们是有用的。

在实践中，经历一个列表，而累加器：

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

列表的头留下，并不能由递归调用进行访问。在递归的每个级别只能看到还剩下什么名单。

使用蓄能器：

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

在每一个递归步骤，你有剩余的名单和所有你所经历的元素。在您的len/3例子，你只保留计数，而不是实际的元素，因为这是你所需要的。

一些谓词（如len/3 ），可以制成尾递归与蓄电池：你不需要等待你的输入（排列表中的所有元素），以做实际工作的结束，而是做增量为您获得输入。序言不必在堆栈上留下的价值观和能为你做尾调用优化。

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

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

希望帮助。

Answer 3:

TL; DR：是的，他们是。

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

甲数学家在这样的位置采用魔称为结构递归 。他对自己说，如果我要送什么我自己的副本一步向 B城更近，并要求它的距离的城市？然后，我会加1，其结果是，从我的副本收到后，因为我已经送了它更接近 一步走向城市，就会知道我的答案，而不必移动一英寸！当然，如果我已经在城门，我不会发送任何副本我的任何地方，因为我知道，距离为0 - 而不必移动一英寸！

而且我怎么知道，我复制的，我会成功吗？很简单，因为他将遵循同样的确切规则，而从一个点开始接近我们的目标。无论价值我的答案是，他将是一个都不能少，只有我们拷贝的有限数量将投入战斗-因为城市间的距离是有限的。所以，总的操作是一定要完成的时间有限，我会得到我的答案。因为让你的答案无限时间过去之后，没有得到它在所有 - 永远。

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

但是，这当然是也不神奇 - 这一切是一个肮脏的把戏！他没有预先找出答案凭空-他已经送出了别人的整叠找给他。艰苦的工作后不得不全部完成，他只是装作没有意识到这一点。的距离行驶。此外，距离后面必须得走，每个副本都告诉他们结果他们的主人，结果被从该目标回来的路上实际创建。所有这一切我们的假魔术师之前曾经开始走自己。是如何形成的一个团队的努力。对于他来说，这可能看起来像一个甜蜜的交易。但总体而言...

所以这是怎么魔术师数学家认为。但他的双勇敢的旅行者刚去的旅程，并计算他的脚步一路走来，加入1至目前的步骤应对每一步，他的实际旅程的其余部分之前。有没有借口了。旅程可能是有限的，也可以是无限的 - 他不知道前期的方式。但在沿着他的路线各点，因此当/如果他在B城城门到达过，他就会知道，到目前为止他的行驶距离。他肯定不会有一路回去的路上开始告诉自己的结果。

这就是第一个的结构递归，和之间的差值与蓄能器尾递归 / 尾递归模利弊 / corecursion由第二使用。第一的知识是建立在距离球门回来的路上; 第二-上描述了从起点的方式，朝着目标。

也可以看看：