tMJ*_*tMJ 9 recursion tail-recursion prolog accumulator
我正在我的人工智能实验室学习Prolog,从源头学习Prolog Now!.
在第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).
我无法理解,这两个片段在概念上有何不同？累加器到底有什么不同？有什么好处？
蓄能器听起来像中间变量.(如果我错了,请纠正我.)到目前为止,我已经在我的程序中使用过它们,所以它真的是一个很大的概念吗？
小智 11
当你给出一个名字时,它会突然变得比以前更真实.现在可以通过简单地使用概念的名称来讨论某些事情.没有得到任何哲学,不,没有什么特别的累加器,但它们是有用的.
在实践中,通过没有累加器的列表:
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)
).
希望有所帮助.
Wil*_*ess 10
TL; DR:是的,他们是.
想象一下,你是从一个城市去一个左边一个城市乙在右边,和你想提前知道两者之间的距离.你是如何实现这一目标的？
甲数学家在这样的位置采用魔称为结构递归.他对自己说,如果我要送什么我自己的副本更近了一步走向城市乙,并要求它的它距离城市？然后,我会加1,其结果是,后从我的副本接受它,因为我已经送了它一个步骤接近往城市,并会知道我的答案,而不必移动一英寸!当然如果我已经在城门口,我不会发送任何地方的任何副本,因为我知道距离是0 - 没有移动一英寸!
我怎么知道我的副本会成功？仅仅因为他将遵循相同的规则,同时从靠近目的地的一点开始.无论我的回答是什么价值,他的意志都会少一些,只有我们有限数量的副本才能被采取行动 - 因为城市之间的距离是有限的.所以总操作肯定会在有限的时间内完成,我会得到答案.因为在无限时间过后得到答案,所以永远都不会得到答案.
而现在,我们提前找到了他的答案,我们谨慎的魔术师数学家准备开始他的安全(现在!)之旅.
但那当然不是魔术 - 这都是一个肮脏的把戏!他没有凭空提前找到答案 - 他已经派出了一大堆其他人为他找到答案.毕竟,艰苦的工作必须完成,他只是假装没有意识到这一点.的距离被行进.此外,后面的距离也必须经过,每个副本要将结果告诉他们的主人,结果实际上是在从目的地回来的路上创造的.所有这一切都在我们的假魔术师开始走路之前.对于团队的努力来说,这是怎么回事？对他来说,这似乎是一个甜蜜的交易.但整体而言......
这就是魔术师数学家的想法.但他勇敢的旅行者的双重旅程正在进行,并计算他的步骤,在每一步的当前步数计数器上加1 ,在他的实际旅程的其余部分之前.没有任何借口了.旅程可能是有限的,也可能是无限的 - 他无法预先知道.但是在他的路线上的每个点,因此当他/如果他到达城市B门时,他将知道他到目前为止的行进距离.而且他肯定不会一直回到路的尽头告诉自己结果.
这就是第一个结构递归和尾递归与第二个采用的累加器/尾递归模数cons/corecursion之间的差异.第一个的知识建立在从目标回来的路上; 第二-在路上来回从起点,向着目标.
也可以看看:
你问,这一切的实际意义是什么？为什么,想象我们的朋友,魔术师数学家需要煮一些鸡蛋.他有一个锅; 一个水龙头; 热板; 和一些鸡蛋.他该怎么办？
嗯,这很容易 - 他只是将鸡蛋放入锅中,从水龙头中加入一些水并将其放在热板上.
如果他已经给了一个装有鸡蛋和水的锅了怎么办？为什么,这对他来说更容易 - 他只是将鸡蛋拿出来,倒出水,最终会遇到他已经知道如何解决的问题!纯粹的魔法,不是吗!
在我们嘲笑这个可怜的家伙之前,我们一定不要忘记 蜈蚣的故事.有时无知是幸福.但是当所需的知识很简单并且像这里的距离一样"一维"时,假装根本就没有记忆是犯罪行为.
累加器是中间变量,是 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).