SWI-Prolog:摘要列表 [英] SWI-Prolog: Sum-List
问题描述
我从Prolog开始,我有点困惑...
I'm starting with Prolog, and i'm a bit confused...
我有一个简单的程序:
sum(0, []).
sum(Total, [Head|Tail]) :- sum(Sum, Tail), Total is Head + Sum.
调试时,我可以看到Prolog首先用Head和Tail拆分列表,结果是0 +空列表,然后它开始对数字求和并将其再次添加到列表中.
When i debug, i can see that Prolog first splits the list with Head and Tail, so the result is 0 + empty list, and AFTER THAT it starts to sum the numbers and adds it again to the list.
有人可以解释为什么它不出现在Total is Head + Sum.
上吗
首先,然后将列表再次拆分为头尾"?
Can someone explain why it doesn't come to Total is Head + Sum.
first and then splits the list to Head and Tail again?
这是跟踪:
[trace] ?- sum(X, [1,2,3]).
Call: (6) sum(_G345, [1, 2, 3]) ? creep
Call: (7) sum(_G424, [2, 3]) ? creep
Call: (8) sum(_G424, [3]) ? creep
Call: (9) sum(_G424, []) ? creep
Exit: (9) sum(0, []) ? creep
Call: (9) _G430 is 3+0 ? creep
Exit: (9) 3 is 3+0 ? creep
Exit: (8) sum(3, [3]) ? creep
Call: (8) _G433 is 2+3 ? creep
xit: (8) 5 is 2+3 ? creep
Exit: (7) sum(5, [2, 3]) ? creep
Call: (7) _G345 is 1+5 ? creep
Exit: (7) 6 is 1+5 ? creep
Exit: (6) sum(6, [1, 2, 3]) ? creep
X = 6.
推荐答案
您的定义将添加项放在堆栈上.避免舍弃加法的优化将是称为 tail recursion 的通用技术的特例.
Your definition puts addition on the stack. The optimization that avoids putting away the addition would be a special case of a general technique known as tail recursion.
以下定义可以使用尾部递归:
The following definition can use tail recursion:
sum(X,L):-sum(0,L,X).
sum(X,[],X).
sum(N, [Head|Tail],Y) :- N1 is Head + N, sum(N1,Tail,Y).
它为部分和的值引入一个累加器,并将其与列表的末尾一起携带.这是sum(X,[1,2,3])
查询执行的痕迹.
It introduces an accumulator for the values of the partial sum and carries it with the tail of the list. Here is the trace of the execution of the sum(X,[1,2,3])
query.
?- trace, sum(S,[1,2,3]),notrace,nodebug.
Call: (7) sum(_G584, [1, 2, 3]) ? creep
Call: (8) sum(0, [1, 2, 3], _G584) ? creep
^ Call: (9) _G792 is 1+0 ? creep
^ Exit: (9) 1 is 1+0 ? creep
Call: (9) sum(1, [2, 3], _G584) ? creep
^ Call: (10) _G795 is 2+1 ? creep
^ Exit: (10) 3 is 2+1 ? creep
Call: (10) sum(3, [3], _G584) ? creep
^ Call: (11) _G798 is 3+3 ? creep
^ Exit: (11) 6 is 3+3 ? creep
Call: (11) sum(6, [], _G584) ? creep
Exit: (11) sum(6, [], 6) ? creep
Exit: (10) sum(3, [3], 6) ? creep
Exit: (9) sum(1, [2, 3], 6) ? creep
Exit: (8) sum(0, [1, 2, 3], 6) ? creep
Exit: (7) sum(6, [1, 2, 3]) ? creep
S = 6 .
这篇关于SWI-Prolog:摘要列表的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!