我正在尝试学习序言,并陷入玩具示例之一。binary_tree
定义为:
术语“-”(减号)表示空树。术语t(L,V,R)表示具有左子树L,节点值V和右子树R的树。
现在,我正在尝试写谓词size(Tree,N)
以查找树的大小。我知道可以使用以下方法:
size( -,0).
size( t(L, _,R), S) :- size(L,Ls), size(R,Rs), S is Ls + Rs + 1.
但我想使用累加器使其工作。我累了一些(和其他一些东西),但没有一个工作:
size(t(L,_,R),N):-size(t(L,_,R),0,N).
size(-,A,A).
size(t(L,_,R),A,N):- A1 is A+1,size(L,A1,N1),size(R,A1,N2), N is N1+N2.
例如测试用例:
size(t(-,n,t(-,m,-)),N).
我得到5
代替2
。这是跟踪:
[debug] [7] 85 ?- trace,size(t(-,n,t(-,m,-)),N).
Call: (73) size(t(-, n, t(-, m, -)), _G10307) ? creep
Call: (74) size(t(-, _G10422, t(-, m, -)), 0, _G10307) ? creep
Call: (75) _G10435 is 0+1 ? creep
Exit: (75) 1 is 0+1 ? creep
Call: (75) size(-, 1, _G10437) ? creep
Exit: (75) size(-, 1, 1) ? creep
Call: (75) size(t(-, m, -), 1, _G10437) ? creep
Call: (76) _G10438 is 1+1 ? creep
Exit: (76) 2 is 1+1 ? creep
Call: (76) size(-, 2, _G10440) ? creep
Exit: (76) size(-, 2, 2) ? creep
Call: (76) size(-, 2, _G10440) ? creep
Exit: (76) size(-, 2, 2) ? creep
Call: (76) _G10441 is 2+2 ? creep
Exit: (76) 4 is 2+2 ? creep
Exit: (75) size(t(-, m, -), 1, 4) ? creep
Call: (75) _G10307 is 1+4 ? creep
Exit: (75) 5 is 1+4 ? creep
Exit: (74) size(t(-, _G10422, t(-, m, -)), 0, 5) ? creep
Exit: (73) size(t(-, n, t(-, m, -)), 5) ? creep
N = 5.
我觉得我需要有两个不同的累加器,但不确定如何做,因为我正在尝试学习这些东西,所以我会感谢任何解释(而不是直接回答)。
您两次计数子树:
size(t(L,_,R),A,N):- A1 is A+1,size(L,A1,N1),size(R,A1,N2), N is N1+N2.
^^ ^^ ^^^^^^^^
该值A1
使用两次。您真正想要的是描述差异(不是差异列表,而是非常相似的东西)。
size(-, N,N). % N-N ... 0
size(t(L,_,R), N0,N) :- % N-N0 ... the total size
N1 is N0+1, % N1-N0 ... 1
size(L, N1,N2), % N2-N1 ... size of L
size(R, N2,N). % N-N2 ... size of R
请为变量标记模式。第一个是N0
,最后一个是N
。它们几乎像鞋带一样铺开。
本文收集自互联网,转载请注明来源。
如有侵权,请联系[email protected] 删除。
我来说两句