试图写一个树高谓词 - 我需要Peano风格的自然数吗？

Question

作为一个基本的Prolog练习,我自己设定了编写二进制树高度谓词的任务,该谓词可以向前和向后工作 - 也就是说,除了确定已知二叉树的高度之外,它应该能够找到所有二进制已知高度的树木(包括不平衡的树木).这是我到目前为止提出的最佳解决方案......

tree_eq1([],s).  % Previously had a cut here - removed (see comments for reason)
tree_eq1([_|T],n(L,R)) :- tree_eq1(T,L), tree_eq1(T,R).
tree_eq1([_|T],n(L,R)) :- tree_eq1(T,L), tree_lt1(T,R).
tree_eq1([_|T],n(L,R)) :- tree_lt1(T,L), tree_eq1(T,R).

tree_lt1([_|_],s).
tree_lt1([_,X|T],n(L,R)) :- XX=[X|T], tree_lt1(XX,L), tree_lt1(XX,R).

第一个参数是高度,表示为列表 - 元素无关,列表的长度表示树的高度.所以我基本上滥用列表作为Peano风格的自然数字.这很方便的原因是......

1. 不关心负数.
2. 我可以在不知道确切数字的情况下检查>或> =例如,通过匹配列表头部的两个项目,我确保列表长度> = 2而不关心尾部的长度.

这些属性似乎都不适用于Prolog数字,到目前为止我无法想到采用相同的基本方法来使用实际数字来代替这些列表.

我在Prolog中看到了一些使用Peano风格数字的例子,所以我的问题是 - 这是正常的做法吗？还是有办法避免我还没有发现的问题？

此外,有没有办法转换为Peano风格的表示,从而不会破坏双向性？以下因为相当明显的原因不起作用......

length(L,N), tree_eq1(L,X).
  % infinite set of lists to explore if N is unknown

tree_eq1(L,X), length(L,N)
  % infinite set of trees to explore if X is unknown

到目前为止,我能想到的最好的是一个is-this-variable-instantiated test,可以在实现之间进行选择,这对我来说就像是在欺骗.

BTW - 我对其他方法有一些想法,我不想要剧透 - 特别是一种动态编程方法.我真的专注于充分理解这一特定尝试的教训.

Answer 1

首先:+1使用列表长度进行计数,这有时非常方便,是继承符号的一个很好的替代方案.

第二:对于可逆算术,通常使用约束而不是后继符号,因为约束允许您使用实际数字并且具有数字之间通常数学关系的内置定义.

例如,使用SICStus Prolog或SWI:

:- use_module(library(clpfd)).

tree_height(s, 0).
tree_height(n(Left,Right), Height) :-
        Height #>= 0,
        Height #= max(HLeft,HRight) + 1,
        tree_height(Left, HLeft),
        tree_height(Right, HRight).

示例查询:

?- tree_height(Tree, 2).
Tree = n(s, n(s, s)) ;
Tree = n(n(s, s), s) ;
Tree = n(n(s, s), n(s, s)) ;
false.

第三,请注意最常见的查询,?- tree_eq1(X, Y).与您的版本无法令人满意地工作.使用上面的代码片段,至少它提供了无数的解决方案(应该如此):

?- tree_height(T, H).
T = s,
H = 0 ;
T = n(s, s),
H = 1 ;
T = n(s, n(s, s)),
H = 2 .

我将他们的公平列举作为练习.