prolog - 尝试编写树高谓词 - 我是否需要 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 风格的自然数。这很方便的原因是......

不用担心负数。

我可以在不知道确切数字的情况下检查 > 或 >= - 例如，通过匹配列表头部的两个项目，我确保列表长度为 >=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 测试，这对我来说似乎是作弊。

顺便说一句 - 我对其他方法有一些想法，我不想剧透 - 特别是一种动态编程方法。我真的很专注于完全理解这次特定尝试的经验教训。

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 .

我把他们的公平列举作为练习。