Trying to write a tree height predicate - do you need natural numbers in the Peano style?

Question

As a basic Prolog exercise, I set myself the task of writing a binary tree height predicate that will work forward and backward, that is, as well as determining the height of a known binary tree, it should be able to find all binary trees (including unbalanced ones) known height. This is the best solution that I have come up with so far ...

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). 

The first argument is the height, expressed as a list - the elements are irrelevant, the length of the list expresses the height of the tree. Therefore, I mostly abuse lists as natural numbers in the Peano style. The reasons why this is convenient is ...

• No problem with negative numbers.
• I can check for> or> = without knowing the exact number - for example, by matching two elements in the head of the list, I guarantee that the length of the list is> = 2, without worrying about the length of the tail.

None of these properties seem to apply to Prolog numbers, and so far I cannot think of a way to adapt the same basic approach to using actual numbers instead of these lists.

I saw some examples in Prolog using Peano-style numbers, so my question is this is common practice? Or is there a way to avoid a problem that I have not noticed yet?

Also, is there a way to convert to / from a Peano-style view that doesn't violate bidirectional? The following does not work for obvious reasons ...

 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 

The best I can guess so far is a test created using this variable to choose between implementations that seem to me to be a hoax.

BTW - I have some ideas for other methods for which I do not want to use spoilers - especially a kind of approach to dynamic programming. I am really focused on fully understanding the lessons of this particular attempt.

Answer 1

First: +1 to use the lengths of lists for counting, which is sometimes very convenient and a good alternative to indicate a successor.

Secondly: for reversible arithmetic, you usually use constraints instead of designating a successor, since constraints allow you to work with real numbers and have built-in definitions of the usual mathematical relations between numbers.

For example, with SICStus Prolog or 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). 

Request example:

 ?- 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. 

Third, note that the most common query ?- tree_eq1(X, Y). not working satisfactorily with your version. With the above snippet, at least it gives an infinite number of solutions (as it should be):

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

I leave their fair listing as an exercise.