How to make this predicate enumerate trees fairly?

Question

We represent the empty tree by the atom 'nil' and the non-empty tree by the term t(X,L,R), where X denotes the root node and L and R denote the left and right subtree, respectively.

As such, a predicate that tests if a term represents a binary tree is as follows:

is_tree(nil).
is_tree(t(_, Left, Right)) :-
    is_tree(Left), is_tree(Right).

And it works great, for example:

% ?- is_tree(nil).
%@    true.
% ?- is_tree(t(a, nil, nil)).
%@    true.
% ?- is_tree(t(a, t(b, nil, nil), nil)).
%@    true.

However, when posed with a general query, it only seems to create right side nodes:

% ?- is_tree(X).
%@    X = nil
%@ ;  X = t(_A,nil,nil)
%@ ;  X = t(_A,nil,t(_B,nil,nil))
%@ ;  ... .

Now, if X was a list, I could have just prepended the query with length(X, _) to get iterative deepening. However, seeing as the argument is not a list, I am at a loss on how to get a fair enumeration.

I tried to make a predicate that calculates the depth of the tree:

tree_depth(nil, 0).
tree_depth(t(_, Left, Right), Depth) :-
    tree_depth(Left, D0), tree_depth(Right, D1),
    Depth #= max(D0, D1) + 1. 

And then tried to limit it with a constraint, but all I got was a nonterminating query, which, upon inspection, just keeps on generating deeper and deeper trees with only right hand subtrees:

% ?- Y #< 3, tree_depth(X, Y), is_tree(X).
%@    Y = 0, X = nil
%@ ;  Y = 1, X = t(_A,nil,nil)
%@ ;  Y = 2, X = t(_A,nil,t(_B,nil,nil))
%@ ;  *hangs*

At this point I am unsure what should I do, nor what am I doing wrong. I am using scryer prolog if it matters.

Answer 1

Your original program was not bad! In fact, it is the only one with a clean definition of depth. To remove the two sources of non-termination, rather write:

tree_depth(nil, 0).
tree_depth(t(_, Left, Right), Depth) :-
   Depth #>= 1,                   % source 2 rule out negatives
   Depth #= max(D0, D1) + 1,      % source 1 post constraint first
   tree_depth(Left, D0),
   tree_depth(Right, D1).

?- D #< 3, tree_depth(T,D).
   D = 0, T = nil
;  D = 1, T = t(_A,nil,nil)
;  D = 2, T = t(_A,nil,t(_B,nil,nil))
;  D = 2, T = t(_A,t(_B,nil,nil),nil)
;  D = 2, T = t(_A,t(_B,nil,nil),t(_C,nil,nil))
;  false.
?- tree_depth(T,2).
   T = t(_A,nil,t(_B,nil,nil))
;  T = t(_A,t(_B,nil,nil),nil)
;  T = t(_A,t(_B,nil,nil),t(_C,nil,nil))
;  false.
?- length(_,D),tree_depth(T,D).
   D = 0, T = nil
;  D = 1, T = t(_A,nil,nil)
;  D = 2, T = t(_A,nil,t(_B,nil,nil))
;  D = 2, T = t(_A,t(_B,nil,nil),nil)
;  D = 2, T = t(_A,t(_B,nil,nil),t(_C,nil,nil))
;  D = 3, T = t(_A,nil,t(_B,nil,t(_C,nil,nil)))
;  D = 3, T = t(_A,nil,t(_B,t(_C,nil,nil),nil))
;  D = 3, T = t(_A,nil,t(_B,t(_C,nil,nil),t(_D,nil,nil)))
;  D = 3, T = t(_A,t(_B,nil,nil),t(_C,nil,t(_D,nil,nil)))
;  D = 3, T = t(_A,t(_B,nil,nil),t(_C,t(_D,nil,nil),nil))
;  D = 3, T = t(_A,t(_B,nil,nil),t(_C,t(_D,nil,nil),t(_E,nil,nil)))
;  D = 3, T = t(_A,t(_B,nil,t(_C,nil,nil)),nil)
;  D = 3, T = t(_A,t(_B,nil,t(_C,nil,nil)),t(_D,nil,nil))
;  D = 3, T = t(_A,t(_B,nil,t(_C,nil,nil)),t(_D,nil,t(_E,nil,nil)))
;  D = 3, T = t(_A,t(_B,nil,t(_C,nil,nil)),t(_D,t(_E,nil,nil),nil))
;  D = 3, T = t(_A,t(_B,nil,t(_C,nil,nil)),t(_D,t(_E,nil,nil),t(_F,nil,nil)))
;  D = 3, T = t(_A,t(_B,t(_C,nil,nil),nil),nil)
;  D = 3, T = t(_A,t(_B,t(_C,nil,nil),nil),t(_D,nil,nil))
;  D = 3, T = t(_A,t(_B,t(_C,nil,nil),nil),t(_D,nil,t(_E,nil,nil)))
;  D = 3, T = t(_A,t(_B,t(_C,nil,nil),nil),t(_D,t(_E,nil,nil),nil))
;  ... .

However, often it is quite handy to use the number of elements instead, as @brebs suggested. Even better, use the list of the elements! Often, you will need that list anyway.

els(nil) -->
   [].
els(t(E, L, R)) -->
   [E],
   els(L),
   els(R).

?- length(Es,2), phrase(els(T),Es).
   Es = [_A,_B], T = t(_A,nil,t(_B,nil,nil))
;  Es = [_A,_B], T = t(_A,t(_B,nil,nil),nil)
;  false.
?- length(Es,2), phrase(els(T),Es,_).
   Es = [_A,_B], T = nil
;  Es = [_A,_B], T = t(_A,nil,nil)
;  Es = [_A,_B], T = t(_A,nil,t(_B,nil,nil))
;  Es = [_A,_B], T = t(_A,t(_B,nil,nil),nil)
;  false.
?- length(Es,N), phrase(els(T),Es).
   Es = [], N = 0, T = nil
;  Es = [_A], N = 1, T = t(_A,nil,nil)
;  Es = [_A,_B], N = 2, T = t(_A,nil,t(_B,nil,nil))
;  Es = [_A,_B], N = 2, T = t(_A,t(_B,nil,nil),nil)
;  Es = [_A,_B,_C], N = 3, T = t(_A,nil,t(_B,nil,t(_C,nil,nil)))
;  ... .

Answer 2

You can constrain the available nodes by list in some traversal order.

tree(nil, []).
tree(t(X, T1, T2), [X|L]) :- append(L1, L2, L), tree(T1, L1), tree(T2, L2).

| ?- length(L, 3), tree(T, L).

L = [A,B,C]
T = t(A,nil,t(B,nil,t(C,nil,nil))) ? ;

L = [A,B,C]
T = t(A,nil,t(B,t(C,nil,nil),nil)) ? ;

L = [A,B,C]
T = t(A,t(B,nil,nil),t(C,nil,nil)) ? ;

L = [A,B,C]
T = t(A,t(B,nil,t(C,nil,nil)),nil) ? ;

L = [A,B,C]
T = t(A,t(B,t(C,nil,nil),nil),nil) ? ;

So you can transform the list generation to tree generation.

| ?- length(L, X), tree(T, L).

L = []
T = nil
X = 0 ? ;

L = [A]
T = t(A,nil,nil)
X = 1 ? ;

L = [A,B]
T = t(A,nil,t(B,nil,nil))
X = 2 ? ;

L = [A,B]
T = t(A,t(B,nil,nil),nil)
X = 2 ? ;

L = [A,B,C]
T = t(A,nil,t(B,nil,t(C,nil,nil)))
X = 3 ? ;

L = [A,B,C]
T = t(A,nil,t(B,t(C,nil,nil),nil))
X = 3 ? ;

L = [A,B,C]
T = t(A,t(B,nil,nil),t(C,nil,nil))
X = 3 ? ;

L = [A,B,C]
T = t(A,t(B,nil,t(C,nil,nil)),nil)
X = 3 ? ;

L = [A,B,C]
T = t(A,t(B,t(C,nil,nil),nil),nil)
X = 3 ? ;

L = [A,B,C,D]
T = t(A,nil,t(B,nil,t(C,nil,t(D,nil,nil))))
X = 4 ? 

yes

Answer 3

Peano is convenient, to constrain the depth count.

tree_side_depth(nil, P, P).
tree_side_depth(t(_, L, R), s(P), P1) :-
    tree_side_depth(L, P, P0),
    tree_side_depth(R, P0, P1).

peano_incrementing(0).
peano_incrementing(s(P)) :-
    peano_incrementing(P).

tree_depth(T, P) :-
    % Iterative deepening of Peano
    peano_incrementing(P),
    tree_side_depth(T, P, 0).

Result in swi-prolog:

?- tree_depth(T, P).
T = nil,
P = 0 ;
T = t(_, nil, nil),
P = s(0) ;
T = t(_, nil, t(_, nil, nil)),
P = s(s(0)) ;
T = t(_, t(_, nil, nil), nil),
P = s(s(0)) ;
T = t(_, nil, t(_, nil, t(_, nil, nil))),
P = s(s(s(0))) ;
T = t(_, nil, t(_, t(_, nil, nil), nil)),
P = s(s(s(0))) ;
T = t(_, t(_, nil, nil), t(_, nil, nil)),
P = s(s(s(0))) ;
T = t(_, t(_, nil, t(_, nil, nil)), nil),
P = s(s(s(0))) ;
T = t(_, t(_, t(_, nil, nil), nil), nil),
P = s(s(s(0))) ;
T = t(_, nil, t(_, nil, t(_, nil, t(_, nil, nil)))),
P = s(s(s(s(0)))) ;
...

It will terminate if given a Peano depth:

?- tree_depth(T, s(s(0))).
T = t(_, nil, t(_, nil, nil)) ;
T = t(_, t(_, nil, nil), nil) ;
false.

Answer 4

The problem is the left recursion before the constraint. A predicate is left recursive and not tail recursive, if the first goal in a clause is the recursive call:

p :- p, ...

If you can stop the recursion before the left recursive call, you could be more lucky. The Depth parameter will give the max depth, and it will generate also smaller trees:

tree_enum(nil, _).
tree_enum(t(_,Left,Right), Depth) :-
   Depth > 0,    %%% stop condition
   Depth2 is Depth-1,
   tree_enum(Left, Depth2),
   tree_enum(Right, Depth2).

Here is an example run:

?- tree_enum(X, 2).
X = nil ;
X = t(_, nil, nil) ;
X = t(_, nil, t(_, nil, nil)) ;
X = t(_, t(_, nil, nil), nil) ;
X = t(_, t(_, nil, nil), t(_, nil, nil)) ;
false.