prolog

How to make this predicate enumerate trees fairly?

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.

Solution

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