Get all possible binary trees using Prolog?

Question

I'm aware there are lots of questions about defining a binary tree to check whether something is a binary tree or not,but i could not find a thread that tackled this question in the "opposite direction".

Why does your definition of binary tree not return all possible binary trees when called as "es_arbol(X)"? Explain in detail and try to implement a different definition that does return all possible binary tree structures.

Ok,so basically i'm stuck in this part of an assignment.After defining my binary-tree-validating function i noticed that when called with no arguments it just returns trees that "grow" through their right nodes,or at least that's how i interpret the output of swi-prolog.What i am not getting is,assuming my definition is correct,Prolog should be able to construct them in both ways.If not,i would like if someone could point me in the right direction to work out a more general definition of a binary tree,or maybe explain why is it that my definition is not sufficient.

This is my definition:

es_arbol(nil).
es_arbol(arbol(_,I,D)) :- es_arbol(I), es_arbol(D).

Answer 1

The reason that your predicate generates an infinite number of trees along one branch is because you have more than one recursion, and like any language, Prolog will continue making the first recursive call it finds until it returns, which in this case, never will. So you always recurse on one leg of the tree. In other words, you have at least two variables in each tree (the left and right subtrees) that have an infinite number of possibilities.

Binary trees have an infinite number of recursive possibilities along two dimensions. You need a way to order the trees using a single-dimensional metric. One such metric could be the count of nodes in the tree. If you order your trees by node count, starting with node count 0, then for each node count, there are a finite number of trees to enumerate. Here is the general way this would work:

1. Nodes is a valid number of nodes
2. nil is a valid binary tree with 0 nodes
3. arbol(_, TL, TR) is a valid binary tree with N nodes if NL and NR2 add up to N-1 and TL is a valid binary tree of NL nodes, and TR is a valid binary tree of NR nodes. Since Prolog will find all solutions from a given point before backtracking prior to that point, it will search for all of the trees with the given number of nodes first before backtracking to a new valid number of nodes.

In Prolog, it looks like this.

:- use_module(library(clpfd)).

es_arbol(Tree) :-
    length(_, Nodes),
    es_arbol(Tree, Nodes).

I'm using length/2 to "generate" Nodes values of 0, 1, 2, etc. es_arbol(Tree) will succeed with binary trees with successive node counts starting at 0. For a given node count, Nodes, it will find all the solutions to es_arbol(Tree, Nodes) before it finally fails and backtracks to length(_, Nodes) again which will succeed on the next value of Node.

es_arbol(nil, 0).
es_arbol(arbol(_,TreeL,TreeR), N) :-
    N #> 0,
    NL + NR #= N - 1,
    NL #>= 0, NR #>= 0,
    es_arbol(TreeL, NL),
    es_arbol(TreeR, NR).

The base case is trivial. nil is the tree with 0 nodes. The recursive case says that arbol(_,L,R) is a binary tree with N nodes if N > 0, NL and NR are non-negative integers that add up to N, and TL and TR are binary trees with length NL and NR, respectively.

The results of running the above code are:

?- es_arbol(Tree).
Tree = nil ;
Tree = arbol(_G258, nil, nil) ;
Tree = arbol(_G17, nil, arbol(_G157, nil, nil)) ;
Tree = arbol(_G17, arbol(_G200, nil, nil), nil) ;
Tree = arbol(_G14, nil, arbol(_G154, nil, arbol(_G593, nil, nil))) ;
Tree = arbol(_G14, nil, arbol(_G154, arbol(_G603, nil, nil), nil)) ;
Tree = arbol(_G14, arbol(_G130, nil, nil), arbol(_G191, nil, nil)) ;
Tree = arbol(_G14, arbol(_G53, nil, arbol(_G193, nil, nil)), nil) ;
Tree = arbol(_G14, arbol(_G53, arbol(_G236, nil, nil), nil), nil) ;
Tree = arbol(_G14, nil, arbol(_G100, nil, arbol(_G214, nil, arbol(_G354, nil, nil)))) ;
Tree = arbol(_G14, nil, arbol(_G100, nil, arbol(_G214, arbol(_G397, nil, nil), nil))) ;
Tree = arbol(_G14, nil, arbol(_G100, arbol(_G216, nil, nil), arbol(_G277, nil, nil))) ;
Tree = arbol(_G14, nil, arbol(_G100, arbol(_G139, nil, arbol(_G279, nil, nil)), nil)) ;
Tree = arbol(_G14, nil, arbol(_G100, arbol(_G139, arbol(_G322, nil, nil), nil), nil)) ;
Tree = arbol(_G14, arbol(_G130, nil, nil), arbol(_G191, nil, arbol(_G664, nil, nil))) ;
Tree = arbol(_G14, arbol(_G130, nil, nil), arbol(_G191, arbol(_G674, nil, nil), nil)) ;
Tree = arbol(_G14, arbol(_G132, nil, arbol(_G272, nil, nil)), arbol(_G676, nil, nil)) .
...

---

As @false has pointed out in the comments, the use of CLP(FD) is not the most efficient way in this case of applying a enumerative constraint. An alternative, more efficient means would be to use between/3:

es_arbol(nil, 0).
es_arbol(arbol(_,TreeL,TreeR), N) :-
    N > 0,
    N1 is N - 1,
    between(0, N1, NL),
    NR is N1 - NL,
    es_arbol(TreeL, NL),
    es_arbol(TreeR, NR).

Answer 2

Lurker has already given a very nice general solution using CLP(FD) constraints.

I would like to augment the existing answer with an alternative way to constrain the depth of the search. Instead of integers, I am using a list to "count" in a symbolic way.

To reason about lists in Prolog, DCG notation (dcg) is often very convenient, also in this case:

es_arbol(nil) --> [].
es_arbol(arbol(_,I,D)) --> [_], es_arbol(I), es_arbol(D).

Declaratively, you can think about these rules as "consuming credit" to apply.

If I query naively, then I get an unfair enumeration:

?- phrase(es_arbol(A), Ls).
A = nil,
Ls = [] ;
A = arbol(_9016, nil, nil),
Ls = [_9024] ;
A = arbol(_9016, nil, arbol(_9030, nil, nil)),
Ls = [_9024, _9038] ;
A = arbol(_9016, nil, arbol(_9030, nil, arbol(_9044, nil, nil))),
Ls = [_9024, _9038, _9052] ;
A = arbol(_9016, nil, arbol(_9030, nil, arbol(_9044, nil, arbol(_9058, nil, nil)))),
Ls = [_9024, _9038, _9052, _9066] .

The point is that we can easily turn this into a fair enumeration by restricting the length of the list. For example, to get all trees with exactly two inner node, we can use:

?- phrase(es_arbol(A), [_,_]).
A = arbol(_10426, nil, arbol(_10434, nil, nil)) ;
A = arbol(_10426, arbol(_10434, nil, nil), nil) ;
false.

Building on this, we can use iterative deepening to fairly enumerate all tree shapes:

?- length(Ls, _), phrase(es_arbol(A), Ls).
Ls = [],
A = nil ;
Ls = [_7130],
A = arbol(_7142, nil, nil) ;
Ls = [_7130, _7136],
A = arbol(_7148, nil, arbol(_7156, nil, nil)) ;
Ls = [_7130, _7136],
A = arbol(_7148, arbol(_7156, nil, nil), nil) ;
Ls = [_7130, _7136, _7142],
A = arbol(_7154, nil, arbol(_7162, nil, arbol(_7170, nil, nil))) ;
Ls = [_7130, _7136, _7142],
A = arbol(_7154, nil, arbol(_7162, arbol(_7170, nil, nil), nil)) ;
Ls = [_7130, _7136, _7142],
A = arbol(_7154, arbol(_7162, nil, nil), arbol(_7170, nil, nil)) .

Thus, counting "symbolically" is sometimes a convenient alternative to using actual integers.