Enumerating binary trees in Prolog

Question

I am trying to create Prolog rules to enumerate 'binary trees' in list form in Prolog. I am new to Prolog.

A tree with 0 nodes is an empty list:

[]

A tree with 1 node is:

[[],[]]

A tree with 2 nodes has 2 possibilities:

[[],[[],[]]]

[[[],[]],[]]

and so on.

Here are my rules:

bintree(0,[]).
bintree(1,[[],[]]).
bintree(N,[Lc,Rc]) :-
  N > 1,
  bintree(N1,Lc),
  bintree(N2,Rc),
  N1 >= 0,
  N2 >= 0,
  N3 is N1+N2+1,
  N==N3.

Queries for 0 and 1 obviously work. For N=2, it prints one of the possibilities, but gives an error after I input the semicolon to get the other possibility. Queries for N>2 directly give an error. The error is always the same:

ERROR: >/2: Arguments are not sufficiently instantiated

I read about this error on some websites, but I can't figure out what is causing this error here.

Thanks for your help in advance.

Answer 1

Using the CLPFD library will help give a clean solution to generating the sizes. Then you don't need a wonky (;)) integer/1 predicate, which can be problematic:

:- use_module(library(clpfd)).

bintree(0,[]).
bintree(1,[[],[]]).
bintree(N, [L, R]) :-
    N #> 1,
    N #= N1 + N2 + 1,
    N1 #>= 0, N2 #>= 0,
    bintree(N1, L), bintree(N2, R).

Or simpler (thanks to @repeat's suggestion):

bintree(0,[]).
bintree(N, [L, R]) :-
    N #> 0,
    N #= N1 + N2 + 1,
    N1 #>= 0, N2 #>= 0,
    bintree(N1, L), bintree(N2, R).

?- bintree(4, L).
L = [[], [[], [[], [[], []]]]] ;
L = [[], [[], [[[], []], []]]] ;
L = [[], [[[], []], [[], []]]] ;
L = [[], [[[], [[], []]], []]] ;
L = [[], [[[[], []], []], []]] ;
L = [[[], []], [[], [[], []]]] ;
L = [[[], []], [[[], []], []]] ;
L = [[[], [[], []]], [[], []]] ;
L = [[[], [[], [[], []]]], []] ;
L = [[[], [[[], []], []]], []] ;
L = [[[[], []], []], [[], []]] ;
L = [[[[], []], [[], []]], []] ;
L = [[[[], [[], []]], []], []] ;
L = [[[[[], []], []], []], []] ;
false.

?-

CLPFD is a nice, declarative way of expressing numeric constraints.