Перечисление бинарных деревьев в Прологе

Question

Я пытаюсь создать правила Пролога для перечисления "двоичных деревьев" в виде списка в Прологе. Я новичок в Прологе.

Дерево с 0 узлами - это пустой список:

[]

Дерево с 1 узлом:

[[],[]]

Дерево с 2 узлами имеет 2 возможности:

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

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

и так далее.

Вот мои правила:

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.

Запросы для 0 и 1, очевидно, работают. Для N=2 он печатает одну из возможностей, но выдает ошибку после ввода точки с запятой, чтобы получить другую возможность. Запросы для N>2 напрямую дают ошибку. Ошибка всегда одна и та же:

ERROR: >/2: Arguments are not sufficiently instantiated

Я читал об этой ошибке на некоторых сайтах, но не могу понять, что является причиной этой ошибки здесь.

Заранее благодарны за Вашу помощь.

Answer 1

Использование библиотеки CLPFD поможет получить чистое решение для генерации размеров. Тогда вам не нужен вонючий (;)) integer/1 Предикат, который может быть проблематичным:

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

Или проще (благодаря предложению @repeat):

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 - это хороший, декларативный способ выражения числовых ограничений.

Answer 2

Я знаю, что опубликовал этот вопрос год назад, но позже мне удалось решить его без использования каких-либо библиотек. Вот мое решение:

%binary tree generator
bintree(0,[]). %0 nodes - empty list
bintree(1,[[],[]]). %1 node - list containing 2 empty lists
bintree(N,[Cl,Cr]) :-
    N>=2, %check only if at least 2 nodes
    between(0,N,Nl), %let Nl be in [0,N]
    between(0,N,Nr), %similarly for Nr
    Ns is Nl+Nr+1, %total no. of nodes should add up correctly
    N==Ns, %so check for that
    bintree(Nl,Cl), %children should also be valid binary trees
    bintree(Nr,Cr).