Перечисление двоичных деревьев в Prolog

Question

Я пытаюсь создать правила Prolog для перечисления «бинарных деревьев» в форме списка в Prolog. Я новичок в Prolog.

Дерево с 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). 

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

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