Prolog binary tree using var(X)

Question

I built the binary tree structure, binarytree(Data,LeftSub,RightSub).

istree(nil).
istree(binarytree(_,L,R)) :- istree(L), istree(R).

However, I want to represent empty tree by uninstantiated variable instead of istree(nil), using built-in predicate var(X).

istree(D) :- var(D).
istree(binarytree(D,_,_)) :- var(D).
istree(binarytree(D,L,R)) :- not(var(D)).
istree(binarytree(D,L,R)) :- not(var(D)), istree(L), istree(R).

I tried but it doesn't seem right.

Ideally, the meaning of a Prolog predicate should be given only by its set of ground (variable free) solutions. Otherwise, your program is simply a procedural artefact. — false
I tried but it doesn't seem right. What specifically did you try that doesn't seem right? If you remove the 2nd and 3rd clauses, and change not(var(D)) to nonvar(D) it seems to be a suitable solution to your needs assuming you do want an uninstantiated variable, on its own, to be considered a valid binary tree (istree(X) will succeed for any uninstantiated variable X). — lurker

CapelliC CapelliC · Accepted Answer · 2015-02-02T02:33:36

Asserting both the trueness and falseness of a set of clauses can be problematic. I think you can state only the positive cases, and let Prolog fail otherwise:

istree(T) :-
    nonvar(T),
    T = t(_,L,R),
    (var(L) ; istree(L)),
    (var(R) ; istree(R)).

I shortened the functor, to ease test

8 ?- istree(t(a,_,_)).
true 
.

9 ?- istree(t(a,t(b,_,_),_)).
true 
.

10 ?- istree(t(a,t(b,_,_),t(c,_,_))).
true 
.

Prolog binary tree using var(X)

1 Answers