Search code examples
prolog

What is wrong with my simple prolog recursion?

I'm new to Prolog. Trying to write a predicate named leaftree, that is True if the given tree is a leaf tree. A tree is a leaf tree if all its leaves are atoms, or if it's empty. There's my predicate:

leaftree(nil).
leaftree(t(nil, X, nil)):-
    atom(X).
leaftree(t(L, X, R)):-  
    leaftree(L), leaftree(R).

There's the input I'm using to test this predicate:

leaftree(t(t(nil, 5, nil), X, nil)).

Well, the output is True but it should be False because 5 isn't an atom. I played around with the leaftree(t(nil, X, nil)):- atom(X) part; it seems like the predicate is called, but it always returns True. Even if I explicitly write fail or other false statements. If matters, I'm using Swish. I'd love your thoughts!

Thanks so much in advance. Orel

Solution

  • The result of your input is true because it matches the third definition of the predicate. So it exists a predicate that is true for your query.

    This happens because in the third definition X is free to be anything. When consulting your file with swi-prolog i receive, in fact, a warning saying: Singleton variable [X].

    You could replace the second and the third definition with the following (which include both)

    leaftree(t(L, X, R)):-  
    leaftree(L), atom(X), leaftree(R).