Tree leaf traversal in Prolog

Question

I experience some issues when I'm training prolog exercises,the problem below is,

The predicate defines what it means to be a tree, and can be used to test whether a term is a tree:

tree(t(L,R)) :- tree(L), tree(R).

tree(T) :- T\=t(_ , _).

By using this predicate you can find an element in a tree, (called a leaf):

leaf(t(L,R),E) :- leaf(L,E);  leaf(R,E).

leaf(T,T) :- T\=t(_ , _).

So here have two problem, first is write predicate elements/2 that produces a list of the elements as they are found in the leafs of a tree in the first argument in a left-to-right order!

The second is write a predicate same content/2 that succeeds exactly when two trees contain the same elements in the same order! Duplicates are significant.

Hope can get anyone good at prolog can help me, thanks a lot.

Have you made any attempt at all to writing these predicates that you want? If you examine all of the results of `leaf/2` when you run it, what do you observe in terms of the order of the results? — lurker, Oct 17 '15 at 13:41
Use a cleaner representation! As is, you state "everything not unifiable with `t(_,_)` is a valid tree / leaf". — repeat, Oct 17 '15 at 14:44
imo, elements/2 is just a findall/3, and content/2 just a join between elements/2 — CapelliC, Oct 17 '15 at 15:20
`elements(Tree, Elements) :- findall( E, leaf(Tree, E), Elements ).` and `content(Tree1, Tree2) :- elements(Tree1, E), elements(Tree2, E).`. — lurker, Oct 20 '15 at 13:44
hi luker,may i ask some other questions? about draw graphs represented these prolog terms: — user2953788, Oct 20 '15 at 14:07
To expand on @repeat's comment, it's hard to imagine how you can use `tree/1` to gain information about anything since it will unify with any term at all. Perhaps your second rule for it should be `tree(T) :- atom(T).`? — Daniel Lyons, Oct 20 '15 at 17:05
hi lurker,according your answer i make some exercises, tree(Leaf) :- Leaf \= tree(_,_). tree(tree(L,R)) :- tree(L), tree(R). Define a predicate sameleafs/2 that succeeds exactly when the set of leafs of two trees coincide! my answer is sameleafs(left,right). sameleafs(tree(Y,L1,R1),tree(Y,R2,L2)):- sameleafs(L1,L2), sameleafs(R1,R2). does it correct? — user2953788, Oct 21 '15 at 23:00

score 2 · Accepted Answer · edited May 23 '17 at 12:23

Both tree/1 and leaf/1 are defaulty^1,2! Why not use a cleaner representation like this?

is_tree(leaf(_)).
is_tree(bin(L,R)) :-
   is_tree(L),
   is_tree(R).

Note that:

is_tree/1 is more versatile than tree/1 and leaf/1: it can generate as well as test trees—and even do a little of both (if the argument is partially instantiated).
is_tree/1 never gives logically unsound answers—no matter which "mode" it is used in.

Some sample uses of is_tree/1:

?- is_tree(T).                                   % generate
  T  = leaf(_A)
; T = bin(leaf(_A),leaf(_B))
; T = bin(leaf(_A),bin(leaf(_B),leaf(_C)))
; T = bin(leaf(_A),bin(leaf(_B),bin(leaf(_C),leaf(_D))))
...

?- is_tree(bin(leaf(1),bin(leaf(2),3))).         % test
false.

?- is_tree(bin(leaf(1),bin(leaf(2),leaf(3)))).   % test
true.

?- T = bin(bin(leaf(1),2),_), is_tree(T).        % do both (or at least try)
false.

?- T = bin(bin(leaf(1),leaf(2)),_), is_tree(T).  % do both
T = bin(bin(leaf(1),leaf(2)),leaf(_A))
T = bin(bin(leaf(1),leaf(2)),bin(leaf(_A),leaf(_B)))
T = bin(bin(leaf(1),leaf(2)),bin(leaf(_A),bin(leaf(_B),leaf(_C)))) 
...

Coming back to your question on how to implement elements/2 and content/2... Use dcg!

leaves(leaf(E))  --> [E].
leaves(bin(L,R)) --> leaves(L), leaves(R).

same_content(A,B) :-
   phrase(leaves(A),Ls),
   phrase(leaves(B),Ls).

Sample query:

?- same_content(bin(leaf(1),bin(leaf(2),leaf(3))), 
                bin(bin(leaf(1),leaf(2)),leaf(3))).
true.

^{Footnote 1: This rock-solid treatise on teaching Prolog discusses many common obstacles, including defaultyness.

Footnote 2: In this answer @mat explains on how defaultyness in Prolog impedes declarative debugging and reasoning.}

Tree leaf traversal in Prolog

1 Answers1