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.

Answer 1

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