CODEWITHSUNDEEP
listtreeprolog
D. Giver
D. Giver

Reputation: 13

Removing lists-within-lists from my prolog code

I've been trying to solve this problem of mine for a while now but I'm not really sure how to go about it.

For example, let's say I have this "tree" in my database:

tree4(b(b(l(Apple),l(Banana)), b(l(Orange), l(Pear)))).

I want to be able to query the database so as to retrieve the information within each l() and present it in a list. So far I've done this:

leaves(l(X), L) :-
    L = X.
leaves(b(X,Y), L) :-
    leaves(X, A),
    leaves(Y, B),
    L = [A, B].

I then query the database and it gives me this:

?- tree4(T), leaves(T, L).
T = b(b(l(1), l(2)), b(l(3), l(4))),
L = [[1, 2], [3, 4]].

The problem with this code is it generates multiple lists nestled within my original one. Is there another way to go about this? Any help would be greatly appreciated!

Upvotes: 1

Views: 69

Answers (4)

CapelliC
CapelliC

Reputation: 60024

Just a reminder about flatten/2, an handy builtin:

?- leaves(b(b(l(1), l(2)), b(l(3), l(4))), L), flatten(L, F).
L = [[1, 2], [3, 4]],
F = [1, 2, 3, 4].

As you can see from documentation, its use is discouraged, and you have already received plenty of good hints that allow to avoid it.

Upvotes: 0

mat
mat

Reputation: 40768

As you are describing a list (in this case: of leaves), consider using a DCG:

leaves(l(L))     --> [L].
leaves(b(B1,B2)) --> leaves(B1), leaves(B2).

Example query (using atoms instead of variables in tree4/1):

?- tree4(Tree), phrase(leaves(Tree), Leaves).
Tree = b(b(l(apple), l(banana)), b(l(orange), l(pear))),
Leaves = [apple, banana, orange, pear].

Upvotes: 2

Paulo Moura
Paulo Moura

Reputation: 18663

You can avoid the cost of the append/3 predicate by using an accumulator to collect the leaves during the traversal of the tree:

leaves(Tree, Leaves) :-
    leaves(Tree, [], Leaves).

leaves(l(Leaf), Leaves, [Leaf| Leaves]).
leaves(b(Left,Right), Leaves0, Leaves) :-
    leaves(Right, Leaves0, Leaves1),
    leaves(Left, Leaves1, Leaves).

Using your sample call:

?- leaves(b(b(l(1), l(2)), b(l(3), l(4))), Leaves).
Leaves = [1, 2, 3, 4].

Upvotes: 1

lurker
lurker

Reputation: 58254

Assuming your Prolog implementation has an append predicate, you could do this:

leaves(l(X), [X]).

leaves(b(X,Y), L) :-
    leaves(X, A),
    leaves(Y, B),
    append(A, B, L).

So leaves will always return a flat list, even if there's just one. This also assumes your tree is strictly binary, as you have it described.

Upvotes: 0

Related Questions