CODEWITHSUNDEEP
listrecursiontreeprologflatten
Andrew
Andrew

Reputation: 117

How to flatten a 1-2-3 tree into a list?

I'm working on a function that converts a tree into a list of integers. My issue is, I can append to the list when I only have to add one or two integers. But I can't seem to be able to append three integers without getting this:

[[2], 3, 4], when I should be getting [2, 3, 4].

I know that the issue stems from this statement 

append([Temp1 | Temp2] , Temp3, L)

Where Temp1, Temp2, and Temp3 are the integers I'd like to add. L is the main list that contains all integers from the tree so far.

I tried having two append statements, but that returns a false boolean instead of [2, 3, 4]. I tried moving around the [ | ] but I don't think I know enough about them to have made a difference.

The append/3 page also only goes up to concatenating two lists into one. Any help would be greatly appreciated :)

Edit: my code is as below, and I added my test example.

chopTree(leaf(_), []).
chopTree(node1(Leaf, Node), L) :- 
    chopTree(Node, Temp), 
    append([], [Leaf | Temp], L).
chopTree(node2(Leaf, Node1, Node2), L) :- 
    chopTree(Node1, Temp1), 
    chopTree(Node2, Temp2), 
    append(Temp1, [Leaf | Temp2], L).
chopTree(node3(_, Node1, Node2, Node3), L) :- 
    chopTree(Node1, Temp1), 
    chopTree(Node2, Temp2), 
    chopTree(Node3, Temp3), 
    append([Temp1 | Temp2] , Temp3, L).

query(E) :- 
    chopTree(node3(1, 
                   node1(2, leaf(1)), 
                   node2(3, leaf(1), leaf(1)), 
                   node1(4, leaf(1))), 
             E).

Upvotes: 1

Views: 187

Answers (2)

mat
mat

Reputation: 40768

When relating trees to lists, checkout DCG notation: DCGs let you avoid append/3 entirely, making your code simpler and at the same time often improve its termination properties.

For example:

tree_list(leaf(Leaf)) --> [Leaf].
tree_list(node1(Leaf, Node)) -->
        [Leaf],
        tree_list(Node).
tree_list(node2(Leaf, Node1, Node2)) -->
        tree_list(Node1),
        [Leaf],
        tree_list(Node2).
tree_list(node3(_, Node1, Node2, Node3)) -->
        tree_list(Node1),
        tree_list(Node2),
        tree_list(Node3).

Sample query and answer:

?- phrase(tree_list(node3(1,
                     node1(2, leaf(1)),
                     node2(3, leaf(1), leaf(1)),
                     node1(4, leaf(1)))), Ls).
Ls = [2, 1, 1, 3, 1, 4, 1].

You can easily adapt this to other desired orders, by simply moving the terminals and nonterminals within the DCG bodies.

Note that all the auxiliary variables are gone entirely!

Upvotes: 1

Will Ness
Will Ness

Reputation: 71065

Your naming is off. The variable looks better called "Label". Then, node3 should probably have two of them:

chopTree(leaf(_), []).
chopTree(node1(Label, Node), L) :- 
    chopTree(Node, Temp), 
    % append([], [Label | Temp], L).
    L = [Label | Temp].
chopTree(node2(Label, Node1, Node2), L) :- 
    chopTree(Node1, Temp1), 
    chopTree(Node2, Temp2), 
    append(Temp1, [Label | Temp2], L).
chopTree(node3(Label1, Label2, Node1, Node2, Node3), L) :- 
    chopTree(Node1, Temp1), 
    chopTree(Node2, Temp2), 
    chopTree(Node3, Temp3), 
    append(Temp1, [Label1 | Temp2] , L1),
    append(L1, [Label2 | Temp3], L).

Perhaps node1 shouldn't have any labels in it, too. Anyway, as you can see, we just call append twice, or however many times we need, to build the result list piece by piece.

Upvotes: 1

Related Questions