Search code examples
listrecursiontreeprolog

Convert General Tree to List in Prolog

So I'm taking a programming paradigms course and we're tackling Prolog. The last exercise is to flatten a general tree structure into a list. By general it means that it can branch any number of times per node. Here's the set of facts and rules that define the tree:

leaf(_).
gnode([]).
gnode([leaf(_)|T]):-
    gnode(T).
gnode([gnode(X)|T]):-
    gnode(X),
    gnode(T).

So my solution, gtree_list, needs to return the element in the leaf, or a list in the case of a gnode, as such (these should all evaluate to true):

gtree_list(leaf(example),example).

gtree_list(gnode( [leaf(5),leaf(4)] ), [5,4]).

gtree_list(gnode( [gnode( [leaf(5)] ),leaf(4)] ), [[5],4]).

gtree_list(gnode( [] ), [] ).

So leaf is element and gnode is list. My current implementation is this:

gtree_list( leaf( L), L ).
gtree_list( gnode( []), [] ).
gtree_list( gnode( [X|Y]), R ):-
    gtree_list( X, R1 ),
    gtree_list( gnode(Y), R2 ),
    append( [R1], R2, R ).

It evaluates all the examples as true so all good there. My issue is that when I ask it to make tree from a nested listed it fails. So, I'm left with the following:

gtree_list(gnode( [gnode( [leaf(5) ]),leaf(4) ]), [ [5],4 ]).

evaluates to true,

gtree_list(gnode( [gnode( [leaf(5)]),leaf(4) ]),X).

returns X=[[5],4], but

gtree_list( X, [[5],4] ).

cannot generate the correct tree. It builds from simplest possible to most complicated, so it goes:

X = leaf( [[5],4] ); 
X = gnode( [leaf([5]), leaf(4)] );

then what I'd like it to do is return X = gnode( [gnode([leaf(5)]), leaf(4)] ), but it never does. In any tree, after going through all possible solutions it infinite loops, which is expected, but apparently my recursion can't figure out how to reverse engineer a nested list, which is a requirement.

What am I missing?

Solution

  • Inlining the append, the second argument gets a chance to guide the inferencing too:

    gtree_list( leaf( L), L ).
gtree_list( gnode( []), [] ).
gtree_list( gnode( [X|Y]), [R1|R2] ):-
    gtree_list(     X,      R1    ),
    gtree_list( gnode(Y),      R2 ).

    This seems to make it work:

    2 ?- gtree_list( gnode( [gnode( [leaf(5) ]), leaf(4)]), [ [5], 4]). 
true ;
false.

3 ?- gtree_list( gnode( [gnode( [leaf(5)]), leaf(4)]), X). 
X = [[5], 4] ;
false.

4 ?- gtree_list( X, [[5], 4]). 
X = leaf([[5], 4]) ;
X = gnode([leaf([5]), leaf(4)]) ;
X = gnode([gnode([leaf(5)]), leaf(4)]) ;
false.