Tree to list (updated)
I tried a suggestion from someone to comment in another post on how to change a tree to a list. However, I have undeclared variables somewhere (or something), so my values in my list are [_G667, _G673, _G679] instead of [5, 2, 6], which is the correct answer. As far as I know, all manipulations are correct.
Here is the code:
flatten( Item , []).
flatten( tree(Left, Val, Right), List) :-
flatten(Left, List1),
append(List1, [E], List2),
flatten(Right, List3),
append(List2, List3, List).
I used the following query:
?- flatten(tree(tree(nil, 2, nil), 5, tree(nil, 6, nil)), L).
Does anyone see a problem with a variable? I thought it might be on the first line (with Item), but if I change item to item, the request will return false immediately.
I have written several Prolog programs, so this is still a new concept to me.
source to share
There are several questions. Let's start with the most fundamental: you have a tree that is of the following type.
is_tree(nil).
is_tree(tree(L,_E,R)) :-
is_tree(L),
is_tree(R).
Your program must reflect this type. Did I say "type"? Well, it is_tree/1
is a predicate just like any other.
Another problem is your heavy use append/3
. It is not for nothing that many Prolog systems do not offer it append/3
, because it is often preferable to formulate concatenation usingdcg s.
tree_elements (nil) -> []. tree_elements (tree (L, E, R)) -> tree_elements (L), [E], tree_elements (R).
Now you can use this
? - phrase (tree_elements (tree (tree (nil, 2, nil), 5, tree (nil, 6, nil))), Es). Es = [2,5,6].
source to share
What @aioobe said. I think you are also using append/3
more than you should. Assuming your tree view looks like this:
tree( Left_subtree, Data , Right_subtree )
with an atom nil
representing an empty tree, I believe you could achieve the same effect:
flatten( nil , [] ).
flatten( tree( Left , Data , Right ) , Flat ) :-
flatten( Left , Pfx ) ,
flatten( Right , Sfx ) ,
append( Pfx , [Data|Sfx] , Flat )
.
source to share