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

3 answers

I believe it E

should be changed to Val

. Be that as it may, Val

not used (!) And E

comes from nowhere.

Also, you must change Item

to for it to work nil




There are several questions. Let's start with the most fundamental: you have a tree that is of the following type.

is_tree(tree(L,_E,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 using s.

tree_elements (nil) -> [].
tree_elements (tree (L, E, R)) ->
   tree_elements (L),
   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].


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  )




All Articles