CODEWITHSUNDEEP
treeprologflattendcg
sup bro
sup bro

Reputation: 391

Tree to list (updated)

I tried a suggestion from someone's comment in another post on how to change a tree into a list. However, I have an 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. All of the manipulations are correct, to my knowledge.

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).

The query that I used was:

?- flatten(tree(tree(nil, 2, nil), 5, tree(nil, 6, nil)), L).

Does anyone see the variable issue? I thought it might be in the first line (with Item), but if I change Item to item, the query immediately returns false.

I have only written a few Prolog programs, so this is still a new concept to me.

Upvotes: 4

Views: 2649

Answers (3)

false
false

Reputation: 10102

There are several issues. Let's start with the most fundamental one: You are having a tree which is of the following type.

is_tree(nil).
is_tree(tree(L,_E,R)) :-
   is_tree(L),
   is_tree(R).

Your program should reflect that type. Have I said 'type'? Well, is_tree/1 is a predicate as any other.

The other issue is your heavy use of append/3. Not without reason, many Prolog systems do not offer append/3 because it is often preferable to formulate the concatenation with the help of 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].

Upvotes: 2

Nicholas Carey
Nicholas Carey

Reputation: 74257

What @aioobe said. I think you're also using append/3 more than you ought. Assuming your tree representation looks like:

tree( Left_subtree, Data , Right_subtree )

with the atom nil representing an empty tree, I believe you could achieve the same effect thusly:

flatten( nil , [] ).
flatten( tree( Left , Data , Right ) , Flat ) :-
  flatten( Left  , Pfx ) ,
  flatten( Right , Sfx ) ,
  append( Pfx , [Data|Sfx] , Flat  )
  .

Upvotes: 2

aioobe
aioobe

Reputation: 420971

I believe E should be change to Val. As it stands, Val is not used (!) and E comes from nowhere.

Also, for it to work, you should change Item to nil.

Upvotes: 2

Related Questions