Baum zum Auflisten (aktualisiert)

Question

Ich habe einen Vorschlag von jemandes Kommentar in einem anderen Beitrag versucht, wie man einen Baum in eine Liste ändert. Allerdings habe ich irgendwo eine undeclared Variablen (oder etwas), so sind meine Werte in meiner Liste [_G667, _G673, _G679] statt [5, 2, 6], was die richtige Antwort ist. Alle Manipulationen sind meines Wissens richtig. Hier

ist der Code:

flatten(Item , []). 

flatten(tree(Left, Val, Right), List) :- 
    flatten(Left, List1), 
    append(List1, [E], List2), 
    flatten(Right, List3), 
    append(List2, List3, List). 

Die Abfrage, die ich verwendet wurde:

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

Hat jemand die Variable Problem sehen? Ich dachte, es könnte in der ersten Zeile (mit Item) sein, aber wenn ich Item zu Item ändere, gibt die Abfrage sofort false zurück.

Ich habe nur ein paar Prolog-Programme geschrieben, also ist das für mich immer noch ein neues Konzept.

Answer 1

Ich glaube, E sollte zu Val geändert werden. So wie es steht, Val wird nicht verwendet (!) Und E kommt aus dem Nichts.

Auch, damit es funktioniert, sollten Sie Item zu nil ändern.

Answer 2

Es gibt mehrere Probleme. Beginnen wir mit dem grundlegendsten: Sie haben einen Baum der folgenden Art.

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

Ihr Programm sollte diesen Typ widerspiegeln. Habe ich "Typ" gesagt? Nun, is_tree/1 ist ein Prädikat wie jedes andere.

Das andere Problem ist Ihre starke Verwendung von append/3. Nicht ohne Grund bieten viele Prolog-Systeme append/3 nicht an, da es oft vorzuziehen ist, die Verkettung mit Hilfe von dcg s zu formulieren.

 
tree_elements(nil) --> []. 
tree_elements(tree(L,E,R)) --> 
    tree_elements(L), 
    [E], 
    tree_elements(R). 

Jetzt können Sie diese verwenden

?- phrase(tree_elements(tree(tree(nil, 2, nil), 5, tree(nil, 6, nil))), Es). 
Es = [2,5,6]. 

Answer 3

Was @aioobe sagte. Ich denke, Sie verwenden auch append/3 mehr als Sie sollten. Angenommen, Ihre Baumdarstellung wie folgt aussieht:

tree(Left_subtree, Data , Right_subtree) 

mit dem Atom nil einen leeren Baum darstellt, ich glaube, Sie könnten den gleichen Effekt erzielen so:

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