www.jammni.de

Gepostet:
19.06.2010 12:42

Baum traversieren Problem

Hallo,
Folgende Baumstruktr ist gebeben:

data ITree a = Leaf Integer a | Node Integer a (ITree a) (ITree a)

Man muss dazu eine Funktion "alle_ab" schreiben, die beim Durchwandern eines Baumes alle ab einem konkreten Integer Eintrag vorkommenden Elemente als Paare zurück liefert.
Die Signatur:

alle_an :: ITree a -> Integer -> [(Integer,a)]

meine Herangehensweise:


alle_ab :: ITree a -> Integer -> [(Integer,a)]
alle_ab (Leaf i a) ab = [(i,a)]
alle_ab (Node i a l r) ab
	| ab == i = [(i,a)] ++ getAllFrom l ++ getAllFrom r 
	| otherwise = {--Hier weiß ich nicht mehr weiter --} 
	
getAllFrom :: ITree a -> [(Integer,a)]
getAllFrom (Leaf i a) = [(i,a)]
getAllFrom (Node i a l r)  = [(i,a)] ++ getAllFrom l ++ getAllFrom r

die hilfsfunktion getAllFrom liefert mir einfach solche paare für irgend einen baum
die fkt. alle_ab ruft wenn wir an einem Knoten angekommen sind der gleich dem gesuchten wert ist die hilfsfunktion für die zwei unterbäume auf und baut eine liste mit den ergebnissen zusammen. Bis daher stimmt es denke ich.
Wenn wir aber noch nicht an einem Knoten angekommen sind wo ab == i gilt dann springt er in den "otherwise zweig". Hier muss ich dann die Suche fortsetzen. Aber wie? einfach alle_ab für die Unterbäume aufzurufen führt mich nicht zum ziel....

ich bitte um hilfe,

lg

Zum Seitenanfang

Siracusa

Gepostet:
20.06.2010 01:24

Hallo,

sofern ich "alle ab einem konkreten Integer Eintrag vorkommenden Elemente" richtig verstehe, war die Idee im otherwise-Zweig von alle_ab die Funktion selbst wieder rekursiv aufzurufen aber nicht falsch. Wieso meinst du ist das der falsche Ansatz? Wo ich noch ein Problem sehen würde ist der Leaf-Fall bei alle_ab, wenn die beiden Integers nicht übereinstimmen sollte doch nur einen leere Liste zurückgegeben werden, oder?

Viele Grüße,

Siracusa

Zum Seitenanfang

constructor

Gepostet:
20.06.2010 11:49

alle_ab :: ITree a -> Integer -> [(Integer,a)]
alle_ab (Leaf i a) ab = []
alle_ab (Node i a l r) ab
	| ab == i = [(i,a)] ++ getAllFrom l ++ getAllFrom r 
	| otherwise = (alle_ab l ab) ++ (alle_ab r ab)
	
getAllFrom :: ITree a -> [(Integer,a)]
getAllFrom (Leaf i a) = [(i,a)]
getAllFrom (Node i a l r)  = [(i,a)] ++ getAllFrom l ++ getAllFrom r

So scheint es zu funktionieren. Das mit der leeren Liste für ein Blatt ist richtig.
hm.
es ist nur komisch. Bzw. scheints mir so als ob das hier halt zufällig funktioniert.
Oft muss ich aus einer funktion raus zwei andere funktionen aufrufen.
So wie in dem fall im otherwise zweig zweimal halt die gleiche funktion. Hier geht das ja schön weil ich die einfach mit ++ zusammenhängen kann und eh immer eine liste [(Integer,a)] kommt.
Aber manchmal geht das nicht einfach so. Wie geht man da denn im üblichen vor? Ich hoffe ihr versteht meine frage.
lg

Zum Seitenanfang

Siracusa

Gepostet:
20.06.2010 19:17

Bei alle_ab Leaf müsstest du aber auch unterscheiden, ob ab == i. Sonst gehen dir die Ergebnisse verloren, wo ab erst in den Blättern gleich i ist.

> Wie geht man da denn im üblichen vor?
Einen allgemeinen Fall anzugeben ist etwas schwierig, so spontan würde ich jetzt mal sagen, auf das Ergebnis vom rekursiven Aufruf noch eine Funktion anwenden, die den gelieferten Typ in den erforderlichen Typ umwandelt. Ideal ist natürlich, wenn man die rekursiven Aufrufe auf schon gegebene Funktionen aus den Standard-Bibliotheken zurückführen kann, z.B. map oder die fold-Funktionen. Klappt bei Bäumen oft allerdings nicht.

Zum Seitenanfang

Haskell-Forum