Gepostet: |
einfache Baumoperationen | ||||||||||
Hallo, Ich übe mich gerade in Haskell und versuche einen binären Baum aufzubauen und zunächst einfache Operationen darauf durchzuführen: meinBaum sieht folgendermaßen aus: data BTree a = Leaf a | Fork (BTree a) (BTree a) nun als erstes habe ich das simpelste probiert, nämlich die Blattknoten zu zählen: size :: BTree a -> Int size (Leaf x) = 1 size (Fork xt yt) = size xt + size yt funktioniert wunderbar :-) auch die summe der Blattknoteninhalte habe ich: summe :: BTree Int -> Int summe (Leaf i) = i summe (Fork xt yt) = summe xt + summe yt meine nächstes würde ich gerne den größten blattknoten ermitteln hier stehe ich ein bisschen an: getGreatest :: BTree Int -> Int --als erstes behandle ich wieder wie schon vorher den fall wo man nur einen Blattknoten bekommt getGreatest (Leaf i) = i --Beim Fall, wo ich eine Verzweigung bekomme weiß ich allerdings nicht wie ich denn an die Werte von xt und yt überhaupt ran komme --habe mir es so überlegt: getGreatest (Fork xt yt) | getGreatest xt > getGreatest yt = --und hier weiß ich nicht wie ich dann fortfahren soll.....? wie komm ich an die konkreten werte ran die ich dann vergleichen kann? und muss ich mir hier vielleicht auch einen "Hilfsparameter" schreiben der mir den aktuell größten knoten zwischenspeichert? lg c |
|||||||||||
Zum Seitenanfang | |||||||||||
Gepostet: |
|||||||||||
Hallo, da du den Wert zweimal benutzt, einmal beim Vergleichen und einmal beim Zurückgeben, musst du ihn in einer Hilfsvariablen speichern (oder die Funktion zweimal ausführen, was allerdings ziemlich ineffizient ist): getGreatest (Fork xt yt) = Alternativ kannst du auch die Funktion max verwenden, damit ergibt sich als rechte Seite dann ... = max (getGreatest xt) (getGreatest yt) und die Hilfsvariablen werden nicht mehr gebraucht. Viele Grüße, Siracusa |
|||||||||||
Zum Seitenanfang | |||||||||||
Gepostet: |
|||||||||||
Ich hab ne Frage zu der Baumdeinition. ich hab die die du da verwendest schonmal gesehen und versteht leider nciht ganz wie die funktioniert. Ich hab außerdem eine ähnliche gesehen die so aussiehtdata Tree a So nun meine Frage. Du hast nur 2 Teilbäume und an den Teilbäumen können Blätter hängen. Aber wie werden die inneren Knoten dargestellt? Oder ist die andere Definition nur so eine Eta-Reduktionsgeschichte wo das a was bei mir in der Mitte der Teilbäume steht so zu sagen am Ende steht? |
|||||||||||
Zum Seitenanfang | ICQ | ||||||||||
Gepostet: |
|||||||||||
Hallo, also die Baumdefinition oben erlaubt nur das Speichern von Werten an Blättern, da gibt es keine inneren Knoten mit Werten, wohingegen bei deinem Baum in jedem Knoten ein Wert gespeichert wird. Eta-Reduktionen gibt es nur bei Funktionsanwendungen, nicht in der Definition von Datentypen. Viele Grüße, Siracusa |
|||||||||||
Zum Seitenanfang | |||||||||||