Baumstrukturen in Haskell |
30.01.2010, 10:44 | Auf diesen Beitrag antworten » | |||||||||||||||
SteveD | Baumstrukturen in Haskell Hallo, ich hab mal eine Frage zu Baumstrukturen in Haskell... also ich habe diese aufgabe: Schreiben Sie eine Funktion findArticlesByPrefix :: Content -> String -> [Content], die aus einem Baum mit Inhalten (erstes Argument) all diejenigen Artikel heraussucht, deren Titel mit dem gegebenen Präfix (zweites Argument) beginnen. Schreiben und nutzen Sie hierzu die Hilfsfunktion prefix :: String -> String -> Bool, die genau dann True zurückgibt, wenn das erste Argument ein Präfix des zweiten ist. Für den Beispielbaum gibt der entsprechende Aufruf mit Präfix "Bl" also die beiden Artikel "Blattlaus" und "Blume" zurück. Hinweis: In der Textdarstellung dieser beiden Knoten sehen Sie bei der Verwendung von deriving Show auch die Textdarstellung der Teilbäume. In diesem Fall ist die Darstellung von "Blume" also etwas umfangreicher. "i48.tinypic.com/35hmwsh.png" so schaut die Baumstruktur aus... die erste Aufgabe war ein Datenkontruktor Content zu erstellen, der zwischen Artikeln und Bildern unterscheidet, was ich so gelöst habe: data Content = Page String Content Content | Pic String | Nil deriving Show den baum hab ich dann so dargestellt... nur das meiner nur 2 unterbäume haben kann... könnte theroetisch nochn Content hinter String kanllen damits auchn dritten nehmen kann, aber das ist ja nicht das problem: bsp = (Page "Startseite" (Page "Tier" (Page "Katze" (Pic "lolcat.jpg") Nil) (Page "Blattlaus" Nil Nil)) (Page "Blume" (Page "Rose" Nil Nil) (Pic "lilie.jpg"))) und bei meiner aufgabe jetzt findAriclesByPrefix zu erstellen sollte man prefix vorher machen, welches ich schon so gemacht habe: prefix :: String -> String -> Bool prefix [] [] = True prefix [] (x:xs) = True prefix (x:xs) (y:ys) = x==y && prefix xs ys nur jetzt weiß ich halt nicht weiter... wär nett wenn mir jemand helfen könnte |
|||||||||||||||
|
||||||||||||||||
30.01.2010, 16:02 | Auf diesen Beitrag antworten » | |||||||||||||||
SteveD | nach längerem überlegen hab ich jetzt diesne Ansatz: findArticlesByPrefix :: Content -> String -> [Content] findArticlesByPrefix Nil [] = [] findArticlesByPrefix Nil (x:xs) = [] findArticlesByPrefix (Page x tl tm tr) y | prefix x y = [tl,tm,tr] jedoch weiß ich nicht wie ich die Unterbäume durchsuchen soll... also ich könnte _einen_ unterbaum durchsuchen in dem ich findArticlesByPrefix (Page x tl tm tr) y | prefix x y = [tl,tm,tr] ........................................................| otherwise findArticlesByPrefix tl y mach, aber weiß halt nicht wie ich noch die anderen durchsuchen soll (ohne die Punkte, wollte nur dass die Einrückung beibehalten wird |
|||||||||||||||
31.01.2010, 10:44 | Auf diesen Beitrag antworten » | |||||||||||||||
SteveD | Schade, dass man hier keine Hilfe bekommt. |
|||||||||||||||
02.02.2010, 13:56 | Auf diesen Beitrag antworten » | |||||||||||||||
David_pb | Hi, mit deiner Definition für "Content" lässt sich der Baum allerdings nicht abbilden. Ich hab das mal geändert zu:
Damit lässt sich der Baum dann abbilden, nämlich mit String-Listen als Content-Value:
Das traversieren ist relativ einfach, du musst einfach rekursiv durch beide Teilbäume der Kindknoten wandern bis du irgendwo ein "Nil" Knoten findest. Also in etwa:
Übrigens: Dein "prefix" berücksichtigt keine Prefixe die länger sind als der Teststring. |
|||||||||||||||
Anzeige | ||||||||||||||||
|
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
Die Neuesten » |