Baumstrukturen in Haskell

Neue Frage »

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
 
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
Auf diesen Beitrag antworten »
SteveD

Schade, dass man hier keine Hilfe bekommt.
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:

code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
data Content a = Content {
		name :: String,
		value :: a
	} deriving (Show)

data Tree a = Nil
	| Node a (Tree a) (Tree a) deriving (Show)

leaf a = Node a Nil Nil


Damit lässt sich der Baum dann abbilden, nämlich mit String-Listen als Content-Value:

code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
tree = Node (Content "Startseite" []) 
	(Node (Content "Tier" []) 
		-- (Leaf (Content "Katze" ["lolcat.jpg"]))
		-- (Leaf (Content "Blattlaus" [])))
		(leaf (Content "Katze" ["lolcat.jpg"]))
		(leaf (Content "Blattlaus" [])))
	(Node (Content "Blume" ["tulpe.png", "lilie.jpg"]) 
		-- (Leaf (Content "Rose" [])) 
		(leaf (Content "Rose" [])) 
		Nil)


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:

code:
1:
2:
3:
4:
5:
6:
findArticlesByPrefix :: Tree (Content a) -> String -> [Content a]
findArticlesByPrefix Nil _ = []
findArticlesByPrefix (Node a left right) prfx = 
	(findArticlesByPrefix left prfx) ++ /*hier entscheidest du ob der Inhalt in die Liste kommt oder nicht ++ (findArticlesByPrefix right prfx )


Übrigens:
Dein "prefix" berücksichtigt keine Prefixe die länger sind als der Teststring.
 
 
Neue Frage »
Antworten »


Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »