Registrierung Kalender Mitgliederliste Teammitglieder Suche Häufig gestellte Fragen Zur Startseite

Informatiker Board » Themengebiete » Praktische Informatik » Baumstrukturen in Haskell » Hallo Gast [Anmelden|Registrieren]
Letzter Beitrag | Erster ungelesener Beitrag Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen
Neues Thema erstellen Antwort erstellen
Zum Ende der Seite springen Baumstrukturen in Haskell
Autor
Beitrag « Vorheriges Thema | Nächstes Thema »
SteveD
unregistriert
Baumstrukturen in Haskell Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

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 10:44
SteveD
unregistriert
Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

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
30.01.2010 16:02
SteveD
unregistriert
Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

Schade, dass man hier keine Hilfe bekommt.
31.01.2010 10:44
David_pb
Mitglied


Dabei seit: 01.06.2007
Beiträge: 44

Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

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.

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von David_pb: 02.02.2010 18:31.

02.02.2010 13:56 David_pb ist offline E-Mail an David_pb senden Beiträge von David_pb suchen Nehmen Sie David_pb in Ihre Freundesliste auf
Baumstruktur | Brettstruktur
Gehe zu:
Neues Thema erstellen Antwort erstellen
Informatiker Board » Themengebiete » Praktische Informatik » Baumstrukturen in Haskell