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

Informatiker Board » Themengebiete » Praktische Informatik » Baumstrukturen in Haskell » Antwort erstellen » Hallo Gast [Anmelden|Registrieren]

Antwort erstellen
Benutzername: (du bist nicht eingeloggt!)
Thema:
Nachricht:

HTML ist nicht erlaubt
BBCode ist erlaubt
Smilies sind erlaubt
Bilder sind erlaubt

Smilies: 21 von 33
smileWinkDaumen hoch
verwirrtAugenzwinkerngeschockt
Mit ZungeGottunglücklich
Forum Kloppebösegroßes Grinsen
TanzentraurigProst
TeufelSpamWillkommen
LehrerLOL HammerZunge raus
Hilfe 
aktuellen Tag schließen
alle Tags schließen
fettgedruckter Textkursiver Textunterstrichener Text zentrierter Text Hyperlink einfügenE-Mail-Adresse einfügenBild einfügen Zitat einfügenListe erstellen CODE einfügenPHP CODE farbig hervorheben
Spamschutz:
Text aus Bild eingeben
Spamschutz

Die letzten 4 Beiträge
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.
SteveD

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