www.jammni.de

Gepostet:
26.03.2010 16:20

YAHT - Tutorial Beispiel bräuchte Hilfe

Hiho,

ich bin noch nen blutiger Anfänger was Haskell angeht und geh grade das "Yet another Haskell Tutorial" durch und komme s halb halb damit klar (Geht zum Teil etwas schnell und mit der expliziten Typangabe von Funktionen komme ich garnicht klar) Nun erstmal zu meiner Frage:

(Quelle: http://en.wikibooks.org/wiki/Haskell/YAHT/Type_advanced)


data Graph v e = Graph [(Int,v)] [(Int,Int,e)]

search :: Graph v e -> Int -> Int -> Maybe [Int]
search g@(Graph vl el) src dst
    | src == dst = Just [src]
    | otherwise  = search' el
    where search' [] = Nothing
          search' ((u,v,_):es)
              | src == u  =
                case search g v dst of
                  Just p  -> Just (u:p)
                  Nothing -> search' es
              | otherwise = search' es

Es geht also um Graphen und mit der Gratheorie bin ich vertraut. Der Algo soll einen Weg von einem Knoten zu einem anderen finden und die Rekursion dahinter ist mir denke ich auch klar. Was ich nicht verstehe ist, die gesamte Case Anweisung. Was ist der Case Just p und wie kommt der zustande? und was tut überhaupt das erneute aufrufen von search in der case Bedingung. Wenn mir das Jemand umfangreich erklären könnte wäre ich echt sehr dankbar.

mfg

Zum Seitenanfang

ICQ

Siracusa

Gepostet:
27.03.2010 07:11

Hallo,

das Prinzip des Algorithmus ist ja, wenn man einen Pfad [v1, v2, ..., vn] mit v1 = Start- und vn = Zielknoten finden will, dann sucht man sich eine Kante (v1,v2) und rekursiv einen Restpfad [v2, ..., vn]. Und genau das macht search'. Wenn die übergebene Kantenliste leer ist, gibt es keinen Pfad => Nothing. Ist die Liste nicht leer, schaut man sich die erste Kante an und unterscheidet wieder zwei Fälle:
1.) Die Kante entspricht (v1,v2), dann ist das Ergebnis gerade das Ergebnis der Pfadsuche nach [v2, ..., vn] plus den Knoten v1 davorgehängt. Genau das macht der case-Ausdruck, er sucht den Restpfad [v2, ..., vn]. Wenn er einen findet (Just p) ist das Ergebnis der Startknoten + Pfad (Just (u:p)). Findet er keinen (Nothing), verwirft er die Kante und sucht rekursiv mit den anderen Kanten weiter.
2.) Die Kante entspricht nicht (v1,v2), dann verwirft man die Kante und sucht rekursiv mit der nächsten weiter.

Viele Grüße,

Siracusa

Zum Seitenanfang

XeZZ

Gepostet:
27.03.2010 16:03

| src == u  =
                case search g v dst of
                  Just p  -> Just (u:p)
                  Nothing -> search' es

Ok soweit ist mir das klar nun aber... Die erste Zeile ist klar. Aber das case search g v dst of nicht. Da versteh ich nicht so ganz was da passiert und wie dann die Ergebnisse zustande kommen.

Zum Seitenanfang

ICQ

Siracusa

Gepostet:
27.03.2010 17:26

(search g v dst) ist die Suche nach einem Pfad von v zu dst im Graphen g. Da gibt es zwei Möglichkeiten, was dieser Ausdruck als Ergebnis liefern kann (weil er ja vom Typ Maybe [Int] ist):
1.) Nothing: Dann ist das Ergebnis des case-Ausdrucks das Ergebnis von (search' es)
2.) Just p: p ist der gefundene Pfad. Das Ergebnis des case-Ausdrucks ist dann wieder dieser Pfad mit dem Knoten u davorgesetzt, und das ganze wieder eingepackt in ein Just.

Du hast oben geschieben Geht zum Teil etwas schnell und mit der expliziten Typangabe von Funktionen komme ich garnicht klar - das ist aber extrem wichtig, dass du die Typen von Funktionen verstehst! Denn bei Haskell kann man sehr oft allein durch die Typsignatur Rückschlüsse darauf ziehen, was die Funktion macht. Ein Beispiel: f :: (a,b) -> (b,a). Die Funktion bekommt als Argument ein Tupel vom Typ (a,b) und macht daraus ein Tupel vom Typ (b,a). Das einzig (pur) mögliche was in f gemacht werden kann, ist die Position der Werte innerhalb des Tupel zu vertauschen, etwas anderes verbietet allein schon die Typsignatur. Umgekehrt ist es teilweise sehr schwer Funktionen zu verstehen, die keine explizite Typangabe haben.

Der erste Schritt beim Entwickeln einer Funktion sollte daher m.E die Angabe des Funktionstyps sein, dann schreiben sich die Funktionen meist "von ganz allein" ;-)

Zum Seitenanfang

XeZZ

Gepostet:
27.03.2010 17:33

Ja das mit den Typen ist eben sone Sache das einfache Beispiel von dir kann ich auch so nachvollziehn. Aber so Sachen die solche Form haben:
findElement :: (a -> Bool) -> [a] -> Maybe a - bringen mich schon ins schwitzen da versteh ich einfach nicht so genau wie das zustande kommt. Kannste mir evtl. nen Tutorial empfehlen wo das ganze richtig aufgegriffen wird? Haskell Tuts sind ja irgendwie schon echt rar und mein Englisch ist leider nicht das beste so das YAHT von der Sprachkomplexität schon das äußerste ist und nebenbei lese ich noch "A Gentle Introduction to Haskell" um nen paar weitere Aspekte zu sehen aber auch da kam ich mit der Typerklärung nur bedingt klar.

Zum Seitenanfang

ICQ

Siracusa

Gepostet:
27.03.2010 18:23

Gute deutsche Tutorials gibt es leider nicht so wirklich für Haskell, und bei vielen englischen hab ich den Eindruck, dass sie entweder zu mathematisch sind, oder versuchen jedes Detail und jeden Sonderfall mit abzudecken, was für Anfänger eher verwirrend ist. LYAH (http://learnyouahaskell.com/) soll recht verständlich sein, ich hab es aber nie komplett durchgelesen, daher kann ich nicht sagen wie ausführlch einzelne Aspekte erklärt werden. Zu empfehlen auch http://book.realworldhaskell.org/read/ mit vielen Beispielen. Da geht's allerdings auch recht schnell an komplexere Sachen.

Zum Seitenanfang

XeZZ

Gepostet:
28.03.2010 17:53

Top Danke ich werd mir die beiden mal ansehen. Mein Problem ist auch net das irgendwas zu mathematisch ist sondernd as ich immer zwei Quellen brauche um irgendwas komplett zu verstehen :P

Zum Seitenanfang

ICQ

Haskell-Forum