Gepostet: |
Monaden und do Funktion | ||||||||||
Hallo liebes Forum ;) Kann mir jemand anhand dieser Funktion: powerset :: [a] -> [[a]] erklären was do mit Listen macht und wie \"powerset\" damit eine Liste aller Teillisten erstellt? Ich bedanke mich schon mal im vorraus. viele grüße ludolf |
|||||||||||
Zum Seitenanfang | |||||||||||
Gepostet: |
|||||||||||
Es hilft vielleicht, eine Liste nicht einfach als Folge von Werten aufzufassen, sondern als eine Art \"multiplen Wert\" oder \"paralleles Resultat\". Wenn ich z.B. (+) im Kontext einer Listen-Monade ausführe, welches Ergebnis soll das liefern? Probieren wir es aus:
Mit der normalen Interpretation von Listen kommen wir hier nicht weiter. Stellen wir uns vor, wir hätten eine Funktion, die 1,2 oder 3 zurückliefern kann, und addieren das Resultat mit dem Ergebnis einer Funktion, die 10 oder 20 zurückliefern kann, haben wir eine Funktion, die 11,21,12,22,13 oder 23 zurückliefern kann - so betrachtet macht es schon eher Sinn. Innerhalb der List-Monade nimmt eine Berechnung also sozusagen \"alle möglichen Wege\". Nun zum Ausgangsbeispiel: der Teil powerset xs liefert einfach rekursiv alle Powersets, bei denen x nicht dabei ist. Im do-Block nehmen wir nochmal diese Powersets ohne x und greifen ein Set \"exemplarisch\" heraus und nennen es y. Dann hängen wir x davor und geben es zurück. Welches Set wird nun \"exemplarisch herausgegriffen\"? Nun, die Berechnung geht wieder \"alle Wege\", greift also in Wirklichkeit alle Sets heraus, und gibt die Vereinigungsmenge zurück. Wenn du jetzt noch weißt, wie der Compiler den do-Block intern übersetzt (mehr dazu unter http://book.realworldhaskell.org/read/monads.html Abschnitt \"Desugaring do blocks\" )...
... und dir die Definition der List-Monade anschaust ...
...kannst du sehen, dass das >>= hier nichts weiter als ein foldr über \"alle Operationen\" ist. Setzt man nämlich die Defintion von >>= in obigen Code ein, erhält man das unübersichtliche, aber völlig monadenfreie:
Noch etwas aufräumen...
... und die ganze Monadenmagie ist verpufft. Du kannst das Ganze übrigens auch mit List-Comprehension schreiben, das ist wahrscheinlich die übersichtlichste Variante:
Die doppelte Berechnung von powerset xs kann man übrigens mit einem let umgehen:
|
|||||||||||
Zum Seitenanfang | |||||||||||