www.jammni.de

Gepostet:
26.05.2011 08:59

Monaden und do Funktion

Hallo liebes Forum ;)

Kann mir jemand anhand dieser Funktion:

powerset :: [a] -> [[a]]
powerset [] = [[]]
powerset (x:xs) = powerset xs ++ do y <- powerset xs ; return (x:y)

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

Landei

Gepostet:
26.05.2011 10:41

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:


import Control.Monad

liftM2 (+) [1,2,3] [10,20]
-- [11,21,12,22,13,23]

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\" )...


powerset :: [a] -> [[a]]
powerset [] = [[]]
powerset (x:xs) = powerset xs ++ (powerset xs >>= (\\y -> [x : y]))

... und dir die Definition der List-Monade anschaust ...


instance  Monad []  where
    m >>= k = foldr ((++) . k) [] m -- führe die Operation für jedes Element der Liste durch
    m >> k = foldr ((++) . (\\ _ -> k)) [] m -- führe die Operation für jedes Element der Liste durch
    return x = [x]  -- ein einzelner Wert wird in eine Liste \"verpackt\"
    fail _ = []

...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:


powerset [] = [[]]
powerset (x:xs) = powerset xs ++ (foldr ((++) . (\\y -> [x : y])) [] (powerset xs))

Noch etwas aufräumen...


powerset [] = [[]]
powerset (x:xs) = powerset xs ++ (foldr addXtoSet [] (powerset xs)) where
    addXtoSet y ys = [x : y] ++ ys

... und die ganze Monadenmagie ist verpufft.

Du kannst das Ganze übrigens auch mit List-Comprehension schreiben, das ist wahrscheinlich die übersichtlichste Variante:


powerset :: [a] -> [[a]]
powerset [] = [[]]
powerset (x:xs) = powerset xs ++ [x:y | y <- powerset xs]

Die doppelte Berechnung von powerset xs kann man übrigens mit einem let umgehen:


powerset [] = [[]]
powerset (x:xs) = let ps = powerset xs 
                  in ps ++ [x:y | y <- ps]

Zum Seitenanfang

Haskell-Forum