Die Typkonstruktorklasse Monad

Nachdem wir mit Functor eine erste Typkonstruktorklasse kennengelernt haben, stellt sich die Frage, ob es noch weitere sinnvolle Typkonstruktorklassen gibt. Hierzu untersuchen wir zunächst die IO-Monade und ihre Verknüpfungen genauer und erkennen die Gültigkeit folgender Gesetze:

return () >> m = m
m >> return () = m
m >> (n >> o)  = (m >> n) >> o

Es fällt auf, dass (>>) assoziativ ist und return () ein neutrales Element ist, d.h. beide ergeben zusammen ein Monoid.

Entsprechend gelten für return und >>= folgende Gesetze:

return v >>= \x -> m = m[x/v]
m >>= \x -> return x = m
m >>= \x -> (n >>= \y -> o) = (m >>= \x -> n) >>= \y -> o

Hierbei müssen wir beim letzten Gesetz noch zusätzlich einschränken, dass x nicht frei in o vorkommen darf¹.

Diese Struktur heißt Monade. Der Monaden-Begriff stammt aus der Kategorientheorie, wo er allgemeiner von einem Funktor und zwei natürlichen Transformationen spricht und wo die Monadengesetze mathematisch formuliert sind². Das Wort Monade wurde von Leibniz’ entlehnt³. In Haskell ist eine Monade also ein einstelliger Typkonstruktor m mit den Operationen return, (>>=) (und fail), welche die obigen Eigenschaften erfüllen und in der Klasse Monad zusammengefasst werden:

class Monad m where
  (>>=) : : m a -> (a -> m b) -> m b
  return : : a -> m a
  fail : : String -> m a
  fails = error s
  (>>) : : m a -> m b -> m b
  p >> q = p >>= \_ -> q

Die do-Notation ist in Haskell syntaktischer Zucker für alle Monaden, IO ist Instanz der Klasse Monad. Nun stellt sich die Frage, ob es noch weitere Instanzen dieser Klasse gibt.

Die Maybe-Monade

Auch Maybe ist ein einstelliger Typkonstruktor und es war auch sinnvoll eine Instanz der Klasse Functor zu definieren. Entsprechend ist Maybe auch eine sinnvolle Instanz der Klasse Monad.

data Maybe a = Nothing | Just a

Wir betrachten noch einmal die Auswertung arithmetischer Ausdrücke:

data Expr = Expr :+: Expr
          | Expr : / : Expr
          | Num Float

Problem ist hier die Vermeidung von Laufzeitfehlern (hier beim Teilen durch Null), Ziel ist eine Funktion eval mit folgenden Eigenschaften:

eval (Num 3 :+: Num 4 ) -> Just 7.0
eval (Num 3 :/: (Num (-1) :+: Num 1)) -> Nothing

Dazu definieren wir nun die Funktion eval:

eval :: Expr -> Maybe Float
eval (Num n) = Just n
eval (e1 :+: e2) = case eval e1 of
                     Nothing -> Nothing
                     Just n1 -> case eval e2 of
                                  Nothing -> Nothing
                                  Just n2 -> Just (n1 + n2)
eval (e1 :/: e2) = case eval e2 of
                     Nothing -> Nothing
                     Just 0  -> Nothing
                     Just n2 -> case eval e1 of
                                  Nothing -> Nothing
                                  Just n1 -> Just (n1 / n2)

Dies geht einfacher und schöner mit Maybe als Monade, wobei ein Fehler „durchschlägt“:

instance Monad Maybe where
  Nothing >>= k = Nothing
  Just x  >>= k = k x
  return = Just
  fail _ = Nothing

Nun kann man den Auswerter einfacher definieren:

eval (Num n) = return n
eval (e1 :+: e2) = do
  n1 <- eval e1
  n2 <- eval e2
  return (n1 + n2 )
eval (e1 :/: e2) = do
  n2 <- eval e1
  if n2==0
    then Nothing
    else do
      n2 <- eval e2
      return (n1/n2)

Die Monadengesetze können für Maybe einfach nachgewiesen werden (Übung).

Die Monade mit dem Plus

Eine andere Sicht auf den Datentyp Maybe ist, dass Maybe eine Struktur (ein Container) ist, die null oder ein Element aufnehmen kann. Wenn man dies auf Listen als Container verallgemeinert, kann man auch für den Listentyp eine Monadeninstanz definieren:

instance Monad [] where
  return x = [x]
  -- return = (:[])

  (x:xs) >>= f = f x ++ (xs >>= f)
  []     >>= f = []
  -- (>>=) = flip concatMap

  fail _       = []

Dann ist

[1,2,3] >>= \x -> [4,5] >>= \y -> return (x, y)
~> [(1,4),(1,5),(2,4),(2,5),(3,4),(3,5)]

Dies ist übersetzt in die do-Notation:

do x <- [1,2,3]
   y <- [4,5]
   return (x, y)

Diese Darstellung erinnert stark an die List Comprehensions, welche tatsächlich nur syntaktischen Zucker für die Listenmonade darstellen:

[ (x, y) | x <- [1,2,3], y <- [4,5] ]

Eine weitere Eigenschaft der Listenmonade ist, dass die leere Liste die Null der Struktur ist, da gilt:

m  >>= \_ -> [] = []
[] >>= \_ -> m  = []

Des Weiteren gibt es eine ausgezeichnete, assoziative Funktion (++) mit

(m ++ n) ++ o = m ++ (n ++ o)

Zusammengefasst ergibt sich die Klasse MonadPlus:

class Monad m => MonadPlus m where
  mzero :: m a
  mplus :: m a -> m a -> m a

Für Listen ergibt sich dann:

instance MonadPlus [] where
  mzero = []
  []     `mplus` ys = ys
  (x:xs) `mplus` ys = x : (xs `mplus` ys)
  -- mplus = (++)

Auch für den Datentyp Maybe können wir eine Instanz angeben:

instance MonadPlus Maybe where
  mzero = Nothing
  Nothing  `mplus` m = m
  (Just x) `mplus` _ = Just x

Bevor wir uns weiter mit der Idee speziell der Listenmonade beschäftigen, kommen wir noch einmal zurück zu den Monaden, für welche viele weitere sinnvolle Funktionen definiert werden können. Wir stellen hier nur die wichtigsten Funktionen vor.

sequence :: Monad m => [m a] -> m [a]
sequence = foldr mcons (return [])
  where mcons p q = p >>= \x ->
                    q >>= \ys ->
                    return (x:ys)

sequence_ :: Monad m => [m a] -> m ()
sequence_ = foldr (>>) (return ())

Nun kann man beispielsweise benutzen:

sequence [getLine, getLine] >>= print
sequence [[1,2],[3,4]]
 ~> [[1,3],[1,4],[2,3],[2,4]]

Wir können nun map auf Monaden definieren:

mapM :: Monad m => (a -> m b) -> [a] -> m [b]
mapM f as = sequence (map f as)

mapM_ :: Monad m => (a -> m b) -> [a] -> m ()
mapM_ f a = sequence_ (map f as)

Nun verwenden wir:

mapM_ putStr ["Hallo ", "Leute"])
 ~> Hallo Leute
mapM (\str -> putStr (str ++ ": ") >>
              getLine)
     ["Vorname", "Name"] >>= print
 ~> Vorname: $Frank$
    Name: $Huch$
    ["Frank","Huch"]

Außerdem ist es für Monaden möglich ein if-then ohne else zu definieren:

when :: Monad m => Bool -> m () -> m ()
when b a = if b then a else return ()

main = do
  str <- getLine
  when (str == "Frank")
       (putStrLn "Hi Frank, nice to meet you")
  ...

Suchen mit der Listenmonade

Wir haben schon gesehen, dass die Listenmonade und List Comprehensions eigentlich die gleiche Struktur sind. Es fehlt aber noch die Möglichkeit booleschen Bedingungen zu formulieren, welche das Ergebnis einschränken. Hierzu definiert man eine Funktion guard, welche den Suchraum einschränkt und für Listen wir folgt definiert werden kann:

guard :: Bool -> [()]
guard False = []
guard True  = [()]

Diese Definition erscheint zunächst wenig sinnvoll, ist es aber in Kombination mit dem bind Operator. Das folgende Beispiel zeigt dies. Der Ausdruck

return False >>= guard >> return 42

wird zu

  guard False >> return 42
= [] >> return 42
= []

ausgewertet, der Ausdruck

return True >>= guard >> return 42

aber zu

  guard True >> return 42
= [()] >> return 42
= return 42
= [42]

Mit guard kann man also Ergebnisse anhand eines Prädikats verwerfen. Das erinnert nicht zufallig an die filter-Funktion, die man mit guard definieren kann:

filter :: (a -> Bool) -> [a] -> [a]
filter p xs = do x <- xs
                 guard (p x)
                 return x

Üblicherweise verwendet man guard um zulässige Ergebnisse aus einem größeren Suchraum auszuwählen. Zum Beispiel könnten wir ein Programm zur Berechnung Pythagoräischer Tripel wie folgt schreiben:

pytriples :: Int -> [(Int,Int,Int)]
pytriples max = do a <- [1..max]
                   b <- [a..max]
                   c <- [b..max]
                   guard (a*a + b*b == c*c)
                   return (a,b,c)

Der Aufruf pytriples 10 ergibt dann [(3,4,5),(6,8,10)]. Tatsächlich kann man beliebige List-Comprehensions in do-Notation übersetzen (siehe Übung).

Die guard-Funktion ist für beliebige Instanzen der Klasse MonadPlus wie folgt vordefiniert:

guard :: MonadPlus m => Bool -> m ()
guard False = mzero
guard True  = return ()

Man könnte also eine (leicht angepasste) Version der pytriples-Funktion auch in anderen MonadPlus-Instanzen ausführen.

Die MonadPlus-Gesetze

Bisher haben wir die MonadPlus-Gesetze nur für die Listeninstanz formuliert. Allgemein lauten sie wie folgt:

  m     >>= \_ -> mzero = mzero
  mzero >>= \_ -> m     = mzero

(m `mplus` n) `mplus` o = m `mplus` (n `mplus` o)

mzero und mplus formen also einen Monoid. Es gibt aber noch eine weitere wünschenswerte Eigenschaft von MonadPlus-Instanzen Für jede Funktion f sollte (>>= f) verknüpfungstreu bezüglich mzero und mplus (also gewissermaßen ein MonadPlus-Homomorphismus) sein:

        mzero >>= f  =  mzero
(a `mplus` b) >>= f  =  (a >>= f) `mplus` (b >>= f)

Diese Gesetze stellen sicher, dass während einer Berechnung keine Ergebnisse verloren gehen, sind aber nicht für jede vordefinierte MonadPlus-Instanz erfüllt. Zum Beispiel erfüllt die Instanz für Maybe das zweite, sogenannte Distributivgesetz für MonadPlus, nicht, denn es gilt für a = return False, b = return True und f = guard:

  (return False `mplus` return True) >>= guard
= (Just False `mplus` Just True) >>= guard
= Just False >>= guard
= guard False
= Nothing

aber

  (return False >>= guard) `mplus` (return True >>= guard)
= guard False `mplus` guard True
= Nothing `mplus` Just ()
= Just ()

Die Maybe-Monade ist daher nur bedingt zum Lösen von Suchproblemen geeignet, da Ergebnisse verloren gehen können. Wenn man zum Beispiel, wie oben beschrieben, Pythagoräische Tripel in der Maybe-Monade berechnen möchte, erhält man als Ergebnis Nothing statt Just (3,4,5).