Monade (Informatik)

In der funktionalen Programmierung sind Monaden ein abstrakter Datentyp. Sie repräsentieren verkettbare Berechnungen.

Formal wird eine Monade durch einen Typkonstruktor M und durch die Definition zweier Operationen (bind und return), die verschiedene Eigenschaften erfüllen müssen, konstruiert. Die return-Operation bildet einen Wert eines einfaches Typs A auf einen Wert vom Typ M A ab. Die bind-Operation kombiniert Ergebnisse, die von einer Funktion von A nach M B erzeugt werden, wenn sie auf M A-„Elemente“ angewendet wird. Das Ergebnis der Kombination ist ein einziges M B.

Hintergrund

Der Hauptnutzen von Monaden ist es, Ein- und Ausgabeoperationen, zustandsbehaftete Berechnungen und Nichtdeterminismus (auch als Iteration über Kollektionen und ihren Kombinationen interpretierbar) und anderes auszudrücken. Dabei soll die Sprache keine Nebeneffekte einführen.^[1]

Der Name Monade stammt aus der Kategorientheorie. Dies ist ein Zweig der Mathematik, der mathematische Objekte mittels Funktoren oder Morphismen vergleicht.

Die Programmiersprache Haskell ist eine funktionale Sprache, die Monaden stark einsetzt und versucht, monadische Kompositionen zu vereinfachen.

Konzepte

Definition

Die übliche Formulierung einer Monade in der Programmierung hat folgende Komponenten:

1. Ein Typkonstruktor, der für jeden zugrunde liegenden Typ definiert, wie der korrespondierende Monadentyp zu erhalten ist. Der Name dieses Typkonstruktors wird dabei oft synonym mit der ganzen Monade verwendet. Wenn M der Name der Monade und t der Datentyp ist, so ist M t der korrespondierende monadische Typ.
2. Eine Einheitsfunktion, die einen Wert des zugrunde liegenden Typs auf den Wert des korrespondierenden Monadentyps abbildet. Das Ergebnis ist der "einfachste" Wert im korrespondierenden Typ, der sich aus dem Originalwert gewinnen lässt. In Haskell wird diese Funktion return genannt. Die Einheitsfunktion hat den polymorphen Typ t→M t.
3. Eine Bindeoperation mit dem polymorphen Typ (M t)→(t→M u)→(M u). Diese wird von Haskell durch den Infixoperator >>= repräsentiert. Sein erstes Argument ist ein Wert von monadischem Typ und sein zweiter ist eine Funktion, die vom zugrunde liegenden Typ des ersten Arguments auf einen anderen monadischen Typ abbildet. Der Rückgabewert ist vom anderen Monadentyp.

In Haskell werden die Anforderungen in einer Typklasse zusammengefasst, die im Wesentlichen folgendermaßen aussieht:

  class Monad m where
      return :: a -> m a
      (>>=)  :: m a -> (a -> m b) -> m b

Auf der Grundlage dieser Klasse lässt sich oben erwähnte Berechnungsverkettung realisieren. Sie ist auch Bestandteil von Haskells Standardbibliothek.

  (>=>) :: Monad m => (a -> m b) -> (b -> m c) -> (a -> m c)
  (f >=> g) a = f a >>= g

Wählt man hier für a den Einheitstyp (), erhält man eine Signatur, die der von >>= im Wesentlichen gleicht. In der Tat könnte man >>= auch auf der Grundlage von >=> angeben.

  m >>= f = (const m >=> f) ()

Monadengesetze

Die Eigenschaften, denen >>= und return genügen müssen, werden Monadengesetze genannt und angegeben als

• m >>= return == m,
• return a >>= f == f a,
• (m >>= f) >>= g == m >>= ( \a -> (f a >>= g) ).

Übersichtlicher lässt sich dies mit Hilfe des Kleisli-Kombinators (>=>) :: Monad m => (b -> m c) -> (a -> m b) -> (a -> m c) darstellen. Dieser ist quasi Funktionskomposition für Monaden:

• f >=> (g >=> h) == (f >=> g) >=> h,
• f >=> return == f,
• return >=> f == f.

Der Operator >=> ist also assoziativ und hat return als neutrales Element. >=> zusammen mit return ist also ein parametrisch polymorpher Monoid und eine Kleisli-Kategorie.

Beziehungen zu anderen Typklassen

Jede Monade ist auch ein Applikativer Funktor und mithin auch ein Funktor. Umgekehrt gilt das nicht. Diese Eigenschaft findet sich jedoch aus historischen Gründen nicht explizit in Haskells Standardbibliothek.

Beispiele

Behälter

Hauptartikel Container (Informatik)

Container wie Listen, Mengen, Multimengen stellen Monaden dar, deren Bindeoperation die übergebene Funktion auf alle Elemente anwendet und die dabei erhaltenen Ergebnisse vereinigt. Die Vereinigungsoperation ist dabei jeweils Listenverkettung, Vereinigungsmengenbildung bzw. Bildung der Multimengenvereinigung. Die Einheitsfunktion ergibt Einermengen und -listen.

Hier als Beispiel die Monade für verkettete Listen. Das Konzept der Instanz für Listen ist es, eine Liste einzulesen, dann jedes Element an die Funktion zu übergeben und die Ergebnisse zu verbinden. Hier eine Beispielimplementation in Haskell:

-- Hier nochmal zur Erinnerung, der Listentyp ist folgendermaßen definiert:
data [a] = [] | a:[a]
-- Als syntaktischer Zucker kann [a,b,c] für a:b:c:[] verwendet werden.
 
instance Monad [] where
--return :: a -> [a]
  return a = [a] -- Per Definition eine Liste mit einem Element zurückgeben
--(>>=) :: [a] -> (a -> [a]) -> [a]
  liste >>= f  = concat zwischenergebnis where -- Die einzelnen Teillisten zusammenfügen
    zwischenergebnis :: [[a]]
    zwischenergebnis = map f liste -- Die Funktion auf die Liste abbilden

Vektoren und lineare Abbildungen

Der Typkonstruktor hier bildet einen Typ T auf einen Vektorraum V(T) ab, bei dem T als (Namensgeber für eine) Basis dient, und dessen Elemente beispielsweise als Funktionen $T\to\mathbb R$ modelliert werden. Die Bindeoperation hat den Typ $V(T) \to (T\to V(U)) \to V(U)$. Durch vertauschen der Argumente erhält man den Typ $(T\to V(U)) \to (V(T) \to V(U))$, an dem man die Semantik erkennen kann: die gegebene Funktion, die auf den Basiselementen definiert ist, wird zu einer vollen linearen Abbildung erweitert. Die Einheitsfunktion bildet das Basiselement (welches in dieser Modellierung noch kein „richtiger“ Vektor ist) auf den entsprechenden Basisvektor ab.

State, I/O

Bei zustandsbehafteten Aktionen dient die Bindeoperation der Verwirklichung der Hintereinanderausführung. Die Einheitsfunktion erstellt eine Aktion, die nichts tut und ein festes Resultat zurückgibt.

Das Konzept ist dabei recht natürlich. Wenn man in einer puren, funktionalen Programmiersprache einen veränderlichen Status übergeben will, dann macht man das in der Regel auf folgende Weise, hier am Beispiel einer Zählerfunktion:

-- Den Zähler hochzählen und den alten Zähler zurückgeben
hochzählen :: Int -> Int -> (Int,Int)
hochzählen schrittweite zählerstand = (zählerstand,neuerZählerstand) where ...

Das Grundprinzip ist, dass man als Parameter den alten Status anhängt und den neuen mit dem Rückgabewert zusammen zurückgibt. Um sich Arbeit zu ersparen, kann man dieses Muster einfach in einen neuen Typen verpacken, der Parameter s des Types ist der Typ des Status, a ist der Parameter des Rückgabewertes:

data Status s a = Status (s -> (a,s))
 
-- Beispiel:
hochzählen :: Int -> Status Int Int
hochzählen schrittweite = Status $ \zählerstand -> (zählerstand,zählerstand+schrittweite)

Was man jetzt noch braucht sind ein paar Funktionen, die den Status manipulieren können. Hier zum Beispiel eine Funktion, die den Status auf einen neuen setzt und eine, die ihn ausliest:

setStatus :: s -> Status s ()
setStatus s = Status $ \_ -> ((),s) -- Der alte Status wird ignoriert und durch den neuen ersetzt. Rückgabewert, da unnötig, ().
 
getStatus :: Status s s
getStatus = Status $ \s -> (s,s) -- Dupliziere den Status in den Rückgabewert.

Dies ist schon fast alles, was nötig ist. Das einzige, was noch fehlt, ist die Möglichkeit mehrere statusverändernde Aktionen zu kombinieren, hier sind Monaden das Werkzeug der Wahl:

instance Monad (Status s) where -- Die Typvariable  s ist irrelevant für die Definition
--return :: a -> Status s a
  return a = Status $ \s -> (a,s) -- Status bleibt unverändert
--(>>=)  :: Status s a -> (a -> Status s b) -> Status s b
  (Status aktion1) >>= f = Status $ \s -> aktion2 zwischenstatus where -- Status aus aktion1 in aktion2 einspeisen.
    (rückgabe1,zwischenstatus) = aktion1 s   -- aktion1 ausführen
    Status aktion2              = f rückgabe1 -- Rückgabewert aus aktion1 in f einspeisen

Mit diesen Funktionen und dem syntaktischem Zucker der do-Notation (der die Monadischen Operationen vor uns versteckt) lässt sich das Beispiel dann folgendermaßen formulieren:

hochzählen :: Int -> Status (Int,Int)
hochzählen schrittweite = do zählerstand <- getStatus -- Zählerstand ermitteln
                             setStatus (zählerstand + schrittweite) -- Zähler setzen
                             return zählerstand -- alten Zählerstand zurückgeben
 
-- Hier entzuckert
hochzählen schrittweite = getStatus >>= \zählerstand ->
                          setStatus (zählerstand + schrittweite) >>= \_ ->
                          return zählerstand

Weblinks

• Papers von Philip Wadler
• You Could Have Invented Monads! (And Maybe You Already Have.)
• What a Monad is not
• Brent Yorgey: Typeclassopedia (PDF) in: The Monad.Reader Issue 13

Monaden in anderen Programmiersprachen

• Monads in Ruby
• Monads in Python
• Monads in Scala
• Monads in Clojure
• Monads in JavaScript
• Monads in C#

Einzelnachweise

1. ↑ Simon L. Peyton Jones, Philip Wadler: Imperative Functional Programming. Conference record of the Twentieth Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, Charleston SC 1993