Monade (Informatik)

In der funktionalen Programmierung ist eine Monade ein abstrakter Datentyp. Monaden werden hauptsächlich zur Modellierung von Computer-Berechnungen (engl. computations) in Sprachen ohne Nebeneffekte verwendet^[1]. Computer-Berechnungen unterscheiden sich von mathematischen Berechnungen dahingehend, dass das Berechnungsergebnis nicht einzig und allein dem „reinen“ (engl. pure) Wert der Berechnung entsprechen muss^[2]. Es sind auch Fehler oder andere Effekte denkbar, u. a., dass man

einen oder keinen Wert erhält (Maybe-Monade),
einen Fehlerwert oder den Berechnungswert bekommt (Either-Monade),
kein, ein oder viele Ergebnisse gleichzeitig (Nichtdeterminismus) zurückbekommt (List-Monade),
Systemzustände berücksichtigen muss (State-Monade) oder
Ein-/Ausgabeoperationen benötigt (IO-Monade).

Ebenso lassen sich auf diese Art Operationen über Kollektionen oder deren Kombinationen ausdrücken.

Monaden gewährleisten durch ihre Struktur und die zugehörigen Gesetzmäßigkeiten, dass man konsistent und Kompositionsprinzipien entsprechend mit beiden Interpretationen umgehen kann.

Wesentliche Eigenschaft von Monaden ist die Fähigkeit der Übertragung von Werten und Berechnungen eines „einfacheren“ Typs auf Berechnungen eines „höheren“ Typs, der mittels eines Typkonstruktors aus dem einfacheren Typ hervorgeht, sowie die Verknüpfung mehrerer solcher Übertragungen zu einer einzigen.

„Höherer“ Typ bedeutet hier, dass der Typ (mindestens) einen Typparameter braucht, um zu einem konkreten Typen zu werden. Ein Beispiel ist die (typhomogene) Liste, deren Elemente in ihrer Definition nur einen abstrakten Typ besitzen (List a mit Elementen des abstrakten Typs a), der jedoch in bestimmten Situationen festgelegt werden muss. Beispielsweise braucht man eine Liste von ganzen Zahlen, um deren Summe zu berechnen sum : List Int -> Int. Andererseits kann man die Länge einer Liste auch für abstrakte Elemente berechnen, weil man nicht direkt mit den Elementen operieren muss, length : List a -> Int. (Links vom Pfeil steht, was in die Funktion als Eingabe eingeht, rechts davon das Ergebnis.)

Remove ads

Hintergrund

Das Konzept der Monade stammt aus der Kategorientheorie, einem Zweig der Mathematik, welcher mathematische Objekte mittels Morphismen oder Funktoren untersucht. Die Wörter Monade oder aber auch Funktor sind wiederum von Konzepten in der Philosophie abgeleitet.

Die Programmiersprache Haskell ist eine funktionale Sprache, die Monaden stark einsetzt und versucht, monadische Kompositionen zu vereinfachen, beispielsweise durch syntaktischen Zucker (u. a. die sogenannte do-Notation).

Remove ads

Definition und Erläuterungen

Zusammenfassung

Kontext

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

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.
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.
Mindestens eine weitere Operation (siehe dazu die folgenden Abschnitte), welche die Verknüpfung monadischer Operationen beschreibt.

Obwohl im Folgenden verschiedene Definitionen in Haskell angegeben werden, wird hier kurz eine an der Kategorientheorie angelehnte Definition in Agda vorgestellt, die alle erforderlichen Merkmale zusammenfasst. Eine Monade besteht aus einem Funktor M von einer Kategorie in sich (mitsamt der Morphismenabbildung fmap) und zwei natürlichen Transformationen, Einheit return vom Identitätsfunktor auf M und Multiplikation join von M verkettet mit M auf M. Alles zusammen wird in einem record gesammelt:

record Monad : Set₁ where
  field
    M      : Set → Set                    -- Typkonstruktor (z. B. List, Maybe usw.)
    return : ∀{A}   → A       → M A       -- nat. Transformation "Einheit"
    join   : ∀{A}   → M (M A) → M A       -- nat. Transformation "Multiplikation"
    fmap   : ∀{A B} → (A → B) → M A → M B -- zu M gehörige Morphismenabbildung
    -- Monadengesetze fehlen hier erst mal
  _>>=_    : ∀{A B} → M A → (A → M B) → M B -- "bind"
  ma >>= f = (join ∘ (fmap f)) ma           -- "∘" ist die Verkettung von Funktionen

Die sog. Bind-Operation >>= (s. u.) wird durch die anderen Funktionen definiert. Set steht stellvertretend für „kleine“ Typen wie Bool, Int, String, usw. Set₁ ist der Typ von Set und damit ein Ausdruck des „höheren“ Typs, der oben erwähnt wurde. ∀{A B} steht für implizite Argumente, deren Typ Agda selbst einsetzen kann. Aus der Definition von M „weiß“ Agda, dass A und B beide vom Typ Set sind. Für jede Monade muss jedes Feld im record definiert werden. Insbesondere muss auch M bekannt sein. Falls die Monadengesetze auch im record stehen, müssen die Beweise mitgeliefert werden. Das ist in Haskell nicht notwendig. Beachte, dass dort M, A und B klein geschrieben werden müssen. Diese Definition ist nur zur Darstellung gedacht, wie man eine Monade selbst definieren könnte. Die einzelnen Bestandteile werden im Folgenden definiert und erläutert.

Die folgenden Operationen sind typisch für Monaden und können für deren Definition Verwendung finden:

Die natürliche Transformation „Einheit“ oder Einheitsfunktion
```
return :: a -> m a
```
macht aus einem einzigen („reinen“) Wert einen monadischen Wert. Beispiel Liste: return macht aus einem Wert eine einelementige Liste mit genau diesem Wert. Wenn man in der Interpretation der Computerberechnungen bleibt, beschreibt die Einheitsfunktion, wie man aus einer mathematischen Berechnung eine Computerberechnung macht.
Die natürliche Transformation „Multiplikation“
```
join :: m (m a) -> m a
```
, welche ein „Abflachen“ des monadischen Typs um eine Verschachtelungsebene erlaubt. Beispiel Liste: Hier wird aus einer verschachtelten Liste eine einfache Liste gemacht. Dabei bestimmt aber die Eigenschaft „natürliche Transformation“, was zulässig ist, damit die Monadengesetze erfüllt bleiben.
Der Morphismenabbildung des Funktors M
```
fmap :: (a -> b) -> m a -> m b
```
erlaubt, einen monadischen Typ an eine Funktion zu übergeben, die nur den zugrundeliegenden Typ verwendet. Das erste Argument ist eine Funktion f, die von einem beliebigen Typ a auf einen beliebigen Typ b abbildet. Das zweite Argument ist ein monadischer Wert, dem der Typ a des Argumentes von f zugrunde liegt. Der Rückgabewert ist vom monadischen Typ, dem der Typ b des Rückgabewertes von f zugrunde liegt. fmap beschreibt, wie man „innerhalb der Monade“ rechnet. Beispiel Liste: fmap benötigt eine Funktion, die aus einem a ein b macht und gibt gleichzeitig an, wie man aus einer Liste von a eine Liste von b macht. Z. B. könnte f aus einem Int einen String machen und damit aus einer Liste von ganzen Zahlen eine Liste von Strings.
Der bind-Operator
```
(>>=) :: m a -> (a -> m b) -> m b
```
erlaubt, einen monadischen Typ an eine Funktion zu übergeben, die nur den zugrundeliegenden Typ verwendet. 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. Beispiel Liste: bind bekommt eine Liste mit Elementen des Typs a und muss als zweiten Parameter angeben, wie man aus einem einzigen Element der Eingangsliste eine Liste von Elementen des Typs b macht. Das kann z. B. durch Ignorieren des a und Verwenden von return passieren oder auch indem man bei Zahlen return verwendet und a und b miteinander verrechnet. Man kann auch das a duplizieren und dann in b umwandeln.
Der Kleisli-Operator
```
(>=>) :: (a -> m b) -> (b -> m c) -> (a -> m c)
```
realisiert eine Komposition (Hintereinanderausführung) für Funktionen, die einen monadischen Typ zurückgeben, aber nur den jeweils zugrundeliegenden Typ verwenden. Hier kann man sich am zweiten Argument für bind orientieren.

Remove ads

Monadengesetze (Auswahl)

Zusammenfassung

Kontext

Da die Monade M auch ein Funktor ist, müssen die Funktorgesetze erfüllt sein. Diese machen Aussagen über die Kompatibilität von fmap mit der Verkettung von Funktionen und der Identitätsfunktion:

Kompatibilität von Identitätsfunktion und fmap
```
fmap id == id
```
Kompatibilität von Verkettung und fmap
```
fmap (f . g) == (fmap f) . (fmap g)
```

Weiterhin sind return und join natürliche Transformationen verschiedener Funktoren aufeinander. (Wenn M ein Funktor ist, dann ist auch M (M ..) ein Funktor. Und es ist auch ein Typkonstruktor, der den abstrakten inneren Typen erhält, ein Funktor, der sog. Identitätsfunktor.) Daher erfüllen beide Funktionen die Natürlichkeitsbedingungen:

return ist eine natürliche Transformation vom Identitätsfunktor Id t = t auf M t
```
(fmap f) . return == return . f
```
join ist eine natürliche Transformation von M (M t) auf M t
```
(fmap f) . join == join . ((fmap . fmap) f)
```

Die Bind-Operation erfüllt ein Assoziativgesetz und return fungiert als Neutralelement:

„Assoziativität“ von >>=

(ma >>= f) >>= g == ma >>= ( \a -> ((f a) >>= g) )

Neutralität von return unter >>=

   ma >>= return == ma
(return a) >>= f == f a

Der Kleisli-Operator erfüllt auch ein Assoziativgesetz und auch hier ist return ein Neutralelement:

Assoziativität von >=>
```
(f >=> g) >=> h  == f >=> (g >=> h)
```
Neutralität von return unter >=>
```
f >=> return == return >=> f == f
```

Die Gesetzmäßigkeiten, die hier angegeben sind, stellen eine Auswahl dar. Da die Bind-Operation und der Kleisli-Operator hier zusätzlich zu den Funktionen fmap, return und join definiert wurden, kann man deren Gesetze auch aus den Gesetzen dieser drei Funktionen ableiten. In diesem Sinne ist der Minimalsatz der Gesetze durch die Funktorengesetze und die zwei Natürlichkeitsbedingungen gegeben.

Die Gesetze sind in Form von Gleichungen angegeben. In manchen Sprachen kann man sie formal beweisen. In Haskell oder Sprachen mit einem schwächeren Typsystem sind die Gesetze als Eigenschaftstests aufzufassen.

Remove ads

Verschiedene Definitionsmöglichkeiten über Typklassen in Haskell

Zusammenfassung

Kontext

Im Folgenden werden Beispiele präsentiert, wie man Monaden auf verschiedene Weisen in Haskell über die dort verfügbaren Typklassen definieren kann. Typklassen repräsentieren den oben genannten abstrakten Datentyp. Man muss nach ihrer Definition später sog. Instanzen der Typklasse für eine konkrete Monade definieren.

In Anlehnung an Haskell

In Haskell wird eine Monade über die Operationen return und (>>=) definiert:

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

Die anderen Operationen lassen sich dann über diese beiden definieren:

(f >=> g) a = f a >>= g
(fmap f) ma =  ma >>= (return . f)
   join mma = mma >>= id

Über den Kleisli-Operator

Eine Monade lässt sich auch über ihre Kleisli-Kategorie definieren:

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

Die übrigen Operationen ergeben sich dann wie folgt:

   ma >>= f = (id >=>  f)  ma
     fmap f =  id >=> (return . f)
       join =  id >=> id

Analog zur Kategorientheorie

In der Kategorientheorie wird eine Monade (die auch ein Funktor ist) üblicherweise über die Morphismenabbildung des Funktors fmap sowie zwei natürliche Transformationen return und join definiert:

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

Die übrigen Operationen lassen sich dann wie folgt realisieren:

   ma >>= f = (join . (fmap f)) ma
    f >=> g =  join . (fmap g) . f

Remove ads

Beziehungen zu anderen Typklassen

Jede Monade ist auch ein Applikativer Funktor und mithin auch ein Funktor. Umgekehrt gilt das nicht.

Diese Eigenschaft fand sich aus historischen Gründen nicht explizit in Haskells Standardbibliothek, der Glasgow Haskell Compiler hat dies jedoch mit Version 7.10 eingeführt.^[3]

Besonders deutlich wird diese Beziehung auch, vergleicht man die kategorientheoretische Definition mit der Funktor-Klasse in Haskell:

class Functor f where
  fmap   :: (a -> b) -> f a -> f b

Dabei muss fmap ebenfalls die Kompatibilitätsbedingung mit der Komposition (.) erfüllen.

Remove ads

Beispiele

Zusammenfassung

Kontext

Behälter

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 -> [b]) -> [b]
  liste >>= f  = concat zwischenergebnis where -- Die einzelnen Teillisten zusammenfügen
    zwischenergebnis :: [[b]]
    zwischenergebnis = map f liste -- Die Funktion auf die Liste abbilden

Die Listen-Monade kann auch unter Verwendung von Templates in C++ implementiert werden:

// g++ --std=c++17 -o template-listmonad template-listmonad.cpp
#include <iostream>
#include <list>
#include <functional>
#include <tuple>

using namespace std;

template <typename T> list<T> return_list(T t)
{
    // einelementige Liste
    return list<T>{t};
}

template <typename T> list<T> join_list(list<list<T>> ll)
{
    // Liste wird "abgeflacht"
    list<T> flattened{};
    for (auto l : ll)
        for (auto v : l)
            flattened.push_back(v);
    return flattened;
}

template <typename A, typename B> list<B> fmap_list(function<B(A)> f, list<A> as)
{
    // aus einer Liste as wird eine Liste bs, die mit Hilfe von f berechnet werden
    list<B> bs{};
    for (A a : as)
        bs.push_back(f(a));
    return bs;
}

template <typename A, typename B> list<B> bind_list(list<A> ma, function<list<B>(A)> f)
{
    // Definition der bind-Operation mit join und fmap
    return join_list(fmap_list(f, ma));
}

template <typename T> void show_list(list<T> l)
{
    for (auto v : l)
        cout << v << " ";
    cout  << endl;
}

void show_int_tuple_list(list<tuple<int, int, int>> l)
{
    for (auto v : l)
        cout << "(" << get<0>(v) << ", "
             << get<1>(v) << ", "
             << get<2>(v) << ") ";
    cout  << endl;
}

int sq(int x)  // Diese Funktion kann in fmap_list<int, int> verwendet werden
{
    return x*x;
}

list<int> five(int x)  // Diese Funktion kann in bind<int, int> verwendet werden und ignoriert die Listenelemente x
{
    return return_list(5);
}

int main(void)
{
    list<int> myints{1, 2, 3};
    list<int> myotherints{7, 8, 9, 10};

    cout << "myints: ";
    show_list<int>(myints);
    cout << "myotherints: ";
    show_list<int>(myotherints);

    list<int> squares = fmap_list<int, int>(sq, myints); // myints quadrieren
    cout << "squares: ";
    show_list<int>(squares);

    list<int> result =
    bind_list<int, int>(myints, [myotherints](int x) { return 
    bind_list<int, int>(myotherints, [x](int y) { return
                        return_list(x + 3*y); }); });
    // Hier werden aus verschiedenen int-Listen die Elemente miteinander verrechnet
    cout << "result = do\n\tx <- myints\n\ty <- myotherints\n\treturn (x + 3*y)\nresult: ";
    show_list<int>(result);
    list<tuple<int, int, int>> result2 =
    bind_list<int, tuple<int, int, int>>(myints, [myotherints](int x) { return
    bind_list<int, tuple<int, int, int>>(myotherints, [x](int y) { return
                                         return_list(tuple(x + 3*y, x, y)); }); });
    // Hier werden aus verschiedenen int-Listen die Elemente miteinander verrechnet und in eine Tupel-Liste gesteckt
    cout << "result2 = do\n\tx <- myints\n\ty <- myotherints\n\treturn (x + 3*y, x, y)\nresult2: ";
    show_int_tuple_list(result2);
    return 0;
}

Die Ausgabe ist:

myints: 1 2 3
myotherints: 7 8 9 10
squares: 1 4 9
result = do
	x <- myints
	y <- myotherints
	return (x + 3*y)
result: 22 25 28 31 23 26 29 32 24 27 30 33
result2 = do
	x <- myints
	y <- myotherints
	return (x + 3*y, x, y)
result2: (22, 1, 7) (25, 1, 8) (28, 1, 9) (31, 1, 10) (23, 2, 7) (26, 2, 8) (29, 2, 9) (32, 2, 10) (24, 3, 7) (27, 3, 8) (30, 3, 9) (33, 3, 10)

In result wird aus zwei int-Listen eine neue int-Liste berechnet und man muss dabei nur beschreiben, wie die Einzelelemente zu kombinieren sind. result2 ist ein Beispiel, wie aus int-Listen auch andere Listen (hier Tupel) berechenbar sind, wobei auch hier nur die Verarbeitung der Einzelelemente zu beschreiben ist. Alle eingegebenen Listen werden abgearbeitet und alle Elemente der entsprechenden Listen werden miteinander, ohne Bezug zur Listen-Struktur, kombiniert, wie man am Tupel-Beispiel nachvollziehen kann.

Die eigentümliche Formatierung des Codes dient zur Veranschaulichung: Die do-Notation in Haskell spart die bind-Aufrufe ein und gestattet es, die monadische Verkettung in einer imperativen Form zu schreiben.

Eine Monade beschreibt somit, wie man „in“ oder „unter“ einem Behälter/Container rechnet. Im Prinzip kann man für andere Container-Typen ähnlich vorgehen. Man muss nur Implementierungen für return, fmap und join vorgeben, welche die Monadengesetze erfüllen.

Die triviale (Identitäts-)Monade für mathematische Berechnungen

Mathematische Berechnungen mit einem „reinen“ Ergebnis können auch in eine Monade eingebettet werden. Hier ist der „höhere“ Typ der abstrakte Typ der Berechnung selbst (Man spricht von der Identitäts-Monade weil man keinen Behälter oder Container für die Werte braucht). Man macht also nicht aus einem abstrakten Typ a eine Liste von a oder ein Maybe a, sondern man lässt das a wie es ist. Damit besitzen die Monadenoperationen folgende Funktionstypen: return : a -> a, fmap : (a -> b) -> a -> b und join : a -> a. Das heißtreturn x = x (Identitätsfunktion), join x = x (auch Identitätsfunktion) und fmap f x = f x (Funktionsanwendung). Die bind-Funktion verkettet dann einfach mathematische Funktionen miteinander (Hintereinanderausführung). In C++ könnte die Implementierung so aussehen:

template <typename T> T return_id(T t)
{
    return t;
}

template <typename T> T join_id(T t)
{
    return t;
}

template <typename A, typename B> B fmap_id(function<B(A)> f, A a)
{
    return f(a);
}

template <typename A, typename B> B bind_id(A ma, function<B(A)> f)
{
    return join_id(fmap_id(f, ma));  // beachte, dass bind_id dieselbe Struktur wie bind_list hat
}

Die Anwendung erfolgt genau wie bei der Listenmonade:

// ... main ...
    int mysingleint = 4;
    int myothersingleint = 5;
    cout << "mysingleint: " << mysingleint << " myothersingleint: " << myothersingleint << endl;
    int result_id = bind_id<int, int>(
        mysingleint,
        [myothersingleint](int x) { return bind_id<int, int>(
                                     myothersingleint,
                                    [x](int y) { return return_id(x + 3*y); });
                                    });
    cout << "result_id = do\n\tx <- mysingleint\n\ty <- myothersingleint\n\treturn (x + 3*y)\nresult_id: ";
    cout << result_id << endl;

Auch hier hat man wieder die gleiche Struktur, nur dass man diesmal auf einzelnen Zahlen operiert. Die Ausgabe ist:

mysingleint: 4 myothersingleint: 5
result_id = do
	x <- mysingleint
	y <- myothersingleint
	return (x + 3*y)
result_id: 19

Demzufolge kann man auch bestimmte Operationen erst einmal auf einfachen Daten testen und hinterher einfach die zugrunde liegende Monade austauschen.

Vektoren und lineare Abbildungen

Der Typkonstruktor bildet hier 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 rein 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 syntaktischen 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

Test eines Funktorgesetzes

Hier soll demonstriert werden, wie man das Gesetz der Kompatibilität von Verkettung und fmap für eine Listen-Monade in C++ für ein einzelnes Beispiel prüft. (Dies ist allerdings ein Funktorgesetz und kein Monadengesetz.)

int gtest(int i)
{
    return i * i;
}

string ftest(int i) 
{
    stringstream ss("");
    ss << i << "(bla)";
    return ss.str();
}

int main(void)
{
    list<int> inputlist{};
    for (int i = 0; i < 5; i++)
        inputlist.push_back(i);
    cout << "inputlist:" << endl;
    show_list<int>(inputlist);
    cout << "fmap_list(ftest . gtest, inputlist): "; 
    show_list<string>(fmap_list<int, string>([](int i){ return ftest(gtest(i)); }, inputlist));
    cout << "fmap_list(ftest, fmap_list(gtest, inputlist)): ";
    show_list<string>(fmap_list<int, string>(ftest, fmap_list<int, int>(gtest, inputlist)));
    return 0;
}

Erst wird eine Liste von ganzen Zahlen quadriert (Funktion gtest) und im zweiten Schritt aus den ganzen Zahlen Strings gemacht (Funktion ftest). Für fmap_list muss es egal sein, ob man die Funktionen innen hintereinander ausführt oder die beiden fmap_list-Aufrufe hintereinander ausführt. Das wird hier geprüft. Die Ausgabe ergibt:

inputlist:
0 1 2 3 4 
fmap_list(ftest . gtest, inputlist): 0(bla) 1(bla) 4(bla) 9(bla) 16(bla) 
fmap_list(ftest, fmap_list(gtest, inputlist)): 0(bla) 1(bla) 4(bla) 9(bla) 16(bla)

Beide Ausgaben stimmen überein.

Remove ads

Andere Sprachen

LINQ-Abfrageausdrücke in C# sind direkt inspiriert von Haskells do-Notation.^[4] Ein Analogon zur Typklasse Monad ist in C# jedoch nicht ausdrückbar; der Compiler übersetzt LINQ-Abfrage-Ausdrücke blind in Aufrufe von Methoden mit festgelegten Namen. Diese sind Select und SelectMany. Auch benutzerdefinierte Klassen können also mittels LINQ-Abfrageausdrücken angesprochen werden, wenn diese Methoden mit entsprechenden Namen zur Verfügung stellen.

Dieselbe Strategie verfolgt Scala im Fall von for-Comprehensions.^[5] Die Methoden heißen da map und flatMap.

In der Standardbibliothek von Java 8 sind mindestens zwei Monaden vorhanden, die derselben Namenskonvention gehorchen: die Schnittstellen Optional und Stream definieren Methoden namens map, flatMap und of.

Remove ads