Monade (Kategorientheorie)
# Monade (Kategorientheorie)

Eine Monade ist im mathematischen Teilgebiet der Kategorientheorie eine Struktur, die gewisse formale Ähnlichkeit mit den Monoiden der Algebra aufweist.

## Definition

Eine Monade ist ein Tripel $(T,\eta ,\mu )$ aus
* einem Funktor $T$ von einer Kategorie ${\mathcal {C}}$ in sich selbst, das heißt
    $T\colon {\mathcal {C}}\to {\mathcal {C}}$
* einer natürlichen Transformation $\eta \colon 1_{\mathcal {C}}\to T$ (dabei steht $1_{\mathcal {C}}$ für den Identitätsfunktor ${\mathcal {C}}\to {\mathcal {C}}$)
* einer natürlichen Transformation $\mu \colon T^{2}\to T$ (dabei steht $T^{2}$ für $T\circ T$),
so dass die folgenden Bedingungen, die man auch die Axiome der Monade nennt, erfüllt sind:
* $\mu \circ T\mu =\mu \circ \mu T$, das heißt das folgende Diagramm kommutiert:
* $\mu \circ \eta T=\mu \circ T\eta =1$, das heißt das folgende Diagramm kommutiert:
Explizit bedeutet die Kommutativität der Diagramme, dass für jedes Objekt $X$ in ${\mathcal {C}}$ die beiden Diagramme
    und
kommutieren. Dabei sind $T\mu$ und $\mu T$ die durch $(T\mu )_{X}\colon =T(\mu _{X})$ und $(\mu T)_{X}:=\mu _{T(X)}$ definierten natürlichen Transformationen, entsprechendes gilt für $T\eta$ und $\eta T$. Die natürlichen Transformationen $\eta$ und $\mu$ nennt man auch Einheit und Multiplikation der Monade.

## Beispiel Listen

Ein Beispiel für eine Monade sind Listen. Es bezeichne $[x_{1},\dotsc ,x_{n}]$ die Liste mit den Elementen $x_{1}$ bis $x_{n}$, wobei mit $n=0$ auch die leere Liste zugelassen ist. Listen sind Tupel, die wir hier der Übersichtlichkeit wegen mit eckigen Klammen schreiben. Das folgende Tripel $(T,\eta ,\mu )$ ist eine Monade in der Kategorie der Mengen $\mathbf {Set}$:
Der Listen-Funktor
* Für ein Objekt $X$ aus $\mathbf {Set}$, das heißt für eine Menge $X$, sei $T(X)=\{[x_{1},\dotsc ,x_{n}]\mid n\in \mathbb {N} ,x_{1},\dotsc ,x_{n}\in X\}$ die Menge aller endlichen Listen, deren Elemente aus $X$ kommen.
* Für eine Abbildung $f\colon X\to Y$ zwischen zwei Mengen sei $T(f)\colon T(X)\to T(Y)$ zwischen den Listenmengen durch $T(f)([x_{1},\dotsc ,x_{n}])=[f(x_{1}),\dotsc ,f(x_{n})]$ definiert.
Einheit und Multiplikation
* Die Einheit $\eta$ sei definiert durch $\eta _{X}(x)=[x]$, das ist die Konstruktion einelementiger Listen.
* Die Multiplikation ist die Konkatenation von Listen: $\mu _{X}([l_{1},\dotsc ,l_{n}])=l_{1}\dotsm l_{n}$, also $\mu _{X}([[x_{11},\dotsc ,x_{1m_{1}}],\dotsc ,[x_{n1},\dotsc ,x_{nm_{n}}]])=[x_{11},\dotsc ,x_{1m_{1}},\dotsc ,x_{n1},\dotsc ,x_{nm_{n}}]$ – dies ist gewissermaßen das (einstufige) Zusammenfügen einer Liste von Listen zu einer Liste.
Diese Daten erfüllen die Definition der Monade.
* Die Gleichung $\mu \circ T\mu =\mu \circ \mu T$ bedeutet für eine Liste von Listen von Listen $l\in T(T(T(X)))$, dass $\mu _{X}(T(\mu _{X})(l))=\mu _{X}(\mu _{T(X)}(l))$, das heißt, dass es bei mehrfach verschachtelten Listen egal ist, ob diese von innen oder von außen beginnend zu einer zusammengefügt werden. Betrachte zum Beispiel $l=[[[x,y],[x]],[[x,y,z],[x,x]]]$, wobei $x,y,z\in X$ seien. Das ist die Liste der beiden Listen von Listen $[[x,y],[x]]$ und $[[x,y,z],[x,x]]$, die ihrerseits aus den Listen $[x,y]$ und $[x]$ bzw. $[x,y,z]$ und $[x,x]$ bestehen. Dann ist
    $\mu _{X}(T(\mu _{X})(l))=\mu _{X}([[x,y,x],[x,y,z,x,x]])=[x,y,x,x,y,z,x,x]$ und
    $\mu _{X}(\mu _{T(X)}(l))=\mu _{X}([[x,y],[x],[x,y,z],[x,x]])=[x,y,x,x,y,z,x,x]$.
* Das zweite Axiom besagt in diesem Beispiel, dass jede Liste durch Zusammenfügen einelementiger Listen entsteht:
    $\mu _{X}(\eta _{T(X)}([x_{1},\dotsc ,x_{n}]))=\mu _{X}([[x_{1},\dotsc ,x_{n}]])=[x_{1},\dotsc ,x_{n}]=\mu _{X}([[x_{1}],\dotsc ,[x_{n}]])=\mu _{X}(T(\eta _{X})([x_{1},\dotsc ,x_{n}]))$.
In einer algebraischen Sichtweise ist $T(X)$ die unterliegende Menge des freien Monoids über $X$. Die Einheit $\eta _{X}$ bettet das Erzeugendensystem in den Monoid ein, die Multiplikation $\mu _{X}$ ist die Monoidmultiplikation.

## Eilenberg-Moore-Algebren

Ist $(T\colon {\mathcal {C}}\to {\mathcal {C}},\eta ,\mu )$ eine Monade, so ist ein Paar $(A,\alpha \colon T(A)\to A)$ eine Eilenberg-Moore-Algebra (auch einfach nur Algebra genannt) für diese Monade, wenn die Gleichungen
* $\alpha \circ \eta _{A}=1_{A}$ und
* $\alpha \circ \mu _{A}=\alpha \circ T(\alpha )$
gelten, das heißt, wenn die folgenden beiden Diagramme kommutieren:
Ein Homomorphismus von $(A,\alpha )$ nach $(B,\beta )$ ist ein Pfeil $h\colon A\to B$ in $K$ mit $h\circ \alpha =\beta \circ T(h)$, das heißt, dass nachstehendes Diagramm kommutiert:
Für beliebige Objekte $X$ aus ${\mathcal {C}}$ ist daher z. B. $(T(X),\mu _{X})$ eine Algebra, und $\mu _{X}$ ist ein Homomorphismus von $(T(T(X)),\mu _{T(X)})$ nach $(T(X),\mu _{X})$. Im obigen Beispiel der Listen sind die Algebren $(A,\alpha \colon TA\to A)$ genau die Monoide $A$ und $\alpha$ multipliziert alle Elemente der Liste.
Die Eilenberg-Moore-Algebren zur Monade $T$ bilden mit den angegebenen Homomorphismen eine Kategorie, die man die Kategorie der $T$-Algebren nennt und mit ${\mathcal {C}}^{T}$ bezeichnet. Im Falle der Listen-Monade $T$ ist also $\mathbf {Set} ^{T}$ die Kategorie der Monoide.

## Weitere Beispiele
### Linearkombinationen

Es sei $K$ ein Körper. Legt man für Mengen $X$ fest, dass $L(X):=\{v\colon X\to K\mid v^{-1}(K\setminus \{0\}){\text{ endlich}}\}$ sei, also (eine Kodierung für) die Menge der formalen $K$-Linearkombinationen von Elementen von $X$, lässt sich $L$ als Objektabbildung eines Funktors $L\colon \mathbf {Set} \to \mathbf {Set}$ auffassen, dessen Pfeilabbildung einer Funktion $f\colon X\to Y$ die Funktion $L(f)\colon L(X)\to L(Y)$, mit $L(f)(v)(y):=\sum _{x\in f^{-1}(\{y\})}v(x)$, zuordnet. $L(X)$ trägt eine naheliegende Vektorraumstruktur: Für $\lambda \in K$ und $v\in L(X)$ ist $\lambda \cdot v$, definiert durch $(\lambda \cdot v)(x):=\lambda \cdot v(x)$, wieder Element von $L(X)$, und für $v,w\in L(X)$ ist $v+w$, definiert durch $(v+w)(x):=v(x)+w(x)$, ebenfalls wieder Element von $L(X)$.
Der Funktor $L$ wird zusammen mit den Festlegungen
* $\eta _{X}(x)(y):={\begin{cases}1&x=y\\0&{\text{sonst}}\end{cases}}$
* $\mu _{X}(l):=\sum _{v\in l^{-1}(K\setminus \{0\})}l(v)\cdot v$
    (hier verwenden wir der Übersichtlichkeit halber $+$ und $\cdot$ aus dem vorangegangenen Satz)
zu einer Monade $\mathbf {Set} \to \mathbf {Set}$. $\mu _{X}$ berechnet dabei auf naheliegende Weise aus einer Linearkombination von Linearkombinationen von Elementen von $X$ die entsprechende Zusammenfassung als Linearkombination von Elementen von $X$.
Die Algebren der Monade $(L,\eta ,\mu )$ sind gerade $K$-Vektorräume, in der zur Monade gehörenden Kleisli-Kategorie sind die Pfeile $X\to Y$ gerade (Mengen-indizierte) $X$-$Y$-Matrizen, die sich als Codes für lineare Abbildungen vom freien Vektorraum über $X$ zum freien Vektorraum über $Y$ auffassen lassen.

### Dcpos

Der Endofunktor $\mathrm {Idl} \colon \mathbf {Pos} \to \mathbf {Pos}$ auf der Kategorie der partiell geordneten Mengen und monotonen Abbildungen ordne jedem $(A,\leq )$ die partiell geordnete Menge $(\mathrm {Idl} (A),\subseteq )$ der Ordnungsideale in $A$ zu. Seine Wirkung auf monotonen Abbildungen $f\colon A\to B$ sei $\mathrm {Idl} (f)\colon I\mapsto {\downarrow }\{f(a)\mid a\in I\}$. Für eine partiell geordnete Menge $X$ und eine Teilmenge $U\subseteq X$ ist hierbei ${\downarrow }U:=\{x\in X\mid \exists u\in U.\ x\leq u\}$.
Die Abbildungsfamilien $\mu _{A}\colon {\mathcal {I}}\mapsto \bigcup {\mathcal {I}}$ und $\eta _{A}\colon a\mapsto {\downarrow }\{a\}$ ergänzen den Funktor $\mathrm {Idl}$ zu einer Monade.
Die Strukturabbildung $\alpha$ einer $\mathrm {Idl}$-Algebra $(A,\alpha \colon \mathrm {Idl} (A)\to A)$ ist nun gerade $I\mapsto \sup I$. Jedes Ideal in $A$ (und somit jede gerichtete Teilmenge) hat also ein Supremum in $A$. Das heißt, eine $\mathrm {Idl}$-Algebra ist dasselbe wie eine Dcpo. Ein Homomorphismus von $\mathrm {Idl}$-Algebren ist eine Scott-stetige Abbildung.

## Adjungierte Funktoren

Ist ein Funktor $F\colon {\mathcal {C}}\to {\mathcal {D}}$ zu einem Funktor $G\colon {\mathcal {D}}\to {\mathcal {C}}$ linksadjungiert, und sind
    $\eta \colon 1_{\mathcal {C}}\to GF$ bzw. $\varepsilon \colon FG\to 1_{\mathcal {D}}$
Einheit bzw. Koeinheit der Adjunktion, so ist $(T,\eta ,\mu )$ mit
* $T=GF\colon {\mathcal {C}}\to {\mathcal {C}}$
* $\mu =G\varepsilon F,$ also $\mu _{X}=G(\varepsilon _{F(X)})$ für Objekte $X\in \mathrm {Ob} ({\mathcal {C}})$
eine Monade.
Dies ist im gewissen Sinn auch schon das einzige Beispiel, da jede Monade auf diese Weise entsteht, jedenfalls bis auf Isomorphie: Die Tripel $({\mathcal {D}},F,G)$ mit $F\colon {\mathcal {C}}\to {\mathcal {D}}$, $G\colon {\mathcal {D}}\to {\mathcal {C}}$, $GF=T$ und $F\dashv G$ sind Objekte einer Kategorie ${\mathfrak {A}}$. In dieser Kategorie ist ein Morphismus von $({\mathcal {D}}_{1},F_{1},G_{1})$ nach $({\mathcal {D}}_{2},F_{2},G_{2})$ ein Funktor $K\colon {\mathcal {D}}_{1}\to {\mathcal {D}}_{2}$, für den $KF_{1}=F_{2}$ und $G_{2}K=G_{1}$ gelten.
Anfangsobjekt in ${\mathfrak {A}}$ ist $({\mathcal {C}}_{T},F_{T},G_{T})$, wobei ${\mathcal {C}}_{T}$ die Kleisli-Kategorie zu $T$ ist. $F_{T}X:=X$, für $f\in {\mathcal {C}}(X,Y)$ ist $F_{T}(f):=\eta _{Y}\circ f$. $G_{T}X:=TX$, für $f\in {\mathcal {C}}_{T}(X,Y)$ ist $G_{T}(f):=\mu _{Y}\circ T(f)$.
Endobjekt in ${\mathfrak {A}}$ ist $({\mathcal {C}}^{T},F^{T},G^{T})$ wobei ${\mathcal {C}}^{T}$ die Kategorie der Eilenberg-Moore-Algebren zu $T$ ist. $F^{T}X:=(TX,\mu _{X})$, für $f\in {\mathcal {C}}(X,Y)$ ist $F^{T}(f):=T(f)$. $G^{T}(X,\alpha ):=X$, $G^{T}(f):=f$.
Für eine vorgegebene Adjunktion $F\dashv G$ gibt es daher eindeutig existierende Funktoren $J$ und $K$ wie im nachfolgenden Diagramm, so dass die oben genannten Gleichungen bestehen, das heißt $JF_{T}=F$, $GJ=G_{T}$, $KF=F^{T}$ und $G^{T}K=G$
Den Funktor $K$ nennt man auch den Vergleichsfunktor, weil der die Kategorie ${\mathcal {D}}$ mit einer Kategorie von Algebren vergleicht. Man nennt die Adjunktion $F\dashv G$ monadisch, wenn der Vergleichsfunktor eine Äquivalenz ${\mathcal {D}}\simeq {\mathcal {C}}^{T}$ ist. Man nennt einen Funktor $G$ monadisch, wenn es eine Linksadjungierte $F$ gibt, so dass die Adjunktion $F\dashv G$ monadisch ist.

## Anwendung in der Informatik

Monaden werden in der Informatik, besonders in funktionalen Programmiersprachen u. a. zur Abstraktion von Nebeneffekten verwendet. Es ist Haskell hervorzuheben, wo Monaden zur Integration von Ein- und Ausgabe in die sonst komplett von Seiteneffekten freie Sprache verwendet werden. Siehe dazu auch Monade (Informatik).