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 T(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 T(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).

Weblinks

• Lektion zu Monaden
• You Could Have Invented Monads! (And Maybe You Already Have.)
• Mehrteiliger Videokurs für Mathematiker (englisch)