Monade (Kategorientheorie)

Eine Monade i​st im mathematischen Teilgebiet d​er Kategorientheorie e​ine Struktur, d​ie gewisse formale Ähnlichkeit m​it den Monoiden d​er Algebra aufweist.

Definition

Eine Monade ist ein Tripel ${\displaystyle (T,\eta ,\mu )}$ aus

• einem Funktor T von einer Kategorie K in sich selbst, d. h.

  ${\displaystyle T\colon K\to K}$

• einer natürlichen Transformation ${\displaystyle \eta \colon 1_{K}\to T}$ (dabei steht ${\displaystyle 1_{K}}$ für den Identitätsfunktor ${\displaystyle K\to K}$)
• einer natürlichen Transformation ${\displaystyle \mu \colon T^{2}\to T}$ (dabei steht ${\displaystyle T^{2}}$ für ${\displaystyle T\circ T}$),

so d​ass die folgenden Bedingungen erfüllt sind:

• ${\displaystyle \mu \circ T\mu =\mu \circ \mu T}$, d. h. das folgende Diagramm kommutiert:

• ${\displaystyle \mu \circ \eta T=\mu \circ T\eta =1}$, d. h. das folgende Diagramm kommutiert:

Explizit bedeutet die Kommutativität der Diagramme, dass für jedes Objekt ${\displaystyle X}$ in ${\displaystyle K}$ die beiden Diagramme

und

kommutieren. Die erste Bedingung ist analog zum Assoziativgesetz bei Monoiden, die zweite zur Existenz eines neutralen Elementes.

Algebren

Ist ${\displaystyle (T\colon K\to K,\eta ,\mu )}$ eine Monade, so ist ein Paar ${\displaystyle (A,\alpha \colon T(A)\to A)}$ eine (Eilenberg-Moore-)Algebra für diese Monade, wenn

• ${\displaystyle \alpha \circ \eta _{A}=1_{A}}$ und
• ${\displaystyle \alpha \circ \mu _{A}=\alpha \circ T(\alpha )}$

gelten. Ein Homomorphismus von ${\displaystyle (A,\alpha )}$ nach ${\displaystyle (B,\beta )}$ ist ein Pfeil ${\displaystyle h\colon A\to B}$ in ${\displaystyle K}$ mit ${\displaystyle h\circ \alpha =\beta \circ T(h)}$.

Für beliebige Objekte ${\displaystyle X}$ aus ${\displaystyle K}$ ist daher z. B. ${\displaystyle (T(X),\mu _{X})}$ eine Algebra, und ${\displaystyle \mu _{X}}$ ist ein Homomorphismus von ${\displaystyle (T(T(X)),\mu _{T(X)})}$ nach ${\displaystyle (T(X),\mu _{X})}$.

Beispiele

Dcpos

Der Endofunktor ${\displaystyle \mathrm {Idl} \colon \mathbf {Pos} \to \mathbf {Pos} }$ auf der Kategorie der partiell geordneten Mengen und monotonen Abbildungen ordne jedem ${\displaystyle (A,\leq )}$ die partiell geordnete Menge ${\displaystyle (\mathrm {Idl} (A),\subseteq )}$ der Ordnungsideale in ${\displaystyle A}$ zu. Seine Wirkung auf monotonen Abbildungen ${\displaystyle f\colon A\to B}$ sei ${\displaystyle \mathrm {Idl} (f)\colon I\mapsto {\downarrow }\{f(a)\mid a\in I\}}$. Für eine partiell geordnete Menge ${\displaystyle X}$ und eine Teilmenge ${\displaystyle U\subseteq X}$ ist hierbei ${\displaystyle {\downarrow }U:=\{x\in X\mid \exists u\in U.\ x\leq u\}}$.

Die Abbildungsfamilien ${\displaystyle \mu _{A}\colon {\mathcal {I}}\mapsto \bigcup {\mathcal {I}}}$ und ${\displaystyle \eta _{A}\colon a\mapsto {\downarrow }\{a\}}$ ergänzen den Funktor ${\displaystyle \mathrm {Idl} }$ zu einer Monade.

Die Strukturabbildung ${\displaystyle \alpha }$ einer ${\displaystyle \mathrm {Idl} }$-Algebra ${\displaystyle (A,\alpha \colon \mathrm {Idl} (A)\to A)}$ ist nun gerade ${\displaystyle I\mapsto \sup I}$. Jedes Ideal in ${\displaystyle A}$ (und somit jede gerichtete Teilmenge) hat also ein Supremum in ${\displaystyle A}$. Das heißt, eine ${\displaystyle \mathrm {Idl} }$-Algebra ist dasselbe wie eine Dcpo. Ein Homomorphismus von ${\displaystyle \mathrm {Idl} }$-Algebren ist eine Scott-stetige Abbildung.

Adjungierte Funktoren

Ist ein Funktor ${\displaystyle F\colon {\mathcal {C}}\to {\mathcal {D}}}$ zu einem Funktor ${\displaystyle G\colon {\mathcal {D}}\to {\mathcal {C}}}$ linksadjungiert, und sind

${\displaystyle \eta \colon 1_{\mathcal {C}}\to GF}$ bzw. ${\displaystyle \varepsilon \colon FG\to 1_{\mathcal {D}}}$

Einheit bzw. Koeinheit der Adjunktion, so ist ${\displaystyle (T,\eta ,\mu )}$ mit

• ${\displaystyle T=GF\colon {\mathcal {C}}\to {\mathcal {C}}}$
• ${\displaystyle \mu =G\varepsilon F,}$ also ${\displaystyle \mu _{X}=G(\varepsilon _{F(X)})}$ für Objekte ${\displaystyle 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 ${\displaystyle ({\mathcal {D}},F,G)}$ mit ${\displaystyle F\colon {\mathcal {C}}\to {\mathcal {D}}}$, ${\displaystyle G\colon {\mathcal {D}}\to {\mathcal {C}}}$, ${\displaystyle GF=T}$ und ${\displaystyle F\dashv G}$ sind Objekte einer Kategorie ${\displaystyle {\mathfrak {A}}}$. In dieser Kategorie ist ein Morphismus von ${\displaystyle ({\mathcal {D}}_{1},F_{1},G_{1})}$ nach ${\displaystyle ({\mathcal {D}}_{2},F_{2},G_{2})}$ ein Funktor ${\displaystyle K\colon {\mathcal {D}}_{1}\to {\mathcal {D}}_{2}}$, für den ${\displaystyle KF_{1}=F_{2}}$ und ${\displaystyle G_{2}K=G_{1}}$ gelten.

Anfangsobjekt in ${\displaystyle {\mathfrak {A}}}$ ist ${\displaystyle ({\mathcal {C}}_{T},F_{T},G_{T})}$, wobei ${\displaystyle {\mathcal {C}}_{T}}$ die Kleisli-Kategorie zu ${\displaystyle T}$ ist. ${\displaystyle F_{T}X:=X}$, für ${\displaystyle f\in {\mathcal {C}}(X,Y)}$ ist ${\displaystyle F_{T}(f):=\eta _{Y}\circ f}$. ${\displaystyle G_{T}X:=TX}$, für ${\displaystyle f\in {\mathcal {C}}_{T}(X,Y)}$ ist ${\displaystyle G_{T}(f):=\mu _{Y}\circ T(f)}$.

Endobjekt in ${\displaystyle {\mathfrak {A}}}$ ist ${\displaystyle ({\mathcal {C}}^{T},F^{T},G^{T})}$ wobei ${\displaystyle {\mathcal {C}}^{T}}$ die Kategorie der Eilenberg-Moore-Algebren zu ${\displaystyle T}$ ist. ${\displaystyle F^{T}X:=(TX,\mu _{X})}$, für ${\displaystyle f\in {\mathcal {C}}(X,Y)}$ ist ${\displaystyle F^{T}(f):=T(f)}$. ${\displaystyle G^{T}(X,\alpha ):=X}$, ${\displaystyle G^{T}(f):=f}$.

Listen

Ein Beispiel für eine Monade sind Listen. Wenn ${\displaystyle [x_{1},\dotsc ,x_{n}]}$ die Liste mit den Elementen ${\displaystyle x_{1}}$ bis ${\displaystyle x_{n}}$ bezeichnet, dann stellt das folgende Tripel ${\displaystyle (T,\eta ,\mu )}$ eine Monade über der Kategorie der Mengen dar:

1. Listen-Funktor:
   • Auf der Objektebene ergibt ${\displaystyle T(X)=\{[x_{1},\dotsc ,x_{n}]\mid n\in \mathbb {N} ,x_{1},\dotsc ,x_{n}\in X\}}$ die Menge aller Listen, deren Elemente aus ${\displaystyle X}$ kommen, für eine beliebige Menge ${\displaystyle X}$.
   • Für eine Abbildung ${\displaystyle f\colon X\to Y}$ zwischen zwei Mengen ergibt ${\displaystyle T}$ die entsprechende Abbildung ${\displaystyle T(f)\colon T(X)\to T(Y)}$ zwischen den Listenmengen mit ${\displaystyle T(f)([x_{1},\dotsc ,x_{n}])=[f(x_{1}),\dotsc ,f(x_{n})]}$
2. Konstruktor für einelementige Listen: ${\displaystyle \eta _{X}(x)=[x]}$
3. Konkatenation von Listen: ${\displaystyle \mu _{X}([l_{1},\dotsc ,l_{n}])=l_{1}\dotsm l_{n}}$, also ${\displaystyle \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) Flachklopfen einer Liste von Listen.

Die Aussagen d​er Axiome lassen s​ich entsprechend a​uf das Listenbeispiel übertragen:

1. Wird das Axiom ${\displaystyle \mu T\mu =\mu \mu T}$ auf das Beispiel angewandt, ergibt sich für eine Menge ${\displaystyle X}$ zunächst ${\displaystyle \mu \circ \mu _{T(X)}=\mu \circ T(\mu _{X})}$. Auf das Listenbeispiel übertragen ergibt sich für ${\displaystyle l\in T(T(T(X)))}$ auch ${\displaystyle \mu _{X}(\mu _{T(X)}(l))=\mu _{X}(T(\mu _{X})(l))}$, d. h., dass es bei mehrfach verschachtelten Listen egal ist, ob von innen oder von außen flachgeklopft wird, was bei Listen offensichtlich erfüllt ist.
2. Das zweite Axiom sagt in diesem Beispiel aus, dass es beim Hinzufügen einer Listenebene egal ist, ob dies innen oder außen passiert, sofern danach flachgeklopft wird – es ist ${\displaystyle \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}]))}$.

Diese Monade gehört zu einem adjungierten Funktorpaar ${\displaystyle F,G}$ (wie oben) zwischen den Kategorien der Mengen bzw. Halbgruppen. ${\displaystyle F}$ ordnet einer Menge die freie Halbgruppe über dieser Menge zu, ${\displaystyle G}$ einer Halbgruppe die zugrunde liegende Menge.

Anwendung

Monaden werden i​n der Informatik, besonders i​n funktionalen Programmiersprachen u. a. z​ur Abstraktion v​on Nebeneffekten verwendet. Es i​st Haskell hervorzuheben, w​o Monaden z​ur Integration v​on Ein- u​nd Ausgabe i​n die s​onst komplett v​on Seiteneffekten f​reie Sprache verwendet werden. Siehe d​azu auch Monade (Informatik).

Literatur

• Saunders Mac Lane, Categories for the Working Mathematician. Springer-Verlag, Berlin 1971. ISBN 3-540-90035-7

Weblinks

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