Monade (Kategorientheorie)

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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

Definition[Bearbeiten]

Eine Monade ist ein Tripel (T, \eta, \mu) aus

so dass die folgenden Bedingungen erfüllt sind:

Monad multiplication.svg
  • \mu\circ \eta T = \mu\circ T\eta = 1, d. h. das folgende Diagramm kommutiert:
Monad unit.svg

Explizit bedeutet die Kommutativität der Diagramme, dass für jedes Objekt X in K die beiden Diagramme

Monad multiplication explicit.svg und Monad unit explicit.svg

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

Algebren[Bearbeiten]

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

  • \alpha \circ \eta_A = 1_A und
  • \alpha \circ \mu_A = \alpha \circ T(\alpha)

gelten. 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).

Für beliebige Objekte X aus K 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).

Beispiele[Bearbeiten]

Dcpos[Bearbeiten]

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[Bearbeiten]

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_2K = 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_TX := X, für f \in \mathcal C(X,Y) ist F_T(f) :=\eta_Y \circ f. G_TX := 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^TX := (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.

Listen[Bearbeiten]

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

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

Die Aussagen der Axiome lassen sich entsprechend auf das Listenbeispiel übertragen:

  1. Wird das Axiom \mu T \mu = \mu \mu T auf das Beispiel angewandt, ergibt sich für eine Menge X zunächst \mu \circ \mu_{T(X)} = \mu \circ T(\mu_X). Auf das Listenbeispiel übertragen ergibt sich für l \in T(T(T(X))) auch \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 \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 F,G (wie oben) zwischen den Kategorien der Mengen bzw. Halbgruppen. F ordnet einer Menge die freie Halbgruppe über dieser Menge zu, G einer Halbgruppe die zugrunde liegende Menge.

Anwendung[Bearbeiten]

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 Nebenwirkungen freie Sprache verwendet werden. Siehe dazu auch Monade (Informatik).

Literatur[Bearbeiten]

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

Weblinks[Bearbeiten]