Monad (category theory)

In the mathematical branch of category theory, a monad is a structure that has a certain formal similarity to the monoids of algebra .

definition

A monad is a triple of ${\ displaystyle (T, \ eta, \ mu)}$

a functor T of category K in itself, d. H.
${\ displaystyle T \ colon K \ to K}$
a natural transformation (where stands for the identity function ) ${\ displaystyle \ eta \ colon 1_ {K} \ to T}$ ${\ displaystyle 1_ {K}}$ ${\ displaystyle K \ to K}$
a natural transformation (where stands for ), ${\ displaystyle \ mu \ colon T ^ {2} \ to T}$ ${\ displaystyle T ^ {2}}$ ${\ displaystyle T \ circ T}$

so that the following conditions are met:

${\ displaystyle \ mu \ circ T \ mu = \ mu \ circ \ mu T}$ , d. H. the following diagram commutates :

${\ displaystyle \ mu \ circ \ eta T = \ mu \ circ T \ eta = 1}$ , d. H. the following diagram commutates:

Explicitly means the commutativity of the diagrams that for each object in the two diagrams ${\ displaystyle X}$ ${\ displaystyle K}$

and

commute. The first condition is analogous to the associative law for monoids, the second to the existence of a neutral element.

Algebras

If a monad, then a pair is an (Eilenberg-Moore) algebra for this monad, if ${\ displaystyle (T \ colon K \ to K, \ eta, \ mu)}$ ${\ displaystyle (A, \ alpha \ colon T (A) \ to A)}$

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

be valid. A homomorphism from to is an arrow in with . ${\ displaystyle (A, \ alpha)}$ ${\ displaystyle (B, \ beta)}$ ${\ displaystyle h \ colon A \ to B}$ ${\ displaystyle K}$ ${\ displaystyle h \ circ \ alpha = \ beta \ circ T (h)}$

For any objects from z. B. an algebra, and is a homomorphism from to . ${\ displaystyle X}$ ${\ displaystyle K}$ ${\ displaystyle (T (X), \ mu _ {X})}$ ${\ displaystyle \ mu _ {X}}$ ${\ displaystyle (T (T (X)), \ mu _ {T (X)})}$ ${\ displaystyle (T (X), \ mu _ {X})}$

Examples

Dcpos

The endofunctor on the category of the partially ordered sets and monotonous mappings assign to each the partially ordered set of the order ideals in . Its effect on monotone pictures is . For a partially ordered set and a subset , here is . ${\ displaystyle \ mathrm {Idl} \ colon \ mathbf {Pos} \ to \ mathbf {Pos}}$ ${\ displaystyle (A, \ leq)}$ ${\ displaystyle (\ mathrm {Idl} (A), \ subseteq)}$ ${\ displaystyle A}$ ${\ displaystyle f \ colon A \ to B}$ ${\ displaystyle \ mathrm {Idl} (f) \ colon I \ mapsto {\ downarrow} \ {f (a) \ mid a \ in I \}}$ ${\ displaystyle X}$ ${\ displaystyle U \ subseteq X}$ ${\ displaystyle {\ downarrow} U: = \ {x \ in X \ mid \ exists u \ in U. \ x \ leq u \}}$

The illustration families and complete the functor to a monad. ${\ displaystyle \ mu _ {A} \ colon {\ mathcal {I}} \ mapsto \ bigcup {\ mathcal {I}}}$ ${\ displaystyle \ eta _ {A} \ colon a \ mapsto {\ downarrow} \ {a \}}$ ${\ displaystyle \ mathrm {Idl}}$

The structure mapping of an algebra is now straight . Every ideal in (and thus every directed subset ) has a supremum in . That is, an algebra is the same as a Dcpo . A homomorphism of algebras is a Scott continuous map. ${\ displaystyle \ alpha}$ ${\ displaystyle \ mathrm {Idl}}$ ${\ displaystyle (A, \ alpha \ colon \ mathrm {Idl} (A) \ to A)}$ ${\ displaystyle I \ mapsto \ sup I}$ ${\ displaystyle A}$ ${\ displaystyle A}$ ${\ displaystyle \ mathrm {Idl}}$ ${\ displaystyle \ mathrm {Idl}}$

Adjoint functors

Is a functor left adjoint to a functor , and are ${\ displaystyle F \ colon {\ mathcal {C}} \ to {\ mathcal {D}}}$ ${\ displaystyle G \ colon {\ mathcal {D}} \ to {\ mathcal {C}}}$

{\ displaystyle \ eta \ colon 1 _ {\ mathcal {C}} \ to GF}

or.

{\ displaystyle \ varepsilon \ colon FG \ to 1 _ {\ mathcal {D}}}

Unity or co-unity of the adjunction, so is with ${\ displaystyle (T, \ eta, \ mu)}$

${\ displaystyle T = GF \ colon {\ mathcal {C}} \ to {\ mathcal {C}}}$
${\ displaystyle \ mu = G \ varepsilon F,}$ so for objects ${\ displaystyle \ mu _ {X} = G (\ varepsilon _ {F (X)})}$ ${\ displaystyle X \ in \ mathrm {Ob} ({\ mathcal {C}})}$

a monad.

This is already the only example, as each monad arises in a certain sense in this way, at least up to isomorphism: The triples with , , and are objects of a category . In this category, a morphism from to is a functor for which and hold. ${\ displaystyle ({\ mathcal {D}}, F, G)}$ ${\ displaystyle F \ colon {\ mathcal {C}} \ to {\ mathcal {D}}}$ ${\ displaystyle G \ colon {\ mathcal {D}} \ to {\ mathcal {C}}}$ ${\ displaystyle GF = T}$ ${\ displaystyle F \ dashv G}$ ${\ displaystyle {\ mathfrak {A}}}$ ${\ displaystyle ({\ mathcal {D}} _ {1}, F_ {1}, G_ {1})}$ ${\ displaystyle ({\ mathcal {D}} _ {2}, F_ {2}, G_ {2})}$ ${\ displaystyle K \ colon {\ mathcal {D}} _ {1} \ to {\ mathcal {D}} _ {2}}$ ${\ displaystyle KF_ {1} = F_ {2}}$ ${\ displaystyle G_ {2} K = G_ {1}}$

Beginning object is , where the Kleisli category to be. , for is . , for is . ${\ displaystyle {\ mathfrak {A}}}$ ${\ displaystyle ({\ mathcal {C}} _ {T}, F_ {T}, G_ {T})}$ ${\ displaystyle {\ mathcal {C}} _ {T}}$ ${\ displaystyle T}$ ${\ displaystyle F_ {T} X: = X}$ ${\ displaystyle f \ in {\ mathcal {C}} (X, Y)}$ ${\ displaystyle F_ {T} (f): = \ eta _ {Y} \ circ f}$ ${\ displaystyle G_ {T} X: = TX}$ ${\ displaystyle f \ in {\ mathcal {C}} _ {T} (X, Y)}$ ${\ displaystyle G_ {T} (f): = \ mu _ {Y} \ circ T (f)}$

End object in is where the Eilenberg-Moore algebras category is closed. , for is . , . ${\ displaystyle {\ mathfrak {A}}}$ ${\ displaystyle ({\ mathcal {C}} ^ {T}, F ^ {T}, G ^ {T})}$ ${\ displaystyle {\ mathcal {C}} ^ {T}}$ ${\ displaystyle T}$ ${\ displaystyle F ^ {T} X: = (TX, \ mu _ {X})}$ ${\ displaystyle f \ in {\ mathcal {C}} (X, Y)}$ ${\ displaystyle F ^ {T} (f): = T (f)}$ ${\ displaystyle G ^ {T} (X, \ alpha): = X}$ ${\ displaystyle G ^ {T} (f): = f}$

Lists

An example of a monad are lists. If the list is labeled with the elements to , then the following triple represents a monad above the category of sets : ${\ displaystyle [x_ {1}, \ dotsc, x_ {n}]}$ ${\ displaystyle x_ {1}}$ ${\ displaystyle x_ {n}}$ ${\ displaystyle (T, \ eta, \ mu)}$

List functor:

At the object level, results in the set of all lists, the elements of which come from , for any set . ${\ displaystyle T (X) = \ {[x_ {1}, \ dotsc, x_ {n}] \ mid n \ in \ mathbb {N}, x_ {1}, \ dotsc, x_ {n} \ in X \}}$ ${\ displaystyle X}$ ${\ displaystyle X}$
For a mapping between two sets, the corresponding mapping between the list sets results in ${\ displaystyle f \ colon X \ to Y}$ ${\ displaystyle T}$ ${\ displaystyle T (f) \ colon T (X) \ to T (Y)}$ ${\ displaystyle T (f) ([x_ {1}, \ dotsc, x_ {n}]) = [f (x_ {1}), \ dotsc, f (x_ {n})]}$

Constructor for single-element lists :

{\ displaystyle \ eta _ {X} (x) = [x]}

Concatenation of lists :so- this is in a way the (single-stage) flat knock a list of lists. ${\ displaystyle \ mu _ {X} ([l_ {1}, \ dotsc, l_ {n}]) = l_ {1} \ dotsm l_ {n}}$ ${\ 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}}]}$

The statements of the axioms can be transferred accordingly to the list example:

If the axiom applied to the example, the result for a lot at first . Transferred to the list of example arises for also , d. This means that in the case of lists that are nested several times, it does not matter whether they are knocked flat from the inside or the outside, which is obviously the case with lists. ${\ displaystyle \ mu T \ mu = \ mu \ mu T}$ ${\ displaystyle X}$ ${\ displaystyle \ mu \ circ \ mu _ {T (X)} = \ mu \ circ T (\ mu _ {X})}$ ${\ displaystyle l \ in T (T (T (X)))}$ ${\ displaystyle \ mu _ {X} (\ mu _ {T (X)} (l)) = \ mu _ {X} (T (\ mu _ {X}) (l))}$
The second axiom says in this example that when adding a list level, it does not matter whether it happens inside or outside, as long as it is tapped flat afterwards - it is . ${\ 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}]))}$

This monad belongs to an adjoint functor pair (as above) between the categories of sets or semigroups . assigns the free semigroup above this set to a set, and the underlying set to a semigroup. ${\ displaystyle F, G}$ ${\ displaystyle F}$ ${\ displaystyle G}$

application

Monads are used in computer science, especially in functional programming languages and the like. a. used for abstraction of side effects. It is Haskell highlight where monads to integrate input and output are used in the otherwise completely of side effects-free language. See also Monad (computer science) .

literature

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