Monad (category theory)

Short description: Operation in algebra and mathematics

In category theory, a branch of mathematics, a monad (also triple, triad, standard construction and fundamental construction)[1] is a monoid in the category of endofunctors of some fixed category. An endofunctor is a functor mapping a category to itself, and a monad is an endofunctor together with two natural transformations required to fulfill certain coherence conditions. Monads are used in the theory of pairs of adjoint functors, and they generalize closure operators on partially ordered sets to arbitrary categories. Monads are also useful in the theory of datatypes, the denotational semantics of imperative programming languages, and in functional programming languages, allowing languages without mutable state to do things such as simulate for-loops; see Monad (functional programming).

## Contents

* 1 Introduction and definition
* 1.1 Formal definition
* 1.2 The power set monad
* 1.3 Remarks
* 1.4 Comonads
* 1.5 Terminological history
* 2 Examples
* 2.1 Identity
* 2.2 Monads arising from adjunctions
* 2.2.1 Double dualization
* 2.2.2 Closure operators on partially ordered sets
* 2.2.3 Free-forgetful adjunctions
* 2.3 Codensity monads
* 2.4 Monads used in denotational semantics
* 2.4.1 The maybe monad
* 2.4.2 The state monad
* 2.4.3 The environment monad
* 2.4.4 The list and set monads
* 3 Algebras for a monad
* 3.1 Examples
* 3.1.1 Algebras over the free group monad
* 3.1.2 Algebras over the distribution monad
* 3.1.3 Algebras over the symmetric monad
* 3.1.4 Commutative algebras in E-infinity ring spectra
* 4 Monads and adjunctions
* 4.1 Monadic adjunctions
* 4.2 Beck's monadicity theorem
* 5 Uses
* 6 Generalization
* 7 See also
* 8 References
* 9 Further reading
* 10 External links

## Introduction and definition

A monad is a certain type of endofunctor. For example, if F and G are a pair of adjoint functors, with F left adjoint to G, then the composition G∘F is a monad. If F and G are inverse functors, the corresponding monad is the identity functor. In general, adjunctions are not equivalences—they relate categories of different natures. The monad theory matters as part of the effort to capture what it is that adjunctions 'preserve'. The other half of the theory, of what can be learned likewise from consideration of F∘G, is discussed under the dual theory of comonads.

### Formal definition

Throughout this article C denotes a category. A monad on C consists of an endofunctor T:C->C together with two natural transformations: η:1C->T (where 1C denotes the identity functor on C) and μ:T2->T (where T2 is the functor T∘T from C to C). These are required to fulfill the following conditions (sometimes called coherence conditions):

* μ∘Tμ=μ∘μT (as natural transformations T3->T); here Tμ and μT are formed by "horizontal composition."
* μ∘Tη=μ∘ηT=1T (as natural transformations T->T; here 1T denotes the identity transformation from T to T).

We can rewrite these conditions using the following commutative diagrams:

|  |

|
|

See the article on natural transformations for the explanation of the notations Tμ and μT, or see below the commutative diagrams not using these notions:

|  |

|
|

The first axiom is akin to the associativity in monoids if we think of μ as the monoid's binary operation, and the second axiom is akin to the existence of an identity element (which we think of as given by η). Indeed, a monad on C can alternatively be defined as a monoid in the category 𝐄𝐧𝐝C whose objects are the endofunctors of C and whose morphisms are the natural transformations between them, with the monoidal structure induced by the composition of endofunctors.

### The power set monad

The power set monad is a monad 𝒫 on the category 𝐒𝐞𝐭: For a set A let T(A) be the power set of A and for a function f:A->B let T(f) be the function between the power sets induced by taking direct images under f. For every set A, we have a map ηA:A->T(A), which assigns to every a∈A the singleton {a}. The function

μA:T(T(A))->T(A)

takes a set of sets to its union. These data describe a monad.

### Remarks

The axioms of a monad are formally similar to the monoid axioms. In fact, monads are special cases of monoids, namely they are precisely the monoids among endofunctors End⁡(C), which is equipped with the multiplication given by composition of endofunctors.

Composition of monads is not, in general, a monad. For example, the double power set functor 𝒫∘𝒫 does not admit any monad structure.[2]

### Comonads

The categorical dual definition is a formal definition of a comonad (or cotriple); this can be said quickly in the terms that a comonad for a category C is a monad for the opposite category Cop. It is therefore a functor U from C to itself, with a set of axioms for counit and comultiplication that come from reversing the arrows everywhere in the definition just given.

Monads are to monoids as comonads are to comonoids. Every set is a comonoid in a unique way, so comonoids are less familiar in abstract algebra than monoids; however, comonoids in the category of vector spaces with its usual tensor product are important and widely studied under the name of coalgebras.

### Terminological history

The notion of monad was invented by Roger Godement in 1958 under the name "standard construction". Monad has been called "dual standard construction", "triple", "monoid" and "triad".[3] The term "monad" is used at latest 1967, by Jean Bénabou.[4][5]

## Examples

### Identity

The identity functor on a category C is a monad. Its multiplication and unit are the identity function on the objects of C.

### Monads arising from adjunctions

Any adjunction

F:C⇄D:G

gives rise to a monad on C. This very widespread construction works as follows: the endofunctor is the composite

T=G∘F.

This endofunctor is quickly seen to be a monad, where the unit map stems from the unit map idC->G∘F of the adjunction, and the multiplication map is constructed using the counit map of the adjunction:

T2=G∘F∘G∘F→G∘counit∘FG∘F=T.

In fact, any monad can be found as an explicit adjunction of functors using the Eilenberg–Moore category CT (the category of T-algebras).[6]

#### Double dualization

The double dualization monad, for a fixed field k arises from the adjunction

(−)*:𝐕𝐞𝐜𝐭k⇄𝐕𝐞𝐜𝐭kop:(−)*

where both functors are given by sending a vector space V to its dual vector space V*:=Hom⁡(V,k). The associated monad sends a vector space V to its double dual V**. This monad is discussed, in much greater generality, by (Kock 1970).

#### Closure operators on partially ordered sets

For categories arising from partially ordered sets (P,≤) (with a single morphism from x to y if and only if x≤y), then the formalism becomes much simpler: adjoint pairs are Galois connections and monads are closure operators.

#### Free-forgetful adjunctions

For example, let G be the forgetful functor from the category Grp of groups to the category Set of sets, and let F be the free group functor from the category of sets to the category of groups. Then F is left adjoint of G. In this case, the associated monad T=G∘F takes a set X and returns the underlying set of the free group Free(X). The unit map of this monad is given by the maps

X->T(X)

including any set X into the set Free(X) in the natural way, as strings of length 1. Further, the multiplication of this monad is the map

T(T(X))->T(X)

made out of a natural concatenation or 'flattening' of 'strings of strings'. This amounts to two natural transformations. The preceding example about free groups can be generalized to any type of algebra in the sense of a variety of algebras in universal algebra. Thus, every such type of algebra gives rise to a monad on the category of sets. Importantly, the algebra type can be recovered from the monad (as the category of Eilenberg–Moore algebras), so monads can also be seen as generalizing varieties of universal algebras.

Another monad arising from an adjunction is when T is the endofunctor on the category of vector spaces which maps a vector space V to its tensor algebra T(V), and which maps linear maps to their tensor product. We then have a natural transformation corresponding to the embedding of V into its tensor algebra, and a natural transformation corresponding to the map from T(T(V)) to T(V) obtained by simply expanding all tensor products.

### Codensity monads

Under mild conditions, functors not admitting a left adjoint also give rise to a monad, the so-called codensity monad. For example, the inclusion

𝐅𝐢𝐧𝐒𝐞𝐭⊂𝐒𝐞𝐭

does not admit a left adjoint. Its codensity monad is the monad on sets sending any set X to the set of ultrafilters on X. This and similar examples are discussed in (Leinster 2013).

### Monads used in denotational semantics

The following monads over the category of sets are used in denotational semantics of imperative programming languages, and analogous constructions are used in functional programming.

#### The maybe monad

The endofunctor of the maybe or partiality monad adds a disjoint point:[7]

(−)*:𝐒𝐞𝐭->𝐒𝐞𝐭
X↦X∪{*}

The unit is given by the inclusion of a set X into X*:

ηX:X->X*
x↦x

The multiplication maps elements of X to themselves, and the two disjoint points in (X*)* to the one in X*.

In both functional programming and denotational semantics, the maybe monad models partial computations, that is, computations that may fail.

#### The state monad

Given a set S, the endofunctor of the state monad maps each set X to the set of functions S->S×X. The component of the unit at X maps each element x∈X to the function

ηX(x):S->S×X
s↦(s,x)

The multiplication maps the function f:S->S×(S->S×X),s↦(s′,f′) to the function

μX(f):S->S×X
s↦f′(s′)

In functional programming and denotational semantics, the state monad models stateful computations.

#### The environment monad

Given a set E, the endofunctor of the reader or environment monad maps each set X to the set of functions E->X. Thus, the endofunctor of this monad is exactly the hom functor Hom(E,−). The component of the unit at X maps each element x∈X to the constant function e↦x.

In functional programming and denotational semantics, the environment monad models computations with access to some read-only data.

#### The list and set monads

The list or nondeterminism monad maps a set X to the set of finite sequences (i.e., lists) with elements from X. The unit maps an element x in X to the singleton list [x]. The multiplication concatenates a list of lists into a single list.

In functional programming, the list monad is used to model nondeterministic computations. The covariant powerset monad is also known as the set monad, and is also used to model nondeterministic computation.

## Algebras for a monad

Given a monad (T,η,μ) on a category C, it is natural to consider T-algebras, i.e., objects of C acted upon by T in a way which is compatible with the unit and multiplication of the monad. More formally, a T-algebra (x,h) is an object x of C together with an arrow h:Tx->x of C called the structure map of the algebra such that the diagrams

|  | and  |  |

|
|
|
|

commute.

A morphism

f:(x,h)->(x′,h′)

-algebras is an arrow

f:x->x′

such that the diagram

commutes.

-algebras form a category called the Eilenberg–Moore category and denoted by

### Examples

#### Algebras over the free group monad

For example, for the free group monad discussed above, a T-algebra is a set X together with a map from the free group generated by X towards X subject to associativity and unitality conditions. Such a structure is equivalent to saying that X is a group itself.

#### Algebras over the distribution monad

Another example is the distribution monad 𝒟 on the category of sets. It is defined by sending a set X to the set of functions f:X->[0,1] with finite support and such that their sum is equal to 1. In set-builder notation, this is the set𝒟(X)={f:X->[0,1]:#supp(f)<+∞∑x∈Xf(x)=1}By inspection of the definitions, it can be shown that algebras over the distribution monad are equivalent to convex sets, i.e., sets equipped with operations x+ry for r∈[0,1] subject to axioms resembling the behavior of convex linear combinations rx+(1−r)y in Euclidean space.[8]

#### Algebras over the symmetric monad

Another useful example of a monad is the symmetric algebra functor on the category of R-modules for a commutative ring R.Sym∙(−):Mod(R)->Mod(R)sending an R-module M to the direct sum of symmetric tensor powersSym∙(M)=⨁k=0∞Symk(M)where Sym0(M)=R. For example, Sym∙(R⊕n)≅R[x1,…,xn] where the R-algebra on the right is considered as a module. Then, an algebra over this monad are commutative R-algebras. There are also algebras over the monads for the alternating tensors Alt∙(−) and total tensor functors T∙(−) giving anti-symmetric R-algebras, and free R-algebras, soAlt∙(R⊕n)=R(x1,…,xn)T∙(R⊕n)=R⟨x1,…,xn⟩where the first ring is the free anti-symmetric algebra over R in n-generators and the second ring is the free algebra over R in n-generators.

#### Commutative algebras in E-infinity ring spectra

There is an analogous construction for commutative 𝕊-algebras[9]pg 113 which gives commutative A-algebras for a commutative 𝕊-algebra A. If ℳA is the category of A-modules, then the functor ℙ:ℳA->ℳA is the monad given byℙ(M)=⋁j≥0Mj/ΣjwhereMj=M∧A⋯∧AM j-times. Then there is an associated category 𝒞A of commutative A-algebras from the category of algebras over this monad.

## Monads and adjunctions

As was mentioned above, any adjunction gives rise to a monad. Conversely, every monad arises from some adjunction, namely the free–forgetful adjunction

T(−):C⇄CT:forget

whose left adjoint sends an object X to the free T-algebra T(X). However, there are usually several distinct adjunctions giving rise to a monad: let 𝐀𝐝𝐣(C,T) be the category whose objects are the adjunctions (F,G,e,ε) such that (GF,e,GεF)=(T,η,μ) and whose arrows are the morphisms of adjunctions that are the identity on C. Then the above free–forgetful adjunction involving the Eilenberg–Moore category CT is a terminal object in 𝐀𝐝𝐣(C,T). An initial object is the Kleisli category, which is by definition the full subcategory of CT consisting only of free T-algebras, i.e., T-algebras of the form T(x) for some object x of C.

### Monadic adjunctions

Given any adjunction (F:C->D,G:D->C,η,ε) with associated monad T, the functor G can be factored as

D->G~CT->forgetC,

i.e., G(Y) can be naturally endowed with a T-algebra structure for any Y in D. The adjunction is called a monadic adjunction if the first functor G~ yields an equivalence of categories between D and the Eilenberg–Moore category CT.[10] By extension, a functor G:D->C is said to be monadic if it has a left adjoint F forming a monadic adjunction. For example, the free–forgetful adjunction between groups and sets is monadic, since algebras over the associated monad are groups, as was mentioned above. In general, knowing that an adjunction is monadic allows one to reconstruct objects in D out of objects in C and the T-action.

### Beck's monadicity theorem

Beck's monadicity theorem gives a necessary and sufficient condition for an adjunction to be monadic. A simplified version of this theorem states that G is monadic if it is conservative (or G reflects isomorphisms, i.e., a morphism in D is an isomorphism if and only if its image under G is an isomorphism in C) and C has and G preserves coequalizers.

For example, the forgetful functor from the category of compact Hausdorff spaces to sets is monadic. However the forgetful functor from all topological spaces to sets is not conservative since there are continuous bijective maps (between non-compact or non-Hausdorff spaces) that fail to be homeomorphisms. Thus, this forgetful functor is not monadic.[11] The dual version of Beck's theorem, characterizing comonadic adjunctions, is relevant in different fields such as topos theory and topics in algebraic geometry related to descent. A first example of a comonadic adjunction is the adjunction

−⊗AB:𝐌𝐨𝐝A⇄𝐌𝐨𝐝B:forget

for a ring homomorphism A->B between commutative rings. This adjunction is comonadic, by Beck's theorem, if and only if B is faithfully flat as an A-module. It thus allows to descend B-modules, equipped with a descent datum (i.e., an action of the comonad given by the adjunction) to A-modules. The resulting theory of faithfully flat descent is widely applied in algebraic geometry.

## Uses

Monads are used in functional programming to express types of sequential computation (sometimes with side-effects). See monads in functional programming, and the more mathematically oriented Wikibook module b:Haskell/Category theory.

Monads are used in the denotational semantics of impure functional and imperative programming languages.[12][13]

In categorical logic, an analogy has been drawn between the monad-comonad theory, and modal logic via closure operators, interior algebras, and their relation to models of S4 and intuitionistic logics.

## Generalization

It is possible to define monads in a 2-category C. Monads described above are monads for C=𝐂𝐚𝐭.

## See also

* Distributive law between monads
* Lawvere theory
* Monad (functional programming)
* Polyad
* Strong monad

## References

1. ↑ Barr, Michael; Wells, Charles (1985), "Toposes, Triples and Theories", Grundlehren der mathematischen Wissenschaften (Springer-Verlag) 278: pp. 82 and 120, ISBN 0-387-96115-1, http://www.tac.mta.ca/tac/reprints/articles/12/tr12.pdf.
2. ↑ Klin; Salamanca (2018), "Iterated Covariant Powerset is not a Monad", Electronic Notes in Theoretical Computer Science 341: 261–276, doi:10.1016/j.entcs.2018.11.013
3. ↑ Mac Lane 1978, p. 138. sfn error: no target: CITEREFMac_Lane1978 (help)
4. ↑ Bénabou, Jean (1967). "Introduction to bicategories". in Bénabou, J.; Davis, R.; Dold, A. et al. (in en). Reports of the Midwest Category Seminar. Lecture Notes in Mathematics. 47. Berlin, Heidelberg: Springer. pp. 1–77. doi:10.1007/BFb0074299. ISBN 978-3-540-35545-8. https://link.springer.com/chapter/10.1007/BFb0074299.
5. ↑ "RE: Monads". 2009-04-04. http://article.gmane.org/gmane.science.mathematics.categories/225/.
6. ↑ Riehl, Emily. "Category Theory in Context". p. 162. https://math.jhu.edu/~eriehl/context.pdf.
7. ↑ Riehl 2017, p. 155.
8. ↑ Świrszcz, T. (1974), "Monadic functors and convexity", Bull. Acad. Polon. Sci. Sér. Sci. Math. Astron. Phys. 22: 39–42 , Jacobs, Bart (2010), "Convexity, Duality and Effects", Theoretical Computer Science, IFIP Advances in Information and Communication Technology, 323, pp. 1–19, doi:10.1007/978-3-642-15240-5_1, ISBN 978-3-642-15239-9
9. ↑ Basterra, M. (1999-12-15). "André–Quillen cohomology of commutative S-algebras" (in en). Journal of Pure and Applied Algebra 144 (2): 111–143. doi:10.1016/S0022-4049(98)00051-6. ISSN 0022-4049.
10. ↑ (MacLane 1978) uses a stronger definition, where the two categories are isomorphic rather than equivalent.
11. ↑ (MacLane 1978)
12. ↑ Wadler, Philip (1993). "Monads for functional programming". in Broy, Manfred (in en). Program Design Calculi. NATO ASI Series. 118. Berlin, Heidelberg: Springer. pp. 233–264. doi:10.1007/978-3-662-02880-3_8. ISBN 978-3-662-02880-3. https://link.springer.com/chapter/10.1007/978-3-662-02880-3_8. "The concept of a monad, which arises from category theory, has been applied by Moggi to structure the denotational semantics of programming languages."
13. ↑ Mulry, Philip S. (1998-01-01). "Monads in Semantics" (in en). Electronic Notes in Theoretical Computer Science. US-Brazil Joint Workshops on the Formal Foundations of Software Systems 14: 275–286. doi:10.1016/S1571-0661(05)80241-5. ISSN 1571-0661.

## Further reading

* Barr, Michael; Wells, Charles (1999), Category Theory for Computing Science, http://www.tac.mta.ca/tac/reprints/articles/22/tr22.pdf
* Godement, Roger (1958), Topologie Algébrique et Théorie des Faisceaux., Actualités Sci. Ind., Publ. Math. Univ. Strasbourg, 1252, Paris: Hermann, pp. viii+283 pp
* Kock, Anders (1970), "On Double Dualization Monads", Mathematica Scandinavica 27: 151, doi:10.7146/math.scand.a-10995
* Leinster, Tom (2013), "Codensity and the ultrafilter monad", Theory and Applications of Categories 28: 332–370, Bibcode: 2012arXiv1209.3606L
* MacLane, Saunders (1978), Categories for the Working Mathematician, Graduate Texts in Mathematics, 5, doi:10.1007/978-1-4757-4721-8, ISBN 978-1-4419-3123-8
* Pedicchio, Maria Cristina; Tholen, Walter, eds (2004). Categorical Foundations. Special Topics in Order, Topology, Algebra, and Sheaf Theory. Encyclopedia of Mathematics and Its Applications. 97. Cambridge: Cambridge University Press. ISBN 0-521-83414-7.
* Riehl, Emily (2017), Category Theory in Context, Courier Dover Publications, ISBN 9780486820804
* Turi, Daniele (1996–2001), Category Theory Lecture Notes, http://www.dcs.ed.ac.uk/home/dt/CT/categories.pdf

## External links

* Monads, five short lectures (with one appendix).
* John Baez's This Week's Finds in Mathematical Physics (Week 89) covers monads in 2-categories.

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Monad (category theory). Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Monad_(category_theory)&oldid=237861"