Monad (category theory)
In
Introduction and definition
A monad is a certain type of
Formal definition
Throughout this article denotes a category. A monad on consists of an endofunctor together with two natural transformations: (where denotes the identity functor on ) and (where is the functor from to ). These are required to fulfill the following conditions (sometimes called coherence conditions):
- (as natural transformations ); here and are formed by "horizontal composition."
- (as natural transformations ; here denotes the identity transformation from to ).
We can rewrite these conditions using the following
See the article on natural transformations for the explanation of the notations and , or see below the commutative diagrams not using these notions:
The first axiom is akin to the
The power set monad
The power set monad is a monad on the category : For a set let be the power set of and for a function let be the function between the power sets induced by taking direct images under . For every set , we have a map , which assigns to every the singleton . The function
takes a set of sets to its union. These data describe a monad.
Remarks
The axioms of a monad are formally similar to the
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 is a monad for the opposite category . It is therefore a functor from 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
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
Monads arising from adjunctions
Any
gives rise to a monad on C. This very widespread construction works as follows: the endofunctor is the composite
This endofunctor is quickly seen to be a monad, where the unit map stems from the unit map of the adjunction, and the multiplication map is constructed using the counit map of the adjunction:
In fact, any monad can be found as an explicit adjunction of functors using the
Double dualization
The double dualization monad, for a fixed field k arises from the adjunction
where both functors are given by sending a
Closure operators on partially ordered sets
For categories arising from partially ordered sets (with a single morphism from to if and only if ), then the formalism becomes much simpler: adjoint pairs are Galois connections and monads are closure operators.
Free-forgetful adjunctions
For example, let be the forgetful functor from the category Grp of groups to the category Set of sets, and let be the free group functor from the category of sets to the category of groups. Then is left adjoint of . In this case, the associated monad takes a set and returns the underlying set of the free group . The unit map of this monad is given by the maps
including any set into the set in the natural way, as strings of length 1. Further, the multiplication of this monad is the map
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
Another monad arising from an adjunction is when is the endofunctor on the category of vector spaces which maps a vector space to its tensor algebra , and which maps linear maps to their tensor product. We then have a natural transformation corresponding to the embedding of into its tensor algebra, and a natural transformation corresponding to the map from to 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
The maybe monad
The endofunctor of the maybe or partiality monad adds a disjoint point:[7]
The unit is given by the inclusion of a set into :
The multiplication maps elements of to themselves, and the two disjoint points in to the one in .
In both functional programming and denotational semantics, the maybe monad models partial computations, that is, computations that may fail.
The state monad
This section needs expansion with: describe multiplication. You can help by adding to it. (February 2023) |
Given a set , the endofunctor of the state monad maps each set to the set of functions . The component of the unit at maps each element to the function
The multiplication maps the function to the function
In functional programming and denotational semantics, the state monad models stateful computations.
The environment monad
This section needs expansion with: describe multiplication. You can help by adding to it. (February 2023) |
Given a set , the endofunctor of the reader or environment monad maps each set to the set of functions . Thus, the endofunctor of this monad is exactly the hom functor . The component of the unit at maps each element to the constant function .
In functional programming and denotational semantics, the environment monad models computations with access to some read-only data.
The list and set monads
This section needs expansion with: describe multiplication. You can help by adding to it. (February 2023) |
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
Algebras for a monad
Given a monad on a category , it is natural to consider -algebras, i.e., objects of acted upon by in a way which is compatible with the unit and multiplication of the monad. More formally, a -algebra is an object of together with an arrow of called the structure map of the algebra such that the diagrams
and |
commute.
A morphism of -algebras is an arrow of 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 -algebra is a set together with a map from the free group generated by towards subject to associativity and unitality conditions. Such a structure is equivalent to saying that 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 to the set of functions with finite support and such that their sum is equal to . In set-builder notation, this is the setBy 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 for subject to axioms resembling the behavior of convex linear combinations in Euclidean space.[8]
Algebras over the symmetric monad
Another useful example of a monad is the symmetric algebra functor on the category of -modules for a commutative ring .sending an -module to the direct sum of symmetric tensor powerswhere . For example, where the -algebra on the right is considered as a module. Then, an algebra over this monad are commutative -algebras. There are also algebras over the monads for the alternating tensors and total tensor functors giving anti-symmetric -algebras, and free -algebras, sowhere the first ring is the free anti-symmetric algebra over in -generators and the second ring is the free algebra over in -generators.
Commutative algebras in E-infinity ring spectra
There is an analogous construction for commutative -algebras[9]pg 113 which gives commutative -algebras for a commutative -algebra . If is the category of -modules, then the functor is the monad given bywhere -times. Then there is an associated category of commutative -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
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 be the category whose objects are the adjunctions such that and whose arrows are the morphisms of adjunctions that are the identity on . Then the above free–forgetful adjunction involving the Eilenberg–Moore category is a terminal object in . An initial object is the Kleisli category, which is by definition the full subcategory of consisting only of free T-algebras, i.e., T-algebras of the form for some object x of C.
Monadic adjunctions
Given any adjunction with associated monad T, the functor G can be factored as
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 yields an equivalence of categories between D and the Eilenberg–Moore category .[10] By extension, a functor is said to be monadic if it has a left adjoint 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
for a ring homomorphism between commutative rings. This adjunction is comonadic, by Beck's theorem, if and only if B is
Uses
Monads are used in
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
Generalization
It is possible to define monads in a
See also
References
- ISBN 0-387-96115-1.
- ^ MacLane 1978, p. 138.
- ISBN 978-3-540-35545-8.
- ^ "RE: Monads". Gmane. 2009-04-04. Archived from the original on 2015-03-26.
- ^ Riehl, Emily. "Category Theory in Context" (PDF). p. 162. Archived (PDF) from the original on 5 Apr 2021.
- ^ Riehl 2017, p. 155.
- MR 0390019, Jacobs, Bart (2010), "Convexity, Duality and Effects", Theoretical Computer Science, IFIP Advances in Information and Communication Technology, vol. 323, pp. 1–19,ISBN 978-3-642-15239-9
- ISSN 0022-4049.
- ^ MacLane (1978) uses a stronger definition, where the two categories are isomorphic rather than equivalent.
- ^ MacLane (1978, §§VI.3, VI.9)
- ISBN 978-3-662-02880-3. "The concept of a monad, which arises from category theory, has been applied by Moggi to structure the denotational semantics of programming languages."
- ISSN 1571-0661.
Further reading
- Barr, Michael; Wells, Charles (1999), Category Theory for Computing Science (PDF)
- Godement, Roger (1958), Topologie Algébrique et Théorie des Faisceaux., Actualités Sci. Ind., Publ. Math. Univ. Strasbourg, vol. 1252, Paris: Hermann, pp. viii+283 pp
- Kock, Anders (1970), "On Double Dualization Monads", Mathematica Scandinavica, 27: 151,
- Leinster, Tom (2013), "Codensity and the ultrafilter monad" (PDF), Theory and Applications of Categories, 28: 332–370, Bibcode:2012arXiv1209.3606L
- MacLane, Saunders (1978), Categories for the Working Mathematician, Graduate Texts in Mathematics, vol. 5, 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. Vol. 97. Cambridge: Zbl 1034.18001.
- Perrone, Paolo (2024), "Chapter 5. Monads and Comonads", Starting Category Theory, World Scientific, ISBN 978-981-12-8600-1
- Riehl, Emily (2017), Category Theory in Context, Courier Dover Publications, ISBN 9780486820804
- Turi, Daniele (1996–2001), Category Theory Lecture Notes (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.
- Monads and comonads, video tutorial.