Monad (category theory) explained
Monad (category theory) should not be confused with Monad (homological algebra).
In category theory, a branch of mathematics, a monad is a triple
consisting of a
functor T from a category to itself and two
natural transformations
that satisfy the conditions like associativity. For example, if
are functors
adjoint to each other, then
together with
determined by the adjoint relation is a monad.
In concise terms, a monad is a monoid in the category of endofunctors of some fixed category (an endofunctor is a functor mapping a category to itself). According to John Baez, a monad can be considered at least in two ways: [1]
- A monad as a generalized monoid; this is clear since a monad is a monoid in a certain category,
- A monad as a tool for studying algebraic gadgets; for example, a group can be described by a certain monad.
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).
A monad is also called, especially in old literature, a triple, triad, standard construction and fundamental construction.
Introduction and definition
A monad is a certain type of endofunctor. For example, if
and
are a pair of
adjoint functors, with
left adjoint to
, then the composition
is a monad. If
and
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
, is discussed under the dual theory of
comonads.
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):
\mu\circT\mu=\mu\circ\muT
(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 commutative diagrams:
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 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
can alternatively be defined as a
monoid in the category
whose objects are the endofunctors of
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
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 monoid axioms. In fact, monads are special cases of monoids, namely they are precisely the monoids among endofunctors
, 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.
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 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". The term "monad" is used at latest 1967, by Jean Bénabou.[2] [3]
Examples
Identity
The identity functor on a category
is a monad. Its multiplication and unit are the
identity function on the objects of
.
Monads arising from adjunctions
Any adjunction
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
\operatorname{id}C\toG\circF
of the adjunction, and the multiplication map is constructed using the counit map of the adjunction:
T2=G\circF\circG\circF\xrightarrow{G\circcounit\circF}G\circF=T.
In fact,
any monad can be found as an explicit adjunction of functors using the Eilenberg–Moore category
(the category of
-algebras).
[4] Double dualization
The double dualization monad, for a fixed field k arises from the adjunction
(-)*:Vectk\rightleftarrows
:(-)*
V*:=\operatorname{Hom}(V,k)
. The associated monad sends a vector space
V to its double dual
. This monad is discussed, in much greater generality, by .
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
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
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 .
Monads used in denotational semantics
See also: Monad (functional programming).
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:
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
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
f:S\toS x (S\toS x X),s\mapsto(s',f')
to the function
In functional programming and denotational semantics, the state monad models stateful computations.
The environment monad
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
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
See also: F-algebra and pseudoalgebra.
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
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 set
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
for
subject to axioms resembling the behavior of convex linear combinations
in Euclidean space.
[5] 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 powers
where
. For example,
Sym\bullet(R ⊕ )\congR[x1,\ldots,xn]
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, so
where 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[6] pg 113 which gives commutative
-algebras for a commutative
-algebra
. If
is the category of
-modules, then the functor
is the monad given by
where
-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
T(-):C\rightleftarrowsCT: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
be the category whose objects are the adjunctions
such that
(GF,e,G\varepsilonF)=(T,η,\mu)
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
(F:C\toD,G:D\toC,η,\varepsilon)
with associated monad
T, the functor
G can be factored as
D\stackrel{\tildeG}\toCT\stackrel{forget
} \to C,
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
.
[7] 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 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.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:ModA\rightleftarrowsModB:\operatorname{forget}
for a ring homomorphism
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 .
Monads are used in the denotational semantics of impure functional and imperative programming languages.[8] [9]
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
. Monads described above are monads for
.
See also
Further reading
- Book: Pedicchio . Maria Cristina . Tholen . Walter . Categorical Foundations. Special Topics in Order, Topology, Algebra, and Sheaf Theory . Encyclopedia of Mathematics and Its Applications . 97 . Cambridge . . 2004 . 0-521-83414-7 . 1034.18001 .
External links
Notes and References
- https://golem.ph.utexas.edu/category/2009/07/the_monads_hurt_my_head_but_no.html
- Book: Bénabou, Jean . Reports of the Midwest Category Seminar . Introduction to bicategories . 1967 . Bénabou . J. . Davis . R. . Dold . A. . Isbell . J. . MacLane . S. . Oberst . U. . Roos . J. -E. . https://link.springer.com/chapter/10.1007/BFb0074299 . Lecture Notes in Mathematics . 47 . en . Berlin, Heidelberg . Springer . 1–77 . 10.1007/BFb0074299 . 978-3-540-35545-8.
- Web site: 2009-04-04 . RE: Monads . dead . https://web.archive.org/web/20150326175332/http://article.gmane.org/gmane.science.mathematics.categories/225/match= . 2015-03-26 . Gmane.
- Web site: Riehl. Emily. Emily Riehl. Category Theory in Context . live. https://web.archive.org/web/20210405153806/https://math.jhu.edu/%7Eeriehl/context.pdf. 5 Apr 2021. 162.
- ,
- 1999-12-15. André–Quillen cohomology of commutative S-algebras. Journal of Pure and Applied Algebra. en. 144. 2. 111–143. 10.1016/S0022-4049(98)00051-6. 0022-4049. free. Basterra . M. .
- uses a stronger definition, where the two categories are isomorphic rather than equivalent.
- Book: Wadler, Philip . Program Design Calculi . Monads for functional programming . 1993 . Broy . Manfred . https://link.springer.com/chapter/10.1007/978-3-662-02880-3_8 . NATO ASI Series . 118 . en . Berlin, Heidelberg . Springer . 233–264 . 10.1007/978-3-662-02880-3_8 . 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."
- Mulry . Philip S. . 1998-01-01 . Monads in Semantics . Electronic Notes in Theoretical Computer Science . US-Brazil Joint Workshops on the Formal Foundations of Software Systems . en . 14 . 275–286 . 10.1016/S1571-0661(05)80241-5 . 1571-0661. free .