In
category theory
Category theory is a general theory of mathematical structures and their relations. It was introduced by Samuel Eilenberg and Saunders Mac Lane in the middle of the 20th century in their foundational work on algebraic topology. Category theory ...
, a branch of
mathematics
Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...
, a monad is a triple
consisting of a
functor
In mathematics, specifically category theory, a functor is a Map (mathematics), mapping between Category (mathematics), categories. Functors were first considered in algebraic topology, where algebraic objects (such as the fundamental group) ar ...
''T'' from a category to itself and two
natural transformation
In category theory, a branch of mathematics, a natural transformation provides a way of transforming one functor into another while respecting the internal structure (i.e., the composition of morphisms) of the categories involved. Hence, a natur ...
s
that satisfy the conditions like associativity. For example, if
are functors
adjoint
In mathematics, the term ''adjoint'' applies in several situations. Several of these share a similar formalism: if ''A'' is adjoint to ''B'', then there is typically some formula of the type
:(''Ax'', ''y'') = (''x'', ''By'').
Specifically, adjoin ...
to each other, then
together with
determined by the adjoint relation is a monad.
In concise terms, a monad is a
monoid
In abstract algebra, a monoid is a set equipped with an associative binary operation and an identity element. For example, the nonnegative integers with addition form a monoid, the identity element being .
Monoids are semigroups with identity ...
in the
category
Category, plural categories, may refer to:
General uses
*Classification, the general act of allocating things to classes/categories Philosophy
* Category of being
* ''Categories'' (Aristotle)
* Category (Kant)
* Categories (Peirce)
* Category ( ...
of
endofunctor
In mathematics, specifically category theory, a functor is a mapping between categories. Functors were first considered in algebraic topology, where algebraic objects (such as the fundamental group) are associated to topological spaces, and ma ...
s of some fixed category (an endofunctor is a
functor
In mathematics, specifically category theory, a functor is a Map (mathematics), mapping between Category (mathematics), categories. Functors were first considered in algebraic topology, where algebraic objects (such as the fundamental group) ar ...
mapping a category to itself). According to
John Baez
John Carlos Baez ( ; born June 12, 1961) is an American mathematical physicist and a professor of mathematics at the University of California, Riverside (UCR) in Riverside, California. He has worked on spin foams in loop quantum gravity, ap ...
, a monad can be considered at least in two ways:
[ https://golem.ph.utexas.edu/category/2009/07/the_monads_hurt_my_head_but_no.html]
# 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
A group is a number of persons or things that are located, gathered, or classed together.
Groups of people
* Cultural group, a group whose members share the same cultural identity
* Ethnic group, a group whose members share the same ethnic iden ...
can be described by a certain monad.
Monads are used in the theory of pairs of
adjoint functors
In mathematics, specifically category theory, adjunction is a relationship that two functors may exhibit, intuitively corresponding to a weak form of equivalence between two related categories. Two functors that stand in this relationship are k ...
, and they generalize
closure operator
In mathematics, a closure operator on a Set (mathematics), set ''S'' is a Function (mathematics), function \operatorname: \mathcal(S)\rightarrow \mathcal(S) from the power set of ''S'' to itself that satisfies the following conditions for all sets ...
s on
partially ordered set
In mathematics, especially order theory, a partial order on a Set (mathematics), set is an arrangement such that, for certain pairs of elements, one precedes the other. The word ''partial'' is used to indicate that not every pair of elements need ...
s to arbitrary categories. Monads are also useful in the
theory of datatypes, the
denotational semantics
In computer science, denotational semantics (initially known as mathematical semantics or Scott–Strachey semantics) is an approach of formalizing the meanings of programming languages by constructing mathematical objects (called ''denotations'' ...
of
imperative programming languages, and in
functional programming language
In computer science, functional programming is a programming paradigm where programs are constructed by applying and composing functions. It is a declarative programming paradigm in which function definitions are trees of expressions that map ...
s, allowing languages without mutable state to do things such as simulate
for-loops; see
Monad (functional programming)
In functional programming, monads are a way to structure computations as a sequence of steps, where each step not only produces a value but also some extra information about the computation, such as a potential failure, non-determinism, or side e ...
.
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
In mathematics, specifically category theory, a functor is a mapping between categories. Functors were first considered in algebraic topology, where algebraic objects (such as the fundamental group) are associated to topological spaces, and ma ...
. For example, if
and
are a pair of
adjoint functors
In mathematics, specifically category theory, adjunction is a relationship that two functors may exhibit, intuitively corresponding to a weak form of equivalence between two related categories. Two functors that stand in this relationship are k ...
, with
left adjoint to
, then the composition
is a monad. If
and
are inverse to each other, the corresponding monad is the
identity functor
In mathematics, specifically category theory, a functor is a mapping between categories. Functors were first considered in algebraic topology, where algebraic objects (such as the fundamental group) are associated to topological spaces, and m ...
. 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
Category, plural categories, may refer to:
General uses
*Classification, the general act of allocating things to classes/categories Philosophy
* Category of being
* ''Categories'' (Aristotle)
* Category (Kant)
* Categories (Peirce)
* Category ( ...
. A ''monad'' on
consists of an endofunctor
together with two
natural transformation
In category theory, a branch of mathematics, a natural transformation provides a way of transforming one functor into another while respecting the internal structure (i.e., the composition of morphisms) of the categories involved. Hence, a natur ...
s:
(where
denotes the identity functor on
) and
(where
is the functor
from
to
). These are required to fulfill the following conditions (sometimes called
coherence condition
In mathematics, specifically in homotopy theory and (higher) category theory, coherency is the standard that equalities or diagrams must satisfy when they hold "up to homotopy" or "up to isomorphism".
The adjectives such as "pseudo-" and "lax-" ...
s):
*
(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
350px, The commutative diagram used in the proof of the five lemma
In mathematics, and especially in category theory, a commutative diagram is a diagram such that all directed paths in the diagram with the same start and endpoints lead to the s ...
:
See the article on
natural transformations
In category theory, a branch of mathematics, a natural transformation provides a way of transforming one functor into another while respecting the internal structure (i.e., the composition of morphisms) of the categories involved. Hence, a natura ...
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 mathematics, the associative property is a property of some binary operations that rearranging the parentheses in an expression will not change the result. In propositional logic, associativity is a Validity (logic), valid rule of replaceme ...
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
In mathematics, an identity element or neutral element of a binary operation is an element that leaves unchanged every element when the operation is applied. For example, 0 is an identity element of the addition of real numbers. This concept is use ...
(which we think of as given by
). Indeed, a monad on
can alternatively be defined as a
monoid
In abstract algebra, a monoid is a set equipped with an associative binary operation and an identity element. For example, the nonnegative integers with addition form a monoid, the identity element being .
Monoids are semigroups with identity ...
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
In mathematics, the power set (or powerset) of a set is the set of all subsets of , including the empty set and itself. In axiomatic set theory (as developed, for example, in the ZFC axioms), the existence of the power set of any set is po ...
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
Singleton may refer to:
Sciences, technology Mathematics
* Singleton (mathematics), a set with exactly one element
* Singleton field, used in conformal field theory Computing
* Singleton pattern, a design pattern that allows only one instance ...
. 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
In abstract algebra, a monoid is a set equipped with an associative binary operation and an identity element. For example, the nonnegative integers with addition form a monoid, the identity element being .
Monoids are semigroups with identity ...
axioms. In fact, monads are special cases of monoids, namely they are precisely the monoids among
endofunctor
In mathematics, specifically category theory, a functor is a mapping between categories. Functors were first considered in algebraic topology, where algebraic objects (such as the fundamental group) are associated to topological spaces, and ma ...
s
, 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
In category theory, a branch of mathematics, duality is a correspondence between the properties of a category ''C'' and the dual properties of the opposite category ''C''op. Given a statement regarding the category ''C'', by interchanging the so ...
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
In category theory, a branch of mathematics, the opposite category or dual category C^ of a given Category (mathematics), category C is formed by reversing the morphisms, i.e. interchanging the source and target of each morphism. Doing the reversal ...
. 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
In mathematics, more specifically algebra, abstract algebra or modern algebra is the study of algebraic structures, which are set (mathematics), sets with specific operation (mathematics), operations acting on their elements. Algebraic structur ...
than monoids; however, comonoids in the category of vector spaces with its usual tensor product are important and widely studied under the name of
coalgebra
In mathematics, coalgebras or cogebras are structures that are dual (in the category-theoretic sense of reversing arrows) to unital associative algebras. The axioms of unital associative algebras can be formulated in terms of commutative diagram ...
s.
Terminological history
The notion of monad was invented by
Roger Godement
Roger Godement (; 1 October 1921 – 21 July 2016) was a French mathematician, known for his work in functional analysis as well as his expository books.
Biography
Godement started as a student at the École normale supérieure in 1940, where he ...
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
Jean Bénabou (1932 – 11 February 2022) was a French mathematician, known for his contributions to category theory. He directed the Research Seminar in Category Theory at the Institut Henri Poincaré
The Henri Poincaré Institute (or IHP fo ...
.
Examples
Identity
The
identity functor
In mathematics, specifically category theory, a functor is a mapping between categories. Functors were first considered in algebraic topology, where algebraic objects (such as the fundamental group) are associated to topological spaces, and m ...
on a category
is a monad. Its multiplication and unit are the
identity function
Graph of the identity function on the real numbers
In mathematics, an identity function, also called an identity relation, identity map or identity transformation, is a function that always returns the value that was used as its argument, unc ...
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
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
Eilenberg–Moore category
In category theory, a branch of mathematics, a monad is a triple (T, \eta, \mu) consisting of a functor ''T'' from a category to itself and two natural transformations \eta, \mu that satisfy the conditions like associativity. For example, if F, ...
(the category of
-algebras).
Double dualization
The ''double dualization monad'', for a fixed
field
Field may refer to:
Expanses of open ground
* Field (agriculture), an area of land used for agricultural purposes
* Airfield, an aerodrome that lacks the infrastructure of an airport
* Battlefield
* Lawn, an area of mowed grass
* Meadow, a grass ...
''k'' arises from the adjunction
:
where both functors are given by sending a
vector space
In mathematics and physics, a vector space (also called a linear space) is a set (mathematics), set whose elements, often called vector (mathematics and physics), ''vectors'', can be added together and multiplied ("scaled") by numbers called sc ...
''V'' to its
dual vector space
In mathematics, any vector space ''V'' has a corresponding dual vector space (or just dual space for short) consisting of all linear forms on ''V,'' together with the vector space structure of pointwise addition and scalar multiplication by const ...
. The associated monad sends a vector space ''V'' to its
double dual
In mathematics, a duality translates concepts, theorems or mathematical structures into other concepts, theorems or structures in a one-to-one fashion, often (but not always) by means of an involution operation: if the dual of is , then the dua ...
. This monad is discussed, in much greater generality, by .
Closure operators on partially ordered sets
For categories arising from
partially ordered set
In mathematics, especially order theory, a partial order on a Set (mathematics), set is an arrangement such that, for certain pairs of elements, one precedes the other. The word ''partial'' is used to indicate that not every pair of elements need ...
s
(with a single morphism from
to
if and only if
In logic and related fields such as mathematics and philosophy, "if and only if" (often shortened as "iff") is paraphrased by the biconditional, a logical connective between statements. The biconditional is true in two cases, where either bo ...
), then the formalism becomes much simpler: adjoint pairs are
Galois connection
In mathematics, especially in order theory, a Galois connection is a particular correspondence (typically) between two partially ordered sets (posets). Galois connections find applications in various mathematical theories. They generalize the fun ...
s and monads are
closure operators
Closure may refer to:
Conceptual Psychology
* Closure (psychology), the state of experiencing an emotional conclusion to a difficult life event
* Law of closure (Gestalt psychology), the perception of objects as complete rather than focusing on ...
.
Free-forgetful adjunctions
For example, let
be the
forgetful functor
In mathematics, more specifically in the area of category theory, a forgetful functor (also known as a stripping functor) "forgets" or drops some or all of the input's structure or properties mapping to the output. For an algebraic structure of ...
from
the category Grp of
groups
A group is a number of persons or things that are located, gathered, or classed together.
Groups of people
* Cultural group, a group whose members share the same cultural identity
* Ethnic group, a group whose members share the same ethnic iden ...
to the
category Set of sets, and let
be the
free group
In mathematics, the free group ''F'S'' over a given set ''S'' consists of all words that can be built from members of ''S'', considering two words to be different unless their equality follows from the group axioms (e.g. ''st'' = ''suu''− ...
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
In formal language theory and computer programming, string concatenation is the operation of joining character strings end-to-end. For example, the concatenation of "snow" and "ball" is "snowball". In certain formalizations of concatenati ...
or 'flattening' of 'strings of strings'. This amounts to two
natural transformation
In category theory, a branch of mathematics, a natural transformation provides a way of transforming one functor into another while respecting the internal structure (i.e., the composition of morphisms) of the categories involved. Hence, a natur ...
s.
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
Universal algebra (sometimes called general algebra) is the field of mathematics that studies algebraic structures in general, not specific types of algebraic structures.
For instance, rather than considering groups or rings as the object of stud ...
. 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
In mathematics, the tensor algebra of a vector space ''V'', denoted ''T''(''V'') or ''T''(''V''), is the algebra over a field, algebra of tensors on ''V'' (of any rank) with multiplication being the tensor product. It is the free algebra on ''V'', ...
, and which maps linear maps to their tensor product. We then have a natural transformation corresponding to the embedding of
into its
tensor algebra
In mathematics, the tensor algebra of a vector space ''V'', denoted ''T''(''V'') or ''T''(''V''), is the algebra over a field, algebra of tensors on ''V'' (of any rank) with multiplication being the tensor product. It is the free algebra on ''V'', ...
, 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
In mathematics, especially in category theory, the codensity monad is a fundamental construction associating a monad to a wide class of functors.
Definition
The codensity monad of a functor G: D \to C is defined to be the right Kan extension ...
. 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
ultrafilter
In the Mathematics, mathematical field of order theory, an ultrafilter on a given partially ordered set (or "poset") P is a certain subset of P, namely a Maximal element, maximal Filter (mathematics), filter on P; that is, a proper filter on P th ...
s on ''X''. This and similar examples are discussed in .
Monads used in denotational semantics
The following monads over the category of sets are used in
denotational semantics
In computer science, denotational semantics (initially known as mathematical semantics or Scott–Strachey semantics) is an approach of formalizing the meanings of programming languages by constructing mathematical objects (called ''denotations'' ...
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
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
In mathematics, specifically in category theory, hom-sets (i.e. sets of morphisms between object (category theory), objects) give rise to important functors to the category of sets. These functors are called hom-functors and have numerous applicati ...
. The component of the unit at
maps each element
to the
constant function
In mathematics, a constant function is a function whose (output) value is the same for every input value.
Basic properties
As a real-valued function of a real-valued argument, a constant function has the general form or just For example, ...
.
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
In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is call ...
(i.e.,
lists
A list is a set of discrete items of information collected and set forth in some format for utility, entertainment, or other purposes. A list may be memorialized in any number of ways, including existing only in the mind of the list-maker, but ...
) with elements from ''X''. The unit maps an element ''x'' in ''X'' to the singleton list
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
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