Editing Monad (category theory) (section)

==Examples==

===Identity===

The [[identity functor]] on a category <math>C</math> is a monad. Its multiplication and unit are the [[identity function]] on the objects of <math>C</math>.

===Monads arising from adjunctions===

Any [[adjunction (category theory)|adjunction]]

:<math>F: C \rightleftarrows D : G</math>

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

:<math>T = G \circ F.</math>

This endofunctor is quickly seen to be a monad, where the unit map stems from the unit map <math>\operatorname{id}_C \to G \circ F</math> of the adjunction, and the multiplication map is constructed using the counit map of the adjunction:

:<math>T^2 = G \circ F \circ G \circ F \xrightarrow{G \circ \text{counit} \circ F} G \circ F = T.</math>
In fact, '''any monad can be found as an explicit adjunction of functors''' using the [[Eilenberg–Moore category]] <math>C^T</math> (the category of <math>T</math>-algebras).<ref>{{Cite web|last=Riehl|first=Emily|author-link=Emily Riehl|title=Category Theory in Context |url=https://math.jhu.edu/%7Eeriehl/context.pdf|url-status=live|archive-url=https://web.archive.org/web/20210405153806/https://math.jhu.edu/%7Eeriehl/context.pdf|archive-date=5 Apr 2021|page=162}}</ref>

====Double dualization====
The ''double dualization monad'', for a fixed [[field (mathematics)|field]] ''k'' arises from the adjunction

:<math>(-)^* : \mathbf{Vect}_k \rightleftarrows \mathbf{Vect}_k^{op} : (-)^*</math>

where both functors are given by sending a [[vector space]] ''V'' to its [[dual vector space]] <math>V^* := \operatorname{Hom}(V, k)</math>. The associated monad sends a vector space ''V'' to its [[double dual]] <math>V^{**}</math>. This monad is discussed, in much greater generality, by {{harvtxt|Kock|1970}}.

====Closure operators on partially ordered sets====
For categories arising from [[partially ordered set]]s <math>(P, \le)</math> (with a single morphism from <math>x</math> to <math>y</math> [[if and only if]] <math>x \le y</math>), then the formalism becomes much simpler: adjoint pairs are [[Galois connection]]s and monads are [[closure operator#Closure operators on partially ordered sets|closure operators]].

====Free-forgetful adjunctions====
For example, let <math>G</math> be the [[forgetful functor]] from [[category of groups|the category '''Grp''']] of [[group (mathematics)|groups]] to the [[category of sets|category '''Set''']] of sets, and let  <math>F</math> be the [[free group]] functor from the category of sets to the category of groups.  Then <math>F</math> is left adjoint of <math>G</math>. In this case, the associated monad <math>T = G \circ F</math> takes a set <math>X</math> and returns the underlying set of the free group <math>\mathrm{Free}(X)</math>.
The unit map of this monad is given by the maps
:<math>X \to T(X) </math>
including any set <math>X</math> into the set <math>\mathrm{Free}(X)</math> in the natural way, as strings of length 1. Further, the multiplication of this monad is the map
:<math>T(T(X)) \to T(X) </math>
made out of a natural [[concatenation]] or 'flattening' of 'strings of strings'.  This amounts to two [[natural transformation]]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]].  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 <math>T</math> is the endofunctor on the category of vector spaces which maps a vector space <math>V</math> to its [[tensor algebra]] <math>T(V)</math>, and which maps linear maps to their tensor product. We then have a natural transformation corresponding to the embedding of <math>V</math> into its [[tensor algebra]], and a natural transformation corresponding to the map from <math>T(T(V))</math> to <math>T(V)</math> 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

:<math>\mathbf{FinSet} \subset \mathbf{Set}</math>

does not admit a left adjoint. Its codensity monad is the monad on sets sending any set ''X'' to the set of [[ultrafilter]]s on ''X''. This and similar examples are discussed in {{harvtxt|Leinster|2013}}.

===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 language|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:{{sfn|Riehl|2017|p=155}}

:<math>(-)_{*}: \mathbf{Set}\to\mathbf{Set}</math>
:<math>X\mapsto X\cup\{*\}</math>

The unit is given by the inclusion of a set <math>X</math> into <math>X_*</math>:

:<math>\eta_X: X\to X_{*}</math>
:<math>x\mapsto x</math>

The multiplication maps elements of <math>X</math> to themselves, and the two disjoint points in <math>(X_{*})_{*}</math> to the one in <math>X_{*}</math>.

In both functional programming and denotational semantics, the maybe monad models [[Partial function|partial computations]], that is, computations that may fail.

====The state monad====

{{Expand section|date=February 2023|with=describe multiplication}}

Given a set <math>S</math>, the endofunctor of the '''state monad''' maps each set <math>X</math> to the set of functions <math>S\to S \times X</math>. The component of the unit at <math>X</math> maps each element <math>x\in X</math> to the function

:<math>\eta_X(x): S\to S\times X</math>
:<math>s\mapsto (s, x)</math>

The multiplication maps the function <math>f: S\to S\times (S\to S\times X), s\mapsto (s',f')</math> to the function

:<math>\mu_X(f): S\to S\times X</math>
:<math>s\mapsto f'(s')</math>

In functional programming and denotational semantics, the state monad models [[State (computer science)|stateful computations]].

====The environment monad====

{{Expand section|date=February 2023|with=describe multiplication}}

Given a set <math>E</math>, the endofunctor of the '''reader''' or '''environment monad''' maps each set <math>X</math> to the set of functions <math>E\to X</math>. Thus, the endofunctor of this monad is exactly the [[hom functor]] <math>\mathrm{Hom}(E, -)</math>. The component of the unit at <math>X</math> maps each element <math>x\in X</math> to the [[constant function]] <math>e\mapsto x</math>.

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

====The list and set monads====

{{Expand section|date=February 2023|with=describe multiplication}}

The '''list''' or '''nondeterminism monad''' maps a set ''X'' to the set of finite [[Sequence|sequences]] (i.e., [[List (abstract data type)|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 model of computation|nondeterministic computations]]. The covariant powerset monad is also known as the '''set monad''', and is also used to model nondeterministic computation.