nLab monad

Contents

This entry is about the notion of monad in category theory and categorical algebra. For other notions see monad (disambiguation).


Contents

Idea

In category theory, the notion of monad (earlier: “standard construction” or “triple”) is a kind of categorification of that of monoid: In their default incarnation monads are endofunctors on some category which are equipped with a unital associative binary operation under composition. More generally this notion makes sense for endo- 1-morphisms on any object in any 2-category beyond Cat: Monads are monoid objects internal to endo-hom-categories.

Together with the adjunctions (adjoint functors) that they correspond to (see below) monads are among the most pervasive structures in category theory (where they form the basis of categorical and universal algebra, whence one speaks of algebras over a monad) and in mathematics more generally (certainly in fields like algebraic topology, sheaf and topos theory and homological algebra, where the notion originates in the guise of “canonical resolutions”).

Last not least, monads play a central role in formal logic (cf. modal logic and modal type theory) and in computer science, where they are understood (cf. the “computational trilogy”) as encoding “notions of computation” with “computational effects” in the framework of functional programming: see at monads in computer science.

Etymology

The terminology “monad” was introduced in Bénabou 1967, Def. 5.4.1, where, after observing (Exp. 5.4.1) that monads in 1-object 2-categories (deloopings of monoidal categories) are monoids:

it says in a footnote:

(from Bénabou 1967, p. 40)

Beyond this footnote, the only contemporary account that seems to exist of the terminological genesis, Barr 2009, recalls the following exchange, on the backdrop of a widely felt dissatisfaction with the earlier terminology of “standard construction” and “triple”:

In the summer (or maybe late spring, the Oberwohlfach records will show this) of 1966, there was a category meeting there. […] One day at lunch or dinner I happened to be sitting next to Jean Bénabou and he turned to me and said something like “How about `monad'?" I thought about and said it sounded pretty good to me. So Jean proposed it to the general audience and there was general agreement. It suggested "monoid" of course and it is a monoid in a functor category.

Further discussion on the issue in 2023 has recollections by Jirí Adámek of recollections by Bill Lawvere to the extent that:

it was in the common room of the old castle at Oberwolfach when Sammy [Samuel Eilenberg] came out from behind the piano and announced the change.

But Michael Barr clarifies that:

I am more than willing to believe that it was Bénabou sitting next to me who proposed monad. It is entirely possible that Sammy came down and pronounced it “official”. And it was certainly in the old castle.

Interestingly Bénabou’s footnote above gives a second motivation for “monad”:

It is striking that Bénabou 1967, Def. 5.4.1 defines a monad to be a lax 2-functor from the terminal category 11 to the 2-category of categories (and more generally to whatever given ambient 2-categoryS̲\underline{S}”) and then proceeds to unwind the equivalence of this definition to the traditional one:

Monads(S̲){1laxS̲}. Monads(\underline{S}) \;\;\; \simeq \;\;\; \Big\{ 1 \xrightarrow{\; lax \;} \underline{S} \Big\} \,.

In this sense, monads are point-like elements in a 2-category theoretic sense (say in the 2-topos Cat), which squares well with Euclid’s ancient notion of monads as indivisible building blocks. In fact, as discussed there, “monad” (both in ancient and still in modern Greek) just means “unit” in the sense of the unit natural number 11, and Bénabou 1967, Def. 5.4.1 literally identifies monads with the (lax) units 1S̲1 \to \underline{S} in the ambient 2-category.

In generalization of this situation, one may consider lax functors out of codiscrete groupoids CoDisc(1 n)CoDisc(1^{\sqcup_n}) on nn objects, which Bénabou 1967, Def. 5.5 calls polyads:

Polyads(S̲){CoDisc(1 n)laxS̲}. Polyads(\underline{S}) \;\;\; \simeq \;\;\; \Big\{ CoDisc(1^{\sqcup_n}) \xrightarrow{\; lax \;} \underline{S} \Big\} \,.

On the other hand (as maybe alluded to in the first line of Barr 2009), just a few years earlier the ancient monad terminology had already been adopted in nonstandard analysis as the term for infinitesimal neighbourhoods (Robinson 1966, p. 57 and Luxembourg 1966, compare also Keisler 1976, Def. 1.2, Kutateladze 2011 and, speaking synthetically: Kock 1980).

Now it so happens — in the topos theoretic formulation of infinitesimals via differential cohesion — that the construction of infinitesimal neighbourhoods is (see here) a monad in the sense of category theory! – namely the left adjoint monad to the jet comonad (Khavkine & Schreiber 2017, p. 23).

Definition

Monads

A monad in a bicategory KK is given by

  1. an object aa in KK

  2. an endomorphism t:aat \colon a \to a in KK

  3. a 2-morphism η:1 at\;\eta \colon 1_a \to t in KK

    (the unit or return operation)

  4. a 2-morphism μ:ttt\mu \colon t \circ t \to t

    (the multiplication or join operation)

such that the diagrams commute (where certain coherence isomorphisms have been omitted).

The name “monad” and the terms “unit”, “multiplication” and “associativity” bear a clear analogy with monoids (but see also at monad (disambiguation)). Indeed, one can define a monad on an object aa of a bicategory KK as just a monoid object in the endomorphism category K(a,a)K(a,a). Alternatively, monads can be taken as more fundamental, and a monoid in a monoidal category CC can be defined as a monad in BC\mathbf{B} C, the one-object bicategory corresponding to CC.

A third and somewhat less obvious definition says that a monad in KK is a lax 2-functor from the terminal bicategory 11 to KK: the unique object *\ast of 11 is sent to the object aa, the morphism 1 a1_a becomes tt, and η\eta and μ\mu arise from the coherent 2-cells expressing lax functoriality. This in turn is equivalent to saying that a monad is a category enriched in a bicategory with a single object and single morphism. Among higher-category theorists, it’s tempting to suggest that this is the most fundamental definition, and the most basic reason for the ubiquity and importance of monads. Regardless of this, however, the earlier more elementary definitions are both practically and pedagogically essential.

Finally, a monad can be defined in terms of the “Kleisli operation” taking any map aTba \to T b to a map TaTbT a \to T b; see extension system.

We can picture a monad in KK as an image of the third oriental in KK. See the remarks at monoidal category.

The data of and axioms for a monad can be expressed graphically as string diagrams. Writing T:CC,η,μT \colon C \to C, \eta, \mu for the monad in question (this notation being the standard one when K=CatK = Cat), these data can be represented as

String diagrams of the monad data (for "Monad")

Thanks to the distinctive shapes, one can usually omit the labels:

String diagrams of the monad data, unlabeled (for "Monad")

The axioms then appear as:

String diagrams of the monad axioms, unlabeled (for "Monad")

The 2-category of monads

Given the equivalence between monads in a 2-category KK and lax functors 1K1 \to K [Bénabou 1967, pp. 39] it is straightforward to define the 2-category Mnd(K)Mnd(K) of monads in KK to be the lax functor category [1,K] [1,K]_\ell, which consists of lax functors, lax transformations and theirmodifications.

Spelling this out [Maranda 1966, Maranda 1968, Frei 1969 p. 269, Pumplün 1970 p 330 & 334, Coppey 1970, Street 1972 p. 150-151, review in Leinster 2004 pp. 148]:

Definition

(2-category of monads)
Let KK be a 2-category.

  1. An object in Mnd(K)Mnd(K) is a monad (a,t,η,μ)(a,t,\eta,\mu) in KK;

  2. a 1-morphism (a,t)(b,s)(a,t) \to (b,s) in Mnd(K)Mnd(K) (“monad functor” or “monad transformation”)

    is given by

    1. a 1-morphism x:abx \colon a \to b in KK

    2. a 2-morphism λ:sxxt\lambda \colon s x \to x t in KK

    making the following diagrams commute:

    x η sx sx xη t λ xt 1 xtssx sλ sxt λt xtt μ sx xμ t sx λ xt \array{ x & \stackrel{\eta^s x}{\to} & s x \\ \mathllap{x \eta^t} \big\downarrow & & \big\downarrow \mathrlap{\lambda} \\ x t & \overset{1}{\longrightarrow} & x t } \qquad \qquad \array{ s s x & \overset{s \lambda}{\to} & s x t & \overset{\lambda t}{\longrightarrow} & x t t \\ \mathllap{\mu^s x} \big\downarrow & & & & \big\downarrow \mathrlap{x \mu^t} \\ s x & & \overset{\lambda}{\longrightarrow} & & x t }
  3. a 2-morphism (x,λ)(y,κ)(x,\lambda) \Rightarrow (y, \kappa) in Mnd(K)Mnd(K) is given by

    • a 2-morphism m:xym \colon x \Rightarrow y in KK

    making the following diagram commute

    sx sm sy λ κ xt mt yt \array{ s x & \stackrel{s m}{\to} & s y \\ \mathllap{\lambda} \downarrow & & \downarrow \mathrlap{\kappa} \\ x t & \stackrel{m t}{\to} & y t }

Remark

(handedness of the underlying natural transformation)
Beware that λ\lambda in Def. is oriented oppositely to what one might expect. This need not be so but is a possible choice, see Pumplün 1970 p 334, Street 1972 pp 158.

One issue is that the functor between Kleisli categories induced by a monad morphism goes in the direction opposite of λ\lambda as defined above (as generally for extension of scalars of module objects along a homomorphism of monoids), so that for authors who adopt the opposite of the above convention (such as Frei 1969 p. 269, Pumplün 1970 p 330, Barr & Wells 1985 §6.1 and in our Exp. below) the association of monad morphisms to functors between Kleisli catgeories is contravariant (eg. Frei 1969, Thm. 2, Barr & Wells 1985 Thm. 6.3).

Example

(transformation of monads on a fixed category)
This example is the simpler but important special case of the general Def. where the monads all act on the same fixed object – in particular the same category if K=CatK = Cat (stated in this form for instance in Barr & Wells 1985 §6.1), of relevance notably for monads in computer science (where this is Moggi 1989 Def. 4.0.11) which typically all act on the same category of data types:

For a pair of monads (,ret ,join )(\mathcal{E}, ret^{\mathcal{E}}, join^{\mathcal{E}}), (,ret ,join )(\mathcal{E}', ret^{\mathcal{E}'}, join^{\mathcal{E}'}) on a fixed category C\mathbf{C}:

,:CC, \mathcal{E}, \mathcal{E}' \;\colon\; \mathbf{C} \longrightarrow \mathbf{C} \,,

a morphism between them is

such that it respects, in the evident way, the monad units

and the joins:

in that it makes these squares commute.

Remark

A monad transformation as in Exp. contravariantly induces a functor of Eilenberg-Moore categories of modales by extension of scalars [Frei 1969, Thm. 2, Barr & Wells 1985 thm. 6.3]:

Since this extension of scalars is the identity on underlying objects, it cannot in general restrict to a functor on Kleisli categories.

However, when the monad transformation tr:tr \,\colon\, \mathcal{E} \to \mathcal{E}' is an isomorphism then tr *tr^\ast does take free modales to free modales up to isomorphism. This is seen from the following diagram:

(D) (tr D) (D) trans (D) (D) join D trans *join D join D (D) trans D (D) = (D) \array{ \mathcal{E} \mathcal{E}(D) & \overset{ \mathcal{E}(tr_D) }{\longrightarrow} & \mathcal{E} \mathcal{E}'(D) & \overset{ trans ^{\mathcal{E} \to \mathcal{E}'} _{\mathcal{E}'(D)} }{\longrightarrow} & \mathcal{E}' \mathcal{E}'(D) \\ \Big\downarrow\mathrlap{ {}^{ join^{\mathcal{E}}_D } } && \Big\downarrow\mathrlap{ {}^{ trans^\ast join^{\mathcal{E}'}_D } } && \Big\downarrow\mathrlap{ {}^{ join^{\mathcal{E}'}_D } } \\ \mathcal{E}(D) & \underset{ \;\; trans^{\mathcal{E} \to \mathcal{E}'}_D \;\; }{\longrightarrow} & \mathcal{E}'(D) &=& \mathcal{E}'(D) }

Here the middle vertical morphism is the nominal image under extension of the free modale on the right along trans trans^{\mathcal{E} \to \mathcal{E}'}, but the square on the left, which commutes by assumption on trans trans^{\mathcal{E} \to \mathcal{E}'}, exhibits an isomorphism from the middle modale to the \mathcal{E}-free modale on the left.

Remark

(monad transfomers)
When monads are used to model computational effects in functional programming, a common concern is to combine different effects, such that previous effects are subsumed among the newly combined effects. This is formalized by “monad transformers” which are systems of morphisms of monads as in Exp. , forming a pointed endofunctor on the category MndMnd of all monads.

Example

The initial object in the category of monads on a fixed category C\mathbf{C} (Exp. ) is the identity monad.

Proof

We need to show that for every monad \mathcal{E} on C\mathbf{C} there is a natural transformation trans Id:Idtrans^{Id \to \mathcal{E}} \,\colon\, Id \to \mathcal{E} which makes, first of all, this square commute:

and this already fixes the transformation to be the monad unit of \mathcal{E}, as shown – such that, secondly, this square commutes:

which is the case by the unitality clause on \mathcal{E}, as indicated.


Algebras/modules over a monad

Given that a monad in a bicategory \mathcal{B} is nothing but a monoid object in a hom-category (a,a)\mathcal{B}(a,a), it is natural to consider a module over this monoid: a module for a monad. This notion of module is more general than a module in a monoidal category, however, since it need not live in (a,a)\mathcal{B}(a,a) but can be in (b,a)\mathcal{B}(b,a) (for left modules) or (a,c)\mathcal{B}(a,c) (for right modules).

In a Cat-like bicategory, left modules over a monad are usually known as algebras over the monad. This terminology is confusing from the point of view of monads as monoids, but is justified because in Cat itself, such algebras with domain 1 are just algebras for a monad in the classical sense. Such algebras are a powerful tool to encode general algebraic structures; this is the topic of universal algebra. The algebras over a monad form its Eilenberg-Moore category, which is characterized by a universal property.

Some monads arise from operads, in which case algebras for the monad are the same as algebras for the operad. A Lawvere theory is another special sort of monad in CatCat.

Properties

Relation between adjunctions and monads

There is a close relation between adjunctions (adjoint functors) and monads:

Monad induced by an adjunction

Every adjunction (LR)(L \dashv R) induces a monad RLR \circ L and a comonad LRL \circ R.

(Huber 1961, §4; see eg. MacLane 1971, §VI.1 (p 134); Borceux 1994, vol. 2, prop. 4.2.1).

In detail:

Proposition

Let (𝒞,𝒟,F,U,η,ϵ)(\mathcal{C},\mathcal{D},F,U,\eta,\epsilon) be a pair of adjoint functors ie FUF \dashv U are adjoint functors where F:𝒞𝒟F \colon \mathcal{C} \rightarrow \mathcal{D}, U:𝒟𝒞U \colon\mathcal{D} \rightarrow \mathcal{C}, η A:AU(F(A))\eta_{A}:A \rightarrow U(F(A)) is the unit and ϵ B:F(U(B))B\epsilon_{B} \colon F(U(B)) \rightarrow B is the counit. Then:

  • UFU \circ F is a monad on 𝒞\mathcal{C}, with unit η\eta and multiplication U(ϵ F(A)):U(F(U(F(A))))U(F(A))U(\epsilon_{F(A)}):U(F(U(F(A)))) \rightarrow U(F(A)).

  • FUF \circ U is a comonad on 𝒟\mathcal{D}, with counit ϵ\epsilon and comultiplication F(η U(B)):F(U(B))F(U(F(U(B))))F(\eta_{U(B)}):F(U(B)) \rightarrow F(U(F(U(B)))).

Proof

We verify that we obtain a monad, the argument for the comonad is formally dual.

(1) We know that this diagram commutes:

By applying UU, we obtain the first part of the unitaly of the monad:

(2) We know that this diagram commutes: By putting B=F(A)B=F(A), we obtain the second part of the unitality of the monad:

(3) The naturality of ϵ\epsilon is written, for every f:BBf:B \rightarrow B':

We apply it to f=ϵ F(A)f=\epsilon_{F(A)} and it gives:

Finally apply UU to this diagram to obtain:

which is exactly the associativity of the multiplication of the monad.

(4) The naturality of the multiplication U(ϵ F(A)):U(F(U(F(A))))U(F(A))U(\epsilon_{F(A)}):U(F(U(F(A)))) \rightarrow U(F(A)) is obtained by two whiskerings of the counit ϵ B:U(F(B))B\epsilon_{B}:U(F(B)) \rightarrow B.

Category of adjunction-resolutions of a monad

An adjunction inducing a monad TT (as above) is also called a resolution of TT.

There is in general more than one such resolution, in fact there is a category of adjunctions for a given monad whose morphisms are “comparison functors” (eg. MacLane 1971, §VI.3).

In this category:

(e.g. Borceux 1994, vol. 2, prop. 4.2.2)

Semantics-structure adjunction

The above passage from adjunctions to monads and back to their monadic adjunctions constitutes itself an adjunction, sometimes called the semantics-structure adjunction.

Examples

Monads on SetSet

Many of these monads also have standard usages as monads in computer science.

Example

The free-forgetful adjunction between pointed sets and sets induces an endofunctor () *:SetSet(-)_* : Set \to Set which adds a new disjoint point. This is called the maybe monad in computer science.

Example

The free-forgetful adjunction between monoids and sets induces an endofunctor T:SetSetT : Set \to Set defined by

TA:= n0A nTA := \bigsqcup_{n \ge 0} A^n

giving the free monoid monad. This also goes by the name list monad or Kleene-Star? in computer science. The components of the unit η A:ATA\eta_A : A \to T A give inclusions sending each element of AA to the corresponding singleton list. The components of the multiplication μ A:T 2ATA\mu_A : T^2 A \to T A are the concatenation functions, sending a list of lists to the corresponding list (Known as flattening in computer science). This monad can be defined in any monoidal category with coproducts that distribute over the monoidal product.

Example

For a fixed set of “states” SS, the (S×() SS \times - \dashv (-)^S)-adjunction induces a monad (S×) S(S \times -)^S on SetSet called the state monad. This is a commonly used monad in computer science. In functional programming languages such as Haskell, states can be used to model “side effects” of computations.

Example

The contravariant power set-functor is its own right adjoint, giving Set(A,PB)Set(B,PA)\Set(A,P B) \cong \Set (B, P A). Note that hom(A,PB)=hom(A,hom(B,Ω))hom(A×B,Ω)=P(A×B)\hom(A, P B) = \hom(A, \hom(B,\Omega)) \cong \hom( A \times B, \Omega) = P(A \times B) inducing a double power set monad taking a set AA to P 2AP^2 A. The components of the unit are the principal ultrafilter functions η A:AP 2A\eta_A \colon A \to P^2 A which send an element aa to the set of subsets of AA that contain aa. The components of the multiplication μ A\mu_A is the inverse image function for the map η PA:PAP 3A\eta_{P A} \colon P A \to P^3 A; which can be painfully stated as: the function taking a set of sets of sets of subsets to the set of subsets of AA with the property that one of the sets of sets of subsets is the set of all sets of subsets of AA that include that particular subset as an element.

Replacing the two element power object Ω\Omega with any other set gives similar monads. In computer science contexts these are known as continuation monads. This construction can also be generalised for any other bi-closed monoidal category. For example there is a similar double dual monad on Vect k \Vect_k .

Example

function monad (also “reader monad”, cf. coreader comonad)

Example

possibility

Example

selection monad

Algebra

Example

The free-forgetful adjunction between sets and the category of RR-modules. This induces the free RR-module monad R[]:SetSetR[-] : Set \to Set. The free abelian group monad and free vector space monad are special cases.

Example

The free-forgetful adjunction between sets and the category of groups gives the free group monad F:SetSetF : Set \to Set that sends AA to the set F(A)F(A) of finite words in the letters aAa \in A together with inverses a 1a^{-1}.

Topology

Example

There is a forgetful functor U:TopSetU : \Top \to \Set taking a topological space to its underlying set. It is right adjoint to the discrete space functor D:SetTopD: \Set \to \Top taking a set to its discrete topology. There is also an adjoint pair βU\beta \dashv U' between the category of compact Hausdorff topological spaces and the category of topological spaces, where β\beta is the Stone-Cech compactification. The composites of these two adjoint pairs gives a monad β:SetSet\beta : \Set \to \Set sending a set to its underlying set of the Stone-Cech compactification of its discrete space. It is also known as the ultrafilter monad as β\beta can be thought of as the functor taking a set to its set of ultrafilters.

Monads in Cat

Monads are often considered in the 2-category Cat where they are given by endofunctors with a monoid structure on them. In particular, monads in Cat on Set are equivalent to the equational theories studied in universal algebra. In this context, a monad abstracts the concept of an algebraic theory (such as “group” or “ring”), giving a general notion of extra structure on an object of a category.

Classically, if T\mathbf{T} is an algebraic theory (e.g. the theory of groups), a T\mathbf{T}-structure on a set tells us how to interpret various terms (e.g. (ac)(a\cdot c)) formed from elements of the set, subject to certain axioms (e.g. (a(bc))=((ab)c)(a\cdot (b\cdot c))=((a\cdot b)\cdot c)). A monad collects this up into a functor TT. For a set XX, TXT X is the set of all terms of the theory formed from elements of XX, with terms identified if axioms force them to be equal. For groups, TXT X is thus the (underlying set of the) free group of formal words absa \cdot b \cdot \cdots \cdot s from XX; the fact that TT gives free structures turns out to be typical.

To capture the theory fully, we need to include a little more data: a natural map η X:XTX\eta_X : X \to T X recording how each aXa \in X gives a trivial term aa, and a map μ X:TTXTX\mu_X:T T X \to T X recording how further terms built from terms are already present as terms in TXT X.

Given a monad in Cat on a category CC, one can always produce a canonical resolution of any object of CC.

Other examples

Monads in higher category theory

There is a vertical categorification of monads to (∞,1)-categories. See (∞,1)-monad.

in section 3 of

References

The notion of (co)monads was introduced under the name “standard construction” (namely what is now thought of as their induced canonical resolution) in:

following:

  • Roger Godement, Appendix of: Topologie algébrique et theorie des faisceaux, Actualités Sci. Ind. 1252, Hermann, Paris (1958) [webpage, pdf]

    (where the monad laws appear on p. 272 as part of the structure of the induced canonical resolution, called there the “fundamental construction”).

In the early category theory-literature monads were called triples, referring to the fact that (just as for monoids) their data-structure is that of triples consisting of: (1.) the underlying category, (2.) a binary operation and (3.) a unit operation:

The modern terminology “monad” (and the definition in the generality internal to any bicategory) is (cf. Barr 2009) due to:

Further historical comments:

Further original texts:

Further textbook accounts:

Expositions:

More on the relation to universal algebra:

An elementary proof of the equivalence between infinitary Lawvere theories and monads on the category of sets is given in Appendix A of

In higher category theory:

Last revised on January 22, 2024 at 07:13:03. See the history of this page for a list of all contributions to it.