↑ arvau

Wikipedia / Monad (category theory)

In category theory, a branch of mathematics, a monad consisting of a functor T from a category to itself and two natural transformations that satisfy versions of the associativity and unitality axioms. Equivalently, a monad is a monoid in the category of endofunctors of some fixed category (an endofunctor is a functor mapping a category to itself).

are functors adjoint determined by the adjoint relation is a monad.

According to mathematician 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,

  2. 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 are a pair of adjoint functors are inverse to each other, the corresponding monad is the identity functor. In general, adjunctions are not equivalences, is discussed under the dual theory of comonads.

Formal definition

denotes a category. A monad together with two natural transformations). These are required to fulfill the following conditions (sometimes called coherence conditions):

We can rewrite these conditions using the following commutative diagrams:See the article on natural transformations, or see below the commutative diagrams not using these notions:The first axiom is akin to the associativity in monoids as the monoid's binary operation, and the second axiom is akin to the existence of an identity element can alternatively be defined as a monoid 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 be the power set be the function between the power sets induced by taking direct images 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 a type of monoid object; they are precisely the monoids among endofunctors, with the multiplication given by composition of endofunctors.

does not admit any monad structure.

Comonads

The categorical dual definition is a formal definition of a comonad (or cotriple is a monad for the opposite category 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.

Examples

Identity

The identity functor is a monad. Its multiplication and unit are the identity function.

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

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-algebras).

Double dualization

The double dualization monad, for a fixed field k arises from the adjunction

where both functors are given by sending a vector space V to its dual vector space. 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 if and only if), then the formalism becomes much simpler: adjoint pairs are Galois connections and monads are closure operators.

Free-forgetful adjunctions

be the forgetful functor from the category Grp of groups to the category Set be the free group. The unit map of this monad is given by the maps

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.

to its tensor algebra into its tensor algebra 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

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:

:

.

In both functional programming and denotational semantics, the maybe monad models partial computations, that is, computations that may fail.

The state monad

, the endofunctor of the state monad.

to the function

to the function

.

so that

as

In functional programming and denotational semantics, the state monad models stateful computations.

The environment monad

, the endofunctor of the reader or environment monad. Thus, the endofunctor of this monad is exactly the hom functor to the constant function.

The multiplication maps a two-variable function. In other words, multiplication is precomposition with

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

, it is natural to consider -algebras called the structure map of the algebra such that the diagramscommute.

such that the diagram -algebras form a category called the Eilenberg–Moore category.

Examples

Algebras over the free group monad

is a group itself.

Algebras over the distribution monad

Another example is the distribution monadBy inspection of the definitions, it can be shown that algebras over the distribution monad are equivalent to convex sets in Euclidean space.

Algebras over the symmetric monad

to the direct sum of symmetric tensor-generators.

Commutative algebras in E-infinity ring spectra

There is an analogous construction for \mathbb{S}-algebraspg 113-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. An initial object is the Kleisli category consisting only of free T-algebras, i.e., T for some object x of C.

Monadic adjunctions

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 yields an equivalence of categories between D. 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 and only 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 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

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 b:Haskell/Category theory.

Monads are used in the denotational semantics of impure functional and imperative programming languages.

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.

Generalizations

Monads can be defined in a any weak 2-category as lax 2-functors from terminal category to 2-category Cat. The theory of 2-monads was introduced by Blackwell–Kelly–Power, and 2-monads without prefixes are usually a strict notion. A notion that weakens monad laws so that they hold "up to coherent invertible modifications" is called pseudomonad. While there are attempts to define monad preserving composition only up to a noninvertible transformation, there is no obvious general notion of lax monad on a weak 2-category, since there is no good 2-category (or even a weak 3-category) of weak 2-categories that contain lax or oplax functors. The lax monad was first introduced by Bunge, but other definitions different from lax monad à la Bunge.

See also

References

Further reading