Monad (category theory)

In category theory, a branch of mathematics, a monad is a special way to work with functions and their relationships. It is made up of three parts: a functor, and two natural transformations, which follow certain rules called associativity and unitality. Think of a monad like a set of instructions that help organize and combine operations in a neat way.

One way to understand a monad is to see it as a kind of generalized monoid, which is a structure with a rule for combining elements and an identity element. Monads can also help us study algebraic objects, like groups, by providing a clear framework to describe them.

Monads are important in many areas of mathematics and computer science. They are used in the study of pairs of adjoint functors and help generalize certain operations to work in any category. In computer science, monads are especially useful in the theory of datatypes, denotational semantics of imperative programming languages, and in functional programming languages. They even allow programmers to write effective loops in languages that normally do not support changing values directly. For more on this, see monads in functional programming.

Introduction and definition

A monad is a special kind of structure in mathematics, particularly in a field called category theory. It helps us understand how different mathematical ideas connect and work together.

Think of a monad as a way to apply a rule or process twice in a special pattern. For example, imagine you have two steps, F and G, that change one set of things into another. When you combine these steps in a certain way, you create a new process that follows special rules. This new process is what we call a monad.

The study of monads helps mathematicians see patterns and relationships between different areas of math. It shows how some ideas that seem different are actually related in deeper ways.

Examples

Identity

The identity functor on a category C is a monad. Its multiplication and unit are the identity function on the objects of C.

Monads arising from adjunctions

Any adjunction F : C ⇄ D : G gives rise to a monad on C. This very widespread construction works as follows: the endofunctor is the composite T = G ∘ F. This endofunctor is quickly seen to be a monad.

Double dualization

The double dualization monad, for a fixed field k arises from the adjunction (−)∗ : Vect_k ⇄ Vect_k^op : (−)∗ where both functors are given by sending a vector space V to its dual vector space V∗ := Hom(V, k). The associated monad sends a vector space V to its double dual V∗∗.

Closure operators on partially ordered sets

For categories arising from partially ordered sets (P, ≤) (with a single morphism from x to y if and only if x ≤ y), then the formalism becomes much simpler: adjoint pairs are Galois connections and monads are closure operators.

Free-forgetful adjunctions

For example, let G be the forgetful functor from the category Grp of groups to the category Set of sets, and let F be the free group functor from the category of sets to the category of groups. Then F is left adjoint of G. In this case, the associated monad T = G ∘ F takes a set X and returns the underlying set of the free group Free(X).

Another monad arising from an adjunction is when T is the endofunctor on the category of vector spaces which maps a vector space V to its tensor algebra T(V), and which maps linear maps to their tensor product.

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 FinSet ⊂ Set 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.

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: X ↦ X ∪ {∗}. The unit is given by the inclusion of a set X into X∗: x ↦ x. The multiplication maps elements of X to themselves, and the two disjoint points in (X∗)∗ to the one in X∗.

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 S, the endofunctor of the state monad maps each set X to the set of functions S → S × X. That is S(X) = {f: S → S × X}, and S(S(X)) = {f: S → S × (S → S × X)}.

The component of the unit at X maps each element x ∈ X to the function η_X(x): S → S × X s ↦ (s, x).

The multiplication maps the function f: S → S × (S → S × X), s ↦ (s′, f′) to the function μ_X(f): S → S × X s ↦ f′(s′).

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

The environment monad

Given a set E, the endofunctor of the reader or environment monad maps each set X to the set of functions E → X. Thus, the endofunctor of this monad is exactly the hom functor Hom(E, −). The component of the unit at X maps each element x ∈ X to the constant function e ↦ x.

The multiplication maps a two-variable function f: E → (E → X) to its "diagonal component" (e ↦ f(e, e)): E → X. In other words, multiplication is precomposition with Δ: E → E × E e ↦ (e, e).

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

When we have a special kind of math rule called a monad, we can look at how it acts on objects in a category. This helps us understand the structure better.

For example, if we have a rule for creating free groups, the objects that follow this rule are actually groups themselves. Another example is the "distribution monad," which deals with sets and functions that add up to one. This creates a special category of algebras that follow the rules of this monad.

Monads and adjunctions

When two parts of mathematics fit together very well, we call this an "adjunction." Every time this happens, it creates something called a monad. In fact, every monad comes from such a fitting-together of parts.

One common way this happens is through pairs of processes that are opposites, like one that builds something up and one that takes it apart. When we study these pairs, we can understand how to rebuild objects using the rules of the monad.

Uses

Monads are helpful in computer programming. They help describe steps in a program, especially when there are extra actions involved. You can read more about this in monads in functional programming.

They are also used to understand how programs mean things in a certain way. This connects to ideas in logic and how we think about rules and conditions.

Generalization

It is possible to define monads in a 2-category C. The monads described earlier are for the specific case where C is the category of categories, written as C = Cat.