Monad (category theory)

In category theory, a branch of mathematics, a monad is a special way to work with functions and how they relate to each other.

A monad has three parts: a functor, and two natural transformations. These parts follow certain rules called associativity and unitality. You can think of a monad like a set of instructions that help organize and combine operations neatly.

One way to understand a monad is to see it as a kind of generalized monoid. A monoid is a structure with a rule for combining elements and an identity element. Monads help us study algebraic objects, like groups, by giving a clear way 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. They also help generalize certain operations to work in any category.

In computer science, monads are very useful. They are used in the theory of datatypes, denotational semantics of imperative programming languages, and in functional programming languages. They even help programmers 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 idea in mathematics, especially in a part called category theory. It helps us see how different math ideas are connected.

Think of a monad as a way to use a rule or process two times in a special pattern. For example, imagine you have two steps, F and G, that change one group of things into another. When you put these steps together in a certain way, you make a new process that follows special rules. This new process is called a monad.

Studying monads helps mathematicians find patterns and links between different parts of math. It shows how some ideas that look different are really 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 common way to create monads works like this: the endofunctor is the combination T = G ∘ F. We can easily see that this endofunctor is a monad.

Double dualization

The double dualization monad, for a fixed field k, comes from the adjunction (−)∗ : Vect_k ⇄ Vect_k^op : (−)∗ where both functors send a vector space V to its dual vector space V∗ := Hom(V, k). The monad linked to this sends a vector space V to its double dual V∗∗.

Closure operators on partially ordered sets

For categories that come from partially ordered sets (P, ≤) (with a single morphism from x to y if and only if x ≤ y), the ideas become much simpler: pairs of adjoints 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 sets to groups. Then F is the left adjoint of G. Here, the monad T = G ∘ F takes a set X and gives the basic set of the free group Free(X).

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

Codensity monads

Under some simple conditions, functors that do not have a left adjoint can also create a monad, called the codensity monad. For example, the inclusion FinSet ⊂ Set does not have a left adjoint. Its codensity monad is the monad on sets that takes 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 similar ideas are used in functional programming.

The maybe monad

The endofunctor of the maybe or partiality monad adds a separate point: X ↦ X ∪ {∗}. The unit puts a set X into X∗: x ↦ x. The multiplication keeps elements of X the same, and combines the two separate points in (X∗)∗ into one in X∗.

In both functional programming and denotational semantics, the maybe monad represents computations that might not finish.

The state monad

Given a set S, the endofunctor of the state monad takes each set X to the set of functions S → S × X. So S(X) = {f: S → S × X}, and S(S(X)) = {f: S → S × (S → S × X)}.

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

The multiplication takes 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 represents computations that keep track of changing data.

The environment monad

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

The multiplication takes a function f: E → (E → X) to its "diagonal component" (e ↦ f(e, e)): E → X. Simply put, multiplication uses Δ: E → E × E e ↦ (e, e).

In functional programming and denotational semantics, the environment monad represents computations that use some read-only data.

The list and set monads

The list or nondeterminism monad takes a set X to the set of finite sequences (lists) of elements from X. The unit takes an element x in X to the single-item list [x]. The multiplication joins a list of lists into one list.

In functional programming, the list monad is used to represent computations that may have many possible results. The covariant powerset monad, also called the set monad, is used for the same purpose.

Algebras for a monad

See also: F-algebra and pseudoalgebra

When we have a special kind of math rule called a monad, we can see how it works 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 groups themselves. Another example is the "distribution monad," which deals with sets and functions. 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 useful in computer programming. They help explain steps in a program, especially when there are extra actions to do. You can read more about this in monads in functional programming.

They are also used to understand how programs give meaning to things. This links to ideas in logic and how we think about rules and conditions.

Generalization

We can describe monads in a 2-category called C. The monads we talked about before are for when C is the category of categories, written as C = Cat.