Monads

Origin. Godement (1958), Eilenberg-Moore (1965). Endofunctor with unit and multiplication. Encapsulates computational effects. Kleisli category for sequencing. Foundation for effectful programming.

Models. Monad T: C → C with η: Id → T, μ: T² → T. Laws: associativity and identity. Algebras: structured objects. Computational interpretation: effects.

Formalism.

Monad: (T, η, μ) where T: C → C η: Id_C → T (unit) μ: T ∘ T → T (multiplication)

Monad laws: μ ∘ Tμ = μ ∘ μT (associativity) μ ∘ Tη = id_T = μ ∘ ηT (unit laws)

Kleisli category: Objects: same as C. Morphisms A → B: morphisms A → TB in C. Composition: g ∘_K f = μ ∘ Tg ∘ f

Kleisli triple: (T, η, —) where —: (A → TB) → (TA → TB) f*: TA → TB extends f: A → TB

Examples: Maybe/Option: T(A) = A + 1 (partial functions) List: T(A) = A* (nondeterminism) State: T(A) = S → (A × S) (stateful computation) Continuation: T(A) = (A → R) → R

Eilenberg-Moore category: Objects: T-algebras (A, α: TA → A) Structure maps satisfying laws.

Strong monad: On a monoidal category, a strength t_{A,B} : A × TB → T(A × B), natural and compatible with η and μ. The mirror map t'_{A,B} : TA × B → T(A × B) is the costrength; on a cartesian category each determines the other by symmetry.

Commutative monad: A strong monad is commutative when the two ways of merging a pair of effects agree: μ ∘ T(t) ∘ t' = μ ∘ T(t') ∘ t : TA × TB → T(A × B) Left path: t' first, running the A-effect outermost; right path: t first, running the B-effect outermost. Both are maps TA × TB → T(A × B), and commutativity says the order of the two effects does not matter.

This is a condition on strength, not on μ alone — an equation between two derived operations, which is why it cannot be stated in η and μ by themselves.

Commutative: powerset, probability distributions, Maybe, reader. Not commutative: state (the two effects read and write in different orders) and list — with [1,2] and [3,4] one path gives [(1,3),(1,4),(2,3),(2,4)] and the other [(1,3),(2,3),(1,4),(2,4)], the same pairs in a different order. Commutativity is what licenses evaluating independent effectful subterms in parallel, or in either order.

Symbols.

Symbol	Unicode	Name	Meaning
η	U+03B7	Eta / Unit	The natural transformation Id → T; return
μ	U+03BC	Mu / Multiplication	The natural transformation T² → T; join
α	U+03B1	Alpha	Structure map TA → A of an Eilenberg–Moore algebra
ε	U+03B5	Epsilon	Counit of the adjunction inducing the monad
λ	U+03BB	Lambda	A distributive law ST → TS
∘	U+2218	Composition	Composite of functors or natural transformations
²	U+00B2	Superscript two	The iterate T² = T ∘ T
×	U+00D7	Product	Domain of strength, A × TB
→	U+2192	Arrow	A morphism, a functor, or a function type
⊣	U+22A3	Adjoint	F ⊣ G, the adjunction whose composite is the monad
′	U+2032	Prime	Distinguishes the costrength t′ from the strength t
—	U+2014	Em dash	The argument placeholder in the Kleisli extension
T	—	Monad	The endofunctor carrying the structure
—*	—	Kleisli extension	Bind
>>=	—	Bind	Sequencing
t, t′	—	Strength, costrength	A × TB → T(A×B); TA × B → T(A×B)
_K	—	Kleisli composition	Composition in the Kleisli category
S	—	State object	The store in the state monad, and a second monad
R	—	Answer type	The result type of the continuation monad

Metatheory. Every adjunction F ⊣ G induces a monad GF with unit the unit of the adjunction and multiplication GεF, and every monad arises this way: Kleisli (1965) and Eilenberg and Moore (1965) construct the two extreme resolutions, and the adjunctions inducing a fixed monad form a category in which the Kleisli one is initial and the Eilenberg–Moore one terminal. Beck's monadicity theorem (1966) says a right adjoint G is monadic exactly when it reflects isomorphisms and its domain has, and G preserves, coequalizers of G-split pairs. Composition is governed by Beck's distributive laws (1969): a law ST → TS satisfying four coherence conditions makes TS a monad, and without one the composite carries no canonical structure. Kock (1970, 1972) showed strength is the same as enrichment and that commutative monads coincide with symmetric monoidal monads, and Moggi's "Notions of Computation and Monads" (1991) made strong monads over a cartesian closed category the semantics of the computational lambda calculus. Finitary monads on Set correspond exactly to Lawvere theories.

Applies to. Functional programming (Haskell). Effect systems. Denotational semantics. Database queries. Probabilistic programming.

Limitations. Monads do not compose: TS is not a monad in general, a distributive law need not exist, and the failure is provable rather than incidental — there is no distributive law of the powerset monad over the finite-distribution monad, so nondeterminism and probability have no monadic combination, and Zwart and Marsden's no-go theorems (2019) rule laws out for wide classes of algebraic monads. Monad transformers are a workaround with no universal property: they are chosen constructions, the resulting stack depends on the order, and operations algebraic for one monad need not lift through another transformer, with the continuation transformer the standard failure. Not every effect is monadic — the continuation monad arises from no algebraic theory, and effect handling is not an algebraic operation, so it cannot be presented as a Kleisli map. A monad fixes evaluation order in its Kleisli composition, and only commutative monads license reordering or parallel evaluation. A monad also grades nothing: it assigns one effect type to a whole computation, which is why graded and parameterized monads were introduced.