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.

Metatheory. Free-forgetful adjunction induces monad. Every monad from adjunction. Distributive laws for composition. Monad transformers.

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

Limitations. Composition not automatic. Transformer overhead. Not all effects monadic. Learning curve.

© 2026 Lingenic LLC