natural deduction metalanguage, practical foundations
type theory (dependent, intensional, observational type theory, homotopy type theory)
= + +
/ | -/ | |
, | ||
of / of | ||
for | for hom-tensor adjunction | |
introduction rule for | for hom-tensor adjunction | |
( of) | ( of) | |
into | into | |
( of) | ( of) | |
, , | ||
higher | ||
/ | -// | |
/ | ||
, () | , | |
(, ) | / | |
(absence of) | (absence of) | |
In computer science, a monad describes a “notion of computation”. Formally, it is a map that
sends every type $X$ of some given programming language to a new type $T(X)$ (called the “type of $T$-computations with values in $X$”);
is equipped with a rule for composing two functions of the form $f : X \to T(Y)$ (called Kleisli functions) and $g : Y \to T(Z)$ to a function $g \circ f : X \to T (Z)$ (their Kleisli composition);
is in a way that is associative in the evident sense and unital with respect to a given unit function called $pure_X : X \to T(X)$, to be thought of as taking a value to the pure computation that simply returns that value.
This is essentially the same structure as a monad in category theory, but presented differently; see below for the precise relationship.
Monads provide one way to “embed imperative programming in functional programming”, and are used that way notably in the programming language Haskell. But monads, as well as comonads and related structures, exist much more generally in programming languages; an exposition is in (Harper). For an account of the use of monads in industry see Benton15, pp. 11-12.
For instance when the monad $T(-)$ forms product types $T(X) \coloneqq X \times Q$ with some fixed type $Q$ that carries the structure of a monoid, then a Kleisli function $f : X \to Y \times Q$ may be thought of as a function $X \to Y$ that produces a side effect output of type $Q$. The Kleisli composition of two functions $f \colon X \to Y \times Q$ and $g \colon Y \to Z \times Q$ then not only evaluates the two programs in sequence but also combines their $Q$-output using the monoid operation of $Q$; so if $f x = (y,q)$ and $g y = (z,q')$ then the final result of $(g \circ f)(x)$ will be $(z, q q')$. For example, $Q$ might be the set of strings of characters, and the monoid operation that of concatenation of strings (i.e. $Q$ is the free monoid on the type of characters). If the software is designed such that values of type $Q$ computed in this way appear on the user’s screen or are written to memory, then this is a way to encode input/output in functional programming (see the IO monad? below).
But monads have plenty of further uses. They are as ubiquituous (sometimes in disguise) in computer science as monads in the sense of category theory are (sometimes in disguise) in category theory. This is no coincidence, see Relation to monads in category theory below.
In computer science, a programming language may be formalised or studied by means of a category, called the syntactic category $\mathcal{C}$, whose
morphisms$X \to Y$ are the terms or programs (or an equivalence class of such) that takes a value of type $X$ as input and returns a value of type $Y$.
This point of view (see computational trinitarianism) is particularly useful when studying purely functional programming languages.
Under this relation between type theory and category theory monads on the type system in the sense of computer science are monads in the sense of category theory, being certain endofunctors
on the syntactic category. This functor
sends each type, hence object $X \in \mathcal{C}$ to another object $T(X)$;
the unit natural transformation $\epsilon \colon Id_{\mathcal{C}} \Rightarrow T$ of the monad $T$ provides for each type $X$ a component morphism $pure_X : X \to T(X)$;
the multiplication natural transformation $\mu \colon T \circ T \Rightarrow T$ of the monad provides for each object $X$ a morphism $\mu_X : T(T(X)) \to T(X)$ which induces the Kleisli composition by the formula
Here the morphism $T(g)$ in the middle of the last line makes use of the fact that $T(-)$ is indeed a functor and hence may also be applied to morphisms / functions between types. The last morphism $\mu(Z)$ is the one that implements the “$T$-computation”.
The monads arising this way in computer science are usually required also to interact nicely with the structure of the programming language, as encoded in the structure of its syntactic category; in most cases, terms of the language will be allowed to take more than one input, so the category $\mathcal{C}$ will be at least monoidal, and the corresponding kind of ‘nice’ interaction corresponds to the monad’s being a strong monad.
The ‘bind’ operation is a means of describing multiplication on such a strong monad $M$. It is a term of the form $M A \to (M B)^A \to M B$, which is equivalent to a map of the form $M A \times M B^A \to M B$. It is the composite
where $m \colon M M \to M$ is the monad multiplication.
When monads are defined in Haskell, the Kleisli composition, ‘bind’, is defined in Haskell. So monads in Haskell are always enriched monads, according to the self-enrichment defined by the function type in Haskell.
Various monads are definable in terms of the the standard type-forming operations (product type, function type, etc.). These include the following.
A functional program with input of type $X$, output of type $Y$ and mutable state $S$ is a function (morphism) of type $X \times S \longrightarrow Y \times S$. Under the (Cartesian product $\dashv$ internal hom)-adjunction this is equivalently given by its adjunct, which is a function of type $X \longrightarrow [S, S \times Y ]$. Here the operation $[S, S\times (-)]$ is the monad induced by the above adjunction and this latter function is naturally regarded as a morphism in the Kleisli category of this monad. This monad $[S, S\times (-)]$ is called the state monad for mutable states of type S.
The maybe monad is the operation $X \mapsto X \coprod \ast$. The idea here is that a function $X \longrightarrow Y$ in its Kleisli category is in the original category a function of the form $X \longrightarrow Y \coprod \ast$ so either returns indeed a value in $Y$ or else returns the unique element of the unit type/terminal object $\ast$. This is then naturally interpreted as “no value returned”, hence as indicating a “failure in computation”.
The continuation monad for a given type $S$ acts by $X \mapsto [[X,S],S]$.
A number of further monads are similarly definable in terms of standard type-forming operations, such as the reader monad and the writer comonad.
Given a type $W$, then the reader monad is the operation of forming the function type $[W,-] = (W\to (-))$; the writer comonad is the operation of forming the product type $W\times (-)$ and the composite of writer followed by reader is the state monad $[W, W \times (-)]$.
When $W$ carries the structure of a monoid object then writer also inherits the structure of a monad (on top of being a comonad) and converse for reader.
Other monads may be supplied “axiomatically” by the programming language, This includes
The completion monad may be used, as in constructive analysis, for dealing for instance with real numbers.
Equipping homotopy type theory (say implemented as a programming language concretely in Coq or Agda) with two axiomatic idempotent monads, denoted $\sharp$ and $\Pi$, with some additional data and relations, turns it into cohesive homotopy type theory. See also modal type theory.
Examples of (co)monads in (homotopy) type theory involve in particular modal operators as they appear in
See also
For an approach to composing monads, see
Another approach to modelling side effects in functional programming languages are
Free monads in computer science appear in the concepts of
Other generalizations are
There is also
The original reference for monads as ‘notions of computation’ is
The impact of Moggi’s work is assessed and a case for Lawvere theories is made in
Effects treated this way are known as algebraic effects.
Expositions of monads in computer science include
Philip Wadler, Comprehending Monads, in Conference on Lisp and functional programming, ACM Press, 1990 (pdf)
Philip Wadler, Monads for functional programming in Lecture notes for the Marktoberdorf Summer School on Program Design Calculi, Springer Verlag 1992
Philip Mulry?, Monads in semantics , ENTCS 14 (1998) pp.275-286.
John Hughes, section 2 of Generalising Monads to Arrows, Science of Computer Programming (Elsevier) 37 (1-3): 67–111. (2000) (pdf)
Robert Harper, Of course ML Has Monads! (2011) (web)
Nick Benton, Categorical Monads and Computer Programming, (pdf)
Emily Riehl, A categorical view of computational effects, 2017 (pdf)
The specification of monads in Haskell is at
and an exposition of category theory and monads in terms of Haskell is in
A comparison of monads with applicative functors (also known as idioms) and with arrows (in computer science) is in
Generalization from monads to relative monads is discussed in
Discussion of comonads in this context includes
Discussion of aspects of quantum computing in terms of monads in functional programming are in
Thorsten Altenkirch, Alexander Green, The quantum IO monad, in Semantic Techniques in Quantum Computation, January 2009, appeared in 2010 (pdf, talk slides)
J. K. Vizzotto, Thorsten Altenkirch, A. Sabry, Structuring quantum effects: superoperators as arrows (arXiv:quant-ph/0501151)
Last revised on November 8, 2018 at 06:43:52. See the history of this page for a list of all contributions to it.