nLab Kleisli category

Idea

Given a monad $T$ on some category $\mathcal{C}$, then its Kleisli category is the full subcategory of the Eilenberg-Moore category of $T$, hence the category of T-algebras, on those that are free T-algebras (free $T$-modules).

Explicitly one may describe (Prop. below) the Kleisli category of $T$ (Def. ) to have as objects the objects of $\mathcal{C}$, and a morphism $X \to Y$ in the Kleisli category is a morphism in $\mathcal{C}$ of the form $X \to T(Y)$ in $\mathcal{C}$. The monad structure induces a natural composition of such “$T$-shifted” morphisms.

The Kleisli category is also characterized by the following universal property:

Since every adjunction gives rise to a monad on the domain of its left adjoint, we might ask if every monad may be construed as arising from an adjunction. This is in fact true, and the initial such adjunction in the category of adjunctions for the given monad has the Kleisli category as the codomain of its left adjoint.

Definition

Let $\mathbf{T} = (T,\mu,\eta)$ be a monad in Cat, where $T \colon \mathcal{C} \longrightarrow \mathcal{C}$ is an endofunctor with

• multiplication $\mu \colon T T \to T$,

• unit$\eta \colon Id_C \to T$.

In terms of free algebras

Definition

A free $\mathbf{T}$-algebra over a monad (or free $\mathbf{T}$-module) is a $\mathbf{T}$-algebra (module) of the form $(T(M),\mu_M)$, where the action is the component of multiplication transformation $\mu_M : T(T(M))\to T(M)$.

Definition

The Kleisli category $C_{\mathbf{T}}$ of the monad $\mathbf{T}$ is the full subcategory of the Eilenberg-Moore category $C^{\mathbf{T}}$ on the free $\mathbf{T}$-algebras (Def. ).

Remark

If $U:C^{\mathbf{T}}\to C$ is the forgetful functor and $F: C\to C^{\mathbf{T}}$ is the free algebra functor $F: M\mapsto (T M,\mu_M)$, then the Kleisli category is simply the full subcategory of $C^{\mathbf{T}}$ containing those objects in the image of $F$.

In terms of Kleisli morphisms

As another way of looking at this, we can keep the same objects as in $C$ but redefine the morphisms. This was the original Kleisli construction:

Definition

The Kleisli category $C_{\mathbf{T}}$ of a monad $T$ on a category $\mathcal{C}$ has:

1. as objects the objects of $\mathcal{C}$,

2. as morphisms $M \to N$ the morphisms of the form

   (1)$$M \longrightarrow{\;\;} T(N)$$

   in $\mathcal{C}$, called Kleisli morphisms;

and

• composition of $M \xrightarrow{f} T N$ with $N \xrightarrow{ g } T P$ is given by the Kleisli composition rule

  (2)$$g \circ_{Kleisli} f \;\coloneqq\; \mu_P \circ T(g) \circ f \;\colon\; M \overset{f}{\longrightarrow} T (N) \overset{T (g)}{\longrightarrow} T \big(T (P)\big) \overset{\mu_P}{\longrightarrow} T (P) \,;$$

• the identity morphisms on $M$ is the Kleisli morphism which is the $T$-unit $M \xrightarrow{ \eta_M } T M$.

Proposition

(Kleisli equivalence)
The construction which sends a Kleisli morphism $X \xrightarrow{f} T Y$ (1) to

$$T(X) \overset{T(f)}{\longrightarrow} T^2(Y) \overset{\mu_Y}{\longrightarrow} T(Y)$$

constitutes a full and faithful functor

$$\mathcal{C}_{T} \longrightarrow \mathcal{C}^{T}$$

from the $T$-Kleisli category (Def. ) to the category of $T$-algebras, hence constitutes an equivalence of categories onto its essential image which is that of free $T$-algebras.

Proof

Fullness holds because any morphism $g \colon T(X) \to T(Y)$ of algebras has

as antecedent the composite $X \stackrel{\eta_X}{\to} T(X) \stackrel{g}{\to} T(Y)$. Indeed, the latter is mapped by the functor into $\mu_Y \circ T(g) \circ T(\eta_X)$, which is seen to be equal to $g \circ \mu_X \circ T(\eta_X) \;=\;g$, using that $g$ is a homomorphism of algebras.

Faithfulness holds as follows: if $\mu_Y \circ T(f) = \mu_Y \circ T(g)$, then precomposing by $\eta_X$ yields $\mu_Y \circ T(f) \circ \eta_X = \mu_Y \circ \eta_{T(Y)} \circ f = f$ and similarly for $g$, hence $f = g$.

Remark

This Kleisli composition plays an important role in computer science; for this, see the article at monad (in computer science).

Properties

Universal properties

In more general 2-categories the universal properties of Kleisli objects are dual to the universal properties of Eilenberg-Moore objects.

In particular, $C_{\mathbf{T}}$ is initial in the category of adjunctions for $\mathbf{T}$ (whereas $C^{\mathbf{T}}$ is terminal). For a proof, see Category Theory in Context Proposition 5.2.12.

Examples

General

Example

In typed functional programming, the Kleisli category is used to model call-by-value? functions with side effects and computation. Dually, the co-Kleisli category of a comonad may be used to model call-by-name? programming , see there.

Generally, see at monad (in computer science) for more on this.

Specific

Example

(matrix multiplication as (co-)Kleisli composition)
See here.

Related concepts

• Kleisli triple

• co-Kleisli category

• Kleisli object

• extension system

• monad in computer science

• Kleisli 2-category

References

The original articles:

• Heinrich Kleisli, Every standard construction is induced by a pair of adjoint functors, Proc. Amer. Math. Soc. 16, AMS (1965) 544-546 [ISSN0002-9939, jstor:2034693]

• Jenö Szigeti, On limits and colimits in the Kleisli category, Cahiers de Topologie et Géométrie Différentielle Catégoriques 24 4 (1983) 381-391 [numdam:CTGDC_1983__24_4_381_0]

Early accounts (together with the Eilenberg-Moore category):

• Fred Linton, §7 in: An outline of functorial semantics, in Seminar on Triples and Categorical Homology Theory, Lecture Notes in Mathematics 80, Springer (1969) 7-52 [doi:10.1007/BFb0083080]

• Saunders MacLane, §VI.5 of: Categories for the Working Mathematician, Graduate Texts in Mathematics 5 Springer (1971) [doi:10.1007/978-1-4757-4721-8]

• Michael Barr, Charles Wells, §3.2 of: Toposes, Triples, and Theories, Grundlehren der math. Wissenschaften 278, Springer (1983) [TAC:12]

The equivalence of categories between the Kleisli category over a given monad with the co-Kleisli category of an adjoint comonad (if it exists):

• Mark Kleiner, Adjoint monads and an isomorphism of the Kleisli categories, Journal of Algebra

  Volume 133 1 (1990) 79-82 [doi:10.1016/0021-8693(90)90069-Z]

The terminology “Kleisli triple” for a monad presented as an “extension system” and relation to computation with effects (see at monads in computer science):

• Eugenio Moggi, Notions of computation and monads, Information and Computation, 93 1 (1991) [doi:10.1016/0890-5401(91)90052-4, pdf]

Discussion of cases where the inclusion of the Kleisli category into the Eilenberg-Moore category is a reflective subcategory:

• Marcelo Fiore, Matias Menni, Reflective Kleisli subcategories of the category of Eilenberg-Moore algebras for factorization monads, Theory and Applications of Categories, Vol. 15, CT2004, No. 2, pp 40-65. (TAC)

Discussion of combined “double” or “two-sided” Kleisli categories, combining the Kleisli category of a monad with the co-Kleisli category of a comonad that distributes over it:

• Stephen Brookes, Kathryn Van Stone, Monads and Comonads in Intensional Semantics (1993) [dtic:ADA266522, pdf]

and generalization to 2-monads:

• Richard Garner, pp. 11 of: Polycategories via pseudo-distributive laws, Advances in Mathematics 218 3 (2008) 781-827 [arXiv:0606735, doi:10.1016/j.aim.2008.02.001]

Discussion in internal category theory:

• Tomasz Brzeziński, Adrian Vazquez-Marquez, Internal Kleisli categories, Journal of Pure and Applied Algebra 215 9 (2011) 213-147 [arXiv:0911.4048]

Discussion in a context of categorical systems theory:

• David Jaz Myers, §2.3 of: Categorical systems theory, book project [github, pdf]

Discussion of Kleisli categories in type theory is in

• Alex Simpson, Recursive types in Kleisli Categories (pdf)