---
title: The Kleisli Category and Monads in Programming
module: Monads and Algebras
moduleNumber: 7
lessonNumber: 3
order: 703
summary: >
  The Kleisli category of a monad has the same objects as the base but takes
  arrows A to TB, composed by mapping and flattening. These arrows are
  effectful programs, Kleisli composition is the bind of functional
  programming, and the Kleisli adjunction is the initial resolution of the
  monad, with Eilenberg–Moore at the terminal end.
topics: [Monads and Algebras]
sources:
  - book: Barr & Wells
    ref: "§14.4.1 The Kleisli category for a triple; §14.4.4 The Kleisli category and free algebras"
  - book: Barr & Wells
    ref: "§2.2 Functional programming languages as categories"
draft: false
---

The [Eilenberg–Moore category](/category-theory/monads-algebras/algebras-eilenberg-moore)
resolves a monad into an adjunction by building the category of all its
algebras. Kleisli's construction, a decade older, resolves the same monad with
far less structure: keep the objects of the base category, and redefine what an
arrow is.[^bw-kleisli] The resulting category is the category of free algebras.
Read through computer science, it is the category of effectful programs, with the
monad's multiplication as the sequencing operation.

## The construction

> **Definition (Kleisli category).** Let $\mathbb{T} = (T, \eta, \mu)$ be a
> monad on $\mathcal{C}$. The **Kleisli category** $\mathcal{K}(\mathbb{T})$
> has:
>
> - the same objects as $\mathcal{C}$;
> - as arrows $A \to B$, the arrows $A \to TB$ of $\mathcal{C}$;
> - as identity on $A$, the unit $\eta_A : A \to TA$;
> - as composite of $f : A \to TB$ and $g : B \to TC$, the arrow
>
> $$
> g \bullet f \;=\; \mu_C \circ Tg \circ f
> \;:\; A \xrightarrow{\;f\;} TB \xrightarrow{\;Tg\;} T^2C \xrightarrow{\;\mu_C\;} TC.
> $$

To follow $f$ with $g$: run $f$, landing in $TB$; the next step $g$ expects a
bare $B$, so apply $T$ to it, giving $Tg : TB \to T^2C$; the result is doubly
wrapped, so flatten with $\mu_C$. Each piece of the monad has a role. $T$ lifts
the second program over the first one's effect, $\mu$ merges the two layers of
effect, and $\eta$ provides the do-nothing program.

$$
% caption: Kleisli composition of $f : A \to T B$ and $g : B \to T C$: lift $g$
% through $T$, then flatten the double layer with the multiplication $m$; the
% long arrow is the Kleisli composite $g \bullet f$.
\begin{tikzpicture}[>=stealth, font=\small,
  nd/.style={minimum size=8mm, inner sep=2pt}]
  \definecolor{acc}{HTML}{4A6FA5}
  \node[nd] (a)   at (0,0)    {$A$};
  \node[nd] (tb)  at (2.7,0)  {$T B$};
  \node[nd] (ttc) at (5.6,0)  {$T^2 C$};
  \node[nd] (tc)  at (8.4,0)  {$T C$};
  \draw[->, acc, thick] (a)   -- (tb)  node[midway, above] {$f$};
  \draw[->, acc, thick] (tb)  -- (ttc) node[midway, above] {$Tg$};
  \draw[->, acc, thick] (ttc) -- (tc)  node[midway, above] {$m_C$};
  \draw[->, black, thick] (a) to[bend right=28] node[midway, below] {composite} (tc);
\end{tikzpicture}
$$

The verification uses each monad law once. Associativity of $\bullet$ follows
from the associativity law of the monad plus naturality of $\mu$; the unit laws
of the monad make $\eta$ a two-sided identity.[^bw-assoc]

### The Kleisli adjunction

$\mathcal{K}(\mathbb{T})$ resolves the monad. Define

- $F : \mathcal{C} \to \mathcal{K}(\mathbb{T})$ by $FA = A$ and, for
  $g : A \to B$, $Fg = \eta_B \circ g$ (a pure program, run through the unit);
- $U : \mathcal{K}(\mathbb{T}) \to \mathcal{C}$ by $UA = TA$ and, for a Kleisli
  arrow $f : A \to TB$, $Uf = \mu_B \circ Tf : TA \to TB$.

Then $F \dashv U$, and $UF = T$ with the induced multiplication equal to
$\mu$.[^bw-kadj] The monad we started from is recovered, so every monad arises
from an adjunction by this construction alone — the Eilenberg–Moore route is a
second, independent proof of the same fact.

## Kleisli arrows as effectful programs

Barr & Wells model a functional programming language as a category: types are
objects, programs are arrows, and composition is running one program after
another.[^bw-lang] That model handles pure programs. A program with an
**effect** — one that may fail, log output, consult state, or return several
results — does not fit the shape $A \to B$; it fits $A \to TB$ for the monad $T$
encoding the effect. The Kleisli category is then the category whose arrows are
effectful programs, and Kleisli composition runs them in sequence.

| Monad | Kleisli arrow $A \to TB$ | Sequencing behavior of $\bullet$ |
| --- | --- | --- |
| maybe, $TB = B + 1$ | partial program, may fail | failure anywhere aborts the chain |
| list, $TB = B^\ast$ | nondeterministic program | run the next step on every result, concatenate |
| writer, $TB = M \times B$ | program with a log in a monoid $M$ | combine logs with the monoid operation |
| reader, $TB = B^E$ | program reading an environment $E$ | pass the same environment to both steps |
| state, $TB = (B \times S)^S$ | program threading state $S$ | feed the updated state to the next step |

> **Worked example (Kleisli composition on the list monad).** Take
> $A = \{1\}$, $B = \{x, y\}$, $C = \{p, q\}$ and the list monad. Let
> $f : A \to B^\ast$ and $g : B \to C^\ast$ be the Kleisli arrows
> $$
> f(1) = [x, y, x], \qquad g(x) = [p, q], \qquad g(y) = [\,].
> $$
> Compute $g \bullet f = \mu_C \circ Tg \circ f$ at $1$. Run $f$, then map $g$
> over the result, then flatten:
> $$
> f(1) = [x, y, x]
> \xrightarrow{\ Tg\ } \big[\,[p, q],\ [\,],\ [p, q]\,\big]
> \xrightarrow{\ \mu_C\ } [p, q, p, q].
> $$
> The empty result of $g(y)$ drops out under concatenation, and the two copies of
> $x$ each contribute $[p, q]$, so $(g \bullet f)(1) = [p, q, p, q]$: the next step
> is run on every result of the first, and the outputs are concatenated.

$$
% caption: Kleisli composition on the list monad at $1$: apply $g$ to each letter
% of $f(1) = [x, y, x]$ (the map step $T g$), then concatenate the resulting
% lists (the flatten step $m_C$). The empty list from $g(y)$ contributes nothing.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  bx/.style={draw, minimum height=7mm, inner sep=3pt}]
  \definecolor{acc}{HTML}{4A6FA5}
  \node[bx] (f)  at (0,0)   {[x,y,x]};
  \node[bx] (tg) at (4.3,0) {[[p,q],[ ],[p,q]]};
  \node[bx] (mu) at (9.2,0) {[p,q,p,q]};
  \draw[->, acc, thick] (f)  -- (tg) node[midway, above] {$Tg$};
  \draw[->, acc, thick] (tg) -- (mu) node[midway, above] {$m_C$};
\end{tikzpicture}
$$

For the maybe monad, take partial programs $f : A \to B + 1$ and
$g : B \to C + 1$. Then $Tg : B + 1 \to (C + 1) + 1$ sends the failure point to
the outer failure point, and $\mu_C$ merges the two failure points into one. The
composite $g \bullet f$ fails when either stage fails and returns $g(f(a))$
otherwise, the propagation a programmer would otherwise write by hand as a case
analysis.

> **Worked example (Kleisli composition on the maybe monad).** Take
> $A = \{1\}$, $B = \{x, y\}$, $C = \{p\}$, with $f(1) = \mathsf{just}(x)$,
> $g(x) = \mathsf{just}(p)$, and $g(y) = \mathsf{no}$. Then
> $$
> (g \bullet f)(1) = \mu_C\big(Tg(\mathsf{just}(x))\big)
> = \mu_C\big(\mathsf{just}(\mathsf{just}(p))\big) = \mathsf{just}(p).
> $$
> Rerouting the first stage to $f(1) = \mathsf{just}(y)$ instead gives
> $Tg(\mathsf{just}(y)) = \mathsf{just}(\mathsf{no})$, which $\mu_C$ collapses to
> $\mathsf{no}$: the failure of $g(y)$ propagates through the composite.

The same element-chase works for the state monad. Take
$TB = (B \times S)^S$ and Kleisli arrows $f : A \to (B \times S)^S$ and
$g : B \to (C \times S)^S$: each is a program that, given a start state,
returns a result and an end state. Starting from $a \in A$ and $s_0 \in S$:

- $f(a)(s_0) = (b, s_1)$: the first program runs, producing $b$ and an updated
  state $s_1$;
- $Tg(f(a))$ is the function $s \mapsto (g(b), s_1)$-shaped element of
  $T^2C$ — a stateful computation returning another stateful computation;
- $\mu_C$ runs the outer computation and feeds its end state to the inner one,
  giving $(g \bullet f)(a)(s_0) = g(b)(s_1)$.

The composite threads the state from left to right; the multiplication carries
the state-passing. Sequential, stateful execution order is part of $\mu$ for this
particular $T$, not a convention added to the notation.

### Bind

Functional languages present Kleisli composition through the operator **bind**,
written `>>=`. Bind takes an effectful value and a Kleisli arrow and applies the
arrow under the effect:

$$
\mathbin{>\!\!>\!=} \;:\; TA \times (A \to TB) \to TB,
\qquad
t \mathbin{>\!\!>\!=} f \;=\; \mu_B\big(Tf(t)\big).
$$

Bind and Kleisli composition are interdefinable:
$g \bullet f = \lambda a.\, f(a) \mathbin{>\!\!>\!=} g$, and conversely bind is
composition with a constant first program. In this notation the monad laws
become the three program equivalences

$$
\eta(a) \mathbin{>\!\!>\!=} f = f(a),
\qquad
t \mathbin{>\!\!>\!=} \eta = t,
\qquad
(t \mathbin{>\!\!>\!=} f) \mathbin{>\!\!>\!=} g
= t \mathbin{>\!\!>\!=} \big(\lambda a.\, f(a) \mathbin{>\!\!>\!=} g\big),
$$

which say that pure steps can be inlined and that sequencing is associative —
a block of effectful code means the same thing however it is parenthesized.
`do`-notation is the direct syntax for iterated bind: each line
$x \leftarrow f(\ldots)$ binds the result of a Kleisli arrow and passes it on,
and the desugaring is a right-nested chain of `>>=`. The associativity law is
what makes the flat, line-by-line reading legitimate.

$$
% caption: Bind glues an effectful value $t$ in $T A$ to a program $f : A \to
% T B$: map $f$ under the effect, then flatten. A do-block is a chain of these
% gluings.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  bx/.style={draw, minimum width=17mm, minimum height=8mm, align=center}]
  \definecolor{acc}{HTML}{4A6FA5}
  \node[bx] (t)  at (0,0)   {$t : T A$};
  \node[bx] (m)  at (3.4,0) {$T f(t) : T^2 B$};
  \node[bx, draw=acc, text=acc] (r) at (7.0,0) {$T B$};
  \draw[->, acc, thick] (t) -- (m) node[midway, above] {map $f$};
  \draw[->, acc, thick] (m) -- (r) node[midway, above] {merge};
  \node[bx] (l1) at (0,-1.9)   {line 1};
  \node[bx] (l2) at (3.4,-1.9) {line 2};
  \node[bx] (l3) at (7.0,-1.9) {line 3};
  \draw[->, black, thick] (l1) -- (l2) node[midway, above] {bind};
  \draw[->, black, thick] (l2) -- (l3) node[midway, above] {bind};
\end{tikzpicture}
$$

### Substitution and evaluation

Barr & Wells give a reading of Kleisli arrows that predates the effects
vocabulary: **substitution**.[^bw-subst] Take the list monad and a Kleisli arrow
$f : A \to B^\ast$ on alphabets $A = \{a, b\}$, $B = \{c, d, e\}$ with
$f(a) = cddc$ and $f(b) = ec$. Applying $Tf$ to the string $abba \in A^\ast$
substitutes a string for each letter:

$$
Tf(abba) = (cddc)(ec)(ec)(cddc) \in (B^\ast)^\ast,
$$

and $\mu$ concatenates the result to $cddcececcddc \in B^\ast$. The
multiplication carries out a computation: it evaluates a formal expression using
the algebra structure — here the monoid operation, since the algebras of the
list monad are monoids. For a monad built from ring-like structure the free
algebra consists of polynomial expressions and $\mu$ evaluates the polynomial.
Kleisli arrows are substitutions; $\mu$ is evaluation. This viewpoint, developed
through the notion of strong monad, is the root of the monads-as-computation
literature.[^bw-moggi]

## The Kleisli category as free algebras

The two resolutions of a monad are related concretely: the Kleisli category is
the full subcategory of the Eilenberg–Moore category on the **free** algebras.

> **Proposition.** $\mathcal{K}(\mathbb{T})$ is equivalent to the full
> subcategory of $\mathcal{C}^{\mathbb{T}}$ whose objects are the free algebras
> $(TA, \mu_A)$.[^bw-free]

The equivalence sends the Kleisli object $A$ to the free algebra on $A$; a
Kleisli arrow $A \to TB$ corresponds, by freeness, to a unique algebra morphism
$(TA, \mu_A) \to (TB, \mu_B)$. Under this identification $U$ becomes the
restriction of the Eilenberg–Moore forgetful functor.

### The resolution spectrum

Fix a monad $\mathbb{T}$ on $\mathcal{C}$ and consider all adjunctions
$F' \dashv G'$ inducing it. These form a category (arrows are functors between
the codomains commuting with both sides), and the two constructions of this
module are its endpoints:

- **Kleisli is initial.** For any inducing adjunction with codomain
  $\mathcal{B}$ there is a unique functor $\mathcal{K}(\mathbb{T}) \to \mathcal{B}$
  commuting with the adjunctions — it sends $A$ to $F'A$, and exists because
  every Kleisli object is free.
- **Eilenberg–Moore is terminal.** The
  [comparison functor](/category-theory/monads-algebras/algebras-eilenberg-moore)
  $\mathcal{B} \to \mathcal{C}^{\mathbb{T}}$ is the unique functor the other
  way.

$$
% caption: Every adjunction resolving the monad sits between the Kleisli
% category (initial: free algebras only) and the Eilenberg–Moore category
% (terminal: all algebras); each double edge to the base $\mathcal{C}$ (drawn
% $\mathbf{C}$) is an adjunction inducing the same monad.
\begin{tikzpicture}[>=stealth, font=\small,
  bx/.style={draw, minimum width=25mm, minimum height=10mm, align=center}]
  \definecolor{acc}{HTML}{4A6FA5}
  \node[bx] (k)  at (0,2.4)   {Kleisli\\(free algebras)};
  \node[bx] (b)  at (4.6,2.4) {$\mathbf{B}$\\(any resolution)};
  \node[bx] (em) at (9.2,2.4) {EM category\\(all algebras)};
  \node[bx] (c)  at (4.6,0)   {$\mathbf{C}$};
  \draw[->, acc, thick] (k) -- (b)  node[midway, above] {unique};
  \draw[->, acc, thick] (b) -- (em) node[midway, above] {comparison};
  \draw[<->, black, thick] (k)  -- (c) node[midway, below left] {adjoint};
  \draw[<->, black, thick] (b)  -- (c) node[midway, right] {adjoint};
  \draw[<->, black, thick] (em) -- (c) node[midway, below right] {adjoint};
\end{tikzpicture}
$$

Any category of "things the monad acts on" therefore contains the free algebras
and embeds in the full category of algebras. For the list monad the spectrum
runs from the category of free monoids to the category of all monoids, with
every variety of monoid-like structure inducing the same monad falling in
between.

## Two factorizations, two disciplines

The contrast between the endpoints organizes how the two fields use monads.

| | Kleisli | Eilenberg–Moore |
| --- | --- | --- |
| objects | those of $\mathcal{C}$ | all $\mathbb{T}$-algebras |
| arrows | $A \to TB$ | structure-preserving maps |
| position among resolutions | initial | terminal |
| algebras represented | free ones only | all |
| natural reading | programs, substitutions | algebraic structures |
| home discipline | computer science | mathematics |

Mathematics centers on the whole category of algebras (monadicity, transfer of
limits, algebraic theories), so Eilenberg–Moore dominates. Computer science
centers on sequencing effectful computations over base types, which never leaves
the free algebras, so Kleisli dominates.[^bw-culture] Both categories induce the
monad exactly.

Dropping the unit and multiplication and keeping only the endofunctor gives the
theory of
[algebras for an endofunctor](/category-theory/monads-algebras/algebras-for-endofunctors),
where initiality replaces freeness and inductive datatypes appear as least
fixed points.

[^bw-kleisli]: **Barr & Wells**, _Category Theory for Computing Science_, §14.4.1 — the Kleisli category $\mathcal{K}(\mathbb{T})$: same objects, arrows $A \to TB$, composite $\mu C \circ Tg \circ f$, identity $\eta A$; "due to Kleisli [1965], has proven to be quite useful in theoretical computer science."
[^bw-assoc]: **Barr & Wells**, §14.4.5 Exercises 1–2 — $\eta A$ is the Kleisli identity and Kleisli composition is associative.
[^bw-kadj]: **Barr & Wells**, §14.4.1 — the functors $U A = TA$, $Uf = \mu B \circ Tf$ and $FA = A$, $Fg = Tg \circ \eta A$ with $F \dashv U$ and $T = UF$.
[^bw-lang]: **Barr & Wells**, §2.2.4 — a functional programming language has a category structure: types as objects, operations as arrows, composition as the composition constructor.
[^bw-subst]: **Barr & Wells**, §14.4.4 — the list-triple example $f(a) = cddc$, $f(b) = ec$: $Tf$ substitutes and $\mu$ concatenates, "it is instructive in this situation to think of $\mu$ as carrying out a computation."
[^bw-moggi]: **Barr & Wells**, §14.4.4 — the strong-monad development of monads-as-computation, citing Kock, Moggi, Wadler, and others.
[^bw-free]: **Barr & Wells**, §14.4.4 — "The Kleisli category of a triple is equivalent to the full subcategory of free $\mathbb{T}$-algebras."
[^bw-culture]: **Barr & Wells**, §14.4.2 — the Eilenberg–Moore construction has been the more interesting one in mathematics, the Kleisli construction in computer science.