16-MonadsAdjunctions.tex

\documentclass[DaoFP]{subfiles}
\begin{document}
\setcounter{chapter}{15}

\chapter{Monads and Adjunctions}

\section{String Diagrams}

A line partitions a plane. We can think of it as either dividing a plane or as connecting two halves of the plane.

A dot partitions a line. We can think of it as either separating two half-lines or as joining them together.

This is a diagram in which two categories are represented as dots, two functors as arrows, and a natural transformation as a double arrow.

\[
\begin{tikzpicture}[column sep=huge]
\def \xa{-1.2};
\def \xb{0};
\def \xc{1.2};
\def \ya{-1};
\def \yb{0};
\def \yc{1};

\node(c) at (\xa, \yb) {};
\node[left] at (c) {$\mathcal{C}$};
\filldraw[black] (c) circle (1 pt);
\node(d) at (\xc, \yb) {};
\node[right] at (d) {$\mathcal{D}$};
\filldraw[black] (d) circle (1 pt);

\draw [->] (c) to [out=60,in=120] node[midway, above]{$G$}(d);
\draw [->] (c) to [out=-60,in=-120] node[midway, below]{$F$}(d);

\node(mup) at (\xb, \yc -0.5) {};
\node(mdn) at (\xb, \ya + 0.5) {};
\draw[->, -{Implies}, double, double distance=2pt] (mdn) -- node[midway, left]{$\alpha$} (mup);
\end{tikzpicture}
\]

But the same idea can be represented by drawing categories as areas of a plane, functors as lines between areas, and natural transformations as dots that join line segments. 

The idea is that a functor always goes between a pair of categories, therefore it can be drawn as a boundary between them. A natural transformation always goes between a pair of functors, therefore it can be drawn as a dot joining two segments of a line.

\[
\begin{tikzpicture}
\def\x{0};
\def\xl{-1.5};
\def\xr{1.5};


\def \ya{0.8};
\def \yb{1.7};
\def \yc{2.6};
\def \yt {2.3};

\filldraw[fill=blue!50!green!20, draw=white] (\xl, \ya) rectangle (\x, \yc);
\filldraw[fill=orange!30, draw=white] (\x, \ya) rectangle (\xr, \yc);

\node[below] (a) at (\x, \ya) {$F$};
\node(b) at (\x, \yb) {};
\node [above] (c) at (\x, \yc) {$G$};

\node(l)[right] at (\xl, \yt) {$\mathcal{C}$};
\node(r)[left] at (\xr, \yt) {$\mathcal{D}$};


\filldraw[black] (b) circle (1 pt);
\node [left] at (b) {$\alpha$};

\draw (a)  -- (c);

\end{tikzpicture}
\]

This is an example of a \emph{string diagram}. You read such a digram bottom-up, left-to-right (think of the $(x, y)$ system of coordinates). 

The bottom of this diagram shows the functor $F$ that goes from $\mathcal{C}$ to $\mathcal{D}$. The top of the diagram shows the functor $G$ that goes between the same two categories. The transition happens in the middle, where a natural transformation $\alpha$ maps $F$ to $G$.

In Haskell, this diagram is interpreted as a polymorphic function between two endofunctors:
\begin{haskell}
alpha :: forall x. F x -> G x
\end{haskell}

So far it doesn't seem like we gain a lot by using this new visual representation. But let's apply it to something more interesting: vertical composition of natural transformations:
\[
\begin{tikzcd}[column sep=huge]
\mathcal{C}
  \arrow[bend left=60]{rr}[name=U, label=above:$H$]{}
  \arrow[]{rr}[name=M, label={[xshift=15pt, yshift=-5pt]:$G$}]{} 
  \arrow[bend right=60]{rr}[name=D, label=below:$F$]{} 
 &&
\mathcal{D}
  \arrow[shorten <=8pt, shorten >=8pt,Leftarrow, to path={(U) -- node[label=left:$\beta$] {} (M)}]{}
  \arrow[shorten <=8pt, shorten >=8pt,Leftarrow, to path={(M) -- node[label=left:$\alpha$] {} (D)}]{}
\end{tikzcd}
\]

The corresponding string diagram shows the two categories and three functors between them joined by two natural transformations.
\[
\begin{tikzpicture}
\def\x{0};
\def\xl{-1.5};
\def\xr{1.5};


\def \ya{0};
\def \yb{0.8};
\def \ybb{2.2};
\def \yc{3};
\def \yt {2.7};
\def \ymid {1.5}

\filldraw[fill=blue!50!green!20, draw=white] (\xl, \ya) rectangle (\x, \yc);
\filldraw[fill=orange!30, draw=white] (\x, \ya) rectangle (\xr, \yc);

\node[below] (a) at (\x, \ya) {$F$};
\node(b) at (\x, \yb) {};
\node(bb) at (\x, \ybb) {};
\node [above] (c) at (\x, \yc) {$H$};
\node(m)[right] at (\x, \ymid) {$G$};

\node(l)[right] at (\xl, \yt) {$\mathcal{C}$};
\node(r)[left] at (\xr, \yt) {$\mathcal{D}$};

\filldraw[black] (b) circle (1 pt);
\node [left] at (b) {$\alpha$};
\filldraw[black] (bb) circle (1 pt);
\node [left] at (bb) {$\beta$};

\draw (a)  -- (c);

\end{tikzpicture}
\]
As you can see, you can reconstruct the original diagram from the string diagram by scanning it bottom-to-top.

Again, in Haskell we'll be dealing with three endofunctors, and the vertical composition of \hask{beta} after \hask{alpha}:
\begin{haskell}
alpha :: forall x. F x -> G x
beta  :: forall x. G x -> H x
\end{haskell}
 is implemented using regular function composition:
\begin{haskell}
beta_alpha :: forall x. F x -> H x
beta_alpha = beta . alpha
\end{haskell}

Let's continue with the horizontal composition of natural transformations:
\[
\begin{tikzcd}[column sep=huge]
\mathcal{C}
  \arrow[bend left=50]{r}[name=U, label=above:$F'$]{}
  \arrow[bend right=50]{r}[name=D, label=below:$F$]{} 
 &
\mathcal{D}
  \arrow[bend left=50]{r}[name=U1, label=above:$G'$]{}
  \arrow[bend right=50]{r}[name=D1, label=below:$G$]{} 
 &
\mathcal{E}
  \arrow[shorten <=10pt,shorten >=10pt,Leftarrow,to path={(U) -- node[label=left:$\alpha$] {} (D)}]{}
  \arrow[shorten <=10pt,shorten >=10pt,Leftarrow,to path={(U1) -- node[label=left:$\beta$] {} (D1)}]{}
\end{tikzcd}
\]
This time we have three categories, so we'll have three areas. 

The bottom of the string diagram corresponds to the composition of functors $G \circ F$ (in this order). The top corresponds to $G' \circ F'$. One natural transformation, $\alpha$, connects $F$ to $F'$; the other, $\beta$, connects $G$ to $G'$.
\[
\begin{tikzpicture}
\def\xl{-2.75};
\def\xa{-1};
\def\xc{0}
\def\xb{1};
\def\xr{2.75};


\def \ya{0};
\def \yb{1};
\def \yc{2};
\def \yt {1.7};

\filldraw[fill=blue!50!green!20, draw=white] (\xl, \ya) rectangle (\xa, \yc);
\filldraw[fill=black!10!white, draw=white] (\xa, \ya) rectangle (\xb, \yc);
\filldraw[fill=orange!30, draw=white] (\xb, \ya) rectangle (\xr, \yc);

\node[below] (a) at (\xa, \ya) {$F$};
\node(b) at (\xa, \yb) {};
\node [above] (c) at (\xa, \yc) {$F'$};

\node[below] (d) at (\xb, \ya) {$G$};
\node(e) at (\xb, \yb) {};
\node [above] (f) at (\xb, \yc) {$G'$};

\node(l)[right] at (\xl, \yt) {$\mathcal{C}$};
\node(r) at (\xc, \yt) {$\mathcal{D}$};
\node(r)[left] at (\xr, \yt) {$\mathcal{E}$};


\filldraw[black] (b) circle (1 pt);
\node [left] at (b) {$\alpha$};
\filldraw[black] (e) circle (1 pt);
\node [left] at (e) {$\beta$};

\draw (a)  -- (c);
\draw (d)  -- (f);

\end{tikzpicture}
\]
Parallel vertical lines in this new system correspond to functor composition. 

You may think of the horizontal composition of natural transformations as happening along the imaginary horizontal line in the middle of the diagram. But what if somebody was sloppy in drawing the diagram, and one of the dots was a little higher than the other? As it turns out, the exact positioning of the dots doesn't matter, due to the interchange law.

But first, let's illustrate whiskering: horizontal composition in which one of the natural transformation is the identity. We can draw it like this:

\[
\begin{tikzpicture}
\def\xl{-2.75};
\def\xa{-1};
\def\xc{0}
\def\xb{1};
\def\xr{2.75};


\def \ya{0};
\def \yb{1};
\def \yc{2};
\def \yt {1.7};

\filldraw[fill=blue!50!green!20, draw=white] (\xl, \ya) rectangle (\xa, \yc);
\filldraw[fill=black!10!white, draw=white] (\xa, \ya) rectangle (\xb, \yc);
\filldraw[fill=orange!30, draw=white] (\xb, \ya) rectangle (\xr, \yc);

\node[below] (a) at (\xa, \ya) {$F$};
\node(b) at (\xa, \yb) {};
\node [above] (c) at (\xa, \yc) {$F$};

\node[below] (d) at (\xb, \ya) {$G$};
\node(e) at (\xb, \yb) {};
\node [above] (f) at (\xb, \yc) {$G'$};

\node(l)[right] at (\xl, \yt) {$\mathcal{C}$};
\node(r) at (\xc, \yt) {$\mathcal{D}$};
\node(r)[left] at (\xr, \yt) {$\mathcal{E}$};


\filldraw[black] (b) circle (1 pt);
\node [left] at (b) {$id_F$};
\filldraw[black] (e) circle (1 pt);
\node [left] at (e) {$\beta$};

\draw (a)  -- (c);
\draw (d)  -- (f);

\end{tikzpicture}
\]
But, really, the identity can be inserted at any point on a vertical line, so we don't even have to draw it. The following diagram represents the whiskering of $\beta \circ F$.
\[
\begin{tikzpicture}
\def\xl{-2.75};
\def\xa{-1};
\def\xc{0}
\def\xb{1};
\def\xr{2.75};


\def \ya{0};
\def \yb{1};
\def \yc{2};
\def \yt {1.7};

\filldraw[fill=blue!50!green!20, draw=white] (\xl, \ya) rectangle (\xa, \yc);
\filldraw[fill=black!10!white, draw=white] (\xa, \ya) rectangle (\xb, \yc);
\filldraw[fill=orange!30, draw=white] (\xb, \ya) rectangle (\xr, \yc);

\node[below] (a) at (\xa, \ya) {$F$};
\node(b) at (\xa, \yb) {};
\node [above] (c) at (\xa, \yc) {$F$};

\node[below] (d) at (\xb, \ya) {$G$};
\node(e) at (\xb, \yb) {};
\node [above] (f) at (\xb, \yc) {$G'$};

\node(l)[right] at (\xl, \yt) {$\mathcal{C}$};
\node(r) at (\xc, \yt) {$\mathcal{D}$};
\node(r)[left] at (\xr, \yt) {$\mathcal{E}$};

\filldraw[black] (e) circle (1 pt);
\node [left] at (e) {$\beta$};

\draw (a)  -- (c);
\draw (d)  -- (f);

\end{tikzpicture}
\]

In Haskell, where \hask{beta} is a polymorphic function:
\begin{haskell}
beta :: forall x. G x -> G' x
\end{haskell}
 we read this diagram as:
\begin{haskell}
beta_f :: forall x. G (F x) -> G' (F x)
beta_f = beta
\end{haskell}
with the understanding that the type checker instantiates the polymorphic function \hask{beta} for the correct type.

Similarly, you can easily imagine the diagram for $G \circ \alpha$, and its Haskell realization:
\begin{haskell}
g_alpha :: forall x. G (F x) -> G (F' x)
beta_f = fmap alpha
\end{haskell}
with:
\begin{haskell}
alpha :: forall x. F x -> F' x
\end{haskell}

Here's the string diagram that corresponds to the interchange law:
\[
\begin{tikzpicture}
\def\xl{-2.75};
\def\xa{-1};
\def\xc{0}
\def\xb{1};
\def\xr{2.75};


\def \ya{0.2};
\def \yb{1};
\def \ybb{2}
\def \yc{2.8};
\def \yt {\yc -0.3};
\def \ymid {1.5}

\filldraw[fill=blue!50!green!20, draw=white] (\xl, \ya) rectangle (\xa, \yc);
\filldraw[fill=black!10!white, draw=white] (\xa, \ya) rectangle (\xb, \yc);
\filldraw[fill=orange!30, draw=white] (\xb, \ya) rectangle (\xr, \yc);

\node[below] (a) at (\xa, \ya) {$F$};
\node(b) at (\xa, \yb) {};
\node [above] (c) at (\xa, \yc) {$F''$};
\node [right] (ml) at (\xa, \ymid) {$F'$};

\node[below] (d) at (\xb, \ya) {$G$};
\node(e) at (\xb, \yb) {};
\node [above] (f) at (\xb, \yc) {$G''$};
\node [right] (ml) at (\xb, \ymid) {$G'$};

\node(l)[right] at (\xl, \yt) {$\mathcal{C}$};
\node(r) at (\xc, \yt) {$\mathcal{D}$};
\node(r)[left] at (\xr, \yt) {$\mathcal{E}$};


\filldraw[black] (b) circle (1 pt);
\node [left] at (b) {$\alpha$};
\filldraw[black] (e) circle (1 pt);
\node [left] at (e) {$\beta$};

\node(bb) at (\xa, \ybb) {};
\node(ee) at (\xb, \ybb) {};

\filldraw[black] (bb) circle (1 pt);
\node [left] at (bb) {$\alpha'$};
\filldraw[black] (ee) circle (1 pt);
\node [left] at (ee) {$\beta'$};

\draw (a)  -- (c);
\draw (d)  -- (f);

\end{tikzpicture}
\]
This diagram is purposefully ambiguous. Are we supposed to first do vertical composition of natural transformations and then the horizontal one? Or should we compose $\beta \circ \alpha$ and $\beta' \circ \alpha'$ horizontally, and then compose the results vertically? The interchange law says that it doesn't matter: the result is the same. 

Now try to replace a pair of natural transformations in this diagram with identities. If you replace $\alpha'$ and $\beta'$, you get the horizontal composition of $\beta \circ \alpha$. If you replace $\alpha'$ and $\beta$ with identity natural transformations, and rename $\beta'$ to $\beta$, you get the diagram in which $\alpha$ is shifted down with respect to $\beta$, and so on. 

\[
\begin{tikzpicture}
\def\xl{-2.75};
\def\xa{-1};
\def\xc{0}
\def\xb{1};
\def\xr{2.75};


\def \ya{0.2};
\def \yb{1};
\def \ybb{2}
\def \yc{2.8};
\def \yt {\yc -0.3};
\def \ymid {1.5}

\filldraw[fill=blue!50!green!20, draw=white] (\xl, \ya) rectangle (\xa, \yc);
\filldraw[fill=black!10!white, draw=white] (\xa, \ya) rectangle (\xb, \yc);
\filldraw[fill=orange!30, draw=white] (\xb, \ya) rectangle (\xr, \yc);

\node[below] (a) at (\xa, \ya) {$F$};
\node(b) at (\xa, \yb) {};
\node [above] (c) at (\xa, \yc) {$F'$};

\node[below] (d) at (\xb, \ya) {$G$};
\node(e) at (\xb, \yb) {};
\node [above] (f) at (\xb, \yc) {$G'$};

\node(l)[right] at (\xl, \yt) {$\mathcal{C}$};
\node(r) at (\xc, \yt) {$\mathcal{D}$};
\node(r)[left] at (\xr, \yt) {$\mathcal{E}$};


\filldraw[black] (b) circle (1 pt);
\node [left] at (b) {$\alpha$};

\node(bb) at (\xa, \ybb) {};
\node(ee) at (\xb, \ybb) {};

\filldraw[black] (ee) circle (1 pt);
\node [left] at (ee) {$\beta$};

\draw (a)  -- (c);
\draw (d)  -- (f);

\end{tikzpicture}
\]
The interchange law tells us that all these diagrams are equal. We are free to slide natural transformations like beads on a string.

\subsection{String diagrams for the monad}

A monad is defined as an endofunctor equipped with two natural transformations, as illustrated by the following diagrams:
 
\[
\begin{tikzcd}[column sep=huge]
\mathcal{C}
  \arrow[bend left=50]{r}[name=U, label=above:$T$]{}
  \arrow[bend right=50]{r}[name=D, label=below:$\text{Id}$]{} 
 &
\mathcal{C}
  \arrow[shorten <=10pt,shorten >=10pt,Leftarrow,to path={(U) -- node[label=left:$\eta$] {} (D)}]{}
\end{tikzcd}
\hspace{20pt}
\begin{tikzcd}[column sep=huge]
\mathcal{C}
  \arrow[bend left=50]{r}[name=U, label=above:$T$]{}
  \arrow[bend right=50]{r}[name=D, label=below:$T \circ T$]{} 
 &
\mathcal{C}
  \arrow[shorten <=10pt,shorten >=10pt,Leftarrow,to path={(U) -- node[label=left:$\mu$] {} (D)}]{}
\end{tikzcd}
\]

Since we are dealing with just one category, when translating these diagrams to string diagrams, we can dispose of the naming (and the shading) of categories, and just draw the strings alone.
\[
\begin{tikzpicture}

\def \xleft{-2}

\def\xa{0};
\def\xb{0.7};
\def\xc{\xb * 2};

\def \ya{0};
\def \yb{1};
\def \yc{2};

\node(a) at (\xleft, \ya) {};
\node(b) at (\xleft, \yb) {}; % middle
\node(c) at (\xleft, \yc) {};

\draw[dashed] (a) -- node[right] {$\text{Id}$} (b);
\draw (b) -- node[right] {$T$} (c);


\node(d) at (\xa, \ya) {};
\node(e) at (\xc, \ya) {};
\node(f) at (\xb, \yb) {}; % middle
\node(g) at (\xb, \yc) {}; % top


\filldraw[black] (b) circle (1 pt);
\node [left] at (b) {$\eta$};

\draw (d) to [out=90, in=180]  node[left] {$T$}(f);
\draw (e) to [out=90, in=0]  node[right] {$T$} (f);

\draw (f) -- node[right] {$T$} (g);

\filldraw[black] (f) circle (1 pt);
\node [below] at (f) {$\mu$};

\end{tikzpicture}
\]
In the first diagram it's customary to skip the dashed line corresponding to the identity functor. The $\eta$ dot can be used to freely inject a $T$ line into a diagram. Two $T$ lines can be joined by the $\mu$ dot. 

String diagrams are especially useful in expressing monad laws. For instance, we have the left identity law:
\[ \mu \circ (\eta \circ T) = id \]
which can be visualized as a commuting diagram:
\[
 \begin{tikzcd}
 \text{Id} \circ T
 \arrow[rr, "\eta \circ T"]
 \arrow[rrd, "id"']
& & T \circ T
 \arrow[d, "\mu"]
 \\
 && T
  \end{tikzcd}
\]
The corresponding string diagrams represents the equality of the two paths through this diagram:
\[
\begin{tikzpicture}
\def\xa{0};
\def\xb{0.7};
\def\xc{\xb * 2};

\def \ya{0.8};
\def \yb{1.7};
\def \yc{2.6};

\node(a) at (\xa, \ya) {};
\node(b) at (\xb, \yb) {};
\node(c) at (\xc, 0) {};
\node(d) at (\xb, \yc) {};
\filldraw[black] (a) circle (1 pt);
\node [below] at (a) {$\eta$};
\filldraw[black] (b) circle (1 pt);
\node [below] at (b) {$\mu$};
\draw (a) to [out=90, in=180]  node[left] {$T$}(b);
\draw (c) to [out=90, in=0]  node[right] {$T$} (b);
\draw (b) -- node[right] {$T$} (d);

\def\xd{3.5}
\def\xe{2.5}
\node(e) at (\xd, 0) {};
\node(f) at (\xd, \yc) {};
\node at (\xe, 1.5) {$=$};
\draw (e) -- node[right] {$T$} (f);
\end{tikzpicture}
\]
You may think of this equality as the result of yanking the top and bottom strings resulting in the $\eta$ appendage being retracted into the straight line.

There is a symmetric right identity law:
\[
\begin{tikzpicture}
\def\xa{0};
\def\xb{0.7};
\def\xc{\xb * 2};

\def \ya{0.8};
\def \yb{1.7};
\def \yc{2.6};

\node(a) at (\xa, 0) {};
\node(b) at (\xb, \yb) {};
\node(c) at (\xc, \ya) {};
\node(d) at (\xb, \yc) {};
\filldraw[black] (b) circle (1 pt);
\node [below] at (c) {$\eta$};
\filldraw[black] (c) circle (1 pt);
\node [below] at (b) {$\mu$};
\draw (a) to [out=90, in=180]  node[left] {$T$}(b);
\draw (c) to [out=90, in=0]  node[right] {$T$} (b);
\draw (b) -- node[right] {$T$} (d);

\def\xd{3.5}
\def\xe{2.5}
\node(e) at (\xd, 0) {};
\node(f) at (\xd, \yc) {};
\node at (\xe, 1.5) {$=$};
\draw (e) -- node[right] {$T$} (f);
\end{tikzpicture}
\]

Finally, this is the associativity law in terms of string diagrams:
\[
\begin{tikzpicture}
\def\delta{0.7}
\def\xa{0};
\def\xb{\delta};
\def\xc{\delta * 2};
\def\xd{\delta * 3};

\def \ya{0.8};
\def \yb{1.7};
\def \yc{2.6};

\node(a) at (\xa, 0) {};
\node(b) at (\xb, \yb) {};
\node(c) at (\xc, \ya) {};
\node(d) at (\xb, \yc) {};
\node(e) at (\xb, 0) {};
\node(f) at (\xd, 0) {};
\filldraw[black] (b) circle (1 pt);
\filldraw[black] (c) circle (1 pt);
\node [below] at (b) {$\mu$};
\draw (a) to [out=90, in=180]  node[left] {}(b);
\draw (c) to [out=90, in=0]  node[right] {} (b);
\draw (b) -- node[right] {} (d);
\draw (e) to [out=90, in=180]  node[left] {}(c);
\draw (f) to [out=90, in=0]  node[right] {}(c);
\node [below] at (c) {$\mu$};
\node [below] at (a) {$T$};
\node [above] at (d) {$T$};
\node [below] at (e) {$T$};
\node [below] at (f) {$T$};

\def\xe{2.5}
\node at (\xe, 1.5) {$=$};

\def\off{3}
\def\xa{\off + \delta * 0};
\def\xb{\off + \delta * 1};
\def\xc{\off + \delta * 2};
\def\xd{\off + \delta * 3};

\node(a) at (\xa, 0) {};
\node(b) at (\xc, 0) {};
\node(c) at (\xd, 0) {};
\node(d) at (\xb, \ya) {};
\node(e) at (\xc, \yb) {};
\node(f) at (\xc, \yc) {};
\filldraw[black] (d) circle (1 pt);
\filldraw[black] (e) circle (1 pt);
\node [below] at (d) {$\mu$};
\draw (a) to [out=90, in=180]  node[left] {}(d);
\draw (b) to [out=90, in=0]  node[right] {} (d);
\draw (e) -- node[right] {} (f);
\draw (d) to [out=90, in=180]  node[left] {}(e);
\draw (c) to [out=90, in=0]  node[right] {}(e);
\node [below] at (e) {$\mu$};
\node [below] at (a) {$T$};
\node [below] at (b) {$T$};
\node [below] at (c) {$T$};
\node [above] at (f) {$T$};
\end{tikzpicture}
\]

\subsection{String diagrams for the adjunction}

As we discussed before, an adjunction is a relation between a pair of functors, $L \colon \mathcal{D} \to \mathcal{C}$ and $R \colon \mathcal{C} \to \mathcal{D}$. It can be defined by a pair of natural transformations, the unit $\eta$ and the counit $\varepsilon$, satisfying triangular identities.

The unit of the adjunction can be illustrated by a ``cup''-shaped diagram:

\[
\begin{tikzpicture}

\def \xrightmost {2}
\def \xright         {1}
\def \xmid          {0}
\def \xleft           {-\xright}
\def \xleftmost   {-\xrightmost}

\def \ybot           {0}
\def \ymid          {1}
\def \ytop           {2}
\def \ylabel        {\ytop - 0.3}

% functor labels
\node [above] at (\xleft, \ytop)   {$L$};
\node [above] at (\xright, \ytop) {$R$};
% background
\filldraw[fill=orange!30, draw=white] (\xleftmost, \ytop) rectangle (\xrightmost, \ybot);
% cup
\draw [fill=blue!50!green!20] (\xleft, \ytop) to [out=-90, in=180] (\xmid, \ymid) to [out=0, in=-90] (\xright, \ytop);
% natural transformation
\filldraw [black] (\xmid, \ymid) circle (1 pt);
\node [below] at (\xmid, \ymid) {$\eta$};
% category labels
\node           at (\xmid, \ylabel)        {$\mathcal{C}$};
\node [right] at (\xleftmost, \ylabel) {$\mathcal{D}$};

\end{tikzpicture}
\]
The identity functor at the bottom of the diagram is omitted from the picture. The $\eta$ dot turns the identity functor below it to the composition $R \circ L$ above it.

Similarly, the counit can be visualized as a ``cap''-shaped string diagram with the implicit identity functor at the top:

\[
\begin{tikzpicture}
\def\xleft{0};
\def\xmid{1};
\def\xright{\xmid * 2};

\def \ybot{0};
\def \ymid{1};
\def \ytop{2 * \ymid};
\def \yt{2 * \ymid - 0.3};

\node [below] (a) at (\xleft, \ybot) {$R$};
\node(b) at (\xmid, \ymid) {};
\node[below] (c) at (\xright, \ybot) {$L$};

\filldraw[fill=blue!50!green!20, draw=white] (\xleft-1, \ytop) rectangle (\xright+1, \ybot);


\draw [fill=orange!30] (a.north) to [out=90, in=180] (b.west) -- (b.east) to [out=0, in=90] (c.north);

\filldraw[black] (b) circle (1 pt);
\node [above] at (b) {$\varepsilon$};

\node(l)[right] at (\xleft-1, \yt) {$\mathcal{C}$};
\node(r) at (\xmid, \ybot + 0.3) {$\mathcal{D}$};

\end{tikzpicture}
\]

Triangle identities can be easily expressed using string diagrams. They also make intuitive sense, as you can imagine pulling on the string from both sides to straighten the curve.

For instance, this is the first triangle identity, sometimes called the \index{zigzag identity}\emph{zigzag} identity: 

\[
\begin{tikzpicture}
\def \dx {0.7}
\def \dy {0.7}

\def \xa{-3 * \dx};
\def \xb{-2 * \dx};
\def \xc{-1 * \dx};
\def \xd{0};
\def \xe{1 * \dx};
\def \xf{2 * \dx};
\def \xg{3 * \dx};

\def \ya{0};
\def \yb{1 * \dy};
\def \yc{2 * \dy};
\def \yd{3 * \dy};
\def \ye{4 * \dy};

\node [below] at (\xb, \ya) {$R$};
\node [right] at (\xd, \yc) {$L$};
\node [above] at (\xf, \ye) {$R$};
% background
\filldraw[fill=blue!50!green!20, draw=white] (\xa, \ye) rectangle (\xg, \ya);
% fill shape
\path [fill=orange!30] (\xa, \ya) to (\xb, \ya) to (\xb, \yc) to [out=90, in=180]  (\xc, \yd) to  [out=0, in=90] (\xd, \yc) to [out=-90, in=180] (\xe, \yb) to [out=0, in=-90] (\xf, \yc) to (\xf, \ye) to (\xa, \ye);

\draw (\xb, \ya) to (\xb, \yc) to [out=90, in=180]  (\xc, \yd) to  [out=0, in=90] (\xd, \yc) to [out=-90, in=180] (\xe, \yb) to [out=0, in=-90] (\xf, \yc) to (\xf, \ye);

\filldraw[black] (\xc, \yd) circle (1 pt);
\node [above] at (\xc, \yd) {$\varepsilon$};

\filldraw[black] (\xe, \yb) circle (1 pt);
\node [below] at (\xe, \yb) {$\eta$};

\node[right] at (\xa, \ye - 0.3) {$\mathcal{C}$};
\node[left] at (\xg, \ya + 0.3) {$\mathcal{D}$};

% right diagram

\node (eq) at (4 * \dy, \yc) {$=$};
\def \xh {6.3 * \dx}

\filldraw[fill=orange!30, draw=white] (\xh - 1, \ye) rectangle (\xh, \ya);
\filldraw[fill=blue!50!green!20, draw=white] (\xh, \ye) rectangle (\xh + 1, \ya);

\draw (\xh, \ye) -- (\xh, \ya);

\node[below] (bb) at (\xh, \ya) { $R$ };
\node[above] (bt) at (\xh, \ye) { $R$ };

\node(l)[right] at (\xh - 1, \ye - 0.3) {$\mathcal{C}$};
\node(r)[left] at (\xh + 1, \ya + 0.3) {$\mathcal{D}$};

\end{tikzpicture}
\]
Reading the left diagram bottom-to-top produces a series of mappings:

\[  Id_{\mathcal{D}} \circ R \xrightarrow{\eta \circ R} R \circ L \circ R \xrightarrow{R \circ \varepsilon} R \circ Id_{\mathcal{C}}  \]
This must be equal to the right-hand-side, which may be interpreted as the (invisible) identity natural transformation on $R$

In the case $R$ is an endofunctor, we can translate the first diagram directly to Haskell. The whiskering of the unit of the adjunction $\eta$ by $R$ results in the polymorphic function \hask{unit} being instantiated at \hask{R x}. The whiskering of $\varepsilon$ results in the lifting of \hask{counit} by the functor $R$. The vertical composition translates to function composition:
\begin{haskell}
triangle :: forall x. R x -> R x
triangle = fmap counit . unit
\end{haskell}

\begin{exercise}
Draw the string diagrams for the second triangle identity and translate them to Haskell.
\end{exercise}

\section{Monads from Adjunctions}

You might have noticed that the same symbol $\eta$ is used for the unit of the adjunction and for the unit of the monad. This is \emph{not} a coincidence. 

At first sight it might seem like we are comparing apples to oranges: an adjunction is defined with two functors between two categories and a monad is defined by one endofunctor operating on a single category. However, the composition of two functors going in opposite directions is an endofunctor, and the unit of the adjunction maps the identity endofunctor to the endofunctor $R \circ L$. 

Compare this diagram:
\[
\begin{tikzpicture}
\def\xleft{0.5};
\def\xmid{1};
\def\xright{1.5};

\def \ybot{0};
\def \ymid{1};
\def \ytop{2 * \ymid};
\def \yt{2 * \ymid - 0.3};

\node [above] (a) at (\xleft, \ytop) {$L$};
\node(b) [below] at (\xmid, \ymid) {};
\node[above] (c) at (\xright, \ytop) {$R$};

\filldraw[fill=orange!30, draw=white] (\xleft-1, \ytop) rectangle (\xright+1, \ybot);


\draw [fill=blue!50!green!20] (a.south) to [out=-90, in=180] (b.west) -- (b.east) to [out=0, in=-90] (c.south);
\filldraw[black] (b) circle (1 pt);
\node [below] at (b) {$\eta$};

\node(l)[right] at (\xleft-1, \yt) {$\mathcal{D}$};
\node(r) at (\xmid, \yt) {$\mathcal{C}$};

\end{tikzpicture}
\]
with the one defining the monadic unit:

\[
\begin{tikzpicture}
\def\xleft{0.5};
\def\xmid{1};
\def\xright{1.5};

\def \ybot{0};
\def \ymid{1};
\def \ytop{2 * \ymid};
\def \yt{2 * \ymid - 0.3};

\node(b) [above] at (\xmid, \ytop) {$T$};

\filldraw[fill=orange!30, draw=white] (\xleft-1, \ytop) rectangle (\xright+1, \ybot);

\draw (\xmid, \ymid) -- (\xmid, \ytop);

\filldraw[black] (\xmid, \ymid) circle (1 pt);
\node [below] at (\xmid, \ymid) {$\eta$};

\node(l)[right] at (\xleft-1, \yt) {$\mathcal{D}$};

\end{tikzpicture}
\]

It turns out that, for any adjunction $L \dashv R$, the endofunctor $T = R \circ L$ is a monad, with the multiplication $\mu$ defined by the following diagram:

\[
\begin{tikzpicture}
\def \xmid          {0};
\def \xr               {0.5};
\def \xrr             {1}
\def \xrm            {0.25}
\def \xrightmost {1.5}
\def \xl {-\xr}
\def \xll {-\xrr}
\def \xlm {-\xrm}
\def \xleftmost {-\xrightmost}

\def \ybot           {0};
\def \ymidbot     {0.20};
\def \yeps          {0.7};
\def \ymid          {1};
\def \ymidtop     {1.60}
\def \ytop           {2};
\def \ylabel        {\ytop - 0.3};
% functors
\node [above] at (\xlm, \ytop)  {$L$};
\node [above] at (\xrm, \ytop) {$R$};
\node [below] at (\xll, \ybot) {$L$};
\node [below] at (\xl, \ybot) {$R$};
\node [below] at (\xr, \ybot) {$L$};
\node [below] at (\xrr, \ybot) {$R$};

\filldraw[fill=blue!50!green!20, draw=white, draw=white] (\xleftmost, \ytop) rectangle (\xrightmost, \ybot);

% left area
\path [fill=orange!30] (\xleftmost, \ybot) to  (\xll, \ybot) to (\xll, \ymidbot) [out=90, in=-90] to (\xlm, \ymidtop) to  (\xlm, \ytop) to [out=180, in=180] (\xleftmost, \ytop);
% right area
\path [fill=orange!30] (\xrightmost, \ybot) to (\xrr, \ybot) to (\xrr, \ymidbot) [out=90, in=-90] to (\xrm, \ymidtop) to (\xrm, \ytop) to [out=0, in=180]  (\xrightmost, \ytop);
% cap
\draw [fill=orange!30] (\xl, \ybot) to [out=90, in=180] (\xmid, \yeps) to [out=0, in=90] (\xr, \ybot);
% left curve
\draw (\xll, \ybot) to (\xll, \ymidbot) [out=90, in=-90] to (\xlm, \ymidtop) to  (\xlm, \ytop);
% right curve
\draw (\xrr, \ybot) to (\xrr, \ymidbot) [out=90, in=-90] to (\xrm, \ymidtop) to (\xrm, \ytop);
% epsilon
\filldraw [black] (\xmid, \yeps) circle (1 pt);
\node [below] at (\xmid, \yeps) {$\varepsilon$};
% categories
\node [right] at (\xleftmost, \ylabel) {$\mathcal{D}$};
\node           at (\xmid, \ylabel)        {$\mathcal{C}$};
\node [left]   at (\xrightmost, \ylabel) {$\mathcal{D}$};

\end{tikzpicture}
\]
Reading this diagram bottom-to-top, we get the following transformation (imagine slicing it horizontally at the dot):
\[  R \circ L \circ R \circ L \xrightarrow{R \circ \varepsilon \circ L} R \circ L  \]
Compare this with the definition of the monadic $\mu$:

\[
\begin{tikzpicture}
\def \xmid          {0};
\def \xr               {0.5};
\def \xrightmost {1.5};
\def \xl {-\xr};
\def \xleftmost {-\xrightmost};

\def \ybot           {0};
\def \ymid          {1};
\def \ytop           {2};
\def \ylabel        {\ytop - 0.3};

\node [above] at (\xmid, \ytop) {$T$};
\node [below] at (\xl, \ybot)      {$T$};
\node [below] at (\xr, \ybot)      {$T$};

\filldraw[fill=orange!30, draw=white] (\xleftmost, \ytop) rectangle (\xrightmost, \ybot);
% cap
\draw (\xl, \ybot) to [out=90, in=180] (\xmid, \ymid) to [out=0, in=90] (\xr, \ybot);
\draw (\xmid, \ymid) to (\xmid, \ytop);

\filldraw [black] (\xmid, \ymid) circle (1 pt);
\node [below] at (\xmid, \ymid) {$\mu$};

\node [right] at (\xleftmost, \ylabel) {$\mathcal{D}$};

\end{tikzpicture}
\]
We get the definition of $\mu$ for the monad $R \circ L$ as the double-whiskering of $\varepsilon$:
\[ \mu = R \circ \varepsilon \circ L \]

The Haskell translation of the string diagram defining $\mu$ in terms of $\varepsilon$ is always possible. The monadic multiplication, or \hask{join}, becomes:
\begin{haskell}
join :: forall x. T (T x) -> T x
join = fmap counit
\end{haskell}
where \hask{fmap} corresponds to the lifting by the endofunctor \hask{T} defined as the composition $R \circ L$. Notice that $\cat D$ in this case is the Haskell category of types and functions, but $\cat C$ can be an outside category.

To complete the picture, we can use string diagrams to derive monadic laws using triangle identities. The trick is to replace all strings in monadic laws by pairs of parallel strings and then rearrange them according to the rules.

To summarize, every adjunction $L \dashv R$ with the unit $\eta$ and counit $\varepsilon$ defines a monad $(R \circ L, \eta, R \circ \varepsilon \circ L)$.

We'll see later that, dually, the other composition, $L \circ R$ defines a comonad.

\begin{exercise}
Draw string diagrams to illustrate monadic laws (unit and associativity) for the monad derived from an adjunction.
\end{exercise}

\section{Examples of Monads from Adjunctions}

We'll go through several examples of adjunctions that generate some of the monads that we use in programming. We'll expand on these examples later, when we talk about monad transformers.

Most examples involve functors that leave the category of Haskell types and functions, even though the round trip that generates the monad ends up being an endofunctor. This is why it's often impossible to express such adjunctions in Haskell. 

To additionally complicate things, there is a lot of bookkeeping related to explicit naming of data constructors, which is necessary for type inference to work. This may sometimes obscure the simplicity on the underlying formulas.

\subsection{Free monoid and the list monad}
The list monad is generated by the free monoid adjunction we've seen before. The unit of this adjunction, $\eta_X \colon X \to U (F X)$, injects the elements of the set $X$ as the generators of the free monoid $F X$, after which $U$ extracts the underlying set. 

In Haskell, we represent the free monoid as a list type, and its generators are singleton lists. The unit $\eta_X$ maps elements of $X$ to such singletons:
\begin{haskell}
return x = [x]
\end{haskell}
To implement the counit, $\varepsilon_M \colon F (U M) \to M$, we take a monoid $M$, forget its multiplication, and use its set of elements as generators for a new free monoid. A component of the counit at $M$ is then a monoid morphism from the free monoid back to $M$ or, in Haskell, \hask{[m]->m}. It turns out that this monoid morphism is a special case of a catamorphism. 

First, recall the Haskell implementation of a general list catamorphism:
\begin{haskell}
foldMap :: Monoid m => (a -> m) -> ([a] -> m)
foldMap f = foldr mappend mempty . fmap f
\end{haskell}
Here, we interpret \hask{(a -> m)} as a regular function from \hask{a} to the underlying set of a monoid \hask{m}. The result is interpreted as a \emph{monoid morphism} from the free monoid generated by \hask{a} (that is a list of \hask{a}'s) to \hask{m}. This is just one direction of the adjunction:
\[ \Set (a, U m) \cong \Cat{Mon} (F a, m) \]

To get the counit as a monoid morphism \hask{[m]->m} we apply \hask{foldMap} to identity. The result is \hask{(foldMap id)} or, in terms of \hask{foldr}:
\begin{haskell}
epsilon = foldr mappend mempty
\end{haskell}
It is a monoid morphism since it maps an empty list to the monoidal unit, and concatenation to monoidal product.

Monadic multiplication, or \hask{join}, is given by the whiskering of the counit:
\[ \mu = U \circ \varepsilon \circ F \]
You can easily convince yourself that whiskering on the left doesn't do much here, since it's just a lifting of a monoid morphism by the forgetful functor (it keeps the function while forgetting its special property of preserving structure). 

The right whiskering by $F$ is more interesting. It means that the component $\mu_X$ corresponds to the component of $\varepsilon$ at $F X$, which is the free monoid generated from the set $X$. This  free monoid is defined by:
\begin{haskell}
mempty = []
mappend = (++)
\end{haskell}
which gives us the definition of \hask{join}:
\begin{haskell}
join = foldr (++) []
\end{haskell}
As expected, this is the same as \hask{concat}: In the list monad, multiplication is concatenation.

\subsection{The currying adjunction and the state monad}

The state monad is generated by the currying adjunction that we used to define the exponential object. The left functor is defined by a product with some fixed object $s$:
\[ L_s a = a \times s \]
We can, for instance, implement it as a Haskell type:
\begin{haskell}
newtype L s a = L (a, s)
\end{haskell}
The right functor is the exponentiation, parameterized by the same object $s$:
\[ R_s c = c^s \]
In Haskell, it's a thinly encapsulated function type:
\begin{haskell}
newtype R s c = R (s -> c)
\end{haskell}

The monad is given by the composition of these two functors. On objects:
\[(R_s \circ L_s) a = (a \times s)^s \]
In Haskell we would write it as:
\begin{haskell}
newtype St s a = St (R s (L s a))
\end{haskell}
If you expand this definition, it's easy to recognize in it the \hask{State} functor:
\begin{haskell}
newtype State s a = State (s -> (a, s))
\end{haskell}

The unit of the adjunction $L_s \dashv R_s$ is a mapping:
\[ \eta_a \colon a \to (a \times s)^s \]
which can be implemented in Haskell as:
\begin{haskell}
unit :: a -> R s (L s a)
unit a = R (\s -> L (a, s))
\end{haskell}
You may recognized in it a thinly veiled version of \hask{return} for the state monad:
\begin{haskell}
return :: a -> State s a
return a = State (\s -> (a, s))
\end{haskell}

Here's the component of the counit of this adjunction at $c$:
\[ \varepsilon_c \colon c^s \times s \to c \]
It can be implemented in Haskell as:
\begin{haskell}
counit :: L s (R s a) -> a
counit (L ((R f), s))= f s
\end{haskell}
which, after stripping data constructors, is equivalent to \hask{apply}, or the uncurried version of \hask{runState}.

Monad multiplication $\mu$ is given by the whiskering of $\varepsilon$ from both sides:
\[ \mu = R_s \circ \varepsilon \circ L_s \]
Here it is translated to Haskell:
\begin{haskell}
mu :: R s (L s (R s (L s a))) -> R s (L s a)
mu = fmap counit
\end{haskell}
Whiskering on the right doesn't do anything other than select a component of the natural transformation. This is done automatically by Haskell's type inference engine. Whiskering on the left is done by lifting the component of the natural transformation. Again, type inference picks the correct implementation of \hask{fmap}---here, it's equivalent to precomposition.

Compare this with the implementation of \hask{join}:
\begin{haskell}
join :: State s (State s a) -> State s a
join mma = State (fmap (uncurry runState) (runState mma))
\end{haskell}
Notice the dual use of \hask{runState}: 
\begin{haskell}
runState :: State s a -> s -> (a, s)
runState (State h) s = h s
\end{haskell}
When it's uncurried, its type signature becomes:
\begin{haskell}
uncurry runState :: (State s a, s) -> (a, s)
\end{haskell}
which is equivalent to that of \hask{counit}. 

When partially applied, \hask{runState} just strips the data constructor exposing the underlying function type:
\begin{haskell}
runState st :: s -> (a, s)
\end{haskell}



\subsection{M-sets and the writer monad}

The writer monad:
\begin{haskell}
newtype Writer m a = Writer (a, m)
\end{haskell}
is parameterized by a monoid \hask{m}. This monoid is used for accumulating log entries. The adjunction we are going to use involves a category of M-sets for that monoid. 

An \index{M-set}M-set is a set $S$ on which we define the action of a monoid $M$. Such an action is a mapping:
\[a \colon M \times S \to S \]
We often use the curried version of the action, with the monoid element in the subscript position. Thus $a_m$ becomes a function $S \to S$. 

This mapping has to satisfy some constraints. The action of the monoidal unit $1$ must not change the set, so it has to be the identity function:
\[ a_1 = id_S \]
and two consecutive actions must combine to an action of their monoidal product:
\[ a_{m_1} \circ a_{m_2} = a_{m_1 \cdot m_2} \]
This choice of the order of multiplication defines what it called the \emph{left action}. (The right action has the two monoidal elements swapped on the right-hand side.)

M-sets form a category $\mathbf{MSet}$. The objects are pairs $(S, a\colon M\times S \to S)$ and the arrows are  \index{equivariant map}\emph{equivariant maps}, that is  functions between sets that preserve actions. 

A function $f \colon S \to R$ is an \emph{equivariant} mapping from $(S, a)$ to $(R, b)$ if the following diagram commutes, for every $m \in M$:

\[
 \begin{tikzcd}
 S 
 \arrow[r, "f"]
 \arrow[d, "a_m"]
 & R
\arrow[d, "b_m"]
 \\
S
 \arrow[r, "f"]
 & R
  \end{tikzcd}
\]
In other words, it doesn't matter if we first do the action $a_m$, and then map the set; or first map the set, and then do the corresponding action $b_m$.

There is a forgetful functor $U$ from $\mathbf{MSet}$ to $\mathbf{Set}$, which assigns the set $S$ to the pair $(S, a)$, thus forgetting the action.  

Corresponding to it there is a free functor $F$. Its action on a set $S$ produces an M-set. It's a set that is a cartesian product of $S$ and $M$, where $M$ is treated as a set of elements (in other words, the result of the action of a forgetful functor on a monoid). An element of this M-set is a pair $(x \in S, m \in M)$ and the free action is defined by:
\[ \phi_n \colon (x, m) \mapsto (x, n \cdot m) \]
leaving the element $x$ unchanged, and only multiplying the $m$-component.

To show that $F$ is left adjoint to $U$ we have to construct the following natural isomorphism:
\[ \mathbf{MSet}( F S, Q) \cong \mathbf{Set}(S, U Q) \]
for any set $S$ and any M-set $Q$. If we represent $Q$ as a pair $(R, b)$, the element of the right hand side of the adjunction is a plain function $u \colon S \to R$. We can use this function to construct an equivariant mapping on the left.

The trick here is to notice that such  an equivariant mapping $f \colon F S \to Q$ is fully determined by its action on the elements of the form $(x, 1) \in F S$, where $1$ is the monoidal unit. 

Indeed, from the equivariance condition it follows that:
\[
 \begin{tikzcd}
 (x, 1)
 \arrow[r, mapsto, "f"]
 \arrow[d, mapsto, "\phi_m"]
 & r
\arrow[d, mapsto, "b_m"]
 \\
(x, m \cdot 1)
 \arrow[r, mapsto, "f"]
 & r'
  \end{tikzcd}
\]
or:
\[ f( \phi_m (x, 1)) = f (x, m) = b_m ( f (x, 1)) \]
Thus every function $u \colon S \to R$ uniquely defines an equivariant mapping $f \colon F S \to Q$ given by:
\[ f (x, m) = b_m (u x) \]

The unit of this adjunction $\eta_S \colon S \to U (F S)$ maps an element $x$ to a pair $(x, 1)$. Compare this with the definition of \hask{return} for the writer monad:
\begin{haskell}
return a = Writer (a, mempty)
\end{haskell}

The counit is given by an equivariant map:
\[ \varepsilon_Q \colon F (U Q) \to Q \]

The left hand side is the M-set constructed by taking the underlying set of $Q$ and taking its product with the underlying set of $M$. The original action of $Q$ is forgotten and replaced by the free action. The obvious choice for the counit is:
\[ \varepsilon_Q \colon (x, m) \mapsto a_m x \]
where $x$ is an element of (the underlying set of) $Q$ and $a$ is the action defined in $Q$.

Monad multiplication $\mu$ is given by the whiskering of the counit.
\[ \mu = U \circ \varepsilon \circ F \]
It means replacing $Q$ in the definition of $\varepsilon_Q$ with a free M-set whose action is the free action. In other words, we replace $x$ with $(x, m)$ and $a_n$ with $\phi_n$. (Whiskering with $U$ doesn't change anything.)
\[ \mu_S \colon ((x, m), n) \mapsto \phi_n (x, m) = (x, n \cdot m) \]
Compare this with the definition of \hask{join} for the writer monad:
\begin{haskell}
join :: Monoid m => Writer m (Writer m a) -> Writer m a
join (Writer ( Writer (x, m), n)) = Writer (x, mappend n m)
\end{haskell}

\subsection{Pointed objects and the \hask{Maybe} monad}

Pointed objects are objects with a designated element. Since picking an element is done using an arrow from the terminal object, the category of pointed objects is defined using pairs $(a, p \colon 1 \to a)$, where $a$ is an object in $\mathcal{C}$. 

The morphisms between these pairs are the arrows in $\mathcal{C}$ that preserve the points. Thus a morphism from $(a, p \colon 1 \to a)$ to $(b, q \colon 1 \to b)$ is an arrow $f \colon a \to b$ such that $q = f \circ p$. This category is also called a \index{coslice}\emph{coslice category} and is written as $1/\mathcal{C}$.

There is an obvious forgetful functor $U \colon 1/\mathcal{C} \to \mathcal{C}$ that forgets the point. Its left adjoint is a free functor $F$ that maps an object $a$ to a pair $(1 + a, \text{Left})$. In other words, $F$ freely ads a point to an object using a coporoduct. 

The \hask{Either} monad is similarly constructed by replacing $1$ with a fixed object $e$.

\begin{exercise}
Show that $U \circ F$ is the \hask{Maybe} monad.
\end{exercise}

\subsection{The continuation monad}

The continuation monad is defined in terms of a pair of contravariant functors in the category of sets. We don't have to modify the definition of the adjunction to work with contravariant functors. It's enough to select the opposite category for one of the endpoints. 

We'll define the left functor as:
\[ L_Z \colon \mathbf{Set}^{op} \to \mathbf{Set} \] 
It maps a set $X$ to the hom-set in $\mathbf{Set}$:
\[ L_Z X = \mathbf{Set}(X, Z) \] 
This functor is parameterized by another set $Z$. The right functor is defined by essentially the same formula:
\[ R_Z \colon \mathbf{Set} \to \mathbf{Set}^{op} \] 
\[ R_Z X = \mathbf{Set^{op}}(Z, X)  = \mathbf{Set}(X, Z) \] 


The composition $R \circ L$ can be written in Haskell as \hask{((x -> r) -> r)}, which is the same as the (covariant) endofunctor that defines the continuation monad.

\section{Monad Transformers}

Suppose that you want to combine multiple effects, say, state with the possibility of failure. One option is to define your own monad from scratch. You define a functor:
\begin{haskell}
newtype MaybeState s a = MS (s -> Maybe (a, s))
  deriving Functor
\end{haskell}
together with the function to extract the result (or report failure):
\begin{haskell}
runMaybeState :: MaybeState s a -> s -> Maybe (a, s)
runMaybeState (MS h) s = h s
\end{haskell}
You define the monad instance for it:
\begin{haskell}
instance Monad (MaybeState s) where
  return a = MS (\s -> Just (a, s))
  ms >>= k = MS (\s -> case runMaybeState ms s of
                       Nothing -> Nothing
                       Just (a, s') -> runMaybeState (k a) s')
\end{haskell}
and, if you are diligent enough, check that it satisfies the monad laws.

There is no general recipe for combining monads. In that sense, monads are not composable. However, we know that adjunctions are composable. We've also seen how to get monads from adjunctions and, as we'll soon see, every monad can be obtained this way. So, if we can match adjunctions, the monads that they generate will automatically compose.

Consider two composable adjunctions:
\[
 \begin{tikzcd}
  \mathcal{C}
  \arrow[rr, bend right, "R'"']
  &&
  \mathcal{D}
  \arrow[ll, bend right, "L'"']
    \arrow[rr, bend right, "R"']
&&
  \mathcal{E}
  \arrow[ll, bend right, "L"']
 \end{tikzcd}
\]
There are three monads in this picture. There is the ``inner'' monad $R' \circ L'$ and the ``outer'' monad $R \circ L$ as well as the composite $R \circ R' \circ L' \circ L$. 

If we call the inner monad $T = R' \circ L'$, then $R \circ T \circ L$ is the composite monad called the \emph{monad transformer}, because it transforms the monad $T$ into a new monad. 

\[
 \begin{tikzcd}
   &&
  \mathcal{D}
  \arrow[loop, "T = R' \circ L'"']
    \arrow[rr, bend right, "R"']
&&
  \mathcal{E}
  \arrow[ll, bend right, "L"']
 \end{tikzcd}
\]


In our example, we can treat \hask{Maybe} as the inner monad:
\[ T a = 1 + a \]
It is transformed using the outer adjunction $L_s \dashv R_s$, the one that generates the state monad:
\[ L_s a = a \times s \]
\[ R_s c = c^s \]
The result is:
\[ (R_s \circ T \circ L_s) a = (1 + a \times s)^s\]
or, in Haskell:
\begin{haskell}
s -> Maybe (a, s)
\end{haskell}
which matches the definition of our \hask{MaybeState} monad.

In general, the inner monad $T$ is defined by its unit $\eta^i$ and multiplication $\mu^i$ (the superscript $i$ standing for ``inner''). The ``outer'' adjunction is defined by its unit $\eta^o$ and counit $\varepsilon^o$. 

The unit of the composite monad is the natural transformation:
\[ \eta \colon Id \to R \circ T \circ L \]
given by the string diagram:
\[
\begin{tikzpicture}
\def\xright{0.7};
\def\xleft{-\xright};
\def\xmid{0};

\def \ybot{0};
\def \ymid{0.8};
\def \yup{1.7};
\def \ytop{2.5};

\node [above] at (\xleft, \ytop) {$L$};
\node [above] at (\xmid, \ytop) {$T$};
\node [above] at (\xright, \ytop) {$R$};

\filldraw[fill=orange!30, draw=white] (\xleft-1, \ytop) rectangle (\xright+1, \ybot);

\draw [fill=blue!50!green!20] (\xleft, \ytop) to [out=-90, in=180] (\xmid, \ymid) to [out=0, in=-90] (\xright, \ytop);

\filldraw[black] (\xmid, \ymid) circle (1 pt);
\node [below] at (\xmid, \ymid) {$\eta^o$};
\filldraw[black] (\xmid, \yup) circle (1 pt);
\node [below] at (\xmid, \yup) {$\eta^i$};
\draw (\xmid, \yup) -- (\xmid,\ytop);

\end{tikzpicture}
\]
It is the vertical composition of the whiskered inner unit $R \circ \eta^i \circ L$ and the outer unit $\eta^o$. In components:
\[ \eta_a = R(\eta^i_{L a}) \circ \eta^o_a\]

The multiplication of the composite monad is a natural transformation:
\[ \mu \colon R \circ T \circ L \circ R \circ T \circ L \to R \circ T \circ L \]
given by the string diagram:

\[
\begin{tikzpicture}
\def \xmid          {0};
\def \xr               {0.3};
\def \xrt             {0.9};
\def \xrr             {1.5}
\def \xrm            {0.6}
\def \xrightmost {2}
\def \xl {-\xr}
\def \xlt {-\xrt}
\def \xll {-\xrr}
\def \xlm {-\xrm}
\def \xleftmost {-\xrightmost}

\def \ybot           {0};
\def \ymidbot     {0.2};
\def \yeps          {0.8};
\def \ymu           {1.5}; % mu
\def \ymid          {1.9};
\def \ymidtop     {2.6}
\def \ytop           {2.7};
\def \ylabel        {\ytop - 0.3};
% functors
\node [above] at (\xlm, \ytop)  {$L$};
\node [above] at (\xmid, \ytop)  {$T$};
\node [above] at (\xrm, \ytop) {$R$};

\node [below] at (\xll, \ybot) {$L$};
\node [below] at (\xlt, \ybot) {$T$};
\node [below] at (\xl, \ybot) {$R$};
\node [below] at (\xr, \ybot) {$L$};
\node [below] at (\xrt, \ybot) {$T$};
\node [below] at (\xrr, \ybot) {$R$};

\filldraw[fill=blue!50!green!20, draw=white, draw=white] (\xleftmost, \ytop) rectangle (\xrightmost, \ybot);

% left area
\path [fill=orange!30] (\xleftmost, \ybot) to  (\xll, \ybot) to (\xll, \ymidbot) [out=90, in=-90] to (\xlm, \ymidtop) to  (\xlm, \ytop) to [out=180, in=180] (\xleftmost, \ytop);
% right area
\path [fill=orange!30] (\xrightmost, \ybot) to (\xrr, \ybot) to (\xrr, \ymidbot) [out=90, in=-90] to (\xrm, \ymidtop) to (\xrm, \ytop) to [out=0, in=180]  (\xrightmost, \ytop);
% cap
\draw [fill=orange!30] (\xl, \ybot) to [out=90, in=180] (\xmid, \yeps) to [out=0, in=90] (\xr, \ybot);
% fork
\draw (\xlt, \ybot) to [out=90, in=180] (\xmid, \ymu) to [out=0, in=90] (\xrt, \ybot);

% left curve
\draw (\xll, \ybot) to (\xll, \ymidbot) [out=90, in=-90] to (\xlm, \ymidtop) to  (\xlm, \ytop);
% right curve
\draw (\xrr, \ybot) to (\xrr, \ymidbot) [out=90, in=-90] to (\xrm, \ymidtop) to (\xrm, \ytop);
% epsilon
\filldraw [black] (\xmid, \yeps) circle (1 pt);
\node [below] at (\xmid, \yeps) {$\varepsilon^o$};

% mu
\filldraw [black] (\xmid, \ymu) circle (1 pt);
\node [below] at (\xmid, \ymu) {$\mu^i$};
\draw (\xmid, \ymu) -- (\xmid, \ytop);

\end{tikzpicture}
\]
It's the vertical composition of the multiply whiskered outer counit:
\[ R \circ T \circ \varepsilon^o \circ T \circ L \]
followed by the whiskered inner multiplication $R \circ \mu^i \circ L$. In components:
\[ \mu_c = R(\mu^i_{L c}) \circ (R \circ T) (\varepsilon^o_{(T\circ L)c})\]

\subsection{State monad transformer}

Let's unpack these equations for the case of the state monad transformer. The state monad is generated by the currying adjunction. The left functor $L_s$ is the product functor \hask{(a, s)}, and the right functor $R_s$ is the exponential, a.k.a., the reader functor \hask{(s -> a)}. 

As we've seen before, the outer counit $\varepsilon^o_a$ is function application:
\begin{haskell}
counit :: (s -> a, s) -> a
counit (f, x) = f x
\end{haskell}
and the unit $\eta^o_a$ is the curried pair constructor:
\begin{haskell}
unit :: a -> s -> (a, s)
unit x = \s -> (x, s)
\end{haskell}


We'll keep the inner monad $(T, \eta^i, \mu^i)$ arbitrary. In Haskell, we'll call this triple \hask{m}, \hask{return}, and \hask{join}.

The composite monad that we get by applying the state monad transformer to the monad $T$, is the composition $R \circ T \circ L$ or, in Haskell:
\begin{haskell}
newtype StateT s m a = StateT (s -> m (a, s))
\end{haskell}

\begin{haskell}
runStateT :: StateT s m a -> s -> m (a, s)
runStateT (StateT h) s = h s
\end{haskell}

The unit of the monad transformer is the vertical composition of $\eta^o$ and $R \circ \eta^i \circ L$. In components:
\[ \eta_a = R(\eta^i_{L a}) \circ \eta^o_a \]

There are a lot of moving parts in this formula, so let's analyze it step-by-step. We start from the right: we have the $a$-component of the unit of the adjunction, which is an arrow from $a$ to $R (L a)$. In Haskell, it's the function \hask{unit}. 
\begin{haskell}
unit :: a -> s -> (a, s)
\end{haskell}
Let's evaluate this function at some \hask{x :: a}. The result is another function \hask{s -> (a, s)}. We pass this function as an argument to $R(\eta^i_{L a})$. 

$\eta^i_{L a}$ is the component of \hask{return} of the inner monad taken at $L a$. Here, $L a$ is the type \hask{(a, s)}. So we are instantiating the polymorphic function \hask{return :: a -> m a} as a function \hask{(a, s) -> m (a, s)}. (The type inferencer will do this automatically for us.)

Next, we are lifting this component of \hask{return} using $R$. Here, $R$ is the exponential $(-)^s$, so it lifts a function by post-composition. It will post-compose \hask{return} to whatever function is passed to it. In our case, that's the function that was produced by \hask{unit}. Notice that the types match: we are post-composing \hask{(a, s) -> m (a, s)} after \hask{s -> (a, s)}. 

We can write the result of this composition as:
\begin{haskell}
return x = StateT (return . \s -> (x, s))
\end{haskell}
or, inlining function composition:
\begin{haskell}
return x = StateT (\s -> return (x, s))
\end{haskell}
We inserted the data constructor \hask{StateT} to make the type checker happy. This is the \hask{return} of the composite monad in terms of the \hask{return} of the inner monad.

The same reasoning can be applied to the formula for the component of the composite $\mu$ at some $a$: 

\[ \mu_a = R(\mu^i_{L a}) \circ (R \circ T) (\varepsilon^o_{(T\circ L) a})\]
The inner $\mu^i$ is the \hask{join} of the monad \hask{m}. Applying $R$ turns it into post-composition. 

The outer $\varepsilon^o$ is function application taken at $T(L a)$ or \hask{m (a, s)}. It's a function of the type:
\begin{haskell}
(s -> m (a, s), s) -> m (a, s)
\end{haskell}
which, inserting the appropriate data constructors, can be written as \hask{uncurry runStateT}:
\begin{haskell}
uncurry runStateT :: (StateT s m a, s) -> m (a, s)
\end{haskell}
The application of $(R \circ T)$ lifts this component of $\varepsilon$ using the composition of functors $R$ and $T$. The former is implemented as  post-composition, and the latter is the \hask{fmap} of the monad \hask{m}. 

Putting all this together, we get a point-free formula for \hask{join} of the state monad transformer:
\begin{haskell}
join :: StateT s m (StateT s m a) -> StateT s m a
join mma = StateT (join . fmap (uncurry runStateT) . runStateT mma)
\end{haskell}
Here, the partially applied \hask{(runStateT mma)} strips off the data constructor from the argument \hask{mma}:
\begin{haskell}
runStateT mma :: s -> m (a, x)
\end{haskell}

Our earlier example of \hask{MaybeState} can now be rewritten using a monad transformer:
\begin{haskell}
type MaybeState s a = StateT s Maybe a
\end{haskell}

The vanilla \hask{State} monad can be recovered by applying the \hask{StateT} monad transformer to the identity functor, which has a \hask{Monad} instance defined in the library (notice that the last type variable \hask{a} is skipped in this definition):
\begin{haskell}
type State s = StateT s Identity
\end{haskell}

Other monad transformers follow the same pattern. They are defined in the Monad Transformer Library, \hask{MTL}.

\section{Monad Algebras}

Every adjunction generates a monad, and so far we've been able to define adjunctions for all the monads of interest for us. But is every monad generated by an adjunction? The answer is yes, and there are usually many adjunctions---in fact a whole category of adjunctions---for every monad.

Finding an adjunction for a monad is analogous to factorization. We want to express a functor as a composition of two other functors, $T = R \circ L$. The problem is complicated by the fact that this factorization also requires finding the appropriate intermediate category. We'll find such a category by studying algebras for a monad.

A monad is defined by an endofunctor, and we know that it's possible to define algebras for an endofunctor. Mathematicians often think of monads as tools for generating expressions and algebras as tools for evaluating those expressions. However, expressions generated by monads impose some compatibility conditions on those algebras. 

For instance, you may notice that the monadic unit $\eta_a \colon a \to T a$ has the type signature that looks like the inverse of the structure map of an algebra $\alpha \colon T a \to a$. Of course, $\eta$ is a natural transformation that is defined for every type, whereas an algebra has a fixed carrier type. Nevertheless, we might reasonably expect that one might undo the action of the other.

Consider the earlier example of the expression monad \hask{Ex}. An algebra for this monad is a choice of the carrier type, let's say \hask{Char} and an arrow:
\begin{haskell}
alg :: Ex Char -> Char
\end{haskell}
Since \hask{Ex} is a monad, it defines a unit, or \hask{return}, which is a polymorphic function that can be used to generate simple expressions from values. The unit of \hask{Ex} is:
\begin{haskell}
return x = Var x
\end{haskell}
We can instantiate the unit for an arbitrary type, in particular for the carrier type of our algebra. It makes sense to demand that \emph{evaluating} \hask{Var c}, where \hask{c} is a character, should give us back the same \hask{c}. In other words, we'd like:
\begin{haskell}
 alg . return = id
\end{haskell}
This condition will immediately eliminate a lot of algebras, such as:
\begin{haskell}
alg (Var c) = 'a' -- not compatible with the monad Ex
\end{haskell}

The second condition we'd like to impose is that the algebra that's compatible with a monad respects substitution. A monad lets us flatten nested expressions using \hask{join}. An algebra lets us evaluate such expressions. 

There are two ways of doing that: we can apply the algebra to a flattened expression, or we can apply it to the inner expression first (using \hask{fmap}), and then evaluate the resulting expression. 
\begin{haskell}
 alg (join mma) = alg (fmap alg mma)
\end{haskell}
where \hask{mma} is of the nested type \hask{Ex (Ex Char)}.

In category theory these two conditions define a monad algebra. 

We say that $(a, \alpha \colon T a \to a)$ is a \emph{monad algebra} for the monad $(T, \mu, \eta)$ if the following diagrams commute:
\[
 \begin{tikzcd}
 a
 \arrow[r, "\eta_a"]
 \arrow[dr, "id_a"']
 & T a
 \arrow[d, red, "\alpha"]
 \\
 & a
 \end{tikzcd}
  \hspace{30pt}
 \begin{tikzcd}
T(T a) 
\arrow[r, red, "T \alpha "]
\arrow[d, "\mu_a"]
&T a
\arrow[d, red, "\alpha"]
\\
T a
\arrow[r, red, "\alpha"]
& a
 \end{tikzcd}
\]
These laws are sometimes called the unit law and the multiplication law for monad algebras.

Since monad algebras are just special kinds of algebras, they form a sub-category of algebras. Recall that algebra morphisms are arrows that satisfy the following condition:
\[
 \begin{tikzcd}
 T a 
 \arrow[r, "T f"]
 \arrow[d, "\alpha"]
 & T b
\arrow[d, "\beta"]
 \\
 a
 \arrow[r, "f"]
 & b
  \end{tikzcd}
\]

In light of this definition, we can re-interpret the second monad-algebra diagram as asserting that the structure map $\alpha$ of a monad algebra (the bottom arrow) is also an algebra morphism from $(T a, \mu_a)$ to $(a, \alpha)$. This will come in handy in what follows.

\subsection{Eilenberg-Moore category}

The category of monad algebras for a given monad $T$ on $ \mathcal{C}$ is called the Eilenberg-Moore category and is denoted by $ \mathcal{C}^T$. It turns out that it is a good choice for the intermediate category that lets us factorize the monad $T$ as a composition of a pair of adjoint functors.

The process goes as follows: we define a pair of functors, show that they form an adjunction, and then show that the monad generated by this adjunction is the original monad.

First of all, there is an obvious forgetful functor, which we'll call $U^T$, from $ \mathcal{C}^T$ to $ \mathcal{C}$. It maps an algebra $(a, \alpha)$ to its carrier $a$, and treats algebra morphisms as regular morphisms between carriers. 

More interestingly, there is a free functor $F^T$ that is the left adjoint to $U^T$. 
\[
 \begin{tikzcd}
   \mathcal{C}^T
    \arrow[rr, bend right, "U^T"']
&&
  \mathcal{C}
  \arrow[ll, bend right, "F^T"']
 \end{tikzcd}
\]

On objects, $F^T$ maps an object $a$ of $ \mathcal{C}$ to a \emph{monad algebra}, an object in $\cat{C}^T$. For the carrier of this algebra we pick not $a$ but $T a$. For the structure map, which is the mapping $T (T a) \to T a$ we pick the component of monad multiplication $\mu_a \colon T(T a) \to T a$. 

It's easy to check that this algebra $(T a, \mu_a)$ is indeed a monad algebra---the necessary commuting conditions follow from monad laws. Indeed, substituting the algebra $(T a, \mu_a)$ into the monad-algebra diagrams, we get (with the algebra part drawn in red):
\[
 \begin{tikzcd}
 T a
 \arrow[r, "\eta_{T a}"]
 \arrow[dr, "id_{T a}"']
 & T(T a)
 \arrow[d, red, "\mu_a"]
 \\
 & T a
 \end{tikzcd}
  \hspace{30pt}
 \begin{tikzcd}
T(T(T a))
\arrow[r, red, "T \mu_a "]
\arrow[d, "\mu_{T a}"]
&T(T a)
\arrow[d, red, "\mu_a"]
\\
T (T a)
\arrow[r, red, "\mu_a"]
& T a
 \end{tikzcd}
\]
The first diagram is just the left monadic unit law in components. The $\eta_{T a}$ arrow corresponds to the whiskering of $\eta \circ T$. The second diagram is the associativity of $\mu$ with the two whiskerings $\mu \circ T$ and $T \circ \mu$ expressed in components.


To prove that we have an adjunction, we'll define two natural transformations to serve as the unit and the counit of the adjunction. 

For the unit of the adjunction we pick the monadic unit $\eta$ of $T$. They both have the same signature---in components, $\eta_a \colon a \to U^T (F^T a)$.

The counit is a natural transformation:
\[ \varepsilon \colon F^T \circ U^T \to Id \]
The component of $\varepsilon$ at $(a, \alpha)$ is an algebra morphism from the free algebra generated by $a$, that is $(T a, \mu_a)$, back to $(a, \alpha)$. As we've seen earlier, $\alpha$ itself is such a morphism. We can therefore pick $\varepsilon_{(a, \alpha)} = \alpha$.

Triangular identities for these definitions of $\eta$ and $\varepsilon$ follow from unit laws for the monad and the monad algebra.


As is true for all adjunctions, the composition $U^T \circ F^T$ is a monad. We'll show that this the same monad we started with. Indeed, on objects, the composition $U^T (F^T a)$ first maps $a$ to a free monad algebra $(T a, \mu)$ and then forgets the structure map. The net result is the mapping of $a$ to $T a$, which is exactly what the original monad did. 

On arrows, it lifts an arrow $f \colon a \to b$ using $T$. The fact that the arrow $T f$ is an algebra morphism from $(T a, \mu_a)$ to $(T b, \mu_b)$ follows from naturality of $\mu$:
\[
 \begin{tikzcd}
 T (T a)
 \arrow[r, "T( T f)"]
 \arrow[d, "\mu_a"]
 & T (T B)
\arrow[d, "\mu_b"]
 \\
 T a
 \arrow[r, "T f"]
 & T B
  \end{tikzcd}
\]

Finally, we have to show that the unit and the counit of the monad $U^T \circ F^T$ are the same as the unit and the counit of our original monad.

The units are the same by construction.

The monad multiplication of $U^T \circ F^T$ is given by the whiskering $U^T \circ \varepsilon \circ F^T$ of the unit of the adjunction. In components, this means instantiating $\varepsilon$ at $(T a, \mu_a)$, which gives us $\mu_a$ (the action of $U^T$ on arrows is trivial). This is indeed the original monad multiplication.

We have thus shown that, for any monad $T$ we can define the Eilenberg-Moore category and a pair of adjoint functors that factorize this monad.

\subsection{Kleisli category}

Inside every Eilenberg-Moore category there is a smaller Kleisli category struggling to get out. This smaller category is the image of the free functor we have constructed in the previous section. 

Despite appearances, the image of a functor does not necessarily define a subcategory. Granted, it maps identities to identities and composition to composition. The problem may arise if two arrows that were not composable in the source category become composable in the target category. This may happen if the target of the first arrow is mapped to the same object as the source of the second arrow. In the example below, $F f$ and $F g$ are composable, but their composition $F g \circ F f$ may be absent from the image of the first category.


\[
 \begin{tikzcd}
 a
 \arrow[d, "f"]
 \\ b
 \\ c
 \arrow[d, "g"]
 \\ d
 \end{tikzcd}
  \hspace{30pt}
 \begin{tikzcd}
 F a
 \arrow[d, "F f"]
 \arrow[dd, dashed, bend left=90, "F g \circ F f"]
 \\ F b = F c
  \arrow[d, "F g"]
 \\ F d
 \end{tikzcd}
\]


However, the free functor $F^T$ maps distinct objects into distinct free algebras, so its image is indeed a subcategory of $\mathcal{C}^T$.

We have encountered the Kleisli category before. There are many ways of constructing the same category, and the simplest one is to describe the Kleisli category is in terms of Kleisli arrows. 

A Kleisli category for the monad $(T, \eta, \mu)$ is denoted by $\mathcal{C}_T$. Its objects are the same as the objects of $\mathcal{C}$, but an arrow in $\mathcal{C}_T$ from $a$ to $b$ is represented by an arrow in $\mathcal{C}$ that goes from $a$ to $T b$. You may recognize it as the Kleisli arrow \hask{ a -> m b} we've defined before. Because $T$ is a monad, these Kleisli arrows can be composed using the ``fish'' operator \hask{<=<}. 

To establish the adjunction:
\[
 \begin{tikzcd}
   \mathcal{C}_T
    \arrow[rr, bend right, "R^T"']
&&
  \mathcal{C}
  \arrow[ll, bend right, "L_T"']
 \end{tikzcd}
\]
we define the left functor $L_T \colon \mathcal{C} \to \mathcal{C}_T$ as identity on objects. We still have to define what it does to arrows. It should map a regular arrow $f \colon a \to b$ to a Kleisli arrow from $a$ to $b$. This Kleisli arrow $a \twoheadrightarrow b$ is represented by an arrow $a \to T b$ in $\mathcal{C}$. Such an arrow always exists as the composite $\eta_b \circ f$:
\[ L_T f \colon a \xrightarrow{f} b \xrightarrow{\eta_b} T b\]

The right functor $R_T \colon \mathcal{C}_T \to \mathcal{C}$ is defined on objects as a mapping that takes an $a$ in the Kleisli category to an object $T a$ in $\mathcal{C}$. Given a Kleisli arrow $a \twoheadrightarrow b$, which is represented by an arrow $g \colon a \to T b$, $R_T$ will map it to an arrow $R_T a \to R_T b$, that is an arrow $T a \to T b$ in $\mathcal{C}$. We take this arrow to be the composite $\mu_b \circ T g$:
\[  T a \xrightarrow{T g} T(T b) \xrightarrow{\mu_b} T b\]

To establish the adjunction, we'll show the isomorphism of hom-sets:
\[\mathcal{C}_T(L_T a, b) \cong \mathcal{C}(a, R_T b)\]
An element of the left hand-side is a Kleisli arrow $a \twoheadrightarrow b$, which is represented by $f \colon a \to T b$. We can find the same arrow on the right hand side, since $R_T b$ is $T b$. So the isomorphism is between Kleisli arrows in $\mathcal{C}^T$ and the arrows in $\mathcal{C}$ that represent them.

The composite $R_T \circ L_T$ is equal to $T$ and, indeed, it can be shown that this adjunction generates the original monad. 

In general, there may be many adjunctions that generate the same monad. Adjunctions themselves form a 2-category, so it's possible to compare adjunctions using adjunction morphisms (1-cells in the 2-category). It turns out that the Kleisli adjunction is the initial object among all adjunctions that generate a given monad. Dually, the Eilenberg-Moore adjunction is terminal. 

\end{document}