% !TEX root = ../../ctfp-print.tex

\lettrine[lhang=0.17]{P}{rogrammers have developed} a whole mythology around monads. It's
supposed to be one of the most abstract and difficult concepts in
programming. There are people who ``get it'' and those who don't. For
many, the moment when they understand the concept of the monad is like a
mystical experience. The monad abstracts the essence of so many diverse
constructions that we simply don't have a good analogy for it in
everyday life. We are reduced to groping in the dark, like those blind
men touching different parts of the elephant end exclaiming
triumphantly: ``It's a rope,'' ``It's a tree trunk,'' or ``It's a
burrito!''

Let me set the record straight: The whole mysticism around the monad is
the result of a misunderstanding. The monad is a very simple concept.
It's the diversity of applications of the monad that causes the
confusion.

As part of research for this post I looked up duct tape (a.k.a., duck
tape) and its applications. Here's a little sample of things that you
can do with it:

\begin{itemize}
  \tightlist
  \item
        sealing ducts
  \item
        fixing CO\textsubscript{2} scrubbers on board Apollo 13
  \item
        wart treatment
  \item
        fixing Apple's iPhone 4 dropped call issue
  \item
        making a prom dress
  \item
        building a suspension bridge
\end{itemize}

\noindent
Now imagine that you didn't know what duct tape was and you were trying
to figure it out based on this list. Good luck!

So I'd like to add one more item to the collection of ``the monad is
like\ldots{}'' clichés: The monad is like duct tape. Its applications
are widely diverse, but its principle is very simple: it glues things
together. More precisely, it composes things.

This partially explains the difficulties a lot of programmers,
especially those coming from the imperative background, have with
understanding the monad. The problem is that we are not used to thinking
of programming in terms of function composition. This is understandable.
We often give names to intermediate values rather than pass them
directly from function to function. We also inline short segments of
glue code rather than abstract them into helper functions. Here's an
imperative-style implementation of the vector-length function in C:

\begin{snip}{cpp}
double vlen(double * v) {
    double d = 0.0;
    int n;
    for (n = 0; n < 3; ++n)
        d += v[n] * v[n];
    return sqrt(d);
}
\end{snip}
Compare this with the (stylized) Haskell version that makes function
composition explicit:

\src{snippet01}
(Here, to make things even more cryptic, I partially applied the
exponentiation operator \code{(\^{})} by setting its second argument
to \code{2}.)

I'm not arguing that Haskell's point-free style is always better, just
that function composition is at the bottom of everything we do in
programming. And even though we are effectively composing functions,
Haskell does go to great lengths to provide imperative-style syntax
called the \code{do} notation for monadic composition. We'll see its
use later. But first, let me explain why we need monadic composition in
the first place.

\section{The Kleisli Category}

We have previously arrived at the
\hyperref[kleisli-categories]{writer
  monad} by embellishing regular functions. The particular embellishment
was done by pairing their return values with strings or, more generally,
with elements of a monoid. We can now recognize that such an embellishment
is a functor:

\src{snippet02}
We have subsequently found a way of composing embellished functions, or
Kleisli arrows, which are functions of the form:

\src{snippet03}
It was inside the composition that we implemented the accumulation of
the log.

We are now ready for a more general definition of the Kleisli category.
We start with a category $\cat{C}$ and an endofunctor $m$. The
corresponding Kleisli category $\cat{K}$ has the same objects as
$\cat{C}$, but its morphisms are different. A morphism between two
objects $a$ and $b$ in $\cat{K}$ is implemented as a
morphism:
\[a \to m\ b\]
in the original category $\cat{C}$. It's important to keep in mind that
we treat a Kleisli arrow in $\cat{K}$ as a morphism between $a$
and $b$, and not between $a$ and $m\ b$.

In our example, $m$ was specialized to \code{Writer w}, for
some fixed monoid \code{w}.

Kleisli arrows form a category only if we can define proper composition
for them. If there is a composition, which is associative and has an
identity arrow for every object, then the functor $m$ is called a
\newterm{monad}, and the resulting category is called the Kleisli category.

In Haskell, Kleisli composition is defined using the fish operator
\code{>=>}, and the identity arrow is a
polymorphic function called \code{return}. Here's the definition of a
monad using Kleisli composition:

\src{snippet04}
Keep in mind that there are many equivalent ways of defining a monad,
and that this is not the primary one in the Haskell ecosystem. I like it
for its conceptual simplicity and the intuition it provides, but there
are other definitions that are more convenient when programming. We'll
talk about them momentarily.

In this formulation, monad laws are very easy to express. They cannot be
enforced in Haskell, but they can be used for equational reasoning. They
are simply the standard composition laws for the Kleisli category:

\begin{snip}{haskell}
(f >=> g) >=> h = f >=> (g >=> h) -- associativity
return >=> f = f                  -- left unit
f >=> return = f                  -- right unit
\end{snip}
This kind of a definition also expresses what a monad really is: it's a
way of composing embellished functions. It's not about side effects or
state. It's about composition. As we'll see later, embellished functions
may be used to express a variety of effects or state, but that's not
what the monad is for. The monad is the sticky duct tape that ties one
end of an embellished function to the other end of an embellished
function.

Going back to our \code{Writer} example: The logging functions (the
Kleisli arrows for the \code{Writer} functor) form a category because
\code{Writer} is a monad:

\src{snippet05}
Monad laws for \code{Writer w} are satisfied as long as monoid laws
for \code{w} are satisfied (they can't be enforced in Haskell either).

There's a useful Kleisli arrow defined for the \code{Writer} monad
called \code{tell}. It's sole purpose is to add its argument to the
log:

\src{snippet06}
We'll use it later as a building block for other monadic functions.

\section{Fish Anatomy}

When implementing the fish operator for different monads you quickly
realize that a lot of code is repeated and can be easily factored out.
To begin with, the Kleisli composition of two functions must return a
function, so its implementation may as well start with a lambda taking
an argument of type \code{a}:

\src{snippet07}
The only thing we can do with this argument is to pass it to \code{f}:

\src{snippet08}
At this point we have to produce the result of type \code{m c},
having at our disposal an object of type \code{m b} and a function
\code{g :: b -> m c}. Let's define a function that
does that for us. This function is called \emph{bind} and is usually written in
the form of an infix operator:

\src{snippet09}
For every monad, instead of defining the fish operator, we may instead
define bind. In fact the standard Haskell definition of a monad uses
bind:

\src{snippet10}
Here's the definition of bind for the \code{Writer} monad:

\src{snippet11}
It is indeed shorter than the definition of the fish operator.

It's possible to further dissect bind, taking advantage of the fact that
\code{m} is a functor. We can use \code{fmap} to apply the function
\code{a -> m b} to the contents of \code{m a}. This
will turn \code{a} into \code{m b}. The result of the application
is therefore of type \code{m (m b)}. This is not exactly what we
want --- we need the result of type \code{m b} --- but we're close.
All we need is a function that collapses or flattens the double
application of \code{m}. Such a function is called \code{join}:

\src{snippet12}
Using \code{join}, we can rewrite bind as:

\src{snippet13}
That leads us to the third option for defining a monad:

\src{snippet14}
Here we have explicitly requested that \code{m} be a \code{Functor}.
We didn't have to do that in the previous two definitions of the monad.
That's because any type constructor \code{m} that either supports the
fish or bind operator is automatically a functor. For instance, it's
possible to define \code{fmap} in terms of bind and \code{return}:

\src{snippet15}
For completeness, here's \code{join} for the \code{Writer} monad:

\src{snippet16}

\section{The \texttt{do} Notation}

One way of writing code using monads is to work with Kleisli arrows ---
composing them using the fish operator. This mode of programming is the
generalization of the point-free style. Point-free code is compact and
often quite elegant. In general, though, it can be hard to understand,
bordering on cryptic. That's why most programmers prefer to give names
to function arguments and intermediate values.

When dealing with monads it means favoring the bind operator over the
fish operator. Bind takes a monadic value and returns a monadic value.
The programmer may choose to give names to those values. But that's
hardly an improvement. What we really want is to pretend that we are
dealing with regular values, not the monadic containers that encapsulate
them. That's how imperative code works --- side effects, such as
updating a global log, are mostly hidden from view. And that's what the
\code{do} notation emulates in Haskell.

You might be wondering then, why use monads at all? If we want to make
side effects invisible, why not stick to an imperative language? The
answer is that the monad gives us much better control over side effects.
For instance, the log in the \code{Writer} monad is passed from
function to function and is never exposed globally. There is no
possibility of garbling the log or creating a data race. Also, monadic
code is clearly demarcated and cordoned off from the rest of the
program.

The \code{do} notation is just syntactic sugar for monadic
composition. On the surface, it looks a lot like imperative code, but it
translates directly to a sequence of binds and lambda expressions.

For instance, take the example we used previously to illustrate the
composition of Kleisli arrows in the \code{Writer} monad. Using our
current definitions, it could be rewritten as:

\src{snippet17}
This function turns all characters in the input string to upper case and
splits it into words, all the while producing a log of its actions.

In the \code{do} notation it would look like this:

\src{snippet18}
Here, \code{upStr} is just a \code{String}, even though
\code{upCase} produces a \code{Writer}:

\src{snippet19}
This is because the \code{do} block is desugared by the compiler to:

\src{snippet20}
The monadic result of \code{upCase} is bound to a lambda that takes a
\code{String}. It's the name of this string that shows up in the
\code{do} block. When reading the line:

\src{snippet21}
we say that \code{upStr} \emph{gets} the result of \code{upCase s}.

The pseudo-imperative style is even more pronounced when we inline
\code{toWords}. We replace it with the call to \code{tell}, which
logs the string \code{"toWords "}, followed by the call to
\code{return} with the result of splitting the string \code{upStr}
using \code{words}. Notice that \code{words} is a regular function
working on strings.

\src{snippet22}
Here, each line in the do block introduces a new nested bind in the
desugared code:

\src{snippet23}
Notice that \code{tell} produces a unit value, so it doesn't have to
be passed to the following lambda. Ignoring the contents of a monadic
result (but not its effect --- here, the contribution to the log) is
quite common, so there is a special operator to replace bind in that
case:

\src{snippet24}
The actual desugaring of our code looks like this:

\src{snippet25}
In general, \code{do} blocks consist of lines (or sub-blocks) that
either use the left arrow to introduce new names that are then available
in the rest of the code, or are executed purely for side-effects. Bind
operators are implicit between the lines of code. Incidentally, it is
possible, in Haskell, to replace the formatting in the \code{do}
blocks with braces and semicolons. This provides the justification for
describing the monad as a way of overloading the semicolon.

Notice that the nesting of lambdas and bind operators when desugaring
the \code{do} notation has the effect of influencing the execution of
the rest of the \code{do} block based on the result of each line. This
property can be used to introduce complex control structures, for
instance to simulate exceptions.

Interestingly, the equivalent of the \code{do} notation has found its
application in imperative languages, C++ in particular. I'm talking
about resumable functions or coroutines. It's not a secret that C++
\urlref{https://bartoszmilewski.com/2014/02/26/c17-i-see-a-monad-in-your-future/}{futures
  form a monad}. It's an example of the continuation monad, which we'll
discuss shortly. The problem with continuations is that they are very
hard to compose. In Haskell, we use the \code{do} notation to turn the
spaghetti of ``my handler will call your handler'' into something that
looks very much like sequential code. Resumable functions make the same
transformation possible in C++. And the same mechanism can be applied to
turn the
\urlref{https://bartoszmilewski.com/2014/04/21/getting-lazy-with-c/}{spaghetti
  of nested loops} into list comprehensions or ``generators,'' which are
essentially the \code{do} notation for the list monad. Without the
unifying abstraction of the monad, each of these problems is typically
addressed by providing custom extensions to the language. In Haskell,
this is all dealt with through libraries.
