14-Monads.tex

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

\chapter{Monads}

What do a wheel, a clay pot, and a wooden house have in common? They are all useful because of the emptiness in their center. 

Lao Tzu says: ``The value comes from what is there, but the use comes from what is not there.''

What does the \hask{Maybe} functor, the list functor, and the reader functor have in common? They all have emptiness in their center. 

When monads are explained in the context of programming, it's hard to see the common pattern when you focus on the functors. To understand monads you have to look inside functors and read between the lines of code.

\section{Programming with Side Effects}

So far we've been talking about programming in terms of computations that were modeled mainly on functions between sets (with the exception of non-termination). In programming, such functions are called \emph{total} and \emph{pure}. 

A total function is defined for all values of its arguments. 

A pure function is implemented purely in terms of its arguments and, in case of closures, the captured values---it has no access to, much less the ability to modify the outside world. 

Most real-world programs, though, have to interact with the external world: they read and write files, process network packets, prompt users for data, etc. Most programming languages solve this problem by allowing side effect. A side effect is anything that breaks the totality or the purity of a function. 

Unfortunately, this shotgun approach adopted by imperative languages makes reasoning about programs extremely hard. When composing effectful computations one has to carefully reason about the composition of effects on a case-by-case basis. To make things even harder, most effects are hidden not only inside the implementation (as opposed to the interface) of a particular function, but also in the implementation of all the functions that it's calling, recursively.

The solution adopted by purely functional languages, like Haskell, is to encode side effects in the return types of pure functions. Amazingly, this is possible for all relevant effects. 

The idea is that, instead of a computation of the type \hask{a->b} with side effects, we use a function \hask{ a -> f b}, where the type constructor \hask{f} encodes the appropriate effect. At this point there are no conditions imposed on \hask{f}. It doesn't even have to be a \hask{Functor}, much less a monad. This will come later, when we talk about effect composition.

Below is the list of common effects and their pure-function versions.

\subsection{Partiality}
In imperative languages, partiality is often encoded using exceptions. When a function is called with the ``wrong'' value for its argument, it throws an exception. In some languages, the type of exception is encoded in the signature of the function using special syntax. 

In Haskell, a partial computation can be implemented by a function returning the result inside the \hask{Maybe} functor. Such a function, when called with the ``wrong'' argument, returns \hask{Nothing}, otherwise is wraps the result in the \hask{Just} constructor.

If we want to encode more information about the type of the failure, we can use the \hask{Either} functor, with the \hask{Left} traditionally passing the error data (often a simple \hask{String}); and \hask{Right} encapsulating the real return, if available.

The caller of a \hask{Maybe}-valued function cannot easily ignore the exceptional condition. In order to extract the value, they have to pattern-match the result and decide how to deal with \hask{Nothing}. This is in contrast to the ``poor-man's \hask{Maybe}'' of some imperative languages where the error condition is encoded using a null pointer.

\subsection{Logging}

Sometimes a computation has to log some values in some external data structure. Logging or auditing is a side effect that's particularly dangerous in concurrent programs, where multiple threads might try to access the same log simultaneously.

The simple solution is for a function to return the computed value paired with the item to be logged. In other words, a logging computation of the type \hask{ a -> b } can be replaced by a pure function:
\begin{haskell}
a -> Writer w b
\end{haskell}
where the \hask{Writer} functor is a thin encapsulation of the product:
\begin{haskell}
newtype Writer w a = Writer (a, w)
\end{haskell}
with \hask{w} being the type of the log.

The caller of this function is then responsible for extracting the value to be logged. This is a common trick: make the function provide all the data, and let the caller deal with the effects.

\subsection{Environment}

Some computations need read-only access to some external data stored in the environment. The read-only environment, instead of being secretly accessed by a computation, can be simply passed to a function as an additional argument. If we have a computation \hask{ a -> b } that needs access to some environment \hask{e}, we replace it with a function \hask{ (a, e) -> b }. At first, this doesn't seem to fit the pattern of encoding side effects in the return type. However, such a function can always be curried to the form:
\begin{haskell}
a -> (e -> b)
\end{haskell}
The return type of this function can be encoded in the reader functor, itself parameterized by the environment type \hask{e}:
\begin{haskell}
newtype Reader e a = Reader (e -> a)
\end{haskell}

This is an example of a delayed side effect. The function:
\begin{haskell}
a -> Reader e a
\end{haskell}
doesn't want to deal with effects so it delegates the responsibility to the caller. You may think of it as producing a script to be executed at a later time. The function \hask{runReader} plays the role of a very simple interpreter of this script:
\begin{haskell}
runReader :: Reader e a -> e -> a
runReader (Reader h) e = h e
\end{haskell}

\subsection{State}

The most common side effect is related to accessing and potentially modifying some shared state. Unfortunately, shared state is the notorious source of concurrency errors. This is a serious problem in object-oriented languages where stateful objects can be transparently shared between many clients. In Java, such objects may be provided with individual mutexes at the cost of impaired performance and the risk of deadlocks.

In functional programming we make state manipulations explicit: we pass the state as an additional argument and return the modified state paired with the return value. We replace a stateful computation \hask{ a -> b } with
\begin{haskell}
(a, s) -> (b, s)
\end{haskell}
where \hask{s} is the type of state. As before, we can curry such a function to get it to the form:
\begin{haskell}
a -> (s -> (b, s))
\end{haskell}
This return type can be encapsulated in the following functor:
\begin{haskell}
newtype State s a = State (s -> (a, s))
\end{haskell}
The caller of such a function is supposed to retrieve the result and the modified state by providing the initial state and calling the helper function, the interpreter, \hask{runState}:
\begin{haskell}
runState :: State s a -> s -> (a, s)
runState (State h) s = h s
\end{haskell}
Notice that, modulo constructor unpacking, \hask{runState} is bona fide function application. 

\subsection{Nondeterminism}

Imagine performing a quantum experiment that measures the spin of an electron. Half of the time the spin will be up, and half of the time it will be down. The result is non-deterministic. One way to describe it is to use the many-worlds interpretation: when we perform the experiment, the Universe splits into two universes, one for each result.  

What does it mean for a function to be non-deterministic? It means that it will return different results every time it's called. We can model this behavior using the many-worlds interpretation: we let the function return \emph{all possible results} at once. In practice, we'll settle for a (possibly infinite) list of results:

We replace a non-deterministic computation \hask{ a -> b } with a pure function returning a functorful of results---this time it's the list functor:
\begin{haskell}
a -> [b]
\end{haskell}
Again, it's up to the caller to decide what to do with these results.

\subsection{Input/Output}

This is the trickiest side effect because it involves interacting with the external world. Obviously, we cannot model the whole world inside a computer program. So, in order to keep the program pure, the interaction has to happen outside of it. The trick is to let the program generate a script. This script is then passed to the runtime to be executed. The runtime is the effectful virtual machine that runs the program. 

This script itself sits inside the opaque, predefined \hask{IO} functor. The values hidden in this functor are not accessible to the program: there is no \hask{runIO} function. Instead, the \hask{IO} value produced by the program is executed, at least conceptually, \emph{after} the program is finished. 

In reality, because of Haskell's laziness, the execution of I/O is interleaved with the rest of the program.  Pure functions that comprise the bulk of your program are evaluated on demand---the demand being driven by the execution of the \hask{IO} script. If it weren't for I/O, nothing would ever be evaluated.

The \hask{IO} object that is produced by a Haskell program is called \hask{main} and its type signature is:
\begin{haskell}
main :: IO ()
\end{haskell}
It's the \hask{IO} functor containing the unit---meaning: there is no useful value other than the input/output script.

We'll talk about how \hask{IO} actions are created soon.

\subsection{Continuation}

We've seen that, as a consequence of the Yoneda lemma, we can replace a value of type \hask{a} with a function that takes a handler for that value. This handler is called a continuation. Calling a handler is considered a side effect of a computation. In terms of pure functions, we encode it as:
\begin{haskell}
a -> Cont r b
\end{haskell}
where \hask{Cont r} is the following functor:
\begin{haskell}
newtype Cont r a = Cont ((a -> r) -> r)
\end{haskell}
It's the responsibility of the caller of this function to provide the continuation, a function \hask{k :: a -> r}, and retrieve the result:
\begin{haskell}
runCont :: Cont r a -> (a -> r) -> r
runCont (Cont f) k = f k
\end{haskell}

This is the \hask{Functor} instance for \hask{Cont r}:
\begin{haskell}
instance Functor (Cont r) where
  -- f :: a -> b
  -- k :: b -> r
  fmap f c = Cont (\k -> runCont c (k . f))
\end{haskell}
Notice that this is a covariant functor because the type \hask{a} is in a doubly negative position.

In a cartesian closed category, continuations are generated by the endofunctor:
\[ K_r a = r^{r^a} \]

\section{Composing Effects}

Now that we know how to make one giant leap using a function that produces both a value and a side effect, the next problem is to figure out how to decompose this leap into smaller human-sized steps. Or, conversely, how to combine such smaller steps into one larger step. 

The way effectful computations are composed in imperative languages is to use regular function composition for the values and let the side effects combine themselves willy-nilly. 

When we represent effectful computations as pure functions, we are faced with the problem of composing two functions of the form
\begin{haskell}
g :: a -> f b
h :: b -> f c
\end{haskell}
In all cases of interest the type constructor \hask{f} happens to be a \hask{Functor}, so we'll assume that in what follows.

The naive approach would be to unpack the result of the first function, pass the value to the next function, then compose the effects of both functions on the side, and combine them with the result of the second function. This is not always possible, even for cases that we have studied so far, much less for an arbitrary type constructor.

For the sake of the argument, it's instructive to see how we could do it for the \hask{Maybe} functor. If the first function returns \hask{Just}, we pattern match it to extract the contents and call the next function with it.

But if the first function returns \hask{Nothing}, we have no value with which to call the second function. We have to short-circuit it, and return \hask{Nothing} directly. So composition is possible, but it means modifying flow of control by skipping the second call based on the side effect of the first call. 

For some functors the composition of side effects is possible, for others it's not. How can we characterize those ``good'' functors?

For a functor to encode composable side effects we must at least be able to implement the following polymorphic higher-order function: 
\begin{haskell}
composeWithEffects :: Functor f => 
       (b -> f c) -> (a -> f b) -> (a -> f c)
\end{haskell}
This is very similar to regular function composition:
\begin{haskell}
(.) :: (b -> c) -> (a -> b) -> (a -> c)
\end{haskell}
so it's natural to ask if there is a category in which the former defines a composition of arrows. Let's see what more is needed to construct such a category.

Objects in this new category are the same Haskell types as before. But an arrow $a \twoheadrightarrow b$, is implemented as a Haskell function:
\begin{haskell}
g :: a -> f b
\end{haskell}
Our \hask{composeWithEffects} can then be used to implement the composition of such arrows. 

To have a category, we require that this composition be associative. We also need an identity arrow for every object \hask{a}. This is an arrow $a \twoheadrightarrow a$, so it corresponds to a Haskell function:
\begin{haskell}
idWithEffects :: a -> f a
\end{haskell}
It must behave like identity with respect to \hask{composeWithEffects}.

Another way of looking at this arrow is that it lets you add a trivial effect to any value of type \hask{a}. It's the effect that combined with any other effect does nothing to it.

We have just defined a monad! After some renaming and rearranging, we can write it as a typeclass:
\begin{haskell}
class Functor m => Monad m where
  (<=<) :: (b -> m c) -> (a -> m b) -> (a -> m c)
  return :: a -> m a
\end{haskell}
The infix operator \hask{<=<} replaces the function \hask{composeWithEffects}. The \hask{return} function is the identity arrow in our new category. (This is not the definition of the monad you'll find in the Haskell's \hask{Prelude} but, as we'll see soon, it's equivalent to it.)

As an exercise, let's define the \hask{Monad} instance for \hask{Maybe}. The ``fish'' operator \hask{<=<} composes two functions:
\begin{haskell}
f :: a -> Maybe b
g :: b -> Maybe c
\end{haskell}
into one function of the type \hask{a -> Maybe c}. The unit of this composition, \hask{return}, encloses a value in the \hask{Just} constructor.
\begin{haskell}
instance Monad Maybe where
  g <=< f = \a -> case f a of
                    Nothing -> Nothing
                    Just b -> g b
  return = Just  
\end{haskell}

You can easily convince yourself that category laws are satisfied. In particular \hask{ return <=< g } is the same as \hask{g} and \hask{ f <=< return } is the same as \hask{f}. The proof of associativity is also pretty straightforward: If any of the functions returns \hask{Nothing}, the result is \hask{Nothing}; otherwise it's just a straightforward function composition, which is associative.

The category that we have just defined is called the \index{Kleisli category}\emph{Kleisli category} for the monad \hask{m}. The functions \hask{a -> m b} are called the \index{Kleisli arrow}\emph{Kleisli arrows}. They compose using \hask{<=<} and the identity arrow is called \hask{return}.

All functors from the previous section are \hask{Monad} instances. If you look at them as type constructors, or even functors, it's hard to see any similarities between them. The thing they have in common is that they can be used to implement \emph{composable} Kleisli arrows. 

As Lao Tze would say: Composition is something that happens \emph{between} things. While focusing our attention on things, we often lose sight of what's in the gaps. 

\section{Alternative Definitions}

The definition of a monad using Kleisli arrows has the advantage that the monad laws are simply the associativity and the unit laws of a category. There are two other equivalent definitions of a monad, one preferred by mathematicians, and one by programmers. 

First, let's notice that, when implementing the fish operator, we are given two functions as arguments. The only thing a function is useful for is to be applied to an argument. When we apply the first function \hask{ f :: a -> m b } we get a value of the type \hask{ m b}. At this point we would be stuck, if it weren't for the fact that \hask{m} is a functor. Functoriality lets us apply the second function \hask{ g :: b -> m c } to \hask{ m b}. Indeed the lifting of \hask{g} by \hask{m} is of the type:
\begin{haskell}
m b -> m (m c)
\end{haskell}
This is almost the result we are looking for, if we could only flatten \hask{m(m c)} to \hask{m c}. This flattening is called \hask{join}. In other words, if we are given:
\begin{haskell}
join ::  m (m a) -> m a
\end{haskell}
we can implement \hask{<=<}:
\begin{haskell}
g <=< f = \a -> join (fmap g (f a))
\end{haskell}
or, using point free notation:
\begin{haskell}
g <=< f = join . fmap g . f
\end{haskell}

Conversely, \hask{join} can be implemented in terms of \hask{<=<}:
\begin{haskell}
join = id <=< id
\end{haskell}
The latter may not be immediately obvious, until you realize that the rightmost \hask{id} is applided to \hask{m (m a)}, and the leftmost is applied to \hask{m a}. We interpret a Haskell function:
\begin{haskell}
m (m a) -> m (m a)
\end{haskell}
as an arrow in the Kleisli category $ m (m a) \twoheadrightarrow m a$. Similarly, the function:
\begin{haskell}
m a -> m a
\end{haskell}
implements a Kleisli arrow $m a \twoheadrightarrow a$. Their Kleisli composition produces a Kleisli arrow $m (m a) \twoheadrightarrow a$ or a Haskell function:
\begin{haskell}
m (m a) -> m a
\end{haskell}

This leads us to the equivalent definition of a monad in terms of \hask{join} and \hask{return}:
\begin{haskell}
class Functor m => Monad m where
  join :: m (m a) -> m a
  return :: a -> m a
\end{haskell}

This is still not the definition you will find in the standard Haskell \hask{Prelude}. Since the fish operator is a generalization of the dot operator, using it is equivalent to point-free programming. It lets us compose arrows without naming intermediate values. Although some consider point-free programs more elegant, most programmers find them difficult to follow. 

But function composition is really done in two steps: We apply the first function, then apply the second function to the result. Explicitly naming the intermediate result is often helpful in understanding what's going on.

To do the same with Kleisli arrows, we have to know how to apply the second Kleisli arrow to a named monadic value---the result of the first Kleisli arrow. The function that does that is called \emph{bind} and is written as an infix operator:
\begin{haskell}
(>>=) :: m a -> (a -> m b) -> m b
\end{haskell}
Obviously, we can implement Kleisli composition in terms of bind:

\begin{haskell}
g <=< f = \a -> (f a) >>= g
\end{haskell}

Conversely, bind can be implemented in terms of the Kleisli arrow:
\begin{haskell}
ma >>= k = (k <=< id) ma
\end{haskell}

This leads us to the following definition:
\begin{haskell}
class Monad m where
  (>>=) :: m a -> (a -> m b) -> m b
  return :: a -> m a 
\end{haskell}
This is almost the definition you'll find in the \hask{Prelude}, except for the additional constraint. This constraint states the fact that every instance of \hask{Monad} is also an instance of \hask{Applicative}. We will postpone the discussion of applicatives to the section on monoidal functors.

We can also implement \hask{join} using bind:
\begin{haskell}
join  :: (Monad m) => m (m a) -> m a
join mma =  mma >>= id
\end{haskell}
The Haskell function \hask{id} goes from \hask{m a} to \hask{m a} or, as a Kleisli arrow, $m a \twoheadrightarrow a$.

Interestingly, a \hask{Monad} defined using bind is automatically a functor. The lifting function for it is called \hask{liftM}
\begin{haskell}
liftM :: Monad m => (a -> b) -> (m a -> m b)
liftM f ma = ma >>= (return . f)
\end{haskell}

\section{Monad Instances}

We are now ready to define monad instances for the functors we used for side effects. This will allow us to compose side effects.

\subsection{Partiality}
We've already seen the version of the \hask{Maybe} monad implemented using Kleisli composition. Here's the more familiar implementation using bind:
\begin{haskell}
instance Monad Maybe where
  Nothing >>= k = Nothing
  (Just a) >>= k = k a
  return = Just
\end{haskell}
Adding a trivial effect to any value means enclosing it in \hask{Just}.
\subsection{Logging}
In order to compose functions that produce logs, we need a way to combine individual log entries. This is why the writer monad:
\begin{haskell}
newtype Writer w a = Writer (a, w)
\end{haskell}
requires the type of the log to be an instance of \hask{Monoid}. This allows us to append logs, and also to create a trivial effect: an empty log.
\begin{haskell}
instance Monoid w => Monad (Writer w) where
  (Writer (a, w)) >>= k = let (Writer (b, w')) = k a
                          in Writer (b, mappend w w')
  return a = Writer (a, mempty)
\end{haskell}
The \index{\hask{let}}\hask{let} clause is used for introducing local bindings. Here, the result of applying \hask{k} is pattern matched, and the local variables \hask{b} and \hask{w'} are initialized. The \hask{let}/\hask{in} construct is an expression whose value is given by the content of the \hask{in} clause.

\subsection{Environment}

The reader monad is a thin encapsulation of a function from the environment to the return type:
\begin{haskell}
newtype Reader e a = Reader (e -> a)
\end{haskell}
Here's the \hask{Monad} instance:
\begin{haskell}
instance Monad (Reader e) where
  ma >>= k = Reader (\e -> let a = runReader ma e
                           in runReader (k a) e)
  return a = Reader (\e -> a)
\end{haskell}
The implementation of bind for the reader monad creates a function that takes the environment as its argument. This environment is used twice, first to run \hask{ma} to get the value of \hask{a}, and then to evaluate the value produced by \hask{k a}.

The implementation of \hask{return} ignores the environment.

\begin{exercise}
Define the \hask{Functor} and the \hask{Monad} instance for the following data type:
\begin{haskell}
newtype E e a = E (e -> Maybe a)
\end{haskell}
Hint: You may use this handy function:
\begin{haskell}
runE :: E e a -> e -> Maybe a
runE (E f) e = f e
\end{haskell}
\end{exercise}


\subsection{State}
Like reader, the state monad is a function type:
\begin{haskell}
newtype State s a = State (s -> (a, s))
\end{haskell}
Its bind is similar, except that the result of \hask{k} acting on  \hask{a} has to be run with the modified state \hask{s'}.
\begin{haskell}
instance Monad (State s) where
  st >>= k = State (\s -> let (a, s') = runState st s
                          in runState (k a) s')
                          
  return a = State (\s -> (a, s))
\end{haskell}

Applying bind to identity gives us the definition of \hask{join}:
\begin{haskell}
join :: State s (State s a) -> State s a
join mma = State (\s -> let (ma, s') = runState mma s
                        in runState ma s')
\end{haskell}
Notice that we are essentially passing the result of the first \hask{runState} to the second \hask{runState}, except that we have to uncurry the second one so it can accept a pair:
                             
\begin{haskell}
join mma = State (\s -> (uncurry runState) (runState mma s))
\end{haskell}
In this form, it's easy to convert it to point-free notation:
\begin{haskell}
join mma = State (uncurry runState . runState mma)
\end{haskell}

There are two basic Kleisli arrows (the first one, conceptually, coming from the terminal object \hask{()}) with which we can construct an arbitrary stateful computation. The first one retrieves the current state:
\begin{haskell}
get :: State s s
get = State (\s -> (s, s))
\end{haskell}
and the second one modifies it:
\begin{haskell}
set :: s -> State s ()
set s = State (\_ -> ((), s))
\end{haskell}
A lot of monads come with their own libraries of predefined basic Kleisli arrows.
\subsection{Nondeterminism}

For the list monad, let's consider how we would implement \hask{join}. It must turn a list of lists into a single list. This can be done by concatenating all the inner lists using the library function \hask{concat}. From there, we can derive the implementation of bind.
\begin{haskell}
instance Monad [] where
  as >>= k = concat (fmap k as)
  return a = [a]
\end{haskell}
Here, \hask{return} constructs a singleton list. Thus a trivial version of nondeterminism is determinism.

What imperative languages do using nested loops we can do in Haskell using the list monad. Think of \hask{as} in bind as aggregating the result of running the inner loop and \hask{k} as the code that runs in the outer loop. 

In many ways, Haskell's list behaves more like what is called an \index{iterator}\emph{iterator} or a \emph{generator} in imperative languages. Because of laziness, the elements of the list are rarely stored in memory all at once, so you may conceptualize a Haskell list as a pointer to the head and a recipe for advancing it forward towards the tail. Or you may think of a list as a coroutine that produces, on demand, elements of a sequence.

\subsection{Continuation}

The implementation of bind for the continuation monad:

\begin{haskell}
newtype Cont r a = Cont ((a -> r) -> r)
\end{haskell}
requires some backward thinking, because of the inherent inversion of control---the ``don't call us, we'll call you'' principle. 

The result of bind is of the type \hask{Cont r b}. To construct it, we need a function that takes, as an argument \hask{k :: b -> r}:
\begin{haskell}
ma >>= fk = Cont (\k -> ...)
\end{haskell}
We have two ingredients at our disposal: 
\begin{haskell}
ma :: Cont r a
fk :: a -> Cont r b
\end{haskell}
We'd like to run \hask{ma}, and for that we need a continuation that would accept an \hask{a}.
\begin{haskell}
runCont ma (\a -> ...)
\end{haskell}
Once we have an \hask{a}, we can execute our \hask{fk}. The result is of the type \hask{Cont r b}, so we can run it with our continuation \hask{k :: b -> r}. 
\begin{haskell}
runCont (fk a) k
\end{haskell}

Taken together, this convoluted process produces the following implementation:
\begin{haskell}
instance Monad (Cont r) where
  ma >>= fk = Cont (\k -> runCont ma (\a -> runCont (fk a) k))
  return a = Cont (\k -> k a)
\end{haskell}
As I mentioned earlier, composing continuations is not for the faint of heart. However, it has to be implemented only once---in the definition of the continuation monad. From there on, the \hask{do} notation will make the rest relatively easy.

\subsection{Input/Output}

The \hask{IO} monad's implementation is baked into the language. The basic I/O primitives are available through the library. They are either in the form of Kleisli arrows, or \hask{IO} objects (conceptually, Kleisli arrows from the terminal object \hask{()}). 

For instance, the following object contains a command to read a line from the standard input:
\begin{haskell}
getLine :: IO String
\end{haskell}
There is no way to extract the string from it, since it's not there yet; but the program can process it through a further series of Kleisli arrows. 

The \hask{IO} monad is the ultimate procrastinator: the composition of its Kleisli arrows piles up task after task to be executed later by the Haskell runtime.

To output a string followed by a newline, you can use this Kleisli arrow:
\begin{haskell}
putStrLn :: String -> IO ()
\end{haskell}
Combining the two, you may construct a simple \hask{main} object:
\begin{haskell}
main :: IO ()
main = getLine >>= putStrLn
\end{haskell}
which echoes a string you type.

\section{Do Notation}

It's worth repeating that the sole purpose of monads in programming is to let us decompose one big Kleisli arrow into multiple smaller ones. 

This can be either done directly, in a point-free style, using Kleisli composition \hask{<=<}; or by naming intermediate values and binding them to Kleisli arrows using \hask{>>=}. 

Some Kleisli arrows are defined in libraries, others are reusable enough to warrant out-of-line implementation but, in practice, the majority are implemented as single-shot inline lambdas.

Here's a simple example:
\begin{haskell}
main :: IO ()
main = 
  getLine >>= \s1 ->
    getLine >>= \s2 ->
      putStrLn ("Hello " ++ s1 ++ " " ++ s2)
\end{haskell}
which uses an ad-hoc Kleisli arrow of the type \hask{String->IO ()} defined by the lambda expression:
\begin{haskell}
\s1 ->
    getLine >>= \s2 ->
      putStrLn ("Hello " ++ s1 ++ " " ++ s2)
\end{haskell}
The body of this lambda is further decomposed using another ad-hoc Kleisli arrow:
\begin{haskell}
\s2 -> putStrLn ("Hello " ++ s1 ++ " " ++ s2)
\end{haskell}

Such constructs are so common that there is special syntax called the \hask{do} notation that cuts through a lot of boilerplate. The above code, for instance, can be written as:
\begin{haskell}
main = do
  s1 <- getLine
  s2 <- getLine
  putStrLn ("Hello " ++ s1 ++ " " ++ s2)
\end{haskell}
The compiler will automatically convert it to a series of nested lambdas. The line \hask{ s1<-getLine } is usually read as: ``\hask{s1} \emph{gets} the result of \hask{getLine}.''

Here's another example: a function that uses the list monad to generate all possible pairs of elements taken from two lists.
\begin{haskell}
pairs :: [a] -> [b] -> [(a, b)]
pairs as bs = do
  a <- as
  b <- bs
  return (a, b)
\end{haskell}
Notice that the last line in a \hask{do} block must produce a monadic value---here this is accomplished using \hask{return}.

Most imperative languages lack the abstraction power to generically define a monad, and instead they attempt to hard-code some of the more common monads. For instance, they implement exceptions as an alternative to the \hask{Either} monad, or concurrent tasks as an alternative to the continuation monad. Some, like C++, introduce coroutines that mimic Haskell's \hask{do} notation. 

\begin{exercise}
Implement the following function that works for any monad:
\begin{haskell}
ap :: Monad m => m (a -> b) -> m a -> m b
\end{haskell}
Hint: Use \hask{do} notation to extract the function and the argument. Use \hask{return} to return the result.
\end{exercise}

\begin{exercise}
Rewrite the \hask{pairs} function using the bind operators and lambdas.
\end{exercise}

\section{Continuation Passing Style}

I mentioned before that the \hask{do} notation provides the syntactic sugar that makes working with continuations more natural. One of the most important applications of continuations is in transforming programs to use CPS (continuation passing style). The CPS transformation is common in compiler construction. Another very important application of CPS is in converting recursion to iteration. 

The common problem with deeply recursive programs is that they may blow the runtime stack. A function call usually starts by pushing function arguments, local variables, and the return address on the stack. Thus deeply nested recursive calls may quickly exhaust the (usually fixed-size) runtime stack resulting in a runtime error. This is the main reason why imperative languages prefer looping to recursion, and why most programmers learn about loops before they study recursion. However, even in imperative languages, when it comes to traversing recursive data structures, such as linked lists or trees, recursive algorithms are more natural.

The problem with using loops, though, is that they require mutation. There is usually some kind of a counter or a pointer that is advanced and checked with each turn of the loop. This is why purely functional languages that shun mutation must use recursion in place of loops. But since looping is more efficient and it doesn't consume the runtime stack, the compiler tries to covert recursive calls to loops. In Haskell all tail-recursive functions are turned into loops. 

\subsection{Tail recursion and CPS}

\index{tail recursion}Tail recursion means that the recursive call happens at the very end of the function. The function doesn't perform any additional operations on the result of the tail call. For instance this program is not tail recursive, because it has to add \hask{i} to the result of the recursive call:
\begin{haskell}
sum1 :: [Int] -> Int
sum1 [] = 0
sum1 (i : is) = i + sum1 is
\end{haskell}
In contrast, the following implementation is tail recursive because the result of the recursive call to \hask{go} is returned without further modification:
\begin{haskell}
sum2 = go 0 
  where go n [] = n
        go n (i : is) = go (n + i) is
\end{haskell}
The compiler can easily turn the latter into a loop. Instead of making the recursive call, it will overwrite the value of the first argument \hask{n} with \hask{n + i}, overwrite the pointer to the head of the list with the pointer to its tail, and then jump to the beginning of the function. 

Note however that it doesn't mean that the Haskell compiler won't be able to cleverly optimize the first implementation. It just means that the second implementation, which is tail recursive, is \emph{guaranteed} to be turned into a loop.

In fact, it's always possible to turn recursion into tail recursion by performing the CPS transformation. This is because a continuation encapsulates \emph{the rest of the computation}, so it's always the last call in a function. 

To see how it works in practice, consider a simple tree traversal. Let's define a tree that stores strings in both nodes and leaves:
\begin{haskell}
data Tree = Leaf String 
          | Node Tree String Tree
\end{haskell}
To concatenate these strings we use the traversal that first recurses into the left subtree, and then into the right subtree:
\begin{haskell}
show :: Tree -> String
show (Node lft s rgt) =
  let ls = show lft
      rs = show rgt
  in ls ++ s ++ rs
\end{haskell}
This is definitely not a tail recursive function, and it's not obvious how to turn it into one. However, we can almost mechanically rewrite it using the continuation monad:
\begin{haskell}
showk :: Tree -> Cont r String
showk (Leaf s) = return s
showk (Node lft s rgt) = do
  ls <- showk lft
  rs <- showk rgt
  return (ls ++ s ++ rs)
 \end{haskell}
We can run the result with the trivial continuation \hask{id}:
\begin{haskell}
show :: Tree -> String
show t = runCont (showk t) id
\end{haskell}

This implementation is automatically tail recursive. We can see it clearly by desugaring the do notation:
\begin{haskell}
showk :: Tree -> (String -> r) -> r
showk (Leaf s) k = k s
showk (Node lft s rgt) k =
  showk lft (\ls -> 
    showk rgt (\rs -> 
      k (ls ++ s ++ rs)))
\end{haskell}
Let's analyze this code. The function calls itself, passing the left subtree \hask{lft} and the following continuation:
\begin{haskell}
\ls -> 
    showk rgt (\rs -> 
      k (ls ++ s ++ rs))
\end{haskell}
This lambda in turn calls \hask{showk} with the right subtree \hask{rgt} and another continuation:
\begin{haskell}
\rs -> k (ls ++ s ++ rs)
\end{haskell}
This innermost lambda that has access to all three strings: left, middle, and right. It concatenates them and calls the outermost continuation \hask{k} with the result.

In each case, the recursive call to \hask{showk} is the last call, and its result is immediately returned. Moreover, the type of the result is the generic type \hask{r}, which in itself guarantees that we can't perform any operations on it. When we finally run the result of \hask{showk}, we pass it the identity (instantiated for the \hask{String} type):
\begin{haskell}
show :: Tree -> String
show t = runCont (showk t) id
\end{haskell}

\subsection{Using named functions}

But suppose that our programming language doesn't support anonymous functions. Is it possible to replace the lambdas with named functions? We've done this before when we discussed the adjoint functor theorem. We notice that the lambdas generated by the continuation monad are closures---they capture some values from their environment. If we want to replace them with named functions, we'll have to pass the environment explicitly. 

We replace the first lambda with the call to the function named \hask{next}, and pass it the necessary environment in the form or a tuple of three values \hask{(s, rgt, k)}:
\begin{haskell}
showk :: Tree -> (String -> r) -> r
showk (Leaf s) k = k s
showk (Node lft s rgt) k =
  showk lft (next (s, rgt, k))
\end{haskell}
The three values are the string from the current node of the tree, the right subtree, and the outer continuation. 

The function \hask{next} makes the recursive call to \hask{showk} passing to it the right subtree and a continuation named \hask{conc}:
\begin{haskell}
next :: (String, Tree, String -> r) -> String -> r
next (s, rgt, k) ls = showk rgt (conc (ls, s, k))
\end{haskell}
Again, \hask{conc} explicitly captures the environment containing two strings and the outer continuation. It performs the concatenation and calls the outer continuation with the result:
\begin{haskell}
conc :: (String, String, String -> r) -> String -> r
conc (ls, s, k) rs = k (ls ++ s ++ rs)
\end{haskell}
Finally, we define the trivial continuation:
\begin{haskell}
done :: String -> String
done s = s
\end{haskell}
that we use to extract the final result:
\begin{haskell}
show t = showk t done
\end{haskell}

\subsection{Defunctionalization}

Continuation passing style requires the use of higher order functions. If this is a problem, e.g., when implementing distributed systems, we can always use the adjoint functor theorem to defunctionalize our program. 

The first step is to create the sum of all relevant environments, including the empty one we used in \hask{done}:
\begin{haskell}
data Kont = Done 
          | Next String Tree Kont 
          | Conc String String Kont
\end{haskell}
Notice that this data structure can be reinterpreted as a list or a stack. It can be seen as a list of elements of the following sum type:
\begin{haskell}
data Sum = Next' String Tree  | Conc' String String 
\end{haskell}
This list is our version of the runtime stack necessary to implement a recursive algorithm. 

Since we are only interested in producing a string as the final result, we're going to approximate the \hask{String -> String} function type. This is the approximate counit of the adjunction that defines it (see the adjoint functor theorem):
\begin{haskell}
apply :: (Kont, String) -> String
apply (Done, s) = s
apply (Next s rgt k, ls) = showk rgt (Conc ls s k)
apply (Conc ls s k, rs) = apply (k, ls ++ s ++ rs)
\end{haskell}

The \hask{showk} function can be now implemented without recourse to higher order functions:
\begin{haskell}
showk :: Tree -> Kont -> String
showk (Leaf s) k = apply (k, s)
showk (Node lft s rgt) k = showk lft (Next s rgt k)
\end{haskell}
To extract the result, we call it with \hask{Done}:
\begin{haskell}
showTree t = showk t Done
\end{haskell}

\section{Monads Categorically}

In category theory monads first arose in the study of algebras. In particular, the bind operator can be used to implement the very important operation of substitution. 

\subsection{Substitution}

Consider this simple expression type. It's parameterized by the type \hask{x} that we can use for naming our variables:
\begin{haskell}
data Ex x = Val Int 
          | Var x 
          | Plus (Ex x) (Ex x) 
 deriving (Functor, Show)
\end{haskell}
We can, for instance, construct an expression $(2 + a) + b$:
\begin{haskell}
ex :: Ex Char
ex = Plus (Plus (Val 2) (Var 'a')) (Var 'b')
\end{haskell}
We can implement the \hask{Monad} instance for \hask{Ex}:
\begin{haskell}
instance Monad Ex where
  Val n >>= k = Val n
  Var x >>= k = k x
  Plus e1 e2 >>= k = 
    let x = e1 >>= k
        y = e2 >>= k
    in (Plus x y)
    
  return x = Var x 
\end{haskell}

Now suppose that you want to make a substitution by replacing the variable $a$ with $x_1 + 2$ and $b$ with $x_2$ (for simplicity, let's not worry about other letters of the alphabet). This substitution is represented by the Kleisli arrow \hask{sub}:
\begin{haskell}
sub :: Char -> Ex String
sub 'a' = Plus (Var "x1") (Val 2)
sub 'b' = Var "x2"
\end{haskell}
As you can see, we were even able to change the type used for naming variables from \hask{Char} to \hask{String}.

When we bind this Kleisli arrow to \hask{ex}:
\begin{haskell}
ex' :: Ex String
ex' = ex >>= sub
\end{haskell}
we get, as expected, a tree corresponding to $(2 + (x_1 + 2)) + x_2$.

\subsection{Monad as a monoid}

Let's analyze the definition of a monad that uses \hask{join}:
\begin{haskell}
class Functor m => Monad m where
  join :: m (m a) -> m a
  return :: a -> m a
\end{haskell}
We have an endofunctor \hask{m} and two polymorphic functions. 

In category theory, the functor that defines the monad is traditionally denoted by $T$ (probably because monads were initially called ``triples''). The two polymorphic functions become natural transformations. The first one, corresponding to \hask{join}, maps the ``square'' of $T$ (a composition of $T$ with itself) to $T$:
\[ \mu \colon T \circ T \to T \]
(Of course, only \emph{endo}-functors can be squared this way.) 

The second, corresponding to \hask{return}, maps the identity functor to $T$:
\[ \eta \colon \text{Id} \to T \]

Compare this with our earlier definition of a monoid in a monoidal category:
\begin{align*}
\mu &\colon m \otimes m \to m \\
\eta &\colon I \to m
\end{align*}
The similarity is striking. This is why we often call the natural transformation $\mu$ the \emph{monadic multiplication}. But in what category can the composition of functors be considered a tensor product? 

Enter the category of endofunctors. Objects in this category are endofunctors and arrows are natural transformations. 

But there's more structure to that category. We know that any two endofunctors can be composed. How can we interpret this composition if we want to treat endofunctors as objects? An operation that takes two objects and produces a third object looks like a tensor product.  The only condition imposed on a tensor product is that it's functorial in both arguments. That is, given a pair of arrows:
\begin{align*}
 \alpha &\colon T \to T' \\
 \beta &\colon S \to S' 
\end{align*}
 we can lift it to the mapping of the tensor product:
 \[ \alpha \otimes \beta \colon T \otimes S \to T' \otimes S' \]
 
 In the category of endofunctors, the arrows are natural transformations so, if we replace $\otimes$ with $\circ$, the lifting is the mapping:
\[ \alpha \circ \beta \colon T \circ T' \to S \circ S' \]
But this is just horizontal composition of natural transformations (now you understand why it's denoted by a circle).

The unit object in this monoidal category is the identity endofunctor, and unit laws are satisfied ``on the nose,'' meaning
\[ \text{Id} \circ T = T = T \circ \text{Id}\]
We don't need any unitors. We don't need any associators either, since functor composition is automatically associative. 

A monoidal category in which unitors and associators are identity morphisms is called a \index{strict monoidal category}\emph{strict} monoidal category.

Notice, however, that composition is not symmetric, so this is not a symmetric monoidal category.

So, all said, a monad is a monoid in the monoidal category of endofunctors. 

A monad $(T, \eta, \mu)$ consists of an object in the category of endofunctors---meaning an endofunctor $T$; and two arrows---meaning natural transformations:
\begin{align*}
 \eta &\colon \text{Id} \to T \\
 \mu &\colon T \circ T \to T 
\end{align*}
For this to be a monoid, these arrows must satisfy monoidal laws. Here are the unit laws (with unitors replaced by strict equalities):
\[
 \begin{tikzcd}
\text{Id} \circ T
 \arrow[rr, "\eta \circ T"]
 \arrow[rrd, "="']
& & T \circ T
 \arrow[d, "\mu"]
&& T \circ \text{Id}
 \arrow[ll, "T \circ \eta"']
 \arrow[lld, "="]
 \\
 && T
  \end{tikzcd}
\]
and this is the associativity law:
\[
 \begin{tikzcd}
 (T \circ T) \circ T 
 \arrow[rr, "="]
 \arrow[d, "\mu \circ T"]
 &&
 T \circ (T \circ T)
 \arrow[d, "T \circ \mu"]
 \\
 T \circ T 
 \arrow[dr, "\mu"]
& & T \circ T
 \arrow[dl, "\mu"']
 \\
&  T
 \end{tikzcd}
\]
We used the whiskering notation for horizontal composition of $\mu \circ T$ and $T \circ \mu$.

These are the monad laws in terms of $\mu$ and $\eta$. They can be directly translated to the laws for \hask{join} and \hask{return}. They are also equivalent to the laws of the Kleisli category built from arrows $a \to T b$.

\section{Free Monads}

A monad lets us specify a sequence of actions that may produce side effects. Such a sequence tells the computer both what to do and how to do it. But sometimes more flexibility is required: We'd like to separate the ``what'' from the ``how." A free monad lets us produce the sequence without committing to a particular monad for its execution. This is analogous to defining a free monoid (a list), which lets us postpone the choice of the algebra to apply to it; or to creating an AST (abstract syntax tree) before compiling it to executable code.

Free constructions are defined as left adjoints to forgetful functors. So first we have to define what it means to forget to be a monad. Since a monad is an endofunctor equipped with additional structure, we'd like to forget this structure. We take a monad $(T, \eta, \mu)$ and keep only $T$. But in order to define such a mapping as a functor, we first need to define the category of monads.

\subsection{Category of monads}

The objects in the category of monads $\mathbf{Mon}(\cat C)$ are monads $(T, \eta, \mu)$. We can define an arrow between two monads $(T, \eta, \mu)$ and $(T', \eta', \mu')$ as a natural transformation between the two endofunctors:
\[ \lambda \colon T \to T' \]
However, since monads are endofunctors \emph{with structure}, we want these natural transformations to preserve the structure. Preservation of unit means that the following diagram must commute:
\[
 \begin{tikzcd}
&\text{Id}
 \arrow[ld, "\eta"']
 \arrow[rd, "\eta'"]
 \\
 T
 \arrow[rr, "\lambda"]
 && T'
 \end{tikzcd}
\]
Preservation of multiplication means that the following diagram must commute:
\[
 \begin{tikzcd}
 T \circ T
 \arrow[r, "\lambda \circ \lambda"]
 \arrow[d, "\mu"]
 & T' \circ T'
 \arrow[d, "\mu'"]
 \\
 T
 \arrow[r, "\lambda"]
 & T'
 \end{tikzcd}
\]

Another way of looking at $\mathbf{Mon}(\cat C)$ is that it's a category of monoids in the monoidal category $([\cat C, \cat C], \circ, \text{Id})$. 

\subsection{Free monad}

Now that we have a category of monads, we can define the forgetful functor:
\[ U \colon \mathbf{Mon}(\cat C) \to [\cat C, \cat C] \]
that maps every triple $(T, \eta, \mu)$ to $T$ and every monad morphism to the underlying natural transformation.

We would like a free monad to be generated by a left adjoint to this forgetful functor. The problem is that this left adjoint doesn't always exist. As usual, this is related to size issues: monads tend to blow things up. The bottom line is that free monads exist for some, but not all, endofunctors. Therefore we can't define a free monad through an adjunction. Fortunately, in most cases of interest, a free monad can be defined as a fixed point of an algebra. 

The construction is analogous to how we defined a free monoid as an initial algebra for the list functor:
\begin{haskell}
data ListF a x = NilF | ConsF a x
\end{haskell}
or the more general:
\[ F_a x = I + a \otimes x \]
This time, however, the monoidal category in which a monad is defined as a monoid is the category of endofunctors $([\cat C, \cat C], \circ, \text{Id})$. A free monoid in this category is the initial algebra for the higher order ``list'' functor that maps functors to functors:
\[ \Phi_F G = \text{Id} + F \circ G \]

Here, the \index{coproduct of functors}coproduct of two functors is defined point-wise. On objects:
\[ (F + G) a = F a + G a \]
and on arrows:
\[ (F + G) f = F f + G f \]
(We form a coproduct of two morphisms using the functoriality of the coproduct. We assume that $\cat C$ is co-cartesian, that is all coproducts exist.)

The initial algebra is the (least) fixed point of this operator, or the solution to the recursive equation:
\[ L_F \cong \text{Id} + F \circ L_F \]
This formula establishes a natural isomorphism between two functors. Going from right to left, $\text{Id} + F \circ L_F \to L_F$, we have a mapping out of the sum, which is equivalent to a pair of natural transformations:
\begin{align*}
\text{Id} \to L_F
\\
F \circ L_F \to L_F
\end{align*}

When translating this to Haskell, the components of these transformations become two constructors. We define the following recursive data type parameterized by a functor \hask{f}:
\begin{haskell}
data FreeMonad f a where
   Pure :: a -> FreeMonad f a
   Free :: f (FreeMonad f a) -> FreeMonad f a
\end{haskell}

If we think of the functor \hask{f} as a container of values, the constructor \hask{Free} takes a functorful of \hask{(FreeMonad f a)} and stashes it away. An arbitrary value of the type \hask{FreeMonad f a} is therefore a tree in which every node is a functorful of branches, and each leaf contains a value of the type \hask{a}.

Because this definition is recursive, the \hask{Functor} instance for it is also recursive:
\begin{haskell}
instance Functor f => Functor (FreeMonad f) where
  fmap g (Pure a) = Pure (g a)
  fmap g (Free ffa) = Free (fmap (fmap g) ffa)
\end{haskell}
Here, the outer \hask{fmap} uses the \hask{Functor} instance of \hask{f}, while the inner \hask{(fmap g)} recurses into the branches.

It's easy to show that \hask{FreeMonad} is a \hask{Monad}. The monadic unit \hask{eta} is just a thin encapsulation of the identity functor:
\begin{haskell}
eta :: a -> FreeMonad f a
eta a = Pure a
\end{haskell}

Monadic multiplication, or \hask{join}, is defined recursively:
\begin{haskell}
mu :: Functor f => FreeMonad f (FreeMonad f a) -> FreeMonad f a
mu (Pure fa) = fa
mu (Free ffa) = Free (fmap mu ffa)
\end{haskell}

The \hask{Monad} instance for \hask{FreeMonad f} is therefore:
\begin{haskell}
instance Functor f => Monad (FreeMonad f) where
  return a = eta a
  m >>= k = mu (fmap k m)
\end{haskell}

We can also define bind directly:
\begin{haskell}
  (Pure a)   >>= k = k a
  (Free ffa) >>= k = Free (fmap (>>= k) ffa)
\end{haskell}

A free monad accumulates monadic actions in a tree-like structure without committing to any particular evaluation strategy. This tree can be ``interpreted'' using an algebra. But this time it's an algebra in the category of endofunctors, so its carrier is an endofunctor $G$ and the structure map $\alpha$ is a natural transformation $\Phi_F G \to G$:
\[ \alpha \colon \text{Id} + F \circ G \to G\]
This natural transformation, being a mapping out of a sum, is equivalent to a pair of natural transformations :
\begin{align*}
\lambda &\colon \text{Id} \to G
\\
\rho &\colon F \circ G \to G
\end{align*}

We can translate it to Haskell as a pair of polymorphic functions:
\begin{haskell}
type MAlg f g a = (a -> g a, f (g a) -> g a)
\end{haskell}

Since the free monad is the initial algebra, there is a unique mapping---the catamorphism---from it to any other algebra. Recall how we defined a catamorphism for a regular algebra:
\begin{haskell}
cata :: Functor f => Algebra f a -> Fix f -> a
cata alg = alg . fmap (cata alg) . out
\end{haskell}
The \hask{out} part unwraps the contents of the fixed point. Here we can do this by pattern-matching on the two constructors of the free monad. If it's a leaf, we apply our $\lambda$ to it. If it's a node, we recursively process its contents, and apply our $\rho$ to the result:
\begin{haskell}
mcata :: Functor f => MAlg f g a -> FreeMonad f a -> g a
mcata (l, r) (Pure a) = l a
mcata (l, r) (Free ffa) = 
  r (fmap (mcata (l, r)) ffa)
\end{haskell}

Many tree-like monads are in fact free monads for simple functors.

\begin{exercise}
A (non-empty) rose tree is defined as:
\begin{haskell}
data Rose a = Leaf a | Rose [Rose a]
  deriving Functor
\end{haskell}
Implement conversions back and forth between \hask{Rose a} and  \hask{FreeMonad [] a}.
\end{exercise}

\begin{exercise}
Implement conversions between a binary tree and \hask{FreeMonad Bin a}, where:
\begin{haskell}
data Bin a = Bin a a
\end{haskell}
\end{exercise}

\begin{exercise}
Find a functor whose free monad is equivalent to the list monad \hask{[a]}.
\end{exercise}


\subsection{Stack calculator example}
As an example, let's consider a stack calculator implemented as an embedded domain-specific language, EDSL. We'll use the free monad to accumulate simple commands written in this language. 

The commands are defined by the functor \hask{StackF}. Think of the parameter  \hask{k} as the continuation. 
\begin{haskell}
data StackF k  = Push Int k
               | Top (Int -> k)
               | Pop k            
               | Add k
               deriving Functor
\end{haskell}
For instance, \hask{Push} is supposed to push an integer on the stack and then call the continuation \hask{k}.

The free monad for this functor can be thought of as a tree, with most branches having just one child, thus forming lists. The exception is the \hask{Top} node, which has many children, one per every value of \hask{Int}.

Here's the free monad for this functor:
\begin{haskell}
type FreeStack = FreeMonad StackF
\end{haskell}

In order to create domain-specific programs we'll define a few helper functions. There is a generic one that lifts a functorful of values to a free monad:
\begin{haskell} 
liftF :: (Functor f) => f r -> FreeMonad f r
liftF fr = Free (fmap (Pure) fr)
\end{haskell}
We also need a series of ``smart constructors,'' which are Kleisli arrows for our free monad:
\begin{haskell}
push :: Int -> FreeStack ()
push n = liftF (Push n ())

pop :: FreeStack ()
pop = liftF (Pop ())

top :: FreeStack Int
top = liftF (Top id)

add :: FreeStack ()
add = liftF (Add ())
\end{haskell}

Since a free monad is a monad, we can conveniently combine Kleisli arrows using the \hask{do} notation. For instance, here's a toy program that adds two numbers and returns their sum:
\begin{haskell}
calc :: FreeStack Int
calc = do
  push 3
  push 4
  add
  x <- top
  pop
  return x
\end{haskell}

In order to execute this program, we need to define an algebra whose carrier is an endofunctor. Since we want to implement a stack-based calculator, we'll use a version of the state functor. Its state is a stack---a list of integers. The state functor is defined as a function type; here it's a function that takes a list and returns a new list coupled with the type parameter \hask{k}:
\begin{haskell}
data StackAction k = St ([Int] -> ([Int], k))
  deriving Functor
\end{haskell}

To run the action, we apply the function to the stack:
\begin{haskell}
runAction :: StackAction k -> [Int] -> ([Int], k)
runAction (St act) ns = act ns
\end{haskell}

We define the algebra as a pair of polymorphic functions corresponding to the two constructors of the free monad, \hask{Pure} and \hask{Free}:
\begin{haskell}
runAlg :: MAlg StackF StackAction a
runAlg = (stop, go)
\end{haskell}
The first function terminates the execution of the program and returns a value:
\begin{haskell}
stop :: a -> StackAction a
stop a = St (\xs -> (xs, a))
\end{haskell}
The second function pattern matches on the type of the command. Each command carries with it a continuation. This continuation has to be run with a (potentially modified) stack. Each command modifies the stack in a different way:
\begin{haskell}
go :: StackF (StackAction k) -> StackAction k
go (Pop k)    = St (\ns -> runAction k (tail ns))
go (Top ik)   = St (\ns -> runAction (ik (head ns)) ns)
go (Push n k) = St (\ns -> runAction k (n: ns))
go (Add k)    = St (\ns -> runAction k 
                   ((head ns + head (tail ns)): tail (tail ns)))
\end{haskell}
For instance, \hask{Pop} discards the top of the stack. \hask{Top} takes an integer from top of the stack and uses it to pick the branch to be executed. It does it by applying the function \hask{ik} to the integer. \hask{Add} adds the two numbers at the top of the stack and pushes the result. 

Notice that the algebra we have defined does not involve recursion. Separating recursion from the actions is one of the advantages of the free monad approach. The recursion is instead encoded once and for all in the catamorphism. 

Here's the function that can be used to run our toy program:
\begin{haskell}
run :: FreeMonad StackF k -> ([Int], k)
run prog = runAction (mcata runAlg prog) [] 
\end{haskell}

Obviously, the use of partial functions \hask{head} and \hask{tail} makes our interpreter fragile. A badly formed program will cause a runtime error. A more robust implementation would use an algebra that allows for error propagation.

The other advantage of using free monads is that the same program may be interpreted using different algebras.

\begin{exercise}
Implement a ``pretty printer'' that displays the program constructed using our free monad. Hint: Implement the algebra that uses the \hask{Const} functor as the carrier:
\begin{haskell}
showAlg :: MAlg StackF (Const String) a
\end{haskell}
\end{exercise}

\section{Monoidal Functors}

We've seen several examples of monoidal cateogries. Such categories are equipped with some kind of binary operation, e.g., a cartesian product, a sum, composition (in the category of endofunctors), etc. They also have a special object that serves as the unit with respect to that binary operation. Unit and associativity laws are satisfied either on the nose (in strict monoidal categories) or up to isomorphism.

Every time we have more than one instance of some structure, we may ask ourselves the question: is there a whole category of such things? In this case: do monoidal categories form their own category? For this to work we would have to define arrows between monoidal categories.

A \emph{monoidal functor} $F$ from a monoidal category $(\mathcal{C}, \otimes, i)$ to another monoidal category $(\mathcal{D}, \oplus, j)$ maps tensor product to tensor product and unit to unit---all up to isomorphism:
\begin{align*}
F a \oplus F b &\cong F (a \otimes b) \\
j &\cong F i 
\end{align*}
Here, on the left-hand side we have the tensor product and the unit in the target category, and on the right their counterparts in the source category. 

If the two monoidal categories in question are not strict, that is the unit and associativity laws are satisfied only up to isomorphism, there are additional coherency conditions that ensure that unitors are mapped to unitors and associators are mapped to associators.

The category of monoidal categories with monoidal functors as arrows is called $\mathbf{MonCat}$. In fact it's a 2-category, since one can define structure-preserving natural transformations between monoidal functors.

\subsection{Lax monoidal functors}

One of the perks of monoidal categories is that they allow us to define monoids. You can easily convince yourself that monoidal functors map monoids to monoids. It turns out that you don't need the full power of monoidal functors to accomplish that. Let's consider what the minimal requirements are  for a functor to map monoids to monoids. 

Let's start with a monoid $(m, \mu, \eta)$ in the monoidal category $(\mathcal{C}, \otimes, i)$. Consider a functor $F$ that maps $m$ to $F m$. We want $F m$ to be a monoid in the target monoidal category $(\mathcal{D}, \oplus, j)$. For that we need to find two mappings:
\begin{align*}
\eta' &\colon j \to F m \\
 \mu' &\colon F m \oplus F m \to F m 
\end{align*}
satisfying monoidal laws.

Since $m$ is a monoid, we do have at our disposal the liftings of the original mappings:
\begin{align*}
 F \eta &\colon F i \to F m \\
 F \mu &\colon F (m \otimes m) \to F m
\end{align*}

What we are missing, in order to implement $\eta'$ and $\mu'$, are two additional arrows:
\begin{align*}
j &\to F i\\
 F m \oplus F m &\to F (m \otimes m)
 \end{align*}
A monoidal functor would provide such arrows. However, for what we're trying it accomplish, we don't need these arrows to be invertible. 

A \emph{lax monoidal functor} is a functor equipped with a morphism $\phi_i$ and a natural transformation $\phi_{ab}$:
\begin{align*}
\phi_i &\colon j \to F i \\
\phi_{a b} &\colon F a \oplus F b \to F (a \otimes b)
\end{align*}
satisfying the appropriate unitality and associativity conditions.

Such a functor maps a monoid $(m, \mu, \eta)$ to a monoid $(F m, \mu', \eta')$ with:
\begin{align*}
\eta' &= F \eta \circ \phi_i \\
\mu' &= F \mu \circ \phi_{a b}
\end{align*}

The simplest example of a lax monoidal functor is an endofunctor that preserves the usual cartesian product. We can define it in Haskell as a typeclass:

\begin{haskell}
class Monoidal f where
  unit  :: f ()
  (>*<) :: f a -> f b -> f (a, b)
\end{haskell}
Corresponding to $\phi_{a b}$ we have an infix operator which, according to Haskell conventions, is written in its curried form.

\begin{exercise}
Implement the \hask{Monoidal} instance for the list functor.
\end{exercise}

\subsection{Functorial strength}

There is another way a functor may interact with monoidal structure, one that hides in plain sight when we do programming. We take it for granted that functions have access to the environment. Such functions are called closures. 

For instance, here's a function that captures a variable \hask{a} from the environment and pairs it with its argument:
\begin{haskell}
\x -> (a, x)
\end{haskell}
This definition makes no sense in isolation, but it does when the environment contains the variable \hask{a}, e.g.,
\begin{haskell}
pairWith :: Int -> (String -> (Int, String))
pairWith a = \x -> (a, x)
\end{haskell}
The function returned by calling \hask{pairWith 5} ``closes over'' the 5 from its environment.

Now consider the following modification, which returns a singleton list that contains the closure:
\begin{haskell}
pairWith' :: Int -> [String -> (Int, String)]
pairWith' a = [\x -> (a, x)]
\end{haskell}
As a programmer you'd be very surprised if this didn't work. But what we do here is highly nontrivial: we are smuggling the environment \emph{under} the list functor. According to our model of lambda calculus, a closure is a morphism from the product of the environment and the function argument. Here the lambda, which is really a function of \hask{(Int, String)}, is defined inside a list functor, but it captures the value \hask{a} that is defined \emph{outside} the list.

The property that lets us smuggle the environment under a functor is called \index{strength, functorial}\emph{functorial strength} or \emph{tensorial strength} and can be implemented in Haskell as:
\begin{haskell}
strength :: Functor f => (e, f a) -> f (e, a)
strength (e, as) = fmap (e, ) as
\end{haskell}
The notation \hask{(e, )} is called a \index{tuple section}\emph{tuple section} and is equivalent to the partial application of the pair constructor: \hask{(,) e}.

In category theory, strength for an endofunctor $F$ is defined as a natural transformation that smuggles a tensor product into a functor:
\[ \sigma \colon a \otimes F(b) \to F (a \otimes b) \]
There are some additional conditions which ensure that it works nicely with the unitors and the associator of the monoidal category in question.

The fact that we were able to implement \hask{strength} for an arbitrary functor means that, in Haskell, every functor is strong. This is the reason why we don't have to worry about accessing the environment from inside a functor. 

Even more importantly, every monad in Haskell is strong by virtue of being a functor. This is also why every monad is automatically \hask{Monoidal}. 
\begin{haskell}
instance Monad m => Monoidal m where
  unit = return ()
  ma >*< mb = do
    a <- ma
    b <- mb
    return (a, b)
\end{haskell}
If you desugar this code to use monadic bind and lambdas, you'll notice that the final \hask{return} needs access to both \hask{a} and \hask{b}, which are defined in outer environments. This would be impossible without a monad being strong.

In category theory, though, not every endofunctor in a monoidal category is strong. For now, the magic incantation is that the category we're working with is self-enriched, and every endofunctor defined in Haskell is enriched. We'll come back to it when we talk about enriched categories. In Haskell, strength boils down to the fact that we can always \hask{fmap} a partially applied pair constructor \hask{(a, )}.

\subsection{Applicative functors}

In programming, the idea of applicative functors arose from the following question: A functor lets us lift a function of one variable. How can we lift a function of two or more variables? 

By analogy with \hask{fmap}, we'd like to have a function:
\begin{haskell}
liftA2 :: (a -> b -> c) -> f a -> f b -> f c
\end{haskell}

A function of two arguments---here, in its curried form---is a function of one argument returning a function. So, assuming that \hask{f} is a functor, we can \hask{fmap} the first argument of \hask{liftA2}, which has the type:
\begin{haskell}
a -> (b -> c)
\end{haskell}
over the second argument \hask{(f a)} to get:
\begin{haskell}
f (b -> c)
\end{haskell}
The problem is, we don't know how to apply \hask{f (b -> c)} to the remaining argument \hask{(f b)}. 

The class of functors that let us do that is called \hask{Applicative}. It turns out that, once we know how to lift a two-argument function, we can lift functions of any number of arguments, except zero. A zero-argument function is just a value, so lifting it means implementing a function:
\begin{haskell}
pure :: a -> f a
\end{haskell}
Here's the Haskell definition:
\begin{haskell}
class Functor f => Applicative f where
    pure  :: a -> f a
    (<*>) :: f (a -> b) -> f a -> f b
\end{haskell}
The application of a functorful of functions to a functorful of arguments is defined as an infix operator \hask{<*>} that is customarily called ``splat.''

There is also an infix version of \hask{fmap}:
\begin{haskell}
(<$>) :: Functor f => (a -> b) -> f a -> f b
\end{haskell}
which can be used in this terse implementation of \hask{liftA2}:
\begin{haskell}
liftA2 :: Applicative f => (a -> b -> c) -> f a -> f b -> f c
liftA2 g as bs = g <$> as <*> bs
\end{haskell}
Both operators bind to the left, which makes this syntax mimic regular function application.

An applicative functor must also satisfy a set of laws:
\begin{haskell}
pure id <*> v = v                            -- Identity
pure f <*> pure x = pure (f x)               -- Homomorphism
u <*> pure y = pure ($ y) <*> u              -- Interchange
pure (.) <*> u <*> v <*> w = u <*> (v <*> w) -- Composition
\end{haskell}

\begin{exercise}
Implement $\emph{\hask{liftA3}}$, a function that lifts a 3-argument function using an applicative functor.
\end{exercise}

\subsection{Closed functors}
If you squint at the definition of the splat operator:
\begin{haskell}
(<*>) :: f (a -> b) -> (f a -> f b)
\end{haskell}
you may see it as mapping function objects to function objects. 

This becomes clearer if you consider a functor between two categories, both of them closed. You may start with a function object $b^a$ in the source category and apply the functor $F$ to it:
\[ F (b^a) \]
Alternatively, you may map the two objects $a$ and $b$ and construct a function object between them in the target category:
\[ (F b)^{F a} \]
If we demand that the two ways be isomorphic, we get a definition of a strict \emph{closed functor}. But, as was the case with monoidal functors, we are more interested in the lax version, which is equipped with a one-way natural transformation:
\[ F (b^a) \to (F b)^{F a} \]
If $F$ is an endofunctor, this translates directly into the definition of the splat operator. 

The full definition of a lax closed functor includes the mapping of the monoidal unit and some coherence conditions. All said, an applicative functor is a lax closed functor.

In a closed cartesian category, the exponential is related to the cartesian product through the currying adjunction. It's no surprise then, that in such a category lax monoidal and lax closed (applicative) endofunctors are the same. 

We can easily express this in Haskell:
\begin{haskell}
instance (Functor f, Monoidal f) => Applicative f where
  pure a = fmap (const a) unit
  fs <*> as = fmap apply (fs >*< as)
\end{haskell}
where \hask{const} is a function that ignores its second argument:
\begin{haskell}
const :: a -> b -> a
const a b = a
\end{haskell}
and \hask{apply} is the uncurried function application:
\begin{haskell}
apply :: (a -> b, a) -> b
apply (f, a) = f a
\end{haskell}
And the other way around we have:
\begin{haskell}
instance Applicative f => Monoidal f where
  unit = pure ()
  as >*< bs = (,) <$> as <*> bs
\end{haskell}
In the latter, we used the pair constructor \hask{(,)} as a two-argument function.

\subsection{Monads and applicatives}

Since in a cartesian closed category every monad\footnote{Again, the correct incantation is ``every enriched monad''} is lax monoidal, it is automatically applicative. We can show it directly by implementing \hask{ap}, which has the same type signature as the splat operator:
\begin{haskell}
ap :: (Monad m) => m (a -> b) -> m a -> m b
ap fs as = do 
    f <- fs
    a <- as
    return (f a) 
\end{haskell}

This connection is expressed in the Haskell definition of a \hask{Monad} by having \hask{Applicative} as its superclass:
\begin{haskell}
class Applicative m => Monad m where
    (>>=)       :: forall a b. m a -> (a -> m b) -> m b
    return      :: a -> m a
    return      = pure
\end{haskell}
Notice the default implementation of \hask{return} as \hask{pure}. 

The converse is not true: not every \hask{Applicative} is a \hask{Monad}. The standard counterexample is the \hask{Applicative} instance for a list functor that uses zipping:
\begin{haskell}
instance Applicative [] where
  pure = repeat
  fs <*> as = zipWith apply fs as
\end{haskell}
Of course, the list functor is also a monad, so there is another \hask{Applicative} instance based on that. Its splat operator applies every function to every argument.

In programming, monad is more powerful than applicative. That's because monadic code lets you examine the contents of a monadic value and branch depending on it. This is true even for the \hask{IO} monad which otherwise provides no means of extracting the value. In this example we are branching on the contents of an \hask{IO} object:
\begin{haskell}
main :: IO ()
main = do
  s <- getLine
  if s == "yes"
  then putStrLn "Thank you!"
  else putStrLn "Next time."
\end{haskell}
Of course, the inspection of the value is postponed until the runtime interpreter of \hask{IO} gets hold of this code. 

Applicative composition using the splat operator doesn't allow for one part of the computation to inspect the result of the other. This a limitation that can be turned into an advantage. The absence of dependencies makes it possible to run the computations in parallel.  Haskell's parallel libraries use applicative programming extensively.

On the other hand, monads let us use the very convenient \hask{do} syntax, which is arguably more readable than the applicative syntax. Fortunately, there is a language extension \hask{ApplicativeDo}, which instructs the compiler to selectively use applicative constructs in interpreting \hask{do} blocks, whenever there are no dependencies.

\begin{exercise}
Verify \hask{Applicative} laws for the zip instance of the list functor.
\end{exercise}




\end{document}