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

\lettrine[lhang=0.17]{N}{ow that we have covered} monads, we can reap the benefits of duality and
get comonads for free simply by reversing the arrows and working in the
opposite category.

Recall that, at the most basic level, monads are about composing Kleisli
arrows:

\src{snippet01}
where \code{m} is a functor that is a monad. If we use the letter
\code{w} (upside down \code{m}) for the comonad, we can define
co-Kleisli arrows as morphism of the type:

\src{snippet02}
The analog of the fish operator for co-Kleisli arrows is defined as:

\src{snippet03}
For co-Kleisli arrows to form a category we also have to have an
identity co-Kleisli arrow, which is called \code{extract}:

\src{snippet04}
This is the dual of \code{return}. We also have to impose the laws of
associativity as well as left- and right-identity. Putting it all
together, we could define a comonad in Haskell as:

\src{snippet05}
In practice, we use slightly different primitives, as we'll see shortly.

The question is, what's the use for comonads in programming?

\section{Programming with Comonads}

Let's compare the monad with the comonad. A monad provides a way of
putting a value in a container using \code{return}. It doesn't give
you access to a value or values stored inside. Of course, data
structures that implement monads might provide access to their contents,
but that's considered a bonus. There is no common interface for
extracting values from a monad. And we've seen the example of the
\code{IO} monad that prides itself in never exposing its contents.

A comonad, on the other hand, provides the means of extracting a single
value from it. It does not give the means to insert values. So if you
want to think of a comonad as a container, it always comes pre-filled
with contents, and it lets you peek at it.

Just as a Kleisli arrow takes a value and produces some embellished
result --- it embellishes it with context --- a co-Kleisli arrow takes a
value together with a whole context and produces a result. It's an
embodiment of \newterm{contextual computation}.

\section{The Product Comonad}

Remember the reader monad? We introduced it to tackle the problem of
implementing computations that need access to some read-only environment
\code{e}. Such computations can be represented as pure functions of
the form:

\src{snippet06}
We used currying to turn them into Kleisli arrows:

\src{snippet07}
But notice that these functions already have the form of co-Kleisli
arrows. Let's massage their arguments into the more convenient functor
form:

\src{snippet08}
We can easily define the composition operator by making the same
environment available to the arrows that we are composing:

\src{snippet09}
The implementation of \code{extract} simply ignores the environment:

\src{snippet10}
Not surprisingly, the product comonad can be used to perform exactly the
same computations as the reader monad. In a way, the comonadic
implementation of the environment is more natural --- it follows the
spirit of ``computation in context.'' On the other hand, monads come
with the convenient syntactic sugar of the \code{do} notation.

The connection between the reader monad and the product comonad goes
deeper, having to do with the fact that the reader functor is the right
adjoint of the product functor. In general, though, comonads cover
different notions of computation than monads. We'll see more examples
later.

It's easy to generalize the \code{Product} comonad to arbitrary
product types including tuples and records.

\section{Dissecting the Composition}

Continuing the process of dualization, we could go ahead and dualize
monadic bind and join. Alternatively, we can repeat the process we used
with monads, where we studied the anatomy of the fish operator. This
approach seems more enlightening.

The starting point is the realization that the composition operator must
produce a co-Kleisli arrow that takes \code{w a} and produces a
\code{c}. The only way to produce a \code{c} is to apply the second
function to an argument of the type \code{w b}:

\src{snippet11}
But how can we produce a value of type \code{w b} that could be fed
to \code{g}? We have at our disposal the argument of type
\code{w a} and the function \code{f :: w a -> b}.
The solution is to define the dual of bind, which is called extend:

\src{snippet12}
Using \code{extend} we can implement composition:

\src{snippet13}
Can we next dissect \code{extend}? You might be tempted to say, why
not just apply the function \code{w a -> b} to the
argument \code{w a}, but then you quickly realize that you'd have no
way of converting the resulting \code{b} to \code{w b}. Remember,
the comonad provides no means of lifting values. At this point, in the
analogous construction for monads, we used \code{fmap}. The only way
we could use \code{fmap} here would be if we had something of the type
\code{w (w a)} at our disposal. If we could only turn \code{w a}
into\\ \code{w (w a)}. And, conveniently, that would be exactly the
dual of \code{join}. We call it \code{duplicate}:

\src{snippet14}
So, just like with the definitions of the monad, we have three
equivalent definitions of the comonad: using co-Kleisli arrows,
\code{extend}, or \code{duplicate}. Here's the Haskell definition
taken directly from\\ \code{Control.Comonad} library:

\src{snippet15}
Provided are the default implementations of \code{extend} in terms of
\code{duplicate} and vice versa, so you only need to override one of
them.

The intuition behind these functions is based on the idea that, in
general, a comonad can be thought of as a container filled with values
of type \code{a} (the product comonad was a special case of just one
value). There is a notion of the ``current'' value, one that's easily
accessible through \code{extract}. A co-Kleisli arrow performs some
computation that is focused on the current value, but it has access to
all the surrounding values. Think of the Conway's game of life. Each
cell contains a value (usually just \code{True} or \code{False}). A
comonad corresponding to the game of life would be a grid of cells
focused on the ``current'' cell.

So what does \code{duplicate} do? It takes a comonadic container
\code{w a} and produces a container of containers \code{w (w a)}.
The idea is that each of these containers is focused on a different
\code{a} inside \code{w a}. In the game of life, you would get a
grid of grids, each cell of the outer grid containing an inner grid
that's focused on a different cell.

Now look at \code{extend}. It takes a co-Kleisli arrow and a comonadic
container \code{w a} filled with \code{a}s. It applies the
computation to all of these \code{a}s, replacing them with
\code{b}s. The result is a comonadic container filled with
\code{b}s. \code{extend} does it by shifting the focus from one
\code{a} to another and applying the co-Kleisli arrow to each of them
in turn. In the game of life, the co-Kleisli arrow would calculate the
new state of the current cell. To do that, it would look at its context
--- presumably its nearest neighbors. The default implementation of
\code{extend} illustrates this process. First we call
\code{duplicate} to produce all possible foci and then we apply
\code{f} to each of them.

\section{The Stream Comonad}

This process of shifting the focus from one element of the container to
another is best illustrated with the example of an infinite stream. Such
a stream is just like a list, except that it doesn't have the empty
constructor:

\src{snippet16}
It's trivially a \code{Functor}:

\src{snippet17}
The focus of a stream is its first element, so here's the implementation
of \code{extract}:

\src{snippet18}
\code{duplicate} produces a stream of streams, each focused on a
different element.

\src{snippet19}
The first element is the original stream, the second element is the tail
of the original stream, the third element is its tail, and so on, ad
infinitum.

Here's the complete instance:

\src{snippet20}
This is a very functional way of looking at streams. In an imperative
language, we would probably start with a method \code{advance} that
shifts the stream by one position. Here, \code{duplicate} produces all
shifted streams in one fell swoop. Haskell's laziness makes this
possible and even desirable. Of course, to make a \code{Stream}
practical, we would also implement the analog of \code{advance}:

\src{snippet21}
but it's never part of the comonadic interface.

If you had any experience with digital signal processing, you'll see
immediately that a co-Kleisli arrow for a stream is just a digital
filter, and \code{extend} produces a filtered stream.

As a simple example, let's implement the moving average filter. Here's a
function that sums \code{n} elements of a stream:

\src{snippet22}
Here's the function that calculates the average of the first \code{n}
elements of the stream:

\src{snippet23}
Partially applied \code{average n} is a co-Kleisli arrow, so we can
\code{extend} it over the whole stream:

\src{snippet24}
The result is the stream of running averages.

A stream is an example of a unidirectional, one-dimensional comonad. It
can be easily made bidirectional or extended to two or more dimensions.

\section{Comonad Categorically}

Defining a comonad in category theory is a straightforward exercise in
duality. As with the monad, we start with an endofunctor \code{T}. The
two natural transformations, $\eta$ and $\mu$, that define the monad are simply
reversed for the comonad:
\begin{align*}
  \varepsilon & \Colon T \to I   \\
  \delta      & \Colon T \to T^2
\end{align*}
The components of these transformations correspond to \code{extract}
and \code{duplicate}. Comonad laws are the mirror image of monad laws.
No big surprise here.

Then there is the derivation of the monad from an adjunction. Duality
reverses an adjunction: the left adjoint becomes the right adjoint and
vice versa. And, since the composition $R \circ L$ defines a monad,
$L \circ R$ must define a comonad. The counit of the adjunction:
\[\varepsilon \Colon L \circ R \to I\]
is indeed the same $\varepsilon$ that we see in the definition of the comonad ---
or, in components, as Haskell's \code{extract}. We can also use the
unit of the adjunction:
\[\eta \Colon I \to R \circ L\]
to insert an $R \circ L$ in the middle of $L \circ R$ and
produce $L \circ R \circ L \circ R$. Making $T^2$ from $T$
defines the $\delta$, and that completes the definition of the comonad.

We've also seen that the monad is a monoid. The dual of this statement
would require the use of a comonoid, so what's a comonoid? The original
definition of a monoid as a single-object category doesn't dualize to
anything interesting. When you reverse the direction of all
endomorphisms, you get another monoid. Recall, however, that in our
approach to a monad, we used a more general definition of a monoid as an
object in a monoidal category. The construction was based on two
morphisms:
\begin{align*}
  \mu  & \Colon m \otimes m \to m \\
  \eta & \Colon i \to m
\end{align*}
The reversal of these morphisms produces a comonoid in a monoidal
category:
\begin{align*}
  \delta      & \Colon m \to m \otimes m \\
  \varepsilon & \Colon m \to i
\end{align*}
One can write a definition of a comonoid in Haskell:

\src{snippet25}
but it is rather trivial. Obviously \code{destroy} ignores its
argument.

\src{snippet26}
\code{split} is just a pair of functions:

\src{snippet27}
Now consider comonoid laws that are dual to the monoid unit laws.

\src{snippet28}
Here, \code{lambda} and \code{rho} are the left and right unitors,
respectively (see the definition of
\hyperref[monads-categorically]{monoidal
  categories}). Plugging in the definitions, we get:

\src{snippet29}
which proves that \code{g = id}. Similarly, the second law expands
to \code{f = id}. In conclusion:

\src{snippet30}
which shows that in Haskell (and, in general, in the category
$\Set$) every object is a trivial comonoid.

Fortunately there are other more interesting monoidal categories in
which to define comonoids. One of them is the category of endofunctors.
And it turns out that, just like the monad is a monoid in the category
of endofunctors,

\begin{quote}
  The comonad is a comonoid in the category of endofunctors.
\end{quote}

\section{The Store Comonad}

Another important example of a comonad is the dual of the state monad.
It's called the costate comonad or, alternatively, the store comonad.

We've seen before that the state monad is generated by the adjunction
that defines the exponentials:
\begin{align*}
  L z & = z\times{}s      \\
  R a & = s \Rightarrow a
\end{align*}
We'll use the same adjunction to define the costate comonad. A comonad
is defined by the composition $L \circ R$:
\[L (R a) = (s \Rightarrow a)\times{}s\]
Translating this to Haskell, we start with the adjunction between the
\code{Product} functor on the left and the \code{Reader} functor or the
right. Composing \code{Product} after \code{Reader} is equivalent to
the following definition:

\src{snippet31}
The counit of the adjunction taken at the object $a$ is the
morphism:
\[\varepsilon_a \Colon ((s \Rightarrow a)\times{}s) \to a\]
or, in Haskell notation:

\src{snippet32}
This becomes our \code{extract}:

\src{snippet33}
The unit of the adjunction:

\src{snippet34}
can be rewritten as partially applied data constructor:

\src{snippet35}
We construct $\delta$, or \code{duplicate}, as the horizontal composition:
\begin{align*}
  \delta & \Colon L \circ R \to L \circ R \circ L \circ R \\
  \delta & = L \circ \eta \circ R
\end{align*}
We have to sneak $\eta$ through the leftmost $L$, which is the
\code{Product} functor. It means acting with $\eta$, or \code{Store f}, on
the left component of the pair (that's what \code{fmap} for
\code{Product} would do). We get:

\src{snippet36}
(Remember that, in the formula for $\delta$, $L$ and $R$ stand
for identity natural transformations whose components are identity
morphisms.)

Here's the complete definition of the \code{Store} comonad:

\src{snippet37}
You may think of the \code{Reader} part of \code{Store} as a
generalized container of \code{a}s that are keyed using elements of
the type \code{s}. For instance, if \code{s} is \code{Int},
\code{Reader Int a} is an infinite bidirectional stream of
\code{a}s. \code{Store} pairs this container with a value of the key
type. For instance, \code{Reader Int a} is paired with an
\code{Int}. In this case, \code{extract} uses this integer to index
into the infinite stream. You may think of the second component of
\code{Store} as the current position.

Continuing with this example, \code{duplicate} creates a new infinite
stream indexed by an \code{Int}. This stream contains streams as its
elements. In particular, at the current position, it contains the
original stream. But if you use some other \code{Int} (positive or
negative) as the key, you'd obtain a shifted stream positioned at that
new index.

In general, you can convince yourself that when \code{extract} acts on
the \code{duplicate}d \code{Store} it produces the original
\code{Store} (in fact, the identity law for the comonad states that
\code{extract . duplicate = id}).

The \code{Store} comonad plays an important role as the theoretical
basis for the \code{Lens} library. Conceptually, the
\code{Store s a} comonad encapsulates the idea of ``focusing'' (like
a lens) on a particular substructure of the data type \code{a} using
the type \code{s} as an index. In particular, a function of the type:

\src{snippet38}
is equivalent to a pair of functions:

\src{snippet39}
If \code{a} is a product type, \code{set} could be implemented as
setting the field of type \code{s} inside of \code{a} while
returning the modified version of \code{a}. Similarly, \code{get}
could be implemented to read the value of the \code{s} field from
\code{a}. We'll explore these ideas more in the next section.

\section{Challenges}

\begin{enumerate}
  \tightlist
  \item
        Implement the Conway's Game of Life using the \code{Store} comonad.
        Hint: What type do you pick for \code{s}?
\end{enumerate}
