Comonads – Monads Upside Down

Over many previous posts, we have investigated various aspects of monads. To discuss monad theory properly, it is often useful to consider their interaction with the dual notion, comonads. Laying the foundations for such discussions is the aim of the current post. Although comonads can be seen as a special case of monads, that doesn’t really capture how they feel in practice. Our objectives for the current post are:

  1. To introduce several examples of comonads in the familiar setting of sets and functions.
  2. To describe some different ways in which comonad are “monads, but upside down”.

Although comonads are formally dual to monads, and therefore “just the same thing”, they are often seen as rather mysterious. A quick experiment on your favourite search engine will find a lot less discussion of comonads than monads for example. One might be tempted to speculate as to why that is, historical mathematical bias, something fundamental about the nature of mathematics,..? We shall avoid such philosophical musing, and concentrating on trying to build up some familiarity.

Introducing Comonads

A comonad on a category \mathcal{C} consists of:

  1. An endofunctor \mathbb{D} : \mathcal{C} \rightarrow \mathcal{C}.
  2. A counit natural transformation \epsilon : \mathbb{D} \Rightarrow \mathsf{Id}_{\mathcal{C}}.
  3. A comultiplication natural transformation \delta : \mathbb{D} \Rightarrow \mathbb{D} \circ \mathbb{D}.

This data must satisfy the following counitality and coassociativity equations:

(\epsilon \circ \mathbb{D}) \cdot \delta = \mathsf{Id}_{\mathbb{D}} = (\mathbb{D} \circ \epsilon) \cdot \delta \qquad (\mathbb{D} \circ \delta) \cdot \delta = (\delta \circ \mathbb{D}) \cdot \delta

The terms counit and comultiplication drop heavy hints that comonads are a dual notion to monads. We will return to this point shortly. First we plough on, with lots of examples.

Example: Lists are a standard example for monads. For comonads, the non-empty lists provide a similarly canonical example. Let \mathbb{L}^+ be the endofunctor that sends a set to its collection of non-empty lists. This functor is a comonad, with counit the function that returns the tail of the list, and comultiplication mapping a list to its list of prefixes, for example:

\delta([1,2,3]) = [[1],[1,2],[1,2,3]]

Unlike the list monad, we can bound the length of our lists to form another comonad \mathbb{L}^+_k of non-empty lists of length at most k \in \mathbb{N} elements.

As with monads, it’s worth considering some instructive degenerate examples. The first one hopefully wont be a big shock.

Example: For any category \mathcal{C}, the identity functor \mathsf{Id}_{\mathcal{C}} is a comonad, with the counit and comultiplication both being identity morphisms.

The previous example gives a trivial answer to a natural question. It is possible for an endofunctor to carry the structure of both a monad and a comonad. In fact, so does the endofunctor \mathbb{L}^+, which is perhaps a bit more interesting.

The next example is the comonadic analog of the inconsistent monads, in that it provides a healthy source of counterexamples.

Example: For any category with an initial object, the constant functor mapping to the initial object is a comonad. The counit and comultiplication are the unique morphisms:

0 \xrightarrow{\epsilon_X} X \qquad 0 \xrightarrow{\delta_X} 0

We might think of this as the overspecified comonad.

The next few of examples are comonadic relatives of the writer, reader and state monads we’ve encountered previously.

Example: For a fixed set E, the endofunctor (-) \times E is a comonad, with counit:

\epsilon((x,e)) = x

and comultiplication:

\delta((x,e)) = ((x,e),e)

Together these form a comonad, which we shall refer to as the reader comonad. Despite the name, this comonad is dual to the exception monad. Computationally, we can think of a map X \times E \rightarrow Y as a function from X to Y that can depend on some additional data it reads from the environment E.

Recall that for an adjunction L \dashv R, the composition R \circ L is a monad. Dually, the composite L \circ R is a comonad. The following is a standard example of this phenomenon.

Example: For a fixed object S, in a Cartesian closed category we have adjunction:

(-) \times S \dashv S \Rightarrow (-)

Therefore, the functor:

X \mapsto (S \Rightarrow X) \times S

is a comonad. Computationally, if we think of S as a collection of states, morphisms:

(S \Rightarrow X) \times S \rightarrow Y

bijectively correspond to morphisms:

(S \Rightarrow X) \rightarrow (S \Rightarrow Y)

which transforms state dependent values of type X to state dependent elements of type Y. This comonad is often referred to as the costate comonad.

Example: Given a monoid (M, \times,1), the functor M \Rightarrow (-) is a comonad, with counit:

\epsilon(f) = f(1)

and comultiplication:

\delta(f)(m)(n) = f(m \times n)

This is sometimes referred to as the exponent comonad.

A special case of this construction is an important example in itself. Consider the exponent comonad on the monoid of additive natural numbers (\mathbb{N},+,0). We can think of an element of \mathbb{N} \Rightarrow X as an infinite lists, or stream, of values from X:

[f(0),f(1),f(2),\ldots]

The counit returns the first element of the stream, and the comultiplication gives the stream of tails, as follows:

\delta([1,2,3,\ldots]) = [[1,2,3,\ldots],[2,3,4,\ldots],[3,4,5,\ldots],\ldots]

This construction is referred to as the stream comonad.

We now move onto some strategies to systematically construct simple comonads.

Example: Given a non-empty list, we can mark a focus position in it, written as follows:

[1,2,\underline{3},4]

There is then a natural counit operation, which returns the focal element:

\epsilon([1,2,\underline{3},4]) = 3

There is also a comultiplication operation, which acts as follows on our example list:

\delta([1,2,\underline{3},4) = [[\underline{1},2,3,4],[1,\underline{2},3,4],\underline{[1,2,\underline{3},4]},[1,2,3,\underline{4}]]

The resulting comonad is the zipper comonad for non-empty lists.

There was nothing special about non-empty lists in the previous example.

Example: Given a pair of values, we can mark a focus position in it, for example:

(\underline{1},2)

As in the previous example, there is an obvious counit returning the focus:

\epsilon((\underline{1},2)) = 1

There is also a comultiplication, analogously to the previous example, with action:

\delta((\underline{1},2)) = (\underline{(\underline{1},2)},(1,\underline{2}))

The resulting comonad is the zipper comonad for pairs.

This pattern of collections of data with a focus can be repeated in great generality to yield many further examples of comonads.

Another example of a similar kind is the following:

Example: Again, we consider the endofunctor \mathbb{L}^+. We define our counit to return the tail element of lists. We do something slightly more interesting with the comultiplication, which cycles through the list, as in the following example:

\delta([1,2,3]) = [[2,3,1],[3,1,2],[1,2,3]]

This forms what is know as the circular non-empty list comonad.

The previous example answers another natural question. It is possible for a given endofunctor to carry two different comonad structures. In fact, even if we fix the counit, this remains so.

The zipper comonads, the non-empty list comonad, the circular non-empty list comonad, and several other examples we’ve seen, are all built up in a similar manner:

  1. There are certain shapes of collections of data types, such as pairs, lists of length 1,2,3, and so on.
  2. Each shape has a collection of positions in which data is stored. For example, the first and second elements of a pair.
  3. There is a focus position. In the zippers this was given explicitly, in the non-empty list examples, it was the tail element.
  4. There is rather general notion of “sub-shape” at a given position.

The first two aspects allow us to describe an endofunctor, mapping a set X to the collection values of each shape of a given datatypes, with data at each position taken from X. The focus element allow us to build a counit, and the notion of sub-shape is key to describing a comultiplication. Of course, we are only giving imprecise intuitions here, to make all this mathematically precise, we need to introduce more technical machinery. Specifically, we need the framework of (directed) containers, which we may return to in a later post.

It’s all just monads upside-down!

We now return to the question of how monads are related to comonads, which we shall look at from a few different perspectives.

Given a fixed category \mathcal{C}, we can consider the monads on the opposite category \mathcal{C}^{op}. These consist of:

  1. An endofunctor \mathbb{M} on \mathcal{C}^{op}, which is the same thing as an endofunctor \mathbb{D} on \mathcal{C}. The presence of the “op” doesn’t really make a great deal of different here, unlike for the natural transformations.
  2. A unit natural transformation \eta : \mathsf{Id}_{\mathcal{C}^{op}} \Rightarrow \mathbb{M}. Due to the reversal of the direction of morphisms in the opposite category, this is the same thing as a natural transformation \epsilon : \mathsf{Id}_{\mathcal{C}} \Rightarrow \mathbb{D}.
  3. A multiplication natural transformation \mu : \mathbb{M} \circ \mathbb{M} \Rightarrow \mathbb{M}. This is the same thing as a natural transformation \delta : \mathbb{D} \Rightarrow \mathbb{D} \circ \mathbb{D}.

The monad axioms satisfied by \eta and \mu are the same thing as requiring the comonad equations for the corresponding \epsilon and \delta. That is:

A comonad on a category \mathcal{C} is the same thing as a monad on the opposite category \mathcal{C}^{op}.

This is all very nice, but in previous posts, we generalised monads to 2-categories and bicategories. The previous explanation does really help us understand comonads in terms of monads in that setting, as it is very specifically tied to monads on categories. We need to look at things in a slightly different way.

Given a 2-category or bicategory \mathbf{K}, there are a few different ways we can produce new bicategories, by flipping the directions of different cells.

  1. We can reverse the direction of the 1-cells, yielding a bicategory \mathbf{K}^{op}.
  2. We can reverse the direction of the 2-cells, yielding a bicategory \mathbf{K}^{co}.
  3. We can flip the directions of both the 1 and 2 cells, yielding a bicategory \mathbf{K}^{coop}.

The operation we are interested in is flipping the direction of 2-cells. It is fairly routine to check that:

A comonad on 0-cell \mathcal{A} in bicategory \mathbf{K} is the same thing as a monad on \mathcal{A} in \mathbf{K}^{co}.

Finally, we note that for a fixed 0-cell \mathcal{A} in \mathbf{K}, the category \mathbf{K}(\mathcal{A}, \mathcal{A}) is a monoidal category, with the monoidal structure given by composition and identities. A monad on \mathcal{A} is the same thing is a monoid in \mathbf{K}(\mathcal{A}, \mathcal{A}). Dually:

A comonad on a 0-cell \mathcal{A} in bicategory \mathbf{K} is the same thing as a comonoid in the monoidal category \mathbf{K}(\mathcal{A},\mathcal{A}).

If you’ve not encountered comonoids before, you could equally take this as their definition via comonads.

These more esoteric definitions are useful for performing formal calculations at a high level of abstraction, but concrete examples are often important to develop satisfactory intuitions for applications.

Conclusion

We introduced comonads at a fairly rapid pace, building on our previous experience with monads. There is a lot more we could say about comonads, much of which would dualise the situation with monads. For example:

  1. There are corresponding Eilenberg-Moore and Kleisli constructions, with a relation to adjunctions. All of this works out in an entirely dual manner to that for monads.
  2. There is a notion of cofree comonad – again formally dual to that of free monad.

In each case it is worthwhile to examine concrete examples and constructions in familiar categories. There are also interesting questions about the relationships between monads and comonads, and the interaction between them. We will return to such topics in future posts.

Further reading: A good source of information about comonads from a mathematical or computer science perspective is the work of Tarmo Uustalu and Varmo Vene. I would suggest the paper “Comonadic Notions of Computation” as a good starting point.

One thought on “Comonads – Monads Upside Down”

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: