The n-Category Café

Introduction

Algebras over a monad provide a categorical interpretation of what it means to evaluate an expression of a particular theory. The process of summing natural numbers, for example, can be understood as the algebra $e : T{\mathbb{N}} \to \mathbb{N}$ where $T$ is the free commutative monoid monad. Given a particular expression in $T\mathbb{N}$, say $1 + 2 + 3$, it’s natural to consider the expression $q = 1 + 5$ as a partial evaluation of it. If we bracket the expression as $(1) + (2 + 3)$, this becomes more explicit—the expression $1 + 5$ is given by evaluating the bracketed subexpressions.

To express this in the language of category theory, we utilize the fact that for an arbitrary algebra over a monad $e : T A \to A$, there are two maps $\mu : T T A \to T A$ and $T e : T T A \to T A$. If we think of the elements of $T A$ as formal expressions over the variables of $A$, the elements $T T A$ as formal expressions over the formal expressions of $T A$, the map $\mu : T T A \to T A$ flattens formal expressions of formal expressions to “mere” formal expressions, while $T e$ evaluates the inner formal expressions. In our example above, the situation is illustrated in the following picture:

The expression $(1) + (2 + 3) \in T T A$ is witnessing the partial evaluation between $1 + 2 + 3$ and $1 + 5$. To generalize this notion to arbitrary algebras and monads not necessarily over Set, we cannot refer to the elements of a set. Instead, we will formulate things in terms of generalized elements—we will call a morphism $p : S \to T A$ from an arbitrary object $S$ a generalized element (with shape $S$) of $T A$.

Given a monad $(T, \eta, \mu)$ and an algebra $A$ with evaluation map $e : T A \to A$, a partial evaluation from $p : S \to T A$ to $q : S \to T A$ consists of a morphism $k : S \to T T A$ such that the following diagram commutes:

Since the algebra laws ensure that $e \circ \mu = e \circ T e$, we see if there is a partial evaluations from $p$ to $q$, we always have a generalized element $e \circ p = e \circ \mu \circ k = e \circ T e \circ k = e \circ q$ which we call the total evaluation or the result of $p$ and $q$. Furthermore, the unit law of the monad ensures that any expression will always be a partial evaluation of itself, as illustrated by the following diagram:

Partial evaluations induce a relation on the morphisms between $S$ and $T A$, which by the argument above turns out to be reflexive. Later, we will see that for a broad class of monads, this relation will be transitive as well.

So far in this blog post, we have talked about monads as a way of generating formal expressions in a given theory. This is a perspective that is most accurate for finitary monads, but partial evaluations turn out to have a meaningful interpretation in infinitary settings as well.

Partial evaluations as conditional expectations

One of the settings where partial evaluations play an interesting role is in the context of probability monads. As we learned in Paolo Perrone’s recent nCafé blog post, probability monads come in slightly different flavors, but can generally be thought of as a way of taking a set of outcomes to a set of probability distributions of random variables over those outcomes. The multiplication map of such monads combines a probability distribution of probability distributions by a simple averaging. Algebras over these monads are spaces which come equipped with a way of taking the expected value of a convex combinations of its points. Such algebras will correspond to some flavor of convex spaces.

It turns out that for such monads, partial evaluations correspond to a notion familiar from probability theory — conditional expectations. More precisely, given an algebra $e: P A \to A$ over a probability monad and distributions $p, q \in P A$, whenever there exists a partial evaluation of $p$ and $q$, there exists two $A$-valued random variables $X$ and $Y$, with probability distribution $p$ and $q$, respectively, such that $Y$ is a conditional expectation of $X$ with respect to some coarser $\sigma$-algebra.

We won’t spell out the correspondence between partial evaluations and conditional expectations in full detail here, but refer the curious reader to section 4.2.1. of Paolo’s PhD thesis. Instead we will provide an example that hopefully provides some intuition for why this might be the case.

Take $A$ to be $\mathbb{R}^2$ and let $p, q \in P A$ be two probability distributions that assign an equal probability to four distinct points of the real plane, marked in blue and red, respectively, in the figure below.

In words, $p$ assigns the probability of $\frac{1}{4}$ to each corner of the unit square, while $q$ assigns a probability of $\frac{1}{4}$ to the north, south, east and west points of the unit circle.

We can express $p$ and $q$ as a convex combination of probabilities and points as $p = \frac{1}{4}\big( (-1,1) + (-1,-1) + (1,-1) + (1,1) \big )$ and $q = \frac{1}{4}((0,1) + (1,0) + (-1,0) + (0,-1))$.

In this example, the red points can be expressed as an averaging, or expected value of blue points. The top red point, for example, is the expected value of the two top blue points, i.e. given that the outcome will lie in the upper half plane. Similarly, the left red point is the expected value of the two blue points in the left half plane, and so on. In other words, $q$ is the probability distribution of a random variable (the position of the red point) which is a conditional expectation of the position of the blue point. By the correspondence alluded to above, we therefore expect there to be a partial evaluation from $p$ to $q$.

How do we find the element $k \in P P A$ witnessing this partial evaluation? The key here is in our description of the points of $q$ as a combination of averages of the points of $p$.

We can write this combination of averages as a convex combination of probability distributions, i.e. as an element $k$ of $P P A$, as

$$k = \frac{1}{4}\big (\frac{1}{2}(-1,1) + \frac{1}{2}(1,1) \big ) + \frac{1}{4}\big (\frac{1}{2}(-1,-1) + \frac{1}{2}(1,-1) \big ) + \frac{1}{4}\big (\frac{1}{2}(-1,-1) + \frac{1}{2}(-1,1) \big ) + \frac{1}{4}\big (\frac{1}{2}(1,-1) + \frac{1}{2}(1,1) \big ).$$

Applying the multiplication map simplifies the expression to yield $p$:

$$\mu(k) = \frac{1}{8}(-1,1) + \frac{1}{8}(1,1) + \frac{1}{8}(-1,-1) + \frac{1}{8}(1,-1) + \frac{1}{8}(-1,-1) + \frac{1}{8}(-1,1) + \frac{1}{8}(1,-1) + \frac{1}{8}(1,1) = p$$

while applying $T e$ to $k$ returns the expected values of the inner brackets, yielding $q$:

$$T e(k) = \frac{1}{4}E[\frac{1}{2}(-1,1) + \frac{1}{2}(1,1)] + \frac{1}{4}E[\frac{1}{2}(-1,-1) + \frac{1}{2}(1,-1) ] +$$ $$\frac{1}{4}E[\frac{1}{2}(-1,-1) + \frac{1}{2}(-1,1) ] + \frac{1}{4}E[\frac{1}{2}(1,-1) + \frac{1}{2}(1,1) ] = q.$$

This demonstrates that $q$ is a partial evaluation of $q$, as witnessed by the element $k \in P P A$.

Transitivity of partial evaluation

Partial evaluations can be thought of as taking incremental steps towards completely evaluating a formal expression. This makes them start to look like arrows in a category of formal expressions, but for that we need a way to compose them. For example, for $T$ the free monoid monad, $A$ the algebra of natural numbers with addition, and $S$ the terminal set (so a map $S \to X$ is just an element of $X$), the expression $1 + 2 + 3 + 4 + 5$ partially evaluates to $3 + 3 + 9$ by the partial evaluation $h = (1 + 2) + (3) + (4 + 5) \in T^2 A$, and $3 + 3 + 9$ partially evaluates to $3 + 12$ by $k = (3) + (3 + 9) \in T^2 A$. In this example we could certainly find a way of adding parentheses to $1 + 2 + 3 + 4 + 5$ to partially evaluate it into $3 + 12$, but can we construct this as a composite of $h$ and $k$ in some sense?

Consider the doubly nested expression $((1 + 2)) + ((3) + (4 + 5)) \in T^3 A$. Applying $\mu$ removes the outer parentheses to get $h$, and applying $T^2 e$ evaluates the innermost expressions to get $k$. We can also apply $T \mu$ to get $(1 + 2) + (3 + 4 + 5)$, which is precisely the partial evaluation we want. It’s no coincidence that this worked: the monad, algebra, and naturality laws for maps out of $T^2 A$ assemble into a triangle

This means if we have partial evaluations $h$ from $p$ to $q$ and $k$ from $q$ to $r$, and an element $a \in T^3 A$ with $\mu(a) = h$ and $T^2 e(a) = k$, then $T\mu(a)$ is a partial evaluation from $p$ to $r$. There may be a partial evaluation $l$ from $p$ to $r$ without such an $a$, but it would not then be a “composite” of $h$ and $k$ in any meaningful way, just as in a category there can be a triangle of morphisms

where $l$ is not the composition of $h$ and $k$. We can then think of $a$ as a triangle filling in this diagram of partial evaluations on its boundary, and witnessing that $p$ and $q$ can be composed into $l$. Unlike a category, however, there may be many such triangles, since elements $a$ of $T^3 A$ with $\mu (a) = h$, $T^2 e(a) = k$, $T \mu (l)$ are not generally unique. These triangles can also be considered as strategies for composing partial evaluations, so given $h$ and $k$ as above one way to find a partial evaluation from $p$ to $r$ is to look for a strategy $a$ for composing $h$ and $k$ into $T \mu (a)$.

Using this approach, we can consider the class of weakly cartesian monads where such a strategy always turns out to exist. A monad $(T,\eta,\mu)$ is weakly cartesian if it preserves weak pullbacks and the naturality squares of $\eta$ and $\mu$ are weak pullbacks. A weak pullback square

has the property that any pair of maps from $W'$ into $X$ and $Y$ commuting with $f$ and $g$ factors through $W$, but not necessarily uniquely (unlike the usual pullback squares). In particular, $h$ and $k$ as above fit into a diagram

where the square in the diagram is a naturality square of $\mu$. If $T$ is weakly cartesian, we get a map $a : S \to T^3 A$ which agrees with $h$ and $k$ after applying $\mu$ and $T^2 e$, respectively. This $a$ is a composition, so applying $T\mu$ gives a composite of $h$ and $k$:

So partial evaluations can always be composed when $T$ is weakly cartesian, though perhaps in more than one way (since $a$ is not unique). If $T$ is cartesian, as in its naturality squares are pullbacks, then there is a canonical choice of composition and furthermore partial evaluations form a category. This is the case for the free monoid monad, so our choice of $a$ in the example above was no accident.

Bar construction

In the previous section, $a : S \to T^3 A$ was interpreted as a triangle, with the arrows $h$, $k$, and $T\mu(a)$ as its edges. Partial evaluations do more than just reduce formal expressions: they give a nested expression encoding how to compute that reduction. Likewise $a$ tells us not just that $h$ and $k$ have a composite, but how they compose, in the language of the monad $T$, and that information has the “shape” of a triangle. This suggests that $T$ hosts a richer notion of computation than merely reducing formal expressions, where elements of $T^n A$ have some sort of computational meaning.

We don’t yet know much about what elements of $T^n A$ mean for computation, but we know a lot about their shape. These objects and the maps between them derived from $\eta$, $\mu$, and $e$ assemble into a simplicial object

meaning we can see elements of $T A$ as vertices, $T^2 A$ as edges, $T^3 A$ as triangles, $T^4 A$ as tetrahedra, and in general $T^{n+1} A$ as $n$-simplices with $n-1$ dimensional faces identified by $T^n e$ and $T^i \mu$, $0 \leq i < n$. This simplicial object (in the category of $T$-algebras) is called the bar construction of $A$.

The bar construction thus expresses that there is a whole space of computations in $A$. The expressions in $T A$ are the points, partial evaluations in $T^2 A$ form the paths between points, and nested expressions in $T^n$ describe higher dimensional cells. Even more, the space is directed, as 1-simplices $k \in T^2 A$ have a direction from $\mu (k)$ to $T e(k)$, and that directedness comes from partial evaluation.

However, not much is currently known about this space, and we are left with several open questions. How can we interpret the computational meaning of the higher simplices? Can computational properties of a monad relate to topological properties of the space? What kinds of compositional properties exist for partial evaluations in more general monads? What does this all tell us about probability? Answers to these questions could illuminate a relationship between computation and homotopy theory with implications well beyond either of those fields.