A PDF version of this post is available on github.

# Abstract

Co-presheaf optic is a new kind of optic that generalizes the polynomial lens. Its distinguishing feature is that it’s not based on the action of a monoidal category. Instead the action is parameterized by functors between different co-presheaves. The composition of these actions corresponds to composition of functors rather than the more traditional tensor product. These functors and their composition have a representation in terms of profunctors.

# Motivation

A lot of optics can be defined using the existential, or coend, representation:

Here is a monoidal category with an action on objects of two categories and (I’ll use the same notation for both actions). The actions are composed using the tensor product in :

The idea of this optic is that we have a pair of morphisms, one decomposing the source into the action of some on , and the other recomposing the target from the action of the same on . In most applications we pick to be the same category as .

Recently, there has been renewed interest in polynomial functors. Morphisms between polynomial functors form a new kind of optic that doesn’t neatly fit this mold. They do, however, admit an existential representation or the form:

Here the sets and can be treated as fibers over the set , while the sets and are fibers over a different set .

Alternatively, we can treat these fibrations as functors from discrete categories to , that is co-presheaves. For instance is the result of a co-presheaf acting on an object of a discrete category . The products over can be interpreted as ends that define natural transformations between co-presheaves. The interesting part is that the matrices are fibrated over two different sets. I have previously interpreted them as profunctors:

In this post I will elaborate on this interpretation.

# Co-presheaves

A co-presheaf category behaves, in many respects, like a vector space. For instance, it has a “basis” consisting of representable functors ; in the sense that any co-presheaf is as a colimit of representables. Moreover, colimit-preserving functors between co-presheaf categories are very similar to linear transformations between vector spaces. Of particular interest are functors that are left adjoint to some other functors, since left adjoints preserve colimits.

The polynomial lens formula has a form suggestive of vector-space interpretation. We have one vector space with vectors and and another with and . Rectangular matrices can be seen as components of a linear transformation between these two vector spaces. We can, for instance, write:

where is the transposed matrix. Transposition here serves as an analog of adjunction.

We can now re-cast the polynomial lens formula in terms of co-presheaves. We no longer intepret and as discrete categories. We have:

In this interpretation is a functor between categories of co-presheaves:

We’ll write the action of this functor on a presheaf as .

We assume that this functor has a right adjoint and therefore preserves colimits.

where:

We can now generalize the polynomial optic formula to:

The coend is taken over all functors that have a right adjoint. Fortunately there is a better representation for such functors. It turns out that colimit preserving functors:

are equivalent to profunctors (see the Appendix for the proof). Such a profunctor:

is given by the formula:

where is a representable co-presheaf.

The action of can be expressed as a coend:

The co-presheaf optic is then a coend over all profunctors :

# Composition

We have defined the action as the action of a functor on a co-presheaf. Given two composable functors:

and:

we automatically get the associativity law:

The composition of functors between co-presheaves translates directly to profunctor composition. Indeed, the profunctor corresponding to is given by:

and can be evaluated to:

which is the standard definition of profunctor composition.

Consider two composable co-presheaf optics, and . The first one tells us that there exists a and a pair of natural transformations:

The second tells us that there exists a and a pair:

The composition of the two should be an optic of the type . Indeed, we can construct such an optic using the composition and a pair of natural transformations:

# Generalizations

By duality, there is a corresponding optic based on presheaves. Also, (co-) presheaves can be naturally generalized to enriched categories, where the correspondence between left adjoint functors and enriched profunctors holds as well.

# Appendix

I will show that a functor between two co-presheaves that has a right adjoint and therefore preserves colimits:

is equivalent to a profunctor:

The profunctor is given by:

and the functor can be recovered using the formula:

where:

I’ll show that these formulas are the inverse of each other. First, inserting the formula for into the definition of should gives us back:

which follows from the co-Yoneda lemma.

Second, inserting the formula for into the definition of should give us back:

Since preserves all colimits, and any co-presheaf is a colimit of representables, it’s enough that we prove this identity for a representable:

We have to show that:

and this follows from the co-Yoneda lemma.

## Leave a Reply