Lens

This post is based on the talk I gave at Functional Conf 2022. There is a video recording of this talk.

Disclaimers

Data types may contain secret information. Some of it can be extracted, some is hidden forever. We’re going to get to the bottom of this conspiracy.

No data types were harmed while extracting their secrets.

No coercion was used to make them talk.

We’re talking, of course, about unsafeCoerce, which should never be used.

Implementation hiding

The implementation of a function, even if it’s available for inspection by a programmer, is hidden from the program itself.

What is this function, with the suggestive name double, hiding inside?

x double x
2 4
3 6
-1 -2

Best guess: It’s hiding 2. It’s probably implemented as:

double x = 2 * x


How would we go about extracting this hidden value? We can just call it with the unit of multiplication:

double 1
> 2


Is it possible that it’s implemented differently (assuming that we’ve already checked it for all values of the argument)? Of course! Maybe it’s adding one, multiplying by two, and then subtracting two. But whatever the actual implementation is, it must be equivalent to multiplication by two. We say that the implementaion is isomorphic to multiplying by two.

Functors

Functor is a data type that hides things of type a. Being a functor means that it’s possible to modify its contents using a function. That is, if we’re given a function a->b and a functorful of a‘s, we can create a functorful of b‘s. In Haskell we define the Functor class as a type constructor equipped with the method fmap:

class Functor f where
fmap :: (a -> b) -> f a -> f b


A standard example of a functor is a list of a‘s. The implementation of fmap applies a function g to all its elements:

instance Functor [] where
fmap g [] = []
fmap g (a : as) = (g a) : fmap g as


Saying that something is a functor doesn’t guarantee that it actually “contains” values of type a. But most data structures that are functors will have some means of getting at their contents. When they do, you can verify that they change their contents after applying fmap. But there are some sneaky functors.

For instance Maybe a tells us: Maybe I have an a, maybe I don’t. But if I have it, fmap will change it to a b.

instance Functor Maybe where
fmap g Empty = Empty
fmap g (Just a) = Just (g a)


A function that produces values of type a is also a functor. A function e->a tells us: I’ll produce a value of type a if you ask nicely (that is call me with a value of type e). Given a producer of a‘s, you can change it to a producer of b‘s by post-composing it with a function g :: a -> b:

instance Functor ((->) e) where
fmap g f = g . f


Then there is the trickiest of them all, the IO functor. IO a tells us: Trust me, I have an a, but there’s no way I could tell you what it is. (Unless, that is, you peek at the screen or open the file to which the output is redirected.)

Continuations

A continuation is telling us: Don’t call us, we’ll call you. Instead of providing the value of type a directly, it asks you to give it a handler, a function that consumes an a and returns the result of the type of your choice:

type Cont a = forall r. (a -> r) -> r


You’d suspect that a continuation either hides a value of type a or has the means to produce it on demand. You can actually extract this value by calling the continuation with an identity function:

runCont :: Cont a -> a
runCont k = k id


In fact Cont a is for all intents and purposes equivalent to a–it’s isomorphic to it. Indeed, given a value of type a you can produce a continuation as a closure:

mkCont :: a -> Cont a
mkCont a = \k -> k a


The two functions, runCont and mkCont are the inverse of each other thus establishing the isomorphism Cont a ~ a.

The Yoneda Lemma

Here’s a variation on the theme of continuations. Just like a continuation, this function takes a handler of a‘s, but instead of producing an x, it produces a whole functorful of x‘s:

type Yo f a = forall x. (a -> x) -> f x


Just like a continuation was secretly hiding a value of the type a, this data type is hiding a whole functorful of a‘s. We can easily retrieve this functorful by using the identity function as the handler:

runYo :: Functor f => Yo f a -> f a
runYo g = g id


Conversely, given a functorful of a‘s we can reconstruct Yo f a by defining a closure that fmap‘s the handler over it:

mkYo :: Functor f => f a -> Yo f a
mkYo fa = \g -> fmap g fa


Again, the two functions, runYo and mkYo are the inverse of each other thus establishing a very important isomorphism called the Yoneda lemma:

Yo f a ~ f a

Both continuations and the Yoneda lemma are defined as polymorphic functions. The forall x in their definition means that they use the same formula for all types (this is called parametric polymorphism). A function that works for any type cannot make any assumptions about the properties of that type. All it can do is to look at how this type is packaged: Is it passed inside a list, a function, or something else. In other words, it can use the information about the form in which the polymorphic argument is passed.

Existential Types

One cannot speak of existential types without mentioning Jean-Paul Sartre.

An existential data type says: There exists a type, but I’m not telling you what it is. Actually, the type has been known at the time of construction, but then all its traces have been erased. This is only possible if the data constructor is itself polymorphic. It accepts any type and then immediately forgets what it was.

Here’s an extreme example: an existential black hole. Whatever falls into it (through the constructor BH) can never escape.

data BlackHole = forall a. BH a


Even a photon can’t escape a black hole:

bh :: BlackHole
bh = BH "Photon"


We are familiar with data types whose constructors can be undone–for instance using pattern matching. In type theory we define types by providing introduction and elimination rules. These rules tell us how to construct and how to deconstruct types.

But existential types erase the type of the argument that was passed to the (polymorphic) constructor so they cannot be deconstructed. However, not all is lost. In physics, we have Hawking radiation escaping a black hole. In programming, even if we can’t peek at the existential type, we can extract some information about the structure surrounding it.

Here’s an example: We know we have a list, but of what?

data SomeList = forall a. SomeL [a]


It turns out that to undo a polymorphic constructor we can use a polymorphic function. We have at our disposal functions that act on lists of arbitrary type, for instance length:

length :: forall a. [a] -> Int


The use of a polymorphic function to “undo” a polymorphic constructor doesn’t expose the existential type:

len :: SomeList -> Int
len (SomeL as) = length as


Indeed, this works:

someL :: SomeList
someL = SomeL [1..10]
> len someL
> 10


Extracting the tail of a list is also a polymorphic function. We can use it on SomeList without exposing the type a:

trim :: SomeList -> SomeList
trim (SomeL []) = SomeL []
trim (SomeL (a: as)) = SomeL as


Here, the tail of the (non-empty) list is immediately stashed inside SomeList, thus hiding the type a.

But this will not compile, because it would expose a:

bad :: SomeList -> a


Producer/Consumer

Existential types are often defined using producer/consumer pairs. The producer is able to produce values of the hidden type, and the consumer can consume them. The role of the client of the existential type is to activate the producer (e.g., by providing some input) and passing the result (without looking at it) directly to the consumer.

Here’s a simple example. The producer is just a value of the hidden type a, and the consumer is a function consuming this type:

data Hide b = forall a. Hide a (a -> b)


All the client can do is to match the consumer with the producer:

unHide :: Hide b -> b
unHide (Hide a f) = f a


This is how you can use this existential type. Here, Int is the visible type, and Char is hidden:

secret :: Hide Int
secret = Hide 'a' (ord)


The function ord is the consumer that turns the character into its ASCII code:

> unHide secret
> 97


Co-Yoneda Lemma

There is a duality between polymorphic types and existential types. It’s rooted in the duality between universal quantifiers (for all, $\forall$) and existential quantifiers (there exists, $\exists$).

The Yoneda lemma is a statement about polymorphic functions. Its dual, the co-Yoneda lemma, is a statement about existential types. Consider the following type that combines the producer of x‘s (a functorful of x‘s) with the consumer (a function that transforms x‘s to a‘s):

data CoYo f a = forall x. CoYo (f x) (x -> a)


What does this data type secretly encode? The only thing the client of CoYo can do is to apply the consumer to the producer. Since the producer has the form of a functor, the application proceeds through fmap:

unCoYo :: Functor f => CoYo f a -> f a
unCoYo (CoYo fx g) = fmap g fx


The result is a functorful of a‘s. Conversely, given a functorful of a‘s, we can form a CoYo by matching it with the identity function:

mkCoYo :: Functor f => f a -> CoYo f a
mkCoYo fa = CoYo fa id


This pair of unCoYo and mkCoYo, one the inverse of the other, witness the isomorphism

CoYo f a ~ f a

In other words, CoYo f a is secretly hiding a functorful of a‘s.

Contravariant Consumers

The informal terms producer and consumer, can be given more rigorous meaning. A producer is a data type that behaves like a functor. A functor is equipped with fmap, which lets you turn a producer of a‘s to a producer of b‘s using a function a->b.

Conversely, to turn a consumer of a‘s to a consumer of b‘s you need a function that goes in the opposite direction, b->a. This idea is encoded in the definition of a contravariant functor:

class Contravariant f where
contramap :: (b -> a) -> f a -> f b


There is also a contravariant version of the co-Yoneda lemma, which reverses the roles of a producer and a consumer:

data CoYo' f a = forall x. CoYo' (f x) (a -> x)


Here, f is a contravariant functor, so f x is a consumer of x‘s. It is matched with the producer of x‘s, a function a->x.

As before, we can establish an isomorphism

CoYo' f a ~ f a

by defining a pair of functions:

unCoYo' :: Contravariant f => CoYo' f a -> f a
unCoYo' (CoYo' fx g) = contramap g fx

mkCoYo' :: Contravariant f => f a -> CoYo' f a
mkCoYo' fa = CoYo' fa id


Existential Lens

A lens abstracts a device for focusing on a part of a larger data structure. In functional programming we deal with immutable data, so in order to modify something, we have to decompose the larger structure into the focus (the part we’re modifying) and the residue (the rest). We can then recreate a modified data structure by combining the new focus with the old residue. The important observation is that we don’t care what the exact type of the residue is. This description translates directly into the following definition:

data Lens' s a =
forall c. Lens' (s -> (c, a)) ((c, a) -> s)


Here, s is the type of the larger data structure, a is the type of the focus, and the existentially hidden c is the type of the residue. A lens is constructed from a pair of functions, the first decomposing s and the second recomposing it.

Given a lens, we can construct two functions that don’t expose the type of the residue. The first is called get. It extracts the focus:

toGet :: Lens' s a -> (s -> a)
toGet (Lens' frm to) = snd . frm


The second, called set replaces the focus with the new value:

toSet :: Lens' s a -> (s -> a -> s)
toSet (Lens' frm to) = \s a -> to (fst (frm s), a)


Notice that access to residue not possible. The following will not compile:

bad :: Lens' s a -> (s -> c)
bad (Lens' frm to) = fst . frm


But how do we know that a pair of a getter and a setter is exactly what’s hidden in the existential definition of a lens? To show this we have to use the co-Yoneda lemma. First, we have to identify the producer and the consumer of c in our existential definition. To do that, notice that a function returning a pair (c, a) is equivalent to a pair of functions, one returning c and another returning a. We can thus rewrite the definition of a lens as a triple of functions:

data Lens' s a =
forall c. Lens' (s -> c) (s -> a) ((c, a) -> s)


The first function is the producer of c‘s, so the rest will define a consumer. Recall the contravariant version of the co-Yoneda lemma:

data CoYo' f s = forall c. CoYo' (f c) (s -> c)


We can define the contravariant functor that is the consumer of c‘s and use it in our definition of a lens. This functor is parameterized by two additional types s and a:

data F s a c = F (s -> a) ((c, a) -> s)


This lets us rewrite the lens using the co-Yoneda representation, with f replaced by (partially applied) F s a:

type Lens' s a = CoYo' (F s a) s


We can now use the isomorphism CoYo' f s ~ f s. Plugging in the definition of F, we get:

Lens' s a ~ CoYo' (F s a) s
CoYo' (F s a) s ~ F s a s
F s a s ~ (s -> a) ((s, a) -> s)


We recognize the two functions as the getter and the setter. Thus the existential representation of the lens is indeed isomorphic to the getter/setter pair.

Type-Changing Lens

The simple lens we’ve seen so far lets us replace the focus with a new value of the same type. But in general the new focus could be of a different type. In that case the type of the whole thing will change as well. A type-changing lens thus has the same decomposition function, but a different recomposition function:

data Lens s t a b =
forall c. Lens (s -> (c, a)) ((c, b) -> t)


As before, this lens is isomorphic to a get/set pair, where get extracts an a:

toGet :: Lens s t a b -> (s -> a)
toGet (Lens frm to) = snd . frm


and set replaces the focus with a new value of type b to produce a t:

toSet :: Lens s t a b -> (s -> b -> t)
toSet (Lens frm to) = \s b -> to (fst (frm s), b)


Other Optics

The advantage of the existential representation of lenses is that it easily generalizes to other optics. The idea is that a lens decomposes a data structure into a pair of types (c, a); and a pair is a product type, symbolically $c \times a$

data Lens s t a b =
forall c. Lens (s -> (c, a))
((c, b) -> t)


A prism does the same for the sum data type. A sum $c + a$ is written as Either c a in Haskell. We have:

data Prism s t a b =
forall c. Prism (s -> Either c a)
(Either c b -> t)


We can also combine sum and product in what is called an affine type $c_1 + c_2 \times a$. The resulting optic has two possible residues, c1 and c2:

data Affine s t a b =
forall c1 c2. Affine (s -> Either c1 (c2, a))
(Either c1 (c2, b) -> t)


The list of optics goes on and on.

Profunctors

A producer can be combined with a consumer in a single data structure called a profunctor. A profunctor is parameterized by two types; that is p a b is a consumer of a‘s and a producer of b‘s. We can turn a consumer of a‘s and a producer of b‘s to a consumer of s‘s and a producer of t‘s using a pair of functions, the first of which goes in the opposite direction:

class Profunctor p where
dimap :: (s -> a) -> (b -> t) -> p a b -> p s t


The standard example of a profunctor is the function type p a b = a -> b. Indeed, we can define dimap for it by precomposing it with one function and postcomposing it with another:

instance Profunctor (->) where
dimap in out pab = out . pab . in


Profunctor Optics

We’ve seen functions that were polymorphic in types. But polymorphism is not restricted to types. Here’s a definition of a function that is polymorphic in profunctors:

type Iso s t a b = forall p. Profunctor p =>
p a b -> p s t


This function says: Give me any producer of b‘s that consumes a‘s and I’ll turn it into a producer of t‘s that consumes s‘s. Since it doesn’t know anything else about its argument, the only thing this function can do is to apply dimap to it. But dimap requires a pair of functions, so this profunctor-polymorphic function must be hiding such a pair:

s -> a
b -> t


Indeed, given such a pair, we can reconstruct it’s implementation:

mkIso :: (s -> a) -> (b -> t) -> Iso s t a b
mkIso g h = \p -> dimap g h p


All other optics have their corresponding implementation as profunctor-polymorphic functions. The main advantage of these representations is that they can be composed using simple function composition.

Main Takeaways

• Producers and consumers correspond to covariant and contravariant functors
• Existential types are dual to polymorphic types
• Existential optics combine producers with consumers in one package
• In such optics, producers decompose, and consumers recompose data
• Functions can be polymorphic with respect to types, functors, or profunctors

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:

$\mathcal{O}\langle a, b\rangle \langle s, t \rangle = \int^{m \colon \mathcal M} \mathcal C (s, m \bullet a) \times \mathcal D ( m \bullet b, t)$

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

$n \bullet (m \bullet a) = (n \otimes m) \bullet a$

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

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:

$\int^{c_{k i}} \prod_{k \in K} \mathbf{Set} \left(s_k, \sum_{n \in N} a_n \times c_{n k} \right) \times \prod_{i \in K} \mathbf{Set} \left(\sum_{m \in N} b_m \times c_{m i}, t_i \right)$

Here the sets $s_k$ and $t_i$ can be treated as fibers over the set $K$, while the sets $a_n$ and $b_m$ are fibers over a different set $N$.

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

$c \colon \mathcal N^{op} \times \mathcal K \to \mathbf{Set}$

In this post I will elaborate on this interpretation.

Co-presheaves

A co-presheaf category $[\mathcal C, Set ]$ behaves, in many respects, like a vector space. For instance, it has a “basis” consisting of representable functors $\mathcal C (r, -)$; 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 $\vec{s}$ and $\vec{t}$ and another with $\vec{a}$ and $\vec{b}$. Rectangular matrices $c_{n k}$ can be seen as components of a linear transformation between these two vector spaces. We can, for instance, write:

$\sum_{n \in N} a_n \times c_{n k} = c^T a$

where $c^T$ 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 $\mathcal N$ and $\mathcal K$ as discrete categories. We have:

$a, b \colon [\mathcal N, \mathbf{Set}]$

$s, t \colon [\mathcal K, \mathbf{Set}]$

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

$c \colon [\mathcal N, \mathbf{Set}] \to [\mathcal K, \mathbf{Set}]$

We’ll write the action of this functor on a presheaf $a$ as $c \bullet a$.

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

$[\mathcal K, \mathbf{Set}] (c \bullet a, t) \cong [\mathcal N, \mathbf{Set}] (a, c^{\dagger} \bullet t)$

where:

$c^{\dagger} \colon [\mathcal K, \mathbf{Set}] \to [\mathcal N, \mathbf{Set}]$

We can now generalize the polynomial optic formula to:

$\mathcal{O}\langle a, b\rangle \langle s, t \rangle = \int^{c} [\mathcal K, \mathbf{Set}] \left(s, c \bullet a \right) \times [\mathcal K, \mathbf{Set}] \left(c \bullet b, t \right)$

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:

$c \colon [\mathcal N, \mathbf{Set}] \to [\mathcal K, \mathbf{Set}]$

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

$p \colon \mathcal N^{op} \times \mathcal K \to \mathbf{Set}$

is given by the formula:

$p \langle n, k \rangle = c ( \mathcal N(n, -)) k$

where $\mathcal N(n, -)$ is a representable co-presheaf.

The action of $c$ can be expressed as a coend:

$(c \bullet a) k = \int^{n} a(n) \times p \langle n, k \rangle$

The co-presheaf optic is then a coend over all profunctors $p \colon \mathcal N^{op} \times \mathcal K \to \mathbf{Set}$:

$\int^{p} [\mathcal K, \mathbf{Set}] \left(s, \int^{n} a(n) \times p \langle n, - \rangle \right) \times [\mathcal K, \mathbf{Set}] \left(\int^{n'} b(n') \times p \langle n', - \rangle, t \right)$

Composition

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

$c \colon [\mathcal N, \mathbf{Set}] \to [\mathcal K, \mathbf{Set}]$

and:

$c' \colon [\mathcal K, \mathbf{Set}] \to [\mathcal M, \mathbf{Set}]$

we automatically get the associativity law:

$c' \bullet (c \bullet a) = (c' \circ c) a$

The composition of functors between co-presheaves translates directly to profunctor composition. Indeed, the profunctor $p' \diamond p$ corresponding to $c' \circ c$ is given by:

$(p' \diamond p) \langle n, m \rangle = (c' \circ c) ( \mathcal N(n, -)) m$

and can be evaluated to:

$(c' ( c ( \mathcal N(n, -))) m \cong \int^{k} c ( \mathcal N(n, -)) k \times p' \langle k, m \rangle$

$\cong \int^{k} p \langle n, k \rangle \times p' \langle k, m \rangle$

which is the standard definition of profunctor composition.

Consider two composable co-presheaf optics, $\mathcal{O}\langle a, b\rangle \langle s, t \rangle$ and $\mathcal{O}\langle a', b' \rangle \langle a, b \rangle$. The first one tells us that there exists a $c$ and a pair of natural transformations:

$l_c (s, a ) = [\mathcal K, \mathbf{Set}] \left(s, c \bullet a \right)$

$r_c (b, t) = [\mathcal K, \mathbf{Set}] \left(c \bullet b, t \right)$

The second tells us that there exists a $c'$ and a pair:

$l'_{c'} (a, a' ) = [\mathcal K, \mathbf{Set}] \left(a, c' \bullet a' \right)$

$r'_{c'} (b', b) = [\mathcal K, \mathbf{Set}] \left(c' \bullet b', b \right)$

The composition of the two should be an optic of the type $\mathcal{O}\langle a', b'\rangle \langle s, t \rangle$. Indeed, we can construct such an optic using the composition $c' \circ c$ and a pair of natural transformations:

$s \xrightarrow{l_c (s, a )} c \bullet a \xrightarrow{c \,\circ \, l'_{c'} (a, a')} c \bullet (c' \bullet a') \xrightarrow{assoc} (c \circ c') \bullet a'$

$(c \circ c') \bullet b' \xrightarrow{assoc^{-1}} c \bullet (c' \bullet b') \xrightarrow{c \, \circ \, r'_{c'} (b', b)} c \bullet b \xrightarrow{r_c (b, t)} t$

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:

$c \colon [\mathcal N, \mathbf{Set}] \to [\mathcal K, \mathbf{Set}]$

is equivalent to a profunctor:

$p \colon \mathcal N^{op} \times \mathcal K \to \mathbf{Set}$

The profunctor is given by:

$p \langle n, k \rangle = c ( \mathcal N(n, -)) k$

and the functor $c$ can be recovered using the formula:

$c (a) k = \int^{n'} a (n') \times p \langle n', k \rangle$

where:

$a \colon [\mathcal N, \mathbf{Set}]$

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

$\int^{n'} \mathcal N(n, -) (n') \times p\langle n', k \rangle \cong p \langle n, k \rangle$

which follows from the co-Yoneda lemma.

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

$\int^{n'} a n' \times c(\mathcal N(n', -)) k \cong c (a) k$

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

$a (n) = \mathcal N (r, n)$

We have to show that:

$\int^{n'} \mathcal N (r, n') \times c(\mathcal N(n', -)) k \cong c ( \mathcal N (r, -) ) k$

and this follows from the co-Yoneda lemma.

A PDF of this post is available on github.

Motivation

In this post I’ll be looking at a subcategory of $\mathbf{Poly}$ that consists of polynomial functors in which the fibration is done over one fixed set $N$:

$P(y) = \sum_{n \in N} s_n \times \mathbf{Set}(t_n, y)$

The reason for this restriction is that morphisms between such functors, which are called polynomial lenses, can be understood in terms of monoidal actions. Optics that have this property automatically have profunctor representation. Profunctor representation has the advantage that it lets us compose optics using regular function composition.

Previously I’ve explored the representations of polynomial lenses as optics in terms on functors and profunctors on discrete categories. With just a few modifications, we can make these categories non-discrete. The trick is to replace sums with coends and products with ends; and, when appropriate, interpret ends as natural transformations.

Monoidal Action

Here’s the existential representation of a lens between polynomials in which all fibrations are over the same set $N$:

$\mathbf{Pl}\langle s, t\rangle \langle a, b\rangle \cong$

$\int^{c_{k i}} \prod_{k \in N} \mathbf{Set} \left(s_k, \sum_{n \in N} a_n \times c_{n k} \right) \times \prod_{i \in N} \mathbf{Set} \left(\sum_{m \in N} b_m \times c_{m i}, t_i \right)$

This makes the matrices $c_{n k}$ “square.” Such matrices can be multiplied using a version of matrix multiplication.

Interestingly, this idea generalizes naturally to a setting in which $N$ is replaced by a non-discrete category $\mathcal{N}$. In this setting, we’ll write the residues $c_{m n}$ as profunctors:

$c \langle m, n \rangle \colon \mathcal{N}^{op} \times \mathcal{N} \to \mathbf{Set}$

They are objects in the monoidal category in which the tensor product is given by profunctor composition:

$(c \diamond c') \langle m, n \rangle = \int^{k \colon \mathcal{N}} c \langle m, k \rangle \times c' \langle k, n \rangle$

and the unit is the hom-functor $\mathcal{N}(m, n)$. (Incidentally, a monoid in this category is called a promonad.)

In the case of $\mathcal{N}$ a discrete category, these definitions decay to standard matrix multiplication:

$\sum_k c_{m k} \times c'_{k n}$

and the Kronecker delta $\delta_{m n}$.

We define the monoidal action of the profunctor $c$ acting on a co-presheaf $a$ as:

$(c \bullet a) (m) = \int^{n \colon \mathcal{N}} a(n) \times c \langle n, m \rangle$

This is reminiscent of a vector being multiplied by a matrix. Such an action of a monoidal category equips the co-presheaf category with the structure of an actegory.

A product of hom-sets in the definition of the existential optic turns into a set of natural transformations in the functor category $[\mathcal{N}, \mathbf{Set}]$.

$\mathbf{Pl}\langle s, t\rangle \langle a, b\rangle \cong \int^{c \colon [\mathcal{N}^{op} \times \mathcal{N}, Set]} [\mathcal{N}, \mathbf{Set}] \left(s, c \bullet a\right) \times [\mathcal{N}, \mathbf{Set}] \left(c \bullet b, t\right)$

Or, using the end notation for natural transformations:

$\int^{c} \left( \int_m \mathbf{Set}\left(s(m), (c \bullet a)(m)\right) \times \int_n \mathbf{Set} \left((c \bullet b)(n), t(n)\right) \right)$

As before, we can eliminate the coend if we can isolate $c$ in the second hom-set using a series of isomorphisms:

$\int_n \mathbf{Set} \left(\int^k b(k) \times c\langle k, n \rangle , t(n) \right)$

$\cong \int_n \int_k \mathbf{Set}\left( b(k) \times c\langle k, n \rangle , t (n)\right)$

$\cong \int_{n, k} \mathbf{Set}\left(c\langle k, n \rangle , [b(k), t (n)]\right)$

I used the fact that a mapping out of a coend is an end. The result, after applying the Yoneda lemma to eliminate the end over $k$, is:

$\mathbf{Pl}\langle s, t\rangle \langle a, b\rangle \cong \int_m \mathbf{Set}\left(s(m), \int^j a(j) \times [b(j), t(m)] \right)$

or, with some abuse of notation:

$[\mathcal{N}, \mathbf{Set}] ( s, [b, t] \bullet a)$

When $\mathcal{N}$ is discrete, this formula decays to the one for polynomial lens.

Profunctor Representation

Since this poly-lens is a special case of a general optic, it automatically has a profunctor representation. The trick is to define a generalized Tambara module, that is a category $\mathcal{T}$ of profunctors of the type:

$P \colon [\mathcal{N}, \mathbf{Set}]^{op} \times [\mathcal{N}, \mathbf{Set}] \to \mathbf{Set}$

with additional structure given by the following family of transformations, in components:

$\alpha_{c, s, t} \colon P\langle s, t \rangle \to P \left \langle c \bullet s, c \bullet t \right \rangle$

The profunctor representation of the polynomial lens is then given by an end over all profunctors in this Tambara category:

$\mathbf{Pl}\langle s, t\rangle \langle a, b\rangle \cong \int_{P \colon \mathcal{T}} \mathbf{Set}\left ( (U P)\langle a, b \rangle, (U P) \langle s, t \rangle \right)$

Where $U$ is the obvious forgetful functor from $\mathcal{T}$ to the underlying profunctor category\$.

Lenses and, more general, optics are an example of hard-core category theory that has immediate application in programming. While working on polynomial lenses, I had a vague idea how they could be implemented in a programming language. I thought up an example of a polynomial lens that would focus on all the leaves of a tree at once. It could retrieve or modify them in a single operation. There already is a Haskell optic called traversal that could do it. It can safely retrieve a list of leaves from a tree. But there is a slight problem when it comes to replacing them: the size of the input list has to match the number of leaves in the tree. If it doesn’t, the traversal doesn’t work.

A polynomial lens adds an additional layer of safety by keeping track of the sizes of both the trees and the lists. The problem is that its implementation requires dependent types. Haskell has some support for dependent types, so I tried to work with it, but I quickly got bogged down. So I decided to bite the bullet and quickly learn Idris. This was actually easier than I expected and this post is the result.

Counted Vectors and Trees

I started with the “Hello World!” of dependent types: counted vectors. Notice that, in Idris, type signatures use a single colon rather than the Haskell’s double colon. You can quickly get used to it after the compiler slaps you a few times.

data Vect : Type -> Nat -> Type where
VNil : Vect a Z
VCons : (x: a) -> (xs : Vect a n) -> Vect a (S n)

If you know Haskell GADTs, you can easily read this definition. In Haskell, we usually think of Nat as a “kind”, but in Idris types and values live in the same space. Nat is just an implementation of Peano artithmetics, with Z standing for zero, and (S n) for the successor of n. Here, VNil is the constructor of an empty vector of size Z, and VCons prepends a value of type a to the tail of size n resulting in a new vector of size (S n). Notice that Idris is much more explicit about types than Haskell.

The power of dependent types is in very strict type checking of both the implementation and of usage of functions. For instance, when mapping a function over a vector, we can make sure that the result is the same size as the argument:

mapV : (a -> b) -> Vect a n -> Vect b n
mapV f VNil = VNil
mapV f (VCons a v) = VCons (f a) (mapV f v)

When concatenating two vectors, the length of the result must be the sum of the two lengths, (plus m n):

concatV : Vect a m -> Vect a n -> Vect a (plus m n)
concatV VNil v = v
concatV (VCons a w) v = VCons a (concatV w v)

Similarly, when splitting a vector in two, the lengths must match, too:

splitV : (n : Nat) -> Vect a (plus n m) -> (Vect a n, Vect a m)
splitV Z v = (VNil, v)
splitV (S k) (VCons a v') = let (v1, v2) = splitV k v'
in (VCons a v1, v2)

Here’s a more complex piece of code that implements insertion sort:

sortV : Ord a => Vect a n -> Vect a n
sortV VNil = VNil
sortV (VCons x xs) = let xsrt = sortV xs
in (ins x xsrt)
where
ins : Ord a => (x : a) -> (xsrt : Vect a n) -> Vect a (S n)
ins x VNil = VCons x VNil
ins x (VCons y xs) = if x < y then VCons x (VCons y xs)
else VCons y (ins x xs)

In preparation for the polynomial lens example, let’s implement a node-counted binary tree. Notice that we are counting nodes, not leaves. That’s why the node count for Node is the sum of the node counts of the children plus one:

data Tree : Type -> Nat -> Type where
Empty : Tree a Z
Leaf  : a -> Tree a (S Z)
Node  : Tree a n -> Tree a m -> Tree a (S (plus m  n))

All this is not much different from what you’d see in a Haskell library.

Existential Types

So far we’ve been dealing with function that return vectors whose lengths can be easily calculated from the inputs and verified at compile time. This is not always possible, though. In particular, we are interested in retrieving a vector of leaves from a tree that’s parameterized by the number of nodes. We don’t know up front how many leaves a given tree might have. Enter existential types.

An existential type hides part of its implementation. An existential vector, for instance, hides its size. The receiver of an existential vector knows that the size “exists”, but its value is inaccessible. You might wonder then: What can be done with such a mystery vector? The only way for the client to deal with it is to provide a function that is insensitive to the size of the hidden vector. A function that is polymorphic in the size of its argument. Our sortV is an example of such a function.

Here’s the definition of an existential vector:

data SomeVect : Type -> Type where
HideV : {n : Nat} -> Vect a n -> SomeVect a

SomeVect is a type constructor that depends on the type a—the payload of the vector. The data constructor HideV takes two arguments, but the first one is surrounded by a pair of braces. This is called an implicit argument. The compiler will figure out its value from the type of the second argument, which is Vect a n. Here’s how you construct an existential:

secretV : SomeVect Int
secretV = HideV (VCons 42 VNil)

In this case, the compiler will deduce n to be equal to one, but the recipient of secretV will have no way of figuring this out.

Since we’ll be using types parameterized by Nat a lot, let’s define a type synonym:

Nt : Type
Nt = Nat -> Type

Both Vect a and Tree a are examples of this type.

We can also define a generic existential for stashing such types:

data Some : Nt -> Type where
Hide : {n : Nat} -> nt n -> Some nt

and some handy type synonyms:

SomeVect : Type -> Type
SomeVect a = Some (Vect a)
SomeTree : Type -> Type
SomeTree a = Some (Tree a)

Polynomial Lens

We want to translate the following categorical definition of a polynomial lens:

$\mathbf{PolyLens}\langle s, t\rangle \langle a, b\rangle = \prod_{k} \mathbf{Set}\left(s_k, \sum_{n} a_n \times [b_n, t_k] \right)$

We’ll do it step by step. First of all, we’ll assume, for simplicity, that the indices $k$ and $n$ are natural numbers. Therefore the four arguments to PolyLens are types parameterized by Nat, for which we have a type alias:

PolyLens : Nt -> Nt -> Nt -> Nt -> Type

The definition starts with a big product over all $k$‘s. Such a product corresponds, in programming, to a polymorphic function. In Haskell we would write it as forall k. In Idris, we’ll accomplish the same using an implicit argument {k : Nat}.

The hom-set notation $\mathbf{Set}(a, b)$ stands for a set of functions from $a$ to $b$, or the type a -> b. So does the notation $[a, b]$ (the internal hom is the same as the external hom in $\mathbf{Set}$). The product $a \times b$ is the type of pairs (a, b).

The only tricky part is the sum over $n$. A sum corresponds exactly to an existential type. Our SomeVect, for instance, can be considered a sum over n of all vector types Vect a n.

Here’s the intuition: Consider that to construct a sum type like Either a b it’s enough to provide a value of either type a or type b. Once the Either is constructed, the information about which one was used is lost. If you want to use an Either, you have to provide two functions, one for each of the two branches of the case statement. Similarly, to construct SomeVect its enough to provide a vector of some particular lenght n. Instead of having two possibilities of Either, we have infinitely many possibilities corresponding to different n‘s. The information about what n was used is then promptly lost.

The sum in the definition of the polynomial lens:

$\sum_{n} a_n \times [b_n, t_k]$

can be encoded in this existential type:

data SomePair : Nt -> Nt -> Nt -> Type where
HidePair : {n : Nat} ->
(k : Nat) -> a n -> (b n -> t k) -> SomePair a b t

Notice that we are hiding n, but not k.

Taking it all together, we end up with the following type definition:

PolyLens : Nt -> Nt -> Nt -> Nt -> Type
PolyLens s t a b = {k : Nat} -> s k -> SomePair a b t

The way we read this definition is that PolyLens is a function polymorphic in k. Given a value of the type s k it produces and existential pair SomePair a b t. This pair contains a value of the type a n and a function b n -> t k. The important part is that the value of n is hidden from the caller inside the existential type.

Using the Lens

Because of the existential type, it’s not immediately obvious how one can use the polynomial lens. For instance, we would like to be able to extract the foci a n, but we don’t know what the value of n is. The trick is to hide n inside an existential Some. Here is the “getter” for this lens:

getLens :  PolyLens sn tn an bn -> sn n -> Some an
getLens lens t =
let  HidePair k v _ = lens t
in Hide v

We call lens with the argument t, pattern match on the constructor HidePair and immediately hide the contents back using the constructor Hide. The compiler is smart enough to know that the existential value of n hasn’t been leaked.

The second component of SomePair, the “setter”, is trickier to use because, without knowing the value of n, we don’t know what argument to pass to it. The trick is to take advantage of the match between the producer and the consumer that are the two components of the existential pair. Without disclosing the value of n we can take the a‘s and use a polymorphic function to transform them into b‘s.

transLens : PolyLens sn tn an bn -> ({n : Nat} -> an n -> bn n)
-> sn n -> Some tn
transLens lens f t =
let  HidePair k v vt = lens t
in  Hide (vt (f v))

The polymorphic function here is encoded as ({n : Nat} -> an n -> bn n). (An example of such a function is sortV.) Again, the value of n that’s hidden inside SomePair is never leaked.

Example

Let’s get back to our example: a polynomial lens that focuses on the leaves of a tree. The type signature of such a lens is:

treeLens : PolyLens (Tree a) (Tree b) (Vect a) (Vect b)

Using this lens we should be able to retrieve a vector of leaves Vect a n from a node-counted tree Tree a k and replace it with a new vector Vect b n to get a tree Tree b k. We should be able to do it without ever disclosing the number of leaves n.

To implement this lens, we have to write a function that takes a tree of a and produces a pair consisting of a vector of a‘s and a function that takes a vector of b‘s and produces a tree of b‘s. The type b is fixed in the signature of the lens. In fact we can pass this type to the function we are implementing. This is how it’s done:

treeLens : PolyLens (Tree a) (Tree b) (Vect a) (Vect b)
treeLens {b} t = replace b t

First, we bring b into the scope of the implementation as an implicit parameter {b}. Then we pass it as a regular type argument to replace. This is the signature of replace:

replace : (b : Type) -> Tree a n -> SomePair (Vect a) (Vect b) (Tree b)

We’ll implement it by pattern-matching on the tree.

The first case is easy:

replace b Empty = HidePair 0 VNil (\v => Empty)

For an empty tree, we return an empty vector and a function that takes and empty vector and recreates and empty tree.

The leaf case is also pretty straightforward, because we know that a leaf contains just one value:

replace b (Leaf x) = HidePair 1 (VCons x VNil)
(\(VCons y VNil) => Leaf y)

The node case is more tricky, because we have to recurse into the subtrees and then combine the results.

replace b (Node t1 t2) =
let (HidePair k1 v1 f1) = replace b t1
(HidePair k2 v2 f2) = replace b t2
v3 = concatV v1 v2
f3 = compose f1 f2
in HidePair (S (plus k2 k1)) v3 f3

Combining the two vectors is easy: we just concatenate them. Combining the two functions requires some thinking. First, let’s write the type signature of compose:

compose : (Vect b n -> Tree b k) -> (Vect b m -> Tree b j) ->
(Vect b (plus n m)) -> Tree b (S (plus j k))

The input is a pair of functions that turn vectors into trees. The result is a function that takes a larger vector whose size is the sume of the two sizes, and produces a tree that combines the two subtrees. Since it adds a new node, its node count is the sum of the node counts plus one.

Once we know the signature, the implementation is straightforward: we have to split the larger vector and pass the two subvectors to the two functions:

compose {n} f1 f2 v =
let (v1, v2) = splitV n v
in Node (f1 v1) (f2 v2)

The split is done by looking at the type of the first argument (Vect b n -> Tree b k). We know that we have to split at n, so we bring {n} into the scope of the implementation as an implicit parameter.

Besides the type-changing lens (that changes a to b), we can also implement a simple lens:

treeSimpleLens : PolyLens (Tree a) (Tree a) (Vect a) (Vect a)
treeSimpleLens {a} t = replace a t

We’ll need it later for testing.

Testing

To give it a try, let’s create a small tree with five nodes and three leaves:

t3 : Tree Char 5
t3 = (Node (Leaf 'z') (Node (Leaf 'a') (Leaf 'b')))

We can extract the leaves using our lens:

getLeaves : Tree a n -> SomeVect a
getLeaves t = getLens treeSimpleLens t

As expected, we get a vector containing 'z', 'a', and 'b'.

We can also transform the leaves using our lens and the polymorphic sort function:

trLeaves : ({n : Nat} -> Vect a n -> Vect b n) -> Tree a n -> SomeTree b
trLeaves f t = transLens treeLens f t
trLeaves sortV

The result is a new tree: ('a',('b','z'))

Complete code is available on github.

A PDF of this post is available on github

Motivation

Lenses seem to pop up in most unexpected places. Recently a new type of lens showed up as a set of morphisms between polynomial functors. This lens seemed to not fit the usual classification of optics, so it was not immediately clear that it had an existential representation using coends and, consequently a profunctor representation using ends. A profunctor representation of optics is of special interest since it lets us compose optics using standard function composition. In this post I will show how the polynomial lens fits into the framework of general optics.

Polynomial Functors

A polynomial functor in $\mathbf{Set}$ can be written as a sum (coproduct) of representables:

$P(y) = \sum_{n \in N} s_n \times \mathbf{Set}(t_n, y)$

The two families of sets, $s_n$ and $t_n$ are indexed by elements of the set $N$ (in particular, you may think of it as a set of natural numbers, but any set will do). In other words, they are fibrations of some sets $S$ and $T$ over $N$. In programming we call such families dependent types. We can also think of these fibrations as functors from a discrete category $\mathcal{N}$ to $\mathbf{Set}$.

Since, in $\mathbf{Set}$, the internal hom is isomorphic to the external hom, a polynomial functor is sometimes written in the exponential form, which makes it look more like an actual polynomial or a power series:

$P(y) = \sum_{n \in N} s_n \times y^{t_n}$

or, by representing all sets $s_n$ as sums of singlentons:

$P(y) = \sum_{n \in N} y^{t_n}$

I will also use the notation $[t_n, y]$ for the internal hom:

$P(y) = \sum_{n \in N} s_n \times [t_n, y]$

Polynomial functors form a category $\mathbf{Poly}$ in which morphisms are natural transformations.

Consider two polynomial functors $P$ and $Q$. A natural transformation between them can be written as an end. Let’s first expand the source functor:

$\mathbf{Poly}\left( \sum_k s_k \times [t_k, -], Q\right) = \int_{y\colon \mathbf{Set}} \mathbf{Set} \left(\sum_k s_k \times [t_k, y], Q(y)\right)$

The mapping out of a sum is isomorphic to a product of mappings:

$\cong \prod_k \int_y \mathbf{Set} \left(s_k \times [t_k, y], Q(y)\right)$

We can see that a natural transformation between polynomials can be reduced to a product of natural transformations out of monomials. So let’s consider a mapping out of a monomial:

$\int_y \mathbf{Set} \left( s \times [t, y], \sum_n a_n \times [b_n, y]\right)$

We can use the currying adjunction:

$\int_y \mathbf{Set} \left( [t, y], \left[s, \sum_n a_n \times [b_n, y]\right] \right)$

or, in $\mathbf{Set}$:

$\int_y \mathbf{Set} \left( \mathbf{Set}(t, y), \mathbf{Set} \left(s, \sum_n a_n \times [b_n, y]\right) \right)$

We can now use the Yoneda lemma to eliminate the end. This will simply replace $y$ with $t$ in the target of the natural transformation:

$\mathbf{Set}\left(s, \sum_n a_n \times [b_n, t] \right)$

The set of natural transformation between two arbitrary polynomials $\sum_k s_k \times [t_k, y]$ and $\sum_n a_n \times [b_n, y]$ is called a polynomial lens. Combining the previous results, we see that it can be written as:

$\mathbf{PolyLens}\langle s, t\rangle \langle a, b\rangle = \prod_{k \in K} \mathbf{Set}\left(s_k, \sum_{n \in N} a_n \times [b_n, t_k] \right)$

Notice that, in general, the sets $K$ and $N$ are different.

Using dependent-type language, we can describe the polynomial lens as acting on a whole family of types at once. For a given value of type $s_k$ it determines the index $n$. The interesting part is that this index and, consequently, the type of the focus $a_n$ and the type on the new focus $b_n$ depends not only on the type but also on the value of the argument $s_k$.

Here’s a simple example: consider a family of node-counted trees. In this case $s_k$ is a type of a tree with $k$ nodes. For a given node count we can still have trees with a different number of leaves. We can define a poly-lens for such trees that focuses on the leaves. For a given tree it produces a counted vector $a_n$ of leaves and a function that takes a counted vector $b_n$ (same size, but different type of leaf) and returns a new tree $t_k$.

Lenses and Kan Extensions

After publishing an Idris implementation of the polynomial lens, Baldur Blöndal (Iceland Jack) made an interesting observation on Twitter: The sum type in the definition of the lens looks like a left Kan extension. Indeed, if we treat $a$ and $b$ as co-presheaves, the left Kan extension of $a$ along $b$ is given by the coend:

$Lan_b a \cong \int^{n \colon \mathcal{N}} a \times [b, -]$

A coend over a discrete category is a sum (coproduct), since the co-wedge condition is trivially satisfied.

Similarly, an end over a discrete category $\mathcal{K}$ becomes a product. An end of hom-sets becomes a natural transformation. A polynomial lens can therefore be rewritten as:

$\prod_{k \in K} \mathbf{Set}\left(s_k, \sum_{n \in N} a_n \times [b_n, t_k] \right) \cong [\mathcal{K}, \mathbf{Set}](s, (Lan_b a) \circ t)$

Finally, since the left Kan extension is the left adjoint of functor pre-composition, we get this very compact formula:

$\mathbf{PolyLens}\langle s, t\rangle \langle a, b\rangle \cong [\mathbf{Set}, \mathbf{Set}](Lan_t s, Lan_b a)$

which works for arbitrary categories $\mathcal{N}$ and $\mathcal{K}$ for which the relevant Kan extensions exist.

Existential Representation

A lens is just a special case of optics. Optics have a very general representation as existential types or, categorically speaking, as coends.

The general idea is that optics describe various modes of decomposing a type into the focus (or multiple foci) and the residue. This residue is an existential type. Its only property is that it can be combined with a new focus (or foci) to produce a new composite.

The question is, what’s the residue in the case of a polynomial lens? The intuition from the counted-tree example tells us that such residue should be parameterized by both, the number of nodes, and the number of leaves. It should encode the shape of the tree, with placeholders replacing the leaves.

In general, the residue will be a doubly-indexed family $c_{m n}$ and the existential form of poly-lens will be implemented as a coend over all possible residues:

$\mathbf{Pl}\langle s, t\rangle \langle a, b\rangle \cong$

$\int^{c_{k i}} \prod_{k \in K} \mathbf{Set} \left(s_k, \sum_{n \in N} a_n \times c_{n k} \right) \times \prod_{i \in K} \mathbf{Set} \left(\sum_{m \in N} b_m \times c_{m i}, t_i \right)$

To see that this representation is equivalent to the previous one let’s first rewrite a mapping out of a sum as a product of mappings:

$\prod_{i \in K} \mathbf{Set} \left(\sum_{m \in N} b_m \times c_{m i}, t_i \right) \cong \prod_{i \in K} \prod_{m \in N} \mathbf{Set}\left(b_m \times c_{m i}, t_i \right)$

and use the currying adjunction to get:

$\prod_{i \in K} \prod_{m \in N} \mathbf{Set}\left(c_{m i}, [b_m, t_i ]\right)$

The main observation is that, if we treat the sets $N$ and $K$ as a discrete categories $\mathcal{N}$ and $\mathcal{K}$, a product of mappings can be considered a natural transformation between functors. Functors from a discrete category are just mappings of objects, and naturality conditions are trivial.

A double product can be considered a natural transformation from a product category. And since a discrete category is its own opposite, we can (anticipating the general profunctor case) rewrite our mappings as natural transformations:

$\prod_{i \in K} \prod_{m \in N} \mathbf{Set} \left(c_{m i}, [b_m, t_i] \right) \cong [\mathcal{N}^{op} \times \mathcal{K}, \mathbf{Set}]\left(c_{= -}, [b_=, t_- ]\right)$

The indexes were replaced by placeholders. This notation underscores the interpretation of $b$ as a functor (co-presheaf) from $\mathcal{N}$ to $\mathbf{Set}$, $t$ as a functor from $\mathcal{K}$ to $\mathbf{Set}$, and $c$ as a profunctor on $\mathcal{N}^{op} \times \mathcal{K}$.

We can therefore use the co-Yoneda lemma to eliminate the coend over $c_{ki}$. The result is that $\mathbf{Pl}\langle s, t\rangle \langle a, b\rangle$ can be wrtitten as:

$\int^{c_{k i}} \prod_{k \in K} \mathbf{Set} \left(s_k, \sum_{n \in N} a_n \times c_{n k} \right) \times [\mathcal{N}^{op} \times \mathcal{K}, \mathbf{Set}]\left(c_{= -}, [b_=, t_- ]\right)$

$\cong \prod_{k \in K} \mathbf{Set}\left(s_k, \sum_{n \in N} a_n \times [b_n, t_k] \right)$

which is exactly the original polynomial-to-polynomial transformation.

Acknowledgments

I’m grateful to David Spivak, Jules Hedges and his collaborators for sharing their insights and unpublished notes with me, especially for convincing me that, in general, the two sets $N$ and $K$ should be different.

A PDF of this post is available on github.

Motivation

A lens is a reification of the concept of object composition. In a nutshell, it describes the process of decomposing the source object $s$ into a focus $a$ and a residue $c$ and recomposing a new object $t$ from a new focus $b$ and the same residue $c$.

The key observation is that we don’t care what the residue is as long as it exists. This is why a lens can be implemented, in Haskell, as an existential type:

data Lens s t a b where
Lens :: (s -> (c, a)) -> ((c, b) -> t) -> Lens s t a b


In category theory, the existential type is represented as a coend—essentially a gigantic sum over all objects $c$ in the category $\mathcal{C}$:

$\mathcal{L}\langle s, t\rangle \langle a, b \rangle = \int^{c \colon \mathcal{C}} \mathcal{C}(s, c \times a) \times \mathcal{C}(c \times b, t)$

There is a simple recipe to turn this representation into the more familiar one. The first step is to use the currying adjunction on the second hom-functor:

$\mathcal{C}(c \times b, t) \cong \mathcal{C}(c, [b, t])$

Here, $[b, t]$ is the internal hom, or the function object (b->t).
Once the object $c$ appears as the source in the hom-set, we can use the co-Yoneda lemma to eliminate the coend. This is the formula we use:

$\int^c F c \times \mathcal{C}(c, x) \cong F x$

It works for any functor $F$ from the category $\mathcal{C}$ to $\mathbf{Set}$ so, in particular we have:

$\mathcal{L}\langle s, t\rangle \langle a, b \rangle \cong \int^{c} \mathcal{C}(s, c \times a) \times \mathcal{C}(c, [b, t]) \cong \mathcal{C}(s, [b, t] \times a)$

The result is a pair of arrows:

$\mathcal{C}(s, [b, t]) \times \mathcal{C}(s, a)$

the first corrsponding to:

set :: s -> b -> t


and the second to:

get :: s -> a


It turns out that this trick works for more general optics. It all depends on being able to isolate the object $c$ as the source of the second hom-set.

We’ve been able to do it case-by-case for lenses, prisms, traversals, and the whole zoo of optics. It turns out that the same problem was studied in all its generality by Australian category theorists Janelidze and Kelly in a context that had nothing to do with optics.

Monoidal Actions

Here’s the most general definition of an optic:

$\mathcal{O}\langle s, t\rangle \langle a, b \rangle = \int^{c \colon \mathcal{M}} \mathcal{D}(s, K_c a) \times \mathcal{C}(L_c b, t)$

This definition involves three separate categories. The category $\mathcal{M}$ is monoidal, and it has an action defiend on both $\mathcal{C}$ and $\mathcal{D}$. A category with a monoidal action is called an actegory.

We get the definition of a lens by having all three categories be the same—a cartesian closed category $\mathcal{C}$. We define the action of this category on itself:

$L_c a = c \times a$

(and the same for $K_c$).

There are two equivalent ways of defining the action of a monoidal category. One is as the mapping

$\bullet \colon \mathcal{M} \times \mathcal{C} \to \mathcal{C}$

written in infix notation as $c \bullet a$. It has to be equipped with two additional structure maps—isomorphisms that relate the tensor product $\otimes$ in $\mathcal{M}$ and its unit $I$ to the action in $\mathcal{C}$:

$\alpha_{d c a} \colon (d \otimes c) \bullet a \to d \bullet (c \bullet a)$

$\lambda_a \colon I \bullet a \to a$

plus some coherence conditions corresponding to associativity and unit laws.

Using this notation, we can rewrite the definition of an optic as:

$\mathcal{O}\langle s, t\rangle \langle a, b \rangle = \int^{c \colon \mathcal{M}} \mathcal{D}(s, c \bullet a) \times \mathcal{C}(c \bullet b, t)$

with the understanding that we use the same symbol for two different actions in $\mathcal{C}$ and $\mathcal{D}$.

Alternatively, we can curry the action $\bullet$, and use the mapping:

$L \colon \mathcal{M} \to [\mathcal{C}, \mathcal{C}]$

The target category here is the category of endofunctors $[\mathcal{C}, \mathcal{C}]$, which is naturally equipped with a monoidal structure given by functor composition (and, as we well know, a monad is just a monoid in that category).

The two structure maps from the definition of $\bullet$ translate to the requirement that $L$ be a strict monoidal functor, mapping tensor product to functor composition and unit object to identity functor.

When we were eliminating the coend in the definition of a lens, we used the currying adjunction. This particular adjunction works inside a single category but, in general, an adjunction relates two functors between a pair of categories. Therefore, to eliminate the end from the optic, we need an adjunction that looks like this:

$\mathcal{C}(c \bullet a, t) \cong \mathcal{M}(c, R_a t)$

The category on the right is the monoidal category $\mathcal{M}$, because $c$ is the object from this category.

Using the adjunction and the co-Yoneda lemma we get:

$\mathcal{O}\langle s, t\rangle \langle a, b \rangle = \int^{c \colon \mathcal{M}} \mathcal{D}(s, c \bullet a) \times \mathcal{M}(c, R_b t) \cong \mathcal{D}(s, R_b t \bullet a)$

There is a whole slew of monoidal actions that have the right adjoint of this type. Let’s look at an example.

The category of sets is a monoidal category, and we can define its action on another category using the formula:

$\mathcal{C}(c \cdot a, t) \cong \mathbf{Set}(c, \mathcal{C}(a, t))$

This is the definition of a copower. A category in which this adjunction holds for all objects is called copowered or tensored over $\mathbf{Set}$.

The intuition is that a copower is like an iterated sum (hence the multiplication sign). Indeed, a mapping out of a coproduct of $c$ copies of $a$, where $c$ is a set, is equivalent to $c$ mappings out of $a$.

This formula generalizes to the case in which $\mathcal{C}$ is a category enriched over a monoidal category $\mathcal{V}$. In that case we have:

$\mathcal{C}(c \cdot a, t) \cong \mathcal{V}(c, \mathcal{C}(a, t))$

Here, the hom $\mathcal{C}(a, t)$ is an object in $\mathcal{V}$.

Relation to Enrichment

We are interested in the adjunction:

$\mathcal{C}( c \bullet a, t) \cong \mathcal{M}(c, R_a t)$

The functor $R$ is covariant in $t$ and contravariant in $a$:

$R \colon \mathcal{C}^{op} \times \mathcal{C} \to \mathcal{M}$

In other words, it’s a profunctor. In fact, it has the right signature to be a hom-functor. And this is what Janelidze and Kelly show: the functor $R$ can serve as the hom-functor that generates the enrichment for $\mathcal{C}$. If we call the enriched category $\mathbf{C}$, we can define the hom-object as:

$\mathbf{C}(a, t) = R_a t$

Our adjunction can be rewritten as:

$\mathcal{C}( c \bullet a, t) \cong \mathcal{M}(c, \mathbf{C}(a, t))$

The counit of this adjunction is a mapping:

$\epsilon_{a t} \colon \mathbf{C}(a, t) \bullet a \to t$

which is analogous to function application.

The hom-object $\mathbf{C}(a, t)$ in an enriched category must satisfy the composition and identity laws. In an enriched category, composition is a mapping:

$\circ \colon \mathbf{C}(b, t) \otimes \mathbf{C}(a, b) \to \mathbf{C}(a, t)$

Let’s see if we can get this mapping from our adjunction by replacing $c$ with $\mathbf{C}(b, t) \otimes \mathbf{C}(a, b)$. We get:

$\mathcal{C}( (\mathbf{C}(b, t) \otimes \mathbf{C}(a, b)) \bullet a, t) \cong \mathcal{M}(\mathbf{C}(b, t) \otimes \mathbf{C}(a, b), \mathbf{C}(a, t))$

The right-hand side should contain the mapping we’re looking for. All we need is to point at a morphism on the left. Indeed, we can define it as the following composite:

$\big( \mathbf{C}(b, t) \otimes \mathbf{C}(a, b)\big) \bullet a \xrightarrow{\alpha}$

$\mathbf{C}(b, c) \bullet \big(\mathbf{C}(a, b)) \bullet a\big) \xrightarrow{id \; \bullet \; \epsilon}$

$\mathbf{C}(b, t) \bullet b \xrightarrow{\epsilon} t$

We used the structure map $\alpha$ and (twice) the counit of the adjunction $\epsilon$.

Similarly, the identity of composition, which is the mapping:

$id_a \colon I \to \mathbf{C}(a, a)$

is adjoint to the other structure map $\lambda_a$.

Janelidze and Kelly go on to prove that the action of a monoidal right-closed category having the right adjoint is equivalent to the existence of the tensored enrichment of the category on which this action is defined.

The two examples of monoidal actions we’ve seen so far are indeed equivalent to enrichments. A cartesian closed category in which we defined the action $L_c a = c \times a$ is automatically self-enriched. The copower action $L_c a = c \cdot a$ is equivalent to enrichment over $\mathbf{Set}$ (which doesn’t mean much, since regular categories are naturally $\mathbf{Set}$-enriched; but not all of them are tensored).

Acknowledgments

I’m grateful to Jules Hedges and his collaborators for sharing their insights and unpublished notes with me.

Category theory extracts the essence of structure and composition. At its foundation it deals with the composition of arrows. Building on composition of arrows it then goes on describing the ways objects can be composed: we have products, coproducts and, at a higher level, tensor products. They all describe various modes of composing objects. In monoidal categories any two objects can be composed.

Unlike composition, which can be described uniformly, decomposition requires case-by-case treatment. It’s easy to decompose a cartesian product using projections. A coproduct (sum) can be decomposed using pattern matching. A generic tensor product, on the other hand, has no standard means of decompositon.

Optics is the essence of decomposition. It answers the question of what it means to decompose a composite.

We consider an object decomposable when:

• We can split it into the focus and the complement,
• We can replace the focus with something else, without changing the complement, to get a new composite object,
• We can zoom in; that is, if the focus is decomposable, we can compose the two decompositions,
• It’s possible for the whole object to be the focus.

Let’s translate these requirements into the language of category theory. We’ll start with the standard example: the lens, which is the optic for decomposing cartesian products.

The splitting means that there is a morphism from the composite object $s$ to the product $c \times a$, where $c$ is the complement and $a$ is the focus. This morphism is a member of the hom-set $\mathcal{C}(s, c \times a)$.

To replace the focus we need another morphism that takes the same complement $c$, combines it with the new focus $b$ to produce the new composite $t$. This morphism is a member of the hom-set $\mathcal{C}(c \times b, t)$

Here’s the important observation: We don’t care what the complement is. We are “focusing” on the focus. We carry the complement over to combine it with the new focus, but we don’t use it for anything else. It’s a featureless black box.

To erase the identity of the complement, we hide it inside a coend. A coend is a generalization of a sum, so it is written using the integral sign (see the Appendix for details). Programmers know it as an existential type, logicians call it an existential quantifier. We say that there exists a complement $c$, but we don’t care what it is. We “integrate” over all possible complements.

Here’s the existential definition of the lens:

$L(s, t; a, b) = \int^{c : \mathcal{C}} \mathcal{C}(s, c \times a) \times \mathcal{C}(c \times b, t)$

Just like we construct a coproduct using one of the injections, so the coend is constructed using one of (possibly infinite number of) injections. In our case we construct a lens $L(s, t; a, b)$ by injecting a pair of morphisms from the two hom-sets sharing the same $c$. But once the lens is constructed, there is no way to extract the original $c$ from it.

It’s not immediately obvious that this representation of the lens reproduces the standard setter/getter form. However, in a cartesian closed category, we can use the currying adjunction to transform the second hom-set:

$\mathcal{C}(c \times b, t) \cong \mathcal{C}(c, [b, t])$

Here, $[b, t]$ is the internal hom, or the function object representing morphisms from $b$ to $t$. We can then use the co-Yoneda lemma to reduce the coend:

$\int^{c : \mathcal{C}} \mathcal{C}(s, c \times a) \times \mathcal{C}(c, [b, t]) \cong \mathcal{C}(s, [b, t] \times a) \cong \mathcal{C}(s \times b, t) \times \mathcal{C}(s, a)$

The first part of this product is the setter: it takes the source object $s$ and the new focus $b$ to produce the new target $t$. The second part is the getter that extracts the focus $a$.

Even though all optics have similar form, each of them reduces differently.

Here’s another example: the prism. We just replace the product with the coproduct (sum).

$P(s, t; a, b) = \int^{c : \mathcal{C}} \mathcal{C}(s, c + a) \times \mathcal{C}(c + b, t)$

This time the reduction goes through the universal property of the coproduct: a mapping out of a sum is a product of mappings:

$\mathcal{C}(c + b, t) \cong\mathcal{C}(c, t) \times\mathcal{C}(b, t)$

Again, we use the co-Yoneda to reduce the coend:

$\int^{c : \mathcal{C}} \mathcal{C}(s, c + a) \times\mathcal{C}(c, t) \times\mathcal{C}(b, t) \cong\mathcal{C}(s, t + a) \times\mathcal{C}(b, t)$

The first one extracts the focus $a$, if possible, otherwise it constructs a $t$ (by secretly injecting a $c$). The second constructs a $t$ by injecting a $b$.

We can easily generalize existential optics to an arbitrary tensor product in a monoidal category:

$O(s, t; a, b) = \int^{c : \mathcal{C}} \mathcal{C}(s, c \otimes a) \times \mathcal{C}(c \otimes b, t)$

In general, though, this form cannot be further reduced using the co-Yoneda trick.

But what about the third requirement: the zooming-in property of optics? In the case of the lens and the prism it works because of associativity of the product and the sum. In fact it works for any tensor product. If you can decompose $s$ into $c \otimes a$, and further decompose $a$ into $c' \otimes a'$, then you can decompose $s$ into $(c \otimes c') \otimes a'$. Zooming-in is made possible by the associativity of the tensor product.

Focusing on the whole object plays the role of the unit of zooming.

These two properties are used in the definition of the category of optics. The objects in this category are pairs of object in $\mathcal{C}$. A morphism from a pair $\langle s, t \rangle$ to $\langle a, b \rangle$ is the optic $O(s, t; a, b)$. Zooming-in is the composition of morphisms.

But this is still not the most general setting. The useful insight is that the multiplication (product) in a lens, and addition (coproduct) in a prism, look like examples of linear transformations, with the residue $c$ playing the role of a parameter. In fact, a composition of a lens with a prism produces a 2-parameter affine transformation, which also behaves like an optic. We can therefore generalize optics to work with an arbitrary monoidal action (first hinted in the discussion at the end of this blog post). Categories with such actions are known as actegories.

The idea is that you define a family of endofunctors $A_m$ in $\mathcal{C}$ that is parameterized by objects from a monoidal category $\mathcal{M}$. So far we’ve only discussed examples where the parameters were taken from the same category $\mathcal{C}$ and the action was either multiplication or addition. But there are many examples in which $\mathcal{M}$ is not the same as $\mathcal{C}$.

The zooming principles are satisfied if the action respects the tensor product in $\mathcal{M}$:

$A_{m \otimes n} \cong A_m \circ A_n$

$A_1 \cong \mathit{Id}$

(Here, $1$ is the unit object with respect to the tensor product $\otimes$ in $\mathcal{M}$, and $\mathit{Id}$ is the identity endofunctor.)

The actegorical version of the optic doesn’t deal directly with the residue. It tells us that the “unimportant” part of the composite object can be parameterized by some $m \colon \mathcal{M}$.

This additional abstraction allows us to transport the residue between categories. It’s enough that we have one action $L_m$ in $\mathcal{C}$ and another $R_m$ in $\mathcal{D}$ to create this mixed optics (first introduced by Mitchell Riley):

$O(s, t; a, b) = \int^{m : \mathcal{M}} \mathcal{C}(s, L_m a) \times \mathcal{D}(R_m b, t)$

The separation of the focus from the complement using monoidal actions is reminiscent of what physicists call the distinction between “physical”  and “gauge” degrees of freedom.

An in-depth presentation of optics, including their profunctor representation, is available in this paper.

Appendix: Coends and the Co-Yoneda Lemma

A coend is defined for a profunctor, that is a functor of two variables, one contravariant and one covariant, $p \colon \mathcal{C}^{op} \times \mathcal{C} \to \mathbf{Set}$. It’s a cross between a coproduct and a trace, as it’s constructed using injections of diagonal elements (with some identifications):

$\iota_{a} \colon p \langle a, a \rangle \to \int^{c : \mathcal{C}} p \langle c, c \rangle$

Co-Yoneda lemma is the identity that works for any covariant functor (copresheaf) $F \colon \mathcal{C} \to \mathbf{Set}$:

$\int^{c \colon \mathcal{C}} F(c) \times \mathcal{C}(c, x) \cong F(x)$

Dependent types, in programming, are families of types indexed by elements of an indexing type. For instance, counted vectors are families of tuples indexed by natural numbers—the lengths of the vectors.

In category theory we model dependent types as fibrations. We start with the total space $E$, the base space $B$, and a projection, or a display map, $p \colon E \to B$. The fibers of $p$ correspond to members of the type family. For instance, the total space, or the bundle, of counted vectors is the list type $\mathit{List} (A)$ (a free monoid generated by $A$) with the projection $\mathit{len} \colon \mathit{List} (A) \to \mathbb{N}$ that returns the length of a list.

Another way of looking at dependent types is as objects in the slice category $\mathcal{C}/B$. Counted vectors, for instance, are represented as objects in $\mathcal{C}/\mathbb{N}$ given by pairs $\langle \mathit{List} (A), \mathit{len} \rangle$. Morphisms in the slice category correspond to fibre-wise mappings between bundles.

We often require that $\mathcal{C}$ be a locally cartesian closed category, that is a category whose slice categories are cartesian closed. In such categories, the base-change functor $f^*$ has both the left adjoint, the dependent sum $\Sigma_f$; and the right adjoint, the dependent product $\Pi_f$. The base-change functor is defined as a pullback:

This pullback defines a cartesian product in the slice category $\mathcal{C}/B$ between two objects: $\langle B', f \rangle$ and $\langle E, p \rangle$. In a locally cartesian closed category, this product has the right adjoint, the internal hom in $\mathcal{C}/B$.

Dependent optics

The most general optic is given by two monoidal actions $L_m$ and $R_m$ in two categories $\mathcal{C}$ and $\mathcal{D}$. It can be written as the following coend of the product of two hom-sets:

$O(A, A'; S, S') = \int^{m \colon \mathcal{M}} \mathcal{C}( S, L_m A) \times \mathcal{D}(R_m A', S')$

Monoidal actions are parameterized by objects in a monoidal category $(\mathcal{M}, \otimes, 1)$.

Dependent optics are a special case of general optics, where one or both categories in question are slice categories. When the monoidal action is defined in the slice category, the transformations must respect fibrations. For instance, the action in the bundle $\langle E, p \rangle$ over $B$ must commute with the projection:

$p \circ L_m = p$

This is reminiscent of gauge transformations in physics, which act on fibers in bundles over spacetime. The action must respect the monoidal structure of $\mathcal{M}$ so, for instance,

$L_{m \otimes n} \cong L_m \circ L_n$

$L_1 \cong \mathit{Id}$

We can define a dependent (mixed) optic as:

$\int^{m : \mathcal{M}} (\mathcal{C}/B)( S, L_m A) \times (\mathcal{D}/B')(R_m A', S')$

Just like regular optics, dependent optics can be represented using Tambara modules, which are profunctors with the additional structure given by transformations:

$\alpha_{m, \langle A, A' \rangle} \colon P \langle A, A' \rangle \to P\langle L_m A, R_m A' \rangle$

where $A$ and $A'$ are objects in the appropriate slice categories.
The optic is then given by the following end in the Tambara category:

$O(A, A'; S, S') = \int_{p : \mathbf{Tam}} \mathbf{Set}(P \langle A, A' \rangle, P \langle S, S' \rangle)$

Dependent lens

The primordial optic, the lens, is defined by the monoidal action of a product. By analogy, we define a dependent lens by the action of the product in a slice category. The action parameterized by an object $\langle C, q \rangle$ on another object $\langle A, p \rangle$ is given by the pullback:

$M_C A = C \times_B A$

Since a pullback is the product in the slice category $\mathcal{C}/B$, it is automatically associative and unital, so it can be used to define a dependent lens:

$\mathit{DLens}(A, A'; S, S') = \int^{\langle C, p \rangle : \mathcal{C}/B} (\mathcal{C}/B)( S, C \times_B A) \times (\mathcal{C}/B)(C \times_B A', S')$

Since $\mathcal{C}$ is locally cartesian closed, there is an adjunction between the product and the exponential. We can use it to get:

$\cong \int^{\langle C, p \rangle : \mathcal{C}/B} (\mathcal{C}/B)( S, C \times_B A) \times (\mathcal{C}/B)(C , [A', S']_B)$

We can then apply the Yoneda lemma to get the setter/getter form:

$(\mathcal{C}/B)( S, [A', S']_B \times_B A)$

The internal hom $[A', S']_B$ in a locally cartesian closed category can be expressed using a dependent product:

$\left [\left \langle A' \atop p \right \rangle, \left \langle S' \atop q \right \rangle \right ] \cong \Pi_p \left(p^* \left \langle S' \atop q \right \rangle \right)$

where $p \colon A' \to B$ is the fibration of $A'$, $\Pi_p$ is the right adjoint to the base change functor, and $p^*$ is the base-change functor along $p$.

The dependent lens can be written as:

$(\mathcal{C} / B) \left( \left \langle S \atop r \right \rangle, \Pi_p \left(p^* \left \langle S' \atop q \right \rangle \right) \times \left \langle A \atop r' \right \rangle \right)$

In particular, if $B$ is $\mathbb{N}$, this is equal to an infinite tuple of functions:

$O(A, B; S, T) \cong \prod_n \left( s_n \to \left((b_n \to t_n) \times a_n \right) \right)$

or fiber-wise pairs of setter/getter $\langle s_n \to b_n \to t_n, s_n \to a_n \rangle$ indexed by $n$.

Traversals

Traversals are optics whose monoidal action is generated by polynomial functors of the form:

$M_{c} a = \sum_{n \colon \mathbb{N}} c_n \times a^n$

The coefficients $c_n$ can be expressed as a fibration $\langle C, p \colon C \to \mathbb{N} \rangle$, with $C = \sum_n c_n$, the sum of the fibers. The set of powers of $a$ can be similarly written as $\langle L(a), \mathit{len} \rangle$, with $L(a)$ the type of list of $a$ (a free monoid generated by $a$), and $\mathit{len}$ the function that assigns the length to a list. The monoidal action can then be written using a product (pullback) in the slice category $\mathbf{Set}/\mathbb{N}$:

$\left \langle {C \atop p} \right \rangle \times \left \langle {L(a) \atop \mathit{len}} \right \rangle$

There is an obvious forgetful functor $U \colon \mathbf{Set}/\mathbb{N} \to \mathbf{Set}$, which can be used to express the polynomial action:

$M_c a = U\left( \left \langle {C \atop p} \right \rangle \times \left \langle {L(a) \atop \mathit{len}} \right \rangle \right)$

The traversal is the optic:

$\int^{\langle C, p \rangle : \mathbf{Set}/\mathbb{N}} \mathbf{Set} \left(s, M_c a \right) \times \mathbf{Set}(M_c b, t)$

Eqivalently, the second factor can be rewritten as:

$\mathbf{Set}\left( \sum_{n \colon \mathbb{N}} c_n \times b^n, t\right) \cong \prod_{n \colon \mathbb{N}} \mathbf{Set}(c_n \times b^n, t)$

This, in turn, is equivalent to a single hom-set in the slice category:

$\cong (\mathbf{Set}/\mathbb{N})\left(\left \langle {C \atop p} \right \rangle \times \left \langle {L(b) \atop \mathit{len}} \right \rangle, \left \langle {\mathbb{N} \times t \atop \pi_1} \right \rangle \right)$

where $\pi_1$ is the projection from the cartesian product.

The traversal is therefore a mixed optic:

$\int^{\langle C, p \rangle : \mathbf{Set}/\mathbb{N}} \mathbf{Set} \left(s, M_c a \right) \times (\mathbf{Set}/\mathbb{N})\left( \left \langle {C \atop p} \right \rangle \times \left \langle {L(b) \atop \mathit{len}} \right \rangle, \left \langle {\mathbb{N} \times t \atop \pi_1} \right \rangle \right)$

The second factor can be transformed using the internal hom adjunction:

$(\mathbf{Set}/\mathbb{N})\left(\left \langle {C \atop p} \right \rangle, \left[ \left \langle {L(b) \atop \mathit{len}} \right \rangle, \left \langle {\mathbb{N} \times t \atop \pi_1} \right \rangle \right] \right)$

We can then use the ninja Yoneda lemma on the optic to “integrate” over $\langle C, p \rangle$ and get:

$O(a, b; s, t) \cong \mathbf{Set} \left( s, U\left( \left[ \left \langle {L(b) \atop \mathit{len}} \right \rangle, \left \langle {\mathbb{N} \times t \atop \pi_1} \right \rangle \right] \times \left \langle {L(a) \atop \mathit{len}} \right \rangle \right) \right)$

$s \to \sum_n \left( (b^n \to t) \times a^n \right)$

Abstract: I present a uniform derivation of profunctor optics: isos, lenses, prisms, and grates based on the Yoneda lemma in the (enriched) profunctor category. In particular, lenses and prisms correspond to Tambara modules with the cartesian and cocartesian tensor product.

This blog post is the result of a collaboration between many people. The categorical profunctor picture solidified after long discussions with Edward Kmett. A lot of the theory was developed in exchanges on the Lens IRC channel between Russell O’Connor, Edward Kmett and James Deikun. They came up with the idea to use the Pastro functor to freely generate Tambara modules, which was the missing piece that completed the picture.

My interest in lenses started long time ago when I first made the connection between the universal quantification over functors in the van Laarhoven representation of lenses and the Yoneda lemma. Since I was still learning the basics of category theory, it took me a long time to find the right language to make the formal derivation. Unbeknownst to me Mauro Jaskellioff and Russell O’Connor independently had the same idea and they published a paper about it soon after I published my blog. But even though this solved the problem of lenses, prisms still seemed out of reach of the Yoneda lemma. Prisms require a more general formulation using universal quantification over profunctors. I was able to put a dent in it by deriving Isos from profunctor Yoneda, but then I was stuck again. I shared my ideas with Russell, who reached for help on the IRC channel, and a Haskell proof of concept was quickly established. Two years later, after a brainstorm with Edward, I was finally able to gather all these ideas in one place and give them a little categorical polish.

Yoneda Lemma

The starting point is the Yoneda lemma, which states that the set of natural transformations between the hom-functor C(a, -) in the category C and an arbitrary functor f from C to Set is (naturally) isomorphic with the set f a:

[C, Set](C(a, -), f) ≅ f a

Here, f is a member of the functor category [C, Set], where natural transformation form hom-sets.

The set of natural transformations may be represented as an end, leading to the following formulation of the Yoneda lemma:

∫x Set(C(a, x), f x) ≅ f a

This notation makes the object x explicit, which is often very convenient. It can be easily translated to Haskell, by replacing the end with the universal quantifier. We get:

forall x. (a -> x) -> f x ≅ f a

A special case of the Yoneda lemma replaces the functor f with a hom-functor in C:

f x = C(b, x)

and we get:

∫x Set(C(a, x), C(b, x)) ≅ C(b, a)

This form of the Yoneda lemma is useful in showing the Yoneda embedding, which states that any category C can be fully and faithfully embedded in the functor category [C, Set]. The embedding is a functor, and the above formula defines its action on morphisms.

We will be interested in using the Yoneda lemma in the functor category. We simply replace C with [C, Set] in the previous formula, and do some renaming of variables:

∫f Set([C, Set](g, f), [C, Set](h, f)) ≅ [C, Set](h, g)

The hom-sets in the functor category are sets of natural transformations, which can be rewritten using ends:

∫f Set(∫x Set(g x, f x), ∫x Set(h x, f x))
≅ ∫x Set(h x, g x)

This is a short recap of adjunctions. We start with two functors going between two categories C and D:

L :: C -> D
R :: D -> C

We say that L is left adjoint to R iff there is a natural isomorphism between hom-sets:

D(L x, y) ≅ C(x, R y)

In particular, we can define an adjunction in a functor category [C, Set]. We start with two higher order (endo-) functors:

L :: [C, Set] -> [C, Set]
R :: [C, Set] -> [C, Set]

We say that L is left adjoint to R iff there is a natural isomorphism between two sets of natural transformations:

[C, Set](L f, g) ≅ [C, Set](f, R g)

where f and g are functors from C to Set. We can rewrite natural transformations using ends:

∫x Set((L f) x, g x) ≅ ∫x Set(f x, (R g) x)

In Haskell, you may think of f and g as type constructors (with the corresponding Functor instances), in which case L and R are types that are parameterized by these type constructors (similar to how the monad or functor classes are).

Here’s a little trick. Since the fixed objects in the formula for Yoneda embedding are arbitrary, we can pick them to be images of other objects under some functor L that we know is left adjoint to another functor R:

∫x Set(D(L a, x), D(L b, x)) ≅ D(L b, L a)

Using the adjunction, this is isomorphic to:

∫x Set(C(a, R x), C(b, R x)) ≅ C(b, (R ∘ L) a)

Notice that the composition R ∘ L of adjoint functors is a monad in C. Let’s write this monad as Φ.

The interesting case is the adjunction between a forgetful functor U and a free functor F. We get:

∫x Set(C(a, U x), C(b, U x)) ≅ C(b, Φ a)

The end is taken over x in a category D that has some additional structure (we’ll see examples of that later); but the hom-sets are in the underlying simpler category C, which is the target of the forgetful functor U.

The Yoneda-with-adjunction formula generalizes to the category of functors:

∫f Set(∫x Set((L g) x, f x), ∫x Set((L h) x, f x))
≅ ∫x Set((L h) x, (L g) x)

∫f Set(∫x Set((g x, (R f) x), ∫x Set(h x, (R f) x))
≅ ∫x Set(h x, (Φ g) x)

Here, Φ is the monad R ∘ L in the category of functors.

An interesting special case is when we substitute hom-functors for g and h:

g x = C(a, x)
h x = C(s, x)

We get:

∫f Set(∫x Set((C(a, x), (R f) x), ∫x Set(C(s, x), (R f) x))
≅ ∫x Set(C(s, x), (Φ C(a, -)) x)

We can then use the regular Yoneda lemma to “integrate over x” and reduce it down to:

∫f Set((R f) a, (R f) s)) ≅ (Φ C(a, -)) s

Again, we are particularly interested in the forgetful/free adjunction:

∫f Set((U f) a, (U f) s)) ≅ (Φ C(a, -)) s

Φ = U ∘ F

The simplest application of this identity is when the functors in question are identity functors. We get:

∫f Set(f a, f s)) ≅ C(a, s)

forall f. Functor f => f a -> f s  ≅ a -> s

You may think of this formula as defining the trivial kind of optic that simply turns a to s.

Profunctors

Profunctors are just functors from a product category Cop×D to Set. All the results from the last section can be directly applied to the profunctor category [Cop×D, Set]. Keep in mind that morphisms in this category are natural transformations between profunctors. Here’s the key formula:

∫p Set((U p)<a, b>, (U p)<s, t>)) ≅ (Φ (Cop×D)(<a, b>, -)) <s, t>

I have replaced a with a pair <a, b> and s with a pair <s, t>. The end is taken over all profunctors that exhibit some structure that U forgets, and F freely creates. Φ is the monad U ∘ F. It’s a monad that acts on profunctors to produce other profunctors.

Notice that a hom-set in the category Cop×D is a set of pairs of morphisms:

<f, g> :: (Cop×D)(<a, b>, <s, t>)
f :: s -> a
g :: b -> t

the first one going in the opposite direction.

The simplest application of this identity is when we don’t impose any constraints on the profunctors, in which case Φ is the identity monad. We get:

∫p Set(p <a, b>, p <s, t>) ≅ (Cop×D)(<a, b>, <s, t>)

Haskell translation of this formula gives the well-known representation of Iso:

forall p. Profunctor p => p a b -> p s t ≅ Iso s t a b

where:

data Iso s t a b = Iso (s -> a) (b -> t)

Interesting things happen when we impose more structure on our profunctors.

Enriched Categories

First, let’s generalize profunctors to work on enriched categories. We start with some monoidal category V whose objects serve as hom-objects in an enriched category A. The category V will essentially replace Set in our constructions. For instance, we’ll work with profunctors that are enriched functors from the (enriched) product category to V:

p :: Aop ⊗ A -> V

Notice that we use a tensor product of categories. The objects in such a category are pairs of objects, and the hom-objects are tensor products of individual hom-objects. The definition of composition in a product category requires that the tensor product in V be symmetric (up to isomorphism).

For such profunctors, there is a suitable generalization of the end:

∫x p x x

It’s an object in V together with a V-natural family of projections:

pry :: ∫x p x x -> p y y

We can formulate the Yoneda lemma in an enriched setting by considering enriched functors from A to V. We get the following generalization:

∫x [A(a, x), f x] ≅ f a

Notice that A(a, x) is now an object of V — the hom-object from a to x. The notation [v, w] generalizes the internal hom. It is defined as the right adjoint to the tensor product in V:

V(x ⊗ v, w) ≅ V(x, [v, w])

We are assuming that V is closed, so the internal hom is defined for every pair of objects.

Enriched functors, or V-functors, between two enriched categories C and D form a functor category [C, D] that is itself enriched over V. The hom-object between two functors f and g is given by the end:

[C, D](f, g) = ∫x D(f x, g x)

We can therefore use the Yoneda lemma in a category of enriched functors, or in the category of enriched profunctors. Therefore the result of the previous section holds in the enriched setting as well:

∫p [(U p)<a, b>, (U p)<s, t>] ≅ (Φ (Aop⊗A)(<a, b>, -)) <s, t>

with the understanding that:

(Aop⊗A)(<a, b>, -))

is an enriched hom functor mapping pairs of objects in A to objects in V, plus the appropriate action on hom-objects. This hom-functor is the profunctor on which Φ acts.

Tambara Modules

An enriched category A may have a monoidal structure of its own. We’ll use the same tensor product notation for its structure as we did for the underlying monoidal category V. There is also a tensorial unit object i in A.

A Tambara module is a V-functor p from Aop⊗A to V, which transforms under the tensor action of A according to a family of morphisms, natural in all three arguments:

α a x y :: p x y -> p (a ⊗ x) (a ⊗ y)

Notice that these are morphisms in the underlying category V, which is also the target of the profunctor.

We impose the usual unit law:

α i x y = id

and associativity:

α a⊗b x y = α a b⊗x b⊗y ∘ α b x y

Strictly speaking one can separately define left and right action but, for simplicity, we’ll assume that the product is symmetric (up to isomorphism).

The intuition behind Tambara modules is that some of the profunctor values are not independent of others. Once we have calculated p x y, we can obtain the value of p at any of the points on the path <a⊗x, a⊗y> by applying α.

Tambara modules form a category that’s enriched over V. The construction of this enrichment is non-trivial. The hom-object between two profunctors p and q in a category of profunctors is given by the end:

[Aop⊗A, V](p, q) = ∫<x y> V(p x y, q x y)

This object generalizes the set of natural transformations. Conceptually, not all natural transformation preserve the Tambara structure, so we have to define a subobject of this hom-object that does. The intuition is that the end is a generalized product of its components. It comes equipped with projections. For instance, the projection pr<x,y> picks the component:

V(p x y, q x y)

But there is also a projection pr<a⊗x, a⊗y> that picks:

V(p a⊗x a⊗y, q a⊗x a⊗y)

from the same end. These two objects are not completely independent, because they can both be transformed into the same object. We have:

V(id, αa) :: V(p x y, q x y) -> V(p x y, q a⊗x a⊗y)
V(αa, id) :: V(a⊗x a⊗y, q a⊗x a⊗y) -> V(p x y, q a⊗x a⊗y)

We are using the fact that the mapping:

<v, w> -> V(v, w)

is itself a profunctor Vop×V -> V, so it can be used to lift pairs of morphisms in V.

Now, given any triple a, x, and y, we want the two paths to be equivalent, which means finding the equalizer between each pair of morphisms:

V(id, αa) ∘ pr<x, y>
V(αa, id) ∘ pr<a⊗x, a⊗y>

Since we want our hom-object to satisfy the above condition for any triple, we have to construct it as an intersection of all those equalizers. Here, an intersection means an object of V together with a family of monomorphisms, each embedding it into a particular equalizer.

It’s possible to construct a forgetful functor from the Tambara category to the category of profunctors [Aop⊗A, V]. It forgets the existence of α and it maps hom-objects between the two categories. Composition in the Tambara category is defined is such a way as to be compatible with this forgetful functor.

The fact that Tambara modules form a category is important, because we want to be able to use the Yoneda lemma in that category.

Tambara Optics

The key observation is that the forgetful functor from the Tambara category has a left adjoint, and that their composition forms a monad in the category of profunctors. We’ll plug this monad into our general formula.

The construction of this monad starts with a comonad that is given by the following end:

(Θ p) s t = ∫c p (c⊗s) (c⊗t)

For a given profunctor p, this comonad builds a new profunctor that is essentially a gigantic product of all values of this profunctor “shifted” by tensoring its arguments with all possible objects c.

The monad we are interested in is the left adjoint to this comonad (calculated using a Kan extension):

(Φ p) s t = ∫ c x y A(s, c⊗x) ⊗ A(c⊗y, t) ⊗ p x y

Notice that we have two separate tensor products in this formula: one in V, between the hom-objects and the profunctor, and one in A, under the hom-objects. This monad takes an arbitrary profunctor p and produces a new profunctor Φ p.

We can now use our earlier formula:

∫p [(U p)<a, b>, (U p)<s, t>)] ≅ (Φ (Aop⊗A)(<a, b>, -)) <s, t>

inside the Tambara category. To calculate the right hand side, let’s evaluate the action of Φ on the hom-profunctor:

(Φ (Aop⊗A)(<a, b>, -)) <s, t>
= ∫ c x y A(s, c⊗x) ⊗ A(c⊗y, t) ⊗ (Aop⊗A)(<a, b>, <x, y>)

We can “integrate over” x and y using the Yoneda lemma to get:

∫ c A(s, c⊗a) ⊗ A(c⊗b, t)

We get the following result:

∫p [(U p)<a, b>, (U p)<s, t>)] ≅ ∫ c A(s, c⊗a) ⊗ A(c⊗b, t)

where the end on the left is taken over all Tambara modules, and U is the forgetful functor from the Tambara category to the category of profunctors.

If the category in question is closed, we can use the adjunction:

A(c⊗b, t) ≅ A(c, [b, t])

and “perform the integration” over c to arrive at the set/get formulation:

∫ c A(s, c⊗a) ⊗ A(c, [b, t]) ≅ A(s, [b, t]⊗a)

It corresponds to the familiar Haskell lens type:

(s -> b -> t, s -> a)

(This final trick doesn’t work for prisms, because there is no right adjoint to Either.)

A Tambara module is parameterized by the choice of the tensor product ten. We can write a general definition:

class (Profunctor p) => TamModule (ten :: * -> * -> *) p where
leftAction  :: p a b -> p (c ten a) (c ten b)
rightAction :: p a b -> p (a ten c) (b ten c)

This can be further specialized for two obvious monoidal structures: product and sum:

type TamProd p = TamModule (,) p
type TamSum p = TamModule Either p

The former is equivalent to what it called a Strong (or Cartesian) profunctor in Haskell, the latter is equivalent to a Choice (or Cocartesian) profunctor.

Replacing ends and coends with universal and existential quantifiers in Haskell, our main formula becomes (pseudocode):

forall p. TamModule ten p => p a b -> p s t
≅ exists c. (s -> c ten a, c ten b -> t)

The two sides of the isomorphism can be defined as the following data structures:

type TamOptic ten s t a b
= forall p. TamModule ten p => p a b -> p s t
data Optic ten s t a b
= forall c. Optic (s -> c ten a) (c ten b -> t)

Chosing product for the tensor, we recover two equivalent definitions of a lens:

type Lens s t a b = forall p. Strong p => p a b -> p s t
data Lens s t a b = forall c. Lens (s -> (c, a)) ((c, b) -> t)

Chosing the coproduct, we get:

type Prism s t a b = forall p. Choice p => p a b -> p s t
data Prism s t a b = forall c. Prism (s -> Either c a) (Either c b -> t)

These are the well-known existential representations of lenses and prisms.

The monad Φ (or, equivalently, the free functor that generates Tambara modules), is known in Haskell under the name Pastro for product, and Copastro for coproduct:

data Pastro p a b where
Pastro :: ((y, z) -> b) -> p x y -> (a -> (x, z))
-> Pastro p a b
data Copastro p a b where
Copastro :: (Either y z -> b) -> p x y -> (a -> Either x z)
-> Copastro p a b

They are the left adjoints of Tambara and Cotambara, respectively:

newtype Tambara p a b = Tambara forall c. p (a, c) (b, c)
newtype Cotambara p a b = Cotambara forall c. p (Either a c) (Either b c)

which are special cases of the comonad Θ.

Discussion

It’s interesting that the work on Tambara modules has relevance to Haskell optics. It is, however, just one example of an even larger pattern.

The pattern is that we have a family of transformations in some category A. These transformations can be used to select a class of profunctors that have simple transformation laws. Using a tensor product in a monoidal category to transform objects, in essence “multiplying” them, is just one example of such symmetry. A more general pattern involves a family of transformations f that is closed under composition and includes a unit. We specify a transformation law for profunctors:

class Profunctor p => Related p where
α f a b :: forall f. Trans f => p a b -> p (f a) (f b)

This requirement picks a class of profunctors that we call Related.

Why are profunctors relevant as carriers of symmetry? It’s because they generalize a relationship between objects. The profunctor transformation law essentially says that if two objects a and b are related through p then so are the transformed objects; and that there is a function α that relates the proofs of this relationship. This is in the spirit of profunctors as proof-relevant relations.

As an analogy, imagine that we are comparing people, and the transformation we’re interested in is aging. We notice that family relationships remain invariant under aging: if a is a sibling of b, they will remain siblings as they age. This is not true about other relationships, for instance being a boss of another person. But family bonds are not the only ones that survive the test of time. Another such relation is being older or younger than the other person.

Now imagine that you pick four people at random points in time and you find out that any time-invariant relation between two of them, a and b, also holds between s and t. You have to conclude that there is some connection between s and age-adjusted a, and between age-adjusted b and t. In other words there exists a time shift that transforms one pair to another.

Considering all possible relations from the class Related corresponds to taking the end over all profunctors from this class:

type Optic p s t a b = forall p. Related p =>
p a b -> p s t

The end is a generalization of a product, so it’s enough that one of the components is empty for the whole end to be empty. It means that, for a particular choice of the four types a, b, s, and t, we have to be able to construct a whole family of morphisms, one for every p. We have seen that this end exists only if the four types are connected in a very peculiar way — for instance, if a and b are somehow embedded in s and t.

In the simplest case, we may choose the four types to be related by the transformation:

s = f a
t = f b

For these types, we know that the end exists:

forall p. Related p =>
p a b -> p s t

because there is a family of appropriate morphisms: our αf a b. In general, though, we can get away with weaker connection.

Let’s look at an example of a family of transformations generated by pairing with arbitrary type c:

fc a = (c, a)

Profunctors that respect these transformations are Tambara modules over a cartesian product (or, in lens parlance, Strong profunctors). For the choice:

s = (c, a)
t = (c, b)

the end in question trivially exists. As we’ve seen, we can weaken these conditions. It’s enough that one way (lax) transformations exist:

s -> (c, a)
t <- (c, b)

These morphisms assert that s can be split into a pair, and that t can be constructed from a pair (but not the other way around).

Other Optics

With the understanding that optics may be defined using a family of transformations, we can analyze another optic called the Grate. It’s based on the following family:

type Reader e a = e -> a

Notice that, unlike the case of Tambara modules, this family is parameterized by a contravariant parameter e.

We are interested in profunctors that transform under these transformations:

class Profunctor p => Closed p where
closed :: p a b -> p (x -> a) (x -> b)

They let us form the optic:

type Grate s t a b = forall p. Closed p => p a b -> p s t

It turns out that there is a profunctor functor that freely generates Closed profunctors. We have the obvious comonad:

newtype Closure p a b = Closure forall x. p (x -> a) (x -> b)

data Environment p u v where
Environment :: ((c -> y) -> v) -> p x y -> (u -> (c -> x))
-> Environment p a b

or, in categorical notation:

(Φ p) u v = ∫ c x y A([c, y], v) ⊗ p x y ⊗ A(u, [c, x])

Using our construction, we apply this monad to the hom-profunctor:

(Φ (Aop⊗A)(<a, b>, -)) <s, t>
= ∫ c x y A([c, y], t) ⊗ (Aop⊗A)(<a, b>, <x, y>) ⊗ A(s, [c, x])
≅ ∫ c A([c, b], t) ⊗ A(s, [c, a])

Translating it back to Haskell, we get a representation of Grate as an existential type:

Grate s t a b = forall c. Grate ((c -> b) -> t) (s -> (c -> a))

This is very similar to the existential representation of a lens or a prism. It has the intuitive interpretation that s can be thought of as a container of a‘s indexed by some hidden type c.

We can also “perform the integration” using the Yoneda lemma, internal-hom-adjunction, and the symmetry of the product:

∫ c A([c, b], t) ⊗ A(s, [c, a])
≅ ∫ c A([c, b], t) ⊗ A(s ⊗ c, a)
≅ ∫ c A([c, b], t) ⊗ A(c, [s, a])
≅ A([[s, a], b], t)

to get the more familiar form:

Grate s t a b ≅ ((s -> a) -> b) -> t

Conclusion

I find it fascinating that constructions that were first discovered in Haskell to make Haskell’s optics composable have their categorical counterparts. This was not at all obvious, if only because some of them use parametricity arguments. Parametricity is the property of the language, not easily translatable to category theory. Now we know that the profunctor formulation of isos, lenses, prisms, and grates follows from the Yoneda lemma. The work is not complete yet. I haven’t been able to derive the same formulation for traversals, which combine two different tensor products plus some monoidal constraints.

Bibliography

1. Haskell lens library, Edward Kmett
2. Distributors on a tensor category, D. Tambara
3. Doubles for monoidal categories, Craig Pastro, Ross Street
4. Profunctor optics, Modular data accessors,
Matthew Pickering, Jeremy Gibbons, and Nicolas Wu
5. CPS based functional references, Twan van Laarhoven
6. Isomorphism lenses, Twan van Laarhoven
7. Theorem for Second-Order Functionals, Mauro Jaskellioff and Russell O’Connor

In the previous post I explored the application of the Yoneda lemma in the functor category to derive some results from the Haskell lens library. In particular I derived the profunctor representation of isos. There is one more trick that is used in the lens library: combining the Yoneda lemma with adjunctions. Jaskelioff and O’Connor used this trick in the context of free/forgetful adjunctions, but it can be easily generalized to any pair of adjoint higher order functors.

An adjunction between two functors, L and R (left and right functor) is a natural isomorphism between hom-sets:

C(L d, c) ≅ D(d, R c)

The left functor L goes from the category D to C, and the right functor R goes in the opposite direction. Formally, having an adjunction allows us to shift the action of the functor from one end of the hom-set to the other. The shortcut notation for an adjunction is L ⊣ R.

Since adjunctions can be defined for arbitrary categories, they will also work between functor categories. In that case objects are functors and hom-sets are sets of natural transformations. For instance, Let’s consider an adjunction between two higher order functors:

ρ :: [C, C'] -> [D, D']
λ :: [D, D'] -> [C, C']

Here, [C, C'] is a category of functors between two categories C and C’, [D, D'] is a category of functors between D and D’, and ρ maps functors (and natural transformations) between these two categories. λ goes in the opposite direction. The adjunction λ ⊣ ρ is expressed as a natural isomorphism between sets of natural transformations:

[C, C'](λ g, h)  ≅  [D, D'](g, ρ h)

The two objects in functor categories are themselves functors:

h :: C -> C'
g :: D -> D'

Here’s the same adjunction written using ends:

∫x∈C C'((λ g) x, h x)  ≅  ∫y∈D D'(g y, (ρ h) y)

The end notation is easily translatable to Haskell. The end corresponds to a universal quantifier forall, and hom-sets become function types:

forall x. (lambda g) x -> h x ≅ forall y. g y -> (rho h) y

Since lambda and rho act on functors, they have kinds (*->*)->(*->*).

Let’s recall the formula for the Yoneda embedding of the functor category:

∫f Set(∫x D(g x, f x), ∫y D(h y, f y))
≅ ∫z D(h z, g z)

Here, g, h, and f, are functors — objects in the functor category [C, D]. The ends represent natural transformations — morphisms in the functor category. The end over f is a higher order natural transformation.

Since g and h are arbitrary, let’s replace them with the results of the action of some higher order functors, λ g and λ' h. The idea is that λ and λ' are left halves of some higher order adjunctions.

∫f Set(∫x D'((λ g) x, f x), ∫y D'((λ' h) y, f y))
≅ ∫z D'((λ' h) z, (λ g) z)

The right halves of these adjunctions are, respectively, ρ and ρ'.

λ  ⊣ ρ
λ' ⊣ ρ'

Let’s apply these adjunctions inside the hom-sets:

∫f Set(∫x D(g x, (ρ f) x), ∫y D(h y, (ρ' f) y))
≅ ∫z D(h z, (ρ' (λ g)) z)

Let’s focus our attention on the category of sets. If we replace D with Set, we can pick g and h to be hom-functors (which are the simplest representable functors) parameterized by some arbitrary objects b and t:

g = C(b, -)
h = C(t, -)

We get:

∫f Set(∫x Set(C(b, x), (ρ f) x), ∫y Set(C(t, y), (ρ' f) y)
≅ ∫z Set(C(t, z), (ρ' (λ C(b, -))) z)

Remember, hom-functors behave like Dirac delta functions under the integration sign. That is to say, we can use the Yoneda lemma to “integrate” over x, y, and z:

∫f Set((ρ f) b, (ρ' f) t)
≅ (ρ' (λ C(b, -))) t

We are now free to pick a pair of adjoint higher order functors to suit our goal. Here’s one such choice for ρ: the functor that maps a functor f (an endofunctor in C) to a set of morphisms from some fixed object a to f acting on another object. This is an operation that lifts a functor to a profunctor. In Haskell it’s defined as UpStar. This higher-order functor is parameterized by the choice of the object a in C:

κa f = C(a, f -)

It can also be written in terms of the exponential object:

κa f = (f -)a

This functor has an obvious left adjoint:

λa g = a × g -

This follows from the standard adjunction between the product and the exponential.

Our pick for ρ' is the same functor but taken at a different carrier, s:

ρ' = κs

With those choices, the left side of the identity

∫f Set((ρ f) b, (ρ' f) t)
≅ (ρ' (λ C(b, -))) t

becomes:

∫f Set(C(a, f b), C(s, f t))

This is the categorical version of the van Laarhoven lens.

Let’s now evaluate the right hand side. First we apply λa to the hom-functor C(b, -) to get:

λa C(b, -) = a × C(b, -)

The action of ρ' produces the result:

C(s, (a × C(b, t)))

This, in turn, is the categorical version of the getter/setter representation of the lens.

Translation

In Haskell, our formula derived from the higher-order Yoneda lemma with the adjoint pair:

∫f Set((ρ f) b, (ρ' f) t)
≅ (ρ' (λ C(b, -))) t

takes the form:

forall f. Functor f => (rho f) b -> (rho' f) t
≅ (rho' (lambda ((->)b))) t

With our choice for ρ as the up-star functor:

rho  f = a -> f -
rho' f = s -> f -

type Rho  a f b = a -> f b
type Rho' s f t = s -> f t

we get:

forall f. Functor f => (a -> f b) -> (s -> f t)
≅ (rho' (lambda ((->)b))) t

To get the λ, we plug our ρ into the adjunction formula. We get:

forall x. (lambda g) x -> h x ≅ forall x. g x -> a -> h x

which has the obvious solution:

lambda g = (a, g -)

type Lambda a g x = (a, g x)

Indeed, with the currying and flipping of arguments, we get the adjunction:

forall x. (a, g x) -> h x ≅ forall x. g x -> a -> h x

Now let’s evaluate the right hand side:

(rho' (lambda ((->) b))) t

lambda (b -> -) = (a, b -> -)

The action of rho' gives us:

rho' (a, b -> -) = s -> (a, b -> -)

Altogether:

(rho' (lambda ((->) b))) t = s -> (a, b -> t)

So the right hand side is just the getter/setter pair:

(s -> a, s -> b -> t)

The final result is the well known van Laarhoven representation of the lens:

forall f. Functor f => (a -> f b) -> (s -> f t)
≅ (s -> a, s -> b -> t)

This is not a new result, but I like the elegance of this derivation — especially the role played by the exponential adjunction and the lifting of a functor to a profunctor. This formulation has the additional advantage of being generalizable towards the profunctor formulation of lenses.

Next Page »