## The Free Theorem for Ends

In Haskell, the end of a profunctor `p`

is defined as a product of all diagonal elements:

forall c. p c c

together with a family of projections:

pi :: Profunctor p => forall c. (forall a. p a a) -> p c c pi e = e

In category theory, the end must also satisfy the edge condition which, in (type-annotated) Haskell, could be written as:

dimap f id_{b}. pi_{b}= dimap id_{a}f . pi_{a}

for any `f :: a -> b`

.

Using a suitable formulation of parametricity, this equation can be shown to be a free theorem. Let’s first review the free theorem for functors before generalizing it to profunctors.

## Functor Characterization

You may think of a functor as a container that has a shape and contents. You can manipulate the contents without changing the shape using `fmap`

. In general, when applying `fmap`

, you not only change the values stored in the container, you change their type as well. To really capture the shape of the container, you have to consider not only all possible mappings, but also more general *relations* between different contents.

A function is directional, and so is `fmap`

, but relations don’t favor either side. They can map multiple values to the same value, and they can map one value to multiple values. Any relation on values induces a relation on containers. For a given functor `F`

, if there is a relation `a`

between type `A`

and type `A'`

:

A <=a=> A'

then there is a relation between type `F A`

and `F A'`

:

F A <=(F a)=> F A'

We call this induced relation `F a`

.

For instance, consider the relation between students and their grades. Each student may have multiple grades (if they take multiple courses) so this relation is not a function. Given a list of students and a list of grades, we would say that the lists are related if and only if they match at each position. It means that they have to be equal length, and the first grade on the list of grades must belong to the first student on the list of students, and so on. Of course, a list is a very simple container, but this property can be generalized to any functor we can define in Haskell using algebraic data types.

The fact that `fmap`

doesn’t change the shape of the container can be expressed as a “theorem for free” using relations. We start with two related containers:

xs :: F A xs':: F A'

where `A`

and `A'`

are related through some relation `a`

. We want related containers to be `fmap`

ped to related containers. But we can’t use the same function to map both containers, because they contain different types. So we have to use two *related functions* instead. Related functions map related types to related types so, if we have:

f :: A -> B f':: A'-> B'

and `A`

is related to `A'`

through `a`

, we want `B`

to be related to `B'`

through some relation `b`

. Also, we want the two functions to map related elements to related elements. So if `x`

is related to `x'`

through `a`

, we want `f x`

to be related to `f' x'`

through `b`

. In that case, we’ll say that `f`

and `f'`

are related through the relation that we call `a->b`

:

f <=(a->b)=> f'

For instance, if `f`

is mapping students’ SSNs to last names, and `f'`

is mapping letter grades to numerical grades, the results will be related through the relation between students’ last names and their numerical grades.

To summarize, we require that for any two relations:

A <=a=> A' B <=b=> B'

and any two functions:

f :: A -> B f':: A'-> B'

such that:

f <=(a->b)=> f'

and any two containers:

xs :: F A xs':: F A'

we have:

if xs <=(F a)=> xs' then F xs <=(F b)=> F xs'

This characterization can be extended, with suitable changes, to contravariant functors.

## Profunctor Characterization

A profunctor is a functor of two variables. It is contravariant in the first variable and covariant in the second. A profunctor can lift two functions simultaneously using `dimap`

:

class Profunctor p where dimap :: (a -> b) -> (c -> d) -> p b c -> p a d

We want `dimap`

to preserve relations between profunctor values. We start by picking any relations `a`

, `b`

, `c`

, and `d`

between types:

A <=a=> A' B <=b=> B' C <=c=> C' D <=d=> D'

For any functions:

f :: A -> B f' :: A'-> B' g :: C -> D g' :: C'-> D'

that are related through the following relations induced by function types:

f <=(a->b)=> f' g <=(c->d)=> g'

we define:

xs :: p B C xs':: p B'C'

The following condition must be satisfied:

if xs <=(p b c)=> xs' then (p f g) xs <=(p a d)=> (p f' g') xs'

where `p f g`

stands for the lifting of the two functions by the profunctor `p`

.

Here’s a quick sanity check. If `b`

and `c`

are functions:

b :: B'-> B c :: C -> C'

than the relation:

xs <=(p b c)=> xs'

becomes:

xs' = dimap b c xs

If `a`

and `d`

are functions:

a :: A'-> A d :: D -> D'

then these relations:

f <=(a->b)=> f' g <=(c->d)=> g'

become:

f . a = b . f' d . g = g'. c

and this relation:

(p f g) xs <=(p a d)=> (p f' g') xs'

becomes:

(p f' g') xs' = dimap a d ((p f g) xs)

Substituting `xs'`

, we get:

dimap f' g' (dimap b c xs) = dimap a d (dimap f g xs)

and using functoriality:

dimap (b . f') (g'. c) = dimap (f . a) (d . g)

which is identically true.

## Special Case of Profunctor Characterization

We are interested in the diagonal elements of a profunctor. Let’s first specialize the general case to:

C = B C'= B' c = b

to get:

xs = p B B xs'= p B'B'

and

if xs <=(p b b)=> xs' then (p f g) xs <=(p a d)=> (p f' g') xs'

Chosing the following substitutions:

A = A'= B D = D'= B' a = id d = id f = id g'= id f'= g

we get:

if xs <=(p b b)=> xs' then (p id g) xs <=(p id id)=> (p g id) xs'

Since `p id id`

is the identity relation, we get:

(p id g) xs = (p g id) xs'

or

dimap id g xs = dimap g id xs'

## Free Theorem

We apply the free theorem to the term `xs`

:

xs :: forall c. p c c

It must be related to itself through the relation that is induced by its type:

xs <=(forall b. p b b)=> xs

for any relation `b`

:

B <=b=> B'

Universal quantification translates to a relation between different instantiations of the polymorphic value:

xs_{B}<=(p b b)=> xs_{B'}

Notice that we can write:

xs_{B}= pi_{B}xs xs_{B'}= pi_{B'}xs

using the projections we defined earlier.

We have just shown that this equation leads to:

dimap id g xs = dimap g id xs'

which shows that the wedge condition is indeed a free theorem.

## Natural Transformations

Here’s another quick application of the free theorem. The set of natural transformations may be represented as an end of the following profunctor:

type NatP a b = F a -> G b

instance Profunctor NatP where dimap f g alpha = fmap g . alpha . fmap f

The free theorem tells us that for any `mu :: NatP c c`

:

(dimap id g) mu = (dimap g id) mu

which is the naturality condition:

mu . fmap g = fmap g . mu

It’s been know for some time that, in Haskell, naturality follows from parametricity, so this is not surprising.

## Acknowledgment

I’d like to thank Edward Kmett for reviewing the draft of this post.

## Bibliography

- Bartosz Milewski, Ends and Coends
- Edsko de Vries, Parametricity Tutorial, Part 1, Part 2, Contravariant Functions.
- Bartosz Milewski, Parametricity: Money for Nothing and Theorems for Free

April 13, 2017 at 3:18 am

I can’t claim to understand everything (far from here), but I find these post highly interesting and they’re probably as easy to read as they possibly can. Thank you for writing Categories for Programmers series.

April 17, 2017 at 7:51 am

Hello Bartosz,

Sorry for posting sth unrelated to post, but I have recently found some interesting post:

https://graphicallinearalgebra.net/2017/04/16/a-monoid-is-a-category-a-category-is-a-monad-a-monad-is-a-monoid/

Wonder what are your thoughts on that. Maybe you could even explain it nicer?