What is a profunctor?
Recall that a category is a directed graph equipped with an associative and unital composition of its edges. In the categorical context, the nodes of the graph are also called objects and edges are called arrows or morphisms. The unitality requirement says that each object has a unit arrow , called identity, which doesn’t affect the result of the compositions.
A functor is a composition and identity preserving graph morphism from a category to a category.
A profunctor, on the other hand, connects up two categories by (potentially) adding more morphisms in between them ‘from the outer world’. In other perspective, we can describe this setting as one of the two categories acting from the left and the other one acting from the right on the newly added morphisms. This can also be grasped as simply being a two variable functor to the category of sets, contravariant in the first argument.
Here we collected some definitions, each being equivalent to each other, in the sense that the given ‘structures’ can be uniquely transformed into each other.
In what follows, let and be two categories.
Def.1. A category is called a profunctor between and , if it disjointly and fully contains and and any other arrow of goes from an object of to an object of .
Such arrows of are called heteromorphisms or through arrows.
So, a profunctor connects up and by adding heteromorphisms of the form which can be (interchangeably) composed by morphisms of from the left and by morphisms of from the right, in order to make itself a category.
Let’s see some examples. Naturally, all these can be interpreted as examples for any variant of Def.1.
Example 1. Let be the category of sets and the category of groups, and let the heteromorphisms from a set to a group be the functions from to (the underlying set of) . Composition is function composition.
Example 2. Let be a field and be a fixed vector space over , and let and be both the category of -vector spaces. Let the heteromorphisms be the bilinear maps . Compositions can be straightforwardly defined.
Example 3. Let be the category of sets, and let be its opposite category, and let the heteromorphisms be the relations , with composition for functions and relation :
The above examples are all adjoint profunctors, presenting an adjoint situation of two functors by reflections and coreflections in themselves. We present a more general construction at the end of this post.
Def.2. A profunctor is a category over the arrow, i.e. it is a functor for some category , where denotes the arrow category which has objects, call them and , and one arrow .
We can obtain the left and right base categories and as the inverse image of objects and of , respectively, and of their identities.
A categorical way to express this (but only up to isomorphism) is to use pullbacks
Importantly, the -preimage of the arrow consists exactly of the heteromorphisms of .
Def.3. A profunctor is a functor .
It simply assigns the set of heteromorphisms to the object pair , and assigns the function to the morphism pair .
In other words, given the category as above, take its hom functor and restrict it to .
Conversely, a given functor determines a category by adding the elements of regarding them as heteromorphisms , and by defining the compositions as the image of under the function .
A span between sets and is a pair of functions , for some set .
This can be visualized as a kind of bipartite graph between and , the elements of being the edges, and assigns their sources from while assigns their targets from .
Note, however that and as sets may overlap, in particular, we allow , when a span becomes exactly a directed graph (or quiver), having the starting and end points of the edges in the same set.
In other perspective, a span associates the set of edges from to for a given pair . Said that, a span is none other than a ‘function’ : a profunctor at the level of sets.
Spans can be ‘composed‘ as follows:
Let and be two spans. Their composite span between and consists of all length paths of the form with .
This way, spans are organized in a bicategory structure as arrows between sets. Bicategories provide a level of abstraction where general left and right actions can be nicely defined and studied, by means of their ‘internal monoids‘ (also called monads in this context).
An internal monoid in a bicategory is, roughly, an arrow equipped with an ‘associative, unital operation’ .
The internal monoids in the bicategory of spans turn out to be just the categories.
A left action of an internal monoid on an arrow is a which is compatible with . A right action can be dually defined.
If and are monoids, a bimodule between them is an arrow equipped with a left and a right action at once, compatible with each other, in the sense that they provide a unique two sided action .
Def.4. A profunctor is a bimodule in the bicategory of spans.
Construction. Any subcategory of can be seen as a categorical relation between and , and any such induces a profunctor from to by freely adjoining a new heteromorphism whenever and forcing all squares to commute whenever .
Any functor is a categorical relation, and so is the opposite relation of any categorical relation, i.e. when and and the freely added arrows are swapped.
Example 4. Apply the above construction for the singleton subcategory containing only (and its identity) for any fixed pair of objects .
Then we receive a profunctor which satisfies
as each heteromorphism can uniquely be written as with , by construction.