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.
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.