# Profunctor

In category theory, a branch of mathematics, profunctors are a generalization of relations and also of bimodules.

## Definition

A profunctor (also named distributor by the French school and module by the Sydney school) $\,\phi$ from a category $C$ to a category $D$, written
    $\phi :C\nrightarrow D$,
is defined to be a functor
    $\phi :D^{\mathrm {op} }\times C\to \mathbf {Set}$
where $D^{\mathrm {op} }$ denotes the opposite category of $D$ and $\mathbf {Set}$ denotes the category of sets. Given morphisms $f:d\to d',g:c\to c'$ respectively in $D,C$ and an element $x\in \phi (d',c)$, we write $xf\in \phi (d,c),gx\in \phi (d',c')$ to denote the actions.
Using that the category of small categories $\mathbf {Cat}$ is cartesian closed, the profunctor $\phi$ can be seen as a functor
    ${\hat {\phi }}:C\to {\hat {D}}$
where ${\hat {D}}$ denotes the category $\mathrm {Set} ^{D^{\mathrm {op} }}$ of presheaves over $D$.
A correspondence from $C$ to $D$ is a profunctor $D\nrightarrow C$.

### Profunctors as categories

An equivalent definition of a profunctor $\phi :C\nrightarrow D$ is a category whose objects are the disjoint union of the objects of $C$ and the objects of $D$, and whose morphisms are the morphisms of $C$ and the morphisms of $D$, plus zero or more additional morphisms from objects of $D$ to objects of $C$. The sets in the formal definition above are the hom-sets between objects of $D$ and objects of $C$. (These are also known as het-sets, since the corresponding morphisms can be called heteromorphisms.) The previous definition can be recovered by the restriction of the hom-functor $\phi ^{\text{op}}\times \phi \to \mathbf {Set}$ to $D^{\text{op}}\times C$.
This also makes it clear that a profunctor can be thought of as a relation between the objects of $C$ and the objects of $D$, where each member of the relation is associated with a set of morphisms. A functor is a special case of a profunctor in the same way that a function is a special case of a relation.

### Composition of profunctors

The composite $\psi \phi$ of two profunctors
    $\phi :C\nrightarrow D$ and $\psi :D\nrightarrow E$
is given by
    $\psi \phi =\mathrm {Lan} _{Y_{D}}({\hat {\psi }})\circ {\hat {\phi }}$
where $\mathrm {Lan} _{Y_{D}}({\hat {\psi }})$ is the left Kan extension of the functor ${\hat {\psi }}$ along the Yoneda functor $Y_{D}:D\to {\hat {D}}$ of $D$ (which to every object $d$ of $D$ associates the functor $D(-,d):D^{\mathrm {op} }\to \mathrm {Set}$).
It can be shown that
    $(\psi \phi )(e,c)=\left(\coprod _{d\in D}\psi (e,d)\times \phi (d,c)\right){\Bigg /}\sim$
where $\sim$ is the least equivalence relation such that $(y',x')\sim (y,x)$ whenever there exists a morphism $v$ in $D$ such that
    $y'=vy\in \psi (e,d')$ and $x'v=x\in \phi (d,c)$.
Equivalently, profunctor composition can be written using a coend
    $(\psi \phi )(e,c)=\int ^{d\colon D}\psi (e,d)\times \phi (d,c)$

### Bicategory of profunctors

Composition of profunctors is associative only up to isomorphism (because the product is not strictly associative in Set). The best one can hope is therefore to build a bicategory Prof whose
* 0-cells are small categories,
* 1-cells between two small categories are the profunctors between those categories,
* 2-cells between two profunctors are the natural transformations between those profunctors.

## Properties
### Lifting functors to profunctors

A functor $F:C\to D$ can be seen as a profunctor $\phi _{F}:C\nrightarrow D$ by postcomposing with the Yoneda functor:
    $\phi _{F}=Y_{D}\circ F$.
It can be shown that such a profunctor $\phi _{F}$ has a right adjoint. Moreover, this is a characterization: a profunctor $\phi :C\nrightarrow D$ has a right adjoint if and only if ${\hat {\phi }}:C\to {\hat {D}}$ factors through the Cauchy completion of $D$, i.e. there exists a functor $F:C\to D$ such that ${\hat {\phi }}=Y_{D}\circ F$.