Tabulation Tribulations

Previously: Bending, Yanking, and Cartesian Squares in Double Categories. We all know what a graph of a function is: it’s a set of pairs , where . Similarly, a graph of a relation is a set of pairs where is related to . A profunctor can be viewed as a proof-relevant relation. So a graph of a profunctor is a triple, which contains two objects and a proof, or a witness, that they are related. The witness in this case is any element of the set . If the set is empty, it means that the objects are unrelated. Such triples form a category, which is often called the category of elements of a profunctor. Given a profunctor , an object in the category of elements is a triple . We interpret as a witness that is related to .

…

Excerpt limited to ~120 words for fair-use compliance. The full article is at Bartosz Milewski's Programming Cafe.