From any category you can form the **opposite category** , which has the same objects but you turn all the arrows around backwards. This makes sense if you think of a category as being presented as a (directed multi)graph plus a set of relations between paths: you just turn all the edges around and reverse the order of the edges in the relations.

However, if we’re thinking of a category like Set, we just “formally reverse” the arrows: we define a morphism from A to B in Set^{op} to be a function from B to A and define the composition of a morphism and a morphism to be the reversed composition of the functions (that is, in the only way that makes any sense: given an element c of C, return ).

The point of using the opposite category is so that composition happens in the opposite order: if we want to wrap a function f in contracts, then the input contract should be applied *before* f and the output contract should be applied *after* f.

A **profunctor** is a functor of the form We’re already familiar with the profunctor

`hom:Set`

^{op} × Set -> Set

that takes a pair of functions and produces a function that maps to . We can think of any profunctor as being the hom functor for some category.

This profunctor produces a contract for a pair of functions with the given input and output contracts:

var pair = function (aIn, bIn, aOut, bOut) { return makeProduct([hom(aIn, aOut), hom(bIn, bOut)]); };

It’s the hom functor for Contract², the category of pairs of contracts and pairs of functions between them.

Here’s the hom functor for the free category on the complete graph with 26 nodes and self-loops. Objects are letters a-z; morphisms are strings beginning with the source node and ending with the target node. Composition is “overlapping” concatenation: we can only concatenate two strings where the last letter of the first string matches the first letter of the second string, and we “overlap” the matching letters so it only appears once: ‘cap’ + ‘ped’ = ‘caped’, not ‘capped’. The identity morphism on a letter is just the letter itself: ‘c’ + ‘c’ === ‘c’.

var overlap = function (strIn, strOut) { str(strIn); str(strOut); return function (s) { str(s); if (s.length >= 1 && s[0] === strIn[strIn.length-1] && s[s.length-1] === strOut[0]) { return strIn.slice(0, strIn.length-1) + s + strOut.slice(1); } throw new TypeError('Wrong shape string.'); }; }; var tr = overlap('t', 'r'); tr('tubular') === 'tubular'; // passes the tr contract tr('joe'); // throws a type error var catran = typedConcat('cat', 'ran'); catran('tubular') === 'catubularan'; catMan('tamar') === 'catamaran';

The hom profunctor captures everything there is to know about a category; in Haskell, the interface Category is really for a hom profunctor.

## Leave a Reply