Opposite categories and profunctors

From any category C you can form the opposite category C^{\mbox{op}}, 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 Setop to be a function from B to A and define the composition of a morphism f:A \to B and a morphism g:B \to C 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 f(g(c))).

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 P:C^{\mbox{op}} \times D \to \mbox{Set}. We’re already familiar with the profunctor

hom:Setop × Set -> Set

that takes a pair of functions (in, out) and produces a function that maps f to out\circ f\circ in. 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.

Advertisements

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: