Opposite categories and profunctors

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:Setop × 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.

Laziness

JavaScript is an eager language—that is, it evaluates the parameters to a function before evaluating the function itself. A lazy value in JavaScript is a function with no inputs that returns the result of some expression. The function effectively prevents the expression from being evaluated until it’s needed. There’s a functor that takes any contract and returns the lazy form of that contract:

var lazyOf = function (x) {
  return hom([], x);
};

This functor can be made into a monad; if you have a doubly-lazy value, you can just evaluate it to get a singly-lazy value. The unit wraps a value inside of a function to produce the lazy value.

var lazy = monadOf(lazyOf)({
  '*': function (veryLazy) {
    return veryLazy();
  },
  '1': function (x) {
    return function () {
      return x;
    };
  }
});

Here’s a list with a lazy tail:

var next = function (n) {
  return [n, lazy(int32)[1](next(n+1))];
};
var naturals = next(0);

Adjoint functors

The functor arrOf takes a contract for a set of elements and produces a contract for the set of lists of those elements. Concatenation of lists makes them into a monoid. Let Mon be the category of monoids and monoid homomorphisms; then we can say that arrOf is a functor from Set to Mon.

There’s another functor from Mon to Set that simply forgets the monoidal structure: it takes an element of a monoid and produces an opaque wrapper with one method, unwrap. Let’s call it setOf.

The contract setOf(arrOf(x)): Set -> Set is for a wrapped array of x‘s. Given any element xVal, we can produce a value wrap([xVal]) that passes setOf(arrOf(x)).

The contract arrOf(setOf(m)): Mon -> Mon is for lists of wrapped elements of a monoid. Given any list like

[wrap(mVal1), wrap(mVal2), wrap(mVal3)]

passing this contract, we can get a monoid element passing m by unwrapping each element and multiplying them all together.

The categories Set and Mon are not equivalent: setOf ○ arrOf is not isomorphic to the identity since there’s no way to take an element like wrap([xVal1, xVal2, xVal]) that passes setOf(arrOf(x)) and produce an element passing the contract x that doesn’t depend on x.

However, setOf and arrOf are related in a special way: with a little thought, it’s easy to see that the set of monoid homomorphisms from arrOf(x) to y is isomorphic to the set of functions passing hom(x, setOf(y)): a monoid homomorphism from arrOf(x) is completely specified by saying what it does to each of the values that pass x: you just map that function over the list and then multiply the results together.

Two functors and are adjoint functors if for all objects c in C and d in D,

In the example above, is the set of functions from the set c to the set c’, and is the set of monoid homomorphisms from the monoid d to the monoid d’.

Other examples of adjoint functors include

1. PSet is the category of “pointed sets”—i.e. sets with a special chosen element called the “point”—and functions between them that map the point of the domain to the point of the codomain. Here, is the set c plus an extra point, while forgets which element of d was the special one.
2. where is the category whose objects are natural numbers and there’s a morphism from to if Here, the floor function forgets the fractional part of
3. where is the category of polynomials of degree and there’s a morphism from f to f’ if f is bounded above by f’. Here, the derivative operator forgets the constant term.
4. In general, any “forgetful” functor R that forgets some structure has a left adjoint L, the “free” structure of that kind.
5. where Set² is the category of pairs of sets and pairs of functions between them, and This is a categorification of the fact that in real numbers,
6. This is a categorification of the fact that in real numbers,
7. This is a categorification of the fact that in real numbers,
8. where Sub is the category of sets and inclusions (i.e. there’s a morphism if )
9. 
10. Here Bool is the category with two objects F and T and an arrow from F to T—that is, there’s an arrow from one object to another if the one implies the other. is the set of subsets of and maps F to the empty set and T to
11. 

Adjoint functors turn up all over the place.

n-Categories

We have

• -1: a boolean T,
•   0: a set {T, F} of booleans,
•   1: a category Set of sets and functions,
•   2: a 2-category Cat of categories, functors, and natural transformations,
•   …
•   n: an (n+1)-category nCat of n-categories, functors, transformations, modifications, …, and n-cells.

In this hierarchy, a “0-category” is a set, a “(-1)-category” is a boolean, and the only “(-2)-category” is T. When we compare things in an n-category, we get this pattern:

•   0: two booleans are either equal or not,
•   1: two sets may be isomorphic without being equal,
•   2: two categories may be equivalent without being isomorphic,
•   …
•   n: two n-categories may be n-equivalent without being (n-1)-equivalent.

In particular,

•   1: two sets and are isomorphic if there are functions and such that

  , and .

•   2: two categories X and Y are equivalent if there are functors and such that

  , and .

•   …
•   n: two n-categories X and Y are n-equivalent if there are functors and such that

  , and .

To be really pedantic, we could also have said

•   0: two booleans and are equal if there are equations and such that

  , and ,

where is the equation and similarly for

Categories

In addition to categories of data structures and their homomorphisms, there are other simple constructions that give rise to categories from other ones:

• By currying the hom functor, we get the notion of a “slice category”.

  var slice = function (y) {
    return function (x) {
      return hom([x], y);
    };
  };
  

  The objects in the slice category Contract/y are functions whose result passes the contract y; the morphisms from f:x1 -> y to g:x2 -> y are functions h:x1 -> x2 such that f(x) = g(h(x)).

• Contract² is the category whose objects are pairs of contracts and whose morphisms are pairs of functions.
• Functors and natural transformations form a category.
• Given a monad myMonad = monadOf(myFunctor), there’s a category whose objects are contracts and whose morphisms are functions of the form f:x -> myFunctor(y). To compose f:x -> myFunctor(y) and g:y -> myFunctor(z), we write

  function (x) { return myMonad['*'](myFunctor(g)(f(x))); }.

  This is how the register function works in the Parser monad example.

• Given any functor myFunctor, we get a category whose objects are algebras of the functor—i.e. a contract c and a function h:myFunctor(c) -> c—and whose morphisms are functions f:c1 -> c2 such that

  h2(myFunctor(f)(x)) === f(h1(x)).

I’ll go into more detail on these in future posts.

Categories

Here’s our definition of the interface for a monoid:

var monoidOf = function (m, n) {
  n = n || m;
  func(m); func(n);
  return makeInterface({
    '*': hom([m, m], n),
    1: hom([], n)
  });
};

var testMonoidOf = function (t) {
  func(t);
  return {
    testAssoc: hom([monoidOf(t), hom([], t), nat32])(
      function (m, rand, n) {
        var i;
        for (i = 0; i < n; ++i) {
          var a = rand();
          var b = rand();
          var c = rand();
          if (m['*'](a, m['*'](b, c)) !== m['*'](m['*'](a, b), c)) {
             throw new TypeError('Expected multiplication to be associative: ' + [a, b, c]);
          }
        }
      }),
    testUnit: hom([monoidOf(t), hom([], t), nat32])(
      function (m, rand, n) {
        var i;
        for (i = 0; i < n; ++i) {
          var a = rand();
          if (m['*'](a, m[1]) !== a || m['*'](m[1], a) !== a) {
            throw new TypeError('Expected m[1] to be the identity: ' + a);
          }
        }
      })
  };
};

We get implementations of the monoid by choosing a contract for the set of monoid elements and an object with two functions that pass the monoid tests, like

var int32Add = monoidOf(int32)({
  '*': function (i1, i2) { return ((i1 | 0) + (i2 | 0)) | 0; },
  1: function () { return 0; }
});

var xor = monoidOf(bool)({
  '*': function (b1, b2) { return b1 ^ b2; },
  1: function () { return 0; }
});

We get monoid homomorphisms by looking for functions f:m -> n that satisfy

monoidOf(f, n)(y) = monoidOf(m, f)(x),

like

monoidOf(mod2, bool)(xor) = monoidOf(int32, mod2)(int32Add).

Monoids and monoid homomorphisms form a category. In general, any data structure and its homomorphisms form a category, so stacks and stack homomorphisms form a category, graphs and graph homomorphisms form a category, etc.

Natural transformations

We’ve seen stack homomorphisms and monoid homomorphisms. These are homomorphisms between implementations of an interface.

There’s also a general notion of a homomorphism between two arbitrary functors, which is a variant of the hom functor.

var natural = function (f, g) {
  func(f); func(g);
  return function (x, y) {
    y = y || x;
    func(x); func(y);
    return hom([f(x)], g(y));
  };
};

Just as we used hom when defining the interface of a monoid, we can use natural when defining the interface of a monad:

var compose = function (f, g) {
  func(f); func(g);
  return function(x) {
    return f(g(x));
  };
};

var monadOf = function (m, n) {
  n = n || m;
  func(m); func(n);
  return function (intr) {
    return function (t) {
      return makeInterface({
        '*': natural(compose(m, m), n)(t),
        1: natural(id, n)(t)
      })(intr);
    };
  };
};

Given categories and and functors and , a natural transformation assigns to every object of a morphism such that for every morphism in C,

The flatten function is a natural transformation from compose(arrOf, arrOf) to arrOf. It takes a doubly-nested array to a singly-nested array, no matter what the type of the elements in the array. Also, it doesn’t matter if you first map a function over the list of lists and then flatten:

flatten(int)(arrOf(arrOf(function (x) { return x+1; }))([[1, 2], [3]]))

or if you flatten first and then map:

arrOf(function (x) { return x+1; }))(flatten(int)([[1, 2], [3]]).

Monads and parsing

A parser takes a string and produces a list of tokens and the remaining string, so we want a function p:str -> makeProduct([arr, str]).

To get the target type, let’s use a functor. The addState functor takes any contract x and turns it into the pair contract [arr, x], so it expects a tuple containing an array and a value satisfying x.

var addState = function (x) {
  return makeProduct([arr, x]);
};

To chain parsers together, we want to apply the next parser to the second element of the result of the last one, then concatenate the list of tokens. A monad will help with this process.

If we iterate the addState functor twice on the contract x, the resulting contract accepts objects of the form [a1, [a2, xVal]] where a1 and a2 are arrays and xVal satisfies x. The state monad’s multiplication concatenates the two arrays a1 and a2, while its unit provides the empty array for the first parser in the chain.

var state = monadOf(addState)({
  // Input is of the form [a1, [a2, xVal]]
  // where a1, a2 are arrays.
  '*': function (doubleState) {
    var a1 = doubleState[0];
    var a2 = doubleState[1][0];
    var xVal = doubleState[1][1];

    return [a1.concat(a2), xVal];
  },
  1: function (xVal) {
    return [[], xVal];
  }
})(str);

var Parser = function () {
  this.run = state[1];
};

The register method is where it all comes together: since addState is a functor, we can use it to apply a function to the second element of a tuple, and then the multiplication in the monad concatenates the two lists.

Parser.register = function (name, makeParser) {
  Parser.prototype[name] = function (varArgs) {
    var run = this.run;
    this.run = function (s) {
      return state['*'](
          addState( makeParser.apply({}, toArray(arguments)) )
          (run(s)));
    };
    return this;
  };
};

// Given a character, produce a parser
var char = function (c) {
  return hom([str], addState(str))(function (s) {
    if (s[0] !== c) {
      throw new Error('Expected the character "' + c + '"');
    }
    return [[c], s.substr(1)];
  });
};

Parser.register(char);

new Parser()
    .char('a').char('b').char('c')
    .run('abcde');
// === [["a", "b", "c"], "de"]

Monoids and monads

Here’s our definition of a monoid, slightly modified so you have to invoke the property 1 to get the identity element:

var monoidOf = function (m, n) {
  n = n || m;
  func(m); func(n);
  return makeInterface({
    '*': hom([m, m], n),
    1: hom([], n)
  });
};

Here’s a slight variant of this definition of a monoid:

var monadOf = function (m, n) {
  n = n || m;
  func(m); func(n);
  return function (intr) {
    return function (t) {
      return makeInterface({
        '*': hom([m(m(t))], n(t)),
        1: hom([t], n(t))
      })(intr);
    };
  };
};

Instead of the multiplication expecting a pair of functions, it expects the composite of functions. Here’s one way it’s used:

var flatten = monadOf(arrOf)({
  '*': function (arrayOfArrays) {
    var flattened = [], len = arrayOfArrays.length;
    for (var i = 0; i < len; ++i) {
      var innerLen = arrayOfArrays[i].length;
      for (var j = 0; j < innerLen; ++j) {
        flattened.push(arrayOfArrays[i][j]);
      }
    }
    return flattened;
  },
  1: function (x) { return [x]; }
});

var stringFlatten = flatten(str);

The stringFlatten example’s multiplication expects a doubly nested array of strings and returns an array of strings. It’s associative, in the sense that if you have a triply-nested array, it doesn’t matter if you flatten the inner or outer layer first. It’s unital in the sense that if you wrap a list in brackets and then flatten it, you get the same thing back; similarly if you wrap each element in brackets and flatten it, you also get the same thing back.

In a monoid, the multiplication wants two things and returns one; in a monad, the multiplication wants a functor applied twice to t and returns the functor applied once to t. In a monoid, the unit wants no elements and returns one; in a monad, the unit wants a functor applied no times to t and returns the functor applied once to t.

Monads are an exceptionally versatile design pattern. There are monads for lists, exceptions, simulating imperative programming on top of functional programming but still keeping the state explicit so you can mock out the state for easy testing, continuation passing style, parsing, promises (aka futures), event chaining, and more. jQuery, for example, is the combination of several of these monads.

Monoids, trees and tests

Here’s a simple data type and some implementations:

// Times should be associative and
// 1 should behave as the identity
var monoidOf = function (m, n) {
  n = n || m;
  func(m); func(n);
  return makeInterface({
    '*': hom([m, m], n),
    1: n
  });
};

var bool = function (b) {
  if (b !== 0 && b !== 1) {
    throw new TypeError('Expected 0 or 1');
  }
  return b;
}

var and = monoidOf(bool)({
  '*': function (b1, b2) { return b1 & b2; },
  1: 1
});

var xor = monoidOf(bool)({
  '*': function (b1, b2) { return b1 ^ b2; },
  1: 0
});

var or = monoidOf(bool)({
  '*': function (b1, b2) { return b1 | b2; },
  1: 0
});

var int32Add = monoidOf(int32)({
  '*': function (n1, n2) { return (n1 + n2) | 0; },
  1: 0
});

var strConcat = monoidOf(str)({
  '*': function (n1, n2) { return n1 + n2; },
  1: ''
});

Here’s a datatype for an unlabeled binary tree:

var treeOf = function (treeIn, treeOut) {
  treeOut = treeOut || treeIn;
  func(treeIn); func(treeOut);
  return makeInterface({
    node: hom([treeIn, treeIn], treeOut),
    leaf: treeOut
  });
};

var makeTree = treeOf(obj)({
  node: function (left, right) {
    return {left: left, right: right};
  },
  leaf: {}
});

The interfaces are the same except for the names of the methods. The difference is that we expect the multiplication in the monoid to be associative and unital, while there are no restrictions on node. The ability to enforce relations among functions is what makes this category theory instead of graph theory: categories can be presented as (directed multi-)graphs plus relations on paths.

The problem of deciding whether the multiplication is associative is undecidable: it’s as hard as the halting problem. Some research programming languages require you to provide a proof along with your code, but that’s still impractical for daily use. Instead, we rely on tests and hope that we got all the corner cases. If we provide a function to produce random elements of a type, we can use fuzzing.

var testMonoidOf = function (t) {
  func(t);
  return {
    testAssoc: hom([monoidOf(t), hom([], t), nat32])(
      function (m, rand, n) {
        var i;
        for (i = 0; i < n; ++i) {
          var a = rand();
          var b = rand();
          var c = rand();
          if (m['*'](a, m['*'](b, c)) !== m['*'](m['*'](a, b), c)) {
             throw new TypeError('Expected multiplication to be associative: ' + [a, b, c]);
          }
        }
      }),
    testUnit: hom([monoidOf(t), hom([], t), nat32])(
      function (m, rand, n) {
        var i;
        for (i = 0; i < n; ++i) {
          var a = rand();
          if (m['*'](a, m[1]) !== a || m['*'](m[1], a) !== a) {
            throw new TypeError('Expected m[1] to be the identity: ' + a);
          }
        }
      })
  };
};

var xorTest = testMonoidOf(bool);
var randBool = function () { return Math.floor(Math.random() * 2); };
xorTest.testAssoc(xor, randBool, 10);
xorTest.testUnit(xor, randBool, 10);

Now consider the function mod2 and the two parity objects below:

var mod2 = hom([int32], bool)(function (x) {
  return x % 2;
});

var parity1 = monoidOf(mod2, bool)(xor);
var parity2 = monoidOf(int32, mod2)(int32Add);

The times operation in both parity objects takes a pair of int32s and returns a bool. In parity1, mod2 is applied to the inputs and the results are xored together. In parity2, the numbers are added and then mod2 is applied. The end result is the same either way.

A monoid homomorphism from an implementation monoidOf(m)(x) to an implementation monoidOf(n)(y) is a function f: m -> n such that monoidOf(f, n)(y) is observably the same as monoidOf(m, f)(x).