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.

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: