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).

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: