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 `int32`

s and returns a `bool`

. In `parity1`

, `mod2`

is applied to the inputs and the results are `xor`

ed together. In `parity2`

, the numbers are `add`

ed 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)`

.

## Leave a Reply