I’m going through all this stuff in videos on YouTube now. Nine have been uploaded; more to come.

## For-comprehensions in JavaScript

I’m starting to learn Scala, and I love their for-comprehension style of monadic programming. Here’s a small library that uses eval and textual manipulations to do desugaring.

// A Monad class for Array and other monads to inherit from function Monad() { throw "abstract"; } Monad.prototype.flatMap = function (f) { return this.map(f).flatten(); }; // Make Array inherit from Monad Array.prototype.__proto__ = Monad.prototype; // Define the monadic multiplication Array.prototype.flatten = function () { var result = []; var len = this.length; for (var i = 0; i < len; ++i) { result = result.concat(this[i]); } return result; }; // The comprehension class var M = function () { var pairs = []; this.for = function (v, e) { pairs.push({e: e, v: v}); return this; }; this.yield = function (body) { var desugared = pairs.map(function (pair, index) { return '(' + pair.e + ').' + ((index === pairs.length-1) ? 'm' : 'flatM') + 'ap(function(' + pair.v + ') { return '; }).join('') + '(' + body + ');' + pairs.map(function () { return ' });' }).join(''); pairs = []; return desugared; }; }; // Avoid the need to say (new M) at the start M.for = function (v, e) { return (new M).for(v, e); }; // Tensor product of lists // eval(M.for('x','[1,2,3]').for('y','[5,6,7]').yield('x * y')); // 5,6,7,10,12,14,15,18,21 // Aka Maybe function Option() { throw "abstract"; } Option.prototype = Object.create(Monad.prototype); Option.prototype.map = function (f) { if (this instanceof None) { return this; } return new Some(f(this.value)); }; Option.prototype.flatten = function () { if (this instanceof None) { return this; } return this.value; }; function None() {} None.prototype = Object.create(Option.prototype); None.prototype.toString = function () { return 'None'; }; function Some(v) { this.value = v; } Some.prototype = Object.create(Option.prototype); Some.prototype.toString = function () { return 'Some(' + this.value + ')'; }; // var xs = [1,2,3]; // eval(M.for('x','xs').for('y','x % 2 ? new Some(x) : new None()').yield('x * y')); // [Some(1), None, Some(9)]

The call to `eval`

on the outside is necessary to capture the scope in which the for-comprehension occurs (e.g. the scope in which `xs`

occurs in the second example).

## New contract library

I updated the source code page in preparation for a talk on this stuff I might be giving soon.

## 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:Set`

^{op} × 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

- 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. - 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
- 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.
- In general, any “forgetful” functor R that forgets some structure has a left adjoint L, the “free” structure of that kind.
- 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,
- This is a categorification of the fact that in real numbers,
- This is a categorification of the fact that in real numbers,
- where Sub is the category of sets and inclusions (
*i.e.*there’s a morphism if ) - 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

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

.

## Generics / templates

Java has generics and C++ has templates. These language features are only half of a functor, since they only act on types, not functions. In JavaScript we can do better.

// Stack interface var stackOf = function (t, u) { u = u || t; func(t); func(u); return makeInterface({ push: hom(t, id), // pop returns either [0, []] or [1, value] pop: hom([], makeCoproduct([terminal, u])), size: hom([], nat32) }); }; // Stack implementation var makeStack = function (t, u) { var state = []; return stackOf(t, u)({ push: function (val) { state.push(val); }, pop: function () { return state.length ? [1, state.pop()] : [0, []]; }, size: function () { return state.length; } }; }; // Create a stack of strings. var myStack = makeStack(str);

This definition of stack is a little odd because it has the option of taking two contracts instead of just one. A functor like `arrOf`

is both a contract and the `map`

function. If we think of `stackOf`

as a kind of `map`

, then what does it do?

In `arrOf`

, the contract or function gets applied to each element of the array. In `stackOf`

, one contract or function gets applied before pushing and the other gets applied after popping. Given an associative array `obj`

and a `stackOf(str)`

object `myStack`

, we could write

var myLookupStack = stackOf( id, function (s) { return obj[s]; })(myStack);

and get a stack object where you push strings but pop values of `obj`

.

A **stack homomorphism** from an implementation `stackOf(t)(x)`

to `stackOf(u)(y)`

is a function `f: t -> u`

such that `stack(f, u)(y)`

gives the same result as `stack(t, f)(x)`

. This notion of a stack homomorphism hasn’t appeared in the literature (at least not under the name “stack homomorphism”) even though it’s very natural from a category theory perspective. I believe Java and C++ developers didn’t come up with it just because generics and templates deal only with types rather than both types and functions between them.

## Functors again

We’ve seen several different functors:

arrOf: C -> C makeProduct: C* -> C makeInterface: C* -> C hom: Cᵒᵖ × C -> C makeCoproduct: C* -> C

- The functor
`arrOf`

takes a contract and produces one contract that accepts an empty list, or a 1-item list, or a 2-item list, and so on up to a (2^{31}– 1)-item list. It can also take an arbitrary function and iterate over an array. - The functor
`makeProduct`

takes an array of contracts and produces one that accepts tuples of values whose individual entries pass the corresponding contracts. It can also take an array of functions to apply in parallel. - The functor
`makeInterface`

is the same as makeProduct, but with string indices instead of numeric indices. - The functor
`hom`

takes two contracts and produces one contract that accepts functions whose input passes the first contract and whose output passes the second. It can also take two functions and apply them serially, doing one function before and one after. - The functor
`makeCoproduct`

takes an array of contracts and produces one that accepts values that pass one of the contracts. It can also take an array of functions and apply one of them depending on the tag.

In each case, the functor takes some contracts and produces a single new contract, and each one encapsulates some control structure of the language in the way you take apart the values that pass the new contract.

## Lists

Products are what a Python programmer might call a tuple, a list of a fixed length. Let `c`

be a contract; a list of `c`

‘s of arbitrary length (well, up to length 2^{31} – 1) is the contract

arrOf(c) ≅ makeCoproduct([ makeProduct([]), makeProduct([c]), makeProduct([c, c]), makeProduct([c, c, c]), ..., makeProduct([c, ..., c]) // (1 << 31) - 1 copies ]);

That is, it’s either an empty list, or a one-item list, or a two-item list, and so on up to a (2^{31} – 1)-item list. The `length`

member of the array says which of these it is.

## Coproducts

Here are a bunch of constructions that share a similar property:

- The union of two sets is the
*smallest*set that contains both of them. - The maximum of two numbers is the
*smallest*number that’s greater than or equal to both of them. - The least common multiple of two numbers is the
*smallest*number that’s a multiple of both them. - The proposition “A or B” is the one with the
*least*assumptions needed to prove either A or B.

We can get all these concepts by reversing all the arrows in the categorical product diagram:

It says that X is an object with morphisms from A and B such that given any object Y with morphisms from A and B, there exists a morphism from X to Y. We call X the **coproduct** of A and B.

Just as with the product, we can also generalize the coproduct from partial orders to categories and get useful structures.

This says that X is an object with morphisms from A and B such that given any object Y with morphisms from A and B, there exists a unique morphism from X to Y making the diagram commute—that is, if we apply the morphism marked `p`

and then `!`

, we get the same result as applying `r`

; similarly, if we apply `q`

and then `!`

, we get the same result as applying `s`

.

In the category of sets and functions, the categorical product gives us the disjoint union of sets:

An element of A+B is either an element of A or an element of B. In JavaScript, variables have a type that’s a sum over every possible type: it can be an int or a string or a Date object or a function or whatever we want.

We can write a contract for the coproduct of n contracts, where the coproduct of 0 contracts is a contract for the empty set: no item passes the contract.

var makeCoproduct = function (cs) { arrOf(func)(cs); return function (x) { makeProduct([nat32, id])(x); if (x[0] >= cs.length) { throw new TypeError('Expected a tag less than ' + cs.length); } return cs[x[0]](x[1]); }; };

The contract `makeCoproduct([str, nat32])`

will accept values of the form `[0, s]`

where `s`

is a string or `[1, n]`

where `n`

is a natural number.

## makeProduct as a functor

When I defined `makeProduct`

, we hadn’t talked about higher-order contracts yet, so it doesn’t work quite right around `hom`

. To fix it, we return a new array whose elements are the results of the contracts given to `makeProduct`

.

var makeProduct = function (cs) { arrOf(func)(cs); var len = cs.length; return function (args) { arr(args); if (args.length !== len) { throw new TypeError('Expected ' + len + ' arguments'); } var result = []; for (var i = 0; i < len; ++i) { // Apply each contract to the // corresponding argument. result[i] = cs[i](args[i]); } return result; }; };

Written like this, it’s a variant of `map`

where instead of applying the same function to all the members, it applies a list of functions to each respective member. As such, it’s also a functor: you can supply it with either contracts or functions between them.

## This

JavaScript functions always get a reference to an object called `this`

. If you just invoke a function `f()`

, then `this`

is bound to the global scope object in older browsers and to `undefined`

in newer ones.

Method invocation is a special form in JavaScript: if you invoke a property of an object `o.f()`

, then `this`

is bound to the object `o`

. If you don’t want `this`

bound to `o`

, then you have to break up that special form. You can either assign the function to a variable and invoke that:

var g = o.f; g();

or you can make a reference to `o`

be the result of a subexpression and then invoke the `f`

property on that:

(1,o).f()

In the example of the `person`

interface, the `print`

function took a name and an age as explicit parameters. The OOP way of doing it, of course, would be to use `this.name`

and `this.age`

:

var person = makeInterface({ name: str, age: nat32 }); var print = function () { person(this); return str(this.name) + ' is ' + nat32(this.age) + ' year' + ((this.age === 1) ? '' : 's') + ' old.'; }; var joe = person({ name: 'Joe Brown', age: 35, print: print }); joe.print();

This is a lot better, but we’d still like to be able to use `hom`

to express typing decisions. Instead of trying to shoehorn `this`

into `hom`

, we can write a function for labeling functions that should be called as methods on an object satisfying the interface.

// Captures the hom contract instance var method = function (homDecl) { // Returns a higher-order contract that // gets applied when the interface contract // is applied to the object return function (f) { // Binds to the interface contract var intr = this; var g = homDecl(f); // Returns a function that behaves like f return function (varArgs) { return g.apply(intr(this), toArray(arguments)); }; }; }; var person = makeInterface({ print: method(hom([], str)), name: str, age: nat32 }); var joe = person({ name: 'Joe Brown', age: 35, print: function () { return name + ' is ' + this.age + ' year' + ((this.age === 1) ? '' : 's') + ' old'; } });

## Interfaces

JavaScript’s objects (in the OOP sense) are all associative arrays; the `Array`

class just has a magical `length`

property that updates when you assign to indices that satisfy the `nat32`

contract. From a category theory point of view, they’re also products. From a programmer’s point of view, though, they give a nice way of writing an interface.

var obj = function (o) { if (typeof o !== 'object' || o === null) { throw new TypeError( 'Expected an object.'); } return o; } var makeInterface = function (intr) { obj(intr); for (var i in intr) { func(intr[i]); } return function (x) { obj(x); var result = Object.create( Object.getPrototypeOf(x)); for (var i in intr) { result[i] = intr[i](x[i]); } return result; }; }; var person = makeInterface({ name: str, age: nat32, print: hom(makeProduct([str, nat32]), str) }); var joe = person({ name: 'Joe Brown', age: 35, print: function (name, age) { return name + ' is ' + age + 'year' + ((age === 1) ? '' : 's') + ' old'; } });

## Functors

Here’s a contract that checks if the input is an array of natural numbers.

var arrOfNat32 = function (a) { arr(a); return a.map(nat32); };

First it checks to see that `a`

is an array; next it applies `nat32`

to each element of the array.

Here’s a higher-order contract that takes a contract `c`

and returns a contract that checks if the input is an array of values passing `c`

.

var arrOf = function (c) { func(c); return function (a) { arr(a); return a.map(c); }; };

Now we can write things like

var arrOfNat32 = arrOf(nat32); var arrOfStr_to_str = arrOf(hom(str, str));

Note that the function `arrOf`

is a currying of the `map`

method; JavaScript defines `Function.prototype.bind`

for currying, so we could also have written it as

var arrOf = hom([func], hom([arr], id)) (Function.prototype.bind.bind([].map));

The function `arrOf`

acts both on contracts and on the functions between them. For example, the function `atoi`

has the type signature `nat32 -> str`

, while `arrOf(atoi)`

has the type signature `arrOf(nat32) -> arrOf(str)`

.

A **functor** `F`

from a category `C`

to a category `D`

- assigns to every object
`c`

in`C`

an object`F(c)`

in`D`

- assigns to every morphism
`m:c -> c'`

in`C`

a morphism`F(m):F(c) -> F(c')`

in`D`

such that composition and identities are preserved—that is,

`F(function (x) { return m(n(x)); })`

, and

= function (x) { return F(m)(F(n)(x)); }`F(id_c) = id_Fc`

.

The function `arrOf`

is a functor from the category of contracts and functions between them to itself. It maps each contract `c`

to a new contract `arrOf(c)`

, and each function `f:c -> c'`

to a new function `arrOf(f):arrOf(c) -> arrOf(c')`

.

Optimizing compilers use properties of functors like `arrOf`

or `map`

to make code faster. If `a`

is an array, then

`a.map(f).map(g) = a.map(function (x) { return g(f(x)); })`

The right-hand version only iterates over the array once, saving a lot of time; this technique is called “map fusion”.

## Categorical products

Here are a bunch of constructions that share a similar property:

- The intersection of two sets is the
*largest*set that’s a subset of both of them. - The minimum of two numbers is the
*largest*number that’s less than or equal to both of them. - The greatest common divisor of two numbers is the
*largest*number that divides both of them. - The proposition “A and B” is the one with the
*least*assumptions needed to prove both A and B.

A **partial order** is a set equipped with a relation ≤ that is

- transitive
- reflexive and
- antisymmetric

All of these examples are extremes in a partial order, either the largest or smallest example of something. We say they satisfy a “universal property”.

Another definition of partial order is “a category where there’s at most one morphism between any two objects and the only cycles are identities”, so we have four categories:

- The category whose objects are sets and whose morphisms are statements of the form “X ⊂ Y”.
- The category whose objects are real numbers and whose morphisms are statements of the form “x ≤ y”.
- The category whose objects are natural numbers and whose morphisms are statements of the form “x is a factor of y”.
- The category whose objects are propositions and whose morphisms are statements of the form “X implies Y”.

In order to state more precisely what it means to be the most extreme example of this property, let’s look at the examples again:

- Say we have a set X that we believe to be the intersection of A and B. It has to be the case that X ⊂ A and X ⊂ B. It should also be the
*largest*such subset. We can frame this in terms of a duel between competitors: say Y is a set that also satisfies Y ⊂ A and Y ⊂ B. What is the relation between the real intersection and Y? Well, the intersection is the biggest one, so if X is the intersection, we’ve got to have Y ⊂ X for any choice of Y. - Say we have a number x that we believe to be the minimum of two numbers a and b. It has to be the case that x ≤ a and x ≤ b. It should also be the
*largest*such number. We can frame this in terms of a duel between competitors: say y is a number that also satisfies y ≤ a and y ≤ b. What is the relation between the real minimum and y? Well, the minimum is the biggest one, so if x is the minimum, we’ve got to have y ≤ x for any choice of y. - Say we have a number x that we believe to be the GCD of two numbers a and b. It has to be the case that x is a factor of a and x is a factor of b. It should also be the
*largest*such number. We can frame this in terms of a duel between competitors: say y is a number such that y is a factor of a and y is a factor of b. What is the relation between the real GCD and y? Well, the GCD is the biggest one, so if x is the GCD, it’s got to be true that y is a factor of x for any choice of y. - Say we have a proposition X that we believe to be the logical AND, or
**conjunction**, of A and B. It has to be the case that X implies A and X implies B. It should also be the*weakest*such proposition. We can frame this in terms of a duel between competitors: say Y is a proposition that also satisfies Y implies A and Y implies B. What is the relation between the real conjunction and Y? Well, the conjunction is the weakest one, so if X is the conjunction, we’ve got to have Y implies X for any choice of Y.

Each of the examples above can be illustrated with a simple diagram:

It says that X is an object with morphisms to A and B such that given any object Y with morphisms to A and B, there exists a morphism from Y to X. We call X the **categorical product** of A and B.

It turns out that we can generalize the product from partial orders to categories and get useful structures. In the category of sets and functions, we are no longer restricted to a single morphism between two objects, so we need labels on the diagram naming our functions; in order to have a “best” object, though, we want the arrow from Y to X to remain unique:

This says that X is an object with morphisms to A and B such that given any object Y with morphisms to A and B, there exists a unique morphism from Y to X making the diagram commute—that is, if we apply the morphism marked `!`

and then `p`

, we get the same result as applying `r`

; similarly, if we apply `!`

and then `q`

, we get the same result as applying `s`

.

In the category of sets and functions, the categorical product gives us the cartesian product of sets:

If instead of using two sets and two functions “first” and “second”, we use an arbitrary finite number of sets and index them with brackets and natural numbers, then we get arrays.

The function `toArray`

we saw earlier took an array-like object `Y = arguments`

and turned it into a real array.

## Hom

Most statically-typed languages have you put all the typing information in the same place. So far, we’ve had to put the output contract at the end of the function in the return statement. We’ve seen that we can write a higher-order contract that guarantees a function will map strings to strings; here’s one that works for an arbitrary pair of contracts:

var hom = function (sourceArr, target) { var source = makeProduct(sourceArr); return function (f) { func(f); return function (varArgs) { return target(f.apply(this, source(toArray(arguments)))); }; }; };

We can use `hom`

to give type information up front:

var repeat = hom([str, nat32], str) (function (s, n) { return Array(n+1).join(s); });

The name “hom” comes from category theory: given any two objects `A`

and `B`

in a category, there’s a set of morphisms between them called `hom(A, B)`

. The higher-order contract `hom`

ensures that a function is an element of that set.

## Some more categories

Recall that a **category** consists of

- a collection of
**objects**, and - for any pair of objects
`A, B`

, a set of**morphisms**between them (if`f`

is a morphism from`A`

to`B`

, we write`f:A -> B`

)

such that

- every object
`A`

has an**identity morphism**`id_A:A -> A`

; - we can compose morphisms
`f, g`

if the target object of`f`

matches the source object of`g`

; - composition is associative; and
- composing with the identity gives back the same morphism.

Here are some categories with just a single object.

- The category with one object
`str`

and morphisms generated by applying`makeConcat`

to strings:var makeConcat = function (s) { str(s); return function (t) { return str(t) + s; }; };

The identity morphism is

`makeConcat('')`

. - The category with one object
`nat32`

and morphisms generated by applying`makeAdd`

to natural numbers:var makeAdd = function (s) { nat32(s); return function (t) { return nat32(t) + s; }; };

The identity morphism is

`makeAdd(0)`

. - The category with one object
`nat32`

and morphisms generated by applying`makeMultiply`

to natural numbers:var makeMultiply = function (s) { nat32(s); return function (t) { return nat32(t) * s; }; };

The identity morphism is

`makeMultiply(1)`

. - The category with one object
// A higher-order contract var str_to_str = function (f) { func(f); return function (s) { return str(f(str(s))); }; };

that insists that

`f:str -> str`

, and morphisms given by applying`makeCompose`

to functions from`str`

to`str`

:var makeCompose = function (f) { f = str_to_str(f); return function (g) { g = str_to_str(g); return function (s) { return g(f(s)); }; }; };

The identity is

`makeCompose(function (s) { return s; })`

.

A **monoid** is a category with one object. Any time you’re adding or multiplying values, you’re using a one-object category. Note that it’s not true for exponentiation! is not, in general, equal to

Here are three functions that share an interesting property:

// Tells whether the number of 1 bits // in the binary expansion of n is // even or odd. var parity = function (n) { nat32(n); var p = 0; while (n > 0) { p = p ^ (n & 1); n = n >> 1; } return nat32(p); }; // Returns the length of the string. var length = function (s) { str(s); return nat32(s.length); }; // Applies g to every element of an array. var map = function (g) { func(g); return function (a) { arr(a); var result = []; for (var i = 0; i < a.length; ++i) { result[i] = g(a[i]); } return result; }; };

`parity(n ^ m) = parity(n) ^ parity(m)`

`length(s + t) = length(s) + length(t)`

- for all arrays
`a`

,map(function (x) { return g(f(x)); })(a);

is the same as

(function (x) { return map(g)(map(f)(x)); })(a);

A **monoid homomorphism** between monoids `M`

and `N`

is a function `f`

that preserves composition and identity. That is, it maps the morphisms of `M`

to the morphisms of `N`

in such a way that given two morphisms `m`

and `m'`

of `M`

, composing first and then applying `f`

is the same as applying `f`

to each and then composing the results in `N`

:

`f(m m') = f(m) f(m')`

, and

`f(id_M) = id_N`

.

Here are some other useful categories.

- The category whose objects are real numbers (the numbers themselves, not contracts), and where a single morphism exists between
`m`

and`n`

if`m <= n`

. Composition of morphisms is transitivity: for all`m, n, p`

, we have`m <= n <= p`

implies`m <= p`

. The identity morphism for a number is reflexivity: for all`m`

,`m <= m`

. - The category whose objects are monoids and whose morphisms are monoid homomorphisms.
- The category whose objects are natural numbers (the numbers themselves) and whose morphisms from
`m`

to`n`

are`n`

-by-`m`

matrices of integers. Composition is matrix multiplication. - A
**directed multigraph**consists of- a set
`N`

of nodes, - a set
`E`

of edges, - a function
`source:E -> N`

, and - a function
`target:E -> N`

.

This definition allows for parallel edges and self-directed edges.

Given any such directed multigraph, there is a category whose objects are the nodes and whose morphisms are the paths. (If there’s an edge from A to B and from B to C, there’s not necessarily an edge from A to C, but there

*is*a path from A to C.) The identity morphism for an object is the “path of length zero” that starts and ends in the same place. - a set

Categories show up all over the place.

## Subsets

Given a contract like `nat32`

, we can define contracts that are more restrictive:

var positive32 = function (n) { nat32(n); if (n === 0) { throw new TypeError('Expected a ' + 'strictly positive integer.'); } return n; }

The set of values that pass the `positive32`

contract is a subset of the values that pass the `nat32`

contract. A **subcontract** `S`

of a contract `C`

is a contract such that if a value `v`

passes `S`

, then it also passes `C`

. The contract `positive32`

is therefore a subcontract of `nat32`

.

For any contract `C`

, there is a category whose objects are all the subcontracts of `C`

and whose morphisms are injections. This is a **subcategory** (defined in the obvious way) of the category of all contracts and injections between them.

## Memoization and injections

A **higher-order contract** takes a function and returns a wrapped function obeying some input/output contract. If we want to trade memory for time, we can cache the results of a function so we don’t have to recompute them; a side-effect is that the result is guaranteed to be functional: it will always return the same value for a given input. For simplicity, assume the function takes a string as input.

// First-order contract var func = function (f) { if (typeof f !== 'function') { throw new TypeError('Expected a function.'); } return f; }; // Higher-order contract var memoize = function (f) { func(f); var memo = {}; return function (s) { str(s); // The '$' prefix avoids issues with // magic properties like __proto__. var key = '$' + s; if (key in memo) { return memo[key]; } return memo[key] = f(s); }; };

A variant of this technique lets us write a contract for injections—that is, functions where two inputs can never give the same output. Here, for simplicity, assume the function `f`

outputs a string.

// Another higher-order contract var injection = function (f) { func(f); var memo = {}; return function (s) { var key = '$' + str(f(s)); if (key in memo && s !== memo[key]) { throw new TypeError('Violated ' + 'injection contract!'); } else { memo[key] = s; } return f(s); }; };

Notice that `f`

may not actually be an injection; we’ll only get an error if the wrapper realizes it’s not an injection.

There is a category whose objects are contracts and whose morphisms are injections between them. It is a very different category from the one whose objects are contracts and whose morphisms are functions between them. For example, suppose we have two contracts `A, B`

that each allow only a finite set of values to satisfy them—say and elements, respectively. Then there are functions between them, but only injections because injections aren’t allowed to repeat outputs.

## Product and terminal contracts

In the last post, we saw a function from `nat32`

to `str`

:

var spaces = function (n) { nat32(n); var result = new Array(n + 1).join(' '); return str(result); };

This function is pretty specific: it only gives repetitions of the space character. What if we wanted to have lines of hyphens or asterisks or my name? We could write

var repeat = function (s, n) { str(s); nat32(n); var result = (new Array(n + 1)).join(s); return str(result); };

and then say `repeat('.oOo', 6)`

to get a nice scalloped edge: .oOo.oOo.oOo.oOo.oOo.oOo

If the type signature of `spaces`

is `spaces:nat32 -> str`

, what is the type signature of `repeat`

? We have two contracts being applied, not just one. If we want to stick to the rule that we have one contract for input and one for output, we have to combine them somehow. Here, we want a function that will take a list of contracts and produce a single contract that we can apply to the list of arguments:

var arr = function (a) { if (!Array.isArray(a)) { throw new TypeError('Expected an array.'); } return a; }; // Takes an array-like object---one with a // length property and numeric properties--- // and returns an actual array instance. // This is necessary because the 'arguments' // object only duck types as an array. var toArray = function (a) { var result = []; for (var i = 0; i < a.length; ++i) { result[i] = a[i]; } return arr(result); }; var makeProduct = function (cs) { arr(cs); var len = cs.length; return function (args) { arr(args); if (args.length !== len) { throw new TypeError('Expected ' + len + ' arguments'); } for (var i = 0; i < len; ++i) { // Apply each contract to the // corresponding argument. cs[i](args[i]); } return args; }; }; var str_x_nat32 = makeProduct([str, nat32]); var repeat = function (s, n) { str_x_nat32(toArray(arguments)); var result = (new Array(n + 1)).join(s); return str(result); };

Now we can say `repeat: str_x_nat32 -> str`

. I chose to use `_x_`

in the name to remind us that the set of values that pass this new contract is the cartesian product of the sets that pass `str`

and `nat32`

, respectively.

What about the empty list of contracts?

var terminal = makeProduct([]);

The name ‘terminal’ means that there’s a unique function from any contract `c`

to `terminal`

; the only acceptable output value is an empty array, so it just throws away its input.

var makeUnique = function (c) { return function (x) { c(x); return terminal([]); }; };

## Contracts

Can you spot the error in the following?

var raise = function (div) { div.style.setProperty('z-index', div.style.getProperty('z-index') + 1); }

If the z-index of `div`

was ’4′, then calling `raise(div)`

would set z-index to ’41′! The reason is that style properties are strings, and when one of the arguments to `+`

is a string, it coerces the other to a string and concatenates the two.

Contracts can help avoid errors like the one above. A **first-order contract** is a function that either returns its input or throws an exception. Here are two first-order contracts:

var str = function (s) { if (typeof s !== 'string') { throw new TypeError('Expected a string.'); } return s; }; var nat32 = function (n) { if ((n | 0) !== n || n < 0) { throw new TypeError('Expected a 32-bit ' + 'natural.'); } return n; };

Here are two functions from `nat32`

to `str`

:

var itoa = function (n) { return str('' + nat32(n)); }; var spaces = function (n) { nat32(n); var result = new Array(n + 1).join(' '); return str(result); };

I’ll denote the types of `itoa`

and `spaces`

as

`itoa: nat32 -> str`

`spaces: nat32 -> str`

Now for some math: a **category** consists of

- a collection of
**objects**, and - for any pair of objects
`A, B`

, a set of**morphisms**between them (if`f`

is a morphism from`A`

to`B`

, we write`f:A -> B`

)

such that

- every object
`A`

has an**identity morphism**`id_A:A -> A`

; - we can compose morphisms
`f, g`

if the target object of`f`

matches the source object of`g`

; - composition is associative; and
- composing with the identity gives back the same morphism.

Contracts and the functions between them form a category. Given any two contracts, there’s a set of functions going between them. If we have two functions

`f:A -> B`

g:B -> C,

we can compose them to get

`gf: A -> C`

by writing

var gf = function (a) { return g(f(a)); };

Also, given any contract A, there’s the identity function from A to itself:

var id_A = function (a) { return A(a); };

This is obviously equivalent to the contract `A`

, so we’ll always use `A`

instead.

Had `setProperty`

used the appropriate contract, `raise`

would have caused an error the first time it was used, and we could have fixed it:

var raise = function (div) { div.style.setProperty('z-index', // The unary + coerces the // result to a number. +div.style.getProperty('z-index') + 1); }

## Experiment #2

In my first experiment, I tried teaching some category theory from a programmer’s point of view over on Google+, but the platform wasn’t right for the content: posts got reordered whenever someone commented on them, and people didn’t have time or were too shy to engage at the rate I was hoping for. In this experiment, I’ll try it in a blog format and focus on the one programming language everyone on the internet has access to: JavaScript.

Since the category of computably enumerable sets and partial computable functions is—ahem—*function*al, choosing an imperative, dynamically-typed language might seem strange. Dynamic typing, though, can be seen as a tagged union of all possible types, so by using contracts we can split them up again. It also offers benefits like being able to say “the type of prime natural numbers” that we aren’t usually able to express statically.

As for the statefulness of JavaScript, I’ll start with the functional part and show how it avoids all kinds of problems with testing code—so you ought to be programming functionally anyway—and then (eventually) show how the standard object model JavaScript uses can be seen as a state monad on the functional part.

I’d like to do some videos as part of this, too: drawing commuting diagrams beautifully is still difficult on the web. (If you know otherwise, please tell me how!)

So, welcome! Please ask questions—it’s what keeps me motivated, and everyone else who doesn’t understand will thank you for it.