A proof that Promises/A is a Monad

promise-monad-proof.js

//-------------------------------------------------------------
//
// Hypothesis:
//
// Promises/A is a Monad
//
// To be a Monad, it must provide at least:
// - A unit (aka return or mreturn) operation that creates a corresponding
//   monadic value from a non-monadic value.
// - A bind operation that applies a function to a monadic value
//
// And it must satisfy the 3 Monadic Laws:
// 1. unit a >>= f == f
// 2. m >>= unit == m
// 3.(m >>= f) >>= g == m >>= (\x -> f x >>= g)
//
// See:
// http://en.wikipedia.org/wiki/Monad_(functional_programming)
// http://www.haskell.org/haskellwiki/Monad_Laws
// http://mvanier.livejournal.com/3917.html
// http://mvanier.livejournal.com/4305.html
//
// Author: Brian Cavalier ([email protected])
//
//-------------------------------------------------------------

var when, PromiseMonad, a, b, leftResult, rightResult;

// Promise manager
// Used to create Promises/A promises and to help in implementing
// unit and bind for Promises/A

when = require('when');

//-------------------------------------------------------------
//
// Promise Monad
//
// This defines unit and bind, the two fundamental Monad operations
//
//-------------------------------------------------------------

PromiseMonad = {
	// Given a value, return a corresponding monadic value
	// In this case, given a value, return a promise for that value
	unit: when.resolve,

	// Apply a function f to the underlying value of a monadic value
	// In this case, given a promise, apply f to that promise's resolved value
	bind: when,

	// Two promises are equivalent if their resolved values are equivalent
	// This helper observes two promises and compares their underlying
	// values, and is used to validate the monadic laws for Promises/A below.
	compare: function(left, right, msg) {
		return when.all([left, right], function(results) {
			var eq = results[0] === results[1];
			console.log(msg + ': ' + eq);
			return eq;
		}).otherwise(function(e) {
			console.error(e);
			throw e;
		});
	}
};

// Other helpers and setup

// Simple helper to produce a monadic value *without* using unit()
function m(x) {
	var d = when.defer();
	d.resolve(x);
	return d.promise;
}

// Expected values for validation
a = { name: 'a' };
b = { name: 'b' };

// Simple test functions
function f(x) { return a; }
function g(x) { return b; }

//-------------------------------------------------------------
//
// Proof
//
// Promises/A satisfies the 3 Monadic Laws
//
//-------------------------------------------------------------

//-------------------------------------------------------------
// Law 1
// unit a >>= f == f
// f bound to unit(a) == f(a)

leftResult  = PromiseMonad.bind(PromiseMonad.unit(a), f);

rightResult = f(a);

// A little strange here in that only leftResult is a promise
// so technically only have to observe leftResult, but we'll
// just reuse PromiseMonad.compare anyway.
PromiseMonad.compare(leftResult, rightResult, 'Law 1: unit a >>= f == f');

//-------------------------------------------------------------
// Law 2
// m >>= unit == m
// unit bound to promise value == promise value

leftResult  = PromiseMonad.bind(m(a), PromiseMonad.unit);

rightResult = m(a);

PromiseMonad.compare(leftResult, rightResult, 'Law 2: m >>= unit == m');

//-------------------------------------------------------------
// Law 3
// (m >>= f) >>= g == m >>= (\x -> f x >>= g)
// Or, perhaps more simply: (f >=> g) >=> h == f >=> (g >=> h)
// promise function composition is associative

leftResult = PromiseMonad.bind(PromiseMonad.bind(m(a), f), g);

rightResult = PromiseMonad.bind(m(a), function(x) {
	return PromiseMonad.bind(f(x), g);
});

PromiseMonad.compare(leftResult, rightResult, 'Law 3: (m >>= f) >>= g == m >>= (\\x -> f x >>= g)');