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)');

You can also alias the more common method names (resolve -> of, then -> chain), but here's a quick proof for ES6 Promises.

//Left Identity
(function(){
  var value = 6;
  var p_func = x => Promise.resolve(value+6);
  var left = Promise.resolve(value).then(p_func);
  var right = p_func(value);

  Promise.all([left, right]).then(([lVal,rVal]) => console.log(lVal === rVal, {lVal,rVal}));
}());

//Right Identity
(function(){
  var value = 6;
  var left = Promise.resolve(value);
  var right = Promise.resolve(value).then(x=> Promise.resolve(x));

  Promise.all([left, right]).then(([lVal,rVal]) => console.log(lVal === rVal, {lVal,rVal}));
}());

//Associativity
(function(){
  var f = a => Promise.resolve(a * a);
  var g = a => Promise.resolve(a - 6);
  var m = Promise.resolve(7);
  var left = m.then(f).then(g);
  var right = m.then( x => f(x).then(g) );

  Promise.all([left, right]).then(([lVal,rVal]) => console.log(lVal === rVal, {lVal,rVal}));
}());

Promise.resolve won't work quite like a standard MType.of/return/point, unfortunately, so if you wanted to create an .of method, it wouldn't be a simple alias and you'd have to do something like:

Promise.prototype.of = x => Promise.resolve(x);
Promise.of = Promise.prototype.of;

And as noted, .then is overloaded/too-smart because it checks the result and doubles as .map if it's just a value, instead having explicit map/flatMap methods. The laws don't really care about map though (since it can be derived from flatMap/chain as long it obeys those laws). It's just that doing so with the overloaded .then becomes a bit silly/pointless:

Promise.prototype.map = function(fn){
  return this.then( x=> Promise.resolve(fn(x)) );
};