Created
August 8, 2012 15:57
-
-
Save briancavalier/3296186 to your computer and use it in GitHub Desktop.
A proof that Promises/A is a Monad
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
//------------------------------------------------------------- | |
// | |
// 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 (brian@hovercraftstudios.com) | |
// | |
//------------------------------------------------------------- | |
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)) );
};
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
I don't get why the spec doesn't require a promise to be returned from the then/catch callbacks. Then you wouldn't need to have this annoyingly-complicated 'promise resolution procedure', and you could wrap promises in promises. Seems like they're just overcomplicating and restricting things just for the sake of being able to write
return value;
instead ofreturn Promise.resolve(value);
.Oh, and to replace the behaviour of passing a thenable to
Promise.resolve
,new Promise(thenable.then.bind(thenable))
.Unless there is another reason, such as performance?