Skip to content

Instantly share code, notes, and snippets.

@lazywithclass
Last active August 29, 2015 14:03
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save lazywithclass/4e6b8c42392899e7ed00 to your computer and use it in GitHub Desktop.
Save lazywithclass/4e6b8c42392899e7ed00 to your computer and use it in GitHub Desktop.
My take in explaining to myself the Y Combinator
// the original Y Combinator is here: https://leanpub.com/javascript-allonge/read#y
// have a look at that soup of function and return
// I refactored it down to the below version
// I hope is correct, too tired now.
// used like this
var factorial = Y(
// next
function(fac) {
return function(n) {
return n == 0 ? 1 : n * fac(n - 1);
};
}
);
function Y(next) {
function self() {
return next(function(arg1) {
return self()(arg1);
});
}
return self();
}
// * Y is called
// * self is called
// * next is applied on the function representing the
// recursive step
// * so we obtain the function representing the actual
// instruction, in this this case a factorial
// * this function is assigned to factorial on line 2
// * when factorial is called we are calling the function
// from line 5 to line 7
// * on the recursive step at the end of line 6 we are
// calling the function from line 14 to line 16
// * at each recursive step it all resolves at line 15 where
// where we pass execute the next call passing the new
// integer (arg1)
// * arg1 is the integer that is being passed through each
// recursive call
var assert = require('assert');
assert.equal(factorial(1), 1);
assert.equal(factorial(3), 6);
assert.equal(factorial(5), 120);
console.log('ok');
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment