Skip to content

Instantly share code, notes, and snippets.

@logicmason
Last active June 18, 2021 01:46
Show Gist options
  • Save logicmason/0722b5b159a45f7a81b6 to your computer and use it in GitHub Desktop.
Save logicmason/0722b5b159a45f7a81b6 to your computer and use it in GitHub Desktop.
Y combinator in JavaScript and factorial function example (recursion with all anonymous functions)
var Y = function(proc) {
return (function(x) {
return proc(function(y) { return (x(x))(y);});
})(function(x) {
return proc(function(y) { return (x(x))(y);});
});
};
var factgen = function(fact) {
return function(n) {
return (n === 0) ? 1 : n * fact(n-1); // calls argument, not self
};
};
var fibgen = function(fib) {
// this naive solution has exponential runtime complexity
return function(n) {
return (n <= 2) ? 1 : fib(n-1) + fib(n-2);
};
};
console.log( Y(factgen)(5) ); // returns 120, i.e., 1 * 2 * 3 * 4 * 5
console.log( Y(fibgen)(7) ); // returns 13, i.e., the 7th fibonacci number
var factorial = Y(factgen); // built entirely with anonymous functions
var fibonacci = Y(fibgen);
console.log( factorial(6) ); // 120
console.log([1,2,3,4,5,6,7,8,9,10].map( fibonacci) ); // the first 10 fibonacci numbers
console.log( fibonacci(35) ); // uh oh, already getting kind of slow due to poor algorithm
var fibgen = function(fib) {
// this naive solution has exponential runtime complexity
return function(n) {
return (n <= 2) ? 1 : fib(n-1) + fib(n-2);
};
};
var Ymem = function(proc) {
// this Y combinator-like function caches the results of earlier calculations
var results = {};
return (function(x) {
return proc(function(y) {
if (results[y] === undefined) { results[y] = (x(x))(y); }
return results[y];
});
})(function(x) {
return proc(function(y) {
if (results[y] === undefined) { results[y] = (x(x))(y); }
return results[y];
});
});
}
// Using Ymem to cache results, fibgen no longer has exponential runtime complexity
var fibonacci = Ymem(fibgen);
console.log([1,2,3,4,5,6,7,8,9,10].map( fibonacci) ); // the first 10 fibonacci numbers
console.log( fibonacci(35) ); // quickly calculates solution of 9227465
console.log( fibonacci(120) ); // still calculates solution almost instantly
@corlaez
Copy link

corlaez commented Mar 26, 2018

@shmidt-i
Copy link

@Irn2prgrm, I think the whole purpose of Y-combinator is to hide recursion-specific code inside it. Calling fact(fact) inside your pure factorial function kills it ;)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment