Skip to content

Instantly share code, notes, and snippets.

@mrkaspa
Created May 27, 2015 20:48
Show Gist options
  • Save mrkaspa/d814619283d6a8ac5916 to your computer and use it in GitHub Desktop.
Save mrkaspa/d814619283d6a8ac5916 to your computer and use it in GitHub Desktop.
Y Combinator JS and Recursive Calls
var trampoline = function (f) {
while (f && f instanceof Function) {
f = f.apply(f.context, f.args);
}
return f;
}
var thunk = function (fn) {
return function () {
var args = Array.prototype.slice.apply(arguments);
return function () {
return fn.apply(this, args);
};
};
};
var Y = function (F) {
return (function (f) {
return f(f);
}(function (f) {
return F(function (x) {
return f(f)(x);
});
}));
};
var FactorialGen2 = function () {
return function (n) {
var factorial = thunk(function (x, n) {
if (n == 0) {
return x;
}
else {
return factorial(n * x, n - 1);
}
});
return trampoline(factorial(1, n));
}
};
var Factorial2 = Y(FactorialGen2)
console.log(Factorial2(10)); // 3628800
console.log(Factorial2(23456)); // Infinity but works
var Sum = function () {
return function (n) {
var sum = thunk(function (acc, n) {
if (n == 0) return acc
else return sum(acc + n, n - 1)
})
return trampoline(sum(0, n))
}
}
console.log(Y(Sum)(25000))
@angelbotto
Copy link

holy shit!

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