The Y Combiantor is one of the most confusing pieces of code I’ve ever seen.
const Y = (f) => ( x => f(v => x(x)(v)) )( x => f(v => x(x)(v)) );
Used as such:
const factorial = Y(function (fac) { return function (n) { return (n == 0 ? 1 : n * fac(n - 1)); } }); factorial(5) //=> 120
Of course, that’s cheating. Intended use is like this:
((f) => ( x => f(v => x(x)(v)) )( x => f(v => x(x)(v)) )(function (fac) { return function (n) { return (n == 0 ? 1 : n * fac(n - 1)); } }))(5); //=> 120
because it’s harder to understand that way. But really, it’s because the goal of the Y Combinator is to do recursion without naming any functions. It has no practical use, but it has theoretical importance, and it’s appears to be a good way to sink your time if you’re looking for a good puzzle. I thought to myself, could I derive it, if I hadn’t seen this solution before?
We’re trying to achieve the equivalent of this, without naming the function, of course:
function fac (n) { return (n == 0 ? 1 : n * fac(n - 1)); }
A first pass:
(function (fac, n) { return (n == 0 ? 1 : n * fac(fac, n - 1)); }(function (fac, n) { return (n == 0 ? 1 : n * fac(fac, n - 1)); }, 5)); //=> 120
That accomplishes it, but that’s silly. The second pass is much better:
(function (fac) { return function (n) { return fac(fac)(n); } }(function(fac) { return function (n) { return (n == 0 ? 1 : n * fac(fac)(n - 1)); } }))(5); //=> 120
That works, so I guess that qualifies as a solution, but it has a big flaw that the canonical Y Combinator doesn’t – we have to call fac(fac)(n-1)
in the exposed function instead of just fac(n-1)
. Bad.. very bad… But wait! That function taking n
is the same as the one in the Y Combinator. Or is it? I got stuck here for a while, and once I realized I’d started talking to myself, I decided to try a different approach.
Time to cheat a little bit, with a named function. Too much lambda here, hard to understand.
(function (wrapper) { function injector() { return wrapper(n => injector()(n)); } return injector(); }(function(fac) { return function (n) { return (n == 0 ? 1 : n * fac(n - 1)); } }))(5); //=> 120
This idea took a bit of a leap, but it turns out this is exactly what the Y Combinator is doing, in a more sane, readable way of course. I named the function injector
, because it is injecting a function into the fac
parameter of the wrapper function. An alternative name might have been recur
or runner
, because the function it’s injecting does those things. This makes things clearer. But I can’t use named functions. Let’s translate this back to crazy.
Now I can use the idea from the 2nd pass of passing the function to itself:
(function (wrapper) { return (function (injector) { return wrapper(n => injector(injector)(n)); }(function (injector) { return wrapper(n => injector(injector)(n)); })); }(function(fac) { return function (n) { return (n == 0 ? 1 : n * fac(n - 1)); } }))(5); //=> 120
Yikes. injector(injector)
looks crazy, but that’s just what we have to do when we use the pass-function-to-self-trick. After all, it is a function passing itself to itself, so if you want to use it, you have to have it call itself. Makes perfect sense, how did I not see it before (/sarcasm).
Anyway, time to reap the benefits. This is exactly the Y Combinator! To finish it off, and for absolute correctness, we have to rewrite it to make it as obscure as possible, with less descriptive names.
var result = (f => (x => f(n => x(x)(n))) (x => f(n => x(x)(n)))) (fac => n => (n == 0 ? 1 : n * fac(n - 1)))(5); //=> 120
There, perfect.