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.