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. Real men use it 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 looks cooler that way, and 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 oh yeah, it’s an awesome way to sink your time if you’re looking for a good puzzle.

I stared at it for 3 hours before I understood it.

Oh the joy of figuring things out… But then I thought to myself, could I derive it if I didn’t know it?

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)`

. Not cool… 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 I think I even started talking to myself at some point, so I decided to try a different approach.

Time to cheat a little bit, with a named function. Too much lambda. Need name. More 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. Where am I?

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, that’s better.