2013-09-20 00:00:00 +0100 by Alex R. Young

This is a guest post by Michael Hurley. The original is here: JavaScript Y Combinator.

At the end of The Little Schemer, the authors lead you step-by-step through the process of deriving the Y combinator. They do this repeatedly abstracting a `length`

function--and then magically, the Y combinator appears. It is a pretty neat trick, and certainly mind-bending on your first read through the book.

Since JavaScript has first-class functions, we can derive the Y combinator in JavaScript as well. I will take a different approach than *The Little Schemer*. This approach owes a lot to a couple of blog posts I read on the subject^{1}.

Since this is a post about recursive functions, then we can use that old chestnut, `factorial`

. Here is a possible implementation of `factorial`

in JavaScript:

```
function basicFactorial(n) {
return n === 0 ? 1 : n * basicFactorial(n-1);
}
```

Let's start by making a non-recursive `basicFactorial`

, which we'll call `nonRecursive`

:

```
function nonRecursive(f) {
return function(n) {
return n === 0 ? 1 : n * f(n-1);
}
}
```

All we've done here is replace the recursive call of `basicFactorial`

. Instead, we pass in a function that will get called. We can pass any function that returns something that supports the `*`

operator:

```
nonRecursive(function(x) { return 0; })(100); // => 0
nonRecursive(function(x) { return 1; })(100); // => 100
nonRecursive(function(x) { return 10; })(100); // => 1000
// ... etc.
```

But it starts to get a little interesting when we pass `basicFactorial`

in there. Then we get back ... `basicFactorial`

!

```
nonRecursive(basicFactorial)(4) === basicFactorial(4);
nonRecursive(basicFactorial)(10) === basicFactorial(10);
nonRecursive(basicFactorial)(17) === basicFactorial(17);
// ... etc.
```

In other words, `basicFactorial`

is a fixed point of the function `nonRecursive`

.

This is pointless here, since we have already defined `basicFactorial`

. But suppose we had not defined `basicFactorial`

. Wouldn't it be nice if there was a function that we could pass `nonRecursive`

to that would return the fixed point of it, i.e. the `factorial`

function?

That is what the Y combinator does. Pass `nonRecursive`

to `Y`

, and out comes the factorial function:

```
Y(nonRecursive)(100); // 9.33262154439441e+157
```

Note that:

```
Y(nonRecursive)(100) === nonRecursive(basicFactorial)(100);
```

Or in other words:

```
Y(nonRecursive)(100) === nonRecursive(Y(nonRecursive))(100);
```

So if we have `Y`

, we do not need to define `basicFactorial`

*at all*, we let `Y`

derive it from the non-recursive function `nonRecursive`

. Now let's look at it from the other direction, and build up to `Y`

. Here again, is the functional `nonRecursive`

that we want to calculate the fixed point of:

```
function nonRecursive(f) {
return function(n) {
return n === 0 ? 1 : n * f(n-1);
}
}
```

As noted above, pass `basicFactorial`

in, and `nonRecursive`

returns `basicFactorial`

. Notice that we have pretty much defined factorial in the body of `nonRecursive`

: `return n === 0 ? 1 : n * f(n-1);`

--why not use that? So here's our next try: Apply `nonRecursive`

to itself. This requires a small change to the body of `nonRecursive`

, to self-apply the passed-in function to get the body out and apply it to the inner argument.

```
function nonRecursive(f) {
return function(n) {
return n === 0 ? 1 : n * f(f)(n-1);
};
}
nonRecursive(nonRecursive)(5); // => 120
```

Now we want to isolate the fixed point function. Let's wrap that in a function `g`

:

```
function nonRecursive(f) {
return function(x) {
var g = function(q) {
return function(n) {
return n === 0 ? 1 : n * q(n-1);
};
};
return g(f(f))(x);
};
}
```

Since inner function `g`

does not depend on anything in closure, we can pull it out:

```
function g(f) {
return function(n) {
return n === 0 ? 1 : n * f(n-1);
};
}
```

The pulled-out function may look familiar--it's `nonRecursive`

again. Here's what's left over after `g`

(a.k.a. `nonRecursive`

) is pulled out; let's call it `almostY`

:

```
function almostY(f) {
return function(x) {
return g(f(f))(x);
};
}
almostY(almostY)(5); // => 120
```

We've pulled `g`

out of `almostY`

, but `almostY`

still depends on `g`

. The final step is to wrap `almostY`

in a function that takes the functional `g`

as an argument. Then `almostY`

will have no dependencies.

So, let's wrap it in a function that takes our non-recursive factorial functional and returns the fixed point of it. And since this is the last step, let's call that function `Y`

:

```
function Y(f) {
var p = function(h) {
return function(x) {
return f(h(h))(x);
};
};
return p(p);
}
Y(g)(6); // => 720
```

Holy crap! It works! But it's not just for factorial--`Y`

will provide a fixed point for any unary function, e.g.

```
function nonRecursiveFibonacci(f) {
return function(n) {
return n < 2 ? n : f(n-1) + f(n-2);
};
}
Y(nonRecursiveFibonacci)(10); // => 55
```

As presented, this version of `Y`

can only handle unary functions, and it will blow up the stack for relatively low values of `n`

. It is straightforward to extend `Y`

to handle functions of any arity, and to memoize it.

- I found these articles helpful: Fixed-point combinators in JavaScript: Memoizing recursive functions and Deriving the Y combinator.