# Deriving The Y Combinator

October 23, 2020

To this day I remain in awe of a book that contains both a whole page dedicated to peanut butter jelly stains and a derivation of the Y combinator.

For my own understanding, I decided to “re-derive” the Y combinator by writing it in another language. It’ll be in JavaScript because of its natural syntax for lambda expressions.

The big idea behind the Y combinator, as stated in the book, starts off as a sort of musing — if we cannot give names to functions, how can we write recursive functions?

To expand on that a bit, recursive functions usually refer to themselves by name (or to the name of another function, in the case of mutual recursion), like this:

```
const recursiveLength = arr => {
if (arr.length === 0) return 0;
return 1 + recursiveLength(arr.slice(1));
};
```

However, in some fantasy world (i.e. the world of lambda calculus), there is no such concept of a function referring to itself (The Little Schemer says to pretend that `define`

doesn’t exist), so let’s see how we can achieve recursion by reimplementing `recursiveLength`

.

First off, let’s define some primitive functions:

```
const eternity = () => eternity();
const car = l => l[0];
const cdr = l => l.slice(1);
const isNull = l => l.length === 0;
const add1 = x => x + 1;
```

You might recognize the definition of `eternity`

from a previous post on intuiting the Halting problem.

Now, let’s imagine a silly function, whose only use is to calculate the length of empty arrays.

```
const length0 = l => {
if (isNull(l)) return 0;
return 1 + (eternity(cdr(l)));
};
console.log(length0([])); // 0
```

`length0`

only returns a legitimate value (of 0) for empty arrays. For any other array, `length0`

can be thought of as returning an indeterminate value (i.e. does not terminate).

Using `length0`

, how can we build `length1`

without recursion? We can substitute `eternity(cdr(l))`

with another copy of `length0`

, nesting it like so,

```
const length1 = l => {
if (isNull(l)) return 0;
return add1(
(m => {
if (isNull(m)) return 0;
return add1(eternity(cdr(m)));
})(cdr(l))
);
};
console.log(length1(["a"])); // 1
```

Now, using a sleight of hand, we can “pull” `eternity`

out from `length0`

, supplying it as an argument to a now higher-order function:

```
const length0EternityOut = length =>
(l => {
if (isNull(l)) return 0;
return add1(length(cdr(l)));
})(eternity);
```

The same trick applied to `length1`

:

```
const length1EternityOut = (length => l => {
if (isNull(l)) return 0;
return add1(length(cdr(l)));
})(length1 =>
(m => {
if (isNull(m)) return 0;
return add1(length1(cdr(m)));
})(eternity)
);
```

If we want to write `length2`

, or `lengthN`

, we need to figure out a way to avoid duplicating the function body. If you notice, `length1EternityOut`

has a shape of `f(f(enternity))`

, where `f`

is the function `length => l => ...`

, so we can pull that out:

```
const length1Deduplicate = (f => f(f(eternity)))(
length => l => {
if (isNull(l)) return 0;
return add1(length(cdr(l)));
}
);
```

Again, if you can see, we apply the function `length => l...`

to `f => f(f(eternity))`

and it gives us back the same thing as `length1EternityOut`

. It then becomes much easier to write `length2`

. We simply nest it in another call to `f`

:

```
const length2Deduplicate = (f => f(f(f(eternity))))(
length => l => {
if (isNull(l)) return 0;
return add1(length(cdr(l)));
}
);
```

Now we’re getting somewhere. The `eternity`

is a bit of a red herring — it can be safely removed at this point:

```
const length1NoEternity = (f => f(f(f)))(length => l => {
if (isNull(l)) return 0;
return add1(length(cdr(l)));
});
```

We’re still having to nest calls of `f`

for each increasing `lengthX`

— how do we avoid that? I must admit I was completely stumped at this point. In what I can only call a stroke of genius by whoever thought of this, we can move the “recursive” call inside the function instead, yielding this:

```
const lengthItself = (f => f(f))(length => l => {
if (isNull(l)) return 0;
return add1(length(length)(cdr(l)));
});
```

So we can finally have a “non-recursive” function that can compute lengths of arbitrary arrays.

`console.log(lengthItself(["a", "b", "c"]))`

At this point, you might want to stop and ruminate about how this works before continuing. Convince yourself that whatever we have so far works.

Now for the finishing touch: how can we completely abstract the length function out? The `length(length)`

part can be pulled out yet again:

```
const lengthRefactored = (g => (f => f(f))(f => g(x => f(f)(x))))(
length => l => {
if (isNull(l)) return 0;
return add1(length(cdr(l)));
}
);
```

And that’s it! Whatever you see in the front part is the Y combinator, stated on its own here:

`const y = g => (f => f(f))(f => g(x => f(f)(x)));`

When applied to a lambda, it recursively produces another copy of itself with the new argument, until the function no longer needs it (which in this case is represented by the base case `if (isNull)...`

). This is also the reason it is called a **fixed-point combinator**. A fixed point of a function is a point of the function’s domain whose value remains the same after the function is applied to it. For example, for the function `f(x) = x * x`

, a fixed point would be 1, since `f(1) = 1`

.

In using the term *fixed-point* to refer to the Y combinator, what we’re really trying to say is the Y combinator behaves like this:

`y(g) === g(y(g))`

To me it’s a miracle that evaluating `y(g)`

somehow gives itself back (and nested in an additional `g`

, which is what gives it the recursion). Try evaluating it yourself by hand!

Here are a few more example applications of the Y combinator:

```
const length = y(length => l => {
if (isNull(l)) return 0;
return add1(length(cdr(l)));
});
console.log(length(["a", "b", "c"])); // 3
const fact = y(fact => x => {
if (x <= 2) return x;
return x * fact(x - 1);
});
console.log(fact(5)); // 120
```

It can also work with multiple arguments if the function is curried (or tupled):

```
const exists = y(exists => item => arr => {
if (isNull(arr)) return false;
if (item === car(arr)) return true;
return exists(item)(cdr(arr));
});
console.log(exists("a")(["b", "c"])); // false
console.log(exists("a")(["b", "a"])); // true
```