Refactoring out a Y Combinator.

6 min readAug 18, 2016

There’s a company named “Y Combinator” that hosts a news site called “Hacker News”. You might’ve wondered where the company’s name came from and plugged it into Google, only to be confused by some really scary looking functional-programming-ish stuff. Most of the explanations of the Y combinator go into a lot of detail about higher-order functions and lambdas and stuff.

You don’t really need to understand those things to understand the Y combinator, though— we can derive it just by starting with the factorial function you probably learned in Comp Sci 101 and refactoring it a bunch while following a few basic rules. Here’s our starting point, a recursive factorial function written in Javascript-

function factorial(x) {
  if (x == 0) return 1;
  return x * factorial(x-1);
}> console.log( factorial(5) );
> 120

Yep, it works as expected. Now let’s add a new rule to our code. Pretend for a moment that for some reason it’s forbidden for a function to call itself directly — that ‘factorial(x-1)’ line will have to be changed.

Luckily, Javascript is a language where you can pass functions into other functions and everything just works. This lets us get around our new rule by passing a copy of ‘factorial’ into itself -

function factorial(x, copy_of_factorial) {
  if (x == 0) return 1;
  return x * copy_of_factorial(x - 1, copy_of_factorial);
}> console.log( factorial(5, factorial) );
> 120

Note that since ‘factorial’ now takes two arguments, we have to pass the copy to the copy… yeah, it hurts my head a bit too. Read through it again and try to follow how it works — we’ll be using this trick later.

Anyway, *abracadabra*, ‘factorial’ doesn’t call itself anymore… but now it looks weird and it’s a bit of a pain to use. Whenever we call it, we have to give it a copy of itself.

Let’s try to work around that by breaking the problem into smaller pieces. What if we had a function that just did one step of the factorial math instead of doing the whole thing at once?

function factorial_step(x) {...

Uh, wait — what does it actually mean to do ‘one step’ of the factorial function? What do we write here? Well, let’s go back to the original version-

function factorial(x) {
  if (x == 0) return 1;
  return x * factorial(x-1);
}

We want to get rid of that recursive bit, but we need _something_ to go on the right hand side of the * sign. Let’s pretend that we already have a ‘do the next step’ function somewhere and we can just pass it into our ‘do one step’ function like this-

function factorial_step(x, next_step) {
  if (x == 0) return 1;
  return x * next_step(x-1);
}

Waaaait a second… ‘next_step’ is the factorial function. This seems like a problem — we can write factorial_step, but we can’t actually call it unless we have a working factorial function to give it. And we don’t have a working factorial function yet because we’re trying to build one out of factorial_step….

We’re going to need some way out of this, so we need to leverage another feature of Javascript — we can write functions that write functions. What if we had a ‘make_factorial’ function that, if you gave it the ‘factorial_step’ function, it could write a working factorial function for us?

function make_factorial(factorial_step) {
  ...
}

We know that make_factorial has to return a function, and that the function it returns has to take the same ‘x’ argument the original version of ‘factorial’

function make_factorial(factorial_step) {
  return function(x) {
    ...
  }
}

We also know that inside the inner function we’re going to have to call our ‘factorial_step’ function

function make_factorial(factorial_step) {
  return function(x) {
    return factorial_step(x, ...);
  }
}

… and we’re stuck again. Where do we get the ‘next_step’ that we have to pass to ‘factorial_step’? If only we had a working factorial… oh wait, we’re in the middle of a function that writes those right now. Can we call ‘make_factorial’… from inside the function that ‘make_factorial’ is making?

function make_factorial(factorial_step) {
  return function(x) {
    return factorial_step(x, make_factorial(factorial_step));
  }
}

… wait, we can do that? Does that even work?

function make_factorial(factorial_step) {
  return function(x) {
    return factorial_step(x, make_factorial(factorial_step));
  }
}var new_factorial = make_factorial(factorial_step);> console.log(new_factorial(5));
> 120

Huh, it seems to work. At first glance you might think this causes a stack overflow or an infinite loop or something, but if you step through it really carefully it does in fact terminate — eventually ‘factorial_step’ hits the ‘x == 0’ condition and we stop creating new functions.

Unfortunately ‘make_factorial’ is now breaking the “functions can’t call themselves” rule, and it’s somehow doing it from inside a function while it’s still writing it or something. We’ve moved the original problem from ‘factorial’ to ‘make_factorial’, our code is more complicated, and we seem to have made no progress.

Can we fix this by using the ‘call a function with a copy of itself’ trick that we tried to use earlier?

function make_factorial(factorial_step, copy) {
  return function(x) {
    return factorial_step(x, copy(factorial_step, copy));
  }
}var new_factorial = make_factorial(factorial_step, make_factorial);

OK, that seems to work too, but now I’m definitely getting a headache. Now it’s ‘make_factorial’ that has to be called in a weird way, but at least it doesn’t call itself any more.

Let’s try and hide the weirdness a bit by putting a wrapper around it.

function make_factorial(factorial_step, copy) {
  return function(x) {
    return factorial_step(x, copy(factorial_step, copy));
  }
}function wrapper(factorial_step) {
  return make_factorial(factorial_step, make_factorial);
}var new_factorial = wrapper(factorial_step);

That’s a little better. The wrapper function actually looks like what we want — we give it the factorial step and we get a working factorial function out of it.

Since the wrapper is the only thing using ‘make_factorial’, we can move ‘make_factorial’ inside the wrapper entirely — totally allowed in Javascript.

function wrapper(factorial_step) {
  function make_factorial(factorial_step, copy) {
    return function(x) {
      return factorial_step(x, copy(factorial_step, copy));
    }
  }
  return make_factorial(factorial_step, make_factorial);
}

And now that we’ve got that sorted, it’s worth noting that ‘wrapper’ isn’t actually doing anything factorial-specific at all. Sure, its argument is currently named ‘factorial_step’, but we could give it any sort of “do one step” function and it would turn it into something that works like a “do all the steps” function but without breaking the functions-calling-themselves rule.

Since nothing here is factorial-specific, let’s rename things for clarity. We’ll change ‘wrapper’ to ‘make_recursive’, since it sort of recursive-izes the functions we give it. Our ‘factorial_step’ can become just ‘step’. The inner ‘make_factorial’ is what actually creates the new function, so we can name it ‘make_function’.

function make_recursive(step) {
  function make_function(step, copy) {
    return function(x) {
      return step(x, copy(step, copy));
    }
  }
  return make_function(step, make_function);
}

One other thing — since ‘make_function’ can see the copy of ‘step’ that was passed into ‘make_recursive’, it doesn’t need its own copy anymore.

function make_recursive(step) {
  function make_function(copy) {
    return function(x) {
      return step(x, copy(copy));
    }
  }
  return make_function(make_function);
}

That’s pretty weird how some of the calls collapse down into ‘copy(copy)’ and ‘make_function(make_function)’, isn’t it? Let’s put all our pieces together and see what we get.

function make_recursive(step) {
  function make_function(copy) {
    return function(x) {
      return step(x, copy(copy));
    }
  }
  return make_function(make_function);
}function factorial_step(x, next_step) {
  if (x == 0) return 1;
  return x * next_step(x-1);
}var new_factorial = make_recursive(factorial_step);> console.log(new_factorial(5));
> 120

It looks like we’re done. We feed ‘factorial_step’ to ‘make_recursive’ and we get a new function that works like the recursive factorial, but without breaking the functions-calling-themselves rule.

Not only that, but the ‘make_recursive’ function _is_ the “Y combinator” you’ve read about, even if it looks a little different here. Its job is to take a non-recursive “do one step” function and turn it into a recursive-ish “do all the steps” function.

If you only look at the final product, it’s hard to figure out how the hell it even works. It’s even harder to figure out if you see it written using only single-character function names like ‘y’ and ‘h’ and ‘g’.

It’s not magical though — it’s just what happens if you start by trying to write a factorial function and then work around your language limitations by giving functions copies of themselves. Simple.

Ok, you’re right, it’s not simple and it’s probably not something you’re going to need to use unless you’re doing some seriously esoteric programming in strange and limited languages. It’s interesting though, and I think it’s worth spending a few minutes playing around with.

Refactoring out a Y Combinator.

Written by Austin Appleby