Y: The Most Beautiful Idea in Computer Science explained in JavaScript
In this post, we will talk about one of the most beautiful ideas in computer science: the Y-Combinator. And no, I’m not talking about the VC firm in Silicon Valley, even though this post will explain why they’ve got this name.
Put in simple terms, the Y-Combinator (also known as the fixed-point combinator) is a way of doing recursion in a language that does not explicitly supports it.
Let’s say you want to implement a recursive factorial function. In JavaScript, for example, you could simply do this:
const factorial = n => n === 0 ? 1 : n * factorial(n - 1);
But what if you couldn’t use any “names”? What if JavaScript didn’t allow you to call factorial
inside of factorial
, how would you implement it?
In that case, you’d use the Y-Combinator.
It doesn’t have many use cases for solving real world problems, but it is not only one of the most mind blowing ideas in computer science and a great mental exercise, but it also separates those who really understand what functional programming is about from those who don’t.
Before we start I need to warn you that deriving the Y-Combinator for the first time is hard and that it’s normal to struggle with it. So don’t feel bad if you have to read this blog post more than once in order to get it. I tried to make it very detailed and show every single step of what is happening on each example but if you feel like you’re advanced enough and want to read the short version of it, just click here.
I recommend that you follow this post with a notebook or on Node’s REPL and test things by yourself, that will help you understand all the steps we’ll go through. Don’t be afraid of trying things out and testing each example. Doing your own exploration plays a great part in understanding how Y works.
Also, if you want to learn more about recursion I’ve got a very popular post about it in this very same blog. It’s a bit old but it remains amazing and very informative.
I guarantee you this will be one of the most amazing journeys you will go through when it comes to functional programming. The first time deriving the Y-Combinator is an indescribable joy, so get comfortable in your chair, bed, or whatever and let’s get started.
First things first: what on earth is a combinator?
A combinator is a function with no free variables.
Free variables are variables defined outside of the function’s scope. They’re the opposite of bound variables, which are variables that only exist inside of a function’s scope.
Let’s use an example to make it easier to understand:
const num = 13;
const sumPlusThirteen = (a, b) => a + b + num;
In the example above, our function sumPlusThirteen
uses the variables a
, b
and num
. The variables a
and b
are bound variables because they are bound to the function’s parameters: when we refer to their names we are referring to values that were passed to the sumPlusThirteen
function. However, the variable num
refers to a value outside of the function’s scope, which means it is a free variable.
Let’s look at some more examples:
x => x
-x
is a bound variable, because it’s bound to the function’s parametersx => x + y
-x
is a bound variable because it’s bound to the function’s parameters andy
is a free variable because it refers to a value outside of the function’s scopex => y + z
-y
andz
are both free variables because they refer to values outside of the function’s context(x, y) => x + y
- Bothx
andy
are bound variables because they are bound to the function’s parameters
Getting back to combinators, we can now say that the following functions are all combinators:
x => x
is a combinator becausex
is the only variable in the function’s body and it’s bound to the function’s parameters(x, y) => y
- is a combinator because the only variable in its body (y
) is bound to the function’s parameters.x => y
- is not a combinator because the variable in its body (y
) refers to something outside of the function’s context(x, y) => x(y(z))
is not a combinator, because one of the variables in its body (z
) refers to a something outside of the function’s context
I could write an entire blog post about this, but for now, this basic knowledge will suffice. I highly recommend that you read more about bound versus free variables and pass-by-context versus pass-by-name though.
Deriving Y
Discovering what we need
Now that we know what a combinator is, let’s get to the funniest part of this post and derive the Y-Combinator itself.
Let’s get back to our recursive factorial definition:
const factorial = n => n === 0 ? 1 : n * factorial(n - 1);
// I'm just using this to prove it actually works
console.log(factorial(5)); // 120
This is how it works:
As you might remember, what we want is a way of calling factorial
without referring to its own name, we want a function which does not have any free variables, but is still recursive.
Considering this goal, the most obvious thing here would be to eliminate the call to factorial
inside the function’s body. In order to do this, we’d do one of the simplest and most common refactoring techniques in functional programming: we’ll remove the factorial
reference from the function’s body and make it a parameter:
const factorialGenerator = f => n => n === 0 ? 1 : n * f(n - 1);
Now, in order for us to calculate the factorial of a number we must pass a function f
to factorialGenerator
so that it can call it with n - 1
whenever n
is not 0
. If you passed in a function myFun
, for example, you’d get back: n => n === 0 ? 1 : n * myFun(n - 1)
.
Let’s see what happens if we call this function with any function and then 0
:
const literallyAnyFunction = () => null
const factorialGenerator = f => n => n === 0 ? 1 : n * f(n - 1);
console.log(factorialGenerator(literallyAnyFunction)(0)); // 1
Look, it already works for 0
, and we can use literallyAnyFunction
for that! Isn’t it amazing?
This is because when passing zero to the function returned by factorialGenerator
, n
will be equal 0
and then it will return 1
. We won’t even need to call the function we passed in (which is literallyAnyFunction
).
But what if we try to calculate the factorial of 1
in the same way?
const literallyAnyFunction = () => 'a string'
const factorialGenerator = f => n => n === 0 ? 1 : n * f(n - 1);
console.log(factorialGenerator(literallyAnyFunction)(1)); // NaN
Whoah seems like we’ve got NaN
. This definitely not right!
In order to understand what has happened let’s take a look at the function returned by calling factorialGenerator
and passing it literallyAnyFunction
:
const literallyAnyFunction = () => 'a string'
const factorialGenerator = f => n => n === 0 ? 1 : n * f(n - 1);
const fn = factorialGenerator(literallyAnyFunction);
// fn is: n => n === 0 ? 1 : n * (() => 'a string')(n - 1));
As you can see, in the function returned by factorialGenerator(literallyAnyFunction)
, if n
is not 0
we will have to call literallyAnyFunction
with n - 1
and then multiply the result of that by n
. And what is the result of multiplying a String
by a Number
in JavaScript? Exactly, it’s NaN
.
Okay, but what if try calculating the factorial of 2
also using factorialGenerator(literallyAnyFunction)
? Will it work?
const literallyAnyFunction = () => 'a string'
const factorialGenerator = f => n => n === 0 ? 1 : n * f(n - 1);
console.log(factorialGenerator(literallyAnyFunction)(2)); // NaN
Of course not. It’s still NaN
. But that’s not what I want to show you this time. What I want to show you is that literallyAnyFunction
has only been called once.
This is what happened:
factorialGenerator
has been called withliterallyAnyFunction
and returned a function- That function has been called with
2
2
is not equal0
, so we’ll do2 * literallyAnyFunction(2 - 1)
literallyAnyFunction(2 - 1)
will return'a string'
- We’ll try to multiply
'a string'
by2
andNaN
will be returned
As I’ve said, there was only a single call to literallyAnyFunction
.
Let’s make that more obvious by adding a console.log
to literallyAnyFunction
, like this:
const literallyAnyFunction = () => {
console.log('f has been called!')
return 'a string'
}
const factorialGenerator = f => n => n === 0 ? 1 : n * f(n - 1);
console.log(factorialGenerator(literallyAnyFunction)(2));
See? literallyAnyFunction
has only been called once. Now test it again with 0
, 1
and 2
. What happens?
- For
0
it returns1
, which is the correct answer and does not callliterallyAnyFunction
at all - For
1
and2
it returnsNaN
, which is the correct answer and callsliterallyAnyFunction
once
Do you notice any pattern here? Whenever we have to call literallyAnyFunction
and multiply the string it returns we get back NaN
. If only we had a way to avoid it…
Well, we actually have!
If we call factorialGenerator
with factorialGenerator(literallyAnyFunction)
, the first time f
is called, it will be factorialGenerator
, which means we’ll call factorialGenerator
with n - 1
instead of calling literallyAnyFunction
.
Look!
const literallyAnyFunction = () => {
console.log('f has been called!')
return 'a string'
}
const factorialGenerator = f => n => n === 0 ? 1 : n * f(n - 1);
const result = factorialGenerator(
factorialGenerator(literallyAnyFunction)
)(1);
// It works!
console.log(result); // 1
Awesome, it works! But what did happen?
- The first thing that has been evaluated was
factorialGenerator(literallyAnyFunction)
. That returned a function which returns1
if the argument passed to it is0
, otherwise, it will call theliterallyAnyFunction
passed to it - Then we call
factorialGenerator
again with that function we’ve just returned - Finally, the function we’ve obtained will only call
factorialGenerator
the first time it has to callf
. After that, it will callliterallyAnyFunction
- When it’s called with it
1
it sees that1
is not equal to0
, so it will callf
(which isfactorialGenerator
) withn - 1
(a.k.a.0
) and multiply the result of that by1
- Now that
factorialGenerator
has been called with0
it will see thatn
is equal to0
and return1
. This1
will be multiplied by1
, returning1
, which is the correct answer.
Notice that literallyAnyFunction
has not been called at all.
If understanding recursion still seems hard to you, once again I recommend you to read this blog post where I explain how to think about recursion in an easy way first and then come back here.
Another question for you: will this technique work with 2
too?
const literallyAnyFunction = () => {
console.log('f has been called!')
return 'a string'
}
const factorialGenerator = f => n => n === 0 ? 1 : n * f(n - 1);
const result = factorialGenerator(
factorialGenerator(literallyAnyFunction)
)(2);
console.log(result); // NaN
Oops! It doesn’t!
As you can see, this time, literallyAnyFunction
has been called, because the second time we have to call f
it was literallyAnyFunction
. How could we avoid it? Easy, just pass in factorialGenerator
again.
const literallyAnyFunction = () => {
console.log('f has been called!')
return 'a string'
}
const factorialGenerator = f => n => n === 0 ? 1 : n * f(n - 1);
const result = factorialGenerator(
factorialGenerator(
factorialGenerator(literallyAnyFunction)
)
)(2);
console.log(result); // 2
Look, it works again! This happens because we don’t call, literallyAnyFunction
, instead, we just keep calling factorialGenerator
until we reach 0
, then the results bubble back up, the same way it happened in the previous example.
This is what happened this time:
const literallyAnyFunction = () => {
console.log('f has been called!')
return 'a string'
}
const factorialGenerator = f => n => n === 0 ? 1 : n * f(n - 1);
const result = factorialGenerator(
factorialGenerator(
factorialGenerator(literallyAnyFunction)
)
)(2);
// n => 2 === 0 ? 1 : 2 * factorialGenerator(2 - 1)
// n => 1 === 0 ? 1 : 1 * factorialGenerator(1 - 1)
// n => 0 === 0 ? 1 : 0 * literallyAnyFunction(0 - 1) - literallyAnyFunction won't be called!
console.log(result); // 2
Want to make it work for 3
? Easy, just add another call to factorialGenerator
:
const literallyAnyFunction = () => {
console.log('f has been called!')
return 'a string'
}
const factorialGenerator = f => n => n === 0 ? 1 : n * f(n - 1);
const result = factorialGenerator(
factorialGenerator(
factorialGenerator(
factorialGenerator(literallyAnyFunction)
)
)
)(3);
console.log(result); // 6
Feel like calculating the factorial of 4
too? There goes another call to factorialGenerator
:
const literallyAnyFunction = () => {
console.log('f has been called!')
return 'a string'
}
const factorialGenerator = f => n => n === 0 ? 1 : n * f(n - 1);
const result = factorialGenerator(
factorialGenerator(
factorialGenerator(
factorialGenerator(
factorialGenerator(literallyAnyFunction)
)
)
)
)(4);
console.log(result); // 24
We’ve got so many parentheses in that example it already started looking like LISP.
This shows that in order to be able to calculate the factorial
of any number we’d just need to have infinite calls to factorialGenerator
being passed to each other:
const literallyAnyFunction = () => {
console.log('f has been called!')
return 'a string'
}
const factorialGenerator = f => n => n === 0 ? 1 : n * f(n - 1);
const factorial = factorialGenerator(
factorialGenerator(
factorialGenerator(
factorialGenerator(...)
)
)
);
Another way to think about this is that what you want to happen is for the f
inside factorialGenerator
to always be the function returned by it. By doing this you guarantee that you will always call the inner function again.
Fixed Points
Now let’s stop for a moment a talk about another very important concept for understanding Y: the fixed point.
The fixed point of a function is that value that when applied to it results in itself. Basically, if you call a function f
with fixpoint
, the output should be equal to fixpoint
.
Get a calculator and just keep pressing the cos
key until the result doesn’t change anymore. You should get something like 0.73908513321
(might change depending on your calculator’s precision). This means that 0.73908513321
is the fixed point of the cos
function since once we do cos(0.73908513321)
we get back 0.73908513321
.
Let’s summarize this in a single expression:
f(fixpoint) = fixpoint
As you can see, since f(fixpoint
) is the same thing as fixpoint
we can just replace the fixpoint
inside of f
with f(fixpoint)
, like this:
// I've put f(fixpoint) to the right to make it easier to read
fixpoint = f(fixpoint)
fixpoint = f(f(fixpoint))
fixpoint = f(f(f(fixpoint)))
fixpoint = f(f(f(f(fixpoint))))
fixpoint = f(f(f(f(f(fixpoint)))))
// We could go on forever...
This looks familiar, doesn’t it? Of course it does, it’s exactly what we want! We want to be able to nest infinite calls to factorialGenerator
inside of itself whenever we need to do recursion.
This is why we want to find the Y combinator. The Y Combinator is the combinator that allows us to find the fixpoint of a function like factorialGenerator
so that we can make it recursive!
Finding Y
When applying a function to Y we want it to return the fixed point of that function, like this:
Y(f) = fixpoint
Considering that the fixpoint
of a function is the value that when applied to it returns fixpoint
, we can also say that:
Y(f) = fixpoint
Y(f) = f(fixpoint)
Now, if we just replace the fixpoint inside that second expression, look at what we’ve got:
Y(f) = f(Y(f))
That’s the definition of what Y does! When passing a function f
to Y
, that’s what it does (f(Y(f))
). So, instead of showing what it does, let’s define the Y function just by taking f
as an argument instead of applying it to Y
:
const Y = f => f(Y(f))
Now, we’re supposed to call Y
passing factorialGenerator
and get back a factorial
function that works, right? Can we do this?
const factorialGenerator = f => n => n === 0 ? 1 : n * f(n - 1);
const Y = f => f(Y(f));
const factorial = Y(factorialGenerator);
console.log(factorial(5));
Nope, just not yet. If you try to execute the snippet above, this will happen:
RangeError: Maximum call stack size exceeded
at Y (repl:1:11)
at Y (repl:1:18)
at Y (repl:1:18)
at Y (repl:1:18)
at Y (repl:1:18)
at Y (repl:1:18)
at Y (repl:1:18)
at Y (repl:1:18)
at Y (repl:1:18)
at Y (repl:1:18)
You will get a Stack Overflow because Y
is calling itself infinitely. If you stop and replace Y(f)
in the body of that function with its result, this will become obvious:
const Y = f => f(Y(f));
// This is what happens when we apply `f` to it:
// Y(f) = f(Y(f));
// That means we can replace every `Y(f)` with `f(Y(f))`
// = f(Y(f));
// = f(f(Y(f)));
// = f(f(f(Y(f))));
// And so on...
In fact, this very definition would work in lazy (a.k.a. non-strict
) languages, because we would not need to evaluate that Y(f)
in the body of Y
instantly, instead we would only evaluate it when needed. This means that instead of infinitely doing that “replacement” we’ve just done, we would get back the function returned by f
with Y(f)
being the first argument it takes (without having to evaluate it).
Okay, so, in order to translate this to JavaScript we will need to delay the execution of Y(f)
so that it does not get called immediately when we pass a function to Y
.
And what is the easiest way of delaying the execution of a function in JavaScript
?
A thunk! A thunk is a function that wraps an expression to delay its evaluation.
// calculation of 1 + 2 is immediate
// x === 3
let x = 1 + 2;
// calculation of 1 + 2 is delayed
// foo can be called later to perform the calculation
// foo is a thunk!
let foo = () => 1 + 2;
Does this remember you of anything you probably use on a daily basis if you work with Redux? Exactly, that’s exactly what redux-thunk was made for. In fact, the very example above has been taken from their README.
Now that we know what a thunk is, let’s delay the execution of f(Y(f))
by wrapping it into a function:
const Y = f => x => f(Y(f))(x);
Since the function returned by factorialGenerator
will only take a single argument as a parameter, we can just wrap it inside a function that also takes a single argument and applies it to the result of f(Y(f))
, which now will be a function that also takes a single argument instead of evaluating infinitely.
Let’s make this more obvious by imagining what happens when we invoke Y with factorialGenerator
and then apply 5
to it:
const factorialGenerator = f => n => n === 0 ? 1 : n * f(n - 1);
const Y = f => x => f(Y(f))(x);
const factorial = Y(factorialGenerator);
console.log(factorial(5));
- Since Y returns a function which takes a single argument we’ll get the function in its body back, which is
x => f(Y(f))(x)
. In that function we will be able to replace allf
s withfactorialGenerator
:x => factorialGenerator(Y(factorialGenerator))(x)
The trick here is that since everything is still wrapped inside of a function which takesx
as an argument, we will only evaluate it when we passx
to that function. - The trick here is to notice that
factorialGenerator(Y(factorialGenerator))
will take that function whichY(factorialGenerator)
returns but won’t evaluate it once we have passed an argument (x
) to it. It will basically return this:n => n === 0 ? 1 : n * Y(factorialGenerator)(n - 1)
. - Doing another expansion, since
Y(factorialGenerator)
is equal tox => factorialGenerator(Y(factorialGenerator))(x)
(as we’ve seen on step 1) we get:n => n === 0 ? 1 : n * (x => factorialGenerator(Y(factorialGenerator)))(n - 1)
- Finally, we can invoke the function on the previous step with
5
, for example. This will cause the function in the body offactorialGenerator
to haven
replaced by5
, andf
will be the result ofY(factorialGenerator)
, which is the exact same function we had on step 1. We’ll then call the function on step 2 with5 - 1
:5 === 0 ? 1 : 5 * (x => factorialGenerator(Y(factorialGenerator)))(5 - 1)
. - This process will be repeated until we don’t call the function on step 1 anymore, but return 1 instead because
n
reached 0, causing the multiplication to run and return the final result.
And this, my friends, is the very definition of Y, but it is not the Y combinator yet.
As you might remember, in order for it to be a combinator we should not have any free variables in its body, but in this case, we’ve got an explicit call to Y
.
Finding The Y Combinator
There are many ways to derive the Y Combinator, but I think that the easiest one for most people is, by far, to go from the factorial function to Y instead of using mathematical expressions.
As you might remember, at first we had a explicitly recursive factorial
function which looked like this:
const factorial = n => n === 0 ? 1 : n * factorial(n - 1);
Then, in order to remove explicit recursion we made the explicit recursive call to factorial
an argument of this function:
const factorialGenerator = f => n => n === 0 ? 1 : n * f(n - 1);
Now, factorialGenerator
is not explicitly recursive anymore, instead, it calls the function f
passed to it. As long as the f
inside of it is the function returned by factorialGenerator
, we will be able to calculate factorials, since we’ll keep invoking the inner function: n => n === 0 ? 1 : n * f(n - 1)
.
But how can we make factorialGenerator
always invoke its inner function?
We can make f
call itself inside its body:
const factorialRecursive = f => n => n === 0 ? 1 : n * f(f)(n - 1);
const factorial = factorialRecursive(factorialRecursive);
console.log(factorial(5)); // 120
And it works! This is because the first time we invoke factorialRecursive
we get back:
n => n === 0 ? 1 : n * factorialRecursive(factorialRecursive)(n - 1);
And then, when invoking it with 5
, for example, we’ll call exactly the same function: factorialRecursive(factorialRecursive)
, which, as you can see above, is the very same definition of factorial
(and therefore returns the same thing).
This means that it will keep calling factorialRecursive(factorialRecursive)
(which is, in fact, factorial
) until n
reaches 0
, meaning it will then return 1
and allow us to calculate the factorial of a number. Just like this:
const factorialRecursive = f => n => n === 0 ? 1 : n * f(f)(n - 1);
const factorial = factorialRecursive(factorialRecursive);
// factorial is: n => n === 0 ? 1 : n * factorialRecursive(factorialRecursive)(n - 1);
console.log(factorial(5)); // 120
// n => 5 === 0 ? 1 : 5 * factorialRecursive(factorialRecursive)(5 - 1);
// n => 4 === 0 ? 1 : 4 * factorialRecursive(factorialRecursive)(4 - 1);
// n => 3 === 0 ? 1 : 3 * factorialRecursive(factorialRecursive)(3 - 1);
// n => 2 === 0 ? 1 : 2 * factorialRecursive(factorialRecursive)(2 - 1);
// n => 1 === 0 ? 1 : 1 * factorialRecursive(factorialRecursive)(1 - 1);
// n => 0 === 0 ? 1 : 0 * factorialRecursive(factorialRecursive)(0 - 1); // returns 1
// Notice that you can replace all the `factorialRecursive(factorialRecursive)` occurrences
// above for `factorial`, because they are the same thing.
Keep in mind that our goal is to make this process generic enough so that we can make it work for any function we want to make recursive, so let’s remove f(f)
so that we can get factorialGenerator
back and extract it into the near future.
Making it an argument of that function and passing it inside through an immediately invoked function is how we’re going to do that:
const factorialRecursive = myFun => (f => n => n === 0 ? 1 : n * f(n - 1))(myFun(myFun));
const factorial = factorialRecursive(factorialRecursive)
console.log(factorial(5)); // RangeError: Maximum call stack size exceeded
Stack Overflow! Why did that happen? That happened because myFun(myFun)
is the first thing to be evaluated, causing factorialRecursive
to keep invoking itself indefinitely.
Remember what is the easiest way of delaying the execution of a function? Exactly, wrap it into another function.
const factorialRecursive = myFun => (f => n => n === 0 ? 1 : n * f(n - 1))((x) => myFun(myFun)(x));
const factorial = factorialRecursive(factorialRecursive)
console.log(factorial(5)); // 120
Cool, it seems like we’re back on track again. Now, we’ll only evaluate myFun(myFun)
everytime we pass an x
in.
Also, renaming myFun
to g
might make it easier to read:
const factorialRecursive = g => (f => n => n === 0 ? 1 : n * f(n - 1))((x) => g(g)(x));
const factorial = factorialRecursive(factorialRecursive)
console.log(factorial(5)); // 120
The cool thing is that now we don’t even need to define factorial as factorialRecursive(factorialRecursive)
anymore, we can just copy and paste it, making it call itself in its very same definition, like this:
const factorial = (
g => (f => n => n === 0 ? 1 : n * f(n - 1))((x) => g(g)(x)) // The function
)(g => (f => n => n === 0 ? 1 : n * f(n - 1))((x) => g(g)(x))); // Itself again as an argument
console.log(factorial(5)); // 120
I think we can all agree that just copying and pasting that function is a bit ugly, so why don’t we create a function which takes a function and invokes it with itself and uses it?
// `g => g(g)` is a function that takes a function and ivokes it with itself
const factorial = (g => g(g))(g => (f => n => n === 0 ? 1 : n * f(n - 1))((x) => g(g)(x)))
console.log(factorial(5)); // 120
Much better!
Finally we can extract the very definition of factorialGenerator
(f => n => n === 0 ? 1 : n * f(n - 1)
) we’ve got in the body of factorial
and pass it in as an argument to make that function generic:
const factorialGenerator = f => n => n === 0 ? 1 : n * f(n - 1);
const yCombinator = f => (g => g(g))(g => f((x) => g(g)(x)))
const factorial = yCombinator(factorialGenerator);
console.log(factorial(5)); // 120
This is the Y-Combinator!
Applying it to other recursive functions
Our Y-Combinator works with any non-explicitly recursive function which takes a single argument.
Let’s see how it works for the Fibonacci function.
We’ll start by defining the Fibonacci function itself. It returns the Fibonacci number on a certain index n
.
const fibonacci = n => n <= 1 ? 1 : fibonacci(n - 1) + fibonacci(n - 2);
Now, let’s eliminate the explicit recursion by removing the explicit calls to fibonacci
and making it an argument:
const fibonacciGenerator = f => n => n <= 1 ? 1 : f(n - 1) + f(n - 2);
Finally, if we pass fibonacciGenerator
to our Y-Combinator
we’ll get back a recursive fibonacci
function:
const fibonacciGenerator = f => n => n <= 1 ? 1 : f(n - 1) + f(n - 2);
const yCombinator = f => (g => g(g))(g => f((x) => g(g)(x)))
const fibonacci = yCombinator(fibonacciGenerator)
console.log(fibonacci(0)); // 1
console.log(fibonacci(1)); // 1
console.log(fibonacci(2)); // 2
console.log(fibonacci(3)); // 3
console.log(fibonacci(4)); // 5
console.log(fibonacci(5)); // 8
The VC firm in Sillicon Valley
Paul Graham himself is known for his amazing work on Lisp, so he’s obviously very proficient when it comes to functional programming and therefore knows the Y-Combinator.
According to YC’s own website, this is why they’ve chosen the name:
The Y Combinator is one of the coolest ideas in computer science. It’s also a metaphor for what we do. It’s a program that runs programs; we’re a company that helps start companies.
Now that we know a bit about Y we can explore the meaning behind this name a bit more.
By taking into account that YC accelerates startups we can say that:
YC(accelerateStartups)(startup)
And as long as accelerateStartups
doesn’t reach its base case (either by running out of money or motivation), we’ll keep feeding it with more and more startups.
Well done, Mr. Graham. I’m a huge fan.
Related Material and References
- The Y Combinator or How to Succeed at Recursion Without Really Recursing by Mike Vanier - This is one of the best blog posts I’ve read in my life. This very blog post tries to follow the same didactic route as that one, but with a bit more detail and at a slower pace. If you’re interested in more detail about how to derive Y in non-strict programming languages I highly recommend you to read that. Excellent material, thanks, Mike.
- Lambda Calculus: The Y combinator in javascript by Yehonathan Sharvit - Another excellent blog post in JavaScript. More focused on the practical and short derivation of the Y-Combinator and its practical applications
- Essentials: Functional Programming’s Y Combinator by Computerphile - I don’t usually watch many Youtube videos about computer science, but this one is definitely worth your time. It is a very simple explanation which helps you a lot to understand the theoretical side of the Y-Combinator if you’ve never dealt with Lambda Calculus before. It’s a good starting point.
- Clear, intuitive derivation of the fixed-point combinator (Y Combinator)? on CS StackExchange - Also a very good and simple derivation of Y. Not practical, but definitely very elegant and concise. Highly recommended.
- thunks/thunks on Github & redux-thunk - More excellent resources to learn about thunks and how they can be useful
Special Thanks
- I’d also like to thank my friend Morgan Roderick for reviewing this blog post and for all the amazing work he’s been doing on Sinon.js. Thanks, buddy :)