Every now and again you hear developers at some programming event talking about this fabled myth of a function, the understanding of which will transcend you to a new plane of programming. Well, challenge accepted. Spoiler, I am still among us mortals.
Thinking About the Problem
The first place you go: wiki. If you are anything like me, lambda calculus hurts your head and only paints a fuzzy picture. Heavy math aside, what problem does it solve? It lets us have recursion of anonymous functions.
Factorial function to the rescue
function factorial(num) {
return num === 0 ? 1 : num * factorial(num -1);
}
To define recursion you must first define recursion.
But seriously, in order to be able to make this function anonymous, we need to get rid of our dependency on "factorial" I agree, crazy. But lets give it a try. Some closure? Maybe we can wrap it in a function? We no longer call the function by its name, does that help? Maybe if we can somehow call the wrapper function with the result of itself.
function(factorial) {
return function(num) {
return num === 0 ? 1 : num * factorial(num -1);
};
}
And queue the entrance of the Y Combinator!
function Y(bindFn) {
return function () {
return bindFn(Y(bindFn)).apply(null, arguments);
};
}
Untwisting the Pretzel
Right, that's what I thought, that a bit crazy. The factorial wrapper gets passed into it self, is that even possible? Seems so, here is a trace: (jsbin)
There is a beauty to this almost mechanical algorithm, reminiscent of the sewing machine or the RNA copy mechanism.
- Wrap the anonymous function.
- Send in the wrapped anonymous function into the Y combinator function.
- Unpack the anonymous function and execute it, by passing the Y combinator result of the wrapped function into the wrapped function.
