ycombinator.js

// Making an anonymous recursive function
// --------------------------------------


// 1. Create a basic *named* factorial function, which recursively calls itself

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


// 2. Turn this into a factorial *factory*, which returns the factorial function

function factorialFactory() {
    return function factorial(n) {
        if (n === 0) {
            return 1;
        } else {
            return n * factorial(n - 1);
        }
    }
}

var factorial = factorialFactory();


// 3. Now let's make factorialFactory take *itself* as an argument. This won't have any effect yet, but...

function factorialFactory(_factorialFactory) {
    return function factorial(n) {
        if (n === 0) {
            return 1;
        } else {
            return n * factorial(n - 1);
        }
    }
}

var factorial = factorialFactory(factorialFactory);


// 4. Now we have factorialFactory available inside our factorial method! So we can use it make factorial anonymous

function factorialFactory(_factorialFactory) {
    return function(n) {
        if (n === 0) {
            return 1;
        } else {
            var factorial = _factorialFactory(_factorialFactory);
            return n * factorial(n - 1);
        }
    }
}

var factorial = factorialFactory(factorialFactory);


// Note: at this point we're done making an anonymous recursive function.
// But what if we want to make it easier to create these kinds of functions?
// The above pattern isn't exactly straightforward to write out every time. So...


// 5. Generalize out factorialFactory(factorialFactory) into applySelf(factory) 

function applySelf(factory) {
    return factory(factory);
}

var factorial = applySelf(function factorialFactory(_factorialFactory) {
    return function(n) {
        if (n === 0) {
            return 1;
        } else {
            var factorial = applySelf(_factorialFactory);
            return n * factorial(n - 1);
        }
    }
});


// 6. Let's clean up factorialFactory, and let it take 'factorial' as an argument.
//
//    To do this we need something instead of applySelf(), so let's create applyResult().
// 
//    This calls the factory, but instead of calling it with itself, it passes in a new function, which will be lazily
//    called later when we actually invoke the factorial function.
//    
//    When this new function is called, later, it needs to act as a factorial method - which means it needs to get a
//    reference to factorial method. To do this it calls applyResult(factory), which returns the factorial method.
//
//    This is probably the most tricky step to get your head around.

function applyResult(factory) {
    return factory(function(arg) {
        return applyResult(factory)(arg);
    });
}

var factorial = applyResult(function factorialFactory(factorial) {
    return function(n) {
        if (n === 0) {
            return 1;
        } else {
            return n * factorial(n - 1);
        }
    }
});


// 7. Damn, applyResult works great, but it's not anonymous
//    Let's just do the exact same thing we did for factorial, to make that anomymous (using factorialFactory)
//    We'll create an applyResultFactory, which we can call with itself.

function applyResultFactory(_applyResultFactory) {
    return function(factory) {
        return factory(function(arg) {
            return _applyResultFactory(_applyResultFactory)(factory)(arg);
        });
    }
};

var applyResult = applyResultFactory(applyResultFactory);

var factorial = applyResult(function makeFactorial(factorial) {
    return function(n) {
        if (n === 0) {
            return 1;
        } else {
            return n * factorial(n - 1);
        }
    }
});


// 8. Once again (as with factorialFactory) we can generalize out an applySelf() method:

function applySelf(factory) {
    return factory(factory);
}

var applyResult = applySelf(function applyResultFactory(_applyResultFactory) {
    return function(factory) {
        return factory(function(arg) {
            return applySelf(_applyResultFactory)(factory)(arg);
        });
    }
});

var factorial = applyResult(function makeFactorial(factorial) {
    return function(n) {
        if (n === 0) {
            return 1;
        } else {
            return n * factorial(n - 1);
        }
    }
});


// 9. Now let's inline applySelf in the two places it's used, so we can create a single self-contained applyResult() method

var applyResult = (function applySelf(factory) {
    return factory(factory);
})(function applyResultFactory(_applyResultFactory) {
    return function(factory) {
        return factory(function(arg) {
            return _applyResultFactory(_applyResultFactory)(factory)(arg);
        });
    }
});

var factorial = applyResult(function makeFactorial(factorial) {
    return function(n) {
        if (n === 0) {
            return 1;
        } else {
            return n * factorial(n - 1);
        }
    }
});


// 9. Turns out applyResult is actually a Y Combinator function! Let's remove all of the named functions, and clean up the variable names:

var Y = (function(f) {
    return f(f);
})(function(f) {
    return function(g) {
        return g(function(arg) {
            return f(f)(g)(arg);
        });
    }
});

var fac = Y(function(factorial) {
    return function(n) {
        if (n === 0) {
            return 1;
        } else {
            return n * factorial(n - 1);
        }
    }
});