Higher-order functions in Javascript

In Javascript, functions are just like the other variables(AKA first-class citizen), and here are several interesting tricks implemented by treating functions as first-class citizen.

currying

Currying is for partial evaluation, a practical example is Function.prototype.bind() in Javascript:

var add = function(a, b) {
    return a + b;
};

var add_two = add.bind(null, 2);
add_two(4); // 6

And we can implement bind()(under this circumstance only of course) by ourselves:

var bind = function(f, n) {
    return function() {
        return f.apply(null, [n].concat([...arguments]));
    };
};

var add = function(a, b) {
    return a + b;
};

var add_two = bind(add, 2);

add_two(4); // 6

trampolining

Javascript(ES5) does not implement tail call optimization, so using recursion incorrectly(such as calculating Factorial) will lead to a stack-overflow exception. However, this can be avoided by returning a higher-order function, which is called trampolining.

First, we can easily get written factorial() done:

function factorial(n){
    return n == 1 ? n : n * factorial(n-1);
}

But this is not a tail-call recursion, let’s update this method by adding another parameter:

function tail_factorial(n, result) {
    return n == 1 ? result : tail_factorial(n - 1, n * result);
}

Now, we get a tail-call recursion function which ES5 can not optimize, and we are still facing the stack-overflow problem. So let’s look at our trampoline function:

function trampoline(fn){ 
    return function(){
        var result = fn.apply(this, arguments);
        while(result instanceof Function){
            result = result();
        }
        return result;
    }
}

function tail_factorial(n, result) {
    return n == 1 ? result : function() {
        return tail_factorial(n - 1, n * result)
    };
}

trampoline(tail_factorial)(7, 1)  // 5040

However, using trampoline here is just showing concepts of higher-order function and not recommended, for in programming languages like PHP and Javascript it may cause a great performance loss.

Leave a Reply

Your email address will not be published. Required fields are marked *

*