Mike's corner of the web.

Applicative functors in uncurried languages

Sunday 9 September 2012 20:47

Note: this post assumes you already have some familiarity with applicative functors

In this post, I'll show how to implement applicative functors in JavaScript, specifically for options, and then show an alternative formulation that's arguably better suited to languages that generally have uncurried functions (that is, languages that tend to have functions that accept multiple arguments rather than a single argument).

First of all, let's implement the option type (otherwise known as the maybe type) in JavaScript as a functor:

var none = {
    map: function(func) {
        return none;
    },
    
    bind: function(func) {
        return none;
    },
    
    toString: function() {
        return "none";
    }
};

function some(value) {
    return {
        map: function(func) {
            return some(func(value));
        },
        
        bind: function(func) {
            return func(value);
        },
        
        toString: function() {
            return "some(" + value + ")";
        }
    };
}

var functor = {
    map: function(func, option) {
        return option.map(func)
    },
    unit: some,
    applyFunctor: function(funcOption, argOption) {
        return funcOption.bind(function(func) {
            return argOption.map(func);
        });
    }
};

We can then use option values as applicative functors. Let's try our implementation out to make sure it behaves as we expect:

var four = some(4);
var six = some(6);

function add(first, second) {
    return first + second;
};

function curry(func, numberOfArguments) {
    return function(value) {
        if (numberOfArguments === 1) {
            return func(value);
        } else {
            return curry(func.bind(null, value), numberOfArguments - 1);
        }
    };
}

functor.applyFunctor(functor.map(curry(add, 2), four), six);
// => some(10)
functor.applyFunctor(functor.map(curry(add, 2), none), six);
// => none
functor.applyFunctor(functor.map(curry(add, 2), four), none);
// => none

Note that the use of the functor required us to curry the add function. This isn't a problem in functional languages such as Haskell, since functions tend to be curried by default. However, in languages that usually define functions to have multiple arguments (uncurried languages, for short), such as JavaScript, things get a little untidy.

My understanding of applicative functors is that they allow functors, or rather map, to be generalised to functions that accept more than one argument, such as add. Therefore, in an uncurried language, we might imagine the following cleaner API:

functor.applyFunctorUncurried(add, four, six);
// => some(10)
functor.applyFunctorUncurried(add, none, six);
// => none
functor.applyFunctorUncurried(add, four, none);
// => none

And such an API turns out to be not too hard to implement:

functor.applyFunctorUncurried = function(func) {
    var args = Array.prototype.slice.call(arguments, 1);
    return args.reduce(
        functor.applyFunctor,
        functor.unit(curry(func, args.length))
    );
}

Interestingly, the implementation of applyFunctorUncurried is most easily expressed in terms of the original applyFunctor. I've found cases like this explain why functional languages tend to favour curried functions: it often makes the implementation of higher-order functions such as applyFunctor much more straightforward.

This raises an interesting question: are these two formulations of applyFunctor of equal power? That is, is it possible to implement each in terms of the other? It's straightforward to see that we can implement applyFunctorUncurried in terms of applyFunctor since it's precisely the implementation above. What about implementing applyFunctor in terms of applyFunctorUncurried? This turns out to be pretty straightforward too:

function applyFunctor(funcFunctor, argFunctor) {
    return functor.applyFunctorUncurried(apply, funcFunctor, argFunctor);
}

function apply(func, value) {
    return func(value);
}

Please let me know if you spot mistakes in any of the above -- I've not exactly been rigorous in proof!

I'd be curious to know if there are any languages that include the alternative formulation of applyFunctor, and whether there are common cases where the original formulation is preferable even in uncurried languages.

Topics: Functional programming, Language design, JavaScript