### 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