Applicative Without Currying

A few weeks ago, I was asked a really good question by a beginning Haskell programmer. This post will work through the logic of the answer. The question is:

If Haskell didn’t curry its functions, would we still care about applicative functors?

I’ll assume you are familiar with currying — writing a function fun of two parameters as fun :: a -> (b -> c) with a partially applied function as its codomain. I’ll also assume you’ve seen applicative functors before, but let’s still start with a few definitions as a reminder.

class Functor where
    fmap :: (a -> b) -> f a -> f b
(<$>) = fmap
class Functor f => Applicative f where
    pure :: a -> f a
    (<*>) :: f (a -> b) -> f a -> f b

If it’s been a while since you’ve looked at Applicative, it might not be immediately clear what <*> is even useful for. Here’s a recap. Any Functor defines some structure of values — such as a list of many values, or a promise/future that represents a value that’s not yet known, or an FRP behavior whose value changes over time. Now, if you have a curried function fun :: a -> b -> c with two parameters, you may want to apply it to structures of arguments (of types f a and f b) to get a structure of results (f c).

Recall that fun is really a function from its first parameter a to a new function b -> c. If you apply fmap to it, you’ll get a map from f a to the type f (b -> c). What now? With just Functor, you’re stuck! To finish applying fun to its structured arguments, you need something exactly like <*>, where the (partially applied) function itself is in the structure. (In practice, this follows a nice pattern, and you can write fun <$> x <*> y. The <$> is just an infix fmap used to apply the first argument. After that, you have a structure of partially applied functions, and <*> applies the remaining arguments.)

That explanation was almost entirely about currying. Yet, while it’s very convenient, currying is ultimately just a convention. If Haskell didn’t curry its functions, would <*> be of interest to us at all? Would we really care all that much about how to apply lists of functions to lists of arguments? Would applicative functors go away as a concept?

It’s a good question, and indeed it seems obvious that the strange type of <*> itself would be less appealing if it weren’t for currying, and the way it enables the f <$> x <*> y pattern. But hold off on throwing away Applicative entirely. Given an uncurried function fun :: (a, b) -> c, good old fmapcan get you to fmap fun :: f (a, b) -> f c. But once again, this isn’t enough to apply fun to structured arguments of types f a and f b. This time, we need something a bit different. I’ll call it Tuplicative. (McBride and Patterson’s original paper on applicative functors calls it Monoidal, but that’s nowhere near as fun.)

class Functor f => Tuplicative f where
    fnil :: f ()
    fzip :: f a -> f b -> f (a, b)

Given this, I can apply the uncurried fun to structured arguments with little difficulty by writing fun <$> fzip x y. And here’s the punchline:

Applicative and Tuplicative are equivalent.

It turns out that Tuplicative is nothing new. It’s just Applicative again, in disguise. To see this, we can implement each type class in terms of the other. Here’s one direction:

instance Applicative f => Tuplicative f where
    fnil = pure ()
    fzip x y = (,) <$> x <*> y

The key step here just defines fzip by applying the old familiar Applicative pattern to (,) as a function of multiple parameters. And in the other way:

instance Tuplicative f => Applicative f where
    pure x = const x <$> fnil
    fun <*> x = uncurry ($) <$> fzip fun x

To recover <*>, one just fzips the partially applied functions with their arguments, and then maps an uncurried ($) over the pairs. It’s striking how these definitions express their core ideas in such straight-forward ways: in one direction, construct a pair out of multiple parameters, and in the other, just uncurry the function application.

There’s more to be done here, though. Applicative comes with laws, which need to be converted to the Tuplicative language. And one must still prove that these constructions and sets of laws are really inverses of each other. It’s after midnight, though, so I’ll save that for a future post.