Not a Haskell Monad Tutorial: Applicatives

Functors are all very well, but they only allow you to map with a function that takes only one parameter. But there’s plenty of functions that take more than one parameter, including useful ones like add and multiply. So how do we want to multiply to work on nullable integers?

  • 2 times 3 should be 6
  • 2 times null should be null
  • null times 3 should be null
  • null times null should be null

There’s something else we need to do. What if 2 is just an integer, not a nullable integer? Really, we need to be able to promote an integer to a nullable integer. The more parameters a function has, the more likely one of them isn’t in exactly the right format. Haskell calls this function pure. (+)

Now let’s get a bit more complicated. What about multiplying two lists together? Multiplying [2] and [3] should obviously give [6]. But what happens if you’re multiplying [2,3] and [5,7]? Turns out there’s at least three sensible answers:

  • Multiply the pairs in sequence: [10,21]
  • Multiply the pairs like a cross join: [10,14,15,21]
  • Actually, you could also iterate the first sequence first [10,15,14,21

More than one way to skin a list

Let’s just concentrate on the first two. How are they going to deal with lists of different length?

  • [2] * [1,3] should be [2] OR
  • [2] * [1,3] should be [2,6]

But what if the first parameter isn’t a list. What should that look like? Well, 2 * [1,3] should definitely be [2,6]. But that means that, depending on how we generalise multiplication, we also need to generalise turning a number into a list.

  • To multiply like a cross join, 2 can just become [2]
  • To multiply the pairs in sequence 2 needs to be [2,2,2,2,2,...], an infinite sequence of 2s.

So, generalizing multiple-arity functions to functor contexts isn’t as obvious as it is for single-arity functions. What on earth do we do about this? Well, the approach Haskell goes with is “pick an answer and stick with it”. In particular, for most purposes, it picks the cross join. But if you want the other behaviour, you just wrap the list in a type called ZipList and then ZipLists do the pairwise behaviour.

Back to the Functor

So, how should we handle the various examples of functors that we covered in the first part? We’ve already dealt with nullables and lists and sets are a dead loss because of language limitations.

Multiplying two 1d6 distributions just gives you the distribution given by rolling two dice and multiplying the result. Promoting a value e.g. 3 to a random number is just a distribution that has a 100% chance of being 3.

You can multiply two functions returning integer values by creating a function that plugs its input into both functions and then returns the product of the results. You can promote the value 3 to a function that ignores its input and returns 3.

How about records in general? Well, here’s the thing: you can’t promote a record without having a default value for every field. And that isn’t possible in general. So, while you can undoubtedly make some specific datastructures into applicatives, you can’t even turn the abstract pair (a,b) (where you’re mapping over a) into an applicative without knowing something about b.

We could make the mapping work for pair if we were actually supplied with a value. But that doesn’t make sense, does it? How about, instead of (a,b) we work on functions b -> (a,b). Now we can map a, on single and multiple-arity functions, and just leave the b input and output values well alone. It turns out this concept is rather useful: it’s usually called the State Monad.

Would you like Curry with your Applicative?

Up until now, I’ve mostly talked about pairwise functions on integers. It’s pretty obvious how you’d generalize the argument to arbitrary tuples of arbitrary input times. However, it turns out that the formulation I’ve used isn’t really that useful for actual coding, partly because constructing the tuples is a real mess. So let’s look at it a different way.

Let’s go back to multiplying integers. You can use the normal fmap mapping on the first parameter to get partially applied functions. So our [2,3] * [5,7] example gives up [2*,3*] and [5,7]. Now we just need a way of “applying” the functions in the list. We’ll call that <*>. It needs to do the same thing as before and the promotion function, pure is unchanged.

It turns out that once you’ve got that, further applications just need you to do <*> again, so if you’ve got a function f and you’d normally write f a b c to call it, you can instead write

f <$> a <*> pure b <*> c

Assuming a and c are already in the correct type and b isn’t. This is equivalent to

pure f <*> a <*> pure b <*> c

but in practice people tend to write the dollar-star-star form. Finally, you can also write

(liftA3 f) a (pure b) c

which is much more useful when you’re going pointfree.

And finally…

So, here’s the quick version:

  • a functor that can “lift” functions with multiple parameters is termed an “applicative functor”, “idiom” or just “applicative”
  • a functor is uniquely defined by the data type you’re mapping to(*)
  • some data structures like list, however, give rise to multiple possible implementations of Applicative

Functors have been well understood for a long time, and monads provided the big conceptual breakthrough that made Haskell a “useful” language. The appreciative of applicative functors as an abstraction that occupies a power level between the two is a more recent development. When going around the Haskell libraries you’ll often discover two versions of a function, one of which is designed for applicatives and one for monads but they’re the same function. It’s just that the monad version was implemented first. With time, the monad versions will be phased out, but it’s going to take a long tuime. You can read more about the progress of this on the Haskell wiki.

If you want a much more rigorous approach to what I’ve been talking about here, read Brent Yorgey’s excellent lecture notes.

(+) and return, for historical reasons.

(*) Indeed, and this is awesome, Haskell will just automatically generate
the Functor fmap function for you.

Published by

Julian Birch

Full time dad, does a bit of coding on the side.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s