CMSC-16100

Honors Introduction to Programming, I

Autumn Quarter, 2015

Home Policies Lectures Notes Labs

---

Piazza

Lecture 12: Applicative and Alternative

Applicatives

Functors are very nice. They give us a uniform mechanism for "lifting" functions defined at a simple type to act on complicated types that are parameterized by that type, For example, if F is a Functor, and f :: A -> B, then fmap f :: F A -> F B.

But what happens if f isn't unary? Consider a hypothetical f :: A -> B -> C. Intuitively, we might hope fmap f :: F A -> F B -> F C, but it doesn't work that way. We've already defined fmap so that fmap f :: F A -> F (B -> C), i.e., the result of the first application is to produce a function in an F box, rather than a function that takes boxed values, and returns a boxed value. We could work with this if F had a mechanism for applying boxed functions to boxed arguments, returning boxed results.

The Applicative typeclass, defined in Control.Applicative, addresses this issue.

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

A type f is Applicative if it is a Functor that, additionally, comes with two members: an infix operator (<*>) that takes a boxed function of type f (a -> b), applies it to a boxed argument of type f a, and produces a boxed result of type f b; and a function pure of type a -> f a that "lifts" simple values into boxed ones. Once we have this, we can "factor" fmap:

fmap f appA = pure f <*> appA

Or, for those who like to play with eta-reduction:

fmap = (<*>) . pure

In addition to the Functor laws involving fmap, every Applicative functor must satisfy the following laws:

• pure id <*> v = v
• pure (.) <*> u <*> v <*> w = u <*> (v <*> w)
• pure f <*> pure x = pure (f x)
• u <*> pure y = pure ($ y) <*> u

We're not going to dwell on these laws now, but in time, they'll seem obvious.

Maybe

Let's get a little bit of practice with Maybe before considering more complicated examples. We can easily write an instance definition:

instance Applicative Maybe where pure = Just (Just f) <*> (Just x) = Just (f x) _ <*> _ = Nothing

Note here that the instance definition in the Control.Applicative is quite different, and we'll come to that in due course.

Intuitively, we can understand arithmetic expressions in Maybe Int as expressions where operands or operations might be missing. Thus, e.g.,

> :m Control.Applicative > pure (+) <*> Just 1 <*> Just 1 Just 2 > pure (+) <*> Just 1 <*> Just 1 Just 2 > Nothing <*> Just 1 <*> Just 1 Nothing > pure (+) <*> Just 1 <*> Nothing Nothing

Pretty clearly, any expression in which any operand or operation is missing is going to evaluate to Nothing. Note here that I'm just using Just to clue the type checker in as to what Applicative I have in mind. Alternatively:

> pure (*) <*> pure 2 <*> pure 2 :: Maybe Integer Just 4

At this point, we can consider a few bits of simplifying syntax. The most common use case of applicatives involves applying an ordinary "unboxed" function to several boxed arguments. We can inject the function into the Applicative using pure, and then use <*> for "application under the box." This situation is quite common, so the function <$> is defined to apply an unboxed function to a boxed argument. Thus,

> (*) <$> Just 2 <*> Just 3 Just 6

A moment's reflection shows that <$> is just an infix-version of fmap. Expressions like the one above are said to be written in "applicative style" because they look like normal, curried function applications except for the presence of <$> and <*> sprinkled in between.

In addition to the special syntax for applying unboxed functions to boxed arguments, there are also functions liftA, liftA2, and liftA3, that generalize fmap to one or more arguments, i.e.,

liftA :: Applicative f => (a -> b) -> f a -> f b liftA2 :: Applicative f => (a -> b -> c) -> f a -> f b -> f c liftA3 :: Applicative f => (a -> b -> c -> d) -> f a -> f b -> f c -> f d

which is pretty much where the discussion of Applicative began. Thus,

> liftA2 (*) (Just 3) (Just 5) Just 15

Applicative List

It is sometimes useful to think of a function f :: A -> [B] as a non-deterministic function of type f :: A -> B, i.e., a function that can have zero or more return values. In this case, it may help to think of the list Functor as a "computational context" rather than a "box" of values. From such a perspective the effect of "applying" a list of functions to a list of arguments ought to be the list of all ways we can pair functions with arguments, and a pure object is just a singleton list, i.e.,

instance Applicative [] where pure x = [x] fs <*> xs = concat $ map (\f -> map f xs) fs

Thus,

> [] <*> [2,3] <*> [4,5] [] > [(+)] <*> [2,3] <*> [4,5] [6,7,7,8] > [(+),(*)] <*> [2,3] <*> [4,5] [6,7,7,8,8,10,12,15]

Note that the resulting list for the last expression above is [2+4,2+5,3+4,3+5,2*4,2*5,3*4,3*5], in precisely this order.

This particular instance of Applicative becomes very natural with use, in part because this generalizes to the usual Monad instance, of which we will see more later.

Aside: List Comprehensions

Our definition of (<*>) can be written more concisely using Haskell's list comprehension syntax:

fs <*> xs = [f x | f <- fs, x <- xs]

List comprehensions allow writing "generators" that resemble set comprehensions found in mathematical notation. As we'll soon see, list comprehensions are directly tied with yet another nifty type class. In the meantime, if you'd like to learn the basics of list comprehensions, check out these notes.

Applicative ZipList

It turns out that there's a second, natural way to implement a list as an Applicative. The idea is to represent parallel computation, i.e., that the i-th element of the result list comes from applying the i-th operation to the i-th operand. As we are well aware by now, however, a type can be an instance of a typeclass in only one way, and therefore we need a bit of a type-theoretic work-around. We've already seen how to do this several times:

newtype ZipList a = ZipList { getZipList :: [a] }

Thus, a ZipList a is just a [a] inside a (virtual) ZipList box.

Of course, we do this to provide a distinctive Applicative instance, but we have to provide a Functor instance as well. We'll use what is essentially the standard definition of fmap for lists, acting within the box:

instance Functor Ziplist where fmap f (Ziplist xs) = ZipList (fmap f xs)

Note here that the fmap on the right hand side of the definition is []'s fmap, i.e., our old friend map. We now define the following:

instance Applicative ZipList where (ZipList fs) <*> (ZipList xs) = ZipList (zipWith id fs xs)

This requires a bit of explanation, because it's probably not what you'd expect. Certainly, I'd expect something like a binary function that performs application (e.g., \f x -> f x). But...

\f x -> f x = \f -> \x -> f x = \f -> (\x -> f x) = \f -> f = id

Or, to put this same pun differently,

id f x = (id f) x = f x

So we didn't need to "roll up" a special purpose binary application function. We already had one, in the identity function. Weird.

The alert reader/listener will have noticed that I haven't yet provided a definition of pure for Applicative ZipList. This takes a bit of thought... Let's think about what we want:

> id <$> ZipList [1] ZipList {getZipList = [1]} > id <$> ZipList [1,2] ZipList {getZipList = [1,2]} > id <$> ZipList [1,2,3] ZipList {getZipList = [1,2,3]}

Hmm. So pure id has to be a function that contains id in every coordinate of a list of indeterminate length. It's a good thing that Haskell allows this:

instance Applicative ZipList where pure x = ZipList (repeat x)

remembering that repeat: a -> [a] builds an infinite list. Of course, this has implications for pure 3 as well:

> (+) <$> pure 3 <*> ZipList [1..4] ZipList {getZipList = [4,5,6,7]}

Alternative

The Monoid typeclass is useful but describes only ground types. What about type operators that also exhibit monoidal structure? For example, recall that we defined a wrapper type for Maybe called First that constituted a Monoid with an mappend operator that returns the first (leftmost) non-Nothing value.

> getFirst $ First (Just 1) <> First (Just 2) Just 1 > getFirst $ First (Just 1) <> First Nothing Just 1 > getFirst $ First Nothing <> First (Just 2) Just 2

We might like to describe this monoidal structure directly for Maybe even though it is not a ground type. The Alternative class describes Applicative functors f that also exhibit monoidal structure.

class Applicative f => Alternative f where empty :: f a (<|>) :: f a -> f a -> f a

Notice the correspondence between empty and (<|>) in Applicative to mempty and (<>) in Monoid, respectively. Unsurprisingly, an Alternative type f ought to satisfy all of the same laws as Monoids... in addition to the ones for Applicative... in addition to the ones for Functor!

The Maybe instance for Applicative is quite like the First a instance of Monoid:

instance Alternative Maybe where empty = Nothing Nothing <|> r = r l <|> _ = l

And now we can write the previous examples directly in terms of the Maybe monoid (Alternative):

> Just 1 <|> Just 2 Just 1 > Just 1 <|> Nothing Just 1 > Nothing <|> Just 2 Just 2

There are many other applicative functors with monoidal structure. For example, Alternative types are quite handy when writing parsers, as we shall see later in the course.

---

© 2009–2015 Ravi Chugh, Stuart A. Kurtz
Last modified: December 30, 2015