Road to monads: Applicative functors

Introduction

Applicative functors are halfway between functors and monads; all monads are applicative functors, but not all applicative functors are monads. Also, all applicative functors are functors, but not all functors are applicative functors.

Unfortunately, in Haskell this is not accurately represented, because monads and functors preceded the implementation of applicative functors, meaning that there is not a typeclass constraint of applicative functor on monads even though there should be. They are trying to address this with the [FAMP (Functor-Applicative-Monad proposal)][1], which will ship with GHC 7.10.

Make sure you [understand functors][2] before trying to understand applicatives.

What is an applicative functor?

An applicative functor is a functor which allows function application inside it.

This is done by providing a mechanism for values (and in Haskell functions are treated identically to values) to be lifted into the context of the applicative functor. There is also a higher-level fmap to apply functorized functions to functors.

Definition

Applicative functors have the following typeclass:

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

Applicative functors are not in the standard prelude (yet), so must be imported from Control.Applicative; this module also introduces <$> which is a synonym for fmap but in infix form. A lot of code using applicatives uses <$> instead of fmap for readability, so for consistency so will I.

Notice the typeclass constraint on an applicative functor: it must first be a functor, which demonstrates what I said before.

Applicatives implement pure and <*> (pronounced “ap” as in apply); pure takes a value and puts it into the context of the applicative functor:

λ: pure 1
1
λ: pure 1 :: Maybe Int
Just 1
λ: pure 1 :: [Int]
[1]

<*> is like a special <$> which works on functions inside functors:

-- List applicative functor
λ: [(+1), (+2)] <*> [4, 5]
[5,6,6,7]

-- Maybe applicative functor
λ: Just (*2) <*> Just 4
Just 8

Applicative functor laws

Applicatives follow the functor laws, and build upon them:

-- Lifting a function into an applicative context and then applying it is the
-- same as fmap'ing that function
pure f <*> = fmap f
-- Hence, identity
pure id <*> x = x

-- Lifting into applicative context can be deferred - Homomorphism
pure f <*> pure x = pure (f x)

-- Order of evaluation is interchangable
-- LHS means apply x to y in the applicative context
-- RHS means evaluate y in the applicative context before applying x to it
x <*> pure y = pure ($ y) <*> x

-- Composition
x <*> (y <*> z) = pure (.) <*> x <*> y <*> z
-- By example
let x = Just (+1)
    y = Just (*2)
    z = Just 3
-- LHS
Just (+1) <*> (Just (*2) <*> Just 3) =
Just (+1) <*> (Just 6) =
Just 7
-- RHS
pure (.) <*> Just (+1) <*> Just (*2) <*> Just 3 =
Just ((+1) . (*2)) <*> Just 3 =
Just 7

Standard applicatives

Maybe

Maybe is also an instance of Applicative, allowing optional functions to be applied to optional values.

The applicative instance for Maybe looks like this:

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

Here we pattern match to get a function and a value, applying that function to that value, otherwise we get a Nothing because Maybe values are either Just there or Nothing is there.

λ: Just (+1) <*> Just 2
Just 3
λ: Nothing <*> Just 2
Nothing
λ: Just (+1) <*> Nothing
Nothing

List

There are actually multiple logical ways about turning lists into applicative functors: one way is to compute every value non-deterministically, and another which is to apply the function at the nth index in the first list to the value at the nth index in the second list.

The first is the default instance of list applicative:

instance Applicative [] where
  pure x = [x]
  fs <*> xs = [f x | f <- fs, x <- xs]

-- Take the head of the first list, map it over the second list, recurse and
-- concatenate the results
λ: [(+1), (*2), (+4)] <*> [1, 3, 8, 7]
[2,4,9,8,2,6,16,14,5,7,12,11]

The second instance is called a ZipList, and is really a type synonym for an ordinary list using the newtype keyword:

newtype ZipList a = ZipList [a]

Try to work out the functor instance of ZipList:

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

With this wrapper, the applicative instance looks like this:

instance Applicative ZipList where
  -- To satisfy the identity law, we turn the second list into an infinite list
  -- so we aren't left with functions without values to map to
  pure x = ZipList (repeat x)
  -- zipWith ($) is zipping the two lists with the function application operator
  (ZipList fs) <*> (ZipList xs) = ZipList (zipWith ($) fs xs)

Here is an example showing how it works:

λ: ZipList [(*2), (+1), (*2), (*5)] <*> ZipList [1..10]
ZipList {getZipList = [2,3,6,20]}
λ: ZipList [(*2), (+1), (*2), (*5)] <*> pure 1
ZipList {getZipList = [2,2,2,5]}

->

Here is the instance for function composition as an applicative:

instance Applicative ((->) r) where
  pure = const
  f <*> g x = f x (g x)

Here pure is the same as const, which takes two functions and throws the second one away (also known as the K combinator):

const f _ = f

The effect of this is that it creates a function that returns the value inside it, ignoring its parameter:

λ: :t pure 3
pure 3 :: (Applicative f, Num a) => f a
λ: :t pure 3 "abc"
pure 3 "abc" :: Num a => a

<*> here demonstrates the S combinator, applying both functions to the input and applying the output of the first function to the output of the second, which is made clearer by isAlphaNum from Data.Char.

isAlphaNum :: Char -> Bool
isAlphaNum = (||) <$> isAlpha <*> isDigit

isAlphaNum 'a' =
((||) <$> isAlpha <*> isDigit) 'a' =
(((||) . isAlpha) <*> isDigit) 'a' =
((||) . isAlpha) 'a' $ isDigit 'a' =
((||) . isAlpha) 'a' $ False =
((||) True) $ False =
(True ||) $ False =
True || False =
True