Applicative Functors

This lec­ture is adjusted from Niki Vazou who adjusted from Ran­jit Jhala who adjusted from Gra­ham Hut­ton.

Thus far we have only dealt with map­ping of sin­gle argu­ment func­tions. How­ever, there is no rea­son we can’t map a mul­ti­ple argu­ment func­tion. For exam­ple, what do you think will be the type of x after the fol­low­ing is exe­cuted?

Pre­lude> x = fmap (+) [1,2]

Recall that Haskell has cur­ry­ing, mean­ing that we can par­tially apply the two argu­ment func­tion + with one argu­ment.

Pre­lude> :t ((+) 1)
((+) 1) :: Num a => a -> a

Using this knowl­edge, for x, we will get some­thing that looks like this

x = [(+ 1),(+ 2)]

Indeed, if we check the type of x, ghci tells us the type of x is a list of func­tions from a to a where a is an instance of the Num type­class:

Pre­lude> :t x
x :: Num a => [a -> a]

Let’s now con­sider a slightly dif­fer­ent exam­ple. Let’s say we have two lists

Pre­lude> x = [1..5]
Pre­lude> y = [101..105]

As dis­cussed pre­vi­ously, let’s think of lists as rep­re­sent­ing non­de­ter­min­ism. That is to say, x rep­re­sents a sin­gle value that could be any num­ber 1 to 5, y 101 to 105. Let’s sup­pose we want to add these two non­de­ter­min­is­tic val­ues. We could try to use fmap again.

Pre­lude> fmap (fmap (+) x) y

<inter­ac­tive>:31:7: error:
    • Couldn't match expected type ‘Inte­ger -> b’
                  with actual type ‘[Inte­ger -> Inte­ger]’
    • Pos­si­ble cause: ‘fmap’ is applied to too many argu­ments
      In the first argu­ment of ‘fmap’, namely ‘(fmap (+) x)’
      In the expres­sion: fmap (fmap (+) x) y
      In an equa­tion for ‘it’: it = fmap (fmap (+) x) y
    • Rel­e­vant bind­ings include it :: [b] (bound at <inter­ac­tive>:31:1)

Why didn’t this work? Well, let’s take a look at the types.

Pre­lude> :t fmap
fmap :: Func­tor f => (a -> b) -> (f a -> f b)
Pre­lude> :t (fmap (+) x)
(fmap (+) x) :: (Enum a, Num a) => [a -> a]

Hmmm. fmap expected a func­tion from a to b but we gave it a func­tion from list a to b. Hmmm, how can we get around this? Let’s take a step back and look at what fmap does, per it’s type sig­na­ture. We can think of fmap as both 1) tak­ing a func­tion from as to bs and an f a and return­ing an f b and 2) tak­ing a func­tion from as to bs and return­ing a func­tion from f as to f bs. In this sense, we can think of fmap as lift­ing a func­tion from as to bs to the con­text (func­tor) f as to f bs.

Ok, well, can we write a func­tion that would lift a func­tion from as to bs to cs (like +) to a par­tic­u­lar func­tor con­text (like lists)? Let’s try to write such a func­tion.

lift2 :: (a -> b -> c) -> [a] -> [b] -> [c]
lift2 f xs ys = [ f x y | x <- xs, y <- ys]

Let’s see if it works.

Pre­lude> lift2 (+) x y
[102,103,104,105,106,103,104,105,106,107,104,
105,106,107,108,105,106,107,108,109,106,107,
108,109,110]

Good, this per­forms our non­de­ter­min­is­tic addi­tion! But what about lift­ing a func­tion that takes three argu­ments? Four? N? This seems like a place where cur­ry­ing might be nice.

Let’s define a type­class to han­dle this.

class Func­tor f => Applica­tive f where
  pure  :: a -> f a
  (<*>) :: f (a -> b) -> f a -> f b

The Applica­tive type­class has two func­tions pure and <*>. pure takes a type a and turns it into an Applica­tive (and a Func­tor). We can think of pure as turn­ing a into a default instance of the Applica­tive type­class.

For <*>, given an applica­tive func­tion from a to b and an applica­tive a, we get back an applica­tive b.

Note first that for a type f to be an instance of the Applica­tive type­class, it must also be an instance of the Func­tor type­class, mean­ing it has a defined fmap func­tion.

Why is this? It turns our every applica­tive is also a func­tor! How can we prove this? Well, if we can derive fmap from our two func­tions, pure and <*>, we’re good. Let’s do that.

fmap' :: Applica­tive a => (b -> c) -> a b -> a c
fmap' f x = pure f <*> x

Let’s look at the List instance of Applica­tive.

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

Notice pure returns the sin­gle­ton list as opposed to the empty list. While both would sat­isfy the type require­ments of pure, the empty list would ignore the argu­ment x to pure which would be unusual (Note: while unusual, Haskell would allow this def­i­n­i­tion of pure).

Ok, this is nice, but how do we get lift2 from this?

lift2' :: Applica­tive a => (b -> c -> d) -> (a b -> a c -> a d)
lift2' f x y = (pure f) <*> x <*> y

And it works!

Pre­lude> (lift2' (+) x y) == (lift2 (+) x y)
True

Ah-ha! What about lift3?

lift3' :: Applica­tive a => (b -> c -> d -> e) -> (a b -> a c -> a d -> a e)
lift3' f x y z = (pure f) <*> x <*> y <*> z

Nifty!

Let’s look at the Maybe instance of the Applica­tive type­class.

instance Applica­tive Maybe where
    pure = Just
    Noth­ing <*> _   = Noth­ing
    (Just g) <*> mx = fmap g mx

Let’s take a look at some exam­ples to get a feel for how this works.

Pre­lude> pure (+1) <*> Just 1
Just 2
Pre­lude> pure (+) <*> Just 1 <*> Just 2
Just 3
Pre­lude> pure (+) <*> Noth­ing <*> Just 2
Noth­ing

Recall that we often use Noth­ing to rep­re­sent fail­ure/excep­tion. That means the use of applica­tives here can rep­re­sent the prop­a­ga­tion of excep­tions -- error han­dling!

Let’s look at an exam­ple. Let’s first define a func­tion div’ that divides two inte­gers, return­ing the result, unless the denom­i­na­tor is zero, in which case it throws an error.

divv x y = if y == 0 then error "Denom­i­na­tor is 0!" else x / y

Here are some exam­ples.

Pre­lude> divv 1 2
0.5
Pre­lude> divv 1 0
*** Excep­tion: Denom­i­na­tor is 0!
Call­Stack (from Has­Call­Stack):
  error, called at <inter­ac­tive>:30:31 in inter­ac­tive:Ghci13

Hmmm, maybe we can use applica­tives to define a safer divi­sion oper­a­tor.

safe­Divv x y = if y == 0 then Noth­ing else Just (x / y)

Now instead of crash­ing on divide by zero, we get Noth­ing.

Pre­lude> safe­Divv 1 2
Just 0.5
Pre­lude> safe­Divv 1 0
Noth­ing

Let’s try to do some arith­metic with our new safe divi­sion func­tion.

Pre­lude> (safe­Divv 1 2) + (safe­Divv 4 0)

<inter­ac­tive>:73:1: error:
    • Non type-vari­able argu­ment in the con­straint: Num (Maybe a)
      (Use Flex­i­ble­Con­texts to per­mit this)
    • When check­ing the inferred type
        it :: forall a. (Num (Maybe a), Eq a, Frac­tional a) => Maybe a

Well that’s no good. Can we some­how make plus work for our new safe divi­sion with­out defin­ing a whole new safe­Plus func­tion? Sure, with applica­tives!

Pre­lude> pure (+) <*> (safe­Divv 1 2) <*> (safe­Divv 4 0)
Noth­ing

Woah, cool! With applica­tives we get safe­Plus for free! And safe­Times too!

Sim­i­lar to func­tors, applica­tives must also fol­low some laws, in this case four.

• Iden­tity:

  pure id <*> v = v
  

• Com­po­si­tion:

  pure (.) <*> u <*> v <*> w = u <*> (v <*> w)
  

• Iden­tity:

  pure f <*> pure x = pure (f x)
  

• Iden­tity:

  u <*> pure y = pure ($ y) <*> u
  

I would not spend too long try­ing to digest these; they can be a bit chal­leng­ing.