applicative functors (haskell)

1. Motivation

Recall that a functor is something that can be mapped over. For example, List is a functor, because we can map a function over the elements that the list contains. So, given a function with type Int -> Char, we can map List Int to List Char. What if our mapping function has type Int -> Int -> Char? Then, the resulting list will have type List (Int -> Char). What if we wanted to use these functions as a map between lists? We can't use a normal functor, because the type of fmap is (a -> b) -> f a -> f b. We need an applicative functor, which has a mapping with the type f (a -> b) -> f a -> f b. This allows us to use multi-argument functions!

2. Definition

The type class of applicative functors is given by:

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

3. Example: `Maybe`

The Maybe type can be made to implement the applicative functor type class:

instance Applicative Maybe where:
    pure = Just
    Nothing <*> _  = Nothing
    Just f <*> something = fmap f something

In the above Just is a data-constructor (see Types in Haskell) with type a -> Maybe a. In the last line, recall that fmap has type (a -> b) -> f a -> f b

Then, we can write:

pure (\x y -> x+y) <*> Just 3 <*> Just 4

4. Example: `List`

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

5. Example: `Functions`

instance Applicative ((->) a) where:
    pure a = \_ -> a
    f <*> g = \x -> f x (g x) -- remember that f :: a -> (b -> c) and g :: a -> b

5.1. comment:

I think of ((->) a) as ranging over all functions that take a value of type a as an argument. For instance, let's talk about the applicative functor ((->) Int). This is the set of all functions that take an Int as input.

6. <$> notation

Instead of writing

pure (+) <*> Just 3 <*> Just 4

We can instead write

(+) <$> Just 3 <*> Just 4

The definition of <$> is:

(<$>) :: (Functor f) => (a -> b) -> f a -> f b
(<$>) f x = fmap f x

7. liftA2

liftA2 lifts an ordinary function with input type a and b to a function that takes applicative functor arguments f a and f b:

liftA2 :: (Applicative f) => (a -> b -> c) -> f a -> f b -> f c
liftA2 f x y = f <$> x <*> y

8. sequence

sequenceA :: (Applicative f) => [f a] -> f [a]
sequenceA [] = pure []
sequenceA xs = foldr (liftA2 (:)) (pure []) $ xs

where (:) is the concat function which has type

(:) :: a -> [a] -> [a]

Recall, from the definition of liftA2 that:

liftA2 (:) :: f a -> f [a] -> f [a]

liftA2 (:) takes a functor that contains stuff of type a and a functor that contains a list of stuff of type a. It concats the contents of the first functor to the contents of the second.

An alternative definition:

sequenceA xs = (:) <$> x <*> sequenceA xs

8.1. example

For the list monad, sequenceA returns the cartesian product between the input lists:

sequenceA [[1,2],[3,4]]

8.1.1. comments

How do we make sense of this result? Here's how I break it down, from the second definition of sequenceA:

(:) <$> This gives us a list that consists of the concat function: [(:)]
(:) <$> x Remember that x is a list. So, this returns a list of partially applied concat functions. It looks something like [(:) xx | xx <- x]
Then, we take it on faith that sequence xs returns a list of the cartesian products among the remaining lists in xs. So calling <*> between the above list and sequence xs will result in appending xx to every list in sequence xs for every xx in x

8.2. example

For the function monad (->) a, sequence takes a list of functions from type a and returns a single function that takes a value of type a as input and returns a list containing the outputs of the functions.

8.3. comments

Here's how I understand it. Let's imagine that we are talking about the ((->) Int) functor:

(:) <$> gives us a function that takes an Int, discards it, and gives us the concat function
(:) <$> f gives us a function that takes an Int, x:
- feeds it to the above function to get the concat function,
- feeds it to f
- feeds the result of the above to the concat function
- tl;dr: this gives us a function that takes x and returns a concat with f x as the first argument (the concat still needs a list as a second argument)
(:) <$> f <*> sequence fs Now, let's take it on faith that sequence fs gives us a function that takes an input x and gives us a list consisting of the outputs of the fs on x. Then, combined with the above, we will have a function that take an x, feeds it to f and concats it with the result of feeding x to sequence fs. Take a look at the above definition of applicative behavior for functions.

9. Sources

Learn you a haskell: applicative functors