Recreating the Haskell List Part 4: Applicative Functors

This is part 4 of a 6 part tutorial

Applicative Functors

A Haskell list is also an Applicative Functor. If we want to make MyList one too, we can look at the interface for the Applicative class, and implement the right functions.

Interface for the Applicative Typeclass

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

So, it looks as though we need to implement the functions pure and <*> in order to be an instance of Applicative. This also says that whatever is Applictaive has the prerequisite of also being a Functor. The function pure must take any type a and wrap it in the container MyList. This is also called lifting a into the Functor. Implementing pure is easy enough, because it is the same thing as our data constructor, Cons.

The function <*> has the type signature (<*>) :: f (a -> b) -> f a -> f b and represents function application for types that are wrapped in our data structure f, where the function is also wrapped in the same data structure f.

Functions that represent applying functions is sort of weird concept, but I can think of three functions offhand that do accomplish this in different ways. The three are: $, <$>, and <*>, so let’s look at their type signatures.

Function Application

:t ($)
=> ($) :: (a -> b) -> a -> b
:t (<$>)
=> (<$>) :: (Functor f) => (a -> b) -> f a -> f b
:t (<*>)
=> (<*>) :: (Applicative f) => f (a -> b) -> f a -> f b

The $ function takes a function (a -> b) and applies to an a, not surprisingly giving you a b. This is regular function application like odd 3 returning True. Here I show different ways to use $, implicitly, explicitly, and infix.

Functon application using $

odd 3
=> True
($) odd 3
=> True
odd $ 3
=> True
--  Precedence issue here
--  Haskell parses this as (Container 2) + 1
Container 2 + 1
=> <interactive>:1:0:
    No instance for (Num (Container t))
        arising from a use of `+' at <interactive>:1:0-14
    Possible fix: add an instance declaration for (Num (Container t))
        In the expression: Container 2 + 1
        In the definition of `it': it = Container 2 + 1
--  Ways to fix this
Container (2 + 1)
=> Container 3
Container $ 2 + 1
=> Container 3

People generally use $ when they want to change the precedence of an expression without using a lot of parenthesis.

Look at the type signature of <$>, and the one for fmap.

Type signatures of <$> and fmap

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

The function <$> is fmap. It is applying a function to the Functor f a producing f b. The angle brackets around the $ are indicating that this is application inside a container. This is called lifting the normal function (a -> b) into the Functor. What if the function itself is wrapped inside a Functor container?

The answer is that function <*> is used instead. Why wrap a function in a container to apply it to some value in the same type of container? Why not just not have anything in containers at all? Remember that a list is a container and check this out:

The <*> function

-- Type signature
:t (<*>)
=> (<*>) :: (Applicative f) => f (a -> b) -> f a -> f b
--  Applying a list of functions to a list of numbers
[(+2), (*2)] <*> [1,2,3]
=> [3,4,5,2,4,6]

Since lists are applicative functors, you may combine a list of functions to a list of values and have it do the obvious thing, apply everything to everything, and then either mconcat or mappend the results into a single flat list. This just happens to be how <*> is implemented for a Haskell list, because it is really the only way that makes sense to implement it.

Making MyList an Instance of Applicative

instance Applicative MyList where
    pure a = Cons a Empty  -- like [a] for lists
    Empty <*> m = Empty
    (Cons f cdr) <*> m = (fmap f m) `mappend` (cdr <*> m)
--  Make a list
let list = Cons 1 (Cons 2 (Cons 3 Empty))
--  Make a list of functions
let functions = Cons (+2) (Cons (*2) Empty)
-- We get the same result with MyList
functions <*> list
=> Cons {car = 3, cdr = Cons {car = 4, cdr = Cons {car = 5, cdr =
   Cons {car = 2, cdr = Cons {car = 4, cdr = Cons {car = 6, cdr = Empty}}}}}}

The definition of <*> is just building on fmap and mappend. Which is neat and shows how all of these things are related. For a list, <*> just maps each function over each item in the list like a nested loop, and appends them together into one list.