Haskell/Applicative Functors

From Wikibooks, the open-content textbooks collection

There are no reviewed revisions of this page, so it may not have been checked for quality.

Applicative Functors (Solutions)

Applicative functors are functors with some extra properties, the most important one is that it allows you to apply functions inside the functor (hence the name) to other values. First we do a quick recap of functors, next we will see the applicative functors, and for what structure they are used. After that, we'll see that we can get an applicative functor out of every monad, and then we'll see an example of an applicative functor that is not a monad, but still very useful.

[edit] Functors

Functors, or instances of the typeclass Functor, are some of the most often used structures in Haskell. Typically, they are structures that "can be mapped over". Here is the class definition of Functor:

 class Functor f where
   fmap :: (a -> b) -> f a -> f b

The most well-known functor is the list, where fmap corresponds to map. Another example is Maybe:

 instance Functor Maybe where
   fmap f (Just x) = Just (f x)
   fmap _ Nothing  = Nothing

Typically, for all tree-like structures you can write an instance of Functor

Exercises

Define instances of Functor for the following types:

The rose tree type Tree, defined by:
```
data Tree a = Node a [Tree a]
```
Either e for a fixed e.
The function type ((->) t). In this case, f a will be (t -> a)

[edit] Applicative Functors

Applicative functors are functors with extra properties: you can apply functions inside a functor to values that can be inside the functor or not. We will first look at the definition, then at some instances of applicative functors and their most important use.

[edit] Definition

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

The pure function lifts any value inside the functor. (<*>) changes a function inside the functor to a function over values of the functor. The functor should satisfy some laws:

 pure id <*> v = v                            -- Identity
 pure (.) <*> u <*> v <*> w = u <*> (v <*> w) -- Composition
 pure f <*> pure x = pure (f x)               -- Homomorphism
 u <*> pure y = pure ($ y) <*> u              -- Interchange

And the Functor instance should satisfy the following law:

 fmap f x = pure f <*> x                      -- Fmap

[edit] Instances

As we have seen the Functor instance of Maybe, let's try to make it Applicative as well.

The definition of pure is easy. It is Just. Now the definition of (<*>). If any of the two arguments is Nothing, the result should be Nothing. Otherwise, we extract the function and its argument from the two Just values, and return Just the function applied to its argument:

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

Exercises

Check that the Applicative laws hold for this instance for Maybe
Write Applicative instances for

Either e, for a fixed e
((->) t), for a fixed t

[edit] Using Applicative Functors

The use of (<*>) may not be immediately clear, so let us look at some example that you may have come across yourself.

Suppose we have the following function:

 f :: Int -> Int -> Int
 f x y = 2 * x + y

But instead of Ints, we want to apply this function to values of type Maybe Int. Because you've seen this problem before, you decide to write a function fmap2:

 fmap2 :: (a -> b -> c) -> Maybe a -> Maybe b -> Maybe c
 fmap2 f (Just x) (Just y) = Just (f x y)
 fmap2 _ _        _        = Nothing

You are happy for a while, but then you find that f really needs another Int argument. But now, fmap2 isn't sufficient anymore. You need another function to accomodate for this extra parameter:

 fmap3 :: (a -> b -> c -> d) -> Maybe a -> Maybe b -> Maybe c -> Maybe d
 fmap3 f (Just x) (Just y) (Just z) = Just (f x y z)
 fmap3 _ _        _        _        = Nothing

This is all good an such, but what if f suddenly needs 4 arguments, or 5, or 10?

Here is where (<*>) comes in. Look at what happens if you write fmap f:

 f :: (a -> b -> c)
 fmap :: Functor f => (d -> e) -> f d -> f e
 fmap f :: Functor f => f a -> f (b -> c)    -- Identify d with a, and e with (b -> c)

Now the use of (<*>) becomes clear. Once we have the final f (b -> c), we can use it to get a (f b -> f c). And indeed:

 fmap2 f a b = f `fmap` a <*> b
 fmap3 f a b c = f `fmap` a <*> b <*> c
 fmap4 f a b c d = f `fmap` a <*> b <*> c <*> d

To make it look more pretty, the Control.Applicative library defines (<$>) as a synonym of fmap. The ultimate result is that the code is much cleaner to read and easier to adapt and reuse.

Anytime you feel the need to define different higher order functions to accomodate for function-arguments with a different amount of arguments, think about how defining a proper instance of Applicative can make your life easier.

[edit] Monads and Applicative Functors

The type of pure may look familiar. Indeed, if you change its typeclass restriction from:

 Applicative f => a -> f a

to

 Monad m => a -> m a

it has exactly the same type as return.

As a matter of fact, every instance of Monad can also be made an instance of Applicative. Here are the definitions that can be used:

 pure  = return
 (<*>) = ap

Here, ap is defined as:

 ap f a = do
   f' <- f
   a' <- a
   return (f' a')

It is also defined in Control.Monad

Exercises
Check that the `Applicative` instance of `Maybe` can be obtained by the above transformation.

[edit] ZipLists

Let's come back now to the idea that Applicative can make life easier. Perhaps the best known example of this are the different zipWithN functions of Data.List. It looks exactly like the kind of pattern that an applicative functor would be useful for.

For technical reasons, we can not define a Applicative instance for [], as it already has one defined. This instance does something completely different. fs <*> xs takes all functions from fs and applies them to all values in xs. To remedy this, we create a wrapper:

 newtype ZipList a = ZipList [a]
 
 instance Functor ZipList where
   fmap f (ZipList xs) = ZipList (map f xs)

To make this an instance of Applicative with the expected behaviour, we shall first look at the definition of (<*>), as it follows quite straightforward from what we want to do. The (<*>) operator takes a list of functions and a list of values, and it should apply the functions to the values in a pairwise way. This sounds a lot like zipWith ($), we just need to add the ZipList wrapper:

 instance Applicative ZipList where
   (ZipList fs) <*> (ZipList xs) = ZipList $ zipWith ($) fs xs
   pure                          = undefined

Now we only need to define pure. If we define it like this:

 pure x = [x]

it won't satisfy the Identity law, pure id <*> v = v, since v can contain more than one element, and zipWith only returns a list of the smaller of the two input sizes. Since we don't know how many elements v has, the safest way is to let pure return a list of infinite elements. Now our instance declaration is complete:

 instance Applicative ZipList where
   (ZipList fs) <*> (ZipList xs) = ZipList (zipWith ($) fs xs)
   pure x                        = ZipList (repeat x)