Haskell/Applicative Functors

From Wikibooks, open books for an open world
Jump to: navigation, search

Applicative functors are functors with some extra properties. Most importantly, they allow you to apply functions inside the functor (hence the name).

Functors[edit]

Functors (i.e. instances of the typeclass Functor) 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:

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

Applicative Functors[edit]

  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

Instances[edit]

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
  1. Check that the Applicative laws hold for this instance for Maybe
  2. Write Applicative instances for
  1. Either e, for a fixed e
  2. ((->) t), for a fixed t

Using Applicative Functors[edit]

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 have a function that takes more arguments. How can we generalize? We need (<*>).

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.

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

Anytime you feel the need to define different higher order functions to accommodate a different number of arguments, think about how defining a proper instance of Applicative can make your life easier.

Of course, Control.Applicative provides the above functions as convenience, under the names of liftA to liftA3.

Monads and Applicative Functors[edit]

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.

ZipLists[edit]

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 cannot define an 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 = ZipList [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)

References[edit]

Control.Applicative