Haskell/Solutions/Applicative Functors

← Back to Applicative Functors


FunctorsEdit

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. (bonus) The function type ((->) t). In this case, f a will be (t -> a)
 data Tree a = Node a [Tree a]
 
 instance Functor Tree where
   fmap f (Node a ts) = Node (f a) (map (fmap f) ts)
 
 instance Functor (Either e) where
   fmap f (Left l)  = Left l
   fmap f (Right r) = Right (f r)
 
 instance Functor ((->) t) where
   fmap f g = f . g

It may be helpful for the third exercise ((->) t) to walk through the type. fmap has type:

 fmap :: (a -> b) -> f a -> f b

Substituting ((->) t) where we have f:

 fmap :: (a -> b) -> (t -> a) -> (t -> b)

which is the type of composition:

 (.) :: (b -> c) -> (a -> b) -> a -> c

Applicative FunctorsEdit

InstancesEdit

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

1)

 instance Applicative Maybe where
   pure = Just
   (Just f) <*> (Just x) = Just (f x)
   _        <*> _        = Nothing
 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
 fmap f x = pure f <*> x                      -- Fmap
  • Identity:
 pure id <*> v = Just id <*> v

The match depends only on v:

 = case v of
     Nothing -> Nothing
     Just v' -> Just (id v') = Just v'

So the Identity law holds.

  • Composition:
 pure (.) <*> u <*> v <*> w = ((Just (.) <*> u) <*> v) <*> w

In case u is Nothing, the first part (Just (.) <*> u) will also be Nothing, and thus the whole expression will be Nothing. So assume that u is Just u'. Then we have:

 ((Just (.) <*> Just u') <*> v) <*> w = (Just (u' .) <*> v) <*> w

Again, if v is Nothing, the whole expression will be Nothing. Assume that v is Just v'. The result:

 (Just (u' .) <*> v) <*> w = (Just (u' . v')) <*> w

Same here, but now assume that w is Just w':

 (Just (u' . v')) <*> w = Just ((u' . v') w') = Just (u' (v' w'))
 = Just u' <*> Just (v' w')

This can be changed back to u <*> Just (v' w'), because if we add back the probability that u can be Nothing, u <*> Just (v' w') is Nothing, which is what we want. We also have:

 Just (v' w') = Just v' <*> Just w'

And if we add back the probability that v and w can be Nothing, we will see that that subexpression will be Nothing if any of the two is Nothing. Also, this will make the whole expression equal to Nothing. Now we have:

 u <*> (v <*> w)

So the Composition law holds

  • Homomorphism
 pure f <*> pure x = Just f <*> Just x = Just (f x) = pure (f x)

By definition of (<*>) and pure.

  • Interchange
 u <*> pure y = u <*> Just y

This depends only on the value of u:

 = case u of
     Nothing -> Nothing
     Just u' -> Just (u' y)

On the other hand, we have:

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

This also depends only on the value of u:

 = case u of
     Nothing -> Nothing
     Just u' -> Just (($ y) u') = Just (u' y)

So the Interchange law holds.

  • Fmap
 fmap f x = case x of
              Nothing -> Nothing
              Just x' -> Just (f x')

On the other hand, we have:

 pure f <*> x = Just f <*> x

This depends only on the value of x:

 = case x of
     Nothing -> Nothing
     Just x' -> Just (f x')

So the Fmap law holds.

2)

 instance Applicative (Either e) where
   pure = Right
   (Right f) <*> (Right x) = Right (f x)
   (Left e)  <*> _         = Left e
   _         <*> (Left e)  = Left e
 
 instance Applicative ((->) t) where
   pure = const
   f1 <*> f2 = \t -> f1 t (f2 t)

Monads and Applicative FunctorsEdit

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

For reference, here is the Monad instance of Maybe:

 instance Monad Maybe where
   return = Just
   Nothing >>= _ = Nothing
   Just x  >>= f = f x

Obviously: return = Just = pure.

De-sugaring ap gives:

 ap f x = f >>= \f' -> x >>= \x' -> return (f' x')

Substituting the first (>>=) by its definition gives:

 ap f x = case f of
   Nothing -> Nothing
   Just f' -> x >>= \x' -> return (f' x')

Substituting the second (>>=) and return by its definition gives:

 ap f x = case f of
   Nothing -> Nothing
   Just f' -> case x of
     Nothing -> Nothing
     Just x' -> Just (f' x')

If we change the case branches by pattern matches, we get:

 ap Nothing _ = Nothing
 ap (Just f') Nothing = Nothing
 ap (Just f') (Just x') = Just (f' x')

which can be written as:

 ap (Just f') (Just x') = Just (f' x')
 ap _         _         = Nothing

Which is the definition of (<*>)

Last modified on 10 March 2013, at 15:00