Haskell/Solutions/Applicative Functors

← Back to Applicative Functors

Functors

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. (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 Functors

Instances

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

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 Functors

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 (<*>)