FunctorsEdit
Exercises 

Define instances of

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