← Back to Applicative Functors

Functors

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 Functors

Instances

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)
```

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