Maybe
Next up, Maybe:
data Maybe a = Nothing | Just a
We have two possibilities here: Either the container is empty, we have a
Nothing; or it stores exactly one element x, we have a Just x. The
identity law says that applying id to every element in a container should
produce the original container. Thus, applying a function to the empty container
should produce an empty container. Applying a function f to a Just x should
produce Just (f x):
instance Functor Maybe where
fmap f Nothing = Nothing
fmap f (Just x) = Just (f x)
Exercise
Verify the functor laws for the Maybe functor.
Solution
Identity:
fmap id Nothing = Nothing -- First equation of fmap
= id Nothing -- Definition of id
fmap id (Just x) = Just (id x) -- Second equation of fmap
= Just x -- Definition of id
= id (Just x) -- Definition of id
Composition:
fmap (f . g) Nothing
= Nothing -- First equation of fmap
= fmap f Nothing -- First equation of fmap
= fmap f (fmap g Nothing) -- First equation of fmap
= (fmap f . fmap g) Nothing -- Definition of function composition
fmap (f . g) (Just x)
= Just ((f . g) x) -- Second equation of fmap
= Just (f (g x)) -- Definition of function composition
= fmap f (Just (g x)) -- Second equation of fmap
= fmap f (fmap g (Just x)) -- Second euation of fmap
= (fmap f . fmap g) (Just x) -- Definition of function composition
Exercise
Recall the replicate function we used in earlier exercises.
replicate n x builds a list containing n copies of x:
>>> replicate 5 1
[1,1,1,1,1]
If n is negative, then replicate n xs simply produces the empty list:
>>> replicate (-1) 1
[]
Assume we have a function safeReplicate instead, one that makes n copies
of x if x is non-negative, and returns Nothing if n is negative:
safeReplicate :: Int -> a -> Maybe [a]
safeReplicate n x | n < 0 = Nothing
| otherwise = Just (replicate n x)
We can now use this function to implement a simple and not very meaningful example of a computation that is quite common: We want to map a function over a list of arguments. For some of these arguments, we obtain a result. For others, we don't:
>>> safeReplicate n x = if n < 0 then Nothing else Just (replicate n x)
>>> map (uncurry safeReplicate) [(1,5),(3,4),(-1,8),(2,7),(-9,10)]
[Just [5],Just [4,4,4],Nothing,Just [7,7],Nothing]
Now we're finally coming to the point of this exercise. We want to take a
list of type [Maybe [a]] and a function f :: a -> b, and we want to
apply f to each of the inner lists. For example, in the example just
given, the list produced by map (uncurry safeReplicate) ... has the type
[Maybe [Int]]. We may want to double each of values in the inner lists:
>>> mysteryFunction (* 2) xss
[Just [10],Just [8,8,8],Nothing,Just [14,14],Nothing]
The function we're after is
mysteryFunction :: (a -> b) -> [Maybe [a]] -> [Maybe [b]]
Use fmap to implement this function. It will be helpful to peel the onion
here:
To apply a function f :: a -> b to a list xs :: [a], we can use
fmap f xs. To apply a function g :: [a] -> [b] to a value
mxs :: Maybe [a], we can use fmap g mxs. Finally, to apply a function
h :: Maybe [a] -> Maybe [b] to a list mxss :: [Maybe [a]], we can use
fmap h mxss. Now put the puzzle pieces together.
Solution
mysteryFunction = fmap . fmap . fmap
Yup, that's it. You can think of fmap f xs as reaching into a
container xs and applying f to each element in xs.
(fmap . fmap) f xs then reaches two levels down: Given a container of
containers, this applies f to each element in each of the inner
containers. In this exercise, we had a container of containers of
containers, the outer container being a list, the containers inside it
being Maybes, and the containers in each of these second-level
containers being lists. So we need to reach three levels down, using
fmap . fmap . fmap.
Maybe that's a bit more illuminating when looking at the types involved.
If you type the above definition of mysteryFunction into GHCi without
specifying its type, you actually get a type of mysteryFunction that
is more general than the one given in the exercise:
>>> mysteryFunction = fmap . fmap . fmap
>>> :t mysteryFunction
mysteryFunction
:: (Functor f1, Functor f2, Functor f3) =>
(a -> b) -> f1 (f2 (f3 a)) -> f1 (f2 (f3 b))
All those numbers make me dizzy, so let's rewrite this type using names
f, g, and h instead of f1, f2, and f3:
mysteryFunction :: (Functor f, Functor g, Functor h) => (a -> b) -> (f (g (h a))) -> (f (g (h b)))
Remember that a functor is our abstraction of a container. If we have a
function of type k :: a -> b and a container of containers of
containers of as, then we can use mysteryFunction to obtain a
container of contaires of containers of bs, by applying k to every
a in this hierarchy of containers. Here, f is the outer container
type. This can be a list, a tree, anything. g is the container type
nested within it. In our example, this was Maybe, but it can once
again be any function. And finally, h is the innermost container type.
Now our three fmap implementations for the three functors have the types:
fmap :: (a -> b) -> (h a -> h b)
fmap :: (c -> d) -> (g c -> g d)
fmap :: (p -> q) -> (f p -> f q)
Given a function k :: a -> b, fmap k thus has type h a -> h b.
Setting c = h a and d = h b, this gives
fmap (fmap k) :: g (h a) -> g (h b). And finally, setting
p = g (h a) and q = (g h b), we have
fmap (fmap (fmap k)) :: f (g (h a)) -> f (g (h b)). Thus, we have
mysteryFunction k xs = fmap (fmap (fmap k)) xs
which we can rewrite to obtain the definition
mysteryFunction = fmap . fmap . fmap:
mysteryFunction k xs = fmap (fmap (fmap k)) xs
mysteryFunction k = fmap (fmap (fmap k)) -- Drop the common argument `xs` from
-- both sides
= (fmap . fmap) (fmap k) -- Definition of (.)
= (fmap . fmap . fmap) k -- Definition of (.)
mysteryFunction = fmap . fmap . fmap -- Drop the common argument `k` from
-- both sides