Haskell Language Functor Common instances of Functor
Example
Maybe
Maybe is a Functor containing a possibly-absent value:
instance Functor Maybe where
fmap f Nothing = Nothing
fmap f (Just x) = Just (f x)
Maybe's instance of Functor applies a function to a value wrapped in a Just. If the computation has previously failed (so the Maybe value is a Nothing), then there's no value to apply the function to, so fmap is a no-op.
> fmap (+ 3) (Just 3)
Just 6
> fmap length (Just "mousetrap")
Just 9
> fmap sqrt Nothing
Nothing
We can check the functor laws for this instance using equational reasoning. For the identity law,
fmap id Nothing
Nothing -- definition of fmap
id Nothing -- definition of id
fmap id (Just x)
Just (id x) -- definition of fmap
Just x -- definition of id
id (Just x) -- definition of id
For the composition law,
(fmap f . fmap g) Nothing
fmap f (fmap g Nothing) -- definition of (.)
fmap f Nothing -- definition of fmap
Nothing -- definition of fmap
fmap (f . g) Nothing -- because Nothing = fmap f Nothing, for all f
(fmap f . fmap g) (Just x)
fmap f (fmap g (Just x)) -- definition of (.)
fmap f (Just (g x)) -- definition of fmap
Just (f (g x)) -- definition of fmap
Just ((f . g) x) -- definition of (.)
fmap (f . g) (Just x) -- definition of fmap
Lists
Lists' instance of Functor applies the function to every value in the list in place.
instance Functor [] where
fmap f [] = []
fmap f (x:xs) = f x : fmap f xs
This could alternatively be written as a list comprehension: fmap f xs = [f x | x <- xs].
This example shows that fmap generalises map. map only operates on lists, whereas fmap works on an arbitrary Functor.
The identity law can be shown to hold by induction:
-- base case
fmap id []
[] -- definition of fmap
id [] -- definition of id
-- inductive step
fmap id (x:xs)
id x : fmap id xs -- definition of fmap
x : fmap id xs -- definition of id
x : id xs -- by the inductive hypothesis
x : xs -- definition of id
id (x : xs) -- definition of id
and similarly, the composition law:
-- base case
(fmap f . fmap g) []
fmap f (fmap g []) -- definition of (.)
fmap f [] -- definition of fmap
[] -- definition of fmap
fmap (f . g) [] -- because [] = fmap f [], for all f
-- inductive step
(fmap f . fmap g) (x:xs)
fmap f (fmap g (x:xs)) -- definition of (.)
fmap f (g x : fmap g xs) -- definition of fmap
f (g x) : fmap f (fmap g xs) -- definition of fmap
(f . g) x : fmap f (fmap g xs) -- definition of (.)
(f . g) x : fmap (f . g) xs -- by the inductive hypothesis
fmap (f . g) xs -- definition of fmap
Functions
Not every Functor looks like a container. Functions' instance of Functor applies a function to the return value of another function.
instance Functor ((->) r) where
fmap f g = \x -> f (g x)
Note that this definition is equivalent to fmap = (.). So fmap generalises function composition.
Once more checking the identity law:
fmap id g
\x -> id (g x) -- definition of fmap
\x -> g x -- definition of id
g -- eta-reduction
id g -- definition of id
and the composition law:
(fmap f . fmap g) h
fmap f (fmap g h) -- definition of (.)
fmap f (\x -> g (h x)) -- definition of fmap
\y -> f ((\x -> g (h x)) y) -- definition of fmap
\y -> f (g (h y)) -- beta-reduction
\y -> (f . g) (h y) -- definition of (.)
fmap (f . g) h -- definition of fmap
