Haskell Language 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