Lists

Let's start with a list because fmap is a function we've already seen in disguise. Remember the map function?

map :: (a -> b) -> [a] -> [b]
map f []     = []
map f (x:xs) = f x : map f xs

It applies its first argument to every element in its second argument and collects the results. It certainly has the right type and is easily verified to satisfy the two functor laws:

• Identity: We need to verify the identity law for both empty and non-empty lists. For the empty list, we have

  map id [] = []       -- First equation of map
            = id []    -- Definition of id
  

  For a non-empty list, we have

  map id (x:xs) = id x : map id xs    -- Second equation of map
                = x : map id xs       -- Definition of id
                = x : id xs           -- Induction because xs is shorter than (x:xs)
                = x : xs              -- Definition of id
                = id (x:xs)           -- Definition of id
  

• Composition: Again, we need to verify that this law holds for both empty and non-empty lists. For the exmply list, we have

  map (f . g) [] = []                    -- First equation of map
                 = map f []              -- First equation of map
                 = map f (map g [])      -- First equation of map
                 = (map f . map g) []    -- Definition of function composition
  

  For a non-empty list, we have

  map (f . g) (x:xs)
      = (f . g) x : map (f . g) xs        -- Second equation of map
      = (f . g) x : (map f . map g) xs    -- Induction because xs is shorter than (x:xs)
      = f (g x) : map f (map g xs)        -- Definition of function composition
      = map f (g x : map g xs)            -- Second equation of map
      = map f (map g xs)                  -- Second equation of map
      = (map f . map g) xs                -- Definition of function composition
  

Thus, for lists, we have

instance Functor [] where
    fmap = map

Indeed, fmap stands for "functor map", a generalization of map to arbitrary functors.