Typeclassopedia: Functors

Exploring the Typeclassopedia. First up: Functors.

A Functor is a type which satisfies the following laws:

fmap id = id
fmap (f . g) = fmap f . fmap g

Its declaration is:

class Functor f where
  fmap :: (a -> b) -> f a -> f b

Defining a Functor for Either we get:

instance Functor (Either a) where
  fmap f (Right x) = Right $ f x
  fmap f (Left l) = Left l
  
Why does the instance require (Either a) rather than just Either?

Look back at the type of Fuctor :: (a -> b) -> f a -> f b

The key is the type variable 'f', which has kind * -> *

Firing up ghci, and running `:k Either` shows that Either has kind: * -> * -> *,
to fit Either in the type hole of the Functor one of the type variables must be
fixed (TODO: is this the right terminiology?).
  
Trying to define this as the following:

instance Functor (Either a) where
  fmap f (Right x) = Right $ f x
  fmap _ l         = l

fails with the somewhat confusing error:

    Couldn't match type `a1' with `b'
      `a1' is a rigid type variable bound by
           the type signature for
             fmap :: (a1 -> b) -> Either a a1 -> Either a b
           at <interactive>:42:3
      `b' is a rigid type variable bound by
          the type signature for
            fmap :: (a1 -> b) -> Either a a1 -> Either a b
          at <interactive>:42:3
    Expected type: Either a b
      Actual type: Either a a1
    In the expression: l
    In an equation for `fmap': fmap _ l = l
    In the instance declaration for `Functor (Either a)'