Type mismatch when writing a Functor instance for Either

Question

Following the exercises in the Typeclassopedia, I tried to implement an instance of Functor for Either. My first attempt was the following:

instance Functor (Either a) where
  fmap f (Right a) = Right (f a)
  fmap _ left = left

This raises the following compile-time error:

functor.hs:7:17:
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 functor.hs:6:3
  ‘b’ is a rigid type variable bound by
      the type signature for
        fmap :: (a1 -> b) -> Either a a1 -> Either a b
      at functor.hs:6:3
Expected type: Either a b
  Actual type: Either a a1
Relevant bindings include
  left :: Either a a1 (bound at functor.hs:7:10)
  fmap :: (a1 -> b) -> Either a a1 -> Either a b
    (bound at functor.hs:6:3)
In the expression: left
In an equation for ‘fmap’: fmap _ left = left

The easiest way to solve this is to replace the second definition of fmap like the following:

instance Functor (Either a) where
  fmap f (Right a) = Right (f a)
  fmap _ (Left a) = Left a

Can someone explain me why the error is solved by explicitly pattern-matching in the second definition of fmap?

bheklilr bheklilr · Accepted Answer · 2014-10-25T13:59:06

The reason is that you're changing the type of the Left a even when you aren't changing the values inside it. Note that for Left 1 :: Either Int String, fmap length (Left 1) has type Either Int Int. Even though only one integer appears in the value of Left 1, it's type has changed because the other type parameter changed.

This is similar to the following case:

> let x = [] :: [String]
> x == fmap length x
Couldn't match type ‘Int’ with ‘[Char]’
Expected type: [Char] -> String
  Actual type: [Char] -> Int
In the first argument of ‘fmap’, namely ‘length’
In the second argument of ‘(==)’, namely ‘fmap length x’

Even though both values are the empty list, the lists have different types. x has type [String] and fmap length x has type [Int]. Since equality has the type (==) :: Eq a => a -> a -> Bool, you see that you can't compare values of two different types for equality since it's the same a.

Type mismatch when writing a Functor instance for Either

2 Answers