Type of inconsistency when writing an instance of Functor for Either

Question

Following the exercises in Typeclassopedia, I tried to implement a Functor instance for Either. My first attempt was as follows:

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

This results in 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 ab at functor.hs:6:3 'b' is a rigid type variable bound by the type signature for fmap :: (a1 -> b) -> Either a a1 -> Either ab at functor.hs:6:3 Expected type: Either ab 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 ab (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 as follows:

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

Can someone explain to me why the error was resolved by explicit pattern matching in the second fmap definition?

Answer 1

The reason is that you change the type of Left a , even if you do not change the values ​​inside it. Note that for Left 1 :: Either Int String , fmap length (Left 1) is of type Either Int Int . Although only one integer is displayed in the Left 1 value, its type has changed because another parameter has 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' 

Although both values ​​are an empty list, lists have different types. x is of type [String] and fmap length x is of type [Int] . Since equality is of type (==) :: Eq a => a -> a -> Bool , you see that you cannot compare the values ​​of two different types for equality, since it is the same a .

Answer 2

Your problem in the third line:

 fmap _ left = left 

The term left on the left side is of type Either a a1 , and the right side should be of type Either ab . In addition, it is expected that a1 and b will not be unified, since the type fmap is equal to Functor f => (a1 -> b) -> (f a1 -> fb) or, in particular, for this instance (a1 -> b) -> (Either a a1) -> (Either ab) . Therefore, a type error.