Understanding how Either is an instance of Functor

Question

In my free time I'm learning Haskell, so this is a beginner question.

In my readings I came across an example illustrating how Either a is made an instance of Functor:

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

Now, I'm trying to understand why the implementation maps in the case of a Right value constructor, but doesn't in the case of a Left?

Here is my understanding:

First let me rewrite the above instance as

instance Functor (Either a) where     fmap g (Right x) = Right (g x)     fmap g (Left x) = Left x 

Now:

1. I know that fmap :: (c -> d) -> f c -> f d

2. if we substitute f with Either a we get fmap :: (c -> d) -> Either a c -> Either a d

3. the type of Right (g x) is Either a (g x), and the type of g x is d, so we have that the type of Right (g x) is Either a d, which is what we expect from fmap (see 2. above)

4. now, if we look at Left (g x) we can use the same reasoning to say that its type is Either (g x) b, that is Either d b, which is not what we expect from fmap (see 2. above): the d should be the second parameter, not the first! So we can't map over Left.

Is my reasoning correct?

Answer 1

This is right. There is also another quite important reason for this behavior: You can think of Either a b as a computation, that may succeed and return b or fail with an error message a. (This is also, how the monad instance works). So it's only natural, that the functor instance won't touch the Left values, since you want to map over the computation, if it fails, there's nothing to manipulate.

Answer 2

Your account is right of course. Maybe the reason why we have a difficulty with instances like this is that we are really defining infinitely many functor instances at once -- one for each possible Left type. But a Functor instance is a systematic way of operating on the infinitely many types in the system. So we are defining infinitely many ways of systematically operating on the infinitely many types in the system. The instance involves generality in two ways.

If you take it by stages, though, maybe it's not so strange. The first of these types is a longwinded version of Maybe using the unit type () and its only legitimate value ():

data MightBe b     = Nope ()    | Yep b data UnlessError b = Bad String | Good b data ElseInt b     = Else Int   | Value b 

Here we might get tired and make an abstraction:

data Unless a b    = Mere a     | Genuine b 

Now we make our Functor instances, unproblematically, the first looking a lot like the instance for Maybe:

instance Functor MightBe where   fmap f (Nope ()) = Nope ()   -- compare with Nothing   fmap f (Yep x)   = Yep (f x) -- compare with Just (f x)  instance Functor UnlessError where   fmap f (Bad str) = Bad str   -- a more informative Nothing   fmap f (Good x)  = Good (f x)  instance Functor ElseInt where   fmap f (Else n) = Else n    fmap f (Value b) = Value (f b) 

But, again, why bother, let's make the abstraction:

instance Functor (Unless a) where   fmap f (Mere a) = Mere a   fmap f (Genuine x) = Genuine (f x) 

The Mere a terms aren't touched, as the (), String and Int values weren't touched.