Why can't I make Either instance of Functor using id in Haskell?

Question

When making my custom Either, and Functor, just to understand clearer types and typeclasses, I found the following situation:

Functor

module Functor (Functor, fmap) where

import Prelude hiding(Functor, fmap)

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

Either

module Either(Either(..)) where
import Prelude hiding(Either(..), Functor, fmap)

data Either a b = Left a | Right b deriving(Show)

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

The code showed above compiles fine but, if I change it to use id, it doesn't compile:

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

Why?? Did I miss something? The following code also doesn't work:

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

... This seems to me very strange because the code showed below compiles:

data Shape = Circle Point Float | Rectangle Point Point deriving (Show)

data Point = Point Float Float deriving (Show)

test :: Shape -> String
test (Circle _ x) = show x
test all@(Rectangle _ x) = show all ++ " - "++ show x

Thank you in advance

Answer 1

What you're trying to do boils down to this:

f :: Either a Bool -> Either a ()
f (Right _) = Right ()
f left = left

with error:

foo.hs:3:7:
    Couldn't match type ‘Bool’ with ‘()’
    Expected type: Either a ()
      Actual type: Either a Bool
    In the expression: left
    In an equation for ‘f’: f left = left
Failed, modules loaded: none.

left is bound to the function argument. So the type checker knows it's of type Either a Bool. Then it's used as the return value. We know from the type f :: Either a Bool -> Either a () that the return value must be of type Either a (). If left is a valid return value, it's type must match the return type of f. So Either a () must be equal to Either a Bool; it is not, so the type checker rejects the program.

In turn, it's basically the same problem as this:

λ let l = Left () :: Either () ()
l :: Either () ()

λ l
Left ()
it :: Either () ()

λ l :: Either () Bool

<interactive>:10:1:
    Couldn't match type ‘()’ with ‘Bool’
    Expected type: Either () Bool
      Actual type: Either () ()
    In the expression: l :: Either () Bool
    In an equation for ‘it’: it = l :: Either () Bool

We gave l a binding and a type, then tried to use it as a different type. That's invalid (and feeding it through id wouldn't change its type either). Even though Left () is also valid source code text for a value of type Either () Bool, that doesn't mean that a particular value known to be of type Either () () that could be defined with the source text Left () can be used as if it were of type Either () Bool.

If you had a polymorphic value, you could do this:

λ let l = Left ()
l :: Either () b

λ l :: Either () ()
Left ()
it :: Either () ()

λ l :: Either () Bool
Left ()
it :: Either () Bool

Note that the original l value here was polymorphic in b; it can be used as an Either () b for any b.

But your fmap case is subtly different. The function fmap is polymorphic in the b, but the value of its argument is "within the scope of the polymorphism"; at the point you have your argument the type b has been chosen to be some specific type by the caller of fmap, so it's "some unknown type that could by anything" rather than "any type I feel like choosing". There is no way to somehow turn a value of type Either a b into a value of type Either a c, so you have to extract the a value and then create an Either a c containing it.

Answer 2

Let's look at the type of fmap specialized for the Either functor:

fmap :: (a -> b) -> Either e a -> Either e b

As we can see from this, in fmap f all@(Left _), the type of all is Either e a. This doesn't match the intended result type Either e b prescribed by the signature of fmap, so fmap f all@(Left _) = all is not well-typed.

Similarly for the case using id.