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

Question

When creating custom Either and Functor to understand clearer types and type classes, I found the following situation:

Functor

 module Functor (Functor, fmap) where import Prelude hiding(Functor, fmap) class Functor f where fmap :: (a -> b) -> fa -> fb 

Either

 module Either(Either(..)) where import Prelude hiding(Either(..), Functor, fmap) data Either ab = Left a | Right b deriving(Show) instance Functor (Either a) where fmap f (Right x) = Right (fx) fmap _ (Left x) = Left x 

The code shown above compiles fine, but if I replaced it with id , it won't compile:

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

Why?? Did I miss something? The following code also does not work:

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

... It seems very strange to me, because the code shown 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 are trying to do boils down to the following:

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

with an 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 bound to the function argument. Thus, the checking type knows its type Either a Bool . Then it is used as the return value. We know from 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 must match the return type f . So, Either a () should be equal to Either a Bool ; this is not so, therefore, the checking type rejects the program.

In turn, this is 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 binding and a type, and then tried to use it as another type. This is invalid (and passing it through id will not change its type either). Although Left () also valid source code for a value of type Either () Bool , this does not mean that a specific value, known as type Either () () , that can be defined with the source text of Left () , can be used as if it were of type Either () Bool .

If you have a polymorphic value, you can do this:

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

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

But your fmap case looks a little different. Function fmap is polymorphic in b , but the value of its argument is "within polymorphism"; at the point where you have an argument, type b was chosen by the specific type as the fmap caller, so it is "some unknown type that could have anything," and not "any type that I feel like a choice." It is not possible to somehow convert a value of type Either ab to a value of type Either ac , so you need to extract the value of a and then create Either ac containing it.

Answer 2

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

 fmap :: (a -> b) -> Either ea -> Either eb 

As you can see from this, in fmap f all@ (Left _) type all is equal to Either ea . This does not match the Either eb result type specified by the fmap signature, so fmap f all@ (Left _) = all not typical.

Similarly for the case using id .

Answer 3

In terms of explaining a type error, I have nothing to add to the previous two answers, however I would like to mention that Left x :: Either ta appears in memory the same way as Left x :: Either tb . This means that, despite the fact that the type system does not allow Either ta to be used instead of a value of type Either tb , for reasons that were explained in full clarity by other answers, you can "force" it through using unsafeCoerce :

 import Unsafe.Coerce (unsafeCoerce) instance Functor (Either t) where fmap f (Right a) = Right (fa) fmap fl = unsafeCoerce l 

And even if unsafeCoerce usually seen as something to avoid, if you know what you are doing and you have good reason for this, for example, performance, unsafeCoerce can be useful in telling the compiler you are sure that the runtime value is will match the expected structure.

In this case, without unsafeCoerce and without taking into account any potential GHC optimizations fmap f (Left x) = Left x will always build a new but physically identical Left value, while the unsafeCoerce flavor unsafeCoerce simply return the original Left value without additional memory allocations.