Tipo non corrispondente durante la scrittura di un'istanza Functor per O

Question

Dopo gli esercizi nella Typeclassopedia, ho provato a implementare un'istanza di Functor per Either. Il mio primo tentativo è stato il seguente:

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

Ciò solleva la seguente fase di compilazione errore:

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 

Il modo più semplice per risolvere questo è quello di sostituire la seconda definizione di fmap come la seguente:

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

Qualcuno può spiegarmi perché l'errore viene risolto esplicitamente con il modello di corrispondenza nella seconda definizione di fmap?

Answer 1

Il motivo è che si sta modificando il tipo di Left a anche quando non si cambiano i valori al suo interno. Si noti che per Left 1 :: Either Int String, fmap length (Left 1) ha tipo Either Int Int. Anche se un solo numero intero appare nel valore di Left 1, il suo tipo è cambiato perché l'altro parametro di tipo è cambiato.

Questo è simile al seguente caso:

> 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’ 

Anche se entrambi i valori sono la lista vuota, gli elenchi sono tipi differenti. x ha tipo [String] e fmap length x ha tipo [Int]. Poiché l'uguaglianza ha il tipo (==) :: Eq a => a -> a -> Bool, si vede che non è possibile confrontare i valori di due diversi tipi per l'uguaglianza poiché è lo stesso a.

Answer 2

Il tuo problema è la terza linea:

fmap _ left = left 

Il termine left nel lato sinistro ha digitare Either a a1, e sul lato destro dovrebbe avere tipo Either a b. Inoltre, non è prevista l'unificazione di a1 e perché il tipo di fmap è Functor f => (a1 -> b) -> (f a1 -> f b) o, in particolare per questa istanza, (a1 -> b) -> (Either a a1) -> (Either a b). Da qui l'errore di tipo.