rendere i dati Tipo di Kind * -> * Questo non è un di Functor

Question

Brent Yorgey Typeclassopedia dà il seguente esercizio:

dare un esempio di un tipo di genere * -> * che non può essere fatto un istanza di Functor (senza utilizzando undefined).

La prego di dirmi che cosa "non può essere fatta un'istanza di Functor" si intende.

Inoltre, mi piacerebbe un esempio, ma forse come uno spoiler in modo che tu possa, per favore, guidami alla risposta.

Answer 1

Parliamo di varianze.

Ecco la nozione di base. Si consideri il tipo A -> B. Quello che voglio che tu possa immaginare è che un simile tipo è simile a "avere un B" e anche "a causa di un A".Infatti, se restituisci il tuo A ricevi immediatamente il tuo B. Le funzioni sono un po 'come l'impegno in questo modo.

La nozione di "avere" e "dovere" può estendersi ad altri tipi. Per esempio, il contenitore più semplice

newtype Box a = Box a 

si comporta in questo modo: se si "ha" un Box a allora anche voi "avere" un a. Consideriamo i tipi che hanno tipo * -> * e "abbiamo" la loro tesi di essere (covarianti) funtori e possiamo istanziare a Functor

instance Functor Box where fmap f (Box a) = Box (f a) 

Che cosa succede se si considera il tipo di predicati oltre un tipo, come

newtype Pred a = Pred (a -> Bool) 

in questo caso, se "abbiamo" un Pred a, in realtà "dobbiamo" un a. Questo deriva dal a che si trova sul lato sinistro della freccia (->). Dovedi Functor viene definito passando la funzione nel contenitore e applicandola a tutti i luoghi in cui "abbiamo" il nostro tipo interno, non possiamo fare lo stesso per Pred a poiché non "abbiamo" e a s.

Invece, lo faremo

class Contravariant f where 
    contramap :: (a -> b) -> (f b -> f a) 

Ora che contramap è come un "capovolto" fmap? Ci consentirà di applicare la funzione ai luoghi in cui "possediamo" uno b in Pred b per ricevere uno Pred a. Potremmo chiamare contramap "baratto" perché codifica l'idea che se si sa come ottenere b s da a s, è possibile convertire un debito di b s in un debito di a s.

Vediamo come funziona

instance Contravariant Pred where 
    contramap f (Pred p) = Pred (\a -> p (f a)) 

abbiamo appena eseguire il nostro commercio con f prima di trasmetterla alla funzione predicato. Meraviglioso!

Quindi ora abbiamo tipi covarianti e controvarianti. Tecnicamente, questi sono conosciuti come "funtori" covarianti e controvarianti. Dirò anche immediatamente che quasi sempre un funzionario controverso non è anche covariante. Questo, quindi, risponde alla tua domanda: esiste un gruppo di funtori controvarianti che non possono essere istanziati a Functor. Pred è uno di questi.

Ci sono tipi complicati che sono sia funtori controvarianti che covarianti. In particolare, i funtori costanti:

data Z a = Z -- phantom a! 

instance Functor  Z where fmap  _ Z = Z 
instance Contravariant Z where contramap _ Z = Z 

In realtà, si può in sostanza, dimostrare che tutto ciò che è sia Contravariant e Functor ha un parametro fantasma.

isPhantom :: (Functor f, Contravariant f) => f a -> f b -- coerce?! 
isPhantom = contramap (const()) . fmap (const())  -- not really... 

D'altra parte, ciò che accade con un tipo come

-- from Data.Monoid 
newtype Endo a = Endo (a -> a) 

In Endo a entrambi dobbiamo e ricevere una a.Significa che siamo senza debiti? Bene, no, significa solo che Endo vuole essere sia covariante che controvariante e non ha un parametro fantasma. Il risultato: Endo è invariante e non è possibile creare un'istanza né Functor né Contravariant.

Answer 2

Un tipo t di tipo * -> * può essere fatta un'istanza di Functor se e solo se è possibile implementare un'istanza rispettoso della legge della classe Functor per esso. In modo che significa che è necessario implementare la classe Functor, e la vostra fmap deve obbedire alle Functor leggi:

fmap id x == x 
fmap f (fmap g x) == fmap (f . g) x 

Quindi, fondamentalmente, per risolvere questo, è necessario nominare un certo tipo di vostra scelta e dimostrare che non c'è nessun legittimo implementazione di fmap per questo.

Iniziamo con un non -esempio, per impostare il tono. (->) :: * -> * -> * è il costruttore del tipo di funzione, come si vede nei tipi di funzioni come String -> Int :: *. In Haskell è possibile applicare parzialmente i costruttori di tipi, quindi è possibile avere tipi come (->) r :: * -> *. Questo tipo è un Functor:

instance Functor ((->) r) where 
    fmap f g = f . g 

Intuitivamente, l'istanza Functor qui consente di applicare f :: a -> b per il valore di ritorno di una funzione g :: r -> a "prima" (si fa per dire) si applica ad alcuni gx :: r. Così, per esempio, se questa è la funzione che restituisce la lunghezza della sua tesi:

length :: [a] -> Int 

... allora questa è la funzione che restituisce due volte la lunghezza del suo argomento:

twiceTheLength :: [a] -> Int 
twiceTheLength = fmap (*2) length 

fatto Utile : la monade Reader è solo un newtype per (->):

newtype Reader r a = Reader { runReader :: r -> a } 

instance Functor (Reader r) where 
    fmap f (Reader g) = Reader (f . g) 

instance Applicative (Reader r) where 
    pure a = Reader (const a) 
    Reader f <*> Reader a = Reader $ \r -> f r (a r) 

instance Monad (Reader r) where 
    return = pure 
    Reader f >>= g = Reader $ \r -> runReader g (f r) r 

Ora che abbiamo che non ad esempio di mezzo, ecco un tipo che non può essere fatto in una Functor:

type Redaer a r = Redaer { runRedaer :: r -> a } 

-- Not gonna work! 
instance Functor (Redaer a) where 
    fmap f (Redaer g) = ... 

Sì, tutto quello che ho fatto è incantesimo il nome all'indietro, e ancora più importante, capovolgere l'ordine dei parametri di tipo. Ti lascio provare e capire perché questo tipo non può essere reso un'istanza di Functor.