Perché le istanze corrispondono solo alle loro teste?

Question

Inizierò introducendo un problema concreto (StackOverflow è così). Dire si definisce un tipo semplice

data T a = T a 

Questo tipo è un Functor, Applicative e Monad. Ignorando la derivazione automatica, per ottenere quelle istanze devi scriverle singolarmente, anche se implica Applicative, che implica Functor. Più di questo, potrei definire una classe come questa

class Wrapper f where 
    wrap :: a -> f a 
    unwrap :: f a -> a 

Questa è una condizione piuttosto forte e implica sicuramente Monad, ma non riesco a scrivere

instance Wrapper f => Monad f where 
    return = wrap 
    fa >>= f = f $ unwrap fa 

perché questo, per qualche ragione , significa "tutto è un f (f), solo se è un Wrapper", invece di "tutto ciò che è un Wrapper è un Monad".

Analogamente non è possibile definire le istanze Monad a => Applicative a e Applicative a => Functor a.

Un'altra cosa che non è possibile fare (che è probabilmente solo correlata, non lo so davvero) è che una classe sia una superclasse di un'altra e fornire un'implementazione predefinita della sottoclasse. Certo, è bello che sia class Applicative a => Monad a, ma è molto meno bello che io debba ancora definire l'istanza Applicative prima di poter definire lo Monad.

Questo non è un rant. Ho scritto molto perché altrimenti questo sarebbe stato rapidamente contrassegnato come "troppo ampio" o "poco chiaro". La domanda si riduce al titolo. So (almeno sono abbastanza sicuro) che c'è qualche ragione teorica per questo, quindi mi chiedo quali sono esattamente i vantaggi qui.

Come domanda secondaria, vorrei chiedere se ci sono alternative valide che mantengono tutti (o la maggior parte) di questi vantaggi, ma consentono ciò che ho scritto.

Aggiunta: Ho il sospetto che una delle risposte potrebbe essere qualcosa del tipo "Che cosa succede se il mio tipo è un Wrapper, ma io non voglio usare l'istanza Monad che questo comporta?". A questo chiedo, perché il compilatore non ha potuto scegliere quello più specifico? Se c'è uno instance Monad MyType, sicuramente è più specifico di instance Wrapper a => Monad a.

Answer 1

Ci sono un sacco di domande in una di queste. Ma prendiamoli uno alla volta.

Primo: perché il compilatore non esamina i contesti dell'istanza quando sceglie quale istanza utilizzare? Questo per mantenere efficiente la ricerca dell'istanza. Se si richiede al compilatore di prendere in considerazione solo le istanze le cui istanze sono soddisfatte, in sostanza si richiede che il compilatore esegua la ricerca di back tracking tra tutte le possibili istanze, a quel punto è stato implementato il 90% di Prolog. Se, d'altra parte, prendi la posizione (come fa Haskell) che cerchi solo le teste di istanza quando scegli quale istanza usare, e poi applica semplicemente il contesto dell'istanza, non c'è backtracking: in ogni momento, c'è solo una scelta che puoi fare.

Avanti: perché non è possibile avere una classe come superclasse di un'altra e fornire un'implementazione predefinita della sottoclasse? Non esiste una ragione fondamentale per questa restrizione, quindi GHC offre questa funzionalità come estensione.Si potrebbe scrivere qualcosa di simile:

{-# LANGUAGE DefaultSignatures #-} 
class Applicative f where 
    pure :: a -> f a 
    (<*>) :: f (a -> b) -> f a -> f b 

    default pure :: Monad f => a -> f a 
    default (<*>) :: Monad f => f (a -> b) -> f a -> f b 
    pure = return 
    (<*>) = ap 

Poi una volta che aveva fornito un instance Monad M where ..., si potrebbe semplicemente scrivere instance Applicative M senza where clausola e farlo funzionare. Non so davvero perché questo non è stato fatto nella libreria standard.

Ultimo: perché il compilatore non può consentire molte istanze e scegliere solo quello più specifico? La risposta a questo è una specie di mix dei due precedenti: ci sono ottime ragioni fondamentali per cui questo non funziona bene, tuttavia GHC offre comunque un'estensione che lo fa. La ragione fondamentale per cui questo non funziona bene è che l'istanza più specifica per un dato valore non può essere conosciuta prima del runtime. La risposta di GHC a questo è, per i valori polimorfici, scegliere quello più specifico compatibile con il polimorfismo completo disponibile. Se più tardi quella cosa cosa viene monomorfizzata, beh, troppo male per te. Il risultato di ciò è che alcune funzioni possono operare su alcuni dati con un'istanza e altri possono operare sugli stessi dati con un'altra istanza; questo può portare a bug molto sottili. Se dopo tutta questa discussione pensi ancora che sia una buona idea e rifiuti di imparare dagli errori degli altri, puoi attivare IncoherentInstances.

Penso che copre tutte le domande.

Answer 2

Coerenza e compilazione separata.

Se abbiamo due casi le cui teste sia partita, ma hanno diversi vincoli, dicono:

-- File: Foo.hs 

instance Monad m => Applicative m 
instance   Applicative Foo 

Allora o questo è valido codice di produrre un'istanza Applicative per Foo, o si tratta di un errore di produzione di due differenti Applicative istanze per Foo. Quale è dipende se esiste un'istanza monad per Foo. Questo è un problema, perché è difficile garantire che la conoscenza sul fatto di mantenere Monad Foo lo farà al compilatore quando sta compilando questo modulo.

Un diverso modulo (ad esempio Bar.hs) può produrre un'istanza Monad per Foo. Se Foo.hs non importa quel modulo (anche indirettamente), allora come lo sa il compilatore? Peggio ancora, possiamo cambiare se questo è un errore o una definizione valida cambiando se in seguito includiamo Bar.hs nel programma finale o no!

Per far funzionare tutto questo, è necessario sapere che tutte le istanze presenti nel programma finale compilato sono visibili in ogni modulo, il che porta alla conclusione che ogni modulo è una dipendenza di ogni altro modulo indipendentemente dal fatto che il modulo importa effettivamente l'altro. Dovresti andare molto lontano lungo il percorso per richiedere l'analisi di programmi completi per supportare tale sistema, il che rende difficile la distribuzione di librerie precompilate.

L'unico modo per evitare questo è di non fare in modo che GHC prenda decisioni in base alle informazioni negative . Non è possibile scegliere un'istanza basata sullo non -esistenza di un'altra istanza.

Ciò significa che i vincoli su un'istanza devono essere ignorati per la risoluzione dell'istanza.È necessario selezionare un'istanza indipendentemente dal fatto che i vincoli siano validi; se questo lascia più di una possibile istanza applicabile, allora avresti bisogno di informazioni negative (vale a dire che tutte tranne una di esse richiedono vincoli che non reggono) per accettare il codice come valido.

Se si dispone di una sola istanza che è addirittura candidata e non è possibile visualizzare una prova dei suoi vincoli, è possibile accettare il codice semplicemente passando i vincoli su dove viene utilizzata l'istanza (possiamo contare sull'ottenere questa informazione ad altri moduli, perché dovranno importarla, anche se solo indirettamente); se le posizioni non sono in grado di visualizzare un'istanza richiesta, quindi genereranno un errore appropriato su un vincolo non soddisfatto.

Quindi ignorando i vincoli, ci assicuriamo che un compilatore possa prendere decisioni corrette sulle istanze anche solo conoscendo altri moduli che importa (in modo transitorio); non deve sapere nulla di tutto ciò che è definito in ogni altro modulo per sapere quali restrizioni non mantengono premuto.