Cosa fa la parola chiave `forall` in Haskell / GHC?

Sto iniziando a capire come viene utilizzata la parola chiave forall nei cosiddetti “tipi esistenziali” come questa:

 data ShowBox = forall s. Show s => SB s 

Questo è solo un sottoinsieme, tuttavia, di come viene utilizzato forall e semplicemente non riesco a comprendere il suo uso in cose del genere:

 runST :: forall a. (forall s. ST sa) -> a 

O spiegando perché questi sono diversi:

 foo :: (forall a. a -> a) -> (Char,Bool) bar :: forall a. ((a -> a) -> (Char, Bool)) 

O tutta la roba di RankNTypes

Io tendo a preferire un inglese chiaro e privo di gergo piuttosto che i tipi di linguaggio che sono normali negli ambienti accademici. La maggior parte delle spiegazioni che cerco di leggere su questo (quelle che posso trovare attraverso i motori di ricerca) hanno questi problemi:

  1. Sono incompleti. Spiegano una parte dell’uso di questa parola chiave (come “tipi esistenziali”) che mi fa sentire felice finché non leggo il codice che lo usa in un modo completamente diverso (come runST , foo e bar sopra).
  2. Sono densamente zeppi di supposizioni secondo cui ho letto le ultime novità in qualsiasi ramo della matematica discreta, della teoria delle categorie o dell’algebra astratta è popolare questa settimana. (Se non leggerò mai le parole “consulta il documento per i dettagli sull’implementazione” di nuovo, sarà troppo presto.)
  3. Sono scritti in modi che spesso trasformano anche semplici concetti in grammatica e semantica tortuosamente contorte e fratturate.

Così…

Alla domanda attuale. Qualcuno può spiegare completamente la parola chiave di forall in chiaro, semplice inglese (o, se esiste da qualche parte, indicare una spiegazione così chiara che ho perso) che non presume che io sia un matematico intriso di gergo?


Modificato per aggiungere:

Di seguito sono emerse due risposte di qualità superiore, ma sfortunatamente posso sceglierne solo una migliore. La risposta di Norman è stata dettagliata e utile, spiegando le cose in un modo che mostrava alcune delle basi teoriche di forall e allo stesso tempo mostrandomi alcune delle implicazioni pratiche di esso. La risposta di yairchu copriva un’area che nessun altro menzionava (variabili di tipo scoped) e illustrava tutti i concetti con codice e una sessione di GHCi. Se fosse ansible selezionare entrambi come meglio, lo farei. Sfortunatamente non posso e, dopo aver esaminato da vicino entrambe le risposte, ho deciso che Yairchu ha leggermente distanziato Norman a causa del codice illustrativo e della spiegazione allegata. Questo è un po ‘ingiusto, tuttavia, perché in realtà avevo bisogno di entrambe le risposte per capire questo al punto che forall non mi lascia con un debole senso di terrore quando lo vedo in un tipo di firma.

Iniziamo con un esempio di codice:

 foob :: forall a b. (b -> b) -> b -> (a -> b) -> Maybe a -> b foob postProcess onNothin onJust mval = postProcess val where val :: b val = maybe onNothin onJust mval 

Questo codice non compila (errore di syntax) in semplice Haskell 98. Richiede un’estensione per supportare la parola chiave forall .

Fondamentalmente, ci sono 3 diversi usi comuni per la parola chiave forall (o almeno così sembra ), e ognuno ha la sua estensione Haskell: ScopedTypeVariables , RankNTypes / Rank2Types , ExistentialQuantification .

Il codice sopra non ottiene un errore di syntax con uno di quelli abilitati, ma solo i controlli di tipo con ScopedTypeVariables abilitato.

Variabili di tipo scopato:

Le variabili di tipo scoped aiutano a specificare i tipi di codice all’interno delle clausole where . Rende la b in val :: b la stessa di b in foob :: forall a b. (b -> b) -> b -> (a -> b) -> Maybe a -> b foob :: forall a b. (b -> b) -> b -> (a -> b) -> Maybe a -> b .

Un punto di confusione : potreste sentire che quando omettete il forall da un tipo in realtà è ancora implicitamente lì. ( dalla risposta di Norman: “normalmente queste lingue omettono la forall da tipi polimorfi” ). Questa affermazione è corretta, ma si riferisce agli altri usi di forall e non all’uso di ScopedTypeVariables .

Posizione-n-Tipi:

Iniziamo con mayb :: b -> (a -> b) -> Maybe a -> b è equivalente a mayb :: forall a b. b -> (a -> b) -> Maybe a -> b mayb :: forall a b. b -> (a -> b) -> Maybe a -> b , tranne quando è abilitato ScopedTypeVariables .

Ciò significa che funziona per ogni b .

Diciamo che vuoi fare qualcosa di simile.

 ghci> let putInList x = [x] ghci> liftTup putInList (5, "Blah") ([5], ["Blah"]) 

Quale deve essere il tipo di questo liftTup ? È liftTup :: (forall x. x -> fx) -> (a, b) -> (fa, fb) . Per capire perché, proviamo a codificarlo:

 ghci> let liftTup liftFunc (a, b) = (liftFunc a, liftFunc b) ghci> liftTup (\x -> [x]) (5, "Hello") No instance for (Num [Char]) ... ghci> -- huh? ghci> :t liftTup liftTup :: (t -> t1) -> (t, t) -> (t1, t1) 

“Hmm .. perché GHC deduce che la tupla deve contenere due dello stesso tipo? Diciamo che non devono essere”

 -- test.hs liftTup :: (x -> fx) -> (a, b) -> (fa, fb) liftTup liftFunc (t, v) = (liftFunc t, liftFunc v) ghci> :l test.hs Couldnt match expected type 'x' against inferred type 'b' ... 

Hmm. quindi qui ghc non ci permette di applicare liftFunc su v perché v :: b e liftFunc vogliono una x . Vogliamo davvero che la nostra funzione ottenga una funzione che accetti qualsiasi x ansible!

 {-# LANGUAGE RankNTypes #-} liftTup :: (forall x. x -> fx) -> (a, b) -> (fa, fb) liftTup liftFunc (t, v) = (liftFunc t, liftFunc v) 

Quindi non è liftTup che funziona per tutti x , è la funzione che ottiene che fa.

Quantificazione esistenziale:

Usiamo un esempio:

 -- test.hs {-# LANGUAGE ExistentialQuantification #-} data EQList = forall a. EQList [a] eqListLen :: EQList -> Int eqListLen (EQList x) = length x ghci> :l test.hs ghci> eqListLen $ EQList ["Hello", "World"] 2 

Com’è diverso da Rank-N-Types?

 ghci> :set -XRankNTypes ghci> length (["Hello", "World"] :: forall a. [a]) Couldnt match expected type 'a' against inferred type '[Char]' ... 

Con Rank-N-Types, forall a significa che la tua espressione deve adattarsi a tutti i possibili a . Per esempio:

 ghci> length ([] :: forall a. [a]) 0 

Una lista vuota funziona come una lista di qualsiasi tipo.

Quindi con la quantificazione esistenziale, per definizione nelle definizioni dei data significa che il valore contenuto può essere di qualsiasi tipo adatto, non che deve essere di tutti i tipi adatti.

Qualcuno può spiegare completamente la parola chiave forall in chiaro, semplice inglese?

No. (Beh, forse Don Stewart può.)

Ecco le barriere a una spiegazione semplice e chiara o forall :

  • È un quantificatore. Hai a avere almeno un po ‘di logica (calcolo dei predicati) per aver visto un quantificatore universale o esistenziale. Se non hai mai visto il calcolo dei predicati o non ti senti a tuo agio con i quantificatori (e ho visto studenti durante gli esami di qualifica di dottorato che non sono a loro agio), allora per te non c’è una spiegazione facile di forall .

  • È un quantificatore di tipo . Se non hai visto il sistema F e ti sei allenato a scrivere dei tipi polimorfi, scoprirai che tutti ti confondono. L’esperienza con Haskell o ML non è sufficiente, perché normalmente queste lingue omettono la forall da tipi polimorfi. (Nella mia mente, questo è un errore di progettazione linguistica).

  • In Haskell in particolare, forall viene usato in modi che trovo confusi. (Non sono un teorico di tipo, ma il mio lavoro mi mette in contatto con molta teoria dei tipi, e mi sento abbastanza a mio agio.) Per me, la principale fonte di confusione è che forall viene usato per codificare un tipo che io stesso preferirei scrivere con exists . È giustificato da un po ‘complicato tipo di isomorfismo che coinvolge quantificatori e frecce, e ogni volta che voglio capirlo, devo cercare le cose e risolvere da solo l’isomorfismo.

    Se non ti senti a tuo agio con l’idea dell’isomorfismo di tipo, o se non hai alcuna pratica per pensare agli isomorfismi di tipo, questo uso di forall ti ostacolerà.

  • Mentre il concetto generale di forall è sempre lo stesso (vincolante per introdurre una variabile di tipo), i dettagli dei diversi usi possono variare in modo significativo. L’inglese informale non è un ottimo strumento per spiegare le variazioni. Per capire veramente cosa sta succedendo, hai bisogno di un po ‘di matematica. In questo caso la matematica pertinente può essere trovata nel testo introduttivo di Benjamin Pierce, Tipi e linguaggi di programmazione , che è un ottimo libro.

Per quanto riguarda i tuoi esempi particolari,

  • runST dovrebbe farti male alla testa. I tipi di rango più elevato (tutti a sinistra di una freccia) si trovano raramente in natura. Vi incoraggio a leggere il documento che ha introdotto runST : “Lazy Functional State Threads” . Questo è davvero un buon documento, e ti darà un’intuizione molto migliore per il tipo di runST in particolare e per i tipi di rango superiore in generale. La spiegazione richiede diverse pagine, è molto ben fatta, e non ho intenzione di provare a condensare qui.

  • Prendere in considerazione

     foo :: (forall a. a -> a) -> (Char,Bool) bar :: forall a. ((a -> a) -> (Char, Bool)) 

    Se chiamo bar , posso semplicemente scegliere qualsiasi tipo che mi piace, e posso passargli una funzione da tipo a per digitare a . Ad esempio, posso passare la funzione (+1) o la funzione reverse . Puoi pensare al forall come a dire “Ora posso scegliere il tipo”. (La parola tecnica per scegliere il tipo è un’istanza .)

    Le restrizioni sulla chiamata di foo sono molto più stringenti: l’argomento di foo deve essere una funzione polimorfica. Con quel tipo, le uniche funzioni che posso passare a foo sono id o una funzione che diverge sempre o errori, come undefined . Il motivo è che con foo , forall è a sinistra della freccia, così come il chiamante di foo non riesco a scegliere ciò che è, piuttosto è l’ implementazione di foo che arriva a scegliere ciò che è. Poiché forall è a sinistra della freccia, piuttosto che sopra la freccia come in bar , l’istanziazione avviene nel corpo della funzione piuttosto che nel sito di chiamata.

Riepilogo: una spiegazione completa della parola chiave forall richiede la matematica e può essere compresa solo da qualcuno che ha studiato la matematica. Anche le spiegazioni parziali sono difficili da capire senza matematica. Ma forse le mie spiegazioni parziali e non matematiche aiutano un po ‘. Vai a leggere Launchbury e Peyton Jones su runST !


Addendum: gergo “sopra”, “sotto”, “a sinistra di”. Questi non hanno nulla a che fare con i modi testuali che i tipi sono scritti e tutto ciò che ha a che fare con gli alberi di syntax astratta. Nella syntax astratta, un forall prende il nome di una variabile di tipo, e poi c’è un tipo completo “sotto” il forall. Una freccia accetta due tipi (argomento e tipo di risultato) e forma un nuovo tipo (il tipo di funzione). Il tipo di argomento è “alla sinistra di” la freccia; è il figlio sinistro della freccia nell’albero della syntax astratta.

Esempi:

  • A forall a . [a] -> [a] forall a . [a] -> [a] , il forall è sopra la freccia; ciò che è a sinistra della freccia è [a] .

  • In

     forall nfex . (forall ex . nex -> f -> Fact xf) -> Block nex -> f -> Fact xf 

    il tipo tra parentesi sarebbe chiamato “un forall a sinistra di una freccia”. (Sto usando tipi come questo in un ottimizzatore su cui sto lavorando.)

La mia risposta originale:

Qualcuno può spiegare completamente la parola chiave forall in chiaro, semplice inglese

Come indica Norman, è molto difficile dare una chiara, chiara spiegazione inglese di un termine tecnico dalla teoria dei tipi. Stiamo tutti provando però.

C’è solo una cosa da ricordare su “forall”: lega i tipi a un certo scopo . Una volta capito, tutto è abbastanza facile. È l’equivalente di “lambda” (o una forma di “let”) a livello di tipo – Norman Ramsey usa la nozione di “sinistra” / “sopra” per trasmettere questo stesso concetto di scopo nella sua eccellente risposta .

La maggior parte degli usi di “forall” sono molto semplici e li potete trovare introdotti nel Manuale per l’utente di GHC, S7.8 ., In particolare l’eccellente S7.8.5 sulle forms annidate di “forall”.

In Haskell, di solito lasciamo il binder per i tipi, quando il tipo è universalmente quanitificato, in questo modo:

 length :: forall a. [a] -> Int 

è equivalente a:

 length :: [a] -> Int 

Questo è tutto.

Poiché ora puoi associare le variabili di tipo a un determinato ambito, puoi avere ambiti diversi dal livello principale (” universalmente quantificato “), come il tuo primo esempio, in cui la variabile di tipo è visibile solo all’interno della struttura dati. Questo consente tipi nascosti (” tipi esistenziali “). Oppure possiamo avere un nidificazione arbitraria di associazioni (“tipi di rango N”).

Per comprendere a fondo i sistemi di tipi, dovrai imparare un po ‘di gergo tecnico. Questa è la natura dell’informatica. Tuttavia, gli usi semplici, come sopra, dovrebbero essere in grado di essere afferrati intuitivamente, per analogia con ‘let’ sul livello di valore. Una grande introduzione è Launchbury e Peyton Jones .

Sono densamente zeppi di supposizioni secondo cui ho letto le ultime novità in qualsiasi ramo della matematica discreta, della teoria delle categorie o dell’algebra astratta è popolare questa settimana. (Se non leggerò mai le parole “consulta il documento per i dettagli sull’implementazione” di nuovo, sarà troppo presto.)

Ehm, e che dire della semplice logica del primo ordine? forall è chiaramente in riferimento alla quantificazione universale , e in quel contesto il termine esistenziale ha anche più senso, anche se sarebbe meno imbarazzante se esistesse una parola chiave exists . La quantificazione è effettivamente universale o esistenziale dipende dal posizionamento del quantificatore rispetto al punto in cui le variabili vengono utilizzate su quale lato di una freccia di funzione e tutto ciò è un po ‘confuso.

Quindi, se ciò non aiuta, o se semplicemente non ti piace la logica simbolica, da una prospettiva di programmazione più funzionale, puoi pensare alle variabili di tipo come parametri di tipo (impliciti) alla funzione. Le funzioni che assumono parametri di tipo in questo senso sono tradizionalmente scritte usando un lambda maiuscola per qualsiasi motivo, che scriverò qui come /\ .

Quindi, considera la funzione id :

 id :: forall a. a -> a id x = x 

Possiamo riscriverlo come lambda, spostando il “parametro di tipo” fuori dalla firma del tipo e aggiungendo annotazioni di tipo in linea:

 id = /\a -> (\x -> x) :: a -> a 

Ecco la stessa cosa fatta per const :

 const = /\ab -> (\xy -> x) :: a -> b -> a 

Quindi la tua funzione bar potrebbe essere qualcosa del genere:

 bar = /\a -> (\f -> ('t', True)) :: (a -> a) -> (Char, Bool) 

Si noti che il tipo della funzione assegnata alla bar come argomento dipende dal parametro di tipo della bar . Considera se hai qualcosa come questo, invece:

 bar2 = /\a -> (\f -> (f 't', True)) :: (a -> a) -> (Char, Bool) 

Qui bar2 sta applicando la funzione a qualcosa di tipo Char , quindi dando a bar2 qualsiasi parametro di tipo diverso da Char causerà un errore di tipo.

D’altra parte, ecco come potrebbe essere il foo :

 foo = (\f -> (f Char 't', f Bool True)) 

A differenza della bar , foo realtà non prende affatto alcun tipo di parametro! Prende una funzione che a sua volta prende un parametro di tipo, quindi applica quella funzione a due tipi diversi .

Quindi, quando vedi un forall in una signature di tipo, pensalo come un’espressione lambda per le firme dei tipi . Proprio come i lambda regolari, lo scope di forall estende il più a destra ansible, fino a racchiudere le parentesi, e proprio come le variabili legate in un lambda regolare, le variabili di tipo legate da un forall sono solo nell’ambito dell’espressione quantificata.


Post scriptum : Forse potresti chiedertelo – ora che stiamo pensando a funzioni che assumono parametri di tipo, perché non possiamo fare qualcosa di più interessante con quei parametri piuttosto che inserirli in un tipo di firma? La risposta è che possiamo!

Una funzione che mette insieme le variabili di tipo con un’etichetta e restituisce un nuovo tipo è un costruttore di tipi , che è ansible scrivere in questo modo:

 Either = /\ab -> ... 

Ma avremmo bisogno di una notazione completamente nuova, perché il modo in cui un tale tipo è scritto, come ad esempio Either ab , è già indicativo di “applicare la funzione a questi parametri”.

D’altra parte, una funzione che tipo “pattern corrisponde” ai suoi parametri tipo, restituendo valori diversi per tipi diversi, è un metodo di una class di tipi . Una leggera espansione alla mia /\ syntax sopra suggerisce qualcosa del genere:

 fmap = /\ fab -> case f of Maybe -> (\gx -> case x of Just y -> Just bgy Nothing -> Nothing b) :: (a -> b) -> Maybe a -> Maybe b [] -> (\gx -> case x of (y:ys) -> gy : fmap [] abg ys [] -> [] b) :: (a -> b) -> [a] -> [b] 

Personalmente, penso di preferire la syntax effettiva di Haskell …

Una funzione che “pattern corrisponde” ai suoi parametri tipo e restituisce un tipo arbitrario, esistente è una famiglia tipo o una dipendenza funzionale – nel primo caso, sembra già molto simile a una definizione di funzione.

Ecco una spiegazione rapida e sporca in termini chiari che probabilmente avrai già familiarità con.

La parola chiave forall viene in realtà usata solo in un modo in Haskell. Significa sempre la stessa cosa quando lo vedi.

Quantificazione universale

Un tipo universalmente quantificato è un tipo di modulo per tutto forall a. fa forall a. fa . Un valore di quel tipo può essere pensato come una funzione che prende un tipo a come argomento e restituisce un valore di tipo fa . Tranne che in Haskell questi argomenti di tipo sono passati implicitamente dal sistema dei tipi. Questa “funzione” deve darti lo stesso valore indipendentemente dal tipo che riceve, quindi il valore è polimorfico .

Ad esempio, considera il tipo per tutto forall a. [a] forall a. [a] . Un valore di quel tipo prende un altro tipo a e ti restituisce un elenco di elementi dello stesso tipo a . C’è solo una ansible implementazione, ovviamente. Dovrebbe darti la lista vuota perché potrebbe essere assolutamente di qualsiasi tipo. La lista vuota è l’unico valore di lista che è polimorfico nel suo tipo di elemento (poiché non ha elementi).

O il tipo per tutto forall a. a -> a forall a. a -> a . Il chiamante di tale funzione fornisce sia un tipo a che un valore di tipo a . L’implementazione deve quindi restituire un valore dello stesso tipo a . C’è solo una ansible implementazione di nuovo. Dovrebbe restituire lo stesso valore che è stato dato.

Quantificazione esistenziale

Un tipo esistenzialmente quantificato avrebbe la forma exists a. fa exists a. fa , se Haskell supportava quella notazione. Un valore di quel tipo può essere pensato come una coppia (o un “prodotto”) costituito da un tipo a e un valore di tipo fa .

Ad esempio, se hai un valore di tipo exists a. [a] exists a. [a] , hai una lista di elementi di qualche tipo. Potrebbe essere di qualsiasi tipo, ma anche se non sai cosa sia, ci sono molte cose che potresti fare in una lista del genere. È ansible invertire la procedura oppure è ansible contare il numero di elementi o eseguire qualsiasi altra operazione di elenco che non dipenda dal tipo di elementi.

OK, quindi aspetta un minuto. Perché Haskell usa forall per denotare un tipo “esistenziale” come il seguente?

 data ShowBox = forall s. Show s => SB s 

Può essere fonte di confusione, ma in realtà sta descrivendo il tipo di costruttore di dati SB :

 SB :: forall s. Show s => s -> ShowBox 

Una volta costruito, puoi pensare a un valore di tipo ShowBox come composto da due cose. È un tipo s insieme con un valore di tipo s . In altre parole, è un valore di un tipo quantificato esistenzialmente. ShowBox potrebbe davvero essere scritto come exists s. Show s => s exists s. Show s => s , se Haskell supportava quella notazione.

runST e amici

Detto questo, come sono questi diversi?

 foo :: (forall a. a -> a) -> (Char,Bool) bar :: forall a. ((a -> a) -> (Char, Bool)) 

Facciamo prima bar . Prende un tipo a e una funzione di tipo a -> a , e produce un valore di tipo (Char, Bool) . Potremmo scegliere Int come a e dargli una funzione di tipo Int -> Int per esempio. Ma foo è diverso. Richiede che l’implementazione di foo sia in grado di passare qualsiasi tipo voglia alla funzione che gli diamo. Quindi l’unica funzione che potremmo ragionevolmente dargli è id .

Ora dovremmo essere in grado di affrontare il significato del tipo di runST :

 runST :: forall a. (forall s. ST sa) -> a 

Quindi runST deve essere in grado di produrre un valore di tipo a , indipendentemente dal tipo che diamo come a . Per fare ciò, ha bisogno di un argomento di tipo forall s. ST sa forall s. ST sa che sotto il cofano è solo una funzione di tipo forall s. s -> (a, s) forall s. s -> (a, s) . Quella funzione deve quindi essere in grado di produrre un valore di tipo (a, s) indipendentemente dal tipo di implementazione di runST decide di fornire come s .

OK, allora? Il vantaggio è che questo pone un vincolo al chiamante di runST in quanto il tipo a non può coinvolgere affatto il tipo s . Ad esempio, non puoi passare un valore di tipo ST s [s] . Ciò significa in pratica che l’implementazione di runST è libera di eseguire la mutazione con il valore di tipo s . Il sistema di tipi garantisce che questa mutazione sia locale all’implementazione di runST .

Il tipo di runST è un esempio di un tipo polimorfo di rango 2 poiché il tipo del suo argomento contiene un quantificatore forall . Il tipo di foo sopra è anche di rango 2. Un ordinario tipo polimorfico, come quello di bar , è rank-1, ma diventa rank-2 se i tipi di argomenti sono richiesti per essere polimorfici, con il loro proprio quantificatore. E se una funzione accetta argomenti di rank-2, il suo tipo è rank-3 e così via. In generale, un tipo che accetta argomenti polimorfici di rango n ha rank n + 1 .

Il motivo per cui ci sono diversi usi di questa parola chiave è che è effettivamente utilizzato in almeno due estensioni di sistema di tipo diverso: tipi di rango superiore ed elementi esistenziali.

Probabilmente è meglio leggere e capire queste due cose separatamente, piuttosto che cercare di ottenere una spiegazione del perché “forall” sia un bit di syntax appropriato in entrambi allo stesso tempo.

Qualcuno può spiegare completamente la parola chiave di forall in chiaro, semplice inglese (o, se esiste da qualche parte, indicare una spiegazione così chiara che ho perso) che non presume che io sia un matematico intriso di gergo?

Cercherò di spiegare solo il significato e forse l’applicazione di forall nel contesto di Haskell e dei suoi sistemi di tipi.

Ma prima che tu capisca che vorrei indirizzarti a un discorso molto accessibile e piacevole di Runar Bjarnason intitolato ” Vincoli Liberare, Liberare Vincola “. Il discorso è pieno di esempi tratti da casi di utilizzo del mondo reale e di esempi in Scala per supportare questa affermazione, sebbene non faccia menzione di tutti. Proverò a spiegare la seguente prospettiva di seguito.

  CONSTRAINTS LIBERATE, LIBERTIES CONSTRAIN 

È molto importante digerire e credere a questa affermazione per procedere con la seguente spiegazione, quindi vi esorto a guardare il discorso (almeno parti di esso).

Ora un esempio molto comune, che mostra l’espressività del sistema di tipi Haskell è questa firma di tipo:

foo :: a -> a

Si dice che data questa firma di tipo, c’è solo una funzione che può soddisfare questo tipo e cioè la funzione di identity o quello che è l’ id più popolarmente conosciuto.

Nelle fasi iniziali di apprendimento di Haskell, mi sono sempre chiesto le seguenti funzioni:

 foo 5 = 6 foo True = False 

entrambi soddisfano la suddetta firma del tipo, allora perché la gente di Haskell afferma che è solo l’ id che soddisfa la firma del tipo?

Questo perché c’è un implicito per tutti nascosto nella firma del tipo. Il tipo effettivo è:

 id :: forall a. a -> a 

Quindi, ora torniamo all’affermazione: i vincoli liberano, le libertà vincolano

Traducendolo nel sistema tipo, questa affermazione diventa:

Un vincolo a livello di tipo, diventa una libertà a livello di termine

e

Una libertà a livello di tipo, diventa un vincolo a livello di termine


Cerchiamo di provare la prima affermazione:

Un vincolo a livello di testo ..

Quindi ponendo un vincolo sulla nostra firma del tipo

 foo :: (Num a) => a -> a 

diventa una libertà a livello di termine ci dà la libertà o la flessibilità di scrivere tutti questi

 foo 5 = 6 foo 4 = 2 foo 7 = 9 ... 

Lo stesso si può osservare vincolando a con qualsiasi altra class di tipografia, ecc

Quindi, ora, cosa significa questo tipo di firma: foo :: (Num a) => a -> a traduce in:

 ∃a , st a -> a, ∀a ∈ Num 

Questo è noto come quantificazione esistenziale, che si traduce in alcune istanze di a per cui una funzione quando si alimenta qualcosa di tipo a restituisce qualcosa dello stesso tipo, e tali istanze appartengono tutte all’insieme di Numeri.

Quindi possiamo vedere l’aggiunta di un vincolo (che a dovrebbe appartenere al set di Numeri), libera il livello di termine per avere più possibili implementazioni.


Ora arriviamo alla seconda affermazione e quella che porta effettivamente la spiegazione di forall :

Una libertà a livello di tipo, diventa un vincolo a livello di termine

Quindi ora liberiamo la funzione a livello di tipo:

 foo :: forall a. a -> a 

Ora questo si traduce in:

 ∀a , a -> a 

il che significa che l’implementazione di questo tipo di firma dovrebbe essere tale che sia a -> a per tutte le circostanze.

Quindi ora inizia a costringerci al livello del termine. Non possiamo più scrivere

 foo 5 = 7 

perché questa implementazione non sarebbe soddisfacente se mettessimo un Bool . a può essere un Char o un [Char] o un tipo di dati personalizzato. In tutte le circostanze dovrebbe restituire qualcosa del tipo simile. Questa libertà a livello di tipo è ciò che è noto come quantificazione universale e l’unica funzione che può soddisfare questo è

 foo a = a 

che è comunemente nota come funzione di identity


Quindi forall è una liberty a livello di tipo, il cui scopo è di constrain il livello di termine a una particolare implementazione.

Come è esistenziale esistenziale?

Con la quantificazione esistenziale, tutte data definizioni dei data indicano che il valore contenuto può essere di qualsiasi tipo adatto, non che deve essere di tutti i tipi adatti. – la risposta di yachiru

Una spiegazione del perché tutte data definizioni dei data sono isomorfe a (exists a. a) (pseudo-Haskell) possono essere trovate in “Haskell / Esistenzialmente quantificati tipi” di wikibooks .

Quello che segue è un breve riassunto letterale:

 data T = forall a. MkT a -- an existential datatype MkT :: forall a. a -> T -- the type of the existential constructor 

Quando MkT x / MkT x , qual è il tipo di x ?

 foo (MkT x) = ... -- -- what is the type of x? 

x può essere di qualsiasi tipo (come indicato nel forall ), e quindi il suo tipo è:

 x :: exists a. a -- (pseudo-Haskell) 

Pertanto, i seguenti sono isomorfi:

 data T = forall a. MkT a -- an existential datatype data T = MkT (exists a. a) -- (pseudo-Haskell) 

forall significa per tutti

La mia semplice interpretazione di tutto ciò è che ” forall significa veramente ‘per tutti'”. Un’importante distinzione da fare è l’impatto di forall sull’applicazione di definizione contro funzione.

Un forall significa che la definizione del valore o della funzione deve essere polimorfica.

Se la cosa che viene definita è un valore polimorfico, significa che il valore deve essere valido per tutti i a , che è piuttosto restrittivo.

Se la cosa che viene definita è una funzione polimorfica, allora significa che la funzione deve essere valida per tutto l’a adatto, il che non è così restrittivo perché solo perché la funzione è polimorfica non significa che il parametro applicato deve essere polimorfico. Cioè, se la funzione è valida per tutte le a , allora inversamente si può applicare a tale funzione. Tuttavia, il tipo di parametro può essere scelto solo una volta nella definizione della funzione.

Se un forall è all’interno del tipo di parametro della funzione (cioè, un Rank2Type ), allora significa che il parametro applicato deve essere veramente polimorfico, per essere coerente con l’idea di forall significa che la definizione è polimorfica. In questo caso, il tipo di parametro può essere scelto più volte nella definizione della funzione ( “ed è scelto dall’implementazione della funzione”, come indicato da Norman )

Pertanto, la ragione per cui data definizioni di data esistenziali consentono qualsiasi a è perché il costruttore di dati è una funzione polimorfica:

 MkT :: forall a. a -> T 

tipo di MkT :: a -> *

Il che significa che a a può essere applicato alla funzione. Al contrario, per esempio, di un valore polimorfico:

 valueT :: forall a. [a] 

tipo di valoreT :: a

Il che significa che la definizione di valueT deve essere polimorfica. In questo caso, valueT può essere definito come lista vuota [] di tutti i tipi.

 [] :: [t] 

differenze

Anche se il significato per forall è coerente in ExistentialQuantification e RankNType , gli elementi esistenziali hanno una differenza in quanto il costruttore di data può essere utilizzato nella corrispondenza dei modelli. Come documentato nella guida dell’utente ghc :

Quando la corrispondenza del modello, ogni corrispondenza di modello introduce un nuovo tipo distinto per ogni variabile di tipo esistenziale. Questi tipi non possono essere unificati con nessun altro tipo, né possono uscire dall’ambito della corrispondenza del modello.