Que fait le mot clé `forall` dans Haskell / GHC?

Je commence à comprendre comment le mot-clé forall est utilisé dans les “types existentiels” comme ceci:

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

Ceci est seulement un sous-ensemble, cependant, de la façon dont tout est utilisé et je ne peux tout simplement pas me concentrer sur son utilisation dans des choses comme ceci:

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

Ou expliquer pourquoi ils sont différents:

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

Ou tout le matériel de RankNTypes

J’ai tendance à préférer un anglais clair, sans jargon, plutôt que le type de langage qui est normal dans les environnements académiques. La plupart des explications que je tente de lire à ce sujet (celles que je peux trouver dans les moteurs de recherche) posent les problèmes suivants:

  1. Ils sont incomplets. Ils expliquent une partie de l’utilisation de ce mot-clé (comme les “types existentiels”), ce qui me rend heureux jusqu’à ce que je lise du code qui l’utilise de manière complètement différente (comme runST , foo et bar ci-dessus).
  2. Ils sont densément remplis d’hypothèses que j’ai lues au plus tard dans le domaine des mathématiques discrètes, de la théorie des catégories ou de l’algèbre abstraite. (Si je ne lis jamais les mots “consultez le document pour plus de détails sur la mise en œuvre”, ce sera trop tôt.)
  3. Ils sont écrits d’une manière qui transforme souvent même des concepts simples en une grammaire et une sémantique tortueuses et tordues.

Alors…

Sur la question réelle. Quelqu’un peut-il expliquer complètement le mot-clé forall en clair, en anglais clair (ou, s’il existe quelque part, indiquer une explication si claire que j’ai ratée) qui ne suppose pas que je suis un mathématicien imprégné du jargon?


Edité pour append:

Il y avait deux réponses distinctes parmi celles de qualité supérieure ci-dessous, mais malheureusement je ne peux en choisir qu’une meilleure. La réponse de Norman était détaillée et utile, expliquant les choses d’une manière qui montrait certains des fondements théoriques de forall et en même temps me montrant certaines de ses implications pratiques. La réponse de yairchu couvre un domaine que personne d’autre n’a mentionné (les variables de type scoped) et illustre tous les concepts avec du code et une session GHCi. S’il était possible de sélectionner les deux mieux, je le ferais. Malheureusement, je ne peux pas et, après avoir examiné attentivement les deux réponses, j’ai décidé que Yairchu dépassait légèrement celle de Norman à cause du code illustratif et de l’explication jointe. C’est un peu injuste, cependant, parce que j’avais vraiment besoin des deux réponses pour comprendre cela, au point que tout cela ne me laisse pas un sentiment d’appréhension quand je le vois dans une signature de type.

    Commençons par un exemple de code:

     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 

    Ce code ne comstack pas (erreur de syntaxe) en clair Haskell 98. Il nécessite une extension pour prendre en charge le mot clé forall .

    Fondamentalement, il y a 3 utilisations communes différentes pour le mot-clé forall (ou du moins, semble-t- il), et chacune a sa propre extension Haskell: ScopedTypeVariables , RankNTypes / Rank2Types , ExistentialQuantification .

    Le code ci-dessus n’obtient pas d’erreur de syntaxe avec l’un de ceux activés, mais uniquement les contrôles de type avec ScopedTypeVariables activés.

    Variables de type Scoped:

    Les variables de type Scoped aident à spécifier les types de code dans les clauses where . Cela rend le b dans val :: b le même que le b dans 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 point confus : vous pouvez entendre que lorsque vous omettez le forall d’un type, il est toujours implicitement là. (d’ après la réponse de Norman: “normalement, ces langues omettent le forall des types polymorphes” ). Cette affirmation est correcte, mais elle fait référence aux autres utilisations de forall et non à l’utilisation de ScopedTypeVariables .

    Rank-N-Types:

    Commençons par mayb :: b -> (a -> b) -> Maybe a -> b est équivalent à mayb :: forall a b. b -> (a -> b) -> Maybe a -> b mayb :: forall a b. b -> (a -> b) -> Maybe a -> b , sauf lorsque ScopedTypeVariables est activé.

    Cela signifie que cela fonctionne pour tous les a et b .

    Disons que vous voulez faire quelque chose comme ça.

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

    Quel doit être le type de ce liftTup ? C’est liftTup :: (forall x. x -> fx) -> (a, b) -> (fa, fb) . Pour voir pourquoi, essayons de le coder:

     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 .. pourquoi GHC en déduit que le tuple doit en contenir deux du même type? Disons qu’ils ne doivent pas l’être”

     -- 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. donc, ghc ne nous permet pas d’appliquer liftFunc sur v car v :: b et liftFunc veulent un x . Nous voulons vraiment que notre fonction obtienne une fonction qui accepte tous les x possibles!

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

    Donc, ce n’est pas un liftTup qui fonctionne pour tous les x , c’est la fonction qui le fait.

    Quantification Existentielle:

    Utilisons un exemple:

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

    En quoi est-ce différent de Rank-N-Types?

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

    Avec Rank-N-Types, forall a signifiait que votre expression devait correspondre à tous les possibles. Par exemple:

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

    Une liste vide fonctionne comme une liste de tout type.

    Ainsi, avec la quantification des existentielles, toutes data définitions de data signifient que la valeur contenue peut être de tout type approprié, et non pas de tous les types appropriés.

    Quelqu’un peut-il expliquer complètement le mot-clé forall en anglais clair et clair?

    Non. (Peut-être que Don Stewart peut.)

    Voici les obstacles à une explication simple et claire:

    • C’est un quantificateur. Vous devez avoir au moins un peu de logique (calcul de prédicat) pour avoir vu un quantificateur universel ou existentiel. Si vous n’avez jamais vu de calcul de prédicats ou n’êtes pas à l’aise avec les quantificateurs (et j’ai vu des étudiants lors d’examens de doctorat qui ne sont pas à l’aise), il n’y a pas d’explication facile pour vous.

    • C’est un quantificateur de type . Si vous n’avez pas encore vu System F et que vous avez commencé à écrire des types polymorphes, vous allez être forall dérouté. L’expérience de Haskell ou de ML n’est pas suffisante, car ces langages omettent normalement la forall des types polymorphes. (Dans mon esprit, ceci est une erreur de conception de langage.)

    • Dans Haskell en particulier, tout est utilisé d’une manière que je trouve déroutante. (Je ne suis pas un théoricien du type, mais mon travail me met en contact avec beaucoup de théorie des types, et je suis assez à l’aise avec cela.) Pour moi, la principale source de confusion est que forall est utilisé pour encoder un type que je préfère moi-même écrire avec exists . C’est justifié par un peu de type d’isomorphisme impliquant des quantificateurs et des flèches, et à chaque fois que je veux le comprendre, je dois moi-même rechercher et trouver l’isomorphisme.

      Si vous n’êtes pas à l’aise avec l’idée d’isomorphisme de type, ou si vous n’avez pas l’habitude de penser aux isomorphismes de type, cette utilisation de forall va vous contrecarrer.

    • Bien que le concept général de forall soit toujours le même (liaison pour introduire une variable de type), les détails des différentes utilisations peuvent varier considérablement. L’anglais informel n’est pas un très bon outil pour expliquer les variations. Pour bien comprendre ce qui se passe, il faut des mathématiques. Dans ce cas, les mathématiques pertinentes peuvent être trouvées dans le texte d’introduction de Benjamin Pierce, Types et langages de programmation , qui est un très bon livre.

    Quant à vos exemples particuliers,

    • runST devrait vous faire mal à la tête. Les types de rang supérieur (à gauche de la flèche) sont rarement trouvés dans la nature. Je vous encourage à lire le document qui présente runST : “Lazy Functional State Threads” . C’est un très bon papier, et cela vous donnera une bien meilleure intuition pour le type de runST en particulier et pour les types de rang supérieur en général. L’explication prend plusieurs pages, c’est très bien fait et je ne vais pas essayer de le condenser ici.

    • Considérer

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

      Si j’appelle bar , je peux simplement choisir n’importe quel type de a que j’aime, et je peux lui passer une fonction du type a pour taper a . Par exemple, je peux passer la fonction (+1) ou la fonction reverse . Vous pouvez penser au forall comme disant “je peux choisir le type maintenant”. (Le mot technique pour choisir le type est instancié .)

      Les ressortingctions sur l’appel de foo sont beaucoup plus ssortingctes: l’argument de foo doit être une fonction polymorphe. Avec ce type, les seules fonctions que je peux transmettre à foo sont id ou une fonction qui diverge ou se trompe toujours, comme undefined . La raison en est que, avec foo , le forall trouve à gauche de la flèche, donc comme l’appelant de foo je ne peux pas choisir ce a c’est – plutôt l’ implémentation de foo qui peut choisir ce qu’est a . Comme forall trouve à gauche de la flèche, et non au-dessus de la flèche comme dans la bar , l’instanciation a lieu dans le corps de la fonction plutôt que sur le site de l’appel.

    Résumé: Une explication complète du mot-clé forall nécessite des mathématiques et ne peut être comprise que par une personne ayant étudié les mathématiques. Même les explications partielles sont difficiles à comprendre sans maths. Mais peut-être que mes explications partielles, non mathématiques, aident un peu. Allez lire Launchbury et Peyton Jones sur runST !


    Addendum: Jargon “ci-dessus”, “ci-dessous”, “à gauche de”. Celles-ci n’ont rien à voir avec les manières textuelles d’ écrire et tout ce qui concerne les arbres de syntaxe abstraite. Dans la syntaxe abstraite, un forall prend le nom d’une variable de type, puis il y a un type complet “sous” le forall. Une flèche prend deux types (argument et type de résultat) et forme un nouveau type (le type de fonction). Le type d’argument est “à gauche de” la flèche; c’est l’enfant gauche de la flèche dans l’arbre de syntaxe abstraite.

    Exemples:

    • Dans tout forall a . [a] -> [a] forall a . [a] -> [a] , le forall est au-dessus de la flèche; ce qui est à gauche de la flèche est [a] .

    • Dans

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

      le type entre parenthèses serait appelé “un forall à gauche d’une flèche”. (J’utilise des types comme celui-ci dans un optimiseur sur lequel je travaille.)

    Ma réponse originale:

    Quelqu’un peut-il expliquer complètement le mot clé forall en anglais clair et clair?

    Comme l’indique Norman, il est très difficile de donner une explication claire et claire en anglais d’un terme technique de la théorie des types. Nous essayons tous cependant.

    Il n’y a qu’une seule chose à retenir à propos de «forall»: il lie les types à une certaine scope . Une fois que vous avez compris cela, tout est assez facile. C’est l’équivalent de «lambda» (ou une forme de «let») au niveau du type – Norman Ramsey utilise la notion de «gauche» / «au-dessus» pour transmettre ce même concept de scope dans son excellente réponse .

    La plupart des utilisations de ‘forall’ sont très simples et vous pouvez les trouver dans le manuel utilisateur GHC, S7.8 ., En particulier l’excellent S7.8.5 sur les formes nestedes de ‘forall’.

    Dans Haskell, nous oublions généralement le classeur pour les types, lorsque le type est universellement quanitifié, comme ceci:

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

    est équivalent à:

     length :: [a] -> Int 

    C’est tout.

    Comme vous pouvez maintenant lier des variables de type à une certaine étendue, vous pouvez avoir des étendues autres que le niveau supérieur (” universellement quantifié “), comme votre premier exemple, où la variable de type est uniquement visible dans la structure de données. Cela permet des types cachés (” types existentiels “). Ou nous pouvons avoir une imbrication arbitraire de liaisons (“types de rang N”).

    Pour bien comprendre les systèmes de types, vous devrez apprendre le jargon. C’est la nature de l’informatique. Cependant, des utilisations simples, comme ci-dessus, devraient pouvoir être saisies intuitivement, par analogie avec «let» au niveau de la valeur. Launchbury et Peyton Jones sont une excellente introduction.

    Ils sont densément remplis d’hypothèses que j’ai lues au plus tard dans le domaine des mathématiques discrètes, de la théorie des catégories ou de l’algèbre abstraite. (Si je ne lis jamais les mots “consultez le document pour plus de détails sur la mise en œuvre”, ce sera trop tôt.)

    Euh, et la simple logique du premier ordre? forall est assez clairement en référence à la quantification universelle et, dans ce contexte, le terme existentiel a également plus de sens, même s’il serait moins gênant s’il existait un mot-clé exists . Que la quantification soit effectivement universelle ou existentielle dépend du placement du quantificateur par rapport à l’endroit où les variables sont utilisées de quel côté d’une flèche de fonction et tout cela est un peu confus.

    Donc, si cela ne vous aide pas ou si vous n’aimez pas la logique symbolique, vous pouvez considérer les variables de type comme étant simplement des parameters de type (implicites) de la fonction. Les fonctions prenant des parameters de type dans ce sens sont traditionnellement écrites en utilisant un lambda majuscule pour une raison quelconque, que je vais écrire ici sous la forme /\ .

    Alors, considérez la fonction id :

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

    On peut le réécrire en lambda, en déplaçant le “paramètre de type” de la signature de type et en ajoutant des annotations de type en ligne:

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

    Voici la même chose à faire pour const :

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

    Donc, votre fonction de bar pourrait être quelque chose comme ceci:

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

    Notez que le type de la fonction donnée à bar en tant qu’argument dépend du paramètre type de la bar . Considérez plutôt si vous aviez quelque chose comme ça:

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

    Ici, bar2 applique la fonction à quelque chose de type Char , par conséquent, donner à bar2 un paramètre de type autre que Char provoquera une erreur de type.

    D’un autre côté, voici à quoi pourrait ressembler foo :

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

    Contrairement à la bar , foo ne prend aucun paramètre de type du tout! Il prend une fonction qui prend ellemême un paramètre de type, puis applique cette fonction à deux types différents .

    Donc, quand vous voyez un forall dans une signature de type, pensez-y simplement comme une expression lambda pour les signatures de type . Tout comme les lambdas ordinaires, la scope de forall s’étend le plus à droite possible, jusqu’à mettre entre parenthèses, et tout comme les variables liées à un lambda régulier, les variables de type liées par un forall ne sont présentes que dans l’expression quantifiée.


    Post scriptum : Peut-être pourriez-vous vous demander, maintenant que nous pensons à des fonctions prenant des parameters de type, pourquoi ne pouvons-nous pas faire quelque chose de plus intéressant avec ces parameters que de les placer dans une signature de type? La réponse est que nous pouvons!

    Une fonction qui place des variables de type avec une étiquette et renvoie un nouveau type est un constructeur de type , dans lequel vous pouvez écrire quelque chose comme ceci:

     Either = /\ab -> ... 

    Mais nous aurions besoin d’une notation complètement nouvelle, car la manière dont un tel type est écrit, comme Either ab , est déjà suggestive de “appliquer la fonction Either à ces parameters”.

    D’autre part, une fonction qui “sortinge les modèles” sur ses parameters de type, renvoyant des valeurs différentes pour différents types, est une méthode d’une classe de type . Une légère extension de ma syntaxe /\ suggère quelque chose comme ceci:

     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] 

    Personnellement, je pense que je préfère la syntaxe actuelle de Haskell …

    Une fonction qui “modèle” ses parameters de type et renvoie un type existant arbitraire est une famille de type ou une dépendance fonctionnelle – dans le premier cas, elle ressemble déjà beaucoup à une définition de fonction.

    Voici une explication rapide et grossière que vous êtes probablement familier.

    Le mot-clé forall n’est en réalité utilisé que dans un sens dans Haskell. Cela signifie toujours la même chose quand vous le voyez.

    Quantification universelle

    Un type universellement quantifié est un type de forme pour tout forall a. fa forall a. fa . Une valeur de ce type peut être considérée comme une fonction qui prend un type a comme argument et renvoie une valeur de type fa . Sauf que dans Haskell, ces arguments de type sont passés implicitement par le système de types. Cette “fonction” doit vous donner la même valeur quel que soit le type qu’elle reçoit, donc la valeur est polymorphe .

    Par exemple, considérons le type forall a. [a] forall a. [a] . Une valeur de ce type prend un autre type a et vous renvoie une liste d’éléments de ce même type a . Bien sûr, il n’ya qu’une seule mise en œuvre possible. Il faudrait vous donner la liste vide car a pourrait être n’importe quel type. La liste vide est la seule valeur de liste polymorphe dans son type d’élément (car elle ne contient aucun élément).

    Ou le type pour tout forall a. a -> a forall a. a -> a . L’appelant d’une telle fonction fournit à la fois un type a et une valeur de type a . L’implémentation doit alors renvoyer une valeur du même type a . Il n’y a qu’une seule implémentation possible à nouveau. Il devrait retourner la même valeur que celle qui lui a été donnée.

    Quantification existentielle

    Un type existentiellement quantifié aurait la forme exists a. fa exists a. fa , si Haskell supportait cette notation. Une valeur de ce type peut être considérée comme une paire (ou un “produit”) consistant en un type a et une valeur de type fa .

    Par exemple, si vous avez une valeur de type exists a. [a] exists a. [a] , vous avez une liste d’éléments de quelque type. Cela pourrait être n’importe quel type, mais même si vous ne savez pas ce que c’est, il y a beaucoup à faire pour une telle liste. Vous pouvez l’inverser ou compter le nombre d’éléments ou effectuer toute autre opération de liste qui ne dépend pas du type des éléments.

    OK, attendez une minute. Pourquoi Haskell utilise-t-il forall pour désigner un type “existentiel” comme le suivant?

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

    Cela peut être déroutant, mais cela décrit vraiment le type du constructeur de données SB :

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

    Une fois construite, vous pouvez penser à une valeur de type ShowBox composée de deux choses. C’est un type s avec une valeur de type s . En d’autres termes, c’est une valeur d’un type quantifié existentiellement. ShowBox pourrait vraiment être écrit tel ShowBox exists s. Show s => s exists s. Show s => s si Haskell supporte cette notation.

    runST et amis

    Compte tenu de cela, comment sont-ils différents?

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

    Prenons d’abord la bar . Il prend un type a et une fonction de type a -> a et produit une valeur de type (Char, Bool) . Nous pourrions choisir Int comme a et lui donner une fonction de type Int -> Int par exemple. Mais foo est différent. Cela nécessite que l’implémentation de foo puisse transmettre n’importe quel type à la fonction que nous lui donnons. Donc, la seule fonction que nous pourrions raisonnablement lui donner est id .

    Nous devrions maintenant être en mesure de runST la signification du type de runST :

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

    Ainsi, runST doit pouvoir produire une valeur de type a , quel que soit le type que nous donnons en tant a . Pour ce faire, il faut un argument de type forall s. ST sa forall s. ST sa qui sous le capot n’est qu’une fonction de type pour tous les forall s. s -> (a, s) forall s. s -> (a, s) . Cette fonction doit alors être capable de produire une valeur de type (a, s) quel que soit le type que l’implémentation de runST décide de donner comme s .

    Okay, alors quoi? L’avantage est que cela met une contrainte sur l’appelant de runST en ce que le type a ne peut pas impliquer le type s du tout. Vous ne pouvez pas lui transmettre une valeur de type ST s [s] , par exemple. En pratique, cela signifie que la mise en œuvre de runST est libre d’effectuer des mutations avec la valeur de type s . Le système de type garantit que cette mutation est locale à la mise en œuvre de runST .

    Le type de runST est un exemple de type polymorphe de rang 2 car le type de son argument contient un quantificateur forall . Le type de foo ci-dessus est également de rang 2. Un type polymorphe ordinaire, comme celui de bar , est rang-1, mais il devient rang-2 si les types d’arguments doivent être polymorphes, avec leur propre quantificateur forall . Et si une fonction prend des arguments de rang 2, alors son type est rang 3, et ainsi de suite. En général, un type qui prend des arguments polymorphes de rang n a le rang n + 1 .

    La raison pour laquelle il existe différentes utilisations de ce mot-clé est qu’il est utilisé dans au moins deux extensions de systèmes de types différents: les types de rang supérieur et les existentiels.

    Il est probablement préférable de lire et de comprendre ces deux choses séparément plutôt que d’essayer d’obtenir une explication de la raison pour laquelle «forall» est un bit de syntaxe approprié à la fois.

    Quelqu’un peut-il expliquer complètement le mot-clé forall en clair, en anglais clair (ou, s’il existe quelque part, indiquer une explication si claire que j’ai ratée) qui ne suppose pas que je suis un mathématicien imprégné du jargon?

    Je vais essayer d’expliquer juste le sens et peut-être l’application de forall dans le contexte de Haskell et de ses systèmes de type.

    Mais avant que vous compreniez que je voudrais vous diriger vers un discours très accessible et sympathique de Runar Bjarnason intitulé ” Contraintes Libérer, Libertés Constrain “. La conférence est pleine d’exemples tirés de cas d’utilisation du monde réel ainsi que d’exemples dans Scala pour soutenir cette déclaration, bien qu’elle ne mentionne pas tout. Je vais essayer d’expliquer la perspective ci-dessous.

      CONSTRAINTS LIBERATE, LIBERTIES CONSTRAIN 

    Il est très important de digérer et de croire cette déclaration pour procéder à l’explication suivante, alors je vous exhorte à regarder la conversation (au moins des parties).

    Un exemple très courant, montrant l’expressivité du système de type Haskell, est ce type de signature:

    foo :: a -> a

    On dit que compte tenu de cette signature de type, il n’existe qu’une seule fonction capable de satisfaire ce type, à savoir la fonction d’ identity ou ce qu’on appelle plus communément l’ id .

    Au début de mon apprentissage de Haskell, je me suis toujours demandé quelles étaient les fonctions suivantes:

     foo 5 = 6 foo True = False 

    ils satisfont tous deux à la signature de type ci-dessus, alors pourquoi les gens de Haskell prétendent-ils que c’est l’ id seul qui satisfait à la signature de type?

    C’est parce qu’il existe un forall implicite caché dans la signature de type. Le type actuel est:

     id :: forall a. a -> a 

    Revenons maintenant à l’énoncé suivant: Les contraintes libèrent, les libertés contraignent

    Traduire cela au système de type, cette déclaration devient:

    Une contrainte au niveau du type, devient une liberté au niveau du terme

    et

    Une liberté au niveau du type, devient une contrainte au niveau du terme


    Essayons de prouver la première déclaration:

    Une contrainte au niveau du type ..

    Donc, mettre une contrainte sur notre signature de type

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

    devient une liberté au niveau du terme nous donne la liberté ou la flexibilité d’écrire tous ces

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

    Même chose peut être observé en contraignant a avec n’importe quelle autre classe de caractères, etc.

    Alors maintenant, ce que ce type de signature: foo :: (Num a) => a -> a traduit par:

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

    Ceci est connu sous le nom de quantification existentielle, ce qui signifie qu’il existe des instances de a pour lesquelles une fonction alimentée par quelque chose de type a renvoie quelque chose du même type, et ces instances appartiennent toutes à l’ensemble de Numbers.

    Par conséquent, nous pouvons voir que l’ajout d’une contrainte (qui doit appartenir à l’ensemble des nombres) libère le niveau du terme pour qu’il ait plusieurs implémentations possibles.


    Maintenant en arrivant à la deuxième déclaration et celle qui porte réellement l’explication de forall :

    Une liberté au niveau du type, devient une contrainte au niveau du terme

    Libérons maintenant la fonction au niveau du type:

     foo :: forall a. a -> a 

    Maintenant, cela se traduit par:

     ∀a , a -> a 

    ce qui signifie que l’implémentation de cette signature de type doit être telle que a -> a pour toutes les circonstances.

    Alors maintenant, cela commence à nous contraindre au niveau du terme. Nous ne pouvons plus écrire

     foo 5 = 7 

    parce que cette implémentation ne satisferait pas si on mettait a comme un Bool . a peut être un Char ou un [Char] ou un type de données personnalisé. En toutes circonstances, il devrait renvoyer quelque chose du même type. Cette liberté au niveau du type est ce que l’on appelle la quantification universelle et la seule fonction capable de

     foo a = a 

    qui est communément appelé la fonction d’ identity


    Par conséquent, forall est une liberty au niveau du type, dont le but réel est de constrain le niveau du terme à une implémentation particulière.

    Comment est l’existentiel existentiel?

    Avec la quantification des existentielles, toutes data définitions de data signifient que la valeur contenue peut être de tout type approprié, et non pas de tous les types appropriés. – La réponse de Yachiru

    Une explication de la raison pour laquelle toutes data définitions de data sont isomorphes à (exists a. a) (pseudo-Haskell) peut être trouvée dans les “types quantifiés Haskell / Existentially” de wikibooks .

    Voici un bref résumé textuel:

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

    Lors de la mise en correspondance / déconstruction de MkT x , quel est le type de x ?

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

    x peut être n’importe quel type (comme indiqué dans le forall ), et son type est donc:

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

    Par conséquent, les éléments suivants sont isomorphes:

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

    forall signifie forall

    Mon interprétation simple de tout cela est que “tout signifie vraiment” pour tous “”. Une distinction importante à faire est l’impact de forall sur l’ application de définition par rapport à la fonction.

    Un forall signifie que la définition de la valeur ou de la fonction doit être polymorphe.

    Si la chose en cours de définition est une valeur polymorphe, cela signifie que la valeur doit être valide pour tous les a appropriés, ce qui est assez ressortingctif.

    Si la chose en cours de définition est une fonction polymorphe, cela signifie que la fonction doit être valide pour tous les a , ce qui n’est pas très ressortingctif car la fonction polymorphe ne signifie pas que le paramètre appliqué doit être polymorphe. C’est-à-dire que si la fonction est valide pour tout a , alors inversement, tout a approprié peut être appliqué à la fonction. Cependant, le type du paramètre ne peut être choisi qu’une seule fois dans la définition de la fonction.

    Si un forall est à l’intérieur du type de paramètre de la fonction (c.-à-d. Un Rank2Type ), cela signifie que le paramètre appliqué doit être vraiment polymorphe. Dans ce cas, le type du paramètre peut être choisi plus d’une fois dans la définition de la fonction ( “et est choisi par l’implémentation de la fonction”, comme le fait remarquer Norman )

    Par conséquent, la raison pour laquelle data définitions de data existentielles permettent a quelconque est que le constructeur de données est une fonction polymorphe:

     MkT :: forall a. a -> T 

    sorte de MkT :: a -> *

    Ce qui signifie que tout a peut être appliqué à la fonction. Contrairement à, disons, une valeur polymorphe:

     valueT :: forall a. [a] 

    genre de valeurT :: a

    Ce qui signifie que la définition de valueT doit être polymorphe. Dans ce cas, valueT peut être défini comme une liste vide de tous types.

     [] :: [t] 

    Différences

    Même si la signification de forall est cohérente dans ExistentialQuantification et RankNType , existentials a une différence puisque le constructeur de data peut être utilisé dans la correspondance de modèle. Comme indiqué dans le guide de l’utilisateur de ghc :

    Lors de la correspondance de modèle, chaque correspondance de modèle introduit un nouveau type distinct pour chaque variable de type existentiel. Ces types ne peuvent être unifiés avec aucun autre type, ni échapper à la scope de la correspondance de modèle.