Qu'est-ce que le mot-clé `forall` dans Haskell / GHC faire?

StackOverflow https://stackoverflow.com/questions/3071136

Question

Je commence à comprendre comment le mot-clé forall est utilisé dans ce qu'on appelle « types existentiels » comme ceci: 

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

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

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

Ou expliquer pourquoi ceux-ci sont différentes: 

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

Ou l'ensemble des trucs RankNTypes ...

J'ai tendance à préférer clair, sans jargon anglais plutôt que les types de langage qui sont normaux dans les milieux universitaires. La plupart des explications je tente de lire sur ce (ceux que je peux trouver par les moteurs de recherche) ont ces problèmes:

  1. Ils sont incomplètes. Ils expliquent une partie de l'utilisation de ce mot-clé (comme « types existentiels ») qui me fait me sentir heureux jusqu'à ce que je lis le code qui l'utilise d'une manière complètement différente (comme runST, foo et bar ci-dessus).
  2. Ils sont densément emballé avec des hypothèses que j'ai lu la dernière de quelque branche de mathématiques discrètes, théorie des catégories ou l'algèbre abstraite est populaire cette semaine. (Si je ne lis jamais les mots « consulter le journal tout pour les détails de la mise en œuvre » à nouveau, il sera trop tôt.)
  3. Ils sont écrits d'une manière qui se tournent fréquemment les concepts même simples dans la grammaire et la sémantique tordue tortueuse et fracturée.

...

Sur la question réelle. Quelqu'un peut-il expliquer complètement le mot-clé forall en anglais clair et simple (ou, si elle existe quelque part, pointez sur une telle explication claire que je l'ai manqué) qui ne suppose pas que je suis un mathématicien imprégné dans le jargon?

Edité à ajouter:

Il y avait deux stand-out des réponses de ceux de qualité supérieure ci-dessous, mais malheureusement je ne peux en choisir un comme meilleur. de réponse de Norman a été détaillé et utile , ce qui explique les choses d'une manière qui a montré quelques-uns des fondements théoriques de forall et en même temps me montrant quelques-unes des implications pratiques de celui-ci. réponse de yairchu couvrait une personne zone (autre mentionné les variables de type scope) et illustré tous les concepts avec code et une session GHCi. Se il était possible de sélectionner à la fois mieux, je le ferais. Malheureusement, je ne peux pas et, après avoir examiné les réponses de près, je l'ai décidé que yairchu dépasse légèrement ya Norman en raison du code d'illustration et l'explication ci-joint. Ceci est un peu injuste, mais, parce que vraiment je besoin à la fois des réponses à comprendre au point que forall ne me laisse pas un vague sentiment d'effroi quand je le vois dans une signature de type.

Était-ce utile?

La solution

Commençons Let avec 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 compile pas (erreur de syntaxe) dans Haskell ordinaire 98. Il faut une extension pour soutenir le mot-clé forall.

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

Le code ci-dessus ne reçoit pas une erreur de syntaxe avec l'un de ces permis, mais seulement le type de contrôles avec ScopedTypeVariables activé.

Scoped variables de type:

variables de type Scoped aide un spécifier les types de code à l'intérieur des clauses de where. Il fait la b dans val :: b le même que le b dans 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 en réalité toujours là implicitement. ( de la réponse de Norman: « normalement ces langues omettent le forall de types polymorphes "). Cette affirmation est correcte, mais il se réfère aux autres utilisations de forall, et non à l'utilisation de ScopedTypeVariables.

Classement-N-types:

Soit Commençons avec cette mayb :: b -> (a -> b) -> Maybe a -> b équivaut à 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.

Le mot Let 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 cette liftTup? Il est liftTup :: (forall x. x -> f x) -> (a, b) -> (f a, f b). Pour voir pourquoi, nous allons essayer de code, il: 

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 déduisons que le tuple doit contenir deux du même type? Raconte-moi ce qu'ils ne doivent pas être » 

-- test.hs
liftTup :: (x -> f x) -> (a, b) -> (f a, f b)
liftTup liftFunc (t, v) = (liftFunc t, liftFunc v)

ghci> :l test.hs
    Couldnt match expected type 'x' against inferred type 'b'
    ...

Hmm. donc ici GHC ne nous laisse pas appliquer liftFunc sur v parce v :: b et liftFunc veut un x. Nous voulons vraiment notre fonction pour obtenir une fonction qui accepte toute x possible! 

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

Il est liftTup pas que des œuvres pour tous x, c'est la fonction qu'il obtient qui.

Existentielle Quantification:

L'utilisation Soit 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

Comment est-ce différent de Rang-N-types? 

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

Rang-N-types, forall a signifie que votre expression doit correspondre à tous les as possibles. Par exemple: 

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

Une liste vide fonctionne comme une liste de tout type.

avec Existentielle-Quantification, foralls dans les définitions de data signifient que la valeur contenue peut être tout type approprié, pas qu'il doit être de tous les types appropriés .

Autres conseils

  

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

Non. (Eh bien, peut-être Don Stewart peut.)

Voici les obstacles à une simple explication claire ou forall:

En ce qui concerne vos exemples particuliers,

  • runST devrait faire votre mal à la tête. types de rang supérieur (forall à gauche d'une flèche) sont rarement trouvés dans la nature. Je vous encourage à lire le journal qui a introduit runST: "Lazy Threads fonctionnels État" . Ceci est un très bon papier, et il vous donnera une 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, il est très bien fait, et je ne vais pas essayer de le condenser ici.

  • Considérez 

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

    Si je l'appelle bar, je peux simplement choisir tout type a que je l'aime, et je peux passer une fonction à partir du type a type a. Par exemple, je peux passer la fonction (+1) ou la fonction reverse. Vous pouvez penser à la forall en disant: « Je reçois de choisir le type maintenant ». (Le mot technique pour choisir le type est instanciation ).

    Les restrictions relatives aux appels foo sont beaucoup plus strictes: l'argument foo doit une fonction polymorphique. Avec ce type, les seules fonctions que je peux passer à foo sont id ou une fonction qui diverge toujours ou des erreurs, comme undefined. La raison est que, avec foo, le forall est à gauche de la flèche, afin de l'appelant foo je ne suis pas à choisir ce a est plutôt c'est le la mise en œuvre de foo qui arrive à choisir ce que a est. Parce que forall est à gauche de la flèche, plutôt qu'au-dessus de la flèche comme dans bar, l'instanciation a lieu dans le corps de la fonction plutôt que sur le site d'appel.

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

Addendum: Jargon "au-dessus", "en dessous", "à gauche de". Cela n'a rien à voir avec le textuelle façons types sont écrits et tout à voir avec des arbres de syntaxe abstraite. Dans la syntaxe abstraite, un forall prend le nom d'une variable de type, et puis il y a un type complet « ci-dessous » la forall. Une flèche prend deux types (type d'argument et le résultat) et forme un nouveau type (le type de fonction). Le type d'argument est « à gauche de » la flèche; il est enfant de la flèche gauche dans l'arbre de syntaxe abstraite.

Exemples:

  • 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 n f e x . (forall e x . n e x -> f -> Fact x f) 
              -> Block n e x -> f -> Fact x f

    type entre parenthèses serait appelé « un forall à gauche d'une flèche ». (J'utilise des types comme ça dans un optimiseur je travaille.)

Ma réponse originale:

  

Quelqu'un peut-il expliquer complètement le mot-clé forall en clair, simple anglais

Norman indique, il est très difficile de donner une explication en anglais clair et simple d'un terme technique de la théorie de type. Nous essayons tous bien.

Il n'y a vraiment une chose à retenir sur « forall »: il se lie à des types une certaine portée . Une fois que vous comprenez que, tout est assez facile. C'est le équivalent de « lambda » (ou une forme de « laisser ») au niveau du type - Norman Ramsey utilise la notion de « gauche » / « au-dessus » de transmettre ce même concept de champ dans son excellente réponse.

La plupart des utilisations de « forall » sont très simples, et vous pouvez les trouver introduites dans la GHC Manuel d'utilisation, S7.8 ., En particulier l'excellent S7.8.5 sur imbriquée formes de 'forall'.

Dans Haskell, nous partons généralement hors du liant pour les types, lorsque le type est universellement quanitified, comme suit: 

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

est équivalent à: 

length :: [a] -> Int

Voilà.

Comme vous pouvez lier des variables de type maintenant une certaine portée, vous pouvez avoir d'autres champs d'application que le niveau supérieur ( " quantifiés universellement "), comme votre premier exemple, où la variable de type est seulement visible à l'intérieur de la structure de données. Ceci permet pour les types cachés ( " types existentiels "). Ou nous pouvons avoir arbitraire imbrication des liaisons ( "rang n types").

Pour comprendre en profondeur les systèmes de type, vous aurez besoin d'apprendre un peu de jargon. C'est la nature de la science informatique. Cependant, les utilisations simples, comme ci-dessus, devraient être pouvant être saisi de manière intuitive, par analogie avec « let » au niveau de la valeur. UNE excellente introduction est Launchbury et Peyton Jones .

  

Ils sont densément emballé avec des hypothèses que j'ai lu la dernière de quelque branche de mathématiques discrètes, théorie des catégories ou l'algèbre abstraite est populaire cette semaine. (Si je ne lis jamais les mots « consulter le papier tout pour les détails de la mise en œuvre » à nouveau, il sera trop tôt.)

Er, et qu'en est logique simple de premier ordre? forall est assez clairement en référence à la quantification universelle , et dans ce contexte, le terme existentiel plus de sens aussi bien, mais il serait moins gênant s'il y avait un mot-clé exists. Que la quantification est effectivement dépend universel ou existentiel sur la mise en place du quantificateur par rapport à l'endroit où les variables sont utilisées de quel côté d'une flèche de fonction et il est tout un peu confus.

Donc, si cela ne veut pas de l'aide, ou si vous ne tout simplement pas comme la logique symbolique, dans une perspective à la rigueur de programmation plus fonctionnel, vous pouvez penser à des variables de type comme étant juste (implicite) type paramètres à la fonction. Les fonctions sont traditionnellement écrites prenant des paramètres de type dans ce sens à l'aide d'un lambda de capital pour une raison quelconque, que je vais écrire ici /\.

Alors, considérez la fonction id: 

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

On peut réécrire comme lambdas, en déplaçant le "paramètre de type" de la signature de type et l'ajout d'annotations de type en ligne: 

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

Voici la même chose fait à const: 

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

Ainsi, votre fonction 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 comme argument dépend du paramètre de type de bar. Demandez-vous si vous aviez quelque chose comme ceci: 

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

Ici bar2 applique la fonction à quelque chose du type Char, donnant ainsi bar2 tout type autre paramètre que Char provoquera une erreur de type.

D'autre part, voici ce que foo pourrait ressembler à: 

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

Contrairement à bar, foo ne prend pas en fait tout à tous les paramètres de type! Il faut une fonction se prend un paramètre de type, puis applique cette fonction à deux différents types.

Alors, quand vous voyez un forall dans une signature de type, il suffit de penser comme un expression lambda pour les signatures de type . Tout comme lambdas réguliers, la portée de forall étend jusqu'à à droite possible, jusqu'à parenthèse enfermer, et tout comme les variables liées dans une lambda régulière, les variables de type lié par un forall ne sont portée dans l'expression quantifiée.

Post Scriptum : Peut-être que vous pourriez vous demander - maintenant que nous réfléchissons sur les fonctions prenant des paramètres de type, pourquoi ne pouvons-nous faire quelque chose de plus intéressant avec ces paramètres que les mettre dans une signature de type ? La réponse est que nous pouvons!

Une fonction qui met les variables de type avec une étiquette et retourne un nouveau type est un constructeur de type , que vous pouvez écrire quelque chose comme ceci: 

Either = /\a b -> ...

Mais nous aurions besoin complètement nouvelle notation, car la façon dont un tel type est écrit, comme Either a b, est déjà évocateur de « appliquer la fonction Either à ces paramètres ».

D'autre part, une fonction de ce genre de « matches de motif » sur ses paramètres de type, de retour des valeurs différentes pour différents types, est méthode d'une classe de type . Une légère expansion à ma syntaxe /\ ci-dessus suggère quelque chose comme ceci: 

fmap = /\ f a b -> case f of
    Maybe -> (\g x -> case x of
        Just y -> Just b g y
        Nothing -> Nothing b) :: (a -> b) -> Maybe a -> Maybe b
    [] -> (\g x -> case x of
        (y:ys) -> g y : fmap [] a b g ys 
        []     -> [] b) :: (a -> b) -> [a] -> [b]

Personnellement, je pense que je préfère syn réelle de Haskelltaxe ...

Une fonction qui "correspond à motif" ses paramètres de type et renvoie un arbitraire, type existant est un type de famille ou dépendance fonctionnelle - dans le premier cas, il a même semble déjà beaucoup comme une définition de fonction.

Voici une explication rapide et sale en termes clairs que vous êtes susceptible d'être déjà familier.

Le mot-clé est forall vraiment utilisé que d'une manière à Haskell. Cela signifie toujours la même chose quand vous le voyez.

quantification universelle

Type universellement quantifiés est un type de forme forall a. f a. Une valeur de ce type peut être considéré comme fonction qui prend un type a comme argument et retourne une valeur de type f a. Sauf que dans Haskell ces arguments de type sont passés implicitement par le système de type. Cette « fonction » doit vous donner la même valeur quel que soit le type qu'il reçoit, de sorte que la valeur est polymorphes .

Par exemple, considérons le forall a. [a] type. Une valeur de ce type prend un autre type a et vous renvoie une liste d'éléments de ce même type a. Il n'y a qu'une seule mise en œuvre possible, bien sûr. Il devrait vous donner la liste vide parce a pourrait être absolument tout type. La liste vide est la seule valeur de la liste qui est polymorphe dans son type d'élément (car elle n'a pas d'éléments).

Ou le forall a. a -> a type. L'appelant de la fonction d'une telle offre à la fois un type a et une valeur de type a. La mise en œuvre doit alors retourner une valeur de ce même type a. Il n'y a qu'une seule mise en œuvre à nouveau possible. Il devrait retourner la même valeur qu'il a été donné.

quantification existentielle

Une de type existentiellement quantifiés aurait la forme exists a. f a, si Haskell a soutenu que la notation. Une valeur de ce type peut être considéré comme une paire (ou un « produit ») constitué d'un type a et une valeur de type f a.

Par exemple, si vous avez une valeur de type exists a. [a], vous avez une liste d'éléments d'un certain type. Il pourrait être tout type, mais même si vous ne savez pas ce qu'il est, il y a beaucoup que vous pouvez faire à la liste d'un tel. Vous pouvez inverser, ou vous pouvez compter le nombre d'éléments, ou d'effectuer toute autre opération de liste qui ne dépend pas du type des éléments.

OK, donc attendez une minute. Pourquoi Haskell utiliser forall pour désigner un type « existentiel » comme ce qui suit? 

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

Il peut être source de confusion, mais il décrit vraiment la type de données constructeur SB: 

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

Une fois construit, vous pouvez penser à une valeur de type ShowBox comme composé de deux choses. Il est un type s avec une valeur de type s. En d'autres termes, il est une valeur d'un type quantifié existentiellement. ShowBox pourrait vraiment être écrit comme exists s. Show s => s, si Haskell a soutenu que la notation.

runST et les amis

Étant donné que, comment sont-ils différents? 

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

premier bar de prendre Let. Il faut 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. Elle exige que la mise en œuvre de foo pouvoir passer tout type il veut la fonction qu'on lui donne. La seule fonction que nous pouvions raisonnablement donner est id.

Nous devrions maintenant pouvoir aborder le sens du type de runST: 

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

runST doit être en mesure de produire une valeur de type a, peu importe quel type nous donnons comme a. Pour ce faire, il a besoin d'un argument de type forall s. ST s a qui, sous le capot est juste une fonction de type forall s. s -> (a, s). Cette fonction doit alors être en mesure de produire une valeur de type (a, s) peu importe quel type de la mise en œuvre runST décide de donner comme s.

OK, donc quoi? L'avantage est que cela met une contrainte sur l'appelant de runST en ce que le a type ne peut pas impliquer le s type du tout. Vous ne pouvez pas passer une valeur de type ST s [s], par exemple. Ce que cela signifie en pratique que la mise en œuvre de runST est libre d'effectuer une mutation avec la valeur du type s. Les garanties du système de type que cette mutation est locale à la mise en œuvre de runST.

Le type de runST est un exemple de rang 2 types polymorphes parce que le type de son argument contient un quantificateur forall. Le type de foo ci-dessus est de rang 2. Un type polymorphes ordinaire, comme celui de bar, est de rang 1, mais il devient de 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 de rang 3, et ainsi de suite. En général, un type qui prend des arguments polymorphes de rang n a rang n + 1.

La raison pour laquelle il existe différentes utilisations de ce mot-clé est qu'il est en fait utilisé dans au moins deux extensions de système de type différents. Types-rang supérieur, et existentiels

Il est probablement préférable juste pour lire et comprendre ces deux choses séparément, plutôt que d'essayer d'obtenir une explication des raisons pour lesquelles « forall » est un peu approprié de syntaxe dans les deux en même temps.

  

Quelqu'un peut-il expliquer complètement le mot-clé forall en anglais clair et simple (ou, si elle existe quelque part, pointez sur une telle explication claire que je l'ai manqué) qui ne suppose pas que je suis un mathématicien imprégné dans le jargon?

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

Mais avant de comprendre que je voudrais vous diriger vers un discours très accessible et agréable par Runar Bjarnason intitulé « Contraintes Liberate, des libertés Contraindre ". Le discours est plein d'exemples de cas d'utilisation du monde réel ainsi que des exemples de Scala pour soutenir cette déclaration, même si elle ne mentionne pas forall. Je vais essayer d'expliquer le point de vue de forall ci-dessous. 

                CONSTRAINTS LIBERATE, LIBERTIES CONSTRAIN

Il est très important à digérer et à croire cette déclaration pour procéder à l'explication suivante, donc je vous invite à regarder le discours (au moins en partie).

Maintenant un exemple très commun, montrant l'expressivité du système de type Haskell est cette signature de type:

foo :: a -> a

On dit que compte tenu de cette signature de type, il n'y a qu'une seule fonction qui peut satisfaire ce type et qui est la fonction identity ou ce qui est plus communément connu id.

Je me demandais toujours les fonctions ci-dessous dans les premières étapes de l'apprentissage me Haskell,: 

foo 5 = 6

foo True = False

ils satisferaient la signature de type ci-dessus, alors pourquoi les gens Haskell prétendent qu'il est id seul qui satisfait la signature de type?

C'est parce qu'il ya un forall implicite caché dans la signature de type. Le type réel est: 

id :: forall a. a -> a

Alors, laissez-nous maintenant revenons à la déclaration: Les contraintes libèrent, les libertés Contraindre

Translating que le système de type, cette affirmation devient:

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

et

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

Essayons de prouver la première déclaration:

Une contrainte au niveau du type ..

mettre donc une contrainte sur notre signature de type 

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

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

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

Même peut être observé en limitant a avec tout autre etc classe de types

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

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

Ceci est connu comme la quantification existentielle, ce qui se traduit par il existe certains cas de a pour lesquels une fonction dans l'alimentation un peu de types retourne a quelque chose du même type, et les cas appartiennent tous à la ensemble de nombres.

On peut donc voir ajouter une contrainte (ce a doit appartenir à l'ensemble des nombres), le niveau libère terme d'avoir plusieurs implémentations possibles.

Venons-en maintenant à la deuxième déclaration et celle qui porte en fait l'explication de forall:

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

Alors maintenant, nous libérons la fonction au niveau du type: 

foo :: forall a. a -> a

Maintenant, cela se traduit par: 

∀a , a -> a

ce qui signifie que la mise en œuvre de cette signature de type doit être tel qu'il est a -> a pour toutes les circonstances.

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

foo 5 = 7

parce que cette mise en œuvre ne satisferait pas si nous mettons a comme Bool. a peut être un Char ou un [Char]ou un type de données personnalisé. Dans tous les cas, il doit retourner quelque chose du même type. Cette liberté au niveau du type est ce qu'on appelle Universal Quantification et la seule fonction qui peut satisfaire c'est 

foo a = a

ce qui est communément connu sous le nom de la fonction identity

Par conséquent forall est un liberty au niveau du type, dont le but réel est de constrain le niveau à long terme à une mise en œuvre particulière.

Comment est existentielle existentielle?

  

Avec Existentielle-Quantification, foralls dans les définitions de data signifient   que la valeur contenue peut est de tout type approprié, non   qu'il doit être tous les types appropriés .   - yachiru de réponse

Une explication des raisons pour lesquelles forall dans les définitions de data sont isomorphes à (exists a. a) (pseudo-Haskell) se trouve dans de Wikibooks "Haskell / types" existentiellement quantifiés.

Voici le résumé d'un bref: 

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

Lorsque ltrage / déconstruisant MkT x, quel est le type de x? 

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

x peut être tout type (comme indiqué dans le forall), et ainsi le type de c'est: 

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

Par conséquent, les points 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 « forall signifie vraiment« pour tous ». Une distinction importante à faire est l'impact de forall sur la définition par rapport à la fonction application .

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

Si la chose étant défini est un polymorphes valeur , cela signifie que la valeur doit être valable pour tous a approprié, ce qui est assez restrictive.

Si la chose étant défini est un polymorphes Fonction , cela signifie que la fonction doit être valable pour tous a approprié, ce qui est pas restrictive, car juste parce que la fonction est ne pas polymorphes signifie le paramètre étant appliqué doivent être polymorphes. Autrement dit, si la fonction est valable pour tous les a, puis à l'inverse tout a approprié peut être appliqué à la fonction. Cependant, le type de paramètre ne peut être choisi une fois dans la définition de la fonction.

Si un forall est à l'intérieur du type de paramètre de fonction (c.-à-un Rank2Type), alors cela signifie que le appliqué paramètre doit être vraiment polymorphes, pour être conforme à l'idée de des moyens de forall définition est polymorphes. Dans ce cas, le type de paramètre peut être choisi plus d'une fois dans la définition de la fonction ( "et est choisi par la mise en œuvre de la fonction », comme sur pointé par Norman )

Par conséquent, la raison pour laquelle les définitions de data existentielle permet tout a est parce que le constructeur de données est un polymorphes Fonction : 

MkT :: forall a. a -> T

type de MKT :: a -> *

Ce qui signifie que toute a peut être appliqué à la fonction. Contrairement à, disons, un polymorphes valeur : 

valueT :: forall a. [a]

type de VALUET :: a

Ce qui signifie que le définition de VALUET doit être polymorphes. Dans ce cas, valueT peut être définie comme une liste vide [] de tous les types. 

[] :: [t]

Différences

Bien que le sens de forall est conforme à ExistentialQuantification et RankNType, a une différence existentiaux puisque le constructeur data peut être utilisé en correspondance de motif. Comme indiqué dans le Guide de l'utilisateur GHC :

  

Lorsque l'appariement de motif, chaque correspondance de motif introduit une nouvelle, distincte, le type de chaque variable de type existentielle. Ces types ne peuvent pas être unifiés avec un autre type, et ils ne peuvent échapper à la portée du match de motif.

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top