Que fait le mot-clé « forall » en Haskell/GHC ?

Question

Je commence à comprendre comment l' forall mot-clé est utilisé dans les soi-disant "existentielle types", comme ceci:

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

Ce n'est qu'un sous-ensemble, cependant, de l' forall est utilisé et j'ai simplement ne peut pas envelopper mon esprit autour de son utilisation dans des choses comme ça:

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

Ou d'expliquer pourquoi elles sont différentes:

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

Ou de l'ensemble de l' RankNTypes trucs...

J'ai tendance à préférer clair, sans jargon anglais plutôt que le genre de langage qui sont normales dans les milieux universitaires. La plupart des explications que 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 "existentielle types") qui me fait me sentir heureux jusqu'à ce que j'ai lu le code qui l'utilise d'une manière complètement différente (comme runST, foo et bar ci-dessus).
2. Ils sont très denses avec des hypothèses que j'ai lu le dernier quelle que soit la branche des mathématiques discrètes, la catégorie de la théorie ou de l'algèbre abstraite est populaire cette semaine. (Si je n'ai jamais lu les mots "consulter le document quel que soit pour des détails de mise en œuvre" de nouveau, il sera trop tôt.)
3. Ils sont écrits dans des voies qui se révèlent souvent même de simples concepts en tortuously tordu et brisé la grammaire et de la sémantique.

Alors...

Sur la question réelle. Quelqu'un peut-il expliquer totalement l' forall mot-clé en clair anglais (ou, si elle existe quelque part, tel une explication claire qui je l'ai raté) qui ne suppose que je suis un mathématicien ancré dans le jargon?

---

Edité pour ajouter:

Il y a deux stand-out réponses de la plus grande qualité de celles ci-dessous, mais malheureusement je ne peux pas en choisir un comme le meilleur. Norman réponse a été détaillées et utiles, de façon d'expliquer les choses d'une façon qui ont montré que certains des fondements théoriques de l' forall et en même temps me montrant des implications pratiques. yairchu réponse couvrait une superficie personne d'autre ne l'a mentionné (dans l'étendue des variables de type) et illustré de tous les concepts avec un code et un GHCi session. S'il était possible de sélectionner à la fois en tant que meilleur, je le ferais. Malheureusement je ne peux pas et, après avoir examiné les deux réponses de près, j'ai décidé que yairchu est légèrement Norman est à cause de l'illustration de code et explication jointe. C'est un peu injuste, cependant, parce que vraiment j'ai besoin de réponses pour comprendre cela au point qu' forall ne me laisse pas avec un faible sentiment d'effroi quand je la vois dans un type de signature.

Answer 1

Commençons 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 la plaine de Haskell 98. Il nécessite une extension à l'appui de l' forall mot-clé.

Fondamentalement, il existe 3 différentes utilisations communes pour l' forall mot-clé (ou, au moins, de sorte qu'il semble), et chacun a ses propres Haskell extension: ScopedTypeVariables, RankNTypes/Rank2Types, ExistentialQuantification.

Le code ci-dessus n'obtenez pas une erreur de syntaxe avec l'une de ces permis, mais uniquement de type vérifie ScopedTypeVariables activé.

L'Étendue Des Variables De Type:

L'étendue des variables de type permet de spécifier les types de code à l'intérieur d' where clauses. Il rend l' b en val :: b le même que l' b en foob :: forall a b. (b -> b) -> b -> (a -> b) -> Maybe a -> b.

Une confusion point: vous pouvez entendre lorsque vous omettez l' forall d'un type qu'il est en fait toujours implicitement. (à partir de Norman réponse: "normalement, ces langues omettre le pourtout de types polymorphes"). Cette affirmation est correcte, mais il se réfère à la d'autres utilisations de l' forall, et de ne pas l' ScopedTypeVariables d'utilisation.

De Rang N-Types:

Commençons avec qui mayb :: b -> (a -> b) -> Maybe a -> b est équivalent à mayb :: forall a b. b -> (a -> b) -> Maybe a -> b, sauf pour quand ScopedTypeVariables est activé.

Cela signifie qu'il fonctionne pour chaque a et b.

Disons que vous voulez faire quelque chose comme cela.

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 comprendre pourquoi, nous allons essayer de code:

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 ne GHC en déduire que le tuple doit contenir deux du même type? Nous allons dire qu'ils n'ont 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 permet pas de postuler liftFunc sur v car v :: b et liftFunc veut un x. Nous voulons vraiment que notre fonction pour obtenir une fonction qui accepte d'éventuelles x!

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

Il n'est donc pas liftTup qui fonctionne pour tous x, c'est la fonction qu'il obtient.

Quantification Existentielle:

Prenons 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]'
    ...

Avec de Rang N-Types, forall a signifie que votre expression doit s'adapter à tous les possibles as. Par exemple:

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

Une liste vide ne fonctionne pas comme une liste de tout type.

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

Answer 2

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

Pas de. (Eh bien, peut-être N'Stewart peut.)

Ici sont les obstacles à une simple explication claire ou forall:

• C'est un quantificateur. Vous disposez d'un avoir au moins un peu de logique (prédicat de calcul), pour avoir vu un universel ou le quantificateur existentiel. Si vous ne l'avez jamais vu prédicat de calcul ou ne sont pas à l'aise avec des quantificateurs (et j'ai vu des étudiants en cours de Doctorat examens de qualification qui ne sont pas à l'aise), alors, pour vous, il n'y a pas d'explication simple de l' forall.

• C'est un type de quantificateur. Si vous n'avez pas vu le Système F et obtenu une certaine pratique de l'écriture polymorphe types, vous allez trouver des forall de la confusion. Expérience avec Haskell ou ML n'est pas assez, parce que, normalement, ces langues omettre l' forall de types polymorphes. (Dans mon esprit, c'est un langage de conception de l'erreur.)

• En Haskell, en particulier, forall est utilisé d'une manière que je trouve déroutant. (Je suis pas un théoricien, mais mon travail m'amène en contact avec beaucoup de type de théorie, et je suis très à l'aise avec elle.) Pour moi, la principale source de confusion, forall est utilisé pour encoder un type que j'ai moi-même préfère écrire avec exists. Il est justifié par un problème de type isomorphisme impliquant des quantificateurs et des flèches, et chaque fois que je veux comprendre, je dois regarder les choses et de travailler sur l'isomorphisme de moi-même.

  Si vous n'êtes pas à l'aise avec l'idée de type isomorphisme, ou si vous n'avez pas de pratique de la réflexion sur le type de isomorphisms, cette utilisation de l' forall va paralyser vous.

• Alors que le concept général de l' forall est toujours la même (la liaison à introduire une variable de type), le détail des différentes utilisations peuvent varier de manière significative. Informel de l'anglais n'est pas un très bon outil pour expliquer les variations. Pour vraiment comprendre ce qui se passe, vous avez besoin d'un peu plus de mathématiques. Ce sont les mathématiques peuvent être trouvés dans de Benjamin Pierce texte d'introduction Types et des Langages de Programmation, ce qui est un très bon livre.

Quant à vos exemples,

• runST devrait faire de votre mal à la tête. De plus haut rang types (forall à la gauche d'une flèche) sont rarement trouvés dans la nature. Je vous encourage à lire l'article qui introduit runST: "Paresseux État Fonctionnel Fils". C'est vraiment un très bon livre, et il vous donnera une bien meilleure intuition pour le type d' runST , en particulier, et pour de plus haut rang types en général. L'explication prendre plusieurs pages, il est très bien fait, et je ne vais pas essayer de le condenser ici.

• Envisager

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

  Si je l'appelle, bar, je peux simplement choisir n'importe quel type d' a que j'aime, et je peux passer d'une fonction de type a type a. Par exemple, je peux passer de la fonction (+1) ou la fonction reverse. Vous pouvez penser à de la forall que de dire "j'arrive à choisir le type de maintenant". (Le mot technique pour choisir le type est l'instanciation.)

  Les restrictions en matière d'appels d' foo sont plus strictes: l'argument d' foo doit être une fonction polymorphe. Avec ce type, la seule les fonctions, je peux passer à l' foo sont id ou une fonction qui toujours diverge ou des erreurs, comme undefined. La raison en est que, avec foo, forall est à gauche de la flèche, de sorte que l'appelant d' foo je n'ai pas à choisir ce qui a est—c'est plutôt la mise en œuvre de l' foo qui obtient de choisir ce qu' a . Parce qu' forall est à gauche de la flèche, plutôt qu'au-dessus de la flèche, comme en bar, l'instanciation se fait dans le corps de la fonction plutôt que sur le site d'appel.

Résumé: Une complète explication de l' forall mot-clé nécessite des maths et ne peut être comprise que par quelqu'un qui a étudié les mathématiques. Même partielle, des explications sont difficiles à comprendre sans les mathématiques. Mais peut-être que mon partiel, non-math explications aider un peu. Allez lire Launchbury et Peyton Jones, runST!

---

Addendum: le Jargon "au-dessus", "dessous", "à gauche de". Ils n'ont rien à voir avec la textuelles moyens sont les types d'écrit et tout à voir avec le résumé des arbres de syntaxe abstraite. Dans la syntaxe abstraite, forall prend le nom d'une variable de type, et puis il y a plein de type "en-dessous" les forall. Une flèche prend deux types (argument et le type de résultat) et les formes d'un nouveau type (le type de fonction). L'argument est de type "à gauche de" la flèche; c'est la flèche de gauche de l'enfant dans le résumé de l'arbre syntaxique.

Exemples:

• En forall a . [a] -> [a], le pourtout 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
  

  le type entre parenthèses serait appelé "un forall à la gauche d'une flèche". (Je suis en utilisant des types comme ça dans un optimiseur je suis en train de travailler sur.)

Answer 3

Ma réponse originale à cette question:

Quelqu'un peut-il expliquer totalement l'forall mot-clé en clair anglais

Comme Norman indique, il est très difficile de donner un clair explication anglais d'un terme technique de type théorie. Nous sommes tous d'essayer de bien.

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

La plupart des utilisations de "forall" sont très simples, et vous pouvez les trouver a introduit dans le GHC Manuel de l'utilisateur, S7.8., en particulier l'excellent S7.8.5 sur imbriquée des formes de "forall'.

En Haskell, nous avons l'habitude de laisser sur le classeur pour les types, lorsque le type est universellement quanitified, comme suit:

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

est équivalent à:

length :: [a] -> Int

C'est tout.

Puisque vous pouvez lier des variables de type maintenant une certaine étendue, vous pouvez avoir étendues autres de haut niveau ("universellement quantifiée"), comme votre premier exemple, lorsque le type de la variable n'est visible que dans la structure des données. Cela permet pour les types ("existentielle types"). Ou nous pouvons avoir arbitraire l'imbrication des liaisons ("rang N types").

Pour comprendre en profondeur des systèmes de type, vous aurez besoin d'apprendre le jargon. C'est la nature de l'informatique. Toutefois, de simples usages, comme ci-dessus, doit être en mesure de saisir intuitivement, par analogie avec " laissez-les sur le plan de la valeur. Un excellente introduction est Launchbury et Peyton Jones.

Answer 4

Voici une rapide explication en termes simples que vous êtes probablement déjà familier avec.

L' forall mot-clé est vraiment utilisé dans un sens en Haskell. C'est toujours la même chose quand vous le voyez.

Quantification universelle

Un universellement quantifiée type est un type de la forme forall a. f a. Une valeur de ce type peut être considéré comme une fonction qui prend un type a comme argument et retourne une valeur de type f a. Sauf qu'en Haskell ces arguments sont transmis implicitement par le système de type.

Par exemple, considérer le type forall a. [a]. Une valeur de ce type prend un autre type a et vous donne une liste d'éléments de même type a. Il y a seulement une mise en œuvre possible, bien sûr. Il devrait vous donner la liste vide, car a peut être absolument n'importe quel type.

Ou le type forall a. a -> a. L'appelant d'une telle fonction est à la fois un type a et une valeur de type a. La mise en œuvre doit alors renvoyer une valeur du même type a. Il n'y a qu'une possibilité de mise en œuvre de nouveau. Il aurait à retourner la même valeur qu'elle a été donnée.

Quantification existentielle

Un existentiellement quantifiés type de aurait la forme exists a. f a, si Haskell 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 n'importe quel type, mais même si vous ne savez pas ce que c'est qu'il y a beaucoup de choses que vous pouvez faire pour une telle liste. Vous pouvez inverser, ou vous pourriez compter le nombre d'éléments, ou d'effectuer toute autre opération qui ne dépend pas du type des éléments.

OK, donc attendez une minute. Pourquoi ne Haskell utiliser forall pour désigner un "existentielle" de type semblable à la suivante?

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

Il peut être déroutant, mais c'est vraiment décrivant le type de données constructeur SB:

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

Une fois construit, vous pouvez penser à une valeur de type ShowBox composé de deux choses. C'est un type s avec une valeur de type s. En d'autres termes, c'est une valeur sur un plan existentiel quantifiés type. ShowBox pourrait vraiment être écrit comme exists s. Show s => s, si Haskell 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))

Nous allons tout d'abord prendre en bar. Il faut un type a et une fonction de type a -> a, et produit une valeur de type (Char, Bool). Nous avons pu choisir Int le a et de lui donner une fonction de type Int -> Int par exemple. Mais foo est différent. Elle nécessite la mise en œuvre de l' foo être capable de passer n'importe quel type il veut à la fonction que nous lui donnons. Donc la seule fonction pourraient raisonnablement donner c'est - id.

Nous devrions être en mesure de s'attaquer à la signification du type d' runST:

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

Donc, runST doit être capable de produire une valeur de type a, quel que soit le type nous donner en 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) quel que soit le type de la mise en œuvre de l' runST décide de donner des s.

OK, et alors? L'avantage est que cela met une contrainte sur l'appelant de runST en que le type a ne peut pas associer le type s . Vous ne pouvez pas passer une valeur de type ST s [s], par exemple. Ce qui signifie en pratique que la mise en œuvre de l' runST est libre d'effectuer la mutation avec la valeur de type s. Le type de système garantit que cette mutation est locale à la mise en œuvre de l' runST.

Le type d' runST est un exemple de rang 2 de type polymorphe , car le type de son argument contient un forall quantificateur. Le type d' foo ci-dessus est aussi de rang 2. Ordinaire de type polymorphe, comme celle de l' bar, est de rang 1, mais il devient de rang 2 si les types d'arguments sont requis pour être polymorphe, avec leurs propres forall quantificateur. Et si une fonction prend rang 2 arguments alors que son type est de rang 3, et ainsi de suite. En général, un type qui prend polymorphes arguments de rang n a rang n + 1.

Answer 5

Ils sont très denses avec des hypothèses que j'ai lu le dernier quelle que soit la branche des mathématiques discrètes, la catégorie de la théorie ou de l'algèbre abstraite est populaire cette semaine. (Si je n'ai jamais lu les mots "consulter le document que ce soit pour les détails de mise en œuvre" de nouveau, il sera trop tôt.)

Er, et ce sur simple logique de premier ordre? forall est assez clairement en référence à une quantification universelle, et dans ce contexte, le terme existentielle a plus de sens, bien qu'il serait moins difficile si il y avait un exists mot-clé. Si la quantification est effectivement universel ou existentielle dépend de l'emplacement de la quantificateur par rapport à l'endroit où les variables sont utilisées sur le côté de fonction de flèche et c'est un peu déroutant.

Donc, si cela ne fonctionne pas, ou si vous n'aimez pas la logique symbolique, de plus en plus de la programmation fonctionnelle-ish point de vue, vous pouvez penser à des variables de type seulement (implicite) type de paramètres à la fonction. Fonctions de prise de paramètres de type dans ce sens sont traditionnellement écrite à l'aide d'un capital lambda pour quelque raison que ce soit, que je vais écrire ici que /\.

Ainsi, considérer l' id fonction de:

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

On peut réécrire sous la forme de lambda, le déplacement de la "paramètre de type" hors de la signature d'un type et en ajoutant des annotations de type inline:

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

Voici la même chose fait à const:

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

Si votre bar fonction pourrait être quelque chose comme ceci:

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

Noter que le type de la fonction attribuée à la bar comme un argument dépend bars'paramètre de type. Envisager si vous avez eu quelque chose comme ceci à la place:

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

Ici, bar2 est l'application de la fonction de quelque chose de type Char, afin de donner des bar2 tout type de paramètre autre que Char va provoquer une erreur de type.

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

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

Contrairement aux bar, foo n'a pas en fait de prendre n'importe quel type de paramètres à tous! Elle prend une fonction qui lui-même prend un paramètre de type, puis applique cette fonction à deux différents types.

Alors, quand vous voyez un forall dans un type de signature, il suffit de penser à cela comme une expression lambda pour le type de signatures. Comme des lambdas, le champ d'application de l' forall s'étend aussi loin que possible à droite, jusqu'à enfermer la parenthèse, et tout comme les variables liées dans une lambda, le type des variables liées par un forall sont uniquement dans la portée à l'intérieur de la quantification de l'expression.

---

Post scriptum: peut-être vous pourriez vous demander, maintenant que nous sommes à la réflexion sur les fonctions de prise de paramètres de type, pourquoi ne pouvons-nous pas faire quelque chose de plus intéressant avec ces paramètres que de les mettre dans un type de signature? La réponse est que nous le pouvons!

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

Either = /\a b -> ...

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

D'autre part, une fonction qui sorte de "modèle correspond" sur ses paramètres de type, le retour des valeurs différentes pour les différents types, est une méthode d'une classe de type. Une légère expansion de mon /\ de la 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 Haskell réels de la syntaxe...

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