Que sont les skolems?

Eeek! GHCi a trouvé Skolems dans mon code!

... Couldn't match type `k0' with `b' because type variable `b' would escape its scope This (rigid, skolem) type variable is bound by the type signature for groupBy :: Ord b => (a -> b) -> Set a -> Set (b, [a]) The following variables have types that mention k0 ... 

Que sont-ils? Que veulent-ils avec mon programme? Et pourquoi essaient-ils de s’enfuir (les petits ingrats)?

Pour commencer, une variable de type “rigide” dans un contexte signifie une variable de type liée par un quantificateur en dehors de ce contexte, qui ne peut donc pas être unifiée avec d’autres variables de type.

Cela fonctionne beaucoup comme les variables liées par un lambda: Etant donné un lambda (\x -> ... ) , à partir de “l’extérieur”, vous pouvez bien sûr l’appliquer à n’importe quelle valeur. mais à l’intérieur, vous ne pouvez pas simplement décider que la valeur de x doit avoir une valeur particulière. Choisir une valeur pour x dans le lambda devrait sembler assez idiot, mais c’est ce que signifient les erreurs sur “ne peut pas correspondre à blah blah, variable de type rigide, bla bla”.

Notez que, même sans utiliser de quantificateurs explicites de forall , toute signature de type de niveau supérieur a un forall implicite pour chaque variable de type mentionnée.

Bien sûr, ce n’est pas l’erreur que vous obtenez. Qu’est-ce qu’une variable de type “échappé” signifie est encore plus ridicule – c’est comme avoir un lambda (\x -> ...) et essayer d’utiliser des valeurs spécifiques de x dehors du lambda, indépendamment de l’appliquer à un argument. Non, ne pas appliquer le lambda à quelque chose et utiliser la valeur du résultat – je veux dire en fait utiliser la variable elle-même en dehors de la scope où elle est définie.

La raison pour laquelle cela peut se produire avec des types (sans paraître aussi absurde que l’exemple avec un lambda) est qu’il y a deux notions de “variables de type” qui flottent: pendant l’unification, vous avez des “variables” représentant des types indéterminés avec d’autres variables de ce type via l’inférence de type. D’autre part, vous avez les variables de type quantifiées décrites ci-dessus, qui sont spécifiquement identifiées comme allant de types possibles.

Considérons le type de l’expression lambda (\x -> x) . En partant d’un type complètement indéterminé a , nous voyons qu’il prend un argument et le réduit à a -> b , alors nous voyons qu’il doit retourner quelque chose du même type que son argument, donc nous le réduisons à a -> a . Mais maintenant, cela fonctionne pour n’importe quel type a vous voulez, nous lui donnons donc un quantificateur (forall a. a -> a) .

Ainsi, une variable de type échappé se produit lorsque vous avez un type lié par un quantificateur que les infodes GHC doivent être unifiées avec un type indéterminé en dehors de la scope de ce quantificateur.


Donc, apparemment, j’ai oublié d’expliquer le terme “variable de type skolem” ici, heh. Comme mentionné dans les commentaires, dans notre cas, il est essentiellement synonyme de “variable de type rigide”, ce qui explique encore l’idée ci-dessus.

Je ne suis pas tout à fait sûr d’où le terme provient, mais je suppose que cela implique la forme normale de Skolem et représente la quantification existentielle en termes d’universels, comme cela se fait dans GHC. Une variable de type skolem (ou rigide) est une variable qui, dans certaines limites, a un type inconnu mais spécifique pour une raison quelconque – faisant partie d’un type polymorphe, provenant d’un type de données existentiel, & c.

Si je comprends bien, une “variable Skolem” est une variable qui ne correspond à aucune autre variable, y compris elle-même.

Cela semble apparaître dans Haskell lorsque vous utilisez des fonctionnalités telles que des foralls explicites, des GADT et d’autres extensions de système de type.

Par exemple, considérez le type suivant:

 data AnyWidget = forall x. Widget x => AnyWidget x 

Cela AnyWidget que vous pouvez prendre n’importe quel type qui implémente la classe Widget et l’ AnyWidget dans un type AnyWidget . Maintenant, supposons que vous essayiez de déballer ceci:

 unwrap (AnyWidget w) = w 

Euh, non, vous ne pouvez pas faire ça. Parce qu’au moment de la compilation, nous n’avons aucune idée du type de w , il n’y a donc aucun moyen d’écrire une signature de type correcte pour cela. Ici, le type de w a échappé à AnyWidget , ce qui n’est pas autorisé.

Si je comprends bien, en interne, GHC donne un type qui est une variable Skolem, pour représenter le fait qu’il ne doit pas s’échapper. (Ce n’est pas le seul scénario de ce type, il y a quelques autres endroits où une certaine valeur ne peut pas s’échapper en raison de problèmes de saisie.)

Le message d’erreur apparaît lorsqu’une variable de type tente d’échapper à son étendue.

Il m’a fallu du temps pour comprendre cela, alors je vais écrire un exemple.

 {-# LANGUAGE ExistentialQuantification #-} data I a = I a deriving (Show) data SomeI = forall a. MkSomeI (I a) 

Alors si nous essayons d’écrire une fonction

  unI (MkSomeI i) = i 

GHC refuse de taper / vérifier cette fonction.


Pourquoi? Essayons de déduire le type nous-mêmes:

  • unI est une définition lambda, donc son type est x -> y pour certains types x et y .
  • MkSomeI a un type pour tout forall a. I a -> SomeI forall a. I a -> SomeI
    • MkSomeI i un type SomeI
    • i sur le LHS a un type I z pour certains types z . A cause du quantificateur forall , nous avons dû introduire une nouvelle variable de type (frais). Notez que ce n’est pas universel, car il est lié à l’intérieur de l’ (SomeI i) .
    • Ainsi, nous pouvons unifier la variable de type x avec SomeI , ce n’est pas SomeI . Donc, l’ unI devrait avoir le type SomeI -> y .
  • i donc le type I z sur le RHS .
  • À ce stade, l’unificateur tente d’unifier y et I z , mais il remarque que z est introduit dans le contexte inférieur. Ainsi, il échoue.

Sinon, le type pour unI aurait le type forall z. SomeI -> I z forall z. SomeI -> I z , mais le correct est exists z. SomeI -> I z exists z. SomeI -> I z . Pourtant, ce GHC ne peut pas représenter directement.


De même, nous pouvons voir pourquoi

 data AnyEq = forall a. Eq a => AE a -- reflexive :: AnyEq -> Bool reflexive (AE x) = x == x 

travaux.

La variable (existentielle) dans AE x n’échappe pas à la scope externe, donc tout va bien.


J’ai aussi rencontré une “fonctionnalité” dans GHC 7.8.4 et 7.10.1 où RankNTypes sur lui-même est correct, mais l’ajout de GADTs déclenche l’erreur

 {-# LANGUAGE RankNTypes #-} {-# LANGUAGE GADTs #-} example :: Ssortingng -> I a -> Ssortingng example str x = withContext xs where si = "Foo" ++ str withContext :: I a -> (forall b. I b -> c) -> c withContext xf = fx 

Donc, il se peut que votre code ne présente aucun problème. Cela pourrait être GHC, qui ne peut pas tout comprendre de manière cohérente.

EDIT : La solution est de donner un type à s :: forall a. I a -> Ssortingng s :: forall a. I a -> Ssortingng .

GADTs MonoLocalBinds , ce qui fait que le type inféré de s a la variable skolem, donc le type n’est pas toujours forall a. I a -> Ssortingng forall a. I a -> Ssortingng , mais t -> Ssortingng , ne sont pas liés dans le mauvais contexte. Voir: https://ghc.haskell.org/trac/ghc/ticket/10644