Utilisation réelle de GADT

Question

Existe-t-il de bonnes ressources sur l'utilisation réelle du type de données algébrique généralisé?

L'exemple donné dans le wikibook haskell est trop court pour me donner un aperçu des possibilités réelles de GADT.

Merci

Answer 1

GADTs sont faibles approximations inductive familles de dépendante tapé langues-donc, nous allons commencer par là au lieu de cela.

Inductive familles sont le type de données principal de l'introduction de la méthode dans un dépendante tapé la langue. Par exemple, dans Agda vous définissez les nombres naturels comme ceci

data Nat : Set where
  zero : Nat
  succ : Nat -> Nat 

ce qui n'est pas très fantaisie, c'est essentiellement la même chose que le Haskell définition

data Nat = Zero | Succ Nat

et en effet, dans GADT syntaxe le Haskell forme est encore plus similaire

{-# LANGUAGE GADTs #-}

data Nat where
  Zero :: Nat
  Succ :: Nat -> Nat

Donc, à première vue, vous pourriez penser GADTs sont juste génial supplémentaire de la syntaxe. C'est juste la pointe de l'iceberg si.

---

Agda a la capacité de représenter toutes sortes de types inconnus et étranges pour un Haskell programmeur. Un exemple simple est le type d'ensembles finis. Ce type est écrit comme Fin 3 et représente l' ensemble des nombres {0, 1, 2}. De même, Fin 5 représente l'ensemble des nombres {0,1,2,3,4}.

Cela devrait être assez bizarre en ce moment. Tout d'abord, on parle d'un type qui a un nombre normal comme un "paramètre" type d'. Deuxièmement, il n'est pas clair ce que cela signifie pour Fin n pour représenter l'ensemble {0,1...n}. Dans la vraie Agda nous aimerions faire quelque chose de plus puissant, mais il suffit de dire que nous pouvons définir une contains fonction

contains : Nat -> Fin n -> Bool
contains i f = ?

Maintenant, c'est étrange encore parce que la définition "naturelle" de l' contains serait quelque chose comme i < n, mais n est une valeur qui n'existe que dans le type Fin n et nous ne devrions pas être en mesure de franchir ce fossé si facilement. Alors qu'il s'avère que la définition n'est pas aussi simple, c'est exactement la puissance que inductive des familles ont dans dépendante tapé langues-ils introduire des valeurs qui dépendent de leurs types et les types qui dépendent de leurs valeurs.

---

Nous pouvons examiner ce qu'il est à propos de Fin qui lui donne cette propriété en regardant sa définition.

data Fin : Nat -> Set where
  zerof : (n : Nat) -> Fin (succ n)
  succf : (n : Nat) -> (i : Fin n) -> Fin (succ n)

cela prend un peu de travail à comprendre, de sorte qu'un exemple permet d'essayer de construire une valeur de type Fin 2. Il ya quelques façons de le faire (en fait, nous allons trouver qu'il y a exactement 2)

zerof 1           : Fin 2
zerof 2           : Fin 3 -- nope!
zerof 0           : Fin 1 -- nope!
succf 1 (zerof 0) : Fin 2

Cela nous permet de voir qu'il y a deux habitants et démontre aussi un peu de la façon dont le type de calcul qui se passe. En particulier, l' (n : Nat) peu dans le type d' zerof tient compte de la valeur n dans le type qui nous permet de former Fin (n+1) pour toute n : Nat. Après cela, nous utilisons des applications répétées d' succf d'incrément de notre - Fin valeurs dans le bon type de famille d'indices (nombre naturel que les indices de l' Fin).

Ce qui donne ces capacités? En toute honnêteté, il existe de nombreuses différences entre un dépendante tapé inductive de la famille et régulier Haskell ADT, mais nous pouvons nous concentrer sur exactement celui qui est le plus pertinent pour comprendre les GADTs.

Dans les GADTs et inductif familles vous obtenez une occasion de préciser l' exacte du type de votre constructeur. Cela pourrait être ennuyeux

data Nat where
  Zero :: Nat
  Succ :: Nat -> Nat

Ou, si nous avons une plus souple, indexé type que l'on peut choisir différents, plus intéressant types de retour

data Typed t where
  TyInt  :: Int                -> Typed Int
  TyChar :: Char               -> Typed Char
  TyUnit ::                       Typed ()
  TyProd :: Typed a -> Typed b -> Typed (a, b)
  ...

En particulier, nous sommes à abuser de la possibilité de modifier le type de retour fondée sur la particulier de la valeur constructeur utilisé. Cela nous permet de tenir compte de certaines informations sur la valeur dans le type et de produire plus finement spécifié (fibrée) tapé.

---

Alors, que pouvons-nous y faire? Eh bien, avec un peu d'huile de coude, on peut produire de l' Fin en Haskell. De façon succincte, il faut définir une notion de produits naturels dans les types

data Z
data S a = S a

> undefined :: S (S (S Z))  -- 3

... puis un GADT refléter des valeurs dans ces types...

data Nat where
  Zero :: Nat Z
  Succ :: Nat n -> Nat (S n)

... alors on peut les utiliser pour créer Fin comme nous l'avons fait dans Agda...

data Fin n where
  ZeroF :: Nat n -> Fin (S n)
  SuccF :: Nat n -> Fin n -> Fin (S n)

Et enfin, nous pouvons construire exactement deux valeurs de Fin (S (S Z))

*Fin> :t ZeroF (Succ Zero)
ZeroF (Succ Zero) :: Fin (S (S Z))

*Fin> :t SuccF (Succ Zero) (ZeroF Zero)
SuccF (Succ Zero) (ZeroF Zero) :: Fin (S (S Z))

Mais remarquez que nous avons perdu beaucoup de commodité, en plus de la inductive familles. Par exemple, nous ne pouvons pas utiliser les littéraux numériques dans nos types (même si c'est techniquement juste un truc dans Agda de toute façon), nous avons besoin de créer un "type de nat" et "valeur nat" et l'utilisation de la GADT pour les relier ensemble, et nous avions également trouver, dans le temps, que tout type de niveau de mathématiques est pénible dans Agda il peut être fait. En Haskell, il est incroyablement douloureux et souvent ne peuvent pas.

Par exemple, il est possible de définir un weaken notion dans Agda de l' Fin type

weaken : (n <= m) -> Fin n -> Fin m
weaken = ...

si nous fournissons un très intéressantes première valeur, preuve qu' n <= m ce qui nous permet d'intégrer "une valeur inférieure à n" dans l'ensemble de "valeurs inférieures m". On peut faire de même en Haskell, techniquement, mais il nécessite de lourds abus de classe de type prolog.

---

Donc, GADTs sont une ressemblance inductive familles dans dépendante tapé langues qui sont plus faibles et plus encombrant. Pourquoi voulons-nous qu'en Haskell, en premier lieu?

Fondamentalement parce que pas tous les types d'invariants nécessitent la puissance inductive familles d'exprimer et de GADTs optez pour un compromis entre l'expressivité, la capacité de mise en œuvre en Haskell, et l'inférence de type.

Quelques exemples utiles GADTs expressions sont des Arbres Rouge-Noir qui ne peut pas avoir le Rouge-Noir bien invalidé ou tout simplement tapé lambda calcul incorporée comme HOAS piggy-backing hors du Haskell type de système.

En pratique, vous pouvez également voir souvent GADTs utiliser pour leurs implicite existentielle contexte. Par exemple, le type

data Foo where
  Bar :: a -> Foo

implicitement se cache l' a type de variable à l'aide de quantification existentielle

> :t Bar 4 :: Foo

d'une manière qui est parfois pratique. Si vous regardez attentivement la CDA exemple de Wikipedia utilise cela pour l' a type de paramètre dans l' App constructeur. Pour exprimer cette déclaration sans GADTs serait un désastre existentiel, contextes, mais la GADT syntaxe fait naturel.

Answer 2

GADTs peut vous donner plus de type appliquée garantit que les ADTs. Par exemple, vous pouvez forcer un arbre binaire équilibré sur le type de système de niveau, comme dans cette mise en œuvre de 2-3 arbres:

{-# LANGUAGE GADTs #-}

data Zero
data Succ s = Succ s

data Node s a where
    Leaf2 :: a -> Node Zero a
    Leaf3 :: a -> a -> Node Zero a
    Node2 :: Node s a -> a -> Node s a -> Node (Succ s) a
    Node3 :: Node s a -> a -> Node s a -> a -> Node s a -> Node (Succ s) a

Chaque nœud a un type codé profondeur où tous ses feuilles résident. Un arbre est alors soit un arbre vide, une valeur singleton, ou un nœud d'une quelconque profondeur, encore une fois à l'aide de GADTs.

data BTree a where
    Root0 :: BTree a
    Root1 :: a -> BTree a
    RootN :: Node s a -> BTree a

Le type de système vous garantit que seuls équilibrée des nœuds peuvent être construits. Cela signifie que lors de la mise en œuvre des opérations comme l' insert sur ces arbres, vos type de code-vérifie seulement si son résultat est toujours un équilibre de l'arbre.

Answer 3

J'ai trouvé le "Prompt" monade (à partir de la "MonadPrompt" package) un outil très utile dans plusieurs endroits (avec l'équivalent du "Programme" de l'errance à partir de la "opérationnel" paquet. Combiné avec les GADTs (qui est la façon dont il était destiné à être utilisé), il vous permet de faire embedded langues est très bon marché et très souple. Il y avait un très bon article dans la Monade problème des lecteurs 15 appelé "les Aventures de Trois Monades" qui a eu une bonne introduction à l'Invite de la monade avec quelques réaliste GADTs.

Answer 4

J'aime l'exemple dans le GHC manuel. C'est une démonstration rapide d'un noyau GADT idée: que vous pouvez incorporer le type de système d'une langue que vous manipulez en Haskell type de système. Cela permet à votre Haskell fonctions à assumer, et les oblige à préserver, que l'arbre de syntaxe correspondent bien tapé des programmes.

Lorsque nous définissons Term, il n'a pas d'importance ce que les types que nous avons choisi. Nous pourrions écrire

data Term a where
  ...
  IsZero :: Term Char -> Term Char

ou

  ...
  IsZero :: Term a -> Term b

et la définition de l' Term seraient encore soumis.

C'est seulement une fois que nous voulons calculer sur Term, comme dans la définition d' eval, que les types de question. Nous avons besoin de nous

  ...
  IsZero :: Term Int -> Term Bool

parce que nous avons besoin de notre appel récursif à l' eval de retour d'un Int, et nous voulons, à son tour, de retour d'un Bool.

Answer 5

C'est une réponse courte, mais consulter le Haskell Wikibook. Il vous guide à bien un GADT pour un bien tapé arborescence d'expression, ce qui est un assez canonique exemple: http://en.wikibooks.org/wiki/Haskell/GADT

GADTs sont également utilisés pour la mise en œuvre de l'égalité de traitement: http://hackage.haskell.org/package/type-equality. Je ne peux pas trouver le bon document de référence pour cette désinvolture -- cette technique a fait son chemin bien dans le folklore maintenant. Il est très bien utilisé, cependant, Oleg est tapé sans étiquette choses. Voir, par exemple, la section sur les tapées de compilation dans les GADTs. http://okmij.org/ftp/tagless-final/#tc-GADT