Utilizzo nel mondo reale di GADT
https://stackoverflow.com/questions/3859200
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Come posso utilizzare il tipo di dati algebrico generalizzato?
L'esempio riportato nel Wikibook di Haskell è troppo breve per darmi un'idea delle reali possibilità di GADT.
Soluzione
ho trovato la monade "Prompt" (dal pacchetto "MonadPrompt") uno strumento molto utile in diversi punti (insieme con l'equivalente monade "Programma" dal pacchetto "operativa". In combinazione con GADTs (che è come è stato destinato ad essere utilizzato), che consente di effettuare lingue incorporati molto a buon mercato e molto flessibile. C'era un bel articolo bene nel problema monade Reader 15 chiamato 'Adventures in tre monadi' che aveva una buona introduzione alla monade Prompt insieme ad alcuni GADTs realistici.
Altri suggerimenti
I GADT sono approssimazioni deboli di famiglie induttive di linguaggi tipizzati in modo dipendente, quindi cominciamo da lì.
Le famiglie induttive sono il metodo principale di introduzione del tipo di dati in un linguaggio tipizzato in modo dipendente.Ad esempio, in Agda definisci i numeri naturali in questo modo
data Nat : Set where
zero : Nat
succ : Nat -> Nat
il che non è molto sofisticato, è essenzialmente la stessa cosa della definizione Haskell
data Nat = Zero | Succ Nat
e in effetti nella sintassi GADT la forma Haskell è ancora più simile
{-# LANGUAGE GADTs #-}
data Nat where
Zero :: Nat
Succ :: Nat -> Nat
Quindi, a prima vista potresti pensare che i GADT siano solo una sintassi extra ordinata.Questa però è solo la punta dell'iceberg.
Agda ha la capacità di rappresentare tutti i tipi di tipi non familiari e strani per un programmatore Haskell.Uno semplice è il tipo di insiemi finiti.Questo tipo è scritto così Fin 3 e rappresenta il impostato di numeri {0, 1, 2}.Allo stesso modo, Fin 5 rappresenta l'insieme dei numeri {0,1,2,3,4}.
Questo dovrebbe essere piuttosto bizzarro a questo punto.Innanzitutto, ci riferiamo a un tipo che ha un numero regolare come parametro "tipo".In secondo luogo, non è chiaro a cosa significhi Fin n per rappresentare l'insieme {0,1...n}.Nella vera Agda faremmo qualcosa di più potente, ma basti dire che possiamo definire a contains funzione
contains : Nat -> Fin n -> Bool
contains i f = ?
Ora, anche questo è strano perché la definizione "naturale" di contains sarebbe qualcosa di simile i < n, Ma n è un valore che esiste solo nel tipo Fin n e non dovremmo essere in grado di superare questo divario così facilmente.Anche se la definizione non è così semplice, questo è esattamente il potere che le famiglie induttive hanno nei linguaggi tipizzati in modo dipendente: introducono valori che dipendono dai loro tipi e tipi che dipendono dai loro valori.
Possiamo esaminare di cosa si tratta Fin che gli conferisce quella proprietà guardando la sua definizione.
data Fin : Nat -> Set where
zerof : (n : Nat) -> Fin (succ n)
succf : (n : Nat) -> (i : Fin n) -> Fin (succ n)
questo richiede un po' di lavoro per essere compreso, quindi come esempio proviamo a costruire un valore del tipo Fin 2.Ci sono alcuni modi per farlo (in effetti, scopriremo che ce ne sono esattamente 2)
zerof 1 : Fin 2
zerof 2 : Fin 3 -- nope!
zerof 0 : Fin 1 -- nope!
succf 1 (zerof 0) : Fin 2
Questo ci permette di vedere che ci sono due abitanti e dimostra anche un po' come avviene il calcolo del tipo.In particolare, il (n : Nat) un po' nel tipo di zerof riflette la realtà valore n nel tipo che ci permette di formarci Fin (n+1) per ogni n : Nat.Successivamente utilizziamo applicazioni ripetute di succf per incrementare il nostro Fin valori nell'indice della famiglia di tipi corretto (numero naturale che indicizza il file Fin).
Cosa fornisce queste capacità?In tutta onestà ci sono molte differenze tra una famiglia induttiva tipizzata in modo dipendente e un normale ADT Haskell, ma possiamo concentrarci su quello esatto che è più rilevante per comprendere i GADT.
Nei GADT e nelle famiglie induttive hai l'opportunità di specificare il esatto tipo dei tuoi costruttori.Potrebbe essere noioso
data Nat where
Zero :: Nat
Succ :: Nat -> Nat
Oppure, se disponiamo di una tipologia più flessibile e indicizzata, possiamo scegliere tipologie di rendimento diverse e più interessanti
data Typed t where
TyInt :: Int -> Typed Int
TyChar :: Char -> Typed Char
TyUnit :: Typed ()
TyProd :: Typed a -> Typed b -> Typed (a, b)
...
In particolare, stiamo abusando della possibilità di modificare il tipo di reso in base al file particolare costruttore di valore utilizzato.Ciò ci consente di riflettere alcune informazioni sul valore nel tipo e di produrre caratteri più finemente specificati (fibrati).
Quindi cosa possiamo fare con loro?Bene, con un po' di olio di gomito possiamo farlo produrre Fin ad Haskell.In breve, ciò richiede di definire una nozione di naturali in tipi
data Z
data S a = S a
> undefined :: S (S (S Z)) -- 3
...quindi un GADT per riflettere i valori in questi tipi...
data Nat where
Zero :: Nat Z
Succ :: Nat n -> Nat (S n)
...quindi possiamo usarli per costruire Fin proprio come abbiamo fatto ad Agda...
data Fin n where
ZeroF :: Nat n -> Fin (S n)
SuccF :: Nat n -> Fin n -> Fin (S n)
E infine possiamo costruire esattamente due valori di 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))
Ma notiamo che abbiamo perso molta convenienza rispetto alle famiglie induttive.Ad esempio, non possiamo utilizzare valori letterali numerici regolari nei nostri tipi (anche se tecnicamente è comunque solo un trucco in Agda), dobbiamo creare un "tipo nat" e un "valore nat" separati e utilizzare GADT per collegarli insieme, e scopriremmo anche, col tempo, che sebbene la matematica a livello di tipo sia dolorosa ad Agda, può essere fatta.In Haskell è incredibilmente doloroso e spesso non è possibile.
Ad esempio, è possibile definire a weaken nozione in Agda Fin tipo
weaken : (n <= m) -> Fin n -> Fin m
weaken = ...
dove forniamo un primo valore molto interessante, una prova di ciò n <= m che ci consente di incorporare "un valore inferiore a n" nell'insieme dei "valori inferiori a m".Possiamo fare lo stesso in Haskell, tecnicamente, ma richiede un pesante abuso del prologo della classe di tipo.
Quindi, i GADT sono una somiglianza delle famiglie induttive nelle lingue tipizzate in modo dipendente che sono più deboli e goffe.Innanzitutto perché li vogliamo ad Haskell?
Fondamentalmente perché non tutte le invarianti di tipo richiedono la piena potenza delle famiglie induttive per esprimersi e i GADT scelgono un particolare compromesso tra espressività, implementabilità in Haskell e inferenza di tipo.
Alcuni esempi di espressioni GADT utili sono Rosso-Nero Alberi per i quali non è possibile invalidare la proprietà Rosso-Nero O calcolo lambda di tipizzazione semplice incorporato come HOAS che si appoggia al sistema di tipi Haskell.
In pratica, spesso vedi anche i GADT utilizzare per il loro contesto esistenziale implicito.Ad esempio, il tipo
data Foo where
Bar :: a -> Foo
nasconde implicitamente il a variabile di tipo utilizzando la quantificazione esistenziale
> :t Bar 4 :: Foo
in un modo che a volte è conveniente.Se guardi attentamente l'esempio HOAS di Wikipedia usa questo per il a digitare il parametro nel file App costruttore.Esprimere questa affermazione senza GADT sarebbe un pasticcio di contesti esistenziali, ma la sintassi GADT lo rende naturale.
GADTs può dare di tipo forzata garanzie più forti di ADT regolari. Ad esempio, è possibile forzare un albero binario essere bilanciato a livello di sistema di tipo, come in questa implementazione di alberi 2-3 :
{-# 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
Ogni nodo ha una profondità tipo codificato dove tutte le foglie risiedono. Un albero è poi sia un albero vuoto, un valore singleton, o un nodo di profondità specificato, nuovamente utilizzando GADTs.
data BTree a where
Root0 :: BTree a
Root1 :: a -> BTree a
RootN :: Node s a -> BTree a
Il sistema di tipo garantisce che i nodi solo in equilibrio possono essere costruiti.
Ciò significa che quando le operazioni di implementazione come insert su tali alberi, la vostra
Codice tipo di controlli solo se il suo risultato è sempre un albero bilanciato.
Mi piace l'esempio in manuale GHC . Si tratta di una demo veloce di un nucleo GADT idea: che è possibile incorporare il sistema tipo di lingua che si sta manipolando nel sistema dei tipi di Haskell. In questo modo le funzioni Haskell assumono, e li costringe a preservare, che gli alberi di sintassi corrispondono a programmi ben tipizzati-.
Quando definiamo Term, non importa quali tipi che scegliamo. Potremmo scrivere
data Term a where
...
IsZero :: Term Char -> Term Char
o
...
IsZero :: Term a -> Term b
e la definizione di Term sarebbe ancora passare attraverso.
E 'solo una volta che vogliamo di calcolo on Term, come ad esempio nella definizione eval, che i tipi di materia. Abbiamo bisogno di avere
...
IsZero :: Term Int -> Term Bool
perché abbiamo bisogno della nostra chiamata ricorsiva per eval per restituire un Int, e vogliamo a sua volta restituire un Bool.
Questa è una risposta breve, ma consultare il Haskell Wikibook. Esso si cammina se un GADT per un albero di espressione ben tipato, che è un esempio abbastanza canonica: http: //en.wikibooks.org/wiki/Haskell/GADT
GADTs sono utilizzati anche per implementare tipo uguaglianza: http://hackage.haskell.org/package / tipo-uguaglianza . Non riesco a trovare la carta giusta per riferimento per questo estemporaneo - questa tecnica si è fatto strada anche nel folklore ormai. E 'utilizzato molto bene, tuttavia, roba senza tag tipizzato di Oleg. Vedi, ad esempio, la sezione compilation digitato in GADTs. http://okmij.org/ftp/tagless-final/#tc-GADT
