Uso real do GADT
https://stackoverflow.com/questions/3859200
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Como faço uso do tipo de dados algébricos generalizados?
O exemplo dado no Wikilivro de Haskell é demasiado curto para me dar uma ideia das reais possibilidades do GADT.
Solução
Eu encontrei a mônada "Prompt" (do pacote "Monadprompt") uma ferramenta muito útil em vários lugares (juntamente com o equivalente "Monad" do pacote "operacional". Combinado com Gadts (e é assim que se destinava a ser usado), ele permite que você faça idiomas incorporados de maneira muito barata e de maneira muito flexível. Havia um artigo muito bom no Monad Reader Edição 15 chamado "aventuras em três mônadas", que tiveram uma boa introdução à mônada rápida, juntamente com alguns gadões realistas.
Outras dicas
Os Gadts são aproximações fracas de famílias indutivas de idiomas digitados dependentemente - então vamos começar por lá.
As famílias indutivas são o método principal de introdução de dados de dados em um idioma digitado dependentemente. Por exemplo, na AGDA, você define os números naturais como este
data Nat : Set where
zero : Nat
succ : Nat -> Nat
O que não é muito chique, é essencialmente a mesma coisa que a definição de Haskell
data Nat = Zero | Succ Nat
e de fato na sintaxe de gadt, a forma haskell é ainda mais semelhante
{-# LANGUAGE GADTs #-}
data Nat where
Zero :: Nat
Succ :: Nat -> Nat
Então, à primeira vista, você pode pensar que os Gadts são apenas uma sintaxe extra. Essa é apenas a ponta do iceberg.
A AGDA tem capacidade para representar todos os tipos de tipos não familiares e estranhos para um programador Haskell. Um simples é o tipo de conjunto finito. este modelo está escrito como Fin 3 e representa o definir de números {0, 1, 2}. Da mesma maneira, Fin 5 representa o conjunto de números {0,1,2,3,4}.
Isso deve ser bastante bizarro neste momento. Primeiro, estamos nos referindo a um tipo que possui um número regular como um parâmetro "tipo". Segundo, não está claro o que significa para Fin n Para representar o conjunto {0,1...n}. No verdadeiro AGDA, faríamos algo mais poderoso, mas basta dizer que podemos definir um contains função
contains : Nat -> Fin n -> Bool
contains i f = ?
Agora isso é estranho novamente porque a definição "natural" de contains seria algo como i < n, mas n é um valor que só existe no tipo Fin n E não devemos ser capazes de atravessar essa divisão tão facilmente. Embora a definição não seja tão direta, esse é exatamente o poder que as famílias indutivas digitam dependentemente idiomas - elas introduzem valores que dependem de seus tipos e tipos que dependem de seus valores.
Podemos examinar o que se trata Fin Isso concede essa propriedade olhando para sua definição.
data Fin : Nat -> Set where
zerof : (n : Nat) -> Fin (succ n)
succf : (n : Nat) -> (i : Fin n) -> Fin (succ n)
Isso exige um pouco de trabalho para entender, então, como exemplo, vamos tentar construir um valor do tipo Fin 2. Existem algumas maneiras de fazer isso (na verdade, descobriremos que existem exatamente 2)
zerof 1 : Fin 2
zerof 2 : Fin 3 -- nope!
zerof 0 : Fin 1 -- nope!
succf 1 (zerof 0) : Fin 2
Isso nos permite ver que existem dois habitantes e também demonstra um pouco de como o computação do tipo acontece. Em particular, o (n : Nat) bit no tipo de zerof reflete o real valor n até o tipo que nos permite formar Fin (n+1) para qualquer n : Nat. Depois disso, usamos aplicações repetidas de succf para incrementar nosso Fin Valores até o índice familiar do tipo correto (número natural que indexa o Fin).
O que fornece essas habilidades? Com toda a honestidade, existem muitas diferenças entre uma família indutiva digitada dependentemente e um Haskell ADT regular, mas podemos nos concentrar no exato que é mais relevante para entender os Gadts.
Em Gadts e famílias indutivas, você tem a oportunidade de especificar o exato tipo de seus construtores. Isso pode ser chato
data Nat where
Zero :: Nat
Succ :: Nat -> Nat
Ou, se tivermos um tipo mais flexível e indexado, podemos escolher diferentes tipos de retorno mais interessantes
data Typed t where
TyInt :: Int -> Typed Int
TyChar :: Char -> Typed Char
TyUnit :: Typed ()
TyProd :: Typed a -> Typed b -> Typed (a, b)
...
Em particular, estamos abusando da capacidade de modificar o tipo de retorno com base no especial construtor de valor usado. Isso nos permite refletir algumas informações de valor no tipo e produzir mais especificados (fibra) digitados.
Então, o que podemos fazer com eles? Bem, com um pouco de graxa de cotovelo, podemos produzir Fin em Haskell. Sucintamente, é necessário que definimos uma noção de naturais nos tipos
data Z
data S a = S a
> undefined :: S (S (S Z)) -- 3
... então um gadt para refletir valores desses tipos ...
data Nat where
Zero :: Nat Z
Succ :: Nat n -> Nat (S n)
... então podemos usá -los para construir Fin Muito parecido com o AGDA ...
data Fin n where
ZeroF :: Nat n -> Fin (S n)
SuccF :: Nat n -> Fin n -> Fin (S n)
E finalmente podemos construir exatamente dois valores 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))
Mas observe que perdemos muita conveniência sobre as famílias indutivas. Por exemplo, não podemos usar literais numéricos regulares em nossos tipos (embora isso seja tecnicamente apenas um truque na AGDA de qualquer maneira), precisamos criar um "tipo NAT" e "Value Nat" separado e usar o gadt para vinculá -los, E também descobriríamos, com o tempo, que, embora o tipo de matemática seja doloroso na AGDA, isso pode ser feito. Em Haskell, é incrivelmente doloroso e muitas vezes não pode.
Por exemplo, é possível definir um weaken noção em AGDA Fin modelo
weaken : (n <= m) -> Fin n -> Fin m
weaken = ...
onde fornecemos um primeiro valor muito interessante, uma prova de que n <= m o que nos permite incorporar "um valor menor que n"no conjunto de" valores menos que m". Podemos fazer o mesmo em Haskell, tecnicamente, mas requer abuso pesado de próLo de classe de tipo.
Portanto, os Gadts são uma semelhança de famílias indutivas em idiomas digitados dependentemente que são cada vez mais fracos. Por que os queremos em Haskell em primeiro lugar?
Basicamente, porque nem todos os invariantes de tipo exigem que todo o poder das famílias indutivas expresse e os GADTs escolham um compromisso particular entre expressividade, implementabilidade em Haskell e inferência de tipo.
Alguns exemplos de expressões de Gadts úteis são Árvores vermelhas que não podem ter a propriedade vermelha-preta invalidada ou cálculo de lambda simplesmente tipado incorporado como bastão de porquinho do sistema do tipo Haskell.
Na prática, você também costuma ver o uso de GADTs para o seu contexto existencial implícito. Por exemplo, o tipo
data Foo where
Bar :: a -> Foo
esconde implicitamente o a Digite variável usando quantificação existencial
> :t Bar 4 :: Foo
de uma maneira que às vezes é conveniente. Se você olhar com cuidado, o exemplo hoas da Wikipedia usa isso para o a Tipo parâmetro no App construtor. Expressar essa afirmação sem Gadts seria uma bagunça de contextos existenciais, mas a sintaxe do gadt a torna natural.
Os Gadts podem oferecer garantias forçadas do tipo mais forte do que o ADTS regular. Por exemplo, você pode forçar uma árvore binária a ser equilibrada no nível do sistema de tipos, como em esta implementação do 2-3 árvores:
{-# 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
Cada nó tem uma profundidade codificada por tipo onde todas as suas folhas residem. Uma árvore é então uma árvore vazia, um valor de singleton ou um nó de profundidade não especificada, novamente usando os Gadts.
data BTree a where
Root0 :: BTree a
Root1 :: a -> BTree a
RootN :: Node s a -> BTree a
O sistema de tipos garante que apenas nós equilibrados possam ser construídos. Isso significa que ao implementar operações como insert Nessas árvores, o seu código verifica apenas se seu resultado for sempre uma árvore equilibrada.
Eu gosto do exemplo em o manual do GHC. É uma demonstração rápida de uma idéia do Gadt Core: que você pode incorporar o sistema de tipo de um idioma que está manipulando no sistema de tipos de Haskell. Isso permite que suas funções Haskell assumam e as obriga a preservar, que as árvores de sintaxe correspondam a programas bem titados.
Quando definimos Term, não importa quais tipos escolhemos. Nós poderíamos escrever
data Term a where
...
IsZero :: Term Char -> Term Char
ou
...
IsZero :: Term a -> Term b
e a definição de Term ainda passaria.
É só quando quisermos Calcule em Term, como em definir eval, que os tipos importam. Precisamos ter
...
IsZero :: Term Int -> Term Bool
Porque precisamos de nossa chamada recursiva para eval para devolver um Int, e queremos, por sua vez, retornar um Bool.
Esta é uma resposta curta, mas consulte o Haskell Wikibook.Ele orienta você em um GADT para uma árvore de expressão bem digitada, que é um exemplo bastante canônico: http://en.wikibooks.org/wiki/Haskell/GADT
GADTs também são usados para implementar igualdade de tipos: http://hackage.haskell.org/package/type-equality.Não consigo encontrar o artigo certo para fazer referência a isso de improviso - essa técnica já se tornou popular no folclore.É usado muito bem, entretanto, nas coisas sem tags digitadas por Oleg.Veja, por exemploa seção sobre compilação digitada em GADTs. http://okmij.org/ftp/tagless-final/#tc-GADT
