uso del mundo real del GADT
https://stackoverflow.com/questions/3859200
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
¿Cómo hago uso de Generalizada algebraica Tipo de datos?
El ejemplo dado en la Haskell wikilibro es demasiado corta como para darme una idea de las posibilidades reales de GADT.
Solución
he encontrado la mónada "sistema" (del paquete "MonadPrompt"), una herramienta muy útil en varios lugares (junto con el equivalente mónada "Programa" del paquete "operativo". En combinación con GADTs (que es como se estaba destinado a ser utilizado), que le permite realizar idiomas incrustados muy barata y muy flexible. Hubo un artículo bastante buena en el tema mónada lector 15 llamado 'aventuras en tres mónadas' que tenía una buena introducción a la mónada Prompt junto con algunos GADTs realistas.
Otros consejos
GADTs son aproximaciones débiles de las familias inductivos de forma dependiente mecanografiadas idiomas, de modo que vamos a comenzar en su lugar.
familias inductivos son el método de introducción de núcleo tipo de datos en un lenguaje dependiente de tecleado. Por ejemplo, en Agda se definen los números naturales como esto
data Nat : Set where
zero : Nat
succ : Nat -> Nat
que no es muy lujoso, es esencialmente lo mismo que la definición Haskell
data Nat = Zero | Succ Nat
y de hecho en GADT Sintaxis de la forma Haskell es aún más similares
{-# LANGUAGE GADTs #-}
data Nat where
Zero :: Nat
Succ :: Nat -> Nat
Así que, a primera vista se podría pensar GADTs son sintaxis extra sólo ordenada. Eso es sólo la punta del iceberg sin embargo.
Agda tiene capacidad para representar todo tipo de tipos desconocidos y extraños a un programador Haskell. A simple es el tipo de conjuntos finitos. Este type se escribe así Fin 3 y representa la Set de números {0, 1, 2}. Del mismo modo, Fin 5 representa el conjunto de números {0,1,2,3,4}.
Esto debería ser bastante raro en este punto. En primer lugar, nos estamos refiriendo a un tipo que tiene una serie regular como un parámetro "tipo". En segundo lugar, no está claro lo que significa para Fin n para representar el conjunto {0,1...n}. En bienes Agda que nos gustaría hacer algo más potente, pero basta decir que podemos definir una función contains
contains : Nat -> Fin n -> Bool
contains i f = ?
Ahora bien, esto es extraño otra vez, porque la definición de "natural" de contains sería algo así como i < n, pero n es un valor que sólo existe en el Fin n tipo y que no debería ser capaz de cruzar ese tan fácilmente. Si bien resulta que la definición no es tan sencillo, esto es exactamente el poder que las familias han inductivos en forma dependiente mecanografiadas lenguajes que introducir los valores que dependen de sus tipos y tipos que dependen de sus valores.
Podemos examinar de qué se trata Fin que le da esa propiedad mirando a su definición.
data Fin : Nat -> Set where
zerof : (n : Nat) -> Fin (succ n)
succf : (n : Nat) -> (i : Fin n) -> Fin (succ n)
Esto toma un poco de trabajo de entender, así como un ejemplo permite tratar la construcción de un valor de la Fin 2 tipo. Hay algunas maneras de hacer esto (de hecho, vamos a encontrar que hay exactamente 2)
zerof 1 : Fin 2
zerof 2 : Fin 3 -- nope!
zerof 0 : Fin 1 -- nope!
succf 1 (zerof 0) : Fin 2
Esto nos deja ver que hay dos habitantes y también demuestra un poco de cómo se produce el tipo de cálculo. En particular, el bit (n : Nat) en el tipo de zerof refleja el real valor n arriba en el tipo que nos permite formar Fin (n+1) para cualquier n : Nat. Después de que utilizamos aplicaciones repetidas de succf para incrementar nuestros valores Fin arriba en el índice del tipo correcto de la familia (número natural que indexa el Fin).
Lo que ofrece estas capacidades? En honor a la verdad hay muchas diferencias de entre una familia de inducción dependiente de tecleado y una Haskell ADT regular, pero nos podemos centrar en el exacto que es más relevante para la comprensión de GADTs.
En GADTs y familias inductivas se obtiene una oportunidad para especificar el exacta tipo de sus constructores. Esto podría ser aburrido
data Nat where
Zero :: Nat
Succ :: Nat -> Nat
O, si tenemos un tipo más flexible, indexada podemos elegir diferentes, más interesante tipos de retorno
data Typed t where
TyInt :: Int -> Typed Int
TyChar :: Char -> Typed Char
TyUnit :: Typed ()
TyProd :: Typed a -> Typed b -> Typed (a, b)
...
En particular, estamos abusando de la capacidad de modificar el tipo de retorno basado en el especialmente constructor de datos utilizado. Esto nos permite reflexionar alguna información de valor hacia el tipo y producir más finamente especificado (Fibered) mecanografiado.
¿Qué podemos hacer con ellos? Bueno, con un poco de grasa del codo que puede Fin productos en Haskell . Sucintamente se requiere que se define una noción de productos naturales en los tipos
data Z
data S a = S a
> undefined :: S (S (S Z)) -- 3
... luego un GADT para reflejar los valores arriba en esos tipos ...
data Nat where
Zero :: Nat Z
Succ :: Nat n -> Nat (S n)
... entonces podemos utilizar éstos para construir Fin tanto como lo hicimos en Agda ...
data Fin n where
ZeroF :: Nat n -> Fin (S n)
SuccF :: Nat n -> Fin n -> Fin (S n)
Y por último podemos construir exactamente dos 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))
Pero aviso que hemos perdido una gran comodidad durante las familias inductivas. Por ejemplo, no podemos usar los literales numéricos regulares en nuestros tipos (aunque eso es técnicamente sólo un truco en Agda de todos modos), tenemos que crear una separada "tipo de NAT" y "valor nat" y utilizar el GADT vincularlos, y también nos encontramos, en el tiempo, mientras que las matemáticas de nivel tipo es dolorosa en Agda se puede hacer. En Haskell es increíblemente doloroso y con frecuencia no pueden.
Por ejemplo, es posible definir una noción weaken en tipo Fin de Agda
weaken : (n <= m) -> Fin n -> Fin m
weaken = ...
donde proporcionamos un primer valor muy interesante, una prueba de que n <= m lo que nos permite incrustar "un valor inferior a n" en el conjunto de "valores de menos de m". Podemos hacer lo mismo en Haskell, técnicamente, pero requiere pesada abuso del prólogo clase de tipo.
Así, GADTs son una semejanza de las familias inductivos en los idiomas de forma dependiente con tipo que están más débiles y más torpe. ¿Por qué los queremos en Haskell en el primer lugar?
Básicamente porque no todos los invariantes tipo requieren el poder de las familias inductivos para expresar y GADTs recogen un compromiso especial entre la expresividad, la aplicabilidad en Haskell, y la inferencia de tipos.
Algunos ejemplos de expresiones útiles son GADTs Rojo-Negro Los árboles que no pueden tener la propiedad rojo-Negro invalidado o simplemente-mecanografiada cálculo lambda incrustado como HOAS que llevan a cuestas apagado el sistema de tipos Haskell .
En la práctica, es frecuente que haya GADTs utilizan para su contexto existencial implícita. Por ejemplo, el tipo
data Foo where
Bar :: a -> Foo
oculta implícitamente la variable de tipo a mediante la cuantificación existencial
> :t Bar 4 :: Foo
de una manera que a veces es conveniente. Si se fijan bien el ejemplo HOAS de Wikipedia utiliza esto para el parámetro de tipo a en el constructor App. Para expresar esa declaración sin GADTs sería un lío de contextos existenciales, pero la sintaxis GADT hace que sea natural.
GADTs le puede dar garantías de tipo forzada más fuertes que los ADT regulares. Por ejemplo, puede obligar a un árbol binario que ser equilibrado en el nivel de sistema de tipos, como en esta implementación de 2-3 árboles :
{-# 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 nodo tiene una profundidad de tipo codificado donde todas sus hojas residen. Un árbol es entonces ya sea un árbol vacío, un valor único, o un nodo de profundidad no especificado, de nuevo usando GADTs.
data BTree a where
Root0 :: BTree a
Root1 :: a -> BTree a
RootN :: Node s a -> BTree a
El sistema de tipos que garantiza que los nodos solamente balanceadas se pueden construir.
Esto significa que cuando la ejecución de operaciones como insert en tales árboles, su
código de tipo controles sólo si su resultado es siempre un árbol de equilibrado.
I como en el ejemplo en el manual GHC . Es una demostración rápida de una idea central GADT: que se puede integrar el sistema de tipos de un idioma que están manipulando en el sistema de tipos de Haskell. Esto permite que sus funciones Haskell asumen, y las fuerzas que preserven, que los árboles de sintaxis corresponden a programas bien escritos.
Cuando definimos Term, no importa qué tipo elegimos. Podríamos escribir
data Term a where
...
IsZero :: Term Char -> Term Char
o
...
IsZero :: Term a -> Term b
y la definición de Term todavía pasar.
Es una sola vez queremos cómputo en Term, como en la definición de eval, que los tipos de materia. Tenemos que tener
...
IsZero :: Term Int -> Term Bool
porque necesitamos nuestra llamada recursiva a eval devolver un Int, y queremos regresar a su vez un Bool.
Esta es una respuesta corta, pero consulte la Haskell Wikibook. Se le guía a través de un GADT para un árbol de expresión así mecanografiados a, que es un ejemplo bastante canónica: http: //en.wikibooks.org/wiki/Haskell/GADT
GADTs también se utilizan para la aplicación de la igualdad Tipo: http://hackage.haskell.org/package / tipo igualdad. No puedo encontrar el papel adecuado de referencia para esta improvisada - esta técnica se ha abierto camino hasta bien entrado el folclore por ahora. Se utiliza bastante bien, sin embargo, en la materia sin etiqueta escrita a máquina de Oleg. Véase, por ejemplo la sección sobre compilación escrito en GADTs. http://okmij.org/ftp/tagless-final/#tc-GADT
