Parametrizar tipos por enteros en Haskell

Estoy tratando de hacer algunos tipos de Haskell que están parametrizados no por tipos sino por elementos de un tipo, específicamente enteros. Por ejemplo, un vector (álgebra lineal) en R^2 y un vector en R^3 son diferentes objetos tipados. Específicamente, estoy escribiendo un árbol K-D en Haskell y quiero parametrizar mi estructura de datos por un entero positivo para que un árbol 3-D y un árbol 4-D tengan un tipo diferente.Parametrizar tipos por enteros en Haskell

He intentado parametrizar mi árbol por tuplas, pero no parecía estar yendo a ninguna parte (y parece poco probable que esto pueda ser llevado a cabo, especialmente porque no parece que triples o algo más grande sean incluso funtores (y no sé de ninguna manera decir como, ejemplo HomogeneousTuple a => Functor a) Quiero hacer algo como esto:.

data (TupleOfDoubles a) => KDTree a b = ... ---so in a 3DTree a is (Double,Double,Double)

que sería bueno, o algo como esto sería igualmente bueno

data KDTree Int a = ... -- The Int is k, so KDTree has kind Int -> * -> *

¿Alguien sabe si alguno de estos los efectos son factibles o razonables?

Gracias -Joseph

Fuente

2011-09-01 Joseph Victor

Una nota al margen, es posible que le interese parte de la literatura sobre tipos dependientes, que es un tipo más general de funciones de valores a tipos: Disfruté http://www.cse.chalmers.se/~peterd /papers/DependentTypesAtWork.pdf –

gracias Amos, eso parece algo que puedo usar –

Hay una extensión GHC está trabajando llamada TypeNats, lo que sería exactamente lo que quiere. Sin embargo, el hito para eso actualmente se establece en 7.4.1 de acuerdo con the ticket, por lo que será un poco de espera.

Hasta que la extensión esté disponible, lo único que puede hacer es codificar la dimensión utilizando los tipos. Por ejemplo algo en este sentido podría funcionar:

{-# LANGUAGE ScopedTypeVariables #-} 
class MyTypeNat a where 
    toInteger :: a -> Integer 

data Zero 
data Succ a 

instance MyTypeNat Zero where 
    toInteger _ = 0 

instance MyTypeNat a => MyTypeNat (Succ a) where 
    toInteger _ = toInteger (undefined :: a) + 1 

data KDTree a b = -- ... 

dimension :: forall a b. MyTypeNat a => KDTree a b -> Integer 
dimension = toInteger (undefined :: a)

La desventaja de un enfoque de este tipo es, por supuesto, que usted tiene que escribir algo como KDTree (Succ (Succ (Succ Zero))) Foo en lugar de KDTree 3 Foo.

Fuente

2011-09-01 07:38:17 sepp2k

Claro, pero entonces un tipo Three = Succ (Succ (Succ Zero)) ayudará. – Ingo

Nifty, gracias (Esto es un poco tonto, pero en realidad me encanta) –

Si solo va a utilizar números pequeños, podría codificarlos directamente: datos One/data Two/data Three/data Four - es más fácil de leer – firefrorefiddle

La respuesta de sepp2k muestra el enfoque básico para hacer esto. De hecho, mucho del trabajo ya se ha realizado.

paquetes de número de nivel de Tipo

Stuff codificaciones usando a nivel de tipo de números naturales (ejemplos)

Desafortunadamente algo como esto:

data KDTree Int a = ...

no es realmente posible. El tipo final (construido por KDTree) depende del valor del Int, que requiere una característica llamada tipos dependientes.Los idiomas como Agda y Epigram apoyan esto, pero no Haskell.

Fuente

2011-09-01 09:21:59

Gracias por eso. Vec parece ser el ejemplo más simple posible para mí para aprender cómo hacer esto. –

Sí, Vec es probablemente el más simple, luego dimensional. llvm y ForSyDe son más complejos, aunque creo que ambos básicamente implementan lo mismo que Vec. –

Parametrizar tipos por enteros en Haskell

Respuesta

Cuestiones relacionadas