2010-01-11 3 views
5

Hice una función similar a array de numpy. Convierte listas para arrays, listas de listas a las matrices 2d, etc.familias de tipo Haskell y argumentos ficticios

funciona así:

ghci> arrFromNestedLists ["hello", "world"] :: Array (Int, (Int,())) Char 
array ((0,(0,())),(1,(4,()))) [((0,(0,())),'h'),((0,(1,())),'e'),((0,(2,())),'l'),((0,(3,())),'l'),((0,(4,())),'o'),((1,(0,())),'w'),((1,(1,())),'o'),((1,(2,())),'r'),((1,(3,())),'l'),((1,(4,())),'d')] 

(Int, (Int,())) y no (Int, Int) porque no sé de una manera programática para aumentar la longitud de una tupla (Pregunta lateral: ¿hay alguna manera?)

La codificación era incómoda y tuve que hacer una "solución alternativa" (pasando argumentos ficticios a las funciones) para que funcione. Me pregunto si hay una mejor manera.

Así que aquí está el código, interrumpido con los detalles de las soluciones feas:

{-# LANGUAGE FlexibleInstances, ScopedTypeVariables, TypeFamilies #-} 

type family ListOfIndex i a 
type instance ListOfIndex() a = a 
type instance ListOfIndex (Int, i) a = [ListOfIndex i a] 

class Ix i => ArrConv i where 
    acBounds :: a -> ListOfIndex i a -> (i, i) 
    acFlatten :: i -> ListOfIndex i a -> [a] 

acBounds "debería" ser :: ListOfIndex i a -> (i, i). Y de manera similar para acFlatten. Cada uno recibe una variable ficticia (undefined es siempre el valor dado) porque de lo contrario no podría conseguir que se compile :(

arrFromNestedLists :: forall i a. ArrConv i => ListOfIndex i a -> Array i a 
arrFromNestedLists lst = 
    listArray 
    (acBounds (undefined :: a) lst) 
    (acFlatten (undefined :: i) lst) 

Arriba está el muñeco undefined argumento que pasa en el trabajo. Narra la GHC qué instancia de ListOfIndex de usar.

instance ArrConv() where 
    acBounds _ = const ((),()) 
    acFlatten _ = (: []) 

Ésta función debería haber sido la función acBounds en una instancia de ArrConv, y está declarado fuera sólo porque necesito usar ScopedTypeVariables y no sé cómo puedo hacerlo de una función en una definición de instancia ...

acSucBounds 
    :: forall a i. ArrConv i 
    => a -> [ListOfIndex i a] -> ((Int, i), (Int, i)) 
acSucBounds _ lst = 
    ((0, inStart), (length lst - 1, inEnd)) 
    where 
    (inStart, inEnd) = acBounds (undefined :: a) (head lst) 

instance ArrConv i => ArrConv (Int, i) where 
    acBounds = acSucBounds 
    acFlatten _ = concatMap (acFlatten (undefined :: i)) 
+3

"No conozco una forma programática para aumentar la longitud de una tupla". No creo que puedas. Ese es un ejemplo perfecto de una función cuyo tipo depende de un valor. Sería fácil de hacer en un lenguaje dependiente de tipeo como 'Agda', pero imposible en Haskell. Tal vez podrías usar 'GADT' de alguna manera para darte un comportamiento dependiente, pero fuera de mi cabeza, no sé cómo. –

+0

Tal vez la plantilla Haskell puede ser útil: http://www.haskell.org/bz/thdoc.htm http://www.haskell.org/haskellwiki/Template_Haskell – primodemus

+0

@primodemus: Con TH podría hacer instancias para 'ArrConv' para arreglos de hasta 10 dimensiones, y usarían tuplas normales para los índices, lo cual es una mejora.Pero me gustaría que el límite sea arbitrario y que el código sea mucho menos legible. – yairchu

Respuesta

4

La razón de que los argumentos adicionales a acBounds y acFlatten son necesarios es que los tipos a y i no se pueden recuperar de ListOfIndex i a -> (i, i) y ListOfIndex i a -> [a] respectivamente. Una solución es combinar los dos métodos en un método acArgs del tipo ListOfIndex i a -> ((i, i), a). Ahora, el único problema es usarlo en la instancia de (Int, i) de una manera que evita que typechecker generalice demasiado su tipo, causando el mismo problema que antes (por ejemplo, no podemos simplemente usar fst . acArgs).

 
{-# LANGUAGE TypeFamilies, FlexibleInstances #-} 

import Data.Array 

type family ListOfIndex i a 
type instance ListOfIndex() a = a 
type instance ListOfIndex (Int, i) a = [ListOfIndex i a] 

class Ix i => ArrConv i where 
    acArgs :: ListOfIndex i a -> ((i, i), [a]) 

instance ArrConv() where 
    acArgs x = (((),()), [x]) 

instance ArrConv i => ArrConv (Int, i) where 
    acArgs lst = 
    (((0, inStart), (length lst - 1, inEnd)), args >>= snd) 
    where 
     args = map acArgs lst 
     (inStart, inEnd) = fst (head args) 

arrFromNestedLists :: ArrConv i => ListOfIndex i a -> Array i a 
arrFromNestedLists = uncurry listArray . acArgs 
+0

@Reid Barton: ¡Increíble! Gracias :) Refactoré su respuesta un poco (espero que no le importe): En lugar de pasar 'acArgs' a una función la hace monomórfica, ahora solo la usa en un solo lugar. – yairchu

+0

Ah, ya veo. Bonito. –

0

Si desea mantener acBounds y acFlatten separada, se puede añadir un type-level tag argument a ella, es decir acBounds tendrían tipo acBounds :: Proxy a -> ListOfIndex i a -> (i, i). Esto elimina la necesidad de los argumentos undefined, ya que solo puede pasarle (Proxy :: SomeConcreteType); y acBounds no tiene forma de extraer ninguna información de nivel de valor útil, ya que es isomorfo (de forma no tipada) para el tipo de unidad.

Cuestiones relacionadas