parámetros de tipos múltiples en las clases de tipo haskell

Question

Estoy tratando de hacer algo de abstracción en Haskell98 pero no sé cómo hacerlo.

Lo que quiero hacer es definir una clase para los tipos que se pueden convertir en listas.

toList :: a -> [b] 

Pero no sé cómo definir una clase para este método. Planteé las siguientes tres ideas:

class ToList a b where 
    toList :: a -> [b] 

class ToList a where 
    toList :: a -> [b] 

class ToList a where 
    toList :: a b -> [b] 

La primera no funciona porque Haskell98 no permite múltiples clases de parámetros.

El segundo no funciona porque b depende de ay no se puede implementar para cada b.

El tercero tampoco funciona porque no sé cómo instanciar la clase con un tipo donde 'b' no es el último parámetro de tipo.

data HTree a b = Nil | Node a b (HTree a b) (HTree a b) 

toList Nil = [] 
toList Node x y l r = toList l ++ [(x,y)] ++ toList r 

o

toList Nil = [] 
toList Node x y l r = toList l ++ [x] ++ toList r 

¿Cómo iba a hacer algo así?

Answer 1

Consulte también Data.Foldable en la biblioteca estándar, que proporciona una función de toList para cualquier Foldable ejemplo. Foldable requiere un poco de sofisticación para crear instancias, pero sería una buena práctica. Como extra, su tipo HTree es casi exactamente igual a la instancia de ejemplo en la documentación.

Además, recomiendo cambiar su HTree a:

data HTree a = Nil | Node a (HTree a) (HTree a) 

Y a continuación, utilizando HTree (a,b) en lugar de HTree a b. Esta versión de un solo parámetro será más fácil de componer con tipos e instancias estándar, y llega más al punto de lo que está sucediendo, ya que depende de ambos parámetros de la misma manera.También es un Functor, y la definición de dicha instancia hará que este tipo sea realmente agradable para trabajar.

Answer 2

Recomendaría Type classes are not as useful as they first seem - si la clase putativa tiene solo un método de interfaz, considere declarar un tipo de función en su lugar. También provengo de un fondo OO y descubrí que pasé demasiado tiempo tratando de hacer que "clase" significara lo que pensé que significaba, cuando realmente debería haber estado usando "datos".

Es mucho más fácil simplemente escribir la función toList 'y luego' levantarla 'para operar en su estructura de datos. De hecho, el aclamado Yet Another Haskell Tutorial realiza un ejercicio exhaustivo que muestra cómo se hace y usa un árbol binario como ejemplo. Lo mejor de hacer un levantamiento es que distingue lo que es importante: la estructura del tipo de datos, no la implementación de toList ', por lo que una vez que el levantamiento se realiza para' atravesar el tipo de datos ', puede usar el ascensor para hacer cualquier cosa: enumerar, imprimir, lo que sea. Respaldar toList no es la parte importante de la estructura de datos, por lo que no debe estar en una declaración de clase; la parte importante es cómo atravesar la estructura de datos.

Answer 3

Es probable que desee elegir la última opción para la lista de la clase, y hacer la instancia (HTree a) de ToList. Entonces toList tiene tipo (HTree a b) -> [b], no por ejemplo (HTree a b) -> [(a,b)]. Supongo que estás pensando en un tipo de "clave" yb como de "valor".

class ToList a where 
    toList :: a b -> [b] 

data HTree a b = Nil | Node a b (HTree a b) (HTree a b) 

instance ToList (HTree a) where 
    toList Nil = [] 
    toList (Node x y l r) = toList l ++ [y] ++ toList r 

test = toList (Node "a" 1 (Node "b" 2 Nil Nil) Nil) 
-- test == [2,1]