plusieurs types de paramètres dans les classes de type haskell

Question

J'essaie de faire une abstraction dans Haskell98 mais je ne sais pas comment le faire.

Ce que je veux faire est de définir une classe pour les types qui peuvent être convertis en listes.

toList :: a -> [b] 

Mais je ne sais pas comment définir une classe pour cette méthode. J'ai apporté les trois idées suivantes:

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

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

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

Le premier ne fonctionne pas parce que haskell98 ne permet pas de classes de paramètres multiples.

La seconde ne fonctionne pas car b dépend de a et ne peut pas être implémenté pour tout b.

La troisième ne fonctionne pas non plus parce que je ne sais pas comment instancier la classe avec un type où 'b' n'est pas le dernier paramètre de type.

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 

ou

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

Comment pourrais-je faire quelque chose comme ça?

Answer 1

Voir aussi Data.Foldable dans la bibliothèque standard, ce qui fournit une fonction toList pour toute instance Foldable. Foldable prend un peu de sophistication à instancier, mais ce serait une bonne pratique. En prime, votre type HTree est presque exactement le même que l'exemple d'instance dans la documentation.

De plus, je vous recommande de changer votre HTree à:

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

Et puis en utilisant HTree (a,b) au lieu de HTree a b. Cette version à un seul paramètre sera plus facilement composable avec des types et des instances standard, et elle ira plus au point de ce qui se passe puisqu'elle dépend des deux paramètres de la même manière.C'est aussi un Functor, et la définition d'une telle instance rendra ce type vraiment agréable à travailler.

Answer 2

Je recommanderais Type classes are not as useful as they first seem - si la classe putative n'a qu'une seule méthode d'interface, pensez plutôt à déclarer un type de fonction. Je suis aussi venu d'un arrière-plan OO et j'ai trouvé que je passais beaucoup trop de temps à essayer de faire en sorte que «classe» signifie ce que je pensais que cela signifiait, alors que j'aurais dû utiliser des «données».

Il est beaucoup plus simple d'écrire la fonction toList puis de la «soulever» pour fonctionner sur votre structure de données. En fait, le célèbre Yet Another Haskell Tutorial fait l'objet d'un vaste exercice montrant comment cela est fait, et utilise un arbre binaire comme exemple. Ce qui est génial, c'est de distinguer ce qui est important - la structure du type de données, pas l'implémentation de toList '- donc une fois que l'ascenseur est fait pour effectuer' traversée du type de données ', vous pouvez utiliser l'ascenseur pour faire n'importe quoi - toList, imprimer, peu importe. La prise en charge de toList n'est pas la partie importante de la structure de données. Elle ne doit donc pas figurer dans une déclaration de classe. La partie importante concerne la façon de parcourir la structure de données.

Answer 3

Vous souhaitez probablement choisir la dernière option pour la classe ToList et créer l'instance (HTree a) de ToList. Puis toList a le type (HTree a b) -> [b], pas par exemple (HTree a b) -> [(a,b)]. Je suppose que vous pensez a comme "clé" et b comme type de "valeur".

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]