mehrere Typparameter in haskell type-Klassen

Question

Ich versuche, Abstraktion in Haskell98 zu tun, aber weiß nicht, wie es geht.

Was ich tun möchte, ist eine Klasse für Typen definieren, die in Listen umgewandelt werden können.

toList :: a -> [b] 

Aber ich weiß nicht, wie man eine Klasse für diese Methode definiert. Ich habe die folgenden drei Ideen angesprochen:

Die erste funktioniert nicht, weil Haskell98 mehrere Parameterklassen nicht zulässt.

Der zweite funktioniert nicht, weil b von a abhängt und nicht für jeden b implementiert werden kann.

Die dritte funktioniert auch nicht, weil ich nicht weiß, wie man die Klasse mit einem Typ instanziiert, wobei 'b' nicht der letzte Typparameter ist.

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 

oder

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

Wie würde ich so etwas tun?

Answer 1

Siehe auch Data.Foldable in der Standardbibliothek, die eine toList Funktion für jede Foldable Instanz zur Verfügung stellt. Foldable braucht ein bisschen Raffinesse, um instanziieren, aber es wäre eine gute Übung. Als Bonus entspricht Ihr Typ HTree fast genau der Beispielinstanz in der Dokumentation.

Zusätzlich empfehle ich das Ändern Ihrer HTree zu:

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

Und dann HTree (a,b) statt HTree a b verwenden. Diese Single-Parameter-Version lässt sich einfacher mit Standardtypen und -instanzen kombinieren und bringt mehr auf den Punkt, da sie von beiden Parametern auf die gleiche Weise abhängt.Es ist auch ein Functor, und die Definition einer solchen Instanz wird diesen Typ wirklich angenehm machen.

Answer 2

Ich würde empfehlen, Type classes are not as useful as they first seem - wenn die putative Klasse hat nur eine Schnittstelle Methode, in Betracht ziehen, stattdessen eine Funktion Typ. Ich kam auch von einem OO-Hintergrund und fand heraus, dass ich viel zu viel Zeit damit verbracht habe, "Klasse" zu meinen, was ich dachte, dass es bedeutete, dass ich wirklich "Daten" hätte verwenden sollen.

Es ist viel einfacher, einfach Ihre toList-Funktion zu schreiben und sie dann zu "heben", um Ihre Datenstruktur zu bearbeiten. In der Tat, die gefeierten Yet Another Haskell Tutorial durchläuft eine umfangreiche Übung zeigt, wie es gemacht wird, und verwendet einen binären Baum als Beispiel. Das Tolle an einem Lift ist, dass er unterscheidet, was wichtig ist - die Struktur des Datentyps, nicht die Implementierung von toList "- sobald also der Lift ausgeführt wird, um den Datentyp zu durchlaufen, können Sie den Lift verwenden alles tun - toList, drucken, was auch immer. Die Unterstützung von toList ist nicht der wichtige Teil der Datenstruktur, daher sollte sie nicht in einer Klassendeklaration enthalten sein - der wichtige Teil ist, wie die Datenstruktur durchlaufen wird.

Answer 3

Sie möchten wahrscheinlich die letzte Option für die Klasse ToList wählen und (HTree a) Instanz von ToList machen. Dann toList hat Typ (HTree a b) -> [b], nicht zum Beispiel (HTree a b) -> [(a,b)]. Ich nehme an, Sie denken an einen "Schlüssel" und einen "Wert" -Typ.

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]