Erstellen von polymorphen rekursiven Typen in Haskell

Question

Ich versuche, einen Baumtyp in Haskell zu erstellen. Ich habe diesen einfachen Datenkonstruktor verwendet, um einen Baum zu speichern, in dem jeder Knoten entweder leer sein kann, ein Blatt sein kann, das eine ganze Zahl enthält, oder ein Knoten sein soll, der eine ganze Zahl mit Verzweigungen zu zwei anderen Blättern/Knoten enthält. Hier ist, was ich habe:

module Tree (Tree(Empty, Leaf, Node)) where 

data Tree = Empty 
| Leaf Int 
| Node Tree Int Tree 
deriving(Eq, Ord, Show, Read) 

Das funktioniert gut, aber ich brauche, um den Baumtyp polymorphen zu machen. Ich habe versucht, "Int" einfach durch "a" zu ersetzen, aber es scheint nicht zu funktionieren. Gibt es ein anderes System, um diese Typen polymorph zu machen?

Answer 1

In der Tat können Sie dem Baum einen Typparameter geben, wie in Alexander Poluektov Beispiel. Einfach genug! Aber warum dort aufhören? Wir können ein bisschen mehr Spaß haben als nur das. Anstatt nur eine rekursive Struktur mit polymorphen Daten, können Sie die Struktur polymorph in der Rekursion selbst machen!

Zuerst die Referenzen des Baums auf sich selbst abstrahieren, in der gleichen Weise wie die Referenzen auf Int abstrahieren, die rekursiven Referenzen durch einen neuen Parameter t ersetzen. Das lässt uns mit dieser eher vage Datenstruktur:

data TNode t a = Empty 
       | Leaf a 
       | Node (t a) a (t a) 
       deriving (Eq, Ord, Show, Read) 

Dies wurde als TNode hier umbenannt worden, weil es nicht wirklich ein Baum ist mehr; nur ein einfacher Datentyp. Nun, die ursprüngliche Rekursion zu erholen und einen Baum erstellen, drehen wir TNode um und ihn an sich selbst:

newtype Tree a = Tree (TNode Tree a) deriving (Eq, Ord, Show, Read) 

Jetzt können wir diese Tree rekursiv verwenden, aber leider auf Kosten von einigen zusätzlichen Wortschwall, etwa so:

Tree (Node (Tree Empty) 5 (Tree (Leaf 2))) 

Also, was gibt uns das, neben der zusätzlichen Typisierung, fragen Sie? Einfach, dass wir den Grundbaum Struktur von den Daten, die er enthält, und der Methode, mit der die Daten konstruiert und verarbeitet werden, getrennt haben, was es uns erlaubt, allgemeinere Funktionen zu schreiben, um mit dem einen oder anderen Aspekt umzugehen.

Zum Beispiel können wir Bäume mit zusätzlichen Daten schmücken oder zusätzliche Teile in den Baum einfügen, ohne die generischen Baumfunktionen zu beeinträchtigen.Sagen wir einen Namen zu jedem Stück des Baumes geben wollten:

toList f t = toList' f (f t) [] 
    where toList' f (Node t1 x t2) xs = toList' f (f t1) (x : toList' f (f t2) xs) 
      toList' f (Leaf x) xs = x:xs 
      toList' _ Empty xs = xs 

Bei einer Funktion der aktuellen TNode zu extrahieren aus:

newtype NameTree a = NameTree (String, TNode NameTree a) deriving (Eq, Ord, Show, Read) 

Auf der anderen Seite können wir allgemeine Baum-Traversal-Logik schreiben eine rekursive Baum, können wir dies auf eine solche Struktur verwenden:

treeToList = toList (\(Tree t) -> t) 
nameTreeToList = toList (\(NameTree (_, t)) -> t) 

natürlich, das geht wahrscheinlich weit jenseits dessen, was Sie zu tun suchen, aber es ist ein schöner Geschmack davon, wie viel Polymorphismus und generischer Code Haskell erlaubt (nein, ermutigt) einen Programmierer zu erstellen.

Answer 2

data Tree a = Empty 
      | Leaf a 
      | Node (Tree a) a (Tree a) 

Answer 3

Ersetzen Int mit a ist der richtige Start, aber Sie müssen auch jedes Vorkommen von Baum mit Tree a ersetzen (das einklammern soweit erforderlich). Der data Tree Teil benötigt das a, um zu deklarieren, dass Tree ein Typargument namens a hat. Die Node Tree Int Tree muss bedeuten, dass die Teilbäume selbst vom Typ Tree a sind und nicht von einem anderen Treetyp.

Answer 4

Versuchen Sie ein wenig über Typkonstruktor Art zu lesen.

Wenn Sie einen polymorphen Typ abhängig von einigen Typvariablen haben, muss Ihr Typkonstruktor eine Art haben, die das widerspiegelt.

Zum Beispiel kann der Typkonstruktor MyBool definiert in:

data MyBool = False | True 

ist von Art *. Das heißt, mein Typkonstruktor MyBool nimmt keine Parameter an, um einen Typ zu definieren. Wenn ich schreibe, so etwas wie:

data MyMaybe a = Just a | Nothing 

dann dem Typkonstruktor MyMaybe Art *->* hat, das heißt, es muss ein „Typen Argument“ eine Art zu definieren.

Sie können vergleichen, wie Typkonstruktorarten mit dem Datenkonstruktortyp arbeiten. Der Datenkonstruktor True kann ein Datenwert des Typs MyBool sein, ohne Parameter. Aber die Daten Konstruktor Just ist ein Wert vom Typ a -> MyMaybe a, wird es betreibt über einen Wert vom Typ a einem anderen Wert des Typs zu schaffen MyMaybe a - wie zum Beispiel in dieser GHCI Sitzung:

> let x = Just 5 
> :t x 
Maybe Int 
> let y = Just 
> :t y 
a -> Maybe a 

Dies ist mehr oder weniger vergleichbar mit dem Unterschied zwischen den Typkonstruktoren MyMaybe und MyBool. Mit MyBool haben Sie die Art *, Sie können Werte mit dem Typ MyBool haben, ohne zusätzlichen Typparameter. Aber MyMaybe ist kein Typ für sich - es ist ein Typkonstruktor, der auf einen Typ "operiert", um einen anderen Typ zu erstellen, das heißt, seine Art ist * -> *. Und so können Sie nicht haben Dinge vom Typ MyMaybe, aber die Dinge vom Typ MyMaybe Int, MyMaybe Bool, MyMaybe [Int], etc ...

Wenn ein Typ ist polymorph, es muss zumindest die Art * -> * sein, aber es könnte *->*->* sein, wie in:

data MyPair a b = Pair a b 

MyPair benötigt zwei Typparameter einen Typ zu definieren, wie in MyPair Int Bool, MyPair Int Int, etc ...

Die Take-Home-Nachricht ist so etwas wie: Da Wertkonstruktoren Typ-Signaturen haben, Typkonstruktoren haben Art-Signaturen, und dies muss berücksichtigt werden, wenn Sie einen neuen Datentyp planen.

http://en.wikipedia.org/wiki/Kind_%28type_theory%29