Datentypen (Haskell)
Aus Infostudium Wiki
Ein (eigener) Datentyp in Haskell ist ein selbstdefinierter Typ, der aus einer Enumeration der erlaubten Werte dieses Typs besteht.
Inhaltsverzeichnis |
Allgemeine Definition
Vereinfacht kann man die Definition eines Datentyps Foo als folgende angeben
data Foo a b c ... = E1 | E2 a | E3 b | ...
Das ist aber keine sehr präzise Definition, eine exakte gibt es bei haskell.org.
Um sich die Datentypen "ansehen" zu können muss man einfach hinter die Deklaration deriving Show anfügen.
Klassisches Beispiel (B0)
Will man beispielsweise einen Wahrheitswert implementieren, so kann man diesen (parameterlosen Typ) einfach angeben als
data Wahrheitswert = Unwahr | Wahr
Das ist aber noch ziemlich langweilig, wenn man bedenkt, was noch alles möglich ist.
Nicht ganz so triviales Beispiel (B1.a)
Möchte man nun einen Stapel konstruieren der natürliche Zahlen speichert, kann man das sehr einfach mit diesen Datentypen machen. Ein Stapel ist entweder ein leerer Stapel, oder ein Datenelement und ein weiterer Stapel, daher kann man ihn rekursiv definieren als:
data Stapel = Leer | Stapelelement Int (Stapel)
Das heißt also, dass ein Stapel entweder leer ist (Datum "Leer") oder (repräsentiert durch den senkrechten Strich) ein Stapelelement ist, welches einen Wert (Int) und einen weiteren Stapel enhält (jener hat natürlich exakt die selben Eigenschafen). Gibt man nun in den Befehlszeilen Inerpreter folgendes ein:
Stapelelement 5 Leer
wird ein Stapel erzeugt der eine 5 enthält. Analog erzeugt
Stapelelement 5 (Stapelelement 6 Leer)
einen Stapel der oben eine 5 enthält und darunter eine 6.
B1.a in schön (B1)
Will man jetzt verschiedene Typen in Stapeln ablegen, müsste man ja jedesmal einen neuen Typ anlegen. Da das total umständlich ist, kann man den Stapel allgemein formulieren - schließlich benutzt er ja keinerlei der Eigenschaften einer Zahl. Ein allgemeiner Stapel hieße also
data Stapel a = Leer | Datenelement a (Stapel a)
Ein solcher Stapel kann alle möglichen Datentypen speichert, wenn man möchte sogar wiederum einen Stapel. Beispielsweise kann man folgende Belegungen wählen:
-- wie der zuvor definierte Stapel für Zahlen; Typ ist :: Stapel Int Datenelement 5 Leer -- ein Stapel der Wahrheitswerte speichert; Typ ist :: Stapel Wahrheitswert Datenelement Unwahr Leer -- ein Stapel der Stapel enhält welche Gleitkommazahlen enthalten; Typ ist :: Stapel (Stapel Float) Datenelement (Datenelement 1.6 (Datenelement 4.2 Leer)) (Datenelment (Datenelement 5.3 Leer) Leer)
Anderes Aussehen dieses Stapels
Ein solcher Stapel wird bereits von Haskell definiert und dürfte bereits bekannt sein; Die Liste! Diese ist in Wirklichkeit nämlich ein Stapel, da mann immer nur auf das oberste Element zugreifen kann.
data [a] = [] | a:[a]
Wie man sieht hat Haskell unser Stapel a schlicht [a] genannt. Den leeren Stapel hat es statt Leer als [] bezeichnet und den sog. Datenkonstruktor Datenelement hat es : genannt.
Komplexeres Beispiel (B2)
Eine weitere wichtige Datenstruktur ist der Baum. Diese Struktur lässt sich ebenso elegant formulieren.
- siehe Baum (Haskell)
Einschränken von Datentypen
Angenommen man möchte ein assoziatives Feld definieren, man möchte also, dass man einen Index angeben kann und man einen Wert zurückerhält. Also etwa in dieser Form:
data Assoziativ a b = Index a b
Um das ganze einfach zu halten ist hier nur ein Element angegeben und nicht die Liste die die Elemente enthält.
Eine solche Datenstrukur kann nur sinnvoll arbeiten, wenn der Index die Eigenschaft hat dass man ihn mit gegebenen Werten vergleichen kann; Angenommen man möchte den Wert bei Index x finden, dann könnte man etwa die folgende Funktion schreiben:
finde :: a -> [Assoziativ a b] -> [b]
finde x ((Index i y):ys) | x == i = [y]
| otherwise = finde x ys
finde _ _ = []
- (Anm.: Das wird Haskell in der Form noch nicht annehmen!)
- (Anm.: Dass eine Liste [b] und nicht einfach b "zurückgegeben" wird, liegt daran, dass man im Fehlerfall eine leere Liste zurückliefern kann.)
Wie man aber sieht, wird in der zweiten Zeile ein == verwendet. Das impliziert aber, dass das dort stehende x und das i vergleichbar sein sollen. Unser Stapel wäre zum beispiel ein Typ bei dem Haskell nicht wüsste wie er ihn vergleichen soll - er wäre aber bei dieser Deklaration ein gültiger Indexwert - das gilt es jetzt auszuschließen.
Typklassen
Dazu benutzt man die Einschränkung des Datentyps Assoziativ auf Typen für a, die verglichen werden können. Dafür könnte man eine Klasse Vergleichbar einführen, da dies verhältnismäßig kompliziert ist, bedienen wir uns der von Haskell vorgegebenen Klasse Eq. Diese Klasse enthält die Funktionen bzw. Operatoren == und /=, die benutzt werden um Typen zu vergleichen. Typen wie Int, Float, Bool oder auch [a] (falls a in Eq ist) sind in der Klasse Eq bzw. erben von ihr. Um diese Einschränkung formal zu notieren, benutzt man folgende Syntax:
... (Eq a) => ...
Man kann dies lesen als; aus a in Eq folgt ... aber auch als für a aus Eq definiere ...
- Dies wird klarer wenn man es in Aktion sieht.
Typklassen zur Einschränkung von Datentypen
Der assoziative Typ muss also nun dergestalt eingeschränkt werden, dass der Index vergleichbar ist, der eigentliche Wert jedoch beliebig. Das geht syntaktisch wie folgt:
data (Eq a) => Assoziativ a b = Index a b
Das heißt, dass der erste Wert, der logisch für die inidzierung benutzt werden soll, vergleichbar sein soll.
Typklassen zur Einschränkung von Funktionen
Entsprechend muss noch die Funktion finde eingeschränkt werden, da ja der Datentyp (Assoziativ) auf dem sie vergleichen soll nur Indizes zulässt die vergleichbar sind (aus Eq sind). Würde man also zulassen, dass auch Indizes zugelassen sind die nicht aus Eq sind, würde es für diese Indizes keine (nicht nur keine sinnvolle, sondern gar keine) Definition für Assoziativ geben. Daher muss finde angegeben werden als:
finde :: (Eq a) => a -> [Assoziativ a b] -> [b]
finde x ((Index i y):ys) | x == i = [y]
| otherwise = finde x ys
finde _ _ = []
