ADTs, GADTS, Typklassen

2023-07-07

ADTs, GADTs, Typklassen #

Ich habe vor Kurzem funktionale Abhängigkeiten kennengelernt und hatte gleich den Impuls, darüber zu schreiben. Das ist eine gute Gelegenheit, um etwas ausführlicher auf Konzepte der Typebene in Sprachen wie Haskell, Purescript, Elm und Ocaml einzugehen.

Einfache Datentypen #

Die meisten Sprachen bringen einen Vorrat an einfachen Datentypen mit: numerische Datentypen für ganze Zahlen und Gleitkommazahlen, Datentypen für einzelne Buchstaben und andere Schriftzeichen, einen Datentyp mit den zwei Wahrheitswerten “falsch” und “wahr”.

In den Details gibt es große Unterschiede zwischen den Sprachen, je nachdem, wo sie ihre Schwerpunkte setzen und welche Form der Programmierung sie unterstützen. Beispielsweise hat C keinen speziellen Datentyp für Wahrheitswerte, Python und Javascript unterscheiden nicht streng zwischen einzelnen Schriftzeichen und Zeichenketten, Javascript unterscheidet nicht zwischen ganzen Zahlen und Gleitkommazahlen, TCL kennt nur Zeichenketten, …

Ein paar einfache Datentypen in Haskell:

  • Int: ganze Zahlen wie -3, 0, 123, 999999999, …
  • Float: Gleitkommazahlen wie -123.45, 1.0, 3.141592653, …
  • Char: Zeichen wie 'a', 'β', '7', '+', '?', '🙂', …
  • Bool: die Wahrheitswerte True und False.

Die Größe einfacher Datentypen #

Man kann einen Datentyp auffassen als die Menge seiner Werte. Hier als Beispiel der Datentyp Bool in Mengenschreibweise:

Bool = { False , True }

Die Größe eines Datentyps ist die Anzahl seiner Werte. Der Datentyp Bool enthält genau zwei Werte. Damit ist seine Größe 2.

Das gleiche Spiel kann man mit allen einfachen Datentypen spielen. Der kleinste Int Wert auf meinem Rechner ist die ganze Zahl -9223372036854775808 und der größte Int Wert die ganze Zahl 9223372036854775807. Daraus ergibt sich für den Datentyp Int die Größe 2^64.

Die Größe eines einfachen Datentyps hängt letztlich auch damit zusammen, wie viele Bits mindestens benötigt werden um einen seiner Werte zu codieren. Ein Int Wert ist auf meinem Rechner in 64 Bits codiert. Daraus ergibt sich, dass 2^64 verschiedene Int Werte codiert werden können. In Sprachen wie C, die dafür gemacht sind, möglichst effiziente Programme zu schreiben und verhältnismäßig nah an der Hardware zu programmieren, bedeutet ein Datentyp im Grunde nicht mehr als die Anzahl von Bits, die einer seiner Werte im Speicher mindestens benötigt.

Bei Char und Float ist die Berechnung der Größe etwas komplizierter. vom Datentyp Char gibt es insgesamt 1114112 Werte. Für Float weiß ich es nicht, aber es lässt sich grundsätzlich ausrechnen.

Zusammengesetzte Datentypen #

Zusammengesetzte Datentypen sind bspw. Arrays, Listen, Strings, Tupel, Records und Structs. Das sind allesamt Datentypen, die sich – wie der Name sagt – auf irgendeine Art aus anderen Datentypen zusammensetzen.

Ein Record-Datentyp für ganzzahlige Punkte in der Ebene könnte so aussehen:

-- Purescript
type Point = { x :: Int , y :: Int }

Ein Tupel-Datentyp für den selben Zweck:

-- Haskell
(Int,Int)

Der Record-Datentyp hat den Vorteil, dass die Felder mit x und y bezeichnet sind. Dadurch ist es vermutlich etwas schwerer, sie zu verwechseln. Außerdem können wir direkt über die Feldnamen auf ihre Werte zugreifen. Beim Tupel-Datentyp verlassen wir uns auf die Position der Felder für ihre Unterscheidung. Der Zugriff auf die Felder erfolgt über Pattern-Matching in Case Expressions oder über spezielle Zugriffsfunktionen wie fst und snd. Dafür deckt sich die Tupel-Schreibweise mit der Schreibweise für Punkte in der Ebene, die auch sonst üblich ist. Das sind aber rein ergonomische Unterschiede. Strukturell unterscheiden sich diese beiden Datentypen nicht voneinander: in beiden Fällen besteht ein Punkt aus zwei Int Werten.

Die Größe zusammengesetzter Datentypen #

Es gibt auf meinem Rechner 2^64 Werte vom Datentyp Int. Für den Datentyp Point ergeben sich damit 2^64 * 2^64 also 2^128 Werte. Das selbe gilt für den Datentyp (Int,Int). Solche Datentypen, die sich aus anderen Datentypen zusammensetzen, so dass ihre Größe das Produkt der Größen der beteiligten Datentypen ist, heißen Produkttypen. Array-Datentypen und C-Structs sind auch Produkttypen. Ein bisschen komplexer ist es bei Listen und Strings. Mehr dazu weiter unten.

In allen herkömmlichen Sprachen kann man Produkttypen definieren, aber oft fehlt die Möglichkeit, Summentypen zu definieren. Das sind Datentypen, die sich aus anderen Datentypen zusammensetzen, so dass ihre Größe die Summe der Größen der beteiligten Datentypen ist.

Algebraische Datentypen #

Algebraische Datentypen (ADTs) vereinen in sich Produkttypen und Summentypen: jeder ADT ist eine Summe von Produkten.

Summen

Einer der einfachsten ADTs ist der Datentyp Bool in Haskell:

-- Haskell
data Bool = False | True

False und True sind sogenannte Wertekonstruktoren (oder einfach nur Werte). Den Balken müssen wir lesen wie ein exklusives Oder: jeder Wert vom Datentyp Bool ist entweder False oder True. Andere als diese zwei Bool Werte gibt es nicht.

ADTs können beliebig viele Wertekonstruktoren haben:

-- Haskell

data Ampel = Grün | Gelb | Rot

data Käse = Gouda | Cheddar | Brie | Camembert | Gruyère

data T = A | B | C | D | E | F | G | H | I | J | K

Wir können auch einen ADT mit genau einem Wertekonstruktor definieren:

-- Haskell
data Eindeutig = Einheit

Hier hat nur der Wert Einheit den Datentyp Eindeutig. Damit besteht zwischen dem Datentyp und dem Wert eine Eins-zu-eins-Beziehung. Sogar der Spezialfall eines ADT mit keinen Wertekonstruktoren ist möglich. Wir geben einfach keine Wertekonstruktoren an:

-- Haskell
data Nichts

Damit hat der Datentyp Nichts keine Werte. Wir haben daher keine Möglichkeit, einen Wert vom Datentyp Nichts zu erzeugen oder eine Funktion anzuwenden, die auf Nichts operiert. Leere Datentypen sind nicht nutzlos, aber darauf werde ich hier nicht weiter eingehen. Stattdessen möchte ich auf eine Sache hinweisen, die Verwirrung stiften kann. Betrachte dafür die folgende Typdefinition:

-- Haskell

data Tasche
    = Tüte
    | Beutel
    | Rucksack
    | Gürteltasche
    | Tasche

Hier definieren wir den Datentyp Tasche mit den Werten Tüte, Beutel, Rucksack, Gürteltasche und Tasche. Es sticht ins Auge, dass der Name Tasche zweimal auftaucht: einmal als der Datentyp Tasche, einmal als der Wertekonstruktor Tasche. Für den Compiler ist das kein Problem. Er unterscheidet streng zwischen Datentypen und Wertekonstruktoren und kann sie nicht verwechseln, auch wenn sie den selben Namen haben. Das Beispiel ist zwar an den Haaren herbeigezogen, aber es ist tatsächlich manchmal sinnvoll, einem Datentyp und einem seiner Wertekonstruktoren den selben Namen zu geben. Weiter unten wird uns so etwas begegnen.

Wertekonstruktoren mit Feldern

Bisher haben wir einfache Wertekonstruktoren wie False, Gouda, Rucksack, A usw. gesehen. Wertekonstruktoren können aber typisierte Felder haben. Hier ein Beispiel:

-- Haskell
data Lampe = Leuchtet Bool

Der Datentyp Lampe hat den Wertekonstruktor Leuchtet mit einem Feld vom Datentyp Bool. Bisher haben wir die Begriffe Wert und Wertekonstruktor als Synonyme behandelt. Das ändert sich sobald Felder ins Spiel kommen. Der Wertekonstruktor Leuchtet ist allein noch kein Wert vom Datentyp Lampe. Wir müssen ihn um einen Bool Wert ergänzen, um einen Wert vom Datentyp Lampe zu erzeugen.

-- Haskell Repl

> data Lampe = Leuchtet Bool

> :type Leuchtet
Leuchtet :: Bool -> Lampe

> lampeAn = Leuchtet True

> :type lampeAn
lampeAn :: Lampe

Produkte

Wertekonstruktoren können mehr als ein Feld haben. Hier ein Beispiel:

-- Haskell
data Datum = Datum Int Int Int  -- Tag Monat Jahr

Der Datentyp Datum hat einen Wertekonstruktor Datum mit drei Feldern vom Datentyp Int. So ein Datentyp entspricht den normalen Produkttypen, die wir oben schon kennengelernt haben.

Summen von Produkten

In einem ADT lassen sich Produkte und Summen kombinieren. Hier ein Datentyp mit drei Wertekonstruktoren, die jeweils ein Feld vom Datentyp Bool haben:

-- Haskell
data MyType = X Bool | Y Bool | Z Bool

Daraus ergeben sich die folgenden konkreten Werte:

  • X False
  • X True
  • Y False
  • Y True
  • Z False
  • Z True

Hier ein Datentyp mit fünf Wertekonstruktoren und unterschiedlichen Anzahlen von Feldern:

-- Haskell

data Zubrot
    = Käse Bool         -- vegan ja/nein
    | Wurst Bool        -- vegan ja/nein
    | Marmelade Int Int -- Frucht- und Zuckergehalt in %
    | Margarine
    | Butter

Die Größe algebraischer Datentypen #

Die Größe eines ADT ist die Summe der Größen seiner Wertekonstruktoren. Die Größe eines Wertekonstruktors ist das Produkt der Größen seiner Feldtypen. Ein Wertekonstruktor ohne Felder hat die Größe 1. Ein Datentyp ohne Wertekonstruktoren hat die Größe 0.

Wir berechnen die Größe für ein paar ADTs:

|Nichts| == 0

|Eindeutig| == |Einheit| == 1

|Bool| == |False| + |True| == 1 + 1 == 2

|Ampel| == |Grün| + |Gelb| + |Rot| == 1 + 1 + 1 == 3

|Lampe| == |Leuchtet Bool| == |Bool| == 2

|Datum| == |Datum Int Int Int|
        == |Int| * |Int| * |Int|
        == 3^64 * 3^64 * 3^64
        == 3^192

|MyType| == |X Bool| + |Y Bool| + |Z Bool|
         == |Bool| + |Bool| + |Bool|
         == 2 + 2 + 2
         == 6

|Zubrot| == |Käse Bool| + |Wurst Bool| + |Marmelade Int Int|
          + |Margarine| + |Butter|
         == |Bool| + |Bool| + |Int| * |Int| + 1 + 1
         == 2 + 2 + 2^64 * 2^64 + 1 + 1
         == 2^128 + 6

Weiter unten werden wir auch unendlich große ADTs sehen.

Der Mehrwert algebraischer Datentypen #

Mit ADTs können wir neue Datentypen jeder beliebigen Größe erzeugen und die Datentypen, die wir schon vorliegen haben, sowohl additiv als auch multiplikativ zu neuen Datentypen verknüpfen. Für jede Datenstruktur, die sich so beschreiben lässt, können wir einen ADT definieren. Ich möchte an zwei Beispielen zeigen, welchen Mehrwert das hat.

Beispiel 1: Verkehrsampel

Ein Datentyp für die drei Zustände einer aktiven Ampel könnte so definiert sein:

--Haskell
data Ampel = Grün | Gelb | Rot

Viele herkömmliche Sprachen scheitern schon daran, einen genau dreiwertigen Datentyp zu erzeugen.

Wenn wir entscheiden müssen, ob jemand für das Überfahren einer Ampel im Straßenverkehr einen Bußgeldbescheid erhalten soll oder nicht, können wir das wie folgt modellieren:

-- Haskell

bußgeldbescheid :: Ampel -> Bool
bußgeldbescheid ampel = case ampel of
    Grün -> False
    Gelb -> False
    Rot -> True

Hier ist bußgeldbescheid eine Funktion von Ampel nach Bool. Die drei Werte des Datentyps Ampel entsprechen den drei Zuständen einer aktiven Ampel. Mit anderen als diesen drei Werten müssen wir uns beim Implementieren nicht auseinandersetzen. Stattdessen können wir uns voll und ganz auf das Wesentliche konzentrieren: die Zuordnung der tatsächlichen Ampelzustände nach Bool. Auch beim Verwenden der Funktion ohne Kenntnis ihrer Implementierung müssen wir uns keine Gedanken über andere als diese drei Werte machen, denn die Funktion akzeptiert nur diese drei und der Compiler sichert das für uns ab.

Ganz anders sieht das aus, wenn wir bei der Modellierung des selben Sachverhaltes ohne ADTs bzw. ohne Summentypen auskommen müssen. Wir sind dann gezwungen, auf bestehende Datentypen zurückzugreifen. Zum Beispiel so:

-- Haskell

grün = 0
gelb = 1
rot = 2

bußgeldbescheid :: Int -> Bool
bußgeldbescheid ampel =
    ampel /= grün && ampel /= gelb

Man kann so programmieren, aber die Funktion hat jetzt für den Compiler einen Definitionsbereich aus 2^64 Werten. Drei davon kümmern uns: nämlich 0, 1 und 2 bzw. grün, gelb und rot. Die übrigen 18446744073709551613 Werte sind für den modellierten Sachverhalt überflüssig. Aber können wir uns darauf verlassen, dass kein anderer Wert an die Funktion übergeben wird? So wie sie jetzt implementiert ist, werden die 18446744073709551613 überflüssigen Werte auf True abgebildet. Das könnte zur Folge haben, dass Bußgeldbescheide an Personen versendet werden, die nicht bei Rot gefahren sind, weil jemand den Aufruf der Funktion vermasselt hat, oder weil jemand die Dokumentation nicht richtig gelesen hat, oder weil die Implementierung sich zwischenzeitlich geändert hat: bei einem Refactoring wurde der Rückgabewert für die 18446744073709551613 überflüssigen Werte verändert und schon tritt ein Fehler auf, den es vorher nicht gab.

Hier liegt ein Fehlerpotenzial vor, das es nicht gibt wenn man ADTs verwendet um die Definitions- und Wertebereiche der Funktionen, Prozeduren und Methoden so festzulegen, dass sie genau zum modellierten Sachverhalt passen.

Beispiel 2: unbekanntes Alter

Stellen wir uns vor, dass wir einen Datentyp für das Alter von Personen als ganze Zahl in Jahren benötigen. Es liegt auf der Hand, dafür den Datentyp Int zu verwenden. Noch besser wäre ein Datentyp für natürliche Zahlen, aber darum kümmern wir uns jetzt nicht.

Komplizierter ist es, wenn wir berücksichtigen müssen, dass das Alter einer Person unbekannt sein kann. Wie bilden wir das ab? Ich zeige erst, wie hier ein ADT helfen kann. Dann kritisiere ich, wie das in Sprachen ohne ADTs gelöst wird. Also, hier mein Vorschlag für einen passenden Datentyp:

-- Haskell
data Alter = AlterUnbekannt | Alter Int

Ein Wert vom Datentyp Alter ist entweder AlterUnbekannt oder Alter mit einem Int Feld. Stellen wir uns die drei Personen Marit, Marta und Max vor. Marit ist 30, Marta ist 11 und von Max kennen wir das Alter nicht.

-- Haskell

maritAlter :: Alter
maritAlter = Alter 30

martaAlter :: Alter
martaAlter = Alter 11

maxAlter :: Alter
maxAlter = AlterUnbekannt

Auf diese Weise unterscheiden wir sauber zwischen einem bekannten und einem unbekannten Alter. Eine Funktion, die Altersklassen bestimmt, könnte so aussehen:

-- Haskell

data Altersklasse
    = Minderjährig
    | Volljährig
    | AltersklasseUnbekannt

altersklasse :: Alter -> Altersklasse
altersklasse Alter = case alter of
    Alter n -> if n < 18 then Minderjährig else Volljährig
    AlterUnbekannt -> AltersklasseUnbekannt

Schauen wir uns die Altersklassen von Marit, Marta und Max an:

-- Haskell Repl

> altersklasse maritAlter
Volljährig

> altersklasse martaAlter
Minderjährig

> altersklasse maxAlter
AltersklasseUnbekannt

Dadurch, dass unser Datentyp Alter ganz ausdrücklich auch den Wert AlterUnbekannt hat, müssten wir uns schon besondere Mühe geben, um diesen Fall bei der Berechnung der Altersklasse unter den Tisch fallen zu lassen.

Aber wie würden wir das ohne ADTs modellieren? Hier noch mal der zu modellierende Sachverhalt: wir müssen das Alter von Personen codieren und dabei berücksichtigen, dass ein Alter unbekannt sein kann. In Sprachen ohne ADTs gibt es für die Codierung solcher Sonderfälle zwei verschiedene Lösungsansätze.

Ansatz 1 ohne ADTs: Numerische Fehlercodes

Bilde Sonderfälle wie Fehlercodes auf Werte ab, die zum selben Datentyp gehören wie die modellierte Größe, aber offensichtlich kein Wert der modellierten Größe sind. Das setzt voraus, dass der Datentyp zusätzlichen Platz dafür bietet. Ein gutes Beispiel dafür ist die Java String-Methode indexOf, die man verwendet um nach Substrings zu suchen. Wenn der Substring gefunden wurde, wertet indexOf zu dem Index aus, bei dem der Substring beginnt. Wenn der Substring nicht gefunden wurde, wertet indexOf zu -1 aus:

// Java
"abc".indexof("c")  // Wertet aus zu: 2
"abc".indexOf("d")  // Wertet aus zu: -1

Die Idee dahinter ist, dass Indizes natürliche Zahlen sind und dass daher mit dem Rückgabewert -1 offensichtlich kein Index gemeint sein kann. In unserem Fall könnte der Ansatz so aussehen:

-- Haskell

maritAlter :: Int
maritAlter = 30

martaAlter :: Int
martaAlter = 11

maxAlter :: Int
maxAlter = -1

Wenn wir jetzt die Altersklassen berechnen und dabei nicht genau aufpassen, könnte die folgende Funktion zustande kommen:

-- Haskell

data Altersklasse = Minderjährig | Volljährig

altersklasse :: Int ->  Altersklasse
altersklasse alter =
    if alter < 18 then Minderjährig else Volljährig

Die Altersklassen für Marit, Marta und Max sehen dann wie folgt aus:

-- Haskell Repl

> altersklasse maritAlter
Volljährig

> altersklasse martaAlter
Minderjährig

> altersklasse maxAlter
Minderjährig

Das ist natürlich Murks. Wir wissen gar nicht, ob Max minderjährig ist, weil wir sein Alter nicht kennen. Der Fehler ist aber nachvollziehbar: bei der Implementierung von altersklasse legen wir fest, dass Personen minderjährig sind wenn ihr Alter in Jahren kleiner als 18 ist, denn genau so ist Minderjährigkeit definiert. Um den Fehler zu vermeiden, müssen wir wissen, dass hier auch negative Zahlen zu berücksichtigen sind und dass -1 das Fehlen der Altersinformation repräsentiert:

-- Haskell

data Altersklasse
    = Minderjährig
    | Volljährig
    | AltersklasseUnbekannt

altersklasse :: Int ->  Altersklasse
altersklasse alter =
    if alter < 0 then AltersklasseUnbekannt
    else if alter < 18 then Minderjährig
    else Volljährig

Wir gehen hier noch einen Schritt weiter und bilden alle negativen Zahlen auf AltersklasseUnbekannt ab. Dadurch sind wir schon auf der sicheren Seite wenn weitere Fehlercodes dazukommen. Die Altersklassen für Marit, Marta und Max stimmen jetzt wieder:

-- Haskell Repl

> altersklasse maritAlter
Volljährig

> altersklasse martaAlter
Minderjährig

> altersklasse maxAlter
AltersklasseUnbekannt

Javas indexOf Methode hat die gleiche Schwäche. Wenn wir bspw. in vielen Strings den gleichen Substring suchen, um seinen durchschnittlichen Index zu berechnen, dürfen wir nicht vergessen, den Wert -1 gesondert zu verarbeiten. Sonst berechnen wir ein falsches Ergebnis. Besser ist es, wenn wir zwischen der erfolgreichen und der gescheiterten Suche so unterscheiden, dass auch der Compiler diese Unterscheidung absichert. Andernfalls liegt die volle Verantwortung für diese Unterscheidung bei der Person, die programmiert.

Ansatz 2 ohne ADTs: Nullreferenzen

Verwende Referenzdatentypen und stelle fehlende Werte dar als Nullreferenzen. Ein gutes Beispiel dafür ist die Prozedur strstr aus der C-Standard-Bibliothek:

// C
char *result = strstr(myString, mySubstr);

Wenn mySubstr in myString enthalten ist, dann enthält result jetzt eine Referenz auf die Speicheradresse der Anfangsposition von mySubstr innerhalb von myString. Andernfalls enthält result jetzt die Nullreferenz NULL.

In Sprachen, die es erlauben, Nullreferenzen so zu verwenden, muss man höllisch aufpassen: es kann passieren, dass man glaubt, einen Wert zu verarbeiten obwohl man eine Nullreferenz verarbeitet. Das führt leicht zu Laufzeitfehlern. In Haskell, Purescript, etc. kann ich das nicht demonstrieren, weil es in diesen Sprachen keine Referenzdatentypen und keine Nullreferenzen gibt. Deswegen hier ein bisschen Java Code:

// Main.java

class Alter {
    int wert;
    public Alter(int wert) {
        this.wert = wert;
    }
    public int get() {
        return this.wert;
    }
}
class Person {
    public Alter alter;
    enum Altersklasse { minderjährig, volljährig }
    public Altersklasse altersklasse() {
        if (this.alter.get() < 18) {
            return Altersklasse.minderjährig;
        } else {
            return Altersklasse.volljährig;
        }
    }
}
class Main {
    public static void main(String[] args) {
        Person marit = new Person();
        Person marta = new Person();
        Person max = new Person();

        marit.alter = new Alter(30);
        marta.alter = new Alter(11);

        System.out.println(marit.altersklasse());
        System.out.println(marta.altersklasse());
        System.out.println(max.altersklasse());
    }
}

Ich wickle das Alter einer Person hier in einen Datentyp Alter ein, weil Basisdatentypen wie int in Java keine Referenzdatentypen sind. Das passiert wenn wir das Programm compilieren und ausführen:

$ javac Main.java
$ java Main
volljährig
minderjährig
Exception in thread "main" java.lang.NullPointerException
        at Person.altersklasse(Main.java:21)
        at Main.main(Main.java:14)

Wir haben für Max kein Alter festgelegt. Sobald wir seine Altersklasse abrufen, terminiert das Programm mit einer NullPointerException. Selbstverständlich lässt sich das beheben, indem wir die Aufzählung Altersklasse und die Methode altersklasse anpassen, so wie wir es auch weiter oben gemacht haben. Die volle Verantwortung dafür, solche Laufzeitfehler zu vermeiden, liegt hier wieder bei der Person, die programmiert.

Welcher dieser beiden Ansätze ist besser? Das kommt darauf an, ob uns die Vermeidung von Laufzeitfehlern oder die Vermeidung falscher Ergebnisse wichtiger ist. Bei der Haskell-Funktion altersklasse :: Alter -> Altersklasse, mit der wir begonnen haben, erübrigt sich diese Abwägung: Nullreferenzen gibt es nicht und um das numerische Alter mit einem Fehlercode zu ergänzen, führen wir einen neuen Datentyp ein, der durch zwei Wertekonstruktoren sauber unterscheidet zwischen einem bekannten und einem unbekannten Alter.

Parametrische algebraische Datentypen #

Parametriche ADTs sind ADTs, die in ihrer Definition einen sogenannten Typparameter enthalten. Das ist ein Platzhalter, der durch einen konkreten Datentyp ersetzt werden muss, damit aus dem parametrischen ADT ein konkreter Datentyp wird. Solche Datentypen, die erst noch konkretisiert werden müssen, nennt man auch generische Datentypen. Um das Konzept zu demonstrieren, schauen wir uns noch mal den oben definierten Datentyp Alter an. Wir steigen an der Stelle von Haskell auf Purescript um, damit wir weiter unten Record-Literale verwenden können:

-- Purescript
data Alter = AlterUnbekannt | Alter Int

Wir haben diesen Datentyp eingeführt, um zu modellieren, dass das Alter einer Person manchmal bekannt und manchmal unbekannt ist. Aber dieses Problem kann auch bei anderen Daten auftreten. Wir könnten dafür jedes mal einen spezifischen Datentyp einführen:

-- Purescript
data Name = NameUnbekannt | Name String
data Alter = AlterUnbekannt | Alter Int
data Wohnort = WohnortUnbekannt | Wohnort String
data Beruf = BerufUnbekannt | Beruf String
...

Ein beispielhafter Record für Marta mit diesen Datentypen könnte so aussehen:

-- Purescript
marta =
    { name : Name "Marta"
    , alter : Alter 11
    , wohnort : WohnortUnbekannt
    , beruf : BerufUnbekannt
    }

Wir müssen aber nicht jeden Datentyp separat auf diese Weise erweitern. Stattdessen können wir einen generischen Datentyp festlegen, der jeden existierenden Datentyp um die Möglichkeit eines fehlenden Wertes erweitert:

-- Purescript
data Vielleicht a = Unbekannt | Wert a

Damit können wir jeden Datentyp so erweitern, dass ein Wert dieses Typs entweder vorhanden oder abhanden ist. Wenn wir das Alter einer Person kennen, sieht das so aus:

-- Purescript
alter :: Vielleicht Int
alter = Wert 23

Wenn wir das Alter nicht kennen, sieht das so aus:

-- Purescript
alter :: Vielleicht Int
alter = Unbekannt

Das gleiche Spiel mit dem Wohnort:

-- Purescript
wohnort :: Vielleicht String
wohnort = Wert "Leipzig"

Oder wenn der Wohnort unbekannt ist:

-- Purescript
wohnort :: Vielleicht String
wohnort = Unbekannt

Beachte, dass das Alter den Datentyp Int hat aber der Wohnort den Datentyp String. Trotzdem konnten wir in beiden Fällen den generischen Datentyp Vielleicht a einsetzen. Wir haben damit den Datentyp Int auf Vielleicht Int und den Datentyp String auf Vielleicht String erweitert. Ein ganzer Record für Marta könnte so aussehen:

-- Purescript

marta =
    { name : Wert "Marta"
    , alter : Wert 11
    , wohnort : Wert "Leipzig"
    , beruf : Wert "Schülerin"
    }

Damit sind die vier spezifischen Datentypen, die wir oben definiert haben, überflüssig, weil wir sie ersetzen konnten durch einen einzigen generischen Datentyp, der die selbe Aufgabe erfüllt.

In der Praxis würde man einen Datentyp wie Vielleicht a nicht definieren, sondern den Datentyp Maybe a verwenden, der genau für diesen Zweck schon vordefiniert ist und die selbe Struktur hat. Zum Vergleich hier die beiden Datentypen:

-- Purescript
data Vielleicht a = Unbekannt | Wert a
data Maybe a = Nothing | Just a

Es gehört zum guten Programmierstil, die vordefinierten Datentypen zu verwenden wenn die Struktur passt. Das erhöht die Lesbarkeit. Es kann zwar manchmal sinnvoll sein, trotzdem eigene Datentypen zu verwenden, um zu verdeutlichen, worum es geht, aber je mehr man beim Lesen von Code schon kennt, desto verständlicher ist der Code.

Unendlich große Datentypen #

Bisher haben wir nur ADTs mit endlicher Größe betrachtet. Es gibt aber auch ADTs, die unendlich groß sind. Das ist zum Beispiel der Fall bei ADTs, die rekursiv über sich selbst definiert sind. Ein gutes Beispiel dafür sind verkettete Listen:

-- Purescript
List a = Nil | Cons a ( List a )

Nil ist der gebräuchliche Name für die leere Liste. Das hat historische Gründe. Cons nimmt einen Wert und eine Liste und konstruiert daraus wieder eine Liste. Die Idee dabei ist, dass man mit der leeren Liste beginnt und von ihr ausgehend Cons verwendet und durch das sukzessive Hinzufügen weiterer Werte immer größere Listen konstruiert. Hier demonstrieren wir schrittweise den Aufbau einer Liste mit den ersten Ziffern der Kreiszahl Pi 3,1415…

-- Purescript

list0 = Nil
list1 = Cons 5 Nil
list2 = Cons 1 ( Cons 5 Nil )
list3 = Cons 4 ( Cons 1 ( Cons 5 Nil ) )
list4 = Cons 1 ( Cons 4 ( Cons 1 ( Cons 5 Nil ) ) )
list5 = Cons 3 ( Cons 1 ( Cons 4 ( Cons 1 ( Cons 5 Nil ) ) ) )

Haskell unterstützt für verkettete Listen eine kompaktere und freundlichere Syntax, mit der man z.B. list5 schreiben kann als [3,1,4,1,5]. Aber letztlich erfolgt die Konstruktion von verketteten Listen auch in Haskell genau so wie oben beschrieben.

List a ist generisch (bzw. parametrisch). Diese Beispiele haben allesamt den Datentyp List Int. Natürlich können wir auch Listen von Bools oder Floats oder Strings etc. konstruieren. Die Werte einer Liste müssen aber allesamt den selben Datentyp haben.

Aus der Definition des generischen Listendatentyps folgt, dass man aus einer Liste der Größe n immer eine Liste der Größe n+1 konstruieren kann indem man noch ein Element hinzufügt. Daraus ergibt sich, dass Listendatentypen unendlich groß sind. Der Datentyp String ist in Standard-Haskell ein Typalias für List Char und damit auch unendlich groß. In Purescript werden Strings wahrscheinlich irgendwie auf Javascript-Strings abgebildet. Auch davon gibt es unendlich viele, da man sie durch Verkettung beliebig verlängern kann.

Einfache Datentypen sind ADTs #

Ich habe es hier noch nicht erwähnt, aber bestimmt ist es schon aufgefallen: die Namen von Datentypen und von Wertekonstruktoren in einer Typdefinition mit dem data Schlüsselwort beginnen in Haskell und in Purescript immer mit einem Großbuchstaben. In Elm ist es auch so, mit dem Unterschied, dass das Schlüsselwort in Elm nicht data sondern type ist.

Während für den Datentyp Bool mit den Werten False und True in Haskell eine normale Typdefinition vordefiniert ist, ist der Datentyp Boolean mit den Werten false und true in Purescript in den Compiler integriert. Purescript ist dafür gemacht, nach Javascript zu compilieren. Um die zu überbrückende Kluft zwischen den Purescript-Datentypen und den Javascript-Datentypen, die nach der Compilation übrigbleiben, möglichst klein zu halten, orientieren sich die vordefinierten Datentypen in Purescript an den Datentypen, die auch in Javascript verfügbar sind. Deswegen gibt es in Purescript statt Bool den Datentyp Boolean mit den Werten false und true, die vom Compiler in die gleichnamigen Javascript-Werte false und true übersetzt werden. Das gleiche macht der Purescript-Compiler mit Zahlenliteralen, Arrays und Records.

Trotz der Sonderbehandlung durch den Compiler, hätte man die Wahrheitswerte auch in Purescript False und True nennen können. Ich vermute, dass man sich bewusst für die Kleinschreibung entschieden hat, um kenntlich zu machen, dass es sich um keine gewöhnlichen Wertekonstruktoren aus einer data Typdefinition handelt.

Es gibt noch mehr vordefinierte Datentypen – auch in Haskell – deren Werte nicht über eine herkömmliche Typdefinition mit Wertekonstruktoren erzeugt worden sind, sondern auf besondere Weise vom Compiler unterstützt werden. Die numerischen Datentypen sind das beste Beispiel dafür. Eine Sonderbehandlung numerischer Datentypen und Werte durch den Compiler ist schon für die syntaktische Unterstützung der gewöhnlichen Zahlenliterale wie -123.45, 0.0 und 99999 nötig, aber auch für die effiziente Arithmetik auf diesen Datentypen.

In Haskell kommt noch dazu, dass Zahlenliterale wie 1 und 1.0 überladen sind. 1 kann in Haskell sowohl für den Int Wert 1 als auch für den Float wert 1.0 stehen. Es kommen sogar noch weitere Datentypen in Frage:

-- Haskell Repl

> 1 :: Int
1

> 1 :: Integer
1

> 1 :: Float
1.0

> 1 :: Double
1.0

> import Numeric.Natural

> 1 :: Natural
1

Integer ist ein Datentyp für ganze Zahlen, der beliebig große Zahlen aufnehmen kann, solange der Speicherplatz es zulässt. Natural ist ein Datentyp für natürliche Zahlen. Zahlenliterale in Gleitkommaschreibweise sind in Haskell ebenso überladen:

-- Haskell Repl

> 1.0 :: Int
1

> 1.0 :: Integer
1

> 1.0 :: Float
1.0

> 1.0 :: Double
1.0

> import Numeric.Natural

> 1.0 :: Natural
1

Trotz ihrer Besonderheiten, können wir solche Datentypen auch als ADTs auffassen. Die Wahrheitswerte false und true werden in Purescript zwar klein geschrieben, aber das ist nur Syntax. Davon abgesehen können wir komplett ignorieren, dass der Datentyp Boolean nicht auf einer herkömmlichen data Typdefinition basiert. Es folgt daraus nichts, worauf wir beim Programmieren achtgeben müssten. So ist es auch mit den numerischen Datentypen: Zahlenliterale wie -3.1415 und 42 sind zwar keine gewöhnlichen Wertekonstruktoren, aber wir können jeden numerischen Datentyp auffassen als einen Summentyp mit all seinen Werten als Wertekonstruktoren ohne Typfelder:

-- Pseudo-Haskell
data Natural = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | ...

Prinzipiell könnten wir die ganzen numerischen Datentypen und die gesamte Zahlenarithmetik auch aus gewöhnlichen data Typdefinitionen nachbauen. Wir müssen uns dafür nur streng an die Konstruktionsregeln halten. Für natürliche Zahlen sind das die Peano-Axiome. Ein selbstgebauter Datentyp für natürliche Zahlen könnte so aussehen:

-- Haskell

data Nat = Null | Nachfolger Nat

plus :: Nat -> Nat -> Nat
plus a b = case a of
    Nachfolger n -> plus n ( Nachfolger b ) 
    Null -> b

mal :: Nat -> Nat -> Nat
mal a b = case a of
    Null -> Null
    Nachfolger Null -> b
    Nachfolger n -> plus b ( mal n b )

Für fast alle praktischen Anwendungen wäre das völlig unbrauchbar. Ohne die spezielle Syntax für Zahlenliterale wäre es sehr sehr umständlich und mühsam, Zahlen aufzuschreiben und zu lesen. Die Zahlenarithmetik wäre damit unendlich langsam. Worum es mir hier geht, ist, dass sich numerische Datentypen, Arrays, Records, Strings usw. zumindest rein formal auch als algebraische Datentypen auffassen lassen. Das verdeutlicht, wie flexibel ADTs sind: jeder Datentyp, der sich als ein Summentyp aus Produkttypen darstellen lässt, kann als ADT beschrieben werden.

Isomorphismen und Aliase #

Bisher haben wir neue Datentypen mit dem data Schlüsselwort definiert. Wir könnten es dabei belassen. Es gibt aber noch zwei weitere Schlüsselwörter, mit denen sich Datentypen definieren lassen: newtype und type.

Isomorphismen

Mit dem newtype Schlüsselwort lassen sich neue Datentypen definieren, die genau einen Wertekonstruktor mit genau einem Feld haben. Damit ist newtype auf den ersten Blick überflüssig, denn dasselbe können wir auch mit dem data Schlüsselwort erledigen:

-- Haskell
data T1 = K1 Bool
newtype T2 = K2 Bool

Wenn man dasselbe auch mit dem data Schlüsselwort machen kann, warum gibt es dann für diesen Spezialfall ein zusätzliches Schlüsselwort? Um das beanworten zu können, müssen wir wissen, dass die Verwendung von Datentypen mit gewissen Laufzeitkosten verbunden ist. Beispielsweise einen Int Wert in einen Maybe Kontext zu stecken und an anderer Stelle wieder aus diesem Maybe Kontext zu befreien: das sind Rechenoperationen, die zur Laufzeit des Programms stattfinden und ein kleines bisschen Speicher und Rechenzeit kosten. Wir nehmen das normalerweise gern in Kauf, weil uns ein korrektes Programm ohne Laufzeitfehler in den meisten Fällen viel wichtiger ist als ein Programm, das möglichst schnell und speichereffizient arbeitet, aber der Sonderfall eines Datentyps T aus genau einem Wertekonstruktor mit genau einem Feld ist hier deswegen interessant, weil bei so einem Datentyp eine Eins-zu-eins-Beziehung zwischen den Werten von T und den Werten des Feldtyps besteht. Hier ein Beispiel:

-- Haskell
data WrapInt = Wrap Int

Dann gilt die Eins-zu-eins-Beziehung:

...
Wrap -3 <--> -3 
Wrap -2 <--> -2 
Wrap -1 <--> -1 
Wrap 0  <--> 0 
Wrap 1  <--> 1 
Wrap 2  <--> 2 
Wrap 3  <--> 3 
Wrap 4  <--> 4 
Wrap 5  <--> 5 
Wrap 6  <--> 6 
Wrap 7  <--> 7 
...

In der Mathematik nennt man so eine Eins-zu-eins-Beziehung einen Isomorphismus. Wenn ein Isomorphismus zwischen Datentypen besteht, ist es schade um den Speicher und die Rechenzeit, die es zur Laufzeit des Programms kostet, Werte zwischen diesen Datentypen zu konvertieren. Hier kommt newtype ins Spiel. Ein Beispiel:

-- Haskell
newtype Password = Password String

Es kann sinnvoll sein, für Passwörter einen eigenen Datentyp einzuführen. Am Ende ist natürlich jedes Passwort einfach nur ein String, aber wenn wir auf der Typebene zwischen String und Password streng unterscheiden, können wir z.B. die Erzeugung von schlechen Passwörtern verhindern. Dafür legen wir ein eigenes Modul an, das den Datentyp Password und bspw. eine sorgfältig geschriebene Funktion makePassword : IO Password enthält. Der entscheidende Trick ist, dass wir den Wertekonstruktor Password nicht exportieren. Dadurch ist Code außerhalb dieses Moduls gezwungen, die Funktion makePassword zu verwenden, um an einen Password Wert zu kommen.

Wir können semantisch (fast) exakt dasselbe auch mit dem data Schlüsselwort erreichen, aber wenn wir das newtype Schlüsselwort verwenden, entfernt der Compiler alle Password Wertekonstruktoren, so dass zur Laufzeit des Programms nur noch gewöhnliche String Werte übrigbleiben. Dadurch entfallen der Speicher und die Rechenzeit, die es sonst zur Laufzeit des Programms gekostet hätte, Werte zwischen diesen Datentypen zu konvertieren.

Übrigens gibt es doch einen semantischen Unterschied zwischen data und newtype, der die Auswertungsstrategie betrifft: Wertekonstruktoren werden bei data verzögert ausgewertet und bei newtype strikt ausgewertet. Was das bedeutet, möchte ich hier nicht erläutern. Der Text ist schon lang genug und der Unterschied ist ohnehin marginal: beide Auswertungsstrategien führen auf den gleichen Wert, wenn sie erfolgreich auswerten. Es gibt aber Fälle in denen die verzögerte Auswertung Erfolg hat aber die strikte Auswertung scheitert. Daher der semantische Unterschied.

Aliase

Das type Schlüsselwort führt einen Typalias bzw. ein Typsynonym ein. Das ist einfach nur ein weiterer Name für einen existierenden Datentyp. Beispielsweise sind herkömmliche Strings in Haskell nichts weiter als verlinkte Listen von Char Werten. Entsprechend ist der Datentyp String wie folgt definiert:

-- Haskell
type String = List Char

Das Beispiel stimmt nicht ganz: der Datentyp List Char wird in idiomatischem Haskell als [Char] geschrieben. Darauf möchte ich hier aber nicht näher eingehen. Leider gibt es in Haskell ein paar Schrulligkeiten wie diese, die die Sprache unnötig und ohne substaniellen Mehrwert verkomplizieren. Deswegen bin ich wirklich froh, dass es mittlerweile Alternativen wie Purescript gibt.

Typklassen #

Typklassen werden unterstützt in Haskell und in Purescript. Sie haben nichts zu tun mit Klassen in der OOP. Ein Konzept aus anderen Sprachen, das mit Typklassen vergleichbar ist, sind Interfaces. Jede Typklasse benennt eine Reihe von Funktionen. Ein Datentyp kann zu einer Typklasse hinzugefügt werden, wenn er alle Funktionen der Typklasse implementiert. Hier ein Beispiel für eine Typklasse mit einer zu implementierenden Funktion:

-- Purscript
class Eq a where
    eq :: a -> a -> Boolean

Ein Datentyp a der Klasse Eq muss also die Funktion eq implementieren, die zwei Werte vom Datentyp a aufnimmt und einen Boolean Wert berechnet. Eq (für equality) ist sowohl in Purescript als auch in Haskell eine vordefinierte Typklasse für die Datentypen, auf denen die Gleichheitsfunktion eq bzw. der Gleichheitsoperator == gegeben sein soll.

Eine Funktion, die wie eq auf mehreren Datentypen operieren kann, nennt man eine polymorphe Funktion. Wenn der Polymorphismus über Typklassen hergestellt wird, spricht man von Typklassenpolymorphismus. Generisch, parametrisch und polymorph sind hier eng verwandte Begriffe. Wenn es um Datentypen geht, spricht man von generischen oder parametrischen Datentypen. Bei Funktionen spricht man von generischen oder polymorphen Funktionen.

Den Code für die Eq Typklasse im Purescript Prelude können wir hier nachlesen:

https://github.com/purescript/purescript-prelude/blob/v6.0.1/src/Data/Eq.purs#L35-L36

Er stimmt mit der oben angegebenen Definition überein. Direkt darunter befindet sich die Definition für den Gleichheitsoperator:

infix 4 eq as ==

Die Zeile legt fest, dass der Infix-Operator == ein Alias für die Funktion eq ist und in der Operatorrangfolge an vierter Stelle steht. Wenn == ein Alias für eq ist und eq eine Funktion der Typklasse Eq ist, dann muss ein Datentyp die Klasse Eq implementieren, damit der Operator == für seine Werte verfügbar ist. Probieren wir das aus:

-- Purescript Repl

> 123 == 123
true

> 123 == 124
false

> "abc" == "abc"
true

> "abc" == "bcd"
false

> false == false
true

> false == true
false

Demnach implementieren die Datentypen Int, String und Boolean die Typklasse Eq. Unser selbst definierter Datentyp Bool implementiert Eq noch nicht:

-- Purescript Repl

> data Bool = False | True

> False == False
...
No type class instance was found for

  Data.Eq.Eq Bool
...

Das können wir aber mit einer Instanzdeklaration nachholen. Mit einer Instanzdeklaration fügt man einen Datentyp zu einer Typklasse hinzu. Anschließend kann man die Funktionen und Operatoren der Typklasse auf Werte von diesem Datentyp anwenden:

-- Purescript

instance Eq Bool where
    eq a b = case [a,b] of
        [False,False] -> true
        [True,True] -> true
        _ ->false

-- Purescript Repl

> False == False
true

Damit ist geklärt, was Typklassen sind: ein Formalismus um polymorphe Funktionen zu beschreiben. Oft hängt an den Funktionen einer Typklasse eine bestimmte Erwartungshaltung hinsichtlich ihrer Semantik, die vom Typsystem nicht erfasst wird. Beispielsweise hätten wir eq auch so angeben können:

-- Purescript

eq a b = case [a,b] of
    [False,False] -> False
    [True,True] -> False
    _ ->True

Damit würde eq nicht mehr auf Gleichheit prüfen sondern auf Ungleichheit. Der Compiler würde die Definition trotzdem akzeptieren, weil der Datentyp passt. Aber der Gleichheitsoperator == würde sich für diesen Datentyp anders verhalten als erwartet und damit für reichlich Verwirrung sorgen.

Man kann zwischen Typklassen auch Abhängigkeiten definieren:

-- Purescript
class (A T, B T, C T) <= D T ...

Das bedeutet, dass ein Datentyp T nur dann zur Typklasse D gehören kann, wenn er auch zu den Typklassen A, B und C gehört. In Haskell sind solche Abhängigkeiten auch möglich. Die Syntax ist fast identisch. Nur der Doppelpfeil wird in Haskell umgekehrt notiert: =>. Wenn links vom Pfeil nur eine Typklasse steht, können die Klammern entfallen.

Elm unterstützt keine Typklassen. In Haskell und Purescript sind zum Beispiel die arithmetischen Operatoren auf den verschiedenen numerischen Datentypen über Typklassen implementiert:

-- Purescript Repl

> :type (+)
forall (a :: Type). Semiring a => a -> a -> a

> :type (-)
forall (a :: Type). Ring a => a -> a -> a

> :type (*)
forall (a :: Type). Semiring a => a -> a -> a

> :type (/)
forall (a :: Type). EuclideanRing a => a -> a -> a

Demnach ist der Operator + in Purescript auf den Datentypen gegeben, die zur Typklasse Semiring gehören, der Operator - auf den Datentypen, die zur Typklasse Ring gehören, usw. Sowohl Haskell als auch Purescript haben eine mathematisch interessante Typklassenhierarchie, aber wenn man sich für Begriffe wie Halbring, Ring und euklidischer Ring nicht interessiert, kann man sie ignorieren: sich mit diesen Begriffen herumzuschlagen, ist keine Voraussetzung dafür, in diesen Sprachen zu programmieren!!!

Typische Idiome der funktionalen Programmierung, wie map, foldr, foldl, traverse, oder der monadische bind Operator >>= sind ebenfalls über entsprechende Typklassen als polymorphe Funktionen definiert. Hier operiert map auf zwei verschiedenen Datentypen:

-- Purescript Repl

> map (_*2) [1,2,3]
[2,4,6]

> import Data.Maybe

> map (_*2) (Just 3)
(Just 6)

Es kommt selten vor, dass ich eigene Typklassen schreibe, weil es mir produktiver erscheint, konkreten Code zu schreiben und dabei nicht darüber nachzudenken, wo sich strukturelle Übereinstimmungen verbergen könnten, aus denen sich vielleicht polymorphe Funktionen ableiten lassen. Probleme, bei denen ich Typklassen vielleicht einsetzen würde, sind Serialisierung und Persistenz. Beispielsweise könnte die Serialisierung und Deserialisierung zwischen einem Datentyp a und Json über zwei polymorphe Funktionen ablaufen:

-- Purescript
class JsonSerializable a where
    toJson :: a -> String
    fromJson :: String -> Maybe a

Dazu würde ich noch fordern, dass für alle Instanzdeklarationen gelten sollte:

fromJson ( toJson value ) == Just value
map toJson ( fromJson string ) == Just string

Diese Regeln kann man zwar nicht vom Compiler absichern lassen, aber eine JsonSerializable Instanz, die sie nicht einhält, ist offensichtlich unbrauchbar.

Eine Typklasse für die Persistenz in einer Datenbank könnte so aussehen:

-- Haskell
class Db a where
    insert :: a -> IO String
    update :: String -> a -> IO ()
    read :: String -> IO ( Maybe a )

Ich muss unbedingt dazusagen, dass ich mir darüber maximal drei Minuten Gedanken gemacht habe. Es ist sehr wahrscheinlich, dass ich hier irgendetwas entscheidendes vergessen oder übersehen habe. Als Beispiel sollte uns das an dieser Stelle trotzdem genügen. Ich beschreibe kurz die Funktionen:

  • insert persistiert einen Wert vom Datentyp a als neuen Record in der Datenbank und liefert einen String, den wir später als Schlüssel verwenden können, um diesen Wert zu aktualisieren oder wieder auszulesen.
  • update nimmt einen String als Schlüssel entgegen und aktualisiert den entsprechenden Record in der Datenbank mit einem Wert vom Datentyp a.
  • read nimmt einen Schlüssel entgegen und liefert den entsprechenden Wert vom Datentyp a aus der Datenbank. Weil wir nicht garantieren können, dass jeder Schlüssel auf einen gültigen Record in der Datenbank verweist, ist dieser Wert in einen Maybe Kontext eingeschlossen.

Ich hätte wirklich Lust, herauszufinden, ob das ein gutes Design oder zu naiv ist, aber erst muss ich diesen Text fertig schreiben.

Im nächsten Abschnitt gehe ich auf Multiparameter-Typklassen ein. Vorher möchte ich noch eine Bemerkung zu Typklassen im Allgemeinen loswerden: Typklassenpolymorphie ist ein produktives Konzept, aber es lohnt sich nicht immer, auf Typklassen und polymorphe Funktionen zu setzen. Wenn die Polymorphie einem formalen Kalkül folgt, so wie es bei der Typklasse Eq und bei den arithmetischen Operationen der Fall ist, oder wenn es darum geht, Datentypen um Funktionalität zu erweitern wie bei der Typklasse JsonSerialize, dann sind Typklassen sinnvoll. Aber man sollte nicht versuchen, Typklassenpolymorphie zu erzwingen: manchmal ist der Code besser ohne Typklassen. Elm kommt ganz ohne Typklassen aus.

Multiparameter-Typklassen #

Eine Vorbemerkung: Man muss bei den Programmierkonzepten der Typebene, die ich hier vorstelle, ein bisschen darauf achten, dass man den Ball flach hält. Wenn man mit einem vordefinierten Datentyp gut auskommt, muss man dafür keinen ADT definieren. Wenn es keinen Grund dafür gibt, einen parametrischen ADT zu definieren, sollte man es bei einem parameterlosen ADT belassen. Wenn man sich nicht ganz sicher ist, ob man eine polymorphe oder mehrere monomorphe Funktionen definieren sollte, ist es besser, auf Polymorphie zu verzichten. Dieser Appell gilt umso mehr für die Konzepte, die jetzt folgen. Mit einem guten Verständnis für ADTs, parametrische ADTs und einfache Typklassen ist man schon sehr gut aufgestellt. Solange man diese Konzepte nicht richtig verinnerlicht hat, muss man sich mit den Konzepten, die jetzt noch folgen, nicht befassen.

Typklassen können mehr als einen Typparameter haben. Auf die Weise können die polymorphen Funktionen einer Typklasse Beziehungen zwischen Datentypen beschreiben. Die Typklasse Db von gerade eben bietet sich an, um zu zeigen, wofür das nützlich sein kann. Mich stört an dieser Typklasse ein bisschen, dass der Datentyp für die Schlüssel auf String festgelegt ist. Warum nicht Int? Oder ein spezieller Datentyp Uuid für sogenannte Universally Unique Identifiers? Also erweitern wir diese einfache Typklasse zu einer Typklasse mit zwei Typparametern:

-- Haskell
class Db key value where
    insert :: value -> IO key
    update :: key -> value -> IO ()
    read :: key -> IO ( Maybe value )

Auf diese Weise sind wir für die Schlüssel nicht auf den Datentyp String festgelegt, sondern können dafür einen Datentyp frei wählen. Hier noch ein Beispiel für eine Multiparameter-Typklasse aus dem Purescript-Buch:

-- Purescript
class Stream stream element where
    uncons :: stream -> Maybe { head :: element , tail :: stream }

Die Idee dabei ist, dass ein Wert vom Datentyp stream ein Datenstrom aus Werten vom Datentyp element ist. Die Funktion uncons trennt diesen Datenstrom auf in den ersten Wert (head) und den Rest des Datenstroms (tail). Auf die Weise lassen sich die Werte in einem Datenstrom durch wiederholtes Aufrufen von uncons der Reihe nach verarbeiten. Sobald der Datenstrom leer ist, liefert uncons den Wert Nothing. Wir fügen die Datentypen String und Char zur Typklasse Stream hinzu, indem wir eine passende uncons Funktion angeben:

-- Purescript
instance Stream String Char where
    uncons = String.uncons

Dass die Funktion String.uncons hier genau passt, ist günstig für uns. Als nächstes fügen wir den generischen Datentyp Array a zusammen mit dem entsprechenden Datentyp a zur Typklasse Stream hinzu. Auch hier gibt es wieder eine passende uncons Funktion für Arrays:

-- Purescript
instance Stream ( Array a ) a where
    uncons = Array.uncons

Jetzt können wir mit der polymorphen uncons Funktion der Stream Typklasse sowohl Char Werte aus String Datenströmen als auch a Werte aus Array a Datenströmen entnehmen.

Funktionale Abhängigkeiten #

Es wäre jetzt naheliegend, aus uncons eine tail Funktion abzuleiten:

-- Purescript
tail :: String -> Maybe String
tail stream = map _.tail ( uncons stream )

Wir wenden erst uncons auf das Argument an. Dann wenden wir die Feldfunktion _.tail auf das Zwischenergebnis an. Das Zwischenergebnis ist in einen Maybe Kontext eingebettet. Deswegen müssen wir map einsetzen, um die Feldfunktion auf den Wert im Kontext anzuwenden. Das ist eine sinnvolle Definition. Trotzdem ist der Compiler nicht mit ihr zufrieden:

No type class instance was found for Main.Stream String t

Was funktioniert hier nicht? Dafür müssen wir (ganz grob) verstehen, wie der Compiler mit polymorphen Funktionen umgeht. Die beiden Instanzdeklarationen haben wir nicht ohne Grund hinzugefügt. Wenn wir die polymorphe Funktion uncons aufrufen, versucht der Compiler, die passenden Datentypen zu ermitteln, um prüfen zu können, ob ihm für diese Datentypen eine Instanzdeklaration bekannt ist. Wir wollen hier natürlich auf die Instanz Stream String Char hinaus. Ein Blick in obige Fehlermeldung verrät, dass die Typinferenz bei Stream String t hängen bleibt. Der Compiler ist offenbar nicht in der Lage, für den Typparameter t zu inferieren, dass es sich um den Datentyp Char handeln muss. Ich weiß nicht, wo genau es klemmt, aber es stimmt, dass wir bei der Definition unserer neuen tail Funktion dem Compiler nirgendwo einen Hinweis darauf geben, dass es sich bei t um Char handeln muss.

Wenn wir das polymorphe uncons durch String.uncons ersetzen, ist der Compiler zufrieden, aber dann können wir uns die Typklasse gleich sparen. Wenn wir uncons um eine Typannotation ergänzen, die ausdrücklich auf Char hinweist, ist der Compiler ebenfalls zufrieden:

-- Purescript
tail :: String -> Maybe String
tail stream = do
    let f :: String -> Maybe { head :: Char , tail :: _ }
        f = uncons
    map _.tail ( f stream )

Aber schön oder sinnvoll ist das auch nicht. Welchen Wert hat die Typklassenpolymorphie, wenn wir sie erst einführen und sie dann zur Hälfte wieder zurücknehmen?

Interessanterweise können wir den Compiler auch zufriedenstellen, indem wir die Definition der Typklasse Stream wie folgt anpassen:

-- Purescript
class Stream stream element | stream -> element where
    uncons :: stream -> Maybe { head :: element , tail :: stream }

Hinzugekommen ist der Teil | stream -> element vor dem where Schlüsselwort. Man nennt das eine funktionale Abhängigkeit. Wir vereinbaren dadurch mit dem Compiler, dass sich aus dem Datentyp für den Typparameter stream stets eindeutig ergeben muss, welcher Datentyp für den Typparameter element einzusetzen ist. Das hat bei mir zunächst für Kopfkratzen gesorgt. Dann ist mir aufgefallen, dass wir nur eine einzige Instanzdeklaration der Form Stream String ... angegeben haben, nämlich Stream String Char. Damit ist die funktionale Abhängigkeit stets erfüllt wenn wir für stream den Datentyp String einsetzen: für element kommt dann nur der Datentyp Char in Frage. Die andere Instanzdeklaration Stream ( Array a ) a erfüllt ebenfalls die Forderung nach funktionaler Abhängigkeit, denn wenn Array a (und damit stream) auf einen konkreten Datentyp festgelegt ist, dann ist auch a selbst (und damit element) eindeutig auf einen Datentyp festgelegt. Der Compiler ist damit zufriedengestellt solange wir keine weiteren Instanzdeklarationen hinzufügen, die diese Eindeutigkeit verletzen.

Verallgemeinerte algebraische Datentypen (GADTs) #

Weiter oben haben wir schon eine Verallgemeinerung der einfachen ADTs kenngenlernt: die parametrischen ADTs. Verallgemeinerung bedeutet, dass das Verallgemeinerte zum Spezialfall des Verallgemeinernden wird. Bei den parametrischen ADTs besteht der Spezialfall eines einfachen, parameterlosen ADT darin, dass die Anzahl seiner Typparameter 0 ist: jeder parameterlose ADT ist ein parametrischer ADT mit 0 Typparametern!

Die Sprache wird bei solchen Dingen oft etwas ungenau. Wenn wir von einem parametrischen ADT sprechen, meinen wir natürlich einen ADT mit mindestens einem Typparameter, sonst müssten wir den allgemeineren Begriff nicht bemühen. Aber wenn jemand über einen ADT sagt: “das ist kein parametrischer sondern ein einfacher ADT”, dann ist das genaugenommen ein Widerspruch und damit falsch. Im Gespräch sollte man das nicht zum Anlass nehmen, gleich mit dem Belehrfinger zu fuchteln, aber man sollte im Hinterkopf behalten, dass genaugenommen der konkretere Begriff in dem allgemeineren Begriff enthalten ist.

GADTs (generalized algebraic data types) sind wiederum eine Verallgemeinerung der parametrischen ADTs. Also ist jeder parameterlose und jeder parametrische ADT stets auch ein GADT. Aber auch über ADTs und GADTs wird häufig so gesprochen als seien es disjunkte Konzepte. Zum Beispiel enthält der englische Wikipedia-Artikel über GADTs in seiner aktuellen Form (2023-06) den folgenden Code-Kommentar:

-- A parametric ADT that is not a GADT

Im Haskell-Wiki und in der GHC-Dokumentation gibt es ähnliche Formulierungen. Das ist nicht schlimm, aber auch hier sollten wir im Hinterkopf behalten, dass formal der konkretere Begriff im allgemeineren Begriff enthalten ist.

Neue Syntax

GADTs bringen in Haskell neben der Verallgemeinerung auch eine eigene Syntax mit. Ich möchte zunächst herkömmliche ADTs in dieser GADT-Syntax aufschreiben. Dann schauen wir uns an, worin genau die Verallgemeinerung besteht. Hier noch mal Bool in der herkömmlichen ADT-Syntax:

-- Haskell
data Bool
    = False
    | True

So würde man Bool in der GADT-Syntax schreiben:

-- Haskell
data Bool where
    False :: Bool
    True :: Bool

Der Ampel Datentyp in herkömmlicher ADT-Syntax:

-- Haskell
data Ampel
    = Grün
    | Gelb
    | Rot

Der Ampel Datentyp in GADT-Syntax:

-- Ampel in GADT-Syntax
data Ampel where
    Grün :: Ampel
    Gelb :: Ampel
    Rot :: Ampel

Herkömmliche ADTs in GADT-Syntax aufzuschreiben, ist kein Gedankenexperiment: die Beispiele sind gültiger Haskell Code und können genau so verwendet werden. Bei der GADT-Syntax fällt gleich auf, dass die Wertekonstruktoren mit Typannotationen versehen sind. Bei parameterlosen ADTs in GADT-Syntax sind diese Typannotationen überflüssig: selbstverständlich haben hier alle Wertekonstruktoren den selben Datentyp. Schauen wir uns als nächstes ein paar echte parametrische ADTs in GADT-Syntax an. Hier noch mal Maybe a in der herkömmlichen Syntax:

-- Haskell
data Maybe a
    = Nothing
    | Just a

Zum Vergleich, Maybe a in GADT-Syntax:

-- Haskell
data Maybe a where
    Nothing :: Maybe a
    Just :: a -> Maybe a

Der Wertekonstrukor Just ist interessant. Er hat den Datentyp a -> Maybe a. Das ist immer der Fall, auch wenn wir den Datentyp in der herkömmlichen ADT-Syntax aufschreiben, aber hier schreiben wir den Datentyp explizit hin. Hier noch mal der Datentyp List, diesmal in Haskell:

-- Haskell
List a
    = Nil
    | Cons a ( List a )

In GADT-Syntax:

-- Haskell
List a where
    Nil :: List a
    Cons :: a -> List a -> List a

Die neue Syntax für GADTs ist ein Wink mit dem Zaunspfahl bzgl. der Verallgemeinerung, um die es geht. Bei einem herkömmlichen parametrischen ADT kann jeder Typparameter stets nur für alle Wertekontruktoren gemeinsam auf einen Datentyp festgelegt werden. Bei einem GADT kann jeder Typparameter für verschiedene Wertekonstruktoren auf verschiedene Datentypen festgelegt werden. Hier ein GADT mit drei Wertekonstruktoren:

-- Haskell
data MyGadt a where
    MyInt :: Int -> MyGadt Int
    MyBool :: Bool -> MyGadt Bool
    MyString :: String -> MyGadt String

Das besondere an einem GADT wie diesem ist, dass die Wertekonstruktoren den Datentyp jeweils unterschiedlich konkretisieren: der Wertekonstruktor MyInt erzeugt immer einen MyGadt Int, der Wertekonstruktor MyBool erzeugt immer einen MyGadt Bool und der Wertekonstruktor MyString erzeugt immer einen MyGadt String. Aber MyGadt hat nur diese drei Wertekonstruktoren. Daraus ergibt sich ein entscheidender Sachverhalt: der Typparameter a kann hier konstruktionsbedingt nur die Datentypen Int, Bool oder MyString annehmen.

Bei einem GADT können wir die Typparameter durch seine Wertekonstruktoren so einschränken, dass konstruktionsbedingt nur noch ganz bestimme Datentypen auf die Typparameter passen. Mehr noch: wir können die Wertekonstruktoren so entwerfen, dass sie Beziehungen zwischen den verschiedenen Konkretisierungen eines generischen Datentyps beschreiben. Es ist ein bisschen so als würden wir mit einem GADT nicht nur einen Datentyp beschreiben, sondern eine ganze Gruppe von Datentypen und ihre Beziehungen zueinander. Wer schon mal eine kleine formale Sprache entworfen und in eine Reihe von Datentypen gegossen hat oder einen Parser für eine formale Sprache geschrieben hat, müsste hier hellhörig werden. Tatsächlich eignen sich GADTs sehr gut dafür, DSLs oder ganze Programmiersprachen zu beschreiben. Grundsätzlich geht das auch mit herkömmlichen ADTs, aber mit GADTs lassen sich solche Beschreibungen kompakter formulieren und mehr Invarianten auf der Typebene festhalten. Als Beispiel dafür schauen wir uns die kleine arithmetische Sprache an, die der Wikipedia-Artikel zu GADTs enthält:

-- Haskell
data Expr a where
    EInt :: Int -> Expr Int
    EBool :: Bool -> Expr Bool
    EEqual :: Expr Int -> Expr Int -> Expr Bool

Der Wertekonsturktor EInt erzeugt immer einen Expr Int Wert. Die Wertekonstruktoren EBool und EEqual erzeugen immer einen Expr Bool Wert. Deswegen kann der Typparameter a hier nur die Typen Int und Bool annehmen. Dazu gehört noch die eval Funktion, die einen Expr a Ausdruck in einen Wert vom Typ a überführt:

-- Haskell
eval :: Expr a -> a
eval expr = case expr of
    EInt n -> n
    EBool b -> b
    EEqual a b -> eval a == eval b

Damit sollte das folgende Programm False ausgeben:

-- Haskell
main = do
    let v1 = EInt 123
    let v2 = EInt 124
    let result = EEqual v1 v2
    putStrLn ( show ( eval result ) )

Eine Sache, die mich ein bisschen daran stört, ist dass wir EEqual nicht auf Expr Bool Werte anwenden können. Das ist aber leicht behoben:

-- Haskell

data Expr a where
    EInt :: Int -> Expr Int
    EBool :: Bool -> Expr Bool
    EEqual :: Eq a => Expr a -> Expr a -> Expr Bool

eval :: Expr a -> a
eval expr = case expr of
    EInt n -> n
    EBool b -> b
    EEqual a b -> eval a == eval b

Damit sollte auch das folgende Programm compilieren und False ausgeben:

-- Haskell
main = do
    let v1 = EBool False
    let v2 = EBool True
    let result = EEqual v1 v2
    putStrLn ( show ( eval result ) )

Wie würde man das ohne GADTs modellieren? Keine Ahnung! Aber wir können uns anschauen, was übrigbleibt, wenn wir Expr auf einen parametrischen ADT reduzieren:

-- Haskell
data Expr a
    = EInt Int
    | EBool Bool
    | EEqual ( Expr a ) ( Expr a )

Wenn wir den so angepassten Datentyp in der GADT-Syntax aufschreiben, sehen wir besser, was sich geändert hat:

-- Haskell
data Expr a where
    EInt :: Int -> Expr a
    EBool :: Bool -> Expr a
    EEqual :: Expr a -> Expr a -> Expr a

Der Datentyp ist so völlig unbrauchbar. Es gibt jetzt keine Beziehung mehr zwischen dem Typparameter a und den Feldtypen von EInt und EBool:

-- Haskell

v1 :: Expr Int
v1 = EBool True

v2 :: Expr String
v2 = EInt 123

Der Wertekonstruktor EEqual ist so auch unbrauchbar. Wenn EEqual einen Expr Bool Wert erzeugen soll, muss er auch auf zwei Expr Bool Werten operieren. Schauen wir uns trotzdem an, wie weit wir bei der eval Funktion kommen:

-- Haskell
eval :: Expr a -> a
eval expr = case expr of
    EInt n -> undefined
    EBool b -> undefined
    EEqual e1 e2 -> undefined

Was sollen wir z.B. für EInt n berechnen? Der Wert n hat hier den Datentyp Int, aber eval operiert auf einem Expr a Wert und erzeugt einen a Wert. Wir bräuchten eine Funktion Int -> a für beliebige Datentypen a. Das wäre zwar rein formal möglich (also typisierbar) aber wie sollen wir für jeden möglichen Datentyp ad hoc und aus dem Nichts einen Wert herzaubern? Die gleiche Frage stellt sich für EBool b. Bei EEqual e1 e2 ist das Problem noch gravierender, weil wir nur dann zu einem Bool Wert auswerten können, wenn e1 und e2 vom Datentyp Expr Bool sind. Die ganze Konstruktion ist also völlig unbrauchbar.

Wenn wir Expr in einen parameterlosen ADT umbauen, kommt z.B. das heraus:

-- Haskell
data Expr
    = EInt Int
    | EBool Bool
    | EEqual Expr Expr

Das erscheint mir auf den ersten Blick schon sinnvoller. Schauen wir uns an, wie eval aussehen könnte:

-- Haskell
eval :: Expr -> a
eval expr = case expr of
    EInt n -> undefined
    EBool b -> undefined
    EEqual e1 e2 -> case ( e1 , e2 ) of
        ( EInt n1 , EInt n2 ) -> undefined
        ( EBool b1 , EBool b2 ) -> undefined
        _ -> undefined

Das ist wieder eine Sackgasse. Wir können eval zwar von Expr -> a konkretisieren auf Expr -> Bool oder auf Expr -> Int, aber das findet immer für die gesamte Funktion inklusive aller Case-Zweige statt. Wir können nicht in einem Case-Zweig nach Bool und im nächsten nach Int auswerten. Überhaupt müssen wir ja nach a auswerten, auch wenn für a weder Bool noch Int eingesetzt worden ist. Wenn wir für a einen konketen Wert einsetzen, wird die Sache einfacher. Für einige Anwendungen genügt sicherlich eine Funktion eval :: Expr -> String:

-- Haskell
eval :: Expr -> String
eval expr = case expr of
    EInt n -> show n
    EBool b -> show b
    EEqual e1 e2 -> case ( e1 , e2 ) of
        ( EInt n1 , EInt n2 ) -> show ( n1 == n2 )
        ( EBool b1 , EBool b2 ) -> show ( b1 == b2 )
        _ -> show False

Andernfalls sehe ich nicht, wie man hier ohne GADTs auskommen könnte. Ich hoffe, ich konnte demonstrieren, was man mit GADTs anstellen kann. Für mich ist das Konzept noch relativ neu.

Epilog #

Dieser Text ist für mich in erster Linie eine Art Selbsttest: kann ich mein Verständnis der Konzepte, die ich hier vorstelle, ausformulieren und aufschreiben, so dass ich hinterher damit zufrieden bin, auch wenn ich den Text zwischenzeitlich für ein paar Wochen beiseite gelegt habe? Wenn nicht, werde ich weiter daran arbeiten (sofern ich Zeit und Lust dazu habe). Mein Bezug zu diesem Thema ist ein praktischer. Bisher bin ich noch nicht dazu gekommen, mich ernsthaft mit Büchern über Typentheorie zu befassen. Insofern hoffe ich, dass sich hier kein Blödsinn eingeschlichen hat. Das wäre mir wirklich peinlich. Wenn der Text noch jemandem außer mir selbst nutzt, freut mich das umso mehr.