Algebraische Datentypen

In diesem Abschnitt werden wir uns ansehen, wie man in Elm sogenannte algebraische Datentypen¹ definieren kann.

Einfache algebraische Datentypen

Zuerst betrachten wir, in welcher Hinsicht diese Datentypen algebraisch sind. Anstelle des Namens Aufzählungstyp verwendet man in der Programmiersprachentheorie (PLT)² auch den Namen Summentyp. Dieser Name zeigt einen Zusammenhang zum Namen algebraischer Datentyp. Eine Algebra ist in der Mathematik eine Struktur, die eine Addition und eine Multiplikation zur Verfügung stellt. Neben der Addition (dem Summentyp) benötigen wir für einen algebraischen Datentyp also noch eine Multiplikation. Man nennt Datentypen, die diese Multiplikation modellieren, Produkttypen.

Ein Produkttyp entspricht einem benannten Paar bzw. Tupel und wird auch Verbund genannt. In der Programmiersprache C wird ein Verbund zum Beispiel mit dem Schlüsselwort struct definiert. Wie bei einem Paar kann man bei einem Produkttyp Werte von unterschiedlichen Typen zu einem Wert zusammenfassen. Im Unterschied zu einem klassischen Paar kann man der Kombination von Werten aber noch einen Namen geben. So kann man zum Beispiel auf die folgende Weise einen Datentyp für einen Punkt, zum Beispiel auf einer 2D-Zeichenfläche, definieren.

type Point
    = Point Float Float

Der Datentyp Point fasst zwei Werte vom Typ Float zu einem Wert vom Typ Point zusammen.

Wichtig

Der Name Point hinter dem Schlüsselwort type ist dabei der Name des Typs. Der Name Point hinter dem =-Zeichen ist wie bei den Aufzählungstypen der Name des Konstruktors.

Hinter dem Namen des Konstruktors folgt ein Leerzeichen und anschließend folgen, durch Leerzeichen getrennt, die Typen der Argumente des Konstruktors.

Wichtig

Im Gegensatz zu den Namen von Funktionen und Variablen müssen die Namen von Konstruktoren und Datentypen immer mit einem großen Buchstaben beginnen.

Der Konstruktor Point erhält zwei Argumente, die beide vom Typ Float sind. Um mithilfe eines Konstruktors einen Wert zu erzeugen, benutzt man den Konstruktor wie eine Funktion. Das heißt, man schreibt den Namen des Konstruktors und durch Leerzeichen getrennt die Argumente des Konstruktors. Die Definition des Datentyps gibt an, welche Typen die Argumente des Konstruktors haben müssen. Im Fall des Konstruktors Point müssen beide Argumente vom Typ Float sein. Wir können nun zum Beispiel wie folgt einen Punkt erstellen.

examplePoint : Point
examplePoint =
    Point 2.3 4.2

Wie im Fall von Aufzählungstypen kann man auch auf Produkttypen Pattern Matching durchführen. Im Fall von Produkttypen kann man mithilfe des Pattern Matching auf die Inhalte des Konstruktors zugreifen. Die folgende Funktion verschiebt einen Punkt um einen Wert auf der x- und einen Wert auf der y-Achse.

translate : Point -> Float -> Float -> Point
translate point dx dy =
    case point of
        Point x y ->
            Point (x + dx) (y + dy)

Wenn wir ein Pattern für einen Produkttyp angeben, muss das Pattern die gleiche Struktur wie der entsprechende Wert haben. Das heißt, im Fall von Point muss der Konstruktor Point im Pattern auch zwei Argumente haben. Die Argumente des Pattern sind im Fall von translate Variablen, nämlich x und y. Wenn wir die Funktion translate zum Beispiel mit dem Wert examplePoint aufrufen, werden die Variablen x und y an die Werte an der entsprechenden Stelle im Wert examplePoint gebunden. Das heißt, die Variable x wird in diesem Beispiel an den Wert 2.3 und die Variable y an den Wert 4.2 gebunden. Wir können dieses Verhalten wieder durch eine Sequenz von Auswertungsschritten illustrieren.

translate examplePoint 4 2

• =

  translate (Point 2.3 4.2) 4 2

  Definition von examplePoint

• =

  case Point 2.3 4.2 of
      Point x y ->
          Point (x + 4) (y + 2)

  Definition von translate

• =

  Point (2.3 + 4) (4.2 + 2)

  Auswertung des case-Ausdrucks

• =

  Point 6.3 (4.2 + 2)

  Definition von +

• =

  Point 6.3 6.2

  Definition von +

Als weiteres Beispiel können wir die folgende Funktion definieren, um einen Point in einen String umzuwandeln.

toString : Point -> String
toString point =
    case point of
        Point x y ->
            "("
                ++ String.fromFloat x
                ++ ", "
                ++ String.fromFloat y
                ++ ")"

In der Definition eines Produkttyps können wir natürlich auch selbstdefinierte Datentypen verwenden. Wir betrachten zum Beispiel folgenden Datentyp, der einen Spieler in einem Spiel modelliert, der einen Namen und eine aktuelle Position hat.

type Player
    = Player String Point

Als Beispiel erzeugen wir zuerst einen Wert vom Typ Player.

examplePlayer :: Player
examplePlayer =
    Player "Spieler A" (Point 0 0)

Wir können nun wie folgt eine Funktion definieren, die den Namen eines Spielers liefert.

playerName : Player -> String
playerName player =
    case player of
        Player name _ ->
            name

Der Unterstrich bedeutet, dass wir uns für das entsprechende Argument des Konstruktors, hier also den Point, nicht interessieren. Wenn wir stattdessen, an die Stelle des Argumentes eines Konstruktors eine Variable schreiben, wird die Variable an den Wert gebunden, der an der entsprechenden Stelle im Konstruktor steht. Im Fall von playerName wird die Variable name zum Beispiel an den Namen gebunden, der im Player steht. Das heißt, wenn wir den Aufruf playerName examplePlayer betrachten, wird die Variable name an den Wert "Spieler A" gebunden.

Als weiteres Beispiel können wir auch eine Funktion zur Umwandlung eines Spielers in einen String schreiben.

toString : Player -> String
toString player =
    case player of
        Player name point ->
            name ++ " " ++ Point.toString point

Wir gehen hier davon aus, dass die Funktion toString für den Datentyp Point, die wir zuvor definiert haben, sich in einem Modul Point befindet.

Wichtig

In der funktionalen Programmierung werden Module häufig um einen Datentyp herum organisiert.

Das heißt, wenn man einen Datentyp benötigt, dessen Bedeutung ohne Kontext klar ist, definiert man diesen Datentyp häufig in einem neuen Modul. In das Modul werden dann auch alle Funktionen, die auf dem Datentyp arbeiten, geschrieben.

Im Allgemeinen kann man Summen- und Produkttypen auch kombinieren. Die Kombination aus Summen- und Produkttypen wird als algebraischer Datentyp bezeichnet. Anders ausgedrückt sind Summen- und Produkttypen jeweils Spezialfälle von algebraischen Datentypen.

Im folgenden ist ein algebraischer Datentyp definiert. Der Datentyp beschreibt, ob ein Spiel unentschieden ausgegangen ist oder ob ein Spieler das Spiel gewonnen hat.

type GameResult
    = Won Player
    | Draw

Der Konstruktor Won modelliert, dass einer der Spieler gewonnen hat. Wenn die Spielrunde unentschieden ausgegangen ist, liefert die Funktion als Ergebnis den Wert Draw. Da wir in diesem Fall keine zusätzlichen Informationen benötigen, hat der Konstruktor keine Argumente.

Wichtig

Man bezeichnet algebraische Datentypen manchmal auch als Tagged Union.

Man spricht von einer Union, da der algebraische Datentyp wie bei einem Aufzählungstyp in der Lage ist, verschiedene Fälle zu einem Datentyp zu vereinigen. Die verschiedenen Fälle, die es gibt, werden dann in dem algebraischen Datentyp zu einem einzigen Datentyp vereinigt. Man bezeichnet diese Vereinigung als Tagged, da durch den Konstruktor immer eindeutig ist, um welchen Teil der Vereinigung es sich handelt. Der folgende Datentyp illustriert noch einmal den Namen Tagged Union.

type IntOrString
    = IntValue Int
    | StringValue String

Der Datentyp IntOrString stellt entweder einen Int oder einen String dar, vereinigt also die möglichen Werte der Datentypen Int und String. Man nennt Typen, welche mehrere andere Typen zu einem neuen vereinigen auch Vereinigungstyp. Im Unterschied zu einem einfachen Vereinigungstyp ist bei einem Wert vom Typ IntOrString durch den Konstruktor klar, um welchen Teil der Vereinigung es sich handelt, also ob es sich um einen Int oder einen String handelt. Anders ausgedrückt: wenn wir den Typ IntOrString verwenden möchten, müssen wir den jeweiligen Konstruktor verwenden. Diese Eigenschaft ist elementar wichtig für die Typinferenz. Wenn die Typinferenz zum Beispiel den Konstruktor IntValue sieht, ist klar, dass es sich um den Typ IntOrString handelt. Bei Programmiersprachen, die Formen von Untagged Unions bieten, ist eine allgemeine Typinferenz wesentlich schwieriger.

Pattern Matching

Wir haben gesehen, dass man Pattern Matching nutzen kann, um Fallunterscheidungen über Zahlen durchzuführen. Man kann Pattern Matching außerdem nutzen, um die verschiedenen Fälle eines Aufzählungstyps zu unterscheiden. Man kann Pattern Matching aber auch ganz allgemein nutzen, um die verschiedenen Konstruktoren eines algebraischen Datentyps zu unterscheiden. Wir können zum Beispiel wie folgt eine Funktion isDraw definieren, um zu überprüfen, ob ein Spiel unentschieden ausgegangen ist.

isDraw : GameResult -> Bool
isDraw result =
    case result of
        Draw ->
            True

        Won _ ->
            False

Diese Funktion liefert True, falls das GameResult gleich Draw ist und False andernfalls. Die Teile Draw und Won _ sind Pattern. Der Unterstrich besagt, dass wir ignorieren, welche Form das Argument von Won hat. Das heißt, mit dem Muster Won _ sagen wir, diese Regel soll genommen werden, wenn der Wert in result ein Won-Konstruktor mit einem beliebigen Argument ist. Anstelle von Won _ könnten wir auch das Pattern _ verwenden. In diesem Fall passt dieses Muster immer. Die Funktionen verhalten sich mit der aktuellen Definition von GameResult identisch, unabhängig davon, ob wir das Pattern Won _ oder das Pattern _ nutzen. Wenn wir zum Datentyp GameResult aber einen weiteren Konstruktor hinzufügen würden, würde das Pattern _ auch für diesen Konstruktor passen, während da Pattern Won _ für diesen neuen Konstruktor nicht passt.

Anstelle des Unterstrichs können wir auch eine Variable verwenden, das heißt, statt Won _ können wir auch Won player schreiben. Wir können zum Beispiel wie folgt eine Funktion definieren, die zu einem Spiel-Ergebnis eine Beschreibung in Form eines Strings liefert.

description : GameResult -> String
description result =
    case result of
        Draw ->
            "Das Spiel ist unentschieden ausgegangen."

        Won player ->
            playerName player ++ " hat das Spiel gewonnen."

In diesem Fall wird die Variable player an den Wert vom Typ Player gebunden, der im Konstruktor Won steckt.

Pattern können auch geschachtelt werden. Das heißt, anstelle einer Variable können wir auch wieder ein komplexes Pattern verwenden. Die folgende Funktion verwendet zum Beispiel ein geschachteltes Pattern, um die x-Position eines Spielers zu bestimmen. Der Teil Player _ (Point x _) ist dabei das Pattern.

playerXCoord : Player -> Float
playerXCoord player =
    case player of
        Player _ (Point x _) ->
            x

Im zweiten Argument des Konstruktors Player steht ein Wert vom Typ Point. Daher können wir im Pattern an der entsprechenden Stelle auch ein Pattern für einen Point verwenden. Der Konstruktor Point erhält zwei Argumente, daher hat das Pattern Point x _ hier ebenfalls zwei Argumente. Das erste Argument binden wir an die Variable x, das zweite Argument ignorieren wir durch das Unterstrich-Pattern.

Als weiteres Beispiel für ein geschachteltes Pattern wollen wir noch einmal die Funktion definieren, die einen String liefert, der beschreibt, wie ein Spiel ausgegangen ist. In diesem Fall verzichten wir aber auf die Hilfsfunktion playerName und verwenden stattdessen ein geschachteltes Pattern.

description : GameResult -> String
description result =
    case result of
        Draw ->
            "Das Spiel ist unentschieden ausgegangen."

        Won (Player name _) ->
            name ++ " hat das Spiel gewonnen."

Wenn wir zum Beispiel den Ausdruck description (Won examplePlayer) in der REPL auswerten – wobei examplePlayer die weiter oben definierte Konstante ist – erhalten wir das folgende Ergebnis.

> description (Won examplePlayer)
"Spieler A hat das Spiel gewonnen." : String

Die Ausgabe der REPL bedeutet, dass der Aufruf description (Won examplePlayer) das Ergebnis

"Spieler A hat das Spiel gewonnen."

geliefert hat und dieses Ergebnis vom Typ String ist.

Ein case-Ausdruck wird für zwei Aufgaben genutzt. Zum einen führen wir eine Fallunterscheidung über die möglichen Konstruktoren eines Datentyps durch. Zum anderen zerlegen wir Konstruktoren in ihre Einzelteile.

Die folgende Grammatik gibt die Konstruktionsregeln für Pattern an. Die Grammatik illustriert – wie die Grammatik für Ausdrücke zuvor – die Konstruktionsprinzipien eines Pattern.

pattern = literal ;
        | identifier ;
        | "_" ;
        | "(" pattern ")" ;
        | constructor { pattern } ;
        | ...

An dieser Grammatik können wir sehen, dass Literale, also explizite Werte wie 1, 'a' oder "Hallo", Pattern sind. Außerdem sind Bezeichner, also Variablennamen wie x, name oder player Pattern. Die dritte Regel der Grammatik besagt, dass der Unterstrich _ ein Pattern ist. Die vierte Regel besagt, dass wir – analog zu den Ausdrücken – ein Pattern klammern können. Die letzte Regel besagt, dass ein Pattern aus einem Konstruktornamen bestehen kann und eine Sequenz von Pattern folgt.

Rekursive algebraische Datentypen

Algebraische Datentypen können auch rekursiv sein. Das heißt, wie eine rekursive Funktion kann ein Datentyp in seiner Definition wieder auf sich selbst verweisen.

Das Standardbeispiel für rekursive Datentypen in einer funktionalen Programmiersprache ist die Definition von einfach verketteten Listen. Diese Datenstruktur wird in funktionalen Programmiersprachen sehr häufig und für viele Anwendungsfälle verwendet. Wir können zum Beispiel wie folgt einen Datentyp definieren, der Listen mit Integern darstellt. In der funktionalen Programmierung haben sich die Namen Nil für eine leere Liste und Cons für eine nicht-leere Liste eingebürgert. Das Wort Nil ist eine Kurzform des lateinischen Wortes nihil, das “nichts” bedeutet.

type IntList
    = Nil
    | Cons Int IntList

Zuerst einmal wollen wir uns anschauen, wie wir mit diesem Datentyp Listen konstruieren können. Die Konstruktion eines Wertes funktioniert bei einem rekursiven Datentyp genau so wie bei den nicht-rekursiven Datentypen, die wir bisher kennengelernt haben. Um einen Wert zu konstruieren, verwenden wir einen Konstruktor. Wenn wir einen Konstruktor anwenden, dann gibt die Datentypdefinition an, welche Typen die Argumente jeweils haben müssen.

Wenn wir eine Liste definieren wollen, können wir also zum Beispiel den Konstruktor Nil verwenden, der keine Argumente nimmt.

exampleList1 : IntList
exampleList1 =
    Nil

Alternativ können wir eine Liste konstruieren, indem wir den Konstruktor Cons verwenden. Das erste Argument von Cons muss vom Typ Int sein. Das zweite Argument von Cons muss wiederum vom Typ IntList sein. Das heißt, wir können als zweites Argument von Cons zum Beispiel Nil verwenden.

exampleList2 : IntList
exampleList2 =
    Cons 23 Nil

Statt als zweites Argument von Cons den Konstruktor Nil zu verwenden, können wir auch wieder Cons verwenden. So definieren wir wie folgt zum Beispiel eine Liste mit zwei Elementen, nämlich 23 und 42.

exampleList3 : IntList
exampleList3 =
    Cons 23 (Cons 42 Nil)

Diese Listendatenstruktur ist einfach verkettet, da das erste Listenelement, das wir mit Cons 23 ... konstruieren, in seinem zweiten Argument einen Verweis auf die restlichen Elemente der Liste hat. Die Liste Cons 42 Nil hat aber keinen Verweis auf das vorherige Listenelement.

In der Praxis werden Werte von rekursiven Datentypen selten explizit definiert, wie es in exampleList1, exampleList2 und exampleList3 der Fall ist. Stattdessen werden diese Datentypen von Funktionen erzeugt und verarbeitet. Um rekursive Datentypen wirklich zu verstehen, ist es daher notwendig, sich rekursive Funktionen auf diesen Datentypen anzuschauen.

Wir starten mit der Definition einer Funktion, die die Länge einer Liste berechnet. Die meisten Funktionen, die eine rekursive Datenstruktur verarbeiten, sind selbst rekursiv. Um eine solche Funktion zu definieren, verwenden wir wie bei den nicht-rekursiven Funktionen Pattern Matching.

length : IntList -> Int
length list =
    case list of
        Nil ->
            0

        Cons _ restlist ->
            1 + length restlist

Die Funktion length testet zuerst, ob die Liste leer ist. In diesem Fall liefert length als Ergebnis 0 zurück. Falls die Liste nicht leer ist, wird der Konstruktor Cons zerlegt. Da wir nur die Länge der Liste berechnen wollen, ignorieren wir den Int-Wert, der im Cons-Konstruktor steht. Wir rufen die Funktion length rekursiv auf die Restliste restlist auf. Da die Liste Cons _ restlist um einen Eintrag länger ist als die Liste restlist, addieren wir auf das Ergebnis von length restlist noch 1 rauf. So erhalten wir die Länge der Liste Cons _ restlist. Als Beispiel betrachten wir die Anwendung length exampleList3.

length exampleList3

• =

  length (Cons 23 (Cons 42 Nil))

  Definition von exampleList3

• =

  case Cons 23 (Cons 42 Nil) of
      Nil ->
          0
  
      Cons _ restlist ->
          1 + length restlist

  Definition von length

• =

  1 + length (Cons 42 Nil)

  Auswertung des case-Ausdrucks

• =

  1 + (case Cons 42 Nil of
           Nil ->
               0
  
           Cons _ restlist ->
               1 + length restlist)

  Definition von length

• =

  1 + (1 + length Nil)

  Auswertung des case-Ausdrucks

• =

  1 + (1 + (case Nil of
                Nil ->
                    0
  
                Cons _ restlist ->
                    1 + length restlist))

  Definition von length

• =

  1 + (1 + 0)

  Auswertung des case-Ausdrucks

• =

  1 + 1

  Definition von +

• =

  2

  Definition von +

Als weiteres Beispiel zeigt die folgende Funktion, wie wir die Zahlen in einer Liste aufaddieren können.

sum : IntList -> Int
sum list =
    case list of
        Nil ->
            0

        Cons int restlist ->
            int + sum restlist

Das Muster ist bei der Funktion sum sehr ähnlich zur Funktion length. In diesem Fall ignorieren wir den Wert, der im Cons-Konstruktor steht, aber nicht, sondern addieren ihn auf das rekursive Ergebnis. Wenn wir den Ausdruck sum exampleList3 auswerten, erhalten wir ein sehr ähnliches Muster wie zuvor bei length exampleList3.

sum exampleList3

• =

  sum (Cons 23 (Cons 42 Nil))

  Definition von exampleList3

• =

  case Cons 23 (Cons 42 Nil) of
      Nil ->
          0
  
      Cons int restlist ->
          int + sum restlist

  Definition von sum

• =

  23 + sum (Cons 42 Nil)

  Auswertung des case-Ausdrucks

• =

  23 + (case Cons 42 Nil of
            Nil ->
                0
  
            Cons _ restlist ->
                int + sum restlist)

  Definition von sum

• =

  23 + (42 + sum Nil)

  Auswertung des case-Ausdrucks

• =

  23 + (42 + (case Nil of
                  Nil ->
                      0
  
                  Cons _ restlist ->
                      int + sum restlist))

  Definition von sum

• =

  23 + (42 + 0)

  Auswertung des case-Ausdrucks

• =

  23 + 42

  Definition von +

• =

  65

  Definition von +

Als nächstes wollen wir eine Funktion definieren, die zu einer Liste eine Liste berechnet, die jedes zweite Element der Originalliste enthält. Das heißt, der Aufruf everySecond (Cons 23 (Cons 42 (Cons 1729 Nil))) soll als Ergebnis die Liste Cons 42 Nil liefern, da wir das erste und das dritte Element verwerfen.

everySecond : IntList -> IntList
everySecond list =
    case list of
        Nil ->
            Nil

        Cons _ Nil ->
            Nil

        Cons _ (Cons int restlist) ->
            Cons int (everySecond restlist)

Um diese Funktion umzusetzen, verwenden wir ein geschachteltes Pattern. Das Muster Cons _ (Cons int restlist) prüft, ob die Liste mindestens zwei Elemente enthält. Im Ergebnis erstellen wir dann eine Liste, die nur das Element int enthält und als Restliste das Ergebnis des rekursiven Aufrufs everySecond restlist enthält. Zur Illustration betrachten wir die Auswertung des Ausdrucks everySecond exampleList3.

everySecond exampleList3

• =

  everySecond (Cons 23 (Cons 42 Nil))

  Definition von exampleList3

• =

  case Cons 23 (Cons 42 Nil) of
      Nil ->
          Nil
  
      Cons _ Nil ->
          Nil
  
      Cons _ (Cons int restlist) ->
          Cons int (everySecond restlist)

  Definition von everySecond

• =

  Cons 42 (everySecond Nil)

  Auswertung des case-Ausdrucks

• =

  Cons 42 (case Nil of
               Nil ->
                   Nil
  
               Cons _ Nil ->
                   Nil
  
               Cons _ (Cons int restlist) ->
                   Cons int (everySecond restlist))

  Definition von everySecond

• =

  Cons 42 Nil

  Auswertung des case-Ausdrucks

Wir wollen anhand der Funktion everySecond noch einen weiteren Aspekt von Rekursion illustrieren. Wir können die Funktion everySecond auch durch zwei Funktionen definieren, die sich gegenseitig rekursiv aufrufen. Während die eine Funktion das erste Element der Liste verwirft, übernimmt die andere Funktion das erste Element der Liste in das Ergebnis. Wir rufen diese Funktionen dann abwechseln auf, so dass abwechselnd ein Element der übernommen und ein Element verworfen wird.

everySecondMutually : IntList -> IntList
everySecondMutually list =
    case list of
        Nil ->
            Nil

        Cons _ restlist ->
            everySecondMutually_ restlist


everySecondMutually_ : IntList -> IntList
everySecondMutually_ list =
    case list of
        Nil ->
            Nil

        Cons int restlist ->
            Cons int (everySecondMutually restlist)

Die Funktionen everySecondMutually und everySecondMutually_ wechseln sich bei der Rekursion ab. Ein solches Muster bezeichnet man als gegenseitig rekursiv (mutually recursive).

Als Abschluss für rekursive Funktionen auf Listen wollen wir eine Funktion definieren, die zwei Listen hintereinanderhängt. Diese Funktion wird klassischerweise als append bezeichnet.

append : IntList -> IntList -> IntList
append list1 list2 =
    case list1 of
        Nil ->
            list2

        Cons int restlist1 ->
            Cons int (append restlist1 list2)

Diese Funktion rekonstruiert ihr erstes Argument. Wenn die Rekonstruktion schließlich bei der leeren Liste angekommen ist, liefert die Funktion das zweite Argument zurück. Auf diese Weise wird die leere Liste in der Liste list1 durch die Liste list2 ersetzt.

Listen sind die am häufigsten verwendete rekursive Datenstruktur in der funktionalen Programmierung. Es gibt aber noch viele andere rekursive Datenstrukturen. Um weitere Aspekte von rekursiven Datenstrukturen zu illustrieren, wollen wir uns an dieser Stelle noch eine weitere rekursive Datenstruktur anschauen.

Ein Baum ist vergleichsweise eng mit einer Liste verwandt. Ein Baum unterscheidet sich im Wesentlichen dadurch, dass ein Inhalt nicht einen, sondern mehrere Nachfolger hat. Bei einem Binärbaum hat ein sogenannter Knoten zwei Nachfolger. Im Folgenden wollen wir einen Datentyp für binäre Bäume in Elm betrachten. Wir betrachten an dieser Stelle wieder den Spezialfall eines Baumes, der ganze Zahlen enthält.

type IntBinTree
    = Empty
    | Node IntBinTree Int IntBinTree

Ein Baum ist entweder leer oder es handelt sich um einen Knoten, der eine Zahl enthält und zwei Nachfolger hat.

Wir wollen zuerst wieder zwei Beispielwerte für diesen Datentyp konstruieren. Um einen Wert vom Typ IntBinTree zu konstruieren, können wir entweder den Konstruktor Empty verwenden oder den Konstruktor Node. Im ersten Fall verwenden wir den Konstruktor Empty.

exampleTree1 : IntBinTree
exampleTree1 =
    Empty

Alternativ können wir einen Baum konstruieren, indem wir den Konstruktor Node verwenden. Das erste Argument von Node muss vom Typ IntBinTree sein. Wir verwenden an dieser Stelle den Ausdruck Node Empty 23 Empty, der vom Typ IntBinTree ist. Das zweite Argument von Node muss vom Typ Int sein. Das dritte Argument von Node muss wiederum vom Typ IntBinTree sein. Wir verwenden an dieser Stelle den Ausdruck Empty, der ebenfalls vom Typ IntBinTree ist.

exampleTree2 : IntBinTree
exampleTree2 =
    Node (Node Empty 23 Empty) 42 Empty

Wir können für einen Baum zum Beispiel wie folgt eine Funktion definieren, die nach einer spezifischen Zahl in einem Baum sucht.

member : Int -> IntBinTree -> Bool
member int tree =
    case tree of
        Empty ->
            False

        Node leftTree value rightTree ->
            int == value || member int leftTree || member int rightTree

Um das Verhalten der Funktion member zu illustrieren werten wir den Ausdruck member 23 exampleTree2 aus.

Wichtig

Obwohl Elm eine strikte Programmiersprache ist, das heißt, Call-by Value nutzt, verhalten sich die Operatoren || und && wie in den meisten anderen Sprachen nicht-strikt.

Das heißt, zum Beispiel, der Operator || wertet zuerst nur sein linkes Argument aus. Hat dieses Argument den Wert False, so wertet || auch sein rechtes Argument aus. Ist der Wert des linken Argumentes aber True, so wird das rechte Argument ähnlich wie beim if-Ausdruck nicht ausgewertet.

member 23 exampleTree2

• =

  member 23 (Node (Node Empty 23 Empty) 42 Empty)

  Definition von exampleTree2

• =

  case Node (Node Empty 23 Empty) 42 Empty of
      Empty ->
          False
  
      Node leftTree value rightTree ->
          23 == value || member 23 leftTree || member 23 rightTree

  Definition von everySecond

• =

  23 == 42 || member 23 (Node Empty 23 Empty) || member 23 Empty

  Auswertung des case-Ausdrucks

• =

  23 == 42 || (member 23 (Node Empty 23 Empty) || member 23 Empty)

  Assoziativität von ||

• =

  False || (member 23 (Node Empty 23 Empty) || member 23 Empty)

  Definition von ==

• =

  member 23 (Node Empty 23 Empty) || member 23 Empty

  Definition von ||

• =

  (case Node Empty 23 Empty of
       Empty ->
             False
  
       Node leftTree value rightTree ->
             23 == value || member 23 leftTree || member 23 rightTree)
      || member 23 Empty

  Definition von member

• =

  (23 == 23 || member 23 Empty || member 23 Empty) || member 23 Empty

  Auswertung des case-Ausdrucks

• =

  (23 == 23 || (member 23 Empty || member 23 Empty)) || member 23 Empty

  Assoziativität von ||

• =

  (True || (member 23 Empty || member 23 Empty)) || member 23 Empty

  Definition von ==

• =

  True || member 23 Empty

  Definition von ==

• =

  True

  Definition von ||

Als weiteres Beispiel wollen wir eine Funktion definieren, die einen Baum spiegelt. Wenn man den ursprünglichen Baum auf einen Zettel malt und daneben einen Spiegel stellt, erhält man den Baum, den die Funktion mirror liefert.

mirror : IntBinTree -> IntBinTree
mirror tree =
    case tree of
        Empty ->
            tree

        Node leftTree value rightTree ->
            Node (mirror rightTree) value (mirror leftTree)

Baumstrukturen wirken auf den ersten Blick sehr theoretisch, tauchen aber in Wirklichkeit bei der Arbeit mit jedem Dateiformat auf. Zum Beispiel wird die Struktur einer HTML-Seite durch einen Baum repräsentiert, nicht nur in funktionalen Sprachen, sondern ganz allgemein. Der Datentyp IntBinTree modelliert binäre Bäume, also Bäume, bei denen jeder Knoten zwei Nachfolger hat. Im Gegensatz dazu ist eine HTML-Struktur ein beliebig verzweigter Baum, da jedes HTML-Element beliebig viele Nachfolgerelemente haben kann. Um einen Datentyp für HTML-Strukturen zu definieren, benötigen wir daher Listen, die HTML-Strukturen enthalten. Bisher haben wir nur Listen kennengelernt, die ganze Zahlen enthalten. Zur Modellierung von HTML-Strukturen benötigen wir außerdem Listen, die Attribute enthalten. Um für diese Listen nicht mehrere Listen-Datentypen definieren zu müssen, werden wir die Definition einer Baumstruktur zur Modellierung von HTML-Strukturen auf später verschieben, wenn wir das Konzept des parametrischen Polymorphismus kennengelernt haben. Parametrischer Polymorphismus erlaubt es uns, eine Datenstruktur wie eine Liste einmal zu definieren und dieselbe Implementierung für verschiedene Inhaltstypen zu verwenden.

Um zu illustrieren, dass man mit diesen vergleichsweise einfachen Konstruktionsmechanismen vergleichsweise komplexe Varianten erzeugen kann, wollen wir uns noch einen etwas ausgefalleneren algebraischen Datentyp anschauen.

type Even
    = Zero
    | SuccOdd Odd


type Odd
    = SuccEven Even

Dieser Datentyp nutzt die sogenannte Peano-Darstellung von natürlichen Zahlen. Dabei ist null eine natürliche Zahl und der Nachfolger von jeder natürlichen Zahl ist wieder eine natürliche Zahl. Die Datentypen Even und Odd unterscheiden zusätzlich noch zwischen geraden und ungeraden natürlichen Zahlen. Man sagt, dass die Datentypen Even und Odd gegenseitig rekursiv (mutually recursive) sind.

Als Beispiel definieren wir zwei Funktionen auf den Datentypen Even und Odd. Diese Funktionen multiplizieren eine Zahl jeweils mit zwei. Wenn man eine gerade Zahl mit zwei multipliziert, erhält man wieder eine gerade Zahl. Wenn man eine ungerade Zahl mit zwei multipliziert, erhält man ebenfalls eine gerade Zahl.

twoTimesEven : Even -> Even
twoTimesEven even =
    case even of
        Zero ->
            Zero

        SuccOdd odd ->
            SuccOdd (SuccEven (twoTimesOdd odd))


twoTimesOdd : Odd -> Even
twoTimesOdd odd =
    case odd of
        SuccEven even ->
            SuccOdd (SuccEven (twoTimesEven even))

Um eine Zahl in der Peano-Darstellung mit zwei zu multiplizieren, muss man jeden Konstruktor der Form Succ* durch zwei dieser Konstruktoren ersetzen. Dies hat zur Folge, dass das Ergebnis doppelt so viele Succ*-Konstruktoren enthält wie das Argument.

• zurück
• Inhaltsverzeichnis
• weiter

1. Artikel zum Thema “Algebraische Datentypen” bei Wikipedia ↩

2. Artikel zum Thema “Programmiersprachentheorie” bei Wikipedia ↩