Datentypen

In diesem Kapitel wollen wir die Grundlagen für die Definition von Datentypen in Elm einführen. Wir haben bereits eine Reihe von Datentypen kennengelernt, zum Beispiel Listen und Aufzählungstypen. In diesem Kapitel werden wir zum Beispiel lernen, wie man einen Datentyp für Listen in Elm definiert.

Records

Da Elm als JavaScript-Ersatz gedacht ist, unterstützt es auch Recordtypen. Wir können zum Beispiel eine Funktion, die für einen Nutzer testet, ob er volljährig ist, wie folgt definieren.

hasFullAge : { firstName : String, lastName : String, age : Int } -> Bool
hasFullAge user =
    user.age >= 18

Diese Funktion erhält einen Record mit dem Feldern firstName, lastName und age als Argument und liefert einen Wert vom Typ Bool. Im Record haben die Felder firstName und lastName Einträge vom Typ String und das Feld age hat einen Eintrag vom Typ Int. Der Ausdruck user.age ist eine Kurzform für .age user, das heißt, .age ist eine Funktion, die einen entsprechenden Record erhält und einen Wert vom Typ Int, nämlich das Alter zurückliefert. Man nennt eine Funktion wie .age einen Record-Selektor, da die Funktion aus einem Record einen Teil selektiert. Das heißt, hinter dem Ausdruck user.age steht eigentlich auch nur eine Funktionsanwendung, nur dass es eine etwas vereinfachte Syntax für diesen Aufruf gibt, die näher an der Syntax ist, die wir aus anderen Sprachen gewohnt sind.

Es ist recht umständlich, den Typ des Nutzers in einem Programm bei jeder Funktion explizit anzugeben. Um unser Beispiel leserlicher zu gestalten, können wir das folgende Typsynonym für unseren Recordtyp einführen.

type alias User =
    { firstName : String
    , lastName : String
    , age : Int
    }

hasFullAge : User -> Bool
hasFullAge user =
    user.age >= 18

Das heißt, wir führen den Namen User als Kurzschreibweise für einen Record ein und nutzen diesen Typ dann an allen Stellen, an denen wir zuvor den ausführlichen Recordtyp genutzt hätten.

Es gibt eine spezielle Syntax, um initial einen Record zu erzeugen.

exampleUser : User
exampleUser =
    { firstName = "Max", lastName = "Mustermann", age = 42 }

Wir können einen Record natürlich auch abändern. Zu diesem Zweck wird die folgende Update-Syntax verwendet. Die Funktion maturing erhält einen Record in der Variable user und liefert einen Record zurück, bei dem die Felder firstName und lastName die gleichen Einträge haben wie user, das Feld age ist beim Ergebnis-Record aber auf den Wert 18 gesetzt.

maturing : User -> User
maturing user =
    { user | age = 18 }

Wichtig

Da Elm eine rein funktionale Programmiersprache ist, wird hier der Record nicht wirklich abgeändert, sondern ein neuer Record mit anderen Werten erstellt.

Das heißt, die Funktion maturing erstellt einen neuen Record, dessen Einträge firstName und lastName die gleichen Werte haben wie die entsprechenden Einträge von user und dessen Eintrag age auf 18 gesetzt ist. Dieses Beispiel demonstriert eine sehr einfache Form von deklarativer Programmierung. In einem sehr imperativen Ansatz, müssten wir den Code, um den neuen Record zu erzeugen und die Felder firstName und lastName zu kopieren, explizit schreiben. In einem deklarativeren Ansatz verwenden wir stattdessen eine spezielle Syntax oder eine vordefinierte Funktion, um das gleiche Ziel zu erreichen.

Wir können das Verändern eines Recordeintrags und das Lesen eines Eintrags natürlich auch kombinieren. Wir können zum Beispiel die folgende Definition verwenden, um einen Benutzer altern zu lassen.

increaseAge : User -> User
increaseAge user =
    { user | age = user.age + 1 }

Es ist auch möglich, mehrere Felder auf einmal abzuändern, wie die folgende Funktion illustriert.

japanese : User -> User
japanese user =
    { user | firstName = user.lastName, lastName = user.firstName }

An dieser Stelle soll kurz auf die Vorteile von unveränderbaren Datenstrukturen hingewiesen werden. Zu diesen Zweck betrachten wir die folgende “Übersetzung” des Beispiels nach Java.

public static User japanese(User user) {
    user.setFirstName(user.getLastName());
    user.setLastName(user.getFirstName());
    return user;
}

Diese Methode liefert nicht das gewünschte Ergebnis, da wir zuerst den Vornamen auf den Nachnamen setzen und in der folgende Zeile den zuvor gesetzen Vornamen auslesen. Das heißt, nach Ausführung der Methode japanese sind Vor- und Nachname auf den Nachnamen gesetzt.

Zu guter Letzt können wir auch Pattern Matching verwenden, um auf die Felder eines Records zuzugreifen. Zu diesem Zweck müssen wir die Variablen im Pattern nennen wie die Felder des entsprechenden Recordtyps.

fullName : User -> String
fullName { firstName, lastName } =
    firstName ++ " " ++ lastName

Wir müssen dabei nicht auf alle Felder des Records Pattern Matching machen, es ist auch möglich, nur einige Felder aufzuführen. Das heißt, auch die folgende Definition ist erlaubt.

firstNames : User -> List String
firstNames { firstName } =
    List.words firstName

Pattern Matching auf Records eignet sich sehr gut, wenn wir die Felder des Records nur lesen möchten. Durch das Pattern Matching können wir den Code kürzen, da die Verwendung der Record-Selektoren länger ist. Außerdem kann es sehr sinnvoll sein, Pattern Matching auf einem Record zu verwenden, wenn es schwierig ist, für den gesamten Record einen sinnvollen Namen zu vergeben. Ein solches Beispiel werden wir weiter unten bei der Funktion rotate kennenlernen.

Wenn wir für einen Record ein Typsynonym einführen, gibt es eine Kurzschreibweise, um einen Record zu erstellen. Um einen Wert vom Typ User zu erstellen, können wir zum Beispiel auch User "John" "Doe" 20 schreiben. Dabei gibt die Reihenfolge der Felder in der Definition des Records an, in welcher Reihenfolge die Argumente übergeben werden. Wir werden im Kapitel Funktionen höherer Ordnung sehen, dass diese Art der Konstruktion bei der Verwendung einer partiellen Applikation praktisch ist. Diese Konstruktion eines Records hat allerdings den Nachteil, dass in der Definition des Records die Reihenfolge der Einträge nicht ohne Weiteres geändert werden kann. Insbesondere besteht die Gefahr, dass wir die Reihenfolge ändern, ohne dass ein Kompilerfehler auftritt. Wenn wir zum Beispiel die Definition von User wie folgt abändern

type alias User =
    { lastName : String
    , firstName : String
    , age : Int
    }

und User "John" "Doe" 20 in unserem Programm verwenden, erhalten wir keinen Fehler, die Anwendung verhält sich aber nicht mehr korrekt.

An dieser Stelle soll noch kurz ein interessanter Anwendungsfall für Records erwähnt werden. Einige Programmiersprachen bieten benannte Argumente als Sprachfeature. Das heißt, Argumente einer Funktion bzw. Methode können einen Namen erhalten, um Entwickler*innen beim Aufruf der Methode klarzumachen, welche Semantik die einzelnen Argumente haben. Wir betrachten als Beispiel die folgende Funktion, die genutzt werden kann, um das transform-Attribut in einer SVG-Graphik zu setzen.

rotate : String -> String -> String -> String
rotate angle x y =
    "rotate(" ++ angle ++ "," ++ x ++ "," ++ y ++ ")"

Wir können diese Funktion nun zum Beispiel mittels rotate "50" "60" "10" aufrufen. Um bei diesem Aufruf herauszufinden, welches der Argumente welche Bedeutung hat, müssen wir uns die Funktion rotate anschauen. In einer Programmiersprache mit benannten Argumenten, können wir den Argumenten einer Funktion/Methode Namen geben und diese Namen beim Aufruf nutzen.

Wichtig

In einer Programmiersprache mit Records können wir diese Funktionalität mithilfe eines Records nachstellen.

Wir können die Funktion rotate zum Beispiel wie folgt definieren.

rotate : { angle : String, x : String, y : String } -> String
rotate { angle, x, y } =
    "rotate(" ++ angle ++ "," ++ x ++ "," ++ y ++ ")"

Wenn wir die Funktion rotate nun aufrufen, schreiben wir rotate { angle = "50", x = "60", y = "10" } und sehen direkt beim Aufruf, welche Semantik die verschiedenen Parameter haben.

Wir können die Struktur der Funktion rotate noch weiter verbessern. Zuerst können wir observieren, dass die Argumente der Funktion rotate nicht alle gleichberechtigt sind. Anders ausdrückt gehören die Argumente x und y der Funktion stärker zusammen, da sie gemeinsam einen Punkt bilden. Diese Eigenschaft können wir in unserem Code wie folgt explizit darstellen.

type alias Point =
    { x : String, y : String }


rotate : { angle : String, origin : Point } -> String
rotate { angle, origin } =
    "rotate(" ++ angle ++ "," ++ origin.x ++ "," ++ origin.y ++ ")"

Wichtig

Gute Programmierer*innen zeichnen sich dadurch aus, dass sie solche Strukturen erkennen und zur Strukturierung des Programms nutzen.

Wir können diese Implementierung aber noch in einem weiteren Aspekt verbessern. Aktuell arbeitet unsere Anwendung mit Werten vom Typ String. Das heißt, wir können auch "a" als Winkel an die Funktion rotate übergeben und müssen dann erst observieren, dass die Anwendung nicht das gewünschte Ergebnis anzeigt. Um eine offensichtlich falsche Verwendung wie diese zu verhindern, können wir statt des Typs String einen Datentyp mit mehr Struktur nutzen.

type alias Point =
    { x : Float, y : Float }


rotate : { angle : Float, origin : Point } -> String
rotate { angle, origin } =
    "rotate("
        ++ String.fromFloat angle
        ++ ","
        ++ String.fromFloat origin.x
        ++ ","
        ++ String.fromFloat origin.y
        ++ ")"

Wenn wir nun versuchen würden, den String "a" als Winkel an die Funktion rotate zu übergeben, würden wir direkt beim Übersetzen des Codes einen Fehler vom Compiler erhalten. Grundsätzlich sind Fehler zur Kompilierzeit (Compile Time) besser als Fehler zur Laufzeit (Run Time), da Fehler zur Kompilierzeit nicht bei Kund*innen auftreten können.

Wichtig

Man sollte in allen Programmiersprachen mit Datentypen mit möglichst viel Struktur arbeiten. Der Datentyp String ist zum Beispiel nur die richtige Wahl, wenn es tatsächlich um einen beliebigen Text handeln kann.

Wichtig

Listen können häufig genutzt werden, um repetitiven Code besser zu strukturieren.

Als Beispiel betrachten wir die Verwendung der Funktion String.concat : List String -> String. Diese Funktion erhält eine Liste von Strings und hängt diese alle aneinander. Wir können diese Funktion zum Beispiel wie folgt nutzen, um die Definition von rotate erweiterbarer zu gestalten.

rotate : { angle : Float, origin : Point } -> String
rotate { angle, origin } =
    String.concat
        [ "rotate("
        , String.fromFloat angle
        , ","
        , String.fromFloat origin.x
        , ","
        , String.fromFloat origin.y
        , ")"
        ]

Wenn wir diese Funktion noch etwas genauer betrachten, stellen wir fest, dass die Wiederholung in der Definition vor allem durch die Trennung der Argumente von rotate durch Kommata entsteht. Mithilfe der Funktion String.join : String -> List String -> String können wir diesen Aspekt noch klarer herausarbeiten. Hier verwenden wir wieder eine Liste, um das wiederholte Hinzufügen eines Kommas besser zu strukturieren.

rotate : { angle : Float, origin : Point } -> String
rotate { angle, origin } =
    "rotate("
        ++ String.join ","
            [ String.fromFloat angle
            , String.fromFloat origin.x
            , String.fromFloat origin.y
            ]
        ++ ")"

Algebraische Datentypen

In diesem Abschnitt werden wir uns ansehen, wie man in Elm sogenannte algebraische Datentypen¹ definieren kann. Zuerst betrachten wir, in welchen 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. Im Gegensatz zu Funktionen und Variablen müssen Konstruktoren und Datentypen immer mit einem großen Anfangsbuchstaben 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. 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 entsprechende 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.

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.concat
                [ "("
                , 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 können wir nun einen Player definieren.

examplePlayer :: Player
examplePlayer =
    Player "Player 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 "Player 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.

Info

Wie mit einer Algebra in der Mathematik kann man tatsächlich mit algebraischen Datentypen auch “rechnen”.

Der algebraische Datentyp Bool hat zwei Werte. Wenn wir den folgenden Datentyp definieren

type Product
    = Product Bool Bool

erzeugen wir das Product aus dem Datentyp Bool mit sich selbst, das heißt, wir “multiplizieren” den Typ Bool mit dem Typ Bool. Analog hat der Datentyp Product tatsächlich auch 4 = 2 * 2 mögliche Werte, nämlich Product False False, Product False True, Product True False und Product True True. Die Analogie zu algebraischen Regeln, wie sie aus der Mathematik bekannt sind, geht noch wesentlich weiter und lässt sich mit polymorphen Datentypen noch besser illustrieren als mit monomorphen Datentypen, wie sie hier verwendet werden. Polymorphe Datentypen lernen wir erst in einem späteren Kapitel kennen.

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
    = Win Player
    | Draw

Der Konstruktor Win 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

        Win _ ->
            False

Diese Funktion liefert True, falls das GameResult gleich Draw ist und False andernfalls. Der Unterstrich besagt, dass wir ignorieren, welche Form das Argument von Win hat. Das heißt, mit dem Muster Win _ sagen wir, diese Regel soll genommen werden, wenn der Wert in result ein Win-Konstruktor mit einem beliebigen Argument ist. Anstelle des Unterstrichs können wir auch eine Variable verwenden, das heißt, statt Win _ können wir auch Win 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."

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

In diesem Fall wird die Variable player an den Wert vom Typ Player gebunden, der im Konstruktor Win 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.

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.

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."

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

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

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

Die Ausgabe der REPL bedeutet, dass der Aufruf description (Win 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. Bei Datentypen, die nur einen Konstruktor zur Verfügung stellen, wie etwa der Typ Point, müssen wir keine Fallunterscheidung über die verschiedenen Konstruktoren durchführen. Daher kann man ein Pattern für Datentypen mit nur einem Konstruktor auch ohne einen case-Ausdruck verwenden. Die folgende Funktion liefert zum Beispiel die x-Koordinate eines Punktes. Wir schreiben in dieser Variante das Pattern also an die Stelle, an der wir sonst die Variable für den Parameter der Funktion schreiben.

xCoord : Point -> Float
xCoord (Point x _) =
    x

Info

Diese Art des Pattern Matching entspricht dem Stil der regel-basierten Definition in Haskell. Der einzige Unterschied besteht darin, dass es in Elm in diesem Fall immer nur eine Regel gibt, da es immer nur einen Konstruktor gibt, wenn diese Art des Pattern Matching angewendet werden kann.

Wenn wir sowohl die gesamte Struktur, die übergeben wird, benötigen als auch einen Teil der Struktur kann man mit dem Schlüsselwort as einen Namen für die gesamte Struktur einführen. Das heißt, im folgenden Beispiel wird der übergebene Punkt an die Variable point gebunden und die x-Koordinate an die Variable x.

xCoord : Point -> Float
xCoord ((Point x _) as point) =
    ...

Diese Art des Pattern wird als Pattern Alias bezeichnet, da ein Alias für ein Pattern eingeführt wird. Ein Pattern Alias kann an jeder Stelle eingesetzt werden, an der ein Pattern steht.

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

Hier wird der Pattern Alias geschachtelt in einem anderen Pattern verwendet.

Info

In Haskell wird für ein Pattern Alias anstelle des Schlüsselwortes as das @ verwendet und der Alias wird vor das Pattern geschrieben. Das heißt, wir schreiben in Haskell zum Beispiel point@Point x _.

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 ")" ;
        | "(" pattern ")" "as" identifier ;
        | constructor { pattern } ;
        | "{" fieldName { "," fieldName } "}" ;
        | ...

An dieser Stelle soll kurz auf die Grammatik für Record-Pattern eingegangen werden. Die Grammatik besagt, dass man geschweifte Klammern nutzt und die Einträge durch Kommata trennt. Im Unterschied zu den anderen Regeln, stehen hier in den Einträgen aber nicht pattern sondern fieldName. Das heißt, die Einträge in eine Record-Pattern sind nicht selbst wieder Pattern sondern Feldnamen. Wenn in einem Record-Pattern wieder Pattern stehen würden, könnte man nicht immer eindeutig identifizieren auf welchen Eintrag im Record sich das Pattern bezieht. Daher müssen in einem Record-Pattern im Gegensatz zu allen anderen Formen von Pattern immer die Namen von Feldern stehen. Man kann also bei einem Record-Pattern zum Beispiel kein tiefes Pattern Matching durchführen.

Rekursive Datentypen

Datentypen können auch rekursiv sein. Das heißt, wie eine rekursive Funktion kann ein Datentyp in seiner Definition wieder auf sich selbst verweisen. 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 jetzt 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)

Wir wollen einmal eine Funktion definieren, die die Länge einer solchen 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 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.

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 13 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.

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 sein 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.

Wir wollen an dieser Stelle auch ganz kurz das Speichermodell und die Laufzeit von Funktionen in Elm diskutieren. Das Aufrufen eines Konstruktors sowie Pattern Matching sind konstante Operationen. Das heißt, die Laufzeit der Funktion append ist linear in der Länge der ersten Liste. Wenn wir einen Konstruktor verwenden, wird im Heap eine entsprechende Struktur angelegt. In der Funktion append wird zum Beispiel die Liste list1 neu erstellt, da wir in der Regel für Cons den Konstruktor jeweils neu erstellen. Wenn die Funktion append am Ende von list1 angekommen ist, wird die Liste list2 aber einfach zurückgegeben, wie sie ist. Dadurch entsteht nach einem Aufruf von append im Speicher die folgende Struktur.

Speicherstruktur nach dem Aufruf append list1 list2

Das heißt, das Ergebnis des Aufrufs append list1 list2 hat die Cons-Zellen mit den Werten 1, 2 und 3 neu erstellt. Diese existieren jetzt doppelt im Speicher. Falls wir die Liste list1 anschließend nicht weiter verwenden, wird sie durch den Garbage Collector aus dem Speicher entfernt. Die Liste list2 wird aber nicht dupliziert, sondern die Variable list2 und das Ergebnis von append list1 list2 verweisen beide auf die gleiche Struktur im Speicher.

Als weiteres Beispiel eines rekursiven Datentyps wollen wir uns eine Baumstruktur anschauen. Der folgende Datentyp stellt zum Beispiel einen binären Baum mit ganzen Zahlen in den Knoten dar.

type IntTree
    = Empty
    | Node IntTree Int IntTree

Die folgende Definition gibt einen Wert dieses Typs an.

exampleTree : IntTree
exampleTree =
    Node (Node Empty 3 (Node Empty 5 Empty)) 8 Empty

Wir können zum Beispiel wie folgt eine Funktion schreiben, die testet, ob ein Eintrag in einem Baum vorhanden ist.

find : Int -> IntTree -> Bool
find n tree =
    case tree of
        Empty ->
            False

        Node leftree int righttree ->
            n == int || find n lefttree || find n righttree

Wichtig

Im Unterschied zur Programmiersprache Haskell ist Elm eine strikte Sprache, nutzt also call-by-value als Auswertungsstrategie.

Das heißt, bei Definitionen wie find müssen wir beachten, dass rekursive Aufrufe auch durchgeführt werden, wenn ihr Ergebnis ggf. gar nicht benötigt wird. Der Ausdruck n == int || find n lefttree müsste zum Beispiel beide Argumente von || auswerten, auch wenn der gesuchte Eintrag bereits gefunden wurde, also n == int als Ergebnis True liefert.

In Elm – wie in vielen anderen Programmiersprachen – sind die logischen Operatoren || und && daher als Kurzschlussoperatoren definiert. Das heißt, falls das erste Argument von || bereits True ist, wird das zweite Argument nicht ausgewertet. Falls das erste Argument von && bereits False ist, wird das zweite Argument ebenfalls nicht ausgewertet. Anders ausgedrückt sind die Operatoren || und && nicht-strikt, obwohl die Programmiersprache Elm strikt ist. In vielen strikten Programmiersprachen sind die Operatoren für das logische Oder und das logische Und nicht-strikt, um unnötige Berechnungen in diesem Fall zu vermeiden.

• zurück
• Inhaltsverzeichnis
• weiter

1. Wikipedia-Artikel zum Thema Algebraische Datentypen ↩

2. Wikipedia-Artikel zum Thema Programmiersprachentheorie ↩