3. Zusammengesetzte Datentypen

3.6 Rekursive Datentypen

In unserem Geometrie-Projekt haben wir Punkte im zweidimensionalen Raum als Objekte vom Typ (Float, Float) repräsentiert. Im dreidimensionalen Raum könnten wir (Float, (Float, Float)) verwenden; vierdimensional (Float, (Float, (Float, Float))). Eine Obergrenze ist hier nur durch unsere Geduld gegeben. Wie können wir aber Sequenzen darstellen, wo wir die Länge ("Dimension") nicht von vornherein kennen? Beliebig lange Folgen von Messwerten; Liste von Studierenden; Liste von Banktransaktionen. Geschachtelte Tupel können wir nicht verwenden, da ja bereits im Typ drinsteht, wieviele Elemente da gespeichert sind; eine Variable vom Typ (Float, (Float, Float)) besteht aus drei Float-Werten; das wissen wir bereits, bevor das Programm läuft. Mit Tupeln kommen wir also nicht weiter.

Mit Custom Types können wir zwar Varianten definieren, die verschieden viele Payloads haben; allerdings ist auch hier von vornherein klar, wieviele das sein werden:

type Gruppe
    = Allein String
    | Paar String String
    | Tripel String String String
    | Quadrupel String String String String
    | Gruppe5 String String String String String

Schon vom Datentyp Gruppe her ist klar, dass sie nicht mehr als 5 Elemente haben kann. Wie können wir aus dieser Limitierung ausbrechen, also mit endlichem Code einen Typ definieren, der beliebig viele Dinge umfassen kann? Die Antwort lautet: mit rekursiven Datentypen. Eine endliche Zahlenfolge beispielsweise ist entweder leer oder besteht aus einem ersten Element und einer Restfolge. Also:

type Folge
    = Leer
    | Paar Int Folge

Ein Objekt vom Typ Folge können wir dann ganz normal konstruieren:

x = Paar 5 Leer                        
Paar 5 Leer : Folge
y = Paar 3 x
Paar 3 (Paar 5 Leer) : Folge 
Paar 1 (Paar 2 y)
Paar 1 (Paar 2 (Paar 3 (Paar 5 Leer))) : Folge

Beachten Sie, dass der Datentyp Folge zwar beliebig lange Folgen erlaubt, jede jedoch endlich sein muss, weil wir ja irgendwo mit Leer anfangen müssen. Der Datentyp

type Weird
    = Pair Int Weird

ist zwar "legal", der Elm-Compiler lässt es Ihnen durchgehen, allerdings ist es unmöglich, ein Objekt vom Typ Unendlich überhaupt zu konstruieren. Denn dafür müssten wir ja Pair x w aufrufen, wobei w ein bereits konstruierter Wert vom Typ Weird ist. Wir können also nie überhaupt erst anfangen.

Rekursive Datentypen verarbeiten sie genau wie alle anderen Custom Types: indem Sie mit einem case-Ausdruck alle Konstruktoren durchgehen und gegebenenfalls die Payload auffangen. Beispielsweise hier laenge, die die Länge einer Folge berechnet und allesVerdoppeln, die jeden Eintrag verdoppelt:

laenge : Folge -> Int
laenge folge =
    case folge of
        Leer ->
            0

        Paar x rest ->
            1 + laenge rest


allesVerdoppeln : Folge -> Folge 
allesVerdoppeln folge = 
    case folge of 
        Leer -> 
            Leer 

        Paar x rest -> 
            Paar (2*x) (allesVerdoppeln rest)

Folgen mit Typenvariablen

Wenn wir nun statt Zahlenfolgen mit Folgen von Strings arbeiten wollen, beispielsweise um eine Liste von Kunden zu verwalten, dann müssten wir einen weiteren Datentyp einführen, beispielsweise FolgeString:

type FolgeString
    = LeerString
    | PaarString Int FolgeString

Das gleiche für Folgen aus Date aus TaxPayer und so weiter. Der Code für Funktionen wie laenge würde im Wesentlichen der Gleiche bleiben, wir müssten ihn aber jedes Mal kopieren. Daher verwenden wir besser Typenvariablen:

type Folge a
    = Leer
    | Paar a (Folge a)


laenge : Folge a -> Int
laenge folge =
    case folge of
        Leer ->
            0

        Paar x rest ->
            1 + laenge rest                        

Ein Datentyp, der beliebig viele Elemente in einer Folge enthalten kann, ist so fundamental, dass es den natürlich in Elm bereits gibt: List. Darum wird es im nächsten Kapitel gehen.