Wir haben in einem früheren Kapitel bereits gelernt, wie man in Elm Listenliterale nutzen kann, um Listen fester Länge zu definieren. In diesem Kapitel werden wir lernen, wie man ganz allgemein Listen konstruieren kann. Es handelt sich dabei wieder um einen Vorgriff. Das heißt, wir lernen an dieser Stelle, wie Listen konstruiert werden, ohne dass wir genau verstehen, was sich dahinter verbirgt. In einem späteren Kapitel werden wir diskutieren, wie der Datentyp der Listen definiert ist. An dieser Stelle benötigen wie nur die Fähigkeit, eine Liste um weitere Elemente zu erweitern.

Der Infixoperator :: (Cons) hängt vorne an eine Liste ein zusätzliches Element an. Das heißt, der Ausdruck 1 :: [ 2, 3 ] liefert die Liste [ 1, 2, 3 ]. Der Operator :: ist rechtsassoziativ. Das heißt, der Ausdruck 1 :: 2 :: [] steht für den Ausdruck 1 :: (2 :: []). Wenn der Operator :: linksassoziativ wäre, würde der Ausdruck 1 :: 2 :: [] für den Ausdruck (1 :: 2) :: [] stehen. Dieser Ausdruck ist allerdings typfalsch. In dem Teilausdruck 1 :: 2 sind beide Argumente von :: eine Zahl. Das zweite Argument von :: muss aber eine Liste sein.

Info

In Haskell wird statt des doppelten Doppelpunktes :: der einfache Doppelpunkt : für die Konstruktion einer Liste verwendet.

Während der Operator :: ein Element an eine bestehende Liste anhängt, hängt der Infixoperator ++ (Append) eine Liste an eine bestehende Liste an. Das heißt, der Ausdruck [ 1, 2 ] ++ [ 3, 4 ] liefert die Liste [ 1, 2, 3, 4 ]. Der Operator ++ ist ebenfalls rechtsassoziativ. Das heißt, der Ausdruck [ 1, 2 ] ++ [ 3 ] ++ [ 4 ] steht für den Ausdruck [ 1, 2 ] ++ ([ 3 ] ++ [ 4 ]).

Wichtig

Datenstrukturen werden in einer rein funktionalen Sprache nicht verändert.

Das heißt, die Operatoren :: und ++ liefern neue Listen und verändern nicht die bestehende Liste.

Im Kapitel Listenliterale haben wir gelernt, dass es sich bei den Listenliteralen um syntaktischen Zucker handelt. An dieser Stelle können wir uns nun anschauen, für welche Syntax der syntaktische Zucker eine Kurzform ist. Ein Ausdruck der Form [ 1, 2, 3 ] wird in einen Ausdruck der Form 1 :: 2 :: 3 :: [] übersetzt.

Die Laufzeit des Cons-Operators ist in \(\mathcal{O}(1)\). Die Laufzeit des Append-Operators ist dagegen in \(\mathcal{O}(n)\), wobei \(n\) die Länge der Liste im ersten Argument ist. Wenn wir uns mit der Implementierung des Listendatentypen beschäftigen werden wir lernen, wie diese Laufzeiten zustande kommen.

Nachdem wir die Laufzeiten von :: und ++ kennen, wollen wir uns noch einmal die Assoziativität von ++ anschauen. Wenn ++ linksassoziativ wäre, würde der Ausdruck [ 1, 2 ] ++ [ 3 ] ++ [ 4 ] für den Ausdruck ([ 1, 2 ] ++ [ 3 ]) ++ [ 4 ] stehen. Im Gegensatz zum Beispiel bei :: wäre dieser Ausdruck auch typrichtig. Dieser Ausdruck hat aber einen anderen Nachteil. Die rechtsassoziative Variante [ 1, 2 ] ++ ([ 3 ] ++ [ 4 ]) wertet zuerst den Ausdruck [ 3 ] ++ [ 4 ] aus. Da die Laufzeit der Funktion ++ linear in der Länge des ersten Argumentes ist, führt diese Auswertung also einen abstrakten Schritt durch. Anschließend wird der Ausdruck [ 1, 2 ] ++ [ 3, 4 ] ausgewertet, was zwei abstrakte Schritte benötigt. Es werden in der rechtsassoziativen Variante also insgesamt drei abstrakte Schritte durchgeführt. Die linksassoziative Variante ([ 1, 2 ] ++ [ 3 ]) ++ [ 4 ] wertet zuerst den Ausdruck [ 1, 2 ] ++ [ 3 ] aus. Da die Laufzeit der Funktion ++ linear in der Länge des ersten Argumentes ist, führt diese Auswertung also zwei abstrakte Schritte durch. Anschließend wird der Ausdruck [ 1, 2, 3 ] ++ [ 4 ] ausgewertet, was drei abstrakte Schritte benötigt. Es werden in der linksassoziativen Variante also insgesamt fünf abstrakte Schritte durchgeführt. Das heißt, die Auswertung der linksassoziativen Variante ist aufwendiger als die Auswertung der rechtsassoziativen Variante.