Teil 6.1: Seq

Die in Scala wohl am meisten benutzte Collection ist Seq bzw. die Implementierung List. Da List deutlich mehr Operationen als Seq unterstützt, wird meistens direkt mit List gearbeitet anstatt den Obertyp zu verwenden. Erstellt werden sie ganz einfach über ihren Typnamen:

scala> val xs = Seq[Int](1,2,3)
xs: Seq[Int] = List(1, 2, 3)

scala> val ys = List[Int](1,2,3)
ys: List[Int] = List(1, 2, 3)

Wie man anhand des REPL-Outputs erkennen kann erstellt sowohl Seq als auch List eine List (rechte Seite der Zuweisung). Dies wird auch der Runtime-Typ genannt. Dem Compiler ist dieser Typ nicht bekannt, er kann lediglich mit dem statischen Type arbeiten (linke Seite der Zuweisung). Innerhalb der REPL können wir sowohl den Runtime als auch den statischen Typ sehen, sobald wir unseren Code aber mit scalac übersetzen wissen weder wir noch der Compiler mit was für genauen Runtime-Typen gearbeitet wird.

In den eckigen Klammern steht der generische Typ eines Objekts, in diesem Fall Int. Durch die Typinferenz ist es aber unnötig ihn explizit bei der Objektkonstruktion mit anzugeben:

scala> val xs = Seq(1,2,3)
xs: Seq[Int] = List(1, 2, 3)

Gehen wir nun auf ein paar der wichtigsten Methoden ein. Zuallererst die Methode zur Größenermittlung einer Collection:

scala> xs.size
res57: Int = 3

Elemente hinzufügen:

scala> xs :+ 4
res63: Seq[Int] = List(1, 2, 3, 4)

scala> xs ++ Seq(4, 5, 6)
res64: Seq[Int] = List(1, 2, 3, 4, 5, 6)

Die `:+`-Methode fügt ein einzelnen Element am Ende hinzu, wohingegen `++` mehrere Elemente hinzufügen kann. Bitte beachtet, dass die Grundliste `xs` nie geändert wird – es wird immer eine neue Liste erstellt. Dass die Listen unveränderlich sind können wir zwar nicht ändern (außer auf die veränderlichen Collections zurückzugreifen), wir können aber die Variable ändern:

scala> var xs = Seq(1, 2, 3)
xs: Seq[Int] = List(1, 2, 3)

scala> xs = xs :+ 4
xs: Seq[Int] = List(1, 2, 3, 4)

scala> xs = xs ++ Seq(5, 6, 7)
xs: Seq[Int] = List(1, 2, 3, 4, 5, 6, 7)

Die Methoden um den Inhalt auf den die Variablen zeigen zu ersetzen heißen genau gleich wie ihre unveränderlichen Pendants. Der einzige Unterschied ist, dass die neu zurückgegebene Collection nun an die Variable gebunden werden kann. Wie bereits aus Java bekannt gibt es die Möglichkeit die Zuweisungen abzukürzen indem man sie einfach vor das Gleichheitszeichen schreibt:

scala> var xs = Seq(1,2,3)
xs: Seq[Int] = List(1, 2, 3)

scala> xs :+= 4

scala> xs
res103: Seq[Int] = List(1, 2, 3, 4)

scala> xs ++= Seq(5, 6, 7)

scala> xs
res105: Seq[Int] = List(1, 2, 3, 4, 5, 6, 7)

Dies ist bei allen Operation möglich, die Variableninhalte verändert. Vielleicht schaut ihr nebenbei die Dokumentation der Methoden, die Variableninhalte verändern können, in der API an, wenn nicht solltet ihr dies jetzt nachholen. Fällt euch was auf? Genau, sie existieren dort überhaupt nicht. Wie kann das sein? Die Methoden wurden keineswegs von dem Dokumentationswerkzeug scaladoc übergangen, es gibt nur eine spezielle Regel, die es überflüssig macht diese Methode tatsächlich zu implementieren: Immer dann wenn das letzte Zeichen einer Methode ein Gleichheitszeichen ist, dann prüft der Compiler als erstes ob diese Methode existiert. Falls dies nicht der Fall ist, dann transformiert er die Methode von

<collection> <op>= <obj>

in

<collection> = <collection> <op> <obj>

Sollte diese Methode ebenfalls nicht existieren, dann gibt der Compiler eine Fehlermeldung aus, ansonsten wird die Methode ausgeführt. Noch ein kleines Beispiel um die Transformation zu verdeutlichen. Wir wollen

xs ++= Seq(5, 6, 7)

ausführen. Die Methode `++=` existiert laut API aber nicht, also transformiert der Compiler das Statement zu

xs = xs ++ Seq(5, 6, 7)

Die Methode `++` kann der Compiler finden, weshalb der Code kompiliert. Sollte `xs` nicht mit `var` sondern mit `val` definiert worden sein, dann würde der Compiler eine Fehlermeldung ausgeben, da er zwar die richtige Methode gefunden hat, die Zuweisung aber nicht ausführen kann:

scala> val xs = Seq(1, 2, 3)
xs: Seq[Int] = List(1, 2, 3)

scala> xs ++= Seq(5, 6, 7)
:10: error: reassignment to val
              xs ++= Seq(5, 6, 7)
                 ^

Neben den Methoden, mit denen man Elemente an eine Collection hinten dran hängen kann, gibt es auch Methoden, mit denen man Objekte an den Anfang der Collections ergänzen kann. Laut API wird die Methode `+:` genannt, sie ist vom Namen her gespiegelt zur Methode `:+`, die ein Objekt an das Ende einer Collection schreibt. Nur irgendwie seltsam, dass wenn wir diese Methode eingeben wir eine Fehlermeldung erhalten:

scala> xs +: 4
:10: error: value +: is not a member of Int
              xs +: 4
                 ^

Was funktioniert da jetzt schon wieder nicht? Wir sind hier wieder auf eines der „geheimen“ Features von Scala gestoßen, die auf den ersten Blick total verwirren. Für das Verhalten gibt es wieder eine Regel: Endet eine Methode mit einem Doppelpunkt, so wird der Parameter mit dem Objekt, auf das die Methode aufgerufen wurde vertauscht. Diese Methoden werden rechts-assoziativ genannt, da sie auf das ihnen rechts stehende Objekt angewendet werden. Der aufgerufene Code

<obj> <op>: <param>

wird zu

<param> <op>: <obj>

Am Beispiel von `+:` bedeutet dies, dass der Aufruf von

xs +: 4

zu

4 +: xs

transformiert wird. Deshalb erhalten wir auch eine Fehlermeldung, da der Typ Int keine Methdode namens `+:` besitzt. Damit der Code erfolgreich kompiliert müssen wir die Codeteile „umdrehen“:

scala> 4 +: xs
res14: Seq[Int] = List(4, 1, 2, 3)

Ein Element an den Beginn einer Collection mag für euch vielleicht noch nicht viel Sinn machen, es gibt aber genug Anwendungsfälle, bei denen man dieses Verhalten gut gebrauchen kann. Wo das genau der Fall ist werde ich bald erklären.

Der Zugriff auf die Elemente einer Seq ist wie vieles andere ebenfalls besonders einfach:

scala> xs(0)
res66: Int = 1

scala> xs(3)
java.lang.IndexOutOfBoundsException: 3

Der Index eines Elements wird einfach in Klammern hinter die Collection gesetzt – das wars. Der erste Index aller Typen von Seq ist dabei immer 0. Falls der Index größer gleich als `seq.size` oder negativ ist fliegt eine Exception.

In Scala sind Methoden mit Operatornamen innerhalb der Collections bevorzugt. Methoden wie `add`, `addAll` oder `get` gibt es daher nicht (zumindest nicht bei Seq). Weitere Operationen:

scala> xs.contains(1)
res72: Boolean = true

scala> xs contains 1
res73: Boolean = true

Bitte ruft euch in Erinnerung, dass auch Methoden ohne Operatornamen in `operator notation` aufgerufen werden können. Besonders wichtig sind auch die Methoden um bestimmte Elementgruppen einer Collection zurückzugeben:

scala> xs.head
res74: Int = 1

scala> xs.tail
res75: Seq[Int] = List(2, 3)

scala> xs.last
res76: Int = 3

scala> xs.init
res77: Seq[Int] = List(1, 2)

`head` gibt den Kopf (das erste Element zurück), `tail` gibt alle Elemente bis auf das Erste zurück, `last` gibt das letzte Element zurück und `init` gibt alle Elemente bis auf das Letzte zurück.

Es gibt noch viele weitere nützliche Methoden, ich möchte diese hier aber nicht zu ausführlich auflisten. Gehen wir lieber weiter zu den anderen Collectiontypen und deren unterschiedliche Handhabung.

List

Wie ich euch bereits am Anfang des Artikel erklärt habe besitzt List viele Methoden, die Seq nicht zur Verfügung stehen. Damit wir auf diese Methoden zugreifen können reicht es nicht nur mit dem Runtime-Typ List zu arbeiten, wir müssen ihn auch bei unserem statischen Typ benutzen. Durch Scalas Typinferenz ist das aber überhaupt kein Problem, da wir so selten die genauen Typen spezifizieren müssen. Wir sollten nur aufpassen, dass die Schnittstellen unserer Objekte keine List sondern eine Seq zurückgeben – wir wollen ja gegen die Schnittstelle programmieren und nicht gegen die Implementierungen. Im Folgenden möchte ich euch die Unterschiede zu Seq aufzeigen.

Eine List zu erstellen ist denkbar einfach, es genügt

scala> val xs = List(1, 2, 3)
xs: List[Int] = List(1, 2, 3)

zu schreiben. Diese Schreibweise kennt ihr bereits. Was ihr noch nicht kennt ist das Folgende:

scala> val xs = 1 :: 2 :: 3 :: Nil
xs: List[Int] = List(1, 2, 3)

Die `::`-Methode konkateniert die Elemente mit einer Liste. Der Typ `Nil` ist ebenfalls eine List, genau genommen ist es ein Singleton-Objekt, das von List erbt und eine leere Liste repräsentiert. Wir könnten anstatt Nil auch `List()` schreiben, dies würde auch eine leere List erzeugen. Nil ist aber weniger zu schreiben und dabei genauso verständlich. Dadurch, dass `::` auf einen Doppelpunkt endet wird die Aufrufereihenfolge umgedreht, der Compiler würde also folgenden Code erkennen:

scala> val xs = Nil.::(3).::(2).::(1)
xs: List[Int] = List(1, 2, 3)

Dies wäre aber lange nicht so gut lesbar wie die erstgenannte Variante. Der Code funktioniert übrigens, da die rechts-assoziative Methode links-assoziativ geparst wird. Das bedeutet, man könnte den Code auch

scala> val xs = (1 :: (2 :: (3 :: Nil)))
xs: List[Int] = List(1, 2, 3)

schreiben. Er wird von rechts nach links aufgelöst, deshalb links-assoziativ. Würden wir nur `1 :: 2` schreiben würden wir eine Fehlermeldung erhalten, da Int keine Methode `::` kennt. Durch die links-Assoziativität hingegen wird nach Auflösung jeder Klammer immer eine List zurückgegeben, auf die `::` angewendet werden kann:

scala> 3 :: Nil
res15: List[Int] = List(3)

scala> 2 :: res15
res16: List[Int] = List(2, 3)

scala> 1 :: res16
res17: List[Int] = List(1, 2, 3)

Das ist die gesamte „Magie“ hinter `::`. Die Methode birgt jetzt schon den ersten Anwendungsfall bei dem es Sinn macht Objekte an den Beginn einer List zu hängen und nicht zum Ende.

List besitzt noch die Methode `:::` die gleich wie `++` funktioniert, die Elemente aber wie `::` an den Anfang der List schreibt:


scala> xs ::: List(4, 5, 6)
res22: List[Int] = List(1, 2, 3, 4, 5, 6)

scala> xs ++ List(4, 5, 6)
res23: List[Int] = List(1, 2, 3, 4, 5, 6)

Die Ausgabe ist zwar identisch, die Auswertungsreihenfolge ist aber eine andere, da `:::` rechts-assoziativ ist (endet mit einem Doppelpunkt). Wir können uns vergewissern, dass dies so ist wenn wir die Methode in `object notation` aufrufen:

scala> xs.:::(List(4, 5, 6))
res25: List[Int] = List(4, 5, 6, 1, 2, 3)

scala> xs.++(List(4, 5, 6))
res26: List[Int] = List(1, 2, 3, 4, 5, 6)

Sobald wir dies tun gilt die Regel mit der rechts-Assoziativität nicht mehr und man kann deutlich erkennen wie die Elemente zum Beginn hinzugefügt werden. Wenn wir mit List arbeiten ist das Voranstellen von Elementen die bevorzugte Variante, da das Anhängen von Elementen mehr Zeit in Anspruch nimmt. Die Implementierung von List entspricht einer einseitig verlinkten Liste, die Variable, die die List aufnimmt zeigt dabei immer auf den Kopf der Liste. Anhängen von Elementen würde also bedeuten, dass die komplette Liste erst durchlaufen werden muss bevor am Ende ein Element hinzugefügt werden kann. Dies entspricht einer Laufzeit von O(n) wobei n gleich der Anzahl der Elemente. Wenn wir Elemente voranstellen haben wir eine Laufzeit von O(1), da das neue Element direkt zum neuen Kopf der List wird (xs.head) und auf den Rest (xs.tail) zeigt. Wollen wir Elemente von einer bestimmten Position lesen müssen wir die Liste wieder umständlich durchlaufen, List eignet sich also besonders wenn wir sie komplett durchlaufen wollen. Bei einem indexbasierten Zugriff sollten wir also zu einer IndexedSeq greifen.

IndexedSeq

Die beiden wichtigsten Vertreter der indexbasierten Collections sind Array und Vector. Im Gegensatz zu List sind dies keine verketteten Listen sondern speichern die Daten indexbasiert ab. Dies bedeutet, dass wir an jedes Element mit einer Laufzeit von O(1) gelangen können. Der Unterschied zwischen Array und Vector ist, dass sich die Elemente eines Vectors nicht ändern können, die eines Arrays hingegen schon. Bei beiden gilt aber weiterhin, dass sich die Anzahl der Elemente nach der Konstruktion nicht mehr ändern lassen. Die Standardimplementierung von IndexedSeq ist Vector weshalb wir ihn nie direkt über die Konstruktoren von Vector erzeugen brauchen:

scala> val xs = IndexedSeq(1, 2, 3)
xs: IndexedSeq[Int] = Vector(1, 2, 3)

scala> xs(0) = 4
:10: error: value update is not a member of IndexedSeq[Int]
              xs(0) = 4
              ^

scala> val xs = Array(1, 2, 3)
xs: Array[Int] = Array(1, 2, 3)

scala> xs(0) = 4

scala> xs
res43: Array[Int] = Array(4, 2, 3)

Vector basiert intern auf einem Array und sorgt dafür, dass sich dessen Elemente nicht ändern lassen. Je nach Anforderung sollte also die eine oder die andere Collection genommen werden. Array zählt eigentlich zu den veränderlichen Collections, die ich nochmal getrennt besprechen möchte. Da das Array aber direkt von der JVM unterstützt wird ist es die schnellste und speichersparendste Collection weshalb ich sie hier auch erwähne.

Zu beachten ist, dass selbst ein Array mit runden Klammern adressiert wird. Die Schreibweise mit den eckigen Klammern funktioniert nicht.

String

Strings gehören in Scala ebenfalls zu den Collections. Wir können auf sie genau die gleichen Methoden aufrufen wie auch bei den anderen Collections:

scala> val str = "8735421960"
str: java.lang.String = 8735421960

scala> str.size
res46: Int = 10

scala> str(0)
res47: Char = 8

scala> str.sorted
res48: String = 0123456789

Ein String ist dabei gleichzusetzen mit einer Seq[Char]:

scala> val str: Seq[Char] = "8735421960"
str: Seq[Char] = 8735421960

String basiert dabei auf der String-Repräsentation der JVM, ist gleichzeitig aber auch eine Collection. Dies ermöglicht uns eine elegante Stringverarbeitung, ohne dass wir wie in Java auf irgendwelche Helper-Klassen zugreifen müssten. Wie genau die Brücke zwischen JVM-String und Scala-Collection geschlagen wird werdet ihr noch früh genug erfahren. Dass implizite Konvertierungen dabei eine Rolle spielen solltet ihr schon wissen wenn ihr die anderen Artikel aufmerksam gelesen habt. Welche Methoden von String genau unterstützt werden erfahrt ihr wenn ihr in die Dokumentation von WrappedString schaut.

Range

Eine besonders tolle Collection ist die Range. Sie ermöglichen uns in Verbindung mit der for-Expression elegante Iterationen über Collections. Schauen wir uns einmal die eleganteste Schreibweise zur Erstellung einer Range an:

scala> 1 to 5
res49: scala.collection.immutable.Range.Inclusive = Range(1, 2, 3, 4, 5)

Einfach. Praktisch. Gut. Mehr gibt es dazu eigentlich nicht zu sagen. `to` ist im übrigen kein Schlüsselwort, sondern eine Methode:

scala> 1.to(5)
res50: scala.collection.immutable.Range.Inclusive = Range(1, 2, 3, 4, 5)

Sie erstellt eine Range, die vom Startwert (1) bis zum Endwert (5) geht. Neben `to` gibt es auch noch `until`, bei dem der letzte Wert nicht inklusive, also ausgelassen wird:

scala> 1 until 5
res51: scala.collection.immutable.Range = Range(1, 2, 3, 4)

Mit der Methode `by` lässt sich die Schrittweite der Range festlegen:

scala> 1 to 10 by 2
res52: scala.collection.immutable.Range = Range(1, 3, 5, 7, 9)

scala> 10 to 1 by -2
res53: scala.collection.immutable.Range = Range(10, 8, 6, 4, 2)

Dies erlaubt uns sowohl vorwärts als auch rückwärts zu gehen. Als Übersichtlichkeitsgründen werde ich mich in einem gesondertem Kapitel darauf konzentrieren wie die for-Expressions mit den Ranges zusammenarbeiten.

Iterator

Wir haben jetzt viele Möglichkeiten kennen gelernt wie wir Collections erstellen können, aber die Collection bringt uns nichts wenn wir nicht mit Schleifen auf ihre Elemente zugreifen können. Die naheliegendste Lösung wäre eine while-Schleife zu benutzen:

def printList(xs: List[Int]) {
  var i = 0
  while (i < xs.size) {
    println(xs(i))
    i += 1
  }
}

scala> val xs = List(1, 2, 3)
xs: List[Int] = List(1, 2, 3)

scala> printList(xs)
1
2
3

Nur leider ist das nicht besonders elegant. Der Iterator, bietet eine weitere Möglichkeit über die Elemente zu iterieren.

def printList(xs: List[Int]) {
  val i = xs.iterator
  while(i.hasNext)
    println(i.next)
}

scala> printList(xs)
1
2
3

Über die Methode `iterator` bekommen wir von jeder Collection einen Iterator. Die Methoden `hasNext` und `next` sprechen für sich.

Die Methode `mkString` macht es übrigens besonders einfach eine Collection in einen String umzuwandeln:

scala> println(xs.mkString("\n"))
1
2
3

scala> println(xs.mkString("[", ", ", "]"))
[1, 2, 3]

Wofür die Parameter genau stehen verrät die API oder die REPL mit ihren auto-completion Fähigkeiten.

Bitte beachtet, dass ein Iterator nur ein mal durchlaufen werden kann. Ist der Iterator am Ende angekommen gibt es keine Möglichkeit mehr ihn zu „resetten“. Stattdessen muss ein neuer Iterator erstellt werden. Der Iterator gehört zu den `lazy collections` da er die Elemente erst dann berechnet bzw. auf sie zugreift wenn sie gebraucht werden. In die gleiche Kategorie fallen View und Stream, wobei sich die drei grundlegend voneinander unterscheiden. Ein Iterator kennt immer nur ein Element, nämlich das über das er gerade iteriert – er ist also mehr ein Pointer auf ein Element als ein eigene Collection.

View

Eine View unterscheidet sich vom Iterator hauptsächlich darin, dass sie eben schon eine eigene Collection darstellt. Im Gegensatz zum Iterator, den nur einmal aufgerufen werden kann, darf man eine View beliebig oft aufrufen. Die Elemente werden dabei bei jedem Zugriff neu berechnet, sie werden also nicht gespeichert. Sowohl View als auch Iterator benötigen also also immer nur Speicherplatz für ein Element. Views kann man mit der Methode `view` erstellen:

scala> xs.view
res60: java.lang.Object with scala.collection.SeqView[Int,List[Int]] = SeqView(...)

Hier noch ein kleines Beispiel, das den Unterschied zwischen View und Iterator erläutert:

scala> val xs = List(1, 2, 3)
xs: List[Int] = List(1, 2, 3)

scala> val i = xs.iterator
i: Iterator[Int] = non-empty iterator

scala> i.drop(2).next
res70: Int = 3

scala> i.drop(2).next
java.util.NoSuchElementException: next on empty iterator

scala> val v = xs.view
v: java.lang.Object with scala.collection.SeqView[Int,List[Int]] = SeqView(...)

scala> v.drop(2).head
res72: Int = 3

scala> v.drop(2).head
res73: Int = 3

Wie ganz klar zu erkennen wirft der Iterator eine Exception wenn man versucht auf ein Element zuzugreifen, das nicht existiert. `drop` versucht die ersten n Elemente zu löschen und da die Liste nur drei Elemente besitzt können wir keine zwei mal zwei Elemente löschen und dann auf ein nachfolgendes Element zugreifen. Da die View hingegen immer wieder eine neue Collection erzeugt können wir den Löschvorgang beliebig oft wiederholen ohne einen Fehler zu bekommen.

Stream

Die letzte Kategorie der `lazy collections` bildet der Stream. Er erzeugt seine Elemente ebenfalls erst auf Anfrage speichert bereits berechnete Elemente aber ab um im Bedarfsfall schnell wieder darauf zugreifen zu können. Der größte Vorteil von Streams ist unendlich lange Collections zu erzeugen, gegebenfalls auch rekursiv.

scala> val s = Stream from 1
s: scala.collection.immutable.Stream[Int] = Stream(1, ?)

scala> s(0)
res80: Int = 1

scala> s(1)
res81: Int = 2

scala> s(1000)
res82: Int = 1001

scala> val s = Stream.from(1, 3)
s: scala.collection.immutable.Stream[Int] = Stream(1, ?)

scala> s(0)
res87: Int = 1

scala> s(1)
res88: Int = 4

scala> s(10)
res89: Int = 31

Streams können schwer zu verstehende Gebilde sein, vor allem wenn sie rekursiv erzeugt werden. Wenn die Zeit reif ist werden wir uns das mal genauer anschauen.

Um von einer `lazy collection` (View, Stream) wieder zurück zu einer `strict collection` (die Collections, die ihre Elemente alle auf einmal berechnen) zu kommen reicht es die Methode `force` aufzurufen:

scala> val xs = List(1, 2, 3)
xs: List[Int] = List(1, 2, 3)

scala> val v = xs.view
v: java.lang.Object with scala.collection.SeqView[Int,List[Int]] = SeqView(...)

scala> v.force
res93: List[Int] = List(1, 2, 3)

`force` sollte nicht auf einen unendlichen Stream aufgerufen werden, da sonst immer neue Elemente bis zum Absturz eures Programms berechnet werden.

Advertisements

No comments yet

Kommentar verfassen

Trage deine Daten unten ein oder klicke ein Icon um dich einzuloggen:

WordPress.com-Logo

Du kommentierst mit Deinem WordPress.com-Konto. Abmelden / Ändern )

Twitter-Bild

Du kommentierst mit Deinem Twitter-Konto. Abmelden / Ändern )

Facebook-Foto

Du kommentierst mit Deinem Facebook-Konto. Abmelden / Ändern )

Google+ Foto

Du kommentierst mit Deinem Google+-Konto. Abmelden / Ändern )

Verbinde mit %s

%d Bloggern gefällt das: