Teil 16.1: Funktionen in der Praxis

Im letzten Kapitel sollte euch klar geworden sein wie ihr Funktionen einsetzen könnt, aber wahrscheinlich noch nicht wozu genau. Wir wollen Abstraktion und diese bekommen wir wenn wir Funktionen Aufgaben übernehmen lassen, die wir sonst selbst erledigen müssten. In den Beispielen aus dem vorherigen Kapitel hab ich versucht das schon ein wenig zu verdeutlichen. Jedoch blieb das alles nur im kleinen Rahmen und die gewonnene Abstraktion war nicht genug um den dadurch erzeugten Overhead auszugleichen. Dies wollen wir nun ändern.

Ich möchte mit euch eine generische Liste schreiben, so wie wir es bereits in vorherigen Kapiteln getan haben. Dieses mal möchte ich aber deutlich weiter gehen und nicht nur erklären wie man solch eine Liste erstellt, sondern auch wie man vernünftig mit ihr arbeitet. Zu Beginn gleich nochmal die Listendefinition:

import scala.{ UnsupportedOperationException => UOE }

object LinkedList {
  def unapplySeq[A](a: LinkedList[A]): Option[Seq[A]] = {
    var xs: List[A] = Nil
    var ys = a
    while (!ys.isEmpty) {
      xs = ys.head :: xs
      ys = ys.tail
    }
    Some(xs.reverse)
  }
}

abstract class LinkedList[+A] {
  def head: A
  def tail: LinkedList[A]
  def isEmpty: Boolean
  
  def +: [B >: A](b: B): LinkedList[B] =
    new +:(b, this)
}

final case class +: [A](head: A, tail: LinkedList[A]) extends LinkedList[A] {
  def isEmpty = false
}

final case object LNil extends LinkedList[Nothing] {
  def head = throw new UOE("nil head")
  def tail = throw new UOE("nil tail")
  def isEmpty = true
}

Der gezeigte Code sollte keine große Schwierigkeiten mehr machen. Falls doch lohnt es sich zuvor noch schnell in einem der früheren Kapitel nachzuschlagen – ich werde hierzu nichts weiter erklären. Viel können wir mit dem Code noch nicht machen, so ist es nur möglich Listen zu erstellen und wieder zu extrahieren:

val xs = 1 +: 2 +: 3 +: LNil
val ys = "a" +: "b" +: "c" +: LNil

xs match {
  case 1 +: 2 +: 3 +: LNil => true
  case _ => false
}

Im Weiteren werden wir die Liste mit Methoden ergänzen, wie sie auch in der Standardbibliothek von Scala vorkommen. Unsere Implementierungen werden dabei ein identisches Resultat wie die bereits definierten erzeugen. Es kann also hilfreich sein während dieses Kapitels immer mal wieder einen Blick in die List-API zu werfen.

Fangen wir damit an, dass wir unsere Liste um eine Methode ergänzen, mit der wir sie auf der Konsole ausgeben können:

// in class LinkedList
def mkString: String = mkString("LinkedList(", ", ", ")")

def mkString(start: String, sep: String, end: String): String =
  if (this.isEmpty) ""
  else {
    val sb = StringBuilder.newBuilder
    sb append start
    sb append head

    var cur = tail
    while (!cur.isEmpty) {
      sb append sep
      sb append cur.head
      cur = cur.tail
    }

    sb append end
    sb.toString
  }

In der Anwendung:

scala> val xs = 1 +: 2 +: 3 +: LNil
xs: LinkedList[Int] = +:(1,+:(2,+:(3,LNil)))

scala> xs.mkString
res1: String = LinkedList(1, 2, 3)

scala> xs.mkString("[", "-", "]")
res4: String = [1-2-3]

scala> LNil.mkString
res5: String = ""

Die mkString-Methode erlaubt uns die Elemente der Liste in beliebiger Form auszugeben. Diese Methode bietet schon ein wenig Abstraktion, da wir nur noch angeben müssen, wie die Liste ausgegeben werden soll, aber nicht wie ihre String-Rerpäsentation konstruiert werden soll. Funktionen haben wir hier aber noch gar nicht eingesetzt. Das kommt aber schon noch. Zunächst wollen wir die toString-Methode noch überschreiben:

// in class +:
override def toString = mkString

scala> val xs = 1 +: 2 +: 3 +: LNil
xs: LinkedList[Int] = LinkedList(1, 2, 3)

scala> LNil
res6: LNil.type = LNil

Da Standard-Implementierung von toString in LNil gefällt uns, weshalb wir daran nichts ändern. Ganz nützlich sind Methoden um unsere Liste umzudrehen und ihre Größe auszugeben:

// in class LinkedList
def size: Int = {
  def loop(xs: LinkedList[A], i: Int): Int =
    if (xs.isEmpty) i else loop(xs.tail, i+1)
  loop(this, 0)
}

def reverse: LinkedList[A] = {
  def loop(xs: LinkedList[A], ys: LinkedList[A]): LinkedList[A] =
    if (xs.isEmpty) ys else loop(xs.tail, xs.head +: ys)
  loop(this, LNil)
}

Noch eine kleine Prüfung ob beide Methoden korrekt funktionieren:

scala> xs.reverse
res7: LinkedList[Int] = LinkedList(3, 2, 1)

scala> xs.size
res8: Int = 3

Mit Hilfe der eben implementierten Methoden können wir nun auch die apply-Methoden erstellen:

// in class LinkedList
def apply(index: Int): A =
  if (this.isEmpty || index < 0 || index >= this.size)
    throw new IndexOutOfBoundsException(index.toString)
  else {
    def loop(i: Int, xs: LinkedList[A]): A =
      if (i == 0) xs.head else loop(i-1, xs.tail)
    loop(index, this)
  }
// in object LinkedList
def apply[A](a: A*): LinkedList[A] = {
  def loop(xs: Seq[A], ys: LinkedList[A]): LinkedList[A] =
    if (xs.isEmpty) ys else loop(xs.tail, xs.head +: ys)
  loop(a, LNil).reverse
}

Damit können wir index-basiert auf die Elemente unserer Liste zugreifen und eine Liste ohne das +:-Objekt erstellen:

scala> xs(2)
res9: Int = 3

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

scala> LinkedList(1, 2, 3)
res0: LinkedList[Int] = LinkedList(1, 2, 3)

Zwei weitere nützliche Methoden sind sind ++ und ++: mit denen wir eine andere Liste vor bzw. nach eine unserer Listen hängen können:

// in class LinkedList
def ++: [B >: A](xs: LinkedList[B]): LinkedList[B] =
  if (this.isEmpty) xs
  else if (xs.isEmpty) this
  else {
    def loop(xs: LinkedList[B], ys: LinkedList[B]): LinkedList[B] =
      if (xs.isEmpty) ys else loop(xs.tail, xs.head +: ys)
    loop(xs.reverse, this)
  }

def ++ [B >: A](xs: LinkedList[B]): LinkedList[B] =
  if (this.isEmpty) xs
  else this ++: xs

Beachtet, dass die beiden Methoden unterschiedlich funktionieren, was auf den ersten Blick wegen der gleichen Ausgaben nicht zu erkennen ist:

scala> val ys = 4 +: 5 +: 6 +: LNil
ys: LinkedList[Int] = LinkedList(4, 5, 6)

scala> xs ++ ys
res11: LinkedList[Int] = LinkedList(1, 2, 3, 4, 5, 6)

scala> xs ++: ys
res12: LinkedList[Int] = LinkedList(1, 2, 3, 4, 5, 6)

Die bisher vorgestellten Methoden habt ihr bereits alle kennen gelernt. Gehen wir nun endlich zu dem Teil über, der für uns richtig interessant wird: Funktionen höherer Ordnung.

Funktionen höherer Ordnung

Als Funktionen höherer Ordnung werden Funktionen bezeichnet, die ihrerseits Funktionen als Argumente erwarten bzw. zurückgeben. Sie sind der ausschlaggebende Grund, warum man mit Funktionen einen hohe Abstraktion erreichen kann oder zumindest eine Abstraktion, die höher ist als die bei gewöhnlichen imperativen Programmiersprachen.

foreach

Die erste Funktion höherer Ordnung, die ihr kennen lernen sollt, heißt foreach. Ihre Aufgabe ist es über die Elemente unserer Liste zu iterieren und eine vorgegeben Funktion für jedes Element auszuführen. Schauen wir uns zuallererst ihre Signatur an:

def foreach(f: A => Unit)

Wir übergeben eine Funktion, die ein A als Eingabe nimmt und Unit als Ausgabe produzieren soll. Unit heißt, dass uns der Wert nicht weiter interessiert. Wir können also auch sagen, dass die Funktion keinen Rückgabewert besitzen soll. A ist der Typparameter unserer Liste, was bedeutet, dass alle Elemente der List vom Typ A sind. foreach kann mit dieser Signatur also jedes Element aus unserer Liste als Eingabe erhalten und muss Unit als Ausgabe produzieren. Aber was könnte foreach mit den Elementen anstellen? Die einfachste Möglichkeit wäre wohl sie einfach auf der Konsole auszugeben:

scala> xs.foreach((x: Int) => println(x))
1
2
3

scala> xs.foreach(x => println(x))
1
2
3

scala> xs.foreach(println(_))
1
2
3

Wir erinnern uns: Mit Hilfe eines Funktions-Literal können wir das Verhalten einer Funktion festlegen. Scalas Syntaxzucker erlaubt uns den Code mit weniger Overhead zu notieren, was der Lesbarkeit dient. Es gibt noch weitere Vereinfachungen, diese sollen jetzt aber nicht Thema sein.

foreach sollte als erste uns nun näher bekannte Funktion höherer Ordnung die Abstraktion verdeutlichen, die man durch funktionales Programmieren erhalten kann. Wir beschreiben nicht, wie unser Code über die Liste iterieren und dessen Elemente verarbeiten soll. Statt dessen geben wir an was getan werden soll. Es soll über die Liste iteriert und jedes Element ausgegeben werden. Ganz deklarativ eben. Es wird ein wenig dauert bis ihr dieses deklarative Prinzip verinnerlicht habt. Wenn es aber so weit ist, dann werdet ihr keinen anderen Code mehr schreiben wollen. Das einzige was jetzt noch fehlt ist die genaue Implementierung von foreach, die aber nicht weiter überraschen sollte:

// in class LinkedList
def foreach(f: A => Unit) {
  var xs = this
  while (!xs.isEmpty) {
    f(xs.head)
    xs = xs.tail
  }
}

Sie funktioniert genau so wie eine Methode in einer imperativen Programmiersprache funktionieren sollte. Mit Hilfe einer Schleife wird über alle Elemente iteriert und die Funktion wird für jedes dieser Elemente aufgerufen. Hinter dem Namen „foreach“ verbirgt sich also nichts weiter als ganz normaler und bekannter imperativer Code, nur mit dem Unterschied, dass wir ihn nicht zu Gesicht bekommen.

Diese Funktion wird von jeder Collection in Scala implementiert und dank einer vorgeschriebenen Signatur ist sicher gestellt, dass sie auch immer das richtige Ergebnis liefert.

scala> Set(1, 2, 3).foreach(println(_))
1
2
3

scala> Seq(1, 2, 3).foreach(println(_))
1
2
3

scala> Map(1 -> "a", 2 -> "b", 3 -> "c").foreach(println(_))
(1,a)
(2,b)
(3,c)

Es gibt noch eine weitere Möglichkeit wie wir über die Collections iterieren können:

scala> for (x <- LinkedList(1, 2, 3)) println(x)
1
2
3

Ist das nicht toll? Die Ausgabe der for-Expression gleicht haargenau der von foreach.

map

Die zweite Funktion höherer Ordnung, die ich euch vorstellen möchte, ist map. Ihre Aufgabe ist es die Wert einer Collection zu anderen zu wandeln. Schauen wir uns zuerst ihre Signatur an:

def map[B](f: A => B): LinkedList[B]

map erwartet eine Funktion, die aus einem A ein B macht. B ist dabei ein beliebiger Typ, der von der übergebenen Funktion bestimmt wird. map führt die Funktion dann für jedes Element aus der Collection aus und kreiert mit den Resultaten eine neue Collection.

scala> val xs = LinkedList('1', '2', '3')
xs: LinkedList[Char] = LinkedList(1, 2, 3)

scala> xs.map(x => x.toInt)
res7: LinkedList[Int] = LinkedList(49, 50, 51)

scala> xs
res8: LinkedList[Char] = LinkedList(1, 2, 3)

scala> xs.map(x => x.asDigit)
res9: LinkedList[Int] = LinkedList(1, 2, 3)

scala> res9.map(_+1)
res10: LinkedList[Int] = LinkedList(2, 3, 4)

scala> res9.map(_.toString)
res11: LinkedList[java.lang.String] = LinkedList(1, 2, 3)

Auch bei diesen Beispielen können wir von Scalas Platzhaltersyntax profitieren und angenehm lesbaren und schreibbaren Code produzieren. Da alle Funktionen höherer Ordnung immer auf alle Elemente einer Collection angewandt werden ist der Typ des Resultats auch immer identisch. Dabei spielt es keine Rolle, ob der Ausgangs-Typ der gleiche wie der Eingangs-Typ ist.

Die Implementierung von map birgt ebenso wie die von foreach keine Geheimnisse:

// in class LinkedList
def map[B](f: A => B): LinkedList[B] = {
  def loop(xs: LinkedList[A], ys: LinkedList[B]): LinkedList[B] =
    if (xs.isEmpty) ys else loop(xs.tail, f(xs.head) +: ys)
  loop(this, LNil).reverse
}

Wieder haben wir eine einfache Schleife (hier als Rekursion) und wieder wird unsere Liste Stück für Stück auseinander und eine neue Liste wieder zusammen gebaut. Keine der Funktionen höherer Ordnung beherbergt ein großes Hexenwerk, es benötigt nur etwas Zeit die Funktionen als Solche zu akzeptieren und deren genaue Bedeutung zu verstehen. Anstatt jedes Mal eine neue Methode zu erstellen, die eine Collection verarbeitet, übernimmt das für uns fortan map.

Wie bei foreach können wir auch das Verhalten von map mit der for-Expression nachbilden:

scala> xs.map(_+5)
res22: LinkedList[Int] = LinkedList(6, 7, 8)

scala> for (x <- xs) yield x+5
res23: LinkedList[Int] = LinkedList(6, 7, 8)

Das sollte euch noch ein wenig helfen die Arbeitsweise von map zu verstehen.

filter

Wollen wir Elemente in einer Collection finden, die eine bestimmte Eigenschaft erfüllen, so gibt es dafür filter. Wie map produziert sie mit allen Elementen, die die Eigenschaft erfüllen, eine neue Collection. Die Signatur lautet:

def filter(f: A => Boolean): LinkedList[A]

Die Funktion soll einen passenden Wahrheitswert liefern, je nach dem ob die Eigenschaft erfüllt wird oder nicht. Beispiele auf was getestet werden kann wären z.B.:

scala> val xs = LinkedList((1 to 10): _*)
xs: LinkedList[Int] = LinkedList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)

scala> xs.filter(_%2 == 0)
res12: LinkedList[Int] = LinkedList(2, 4, 6, 8, 10)

scala> xs.filter(_ > 5)
res14: LinkedList[Int] = LinkedList(6, 7, 8, 9, 10)

scala> val xs = LinkedList("hello", "world", "how", "are", "you?")
xs: LinkedList[java.lang.String] = LinkedList(hello, world, how, are, you?)

scala> xs.filter(_ contains "e")
res15: LinkedList[java.lang.String] = LinkedList(hello, are)

scala> xs.filter(_.length > 3)
res16: LinkedList[java.lang.String] = LinkedList(hello, world, you?)

Ich hoffe ihr habt die Schreibweise mit dem Unterstrich mittlerweile einigermaßen verinnerlicht. Wenn nicht, dann versucht euch einfach vorzustellen, dass der Unterstrich das momentan getestete Element ist. Es sollte einfach zu erkennen sein, dass jede Funktion einen Wahrheitswert produziert und somit auf jedes Element angewendet werden kann. Die Implementierung von filter sollte euch nicht erstaunen, da sie fast genau so aussieht wie die von map:

// in class LinkedList
def filter(f: A => Boolean): LinkedList[A] = {
  def loop(xs: LinkedList[A], ys: LinkedList[A]): LinkedList[A] =
    if (xs.isEmpty) ys else loop(xs.tail, if (f(xs.head)) xs.head +: ys else ys)
  loop(this, LNil).reverse
}

Der einzige Unterschied liegt im Aufruf der Funktion. Eine große Stärke von Funktionen höherer Ordnung ist, dass sie sehr einfach miteinander kombiniert werden können:

scala> xs.map(_.length).filter(_ > 3)
res18: LinkedList[Int] = LinkedList(5, 5, 4)

scala> xs.filter(_.length > 3)
res19: LinkedList[java.lang.String] = LinkedList(hello, world, you?)

Das funktioniert deshalb weil jede Funktion ihrerseits eine neue Collection zurück gibt, auf die wieder eine neue Funktion angewendet werden kann. Je nach dem was man für ein Resultat erhalten will muss man sich also entscheiden wie man die Funktionen aufruft und was man mit ihnen macht.

Auch für filter gibt es wieder ein entsprechendes Konstrukt in der for-Expression:

scala> for (x <- xs if x.length > 3) yield x
<console>:39: warning: `withFilter' method does not yet exist on LinkedList[java.lang.String], using `filter' method instead
              for (x <- xs if x.length > 3) yield x
                        ^
res21: LinkedList[java.lang.String] = LinkedList(hello, world, you?)

Der genaue Grund der Warnung soll uns hier erst mal egal sein. Wichtig ist, dass ihr seht, dass das gleiche Resultat erzielt wird.

contains/find/exists

Ein paar Methoden zum Finden von Elementen sind immer ganz nützlich. Den Anfang macht die Methode contains:

// in class LinkedList
def contains[B >: A](elem: B): Boolean = {
  def loop(xs: LinkedList[A]): Boolean =
    if (xs.isEmpty) false
    else if (xs.head == elem) true
    else loop(xs.tail)
  loop(this)
}

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

scala> xs contains 3
res0: Boolean = true

scala> xs contains 8
res1: Boolean = false

„contains“ arbeitet wie wir es erwarten und ist zur Abwechslung mal keine Funktion höherer Ordnung. Das ändern wir aber gleich wieder, indem wir die Methode nur minimal anpassen:

// in class LinkedList
def find(f: A => Boolean): Option[A] = {
  def loop(xs: LinkedList[A]): Option[A] =
    if (xs.isEmpty) None
    else if (f(xs.head)) Some(xs.head)
    else loop(xs.tail)
  loop(this)
}

find prüft im Gegensazt zu contains nicht ob ein bestimmtes Element in der Collection vorhanden ist, sondern ob ein Element eine bestimmte Eigenschaft erfüllt.

scala> val xs = List(1, 3, 5, 7, 9)
xs: List[Int] = List(1, 3, 5, 7, 9)

scala> xs.find(_%2 == 0)
res6: Option[Int] = None

scala> xs.find(_%3 == 0)
res7: Option[Int] = Some(3)

Eine Frage, die es hier vielleicht noch zu klären gibt, ist, warum die Funktion ein Option zurück gibt. Wenn wir auf Option verzichten und statt dessen null zurück geben würden, dann würden wir zum einen Typsicherheit verlieren, zum anderen würden wir uns der Möglichkeit berauben objektorientiert mit dem Ergebnis weiterzuarbeiten (auf null können keine Methoden aufgerufen werden). „find“ gibt nur einen einzelnen Wert zurück. Genau genommen ist es der Erste auf den eine Bedingung zutrifft. Wollen wir lieber alle Elemente zurück, auf die eine Bedingung zutrifft, so müssen wir „filter“ einsetzen.

Die Funktion exists funktioniert äquivalent zu „find“, gibt aber einen Wahrheitswert zurück:

// in class LinkedList
def exists(f: A => Boolean): Boolean =
  find(f) != None

scala> val xs = List(1, 3, 5, 7, 9)
xs: List[Int] = List(1, 3, 5, 7, 9)

scala> xs.exists(_%2 == 0)
res8: Boolean = false

scala> xs.exists(_%3 == 0)
res9: Boolean = true

take/drop

Mit den beiden Methoden take und drop können wir festlegen, dass wir eine bestimmte Anzahl an Elementen haben bzw. löschen wollen.

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

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

scala> xs drop 2
res11: List[Int] = List(3, 4, 5)

Zu beachten ist auch hier wieder, dass die ursprüngliche List unveränderlich ist. Wir erhalten also neue Listen. Die Implementierungen dazu:

// in class LinkedList
def take(elems: Int): LinkedList[A] =
  if (elems <= 0) LNil
  else if (elems >= this.size) this
  else {
    def loop(i: Int, xs: LinkedList[A], ys: LinkedList[A]): LinkedList[A] =
      if (i == 0) ys else loop(i-1, xs.tail, xs.head +: ys)
    loop(elems, this, LNil).reverse
  }

def drop(elems: Int): LinkedList[A] = {
  def loop(elems: Int, xs: LinkedList[A]): LinkedList[A] =
    if (elems <= 0) xs else loop(elems-1, xs.tail)
  if (elems >= this.size) LNil
  else loop(elems, this)
}

fold

Wir haben jetzt schon eine Menge nützlicher Methoden kennen gelernt. Es gibt aber noch eine sehr wichtige Gruppe namens fold, deren wirklicher Nutzen sich euch wohl erst im Laufe der Zeit offenbaren dürfte. Sinn der fold-Funktionen ist es, die Elemente einer Collection zusammenzufassen. Zusammenfassen können wir tatsächlich sehr viel – viele der bisher vorgestellten Funktionen haben etwas mit zusammenfassen zu tun. Da wäre „map“ das Elemente transformiert und sie zu einer neuen Liste zusammenfasst. Das gleiche bei „filter“. Beide Funktionen sind also nur eine Form von „fold“ und können auch als „fold“ implementiert werden. Wir müssen beim zusammenfassen aber nicht zwingend eine neue Collection kreieren bzw. zu einer Collection zusammenfassen. Oft wollen wir auch nur ein einzelnen Element haben. Das wäre z.B. bei einer Funktion der Fall, die die Summe aller Elemente ermitteln oder gar das größte bzw. kleinste Element ermitteln soll.

Anhand dieser Beschreibung von „fold“ sollte ersichtlich sein, dass diese Funktion doch sehr viel können muss. Sie muss auf beliebige Typen prüfen können, zu einem beliebigen Typ zusammengefasst werden können und sie muss sich vorhergehende Elemente merken können. Der Abstraktionsgehalt dieser Funktion ist also weitaus höher als bei allen anderen bisher vorgestellten Funktionen. Und wie man es von abstrakten Dingen so gewohnt ist, ist ihre wirkliche Aufgabe auf den ersten Blick nicht zu erkennen. Ihr dürft also auch nicht erwarten die folgende Definition schon komplett verstehen zu können:

def fold[B](init: B)(f: (B, A) => B): B

So, das ist jetzt harter Tobak, der erst mal verdaut werden will. Wir haben zwei Parameterlisten. Eine, die einen unbekannten Wert B erwartet und eine, die eine anzuwendende Funktion sehen möchte, die ihrerseits selbst zwei Parameter erwartet. Aufgerufen wird das Ganze ungefähr so:

scala> val xs = LinkedList(1, 2, 3, 4, 5)
xs: LinkedList[Int] = LinkedList(1, 2, 3, 4, 5)

scala> xs.fold(0)((b, a) => b+a)
res0: Int = 15

scala> xs.fold(0)((sum, x) => sum+x)
res1: Int = 15

scala> xs.fold(0)(_+_)
res2: Int = 15

Wenn wir den Funktionsparametern vernünftige Namen gaben, dann ist es schon mal ein wenig einfacher dem Code zu folgen. Wie zu erkennen ist einer der beiden Parameter dafür zuständig den bisher zusammengefassten Wert zu speichern. Der andere Parameter ist das aktuelle Element, das verarbeitet werden soll. Was wir hier machen ist nichts anderes als die Int-Elemente einer Liste aufzuaddieren. In der ersten Parameterliste müssen wir hierbei einen Initialwert festlegen, dessen Typ in die zweite Parameterliste inferiert wird und uns somit typsicheres Arbeiten erlaubt. Im letzten Beispiel dürft ihr noch die „verzuckerte“ Version des Codes bestaunen.

Wir können auch auf ein „fold“ verzichten und den Code ganz imperativ schreiben.

def sum(xs: List[Int]) = {
  var init = 0
  var ys = xs
  while (!ys.isEmpty) {
    init += ys.head
    ys = ys.tail
  }
  init
}
//in functional
//def sum(xs: List[Int]) = xs.fold(0)(_+_)

scala> val xs = (0 to 5).toList
xs: List[Int] = List(0, 1, 2, 3, 4, 5)

scala> sum(xs)
res0: Int = 15

Der imperative Code arbeitet identisch, ist aber um einiges länger als die funktional Variante. Schauen wir uns also mal die Definition von „fold“ an:

// in class LinkedList
def fold[B](init: B)(f: (B, A) => B): B = {
  def loop(xs: LinkedList[A], ret: B): B =
    if (xs.isEmpty) ret else loop(xs.tail, f(ret, xs.head))
  loop(this, init)
}

„fold“ ist für den Anfang schwerer zu verstehen. Das liegt in erster Linie aber an der Abstraktion. Der Code anpassbar an verschieden Aufgaben sein. Der weiter oben dargestellte imperative Code ist dies nicht. Die Methode „sum“ kann nur die Summe der Elemente ermitteln und sonst nichts. Ein „fold“ könnte für uns z.B. auch dann nützlich sein wenn wir unsere eigene Liste in eine Scala-Liste konvertieren wollen:

scala> val xs = LinkedList(1, 2, 3, 4, 5)
xs: LinkedList[Int] = LinkedList(1, 2, 3, 4, 5)

scala> xs.fold(List.empty[Int])((ys,x) => x :: ys)
res14: List[Int] = List(5, 4, 3, 2, 1)

Hm, leider ist die neue Liste umgedreht. Wir könnten sie jetzt von Hand umdrehen, aber das wäre unnötig aufwendig. Also was machen? Was wir bräuchten wäre ein „fold“, das die Elemente nicht von links nach rechts abarbeiten, sondern von rechts nach links. Aber wie geben wir das an? Die Antwort darauf ist, dass wir einfach ein neuen „fold“ erstellen, das genau so arbeitet:

def foldLeft[B](init: B)(f: (B, A) => B): B
def foldRight[B](init: B)(f: (A, B) => B): B

Mit der Richtungsangabe am Methodennamen bestimmen wir welches „fold“ wir benutzen möchten. „foldLeft“ ersetzt fortan unser altes „fold“, das wir nicht mehr benötigen:

// rename "fold" to "foldLeft" in LinkedList
// insert "foldRight"
def foldRight[B](init: B)(f: (A, B) => B): B =
  if (this.isEmpty) init
  else f(head, tail.foldRight(init)(f))

Schauen wir ob der Code so funktioniert wie wir es erwarten.

scala> xs.foldLeft(List.empty[Int])((ys, x) => x :: ys)
res23: List[Int] = List(5, 4, 3, 2, 1)

scala> xs.foldRight(List.empty[Int])((x, ys) => x :: ys)
res24: List[Int] = List(1, 2, 3, 4, 5)

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

„foldRight“ hat den großen Vorteil, dass die Parameter gleich in der richtigen Reihenfolge stehen – wir können also von den Unterstrich-Literalen Gebrauch machen. Die Methode hat aber auch einen riesigen Nachteil: Sie ist nicht tail-rekursiv. Das bedeutet, dass es bei großen Listen irgendwann zu einem StackOverflowError kommen würde. Es ist also ratsam anstatt einem „foldRight“ ein „foldLeft“ zu benutzen, die Collection davor aber mit „reverse“ umzudrehen. Das hat den gleichen Effekt und kann nicht zum Absturz des Programms führen.

Den obigen Code wollen wir nun auch für unsere eigene Liste möglich machen. Dazu benötigen wir aber noch eine parametrisierte leere Liste:

// in object LinkedList
def empty[A]: LinkedList[A] = LNil

Wir benötigen diese Methode, da LNil nicht parametrisiert ist und somit einen Compilerfehler verursachen würde wenn wir es direkt als Initialisierungswert verwenden würden.

Anstatt LinkedList.empty[X] können wir auch Nil: List[X] verwenden. Das würde den gleichen Effekt erzielen und LNil dem Compiler eine parametrisierte Liste vorgaukeln.

In den Scala-Bibliotheken gibt es alle drei Versionen von „fold“. Das normale „fold“ garantiert keine Abarbeitungsreihenfolge. Das bedeutet, dass die Library dynamisch zur Laufzeit entscheidet in welcher Reihenfolge die Elemente abgearbeitet werden sollen. Das ist besonders dann nützlich wenn mit parallelen Collections gearbeitet wird. Laut den Sourcen von TraversableOnce wird „fold“ für sequentielle Collections zwar auf ein „foldLeft“ weitergeleitet, es ist aber nicht sicher gestellt, das dies auch in Zukunft so bleibt. Allein aus dokumentationstechnischen Gründen empfiehlt es sich also „fold“ auch nur dann einzusetzen wenn man genau weiß, dass man es benötigt.

In die Bibliotheken von Scala wurde für die beiden richtungweisende fold-Methoden jeweils ein Operator integriert, der die Lesbarkeit erhöhen soll:

// in class LinkedList
def /: [B](init: B)(f: (B, A) => B): B = this.foldLeft(init)(f)

def :\ [B](init: B)(f: (A, B) => B): B = this.foldRight(init)(f)

Was für ein Schwachsinn werdet ihr euch jetzt vielleicht denken, das soll lesbarer sein? Wenn man es ausschreibt sieht man es vielleicht:

scala> (LinkedList.empty[Int] /: xs) ((ys, x) => x +: ys)
res27: LinkedList[Int] = LinkedList(5, 4, 3, 2, 1)

scala> (xs :\ LinkedList.empty[Int]) (_ +: _)
res29: LinkedList[Int] = LinkedList(1, 2, 3, 4, 5)

Das könnte man lesen als „starte mit einen leeren Liste und fasse alle Elemente von xs mit folgender Funktion zusammen“. Würde man statt dessen list.foldLeft(init)(f) schreiben, dann würde es sich eher als „nimm eine Liste und fasse sie mit der folgenden Funktion zu init zusammen“ lesen, was nicht korrekt wäre. Das gilt allerdings nur für die „foldLeft“-Variante. Die andere Methode würde sich genau gleich schreiben – ob mit oder ohne Operator-Symbol.

Mehrere Parameterlisten ermöglichen die Operator-Notation des Codes. Ein list.foldLeft(init)(f) kann auch als (list foldLeft init)(f) geschrieben werden.

Folding ist ein so allgemeines Konzept, dass man mit dessen Hilfe viele nützliche Methoden direkt in die Bibliotheken integriert hat. Eine dieser Methoden wäre z.B. sum:

// in class LinkedList
def sum[B >: A](implicit num: Numeric[B]): B =
  (num.zero /: this) (num.plus(_, _))

// could also be written as
def sum[B >: A](implicit num: Numeric[B]): B =
  (num.zero /: this) (num.plus)

scala> val xs = LinkedList(1, 2, 3, 4, 5)
xs: LinkedList[Int] = LinkedList(1, 2, 3, 4, 5)

scala> xs.sum
res33: Int = 15

Was wir hier noch nicht kennen ist der implizite Parameter, der sicher stellt, dass Elemente auch zusammen gezählt werden können. Er wird benötigt, da ein beliebiges Element vom Typ B keine Additions-Methode besitzt. Woher dieser Parameter kommt und was er genau macht werde ich euch in einem gesonderten Artikel erklären.

reduce

Die beiden folgende Methoden funktionieren äquivalent zum Folding. Sie sind nur auf einer niederen abstrakten Ebene. So haben sie keinen Initialisierungswert, sondern verwenden das erste Element einer Collection.

// in class LinkedList
def reduceLeft[B >: A](f: (B, A) => B): B =
  if (this.isEmpty) throw new UOE("nil.reduceLeft")
  else tail.foldLeft[B](head) { f }

def reduceRight[B >: A](f: (A, B) => B): B = 
  if (isEmpty) throw new UOE("nil.reduceRight")
  else if (tail.isEmpty) head
  else f(head, tail.reduceRight(f))

Wir müssen jetzt nur überprüfen ob die Liste auch tatsächlich befüllt ist, da wir nicht auf die Elemente einer leeren Liste zugreifen können.

scala> xs.reduceLeft(_+_)
res34: Int = 15

scala> xs.reduceRight(_+_)
res38: Int = 15

scala> LinkedList.empty[Int].reduceLeft(_+_)
java.lang.UnsupportedOperationException: nil.reduceLeft

Die reduce-Methoden bieten sich an wenn die Elemente untereinander zusammengefasst bzw. reduziert werden sollen. Falls wir ein gesondertes Initialisierungselement benötigen, müssen wir zu einem „fold“ greifen. Typische Beispiele für ein „reduce“ sind „min“ und „max“:

// in class LinkedList
def max[B >: A](implicit ord: Ordering[B]): B =
  if (this.isEmpty) throw new UOE("nil.max")
  else this reduceLeft ((ret, x) => if (ord.gteq(ret, x)) ret else x)
  
def min[B >: A](implicit ord: Ordering[B]): B =
  if (this.isEmpty) throw new UOE("nil.max")
  else this reduceLeft ((ret, x) => if (ord.lteq(ret, x)) ret else x)

scala> xs.min
res39: Int = 1

scala> xs.max
res40: Int = 5

Hier finden sich schon wieder implizite Parameter. Dieses Mal werden sie zum Vergleichen der beiden Elemente benötigt. Dass sie tatsächlich benötigt werden, sehen wir, wenn wir versuchen die Methoden auf eine Liste aufzurufen, die Objekte beinhaltet welche nicht sich nicht ordnen lassen:

scala> class X
defined class X

scala> val xs = LinkedList(new X, new X, new X)
xs: LinkedList[X] = LinkedList(X@45fd24c1, X@6e781ecc, X@102e1bbd)

scala> xs.max
<console>:41: error: No implicit Ordering defined for X.
              xs.max
                 ^

scala> xs.sum
<console>:41: error: could not find implicit value for parameter num: Numeric[X]
              xs.sum
                 ^

Diese Objekte haben nichts mit denen man sie vergleichen oder ordnen könnte. Der Code lässt sich also nicht kompilieren.

Lazy Collections

Zum Schluss möchte ich euch noch ein kleines Performance-Problem aufzeigen, das sich in den Funktionen höherer Ordnung versteckt. Folgendes Beispiel:

scala> def func[A](a: A) = { println("f"); a }
func: [A](a: A)A

scala> val xs = LinkedList(1, 2, 3, 4, 5)
xs: LinkedList[Int] = LinkedList(1, 2, 3, 4, 5)

scala> xs.map(x => func(x)+1).map(x => func(x)*2).filter(x => func(x) < 10).find(x => func(x) == 6)
f
f
f
f
f
f
f
f
f
f
f
f
f
f
f
f
f
res65: Option[Int] = Some(6)

Das Code-Beispiel macht praktisch keinen Sinn, verdeutlicht aber das Problem. Jede Funktion erstellt eine neue Collection. Wenn wir große Collections haben kann das schnell zu einem Performance-Killer werden, also müssen wir etwas dagegen tun. Da wir nur an von der zuletzt aufgerufenen Funktion eine Collection bzw. ein Element wollen, wäre es unsinnig all diese Zwischenberechnungen durchzuführen. Wir müssen sie abschalten. Aber wie? Wir könnten den Code ändern, aber das wäre erstens ein immenser Aufwand und zweitens wäre das nicht so ohne weiteres zu implementieren. Die einfache Lösung lauten „Lazy Collections“:

// in class LinkedList
def iterator: Iterator[A] = new Iterator[A] {
  var xs = self
  
  def next(): A = {
    val x = xs.head
    xs = xs.tail
    x
  }
  
  def hasNext = !xs.isEmpty
}

Der Sinn von „Lazy Collections“ ist es nur das zu berechnen was wirklich notwendig ist. Mit Iteratoren, Views und Streams stehen in Scala drei verschiedene „Lazy Collections“ zur Verfügung. Iteratoren sind am einfachsten zu erstellen, weshalb ich einen für euch implementiert habe. Schauen wir uns das mal an:

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

scala> iter.next()
res67: Int = 1

scala> iter.take(4)
res68: Iterator[Int] = non-empty iterator

scala> res68.toList
res69: List[Int] = List(2, 3, 4, 5)

scala> iter.next()
java.lang.UnsupportedOperationException: nil head

Das jeweils nächste Element wird erst dann berechnet wenn es auch tatsächlich angefordert wird. Rufen wir „next“ auf einen leeren Iterator auf, erhalten wir eine Exception. Da wir uns bei den Methoden an die Namensgebung aus der Standardbibliothek gehalten haben, können wir unseren Code ohne Einschränkungen anpassen:

scala> xs.iterator.map(x => func(x)+1).map(x => func(x)*2).filter(x => func(x) < 10).find(x => func(x) == 6)
f
f
f
f
f
f
f
f
res73: Option[Int] = Some(6)

Anhand den ausgegebenen f’s ist ganz klar zu erkennen, dass der Iterator sich bewährt. Und wir mussten nur diese eine Methode namens „iterator“ aufrufen um auf die mächtigen „Lazy Collections“ zugreifen zu können.

Das ist Abstraktion. Das ist Skalierbarkeit. Das ist Scala.

In diesem Kapitel habt ihr viel gelernt und wurdet mit vielen neuen Themen konfrontiert. Ihr werdet einige Zeit brauchen bis diesen Code sicher anwenden könnt, aber ich hoffe ihr habt die gezeigten Abstraktion verstanden und freut euch nun darauf sie irgendwann auch anwenden zu können.

Ich möchte euch hier noch den kompletten Code unserer LinkedList präsentieren. Ich habe ein paar weitere Methoden ergänzt und die Implementierung einzelner Funktionen auf Basis des in diesem Kapitel neu gelernten Wissens etwas überarbeitet. Schaut es euch einfach an und überlegt ob euch die Änderungen zusagen:

import scala.{ UnsupportedOperationException => UOE }

abstract class LinkedList[+A] { self =>
  def head: A
  def tail: LinkedList[A]
  def init: LinkedList[A]
  def last: A
  def isEmpty: Boolean
  
  def size: Int = {
    def loop(xs: LinkedList[A], i: Int): Int =
      if (xs.isEmpty) i else loop(xs.tail, i+1)
    loop(this, 0)
  }
  
  def +: [B >: A](x: B): LinkedList[B] =
    new +:(x, this)
  
  def ++: [B >: A](xs: LinkedList[B]): LinkedList[B] =
    if (this.isEmpty) xs
    else if (xs.isEmpty) this
    else {
      def loop(xs: LinkedList[B], ys: LinkedList[B]): LinkedList[B] =
        if (xs.isEmpty) ys else loop(xs.tail, xs.head +: ys)
      loop(xs.reverse, this)
    }
  
  def ++ [B >: A](xs: LinkedList[B]): LinkedList[B] =
    if (this.isEmpty) xs
    else this ++: xs
    
  def /: [B](init: B)(f: (B, A) => B): B = this.foldLeft(init)(f)
  
  def :\ [B](init: B)(f: (A, B) => B): B = this.foldRight(init)(f)
    
  def apply(index: Int): A =
    if (this.isEmpty || index < 0 || index >= this.size)
      throw new IndexOutOfBoundsException(index.toString)
    else {
      def loop(i: Int, xs: LinkedList[A]): A =
        if (i == 0) xs.head else loop(i-1, xs.tail)
      loop(index, this)
    }
  
  def foreach(f: A => Unit) {
    var xs = this
    while (!xs.isEmpty) {
      f(xs.head)
      xs = xs.tail
    }
  }
  
  def map[B](f: A => B): LinkedList[B] =
    (LinkedList.empty[B] /: this) { (xs, b) => f(b) +: xs } reverse
  
  def take(elems: Int): LinkedList[A] =
    if (elems <= 0) LNil
    else if (elems >= this.size) this
    else {
      def loop(i: Int, xs: LinkedList[A], ys: LinkedList[A]): LinkedList[A] =
        if (i == 0) ys else loop(i-1, xs.tail, xs.head +: ys)
      loop(elems, this, LNil).reverse
    }
  
  def drop(elems: Int): LinkedList[A] = {
    def loop(elems: Int, xs: LinkedList[A]): LinkedList[A] =
      if (elems <= 0) xs else loop(elems-1, xs.tail)
    if (elems >= this.size) LNil
    else loop(elems, this)
  }
  
  def filter(f: A => Boolean): LinkedList[A] =
    (LinkedList.empty[A] /: this) { (xs, a) => if (f(a)) a +: xs else xs } reverse
  
  def reverse: LinkedList[A] =
    (LinkedList.empty[A] /: this) { (xs, a) => a +: xs }
  
  def contains[B >: A](elem: B): Boolean = {
    def loop(xs: LinkedList[A]): Boolean =
      if (xs.isEmpty) false
      else if (xs.head == elem) true
      else loop(xs.tail)
    loop(this)
  }
  
  def find(f: A => Boolean): Option[A] = {
    def loop(xs: LinkedList[A]): Option[A] =
      if (xs.isEmpty) None
      else if (f(xs.head)) Some(xs.head)
      else loop(xs.tail)
    loop(this)
  }
  
  def exists(f: A => Boolean): Boolean =
    find(f) != None
  
  def foldLeft[B](init: B)(f: (B, A) => B): B = {
    def loop(xs: LinkedList[A], ret: B): B =
      if (xs.isEmpty) ret else loop(xs.tail, f(ret, xs.head))
    loop(this, init)
  }
  
  def foldRight[B](init: B)(f: (A, B) => B): B =
    if (this.isEmpty) init
    else f(head, tail.foldRight(init)(f))
  
  def reduceLeft[B >: A](f: (B, A) => B): B =
    if (this.isEmpty) throw new UOE("nil.reduceLeft")
    else tail.foldLeft[B](head) { f }
  
  def reduceRight[B >: A](f: (A, B) => B): B = 
    if (isEmpty) throw new UOE("nil.reduceRight")
    else if (tail.isEmpty) head
    else f(head, tail.reduceRight(f))
  
  def sum[B >: A](implicit num: Numeric[B]): B =
    (num.zero /: this) { num.plus }
  
  def max[B >: A](implicit ord: Ordering[B]): B =
    if (this.isEmpty) throw new UOE("nil.max")
    else this reduceLeft { (ret, x) => if (ord.gteq(ret, x)) ret else x }
    
  def min[B >: A](implicit ord: Ordering[B]): B =
    if (this.isEmpty) throw new UOE("nil.max")
    else this reduceLeft { (ret, x) => if (ord.lteq(ret, x)) ret else x }
  
  def mkString: String = mkString("LinkedList(", ", ", ")")
  
  def mkString(start: String, sep: String, end: String): String =
    if (this.isEmpty) ""
    else {
      val sb = StringBuilder.newBuilder
      sb append start
      sb append head
      
      for (x <- tail) {
        sb append sep
        sb append x
      }
      
      sb append end
      sb.toString
    }
  
  def sorted[B >: A](implicit ord: Ordering[B]): LinkedList[B] = {
    import ord._
    def qsort(xs: LinkedList[B]): LinkedList[B] = xs match {
      case LNil => LNil
      case x +: xs => qsort(xs filter { _ < x }) ++: LinkedList(x) ++: qsort(xs filter { _ >= x })
    }
    qsort(this)
  }
  
  def zip[B](xs: LinkedList[B]): LinkedList[(A, B)] = {
    val (i1, i2) = (this.iterator, xs.iterator)
    def loop(xs: LinkedList[(A, B)]): LinkedList[(A, B)] =
      if (i1.hasNext && i2.hasNext) loop((i1.next() -> i2.next()) +: xs) else xs
    loop(LNil).reverse
  }
  
  def iterator: Iterator[A] = new Iterator[A] {
    var xs = self
    
    def next(): A = {
      val x = xs.head
      xs = xs.tail
      x
    }
    
    def hasNext = !xs.isEmpty
  }
  
  def flatten: LinkedList[Any] =  this match {
    case LNil => LNil
    case (head: LinkedList[_]) +: tail => head.flatten ++ tail.flatten
    case head +: tail => head +: tail.flatten
  }
  
  def break(f: A => Boolean): (LinkedList[A], LinkedList[A]) = {
    def loop(xs: LinkedList[A], ys: LinkedList[A]): (LinkedList[A], LinkedList[A]) =
      if (xs.isEmpty) LNil -> LNil
      else if (f(xs.head)) ys.reverse -> xs
      else loop(xs.tail, xs.head +: ys)
    loop(this, LNil)
  }
}

object LinkedList {
  def apply[A](a: A*): LinkedList[A] =
    (a :\ empty[A]) { _ +: _ }
  
  def empty[A]: LinkedList[A] = LNil
  
  def unapplySeq[A](a: A*): Option[Seq[A]] = Some(a)
}

final case class +: [A](head: A, tail: LinkedList[A]) extends LinkedList[A] {
  def init = this take this.size-1
  def last = (this drop this.size-1).head
  def isEmpty = false
  
  override def toString = mkString
}

final case object LNil extends LinkedList[Nothing] {
  def head = throw new UOE("nil head")
  def tail = throw new UOE("nil tail")
  def init = throw new UOE("nil init")
  def last = throw new UOE("nil last")
  def isEmpty = true
}
Advertisements

1 comment so far

  1. Stefan on

    „Scalas Syntaxzucker“ irgendwie lustig das so zu lesen 😀


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: