Archive for Januar 2012|Monthly archive page

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
}

Teil 16: Funktionen

Viel haben wir uns in letzter Zeit mit Scala beschäftigt. Das bisher gesehene war aber nur die Spitze des Eisbergs und gab uns lediglich einen Einblick in die imperative Programmierung mit Scala. Lassen wir dies aber nun hinter uns und folgen endlich dem Weg der funktionalen Programmierung. Den Anfang machen die Funktionen, da sie der Grundbestandteil einer jeden funktionalen Sprache sind.

Funktionen aus der funktionalen Programmierung sind nicht zu verwechseln mit den Funktionen aus der prozeduralen Programmierung. In letzterem dienen sie dazu den Kontrollfluss übersichtlicher zu gestalten und Redundanzen zu vermindern. Das Konzept einer Funktion aus der funktionalen Programmierung ähnelt dagegen mehr dem einer Methode, die nicht an eine Klasse gebunden ist: Sie kann einen Wert als Eingabe erhalten und liefert dazu ein entsprechendes Resultat. Im Gegensatz zu einer Methode ist eine Funktion in Scala aber ein Objekt und kann deshalb auch so behandelt werden. Sie können in einem Programm herumgereicht und in Ausdrücken ausgewertet werden. Das macht sie viel flexibler als stinknormale Methoden, die immer nur an eine einzelne Klasse gebunden sind.

Durch diese große Ähnlichkeit ist eine Funktion in der Benutzung auf den ersten Blick nicht von einer Methode zu unterscheiden:

val double: (Int) => (Int) = {
  (i: Int) => i*2
}

scala> double(5)
res26: Int = 10

scala> double(-12)
res27: Int = -24

Eine Funktion wird durch das =>-Symbol erstellt, dem sogenannten Funktions-Literal. Wie allem in Scala können wir der Funktion mit dem Gleichheitszeichen einen Körper zuweisen, der jedes Mal ausgeführt wird wenn die Funktion aufgerufen wird. Dass eine Funktion aber eben nicht wie eine Methode funktioniert ist ganz klar an dem „val“ vor der Definition zu erkennen. Die Funktion wird an eine Variable gebunden und kann dennoch mit Parametern aufgerufen werden – das ist bei einer Methode nicht möglich. Was nach dem Namen der Variable folgt ist der Typ der Variable. In unserem Fall wäre das (Int) => (Int). Das bedeutet so viele wie: Nimm einen Int als Eingabe und gebe wieder einen Int aus. Die Syntaxregel für diese Schreibweise lautet:

(<input_param1>, <input_param2>, <input_paramN>) => (<output_param1>, <output_param2>, <output_paramN>)

Die Schreibweise der Ein- und Ausgabeparameter gleicht der von Tupeln. In runden Klammern werden die einzelnen Parameter durch Kommas voneinander getrennt. Tatsächlich handelt es sich aber nur bei den Ausgabeparametern um Tupel, erwarten tut eine Funktion keine Tupel, sondern mehrere Parameter, wie bei einer Methode. Besonders praktisch ist noch, dass wir bei einem einzigen Parameter die runden Klammern weglassen können:

val mul: (Int, Int) => Int = {
  (i: Int, j: Int) => i*j
}
val twice: Int => (Int, Int) = {
  (i: Int) => (i, i)
}

scala> mul(3, 4)
res30: Int = 12

scala> mul.apply(3, 4)
res31: Int = 12

scala> val t = (3, 4)
t: (Int, Int) = (3,4)

scala> mul(t)
:10: error: not enough arguments for method apply: (v1: Int, v2: Int)Int in trait Function2.
Unspecified value parameter v2.
              mul(t)
                 ^

scala> twice(3)
res1: (Int, Int) = (3,3)

scala> val (x, y) = twice(3)
x: Int = 3
y: Int = 3

Versuchen wir einen Tupel an unsere Funktion zu übergeben, so erhalten wir eine Fehlermeldung. Der Aufruf der apply-Methode ist ein weiteres Indiz darauf, dass Funktionen gewöhnliche Objekte sind und bei ihrem Aufruf von Scalas Syntaxzucker profitieren. Wollen wir nun einen Block zur Ausführung an eine Funktion binden, so müssen wir diesen durch notieren eines =>-Symbols auch entsprechend als Funktionskörper kennzeichnen. Wir benötigen ihn um die Eingabeparameter einer Funktion an Variablen binden zu können. Das Literal (i: Int, j: Int) => bedeutet also: Binde den ersten Eingabeparameter an die Variable i, den zweiten an die Variable j und mache diese Variablen auf der rechten Seite verfügbar. Dank Scalas Typinferenz müssen wir den Typ dieser Variablen aber nur seltenst angeben, in unserem Fall können wir sie weglassen.

val mul: (Int, Int) => Int = {
  (i, j) => i*j
}

Existiert nur ein Kommando im Block, so können wir auch die geschweiften Klammern auslassen:

val mul: (Int, Int) => Int = (i, j) => i*j

Auf den ersten Blick sieht das alles sehr abenteuerlich aus und dürfte die Frage aufkommen lassen wofür man das zum Teufel nochmal benötigt. Was für einen Vorteil sollte man schon haben wenn man statt einer Methode eine Funktion zur Abarbeitung des Codes nutzt?

Die Antwort darauf ist kurz aber unverständlich: Es dient zur Abstraktion. Toll, zu welcher Abstraktion? Dies ist die weitaus wichtigere Frage wenn man verstehen will wofür Paradigmen gebraucht werden. Wichtig ist nicht was sie abstrahieren und wie sie es tun, sondern welchen konkreten Vorteil man von deren Einsatz hat.

Um zu erklären welche Vorteile es hat Funktionen einzusetzen, möchte ich zu einem Beispiel aus der imperativen Programmierwelt greifen.

def extensiveOp() = { Thread.sleep(2000); 1 }
def anotherExtensiveOp() = { Thread.sleep(2000); 2 }

def executeWhenNecessary(cond: Boolean, f: Int) =
  if (cond) f else 0

Der Code sollte nicht schwer zu verstehen sein. Wir wollen eine teure Operation nur dann ausführen wenn eine bestimmte Bedingung wahr ist. Übergeben wir die auszuführende Methode, dann erzielen wir aber nicht den gewünschten Effekt. Nicht die Methode wird übergeben, sondern deren Rückgabewert.

scala> executeWhenNecessary(false, extensiveOp)

res10: Int = 1

Nun stellt sich die Frage wie wir dieses Problem am geschicktesten lösen. Eine Möglichkeit wäre anstatt der Methode ein Enum zu übergeben, anhand dessen wir dann innerhalb der Methode die richtige Methode zur Abarbeitung auswählen können:

object Op extends Enumeration {
  val Extensive, AnotherExtensive = Value
}
import Op._

// other methods as before

def executeWhenNecessary(cond: Boolean, op: Op.Value) =
  if (cond) op match {
    case Extensive => extensiveOp()
    case AnotherExtensive => anotherExtensiveOp()
  }
  else 0

Nun funktioniert der Code auch korrekt:

scala> executeWhenNecessary(false, Extensive)

res11: Int = 0

Obige Vorgehensweise birgt aber einige Nachteile. Wir benötigen zum einen einen Enum und müssen diesen umständlich importieren und adressieren. Zum anderen ist unser Code nicht mehr skalierbar. Ändern wir etwas am Enum oder an den auszuführenden Methoden, so müssen wir auch die Methode executeWhenNecessary ändern.
Eine andere Lösung geht über die Ausführung einer gewrappten Methode:

trait Operation {
  def apply(): Int
}

// other methods as before

def executeWhenNecessary(cond: Boolean, op: Operation) =
  if (cond) op() else 0

Bei dieser Lösung benötigen wir einen Wrapper, der den Code beinhaltet, der ausgeführt werden soll.

executeWhenNecessary(false, new Operation {
  def apply() = extensiveOp()
})
// this code will return immediately

Im Gegensatz zur vorherigen Lösung über ein Enum haben wir aber einen entscheidenden Vorteil: Skalierbarkeit. Wollen wir später etwas ändern ist dies kein Problem, da wir nur den Inhalt des Wrappers ändern müssen und sonst nichts. Ein weiterer Vorteil gegenüber Enums ist, dass wir den Code parametrisieren können:

trait Operation[A] {
  def apply(): A
}

// other methods as before

def executeWhenNecessary[A](cond: Boolean, op: Operation[A]): Option[A] =
  if (cond) Some(op()) else None

Nun können wir beliebige Objekte zurückgeben:

executeWhenNecessary(false, new Operation[String] {
  def apply() = "hello world"
})
executeWhenNecessary(false, new Operation[Int] {
  def apply() = 10
})

Wir haben sogar die Möglichkeit eine unterschiedliche Anzahl an Übergabeparametern festzulegen:

trait Operation0[Ret] {
  def apply(): Ret
}
trait Operation1[A, Ret] {
  def apply(a: A): Ret
}
trait Operation2[A, B, Ret] {
  def apply(a: A, b: B): Ret
}

def execute0[Ret](op: Operation0[Ret]) = op()
def execute1[A, Ret](a: A)(op: Operation1[A, Ret]) = op(a)
def execute2[A, B, Ret](a: A, b: B)(op: Operation2[A, B, Ret]) = op(a, b)

// and so on...

Der Einsatz dieser Wrapper erklärt sich von selbst:

//for Operation0

scala> execute0(new Operation0[String] { def apply() = "hello world" })
res27: String = hello world

//for Operation1

val reverse = new Operation1[String, String] { def apply(str: String) = str.reverse }

scala> execute1("hello")(reverse)
res26: String = olleh

// for Operation2

val add = new Operation2[Int, Int, Int] { def apply(i: Int, j: Int) = i+j }
val multiply = new Operation2[Int, Int, Int] { def apply(i: Int, j: Int) = i*j }

scala> execute2(8, 3)(add)
res22: Int = 11

scala> execute2(8, 3)(multiply)
res23: Int = 24

def add(i: Int, j: Int) = execute2(i, j)(new Operation2[Int, Int, Int] { def apply(i: Int, j: Int) = i+j })
def multiply(i: Int, j: Int) = execute2(i, j)(new Operation2[Int, Int, Int] { def apply(i: Int, j: Int) = i*j })

scala> add(8, 3)
res28: Int = 11

scala> multiply(8, 3)
res29: Int = 24

Je nach eingesetzter OperationX und mit Hilfe von sogenanntem Currying können wir unterschiedliche Operationen ausführen.

Currying bezeichnet ein Verfahren bei dem Funktionen mit mehreren Parameterlisten miteinander so verkettet werden, sodass am Ende eine Funktion mit nur einer Parameterliste übrig bleibt (wie gezeigt an den add und multiply Methoden). Oben haben wir zwar Methoden anstatt Funktionen zur Verkettung eingesetzt, aber das kann man durchaus auch als Currying durchgehen lassen.

Tolle Abstraktion, da versteht man ja gar nichts mehr. Das oder so etwas ähnliches werdet ihr jetzt vermutlich denken. Und dem stimme ich euch auch voll zu. Das Problem ist nämlich, dass wir viel zu viel syntaktischen Overhead haben. Wir müssen einen OperationX erstellen, deren Typparameter angeben und die apply-Methode implementieren. Was für ein Aufwand. Geht das nicht einfacher?

Natürlich geht es einfacher, sonst würde ich euch das hier nicht erklären. In der Scala-Lib gibt es bereits vordefinierte Objekte namens FunctionX, die gleich wie unsere OperationX-Objekte funktionieren.

def execute2[A, B, Ret](a: A, b: B)(f: Function2[A, B, Ret]) = f(a, b)

def add(i: Int, j: Int) = execute2(i, j)(new Function2[Int, Int, Int] { def apply(i: Int, j: Int) = i+j })
def multiply(i: Int, j: Int) = execute2(i, j)(new Function2[Int, Int, Int] { def apply(i: Int, j: Int) = i*j })

scala> add(8, 3)
res33: Int = 11

scala> multiply(8, 3)
res34: Int = 24

Somit entfällt schon einmal die Definition der OperationX-Objekte. Das ist aber nicht alles. In Scala ist FunctionX ein Synonym für ein Funktionsliteral. Genau genommen ist ein Funktionsliteral syntaktischer Zucker zur Erstellung von Funktionen. Wir können das obige Beispiel also auch so schreiben:

def execute2[A, B, Ret](a: A, b: B)(f: (A, B) => Ret) = f(a, b)

def add(i: Int, j: Int) = execute2(i,j)((i, j) => i+j)
def multiply(i: Int, j: Int) = execute2(i,j)((i, j) => i*j)

scala> add(8, 3)
res35: Int = 11

scala> multiply(8, 3)
res36: Int = 24

Das sieht doch gleich viel besser aus. Aber ist das jetzt die versprochene Abstraktion? Unser Code ist ein wenig skalierbarer geworden. Wir können die Funktionsweise der executeX-Methoden ändern, ohne dass wir die darauf aufbauenden Methoden ändern müssten. Ebenso haben wir eine komfortable Möglichkeit kennen gelernt wie wir Code verzögert ausführen können (Erinnerung an die executeWhenNecessary-Methode). Aber das dürfte euch noch zu wenig sein. Setzen wir also noch eins drauf und führen noch mehr Syntaxzucker ein.

Unterstrich-Platzhalter

Gegeben sei nach wie vor eine execute-Methode:

def execute[A, B, Ret](a: A, b: B)(f: (A, B) => Ret) = f(a, b)

Sie soll weiterhin als Platzhalter für beliebigen Code dienen, den wir statt dessen ausführen könnten. Die Erstellung einer darauf aufbauenden Methode wie add oder multiply ist nicht schwer, kann aber noch weiter vereinfacht werden:

def add(i: Int, j: Int) = execute(i,j)(_+_)
def multiply(i: Int, j: Int) = execute(i,j)(_*_)

scala> add(8, 3)
res37: Int = 11

scala> multiply(8, 3)
res38: Int = 24

Der Unterstich dient uns – wie schon bei vielem in Scala – als Platzhalter für ein Funktionsargument. Wir können also immer so viele Funktions-Platzhalter verwenden wie wir Argumente haben. Eine Übersicht:

_ = a
_ _ = (a, b)
_ _ _ = (a, b, c)
usw.

Hat man sich erst einmal an die Platzhalter-Schreibweise gewöhnt, so ist diese sehr gut lesbar. (_+_) kann man als „Erzeuge eine Funktion und addiere zu deren ersten Parameter den zweiten Parameter“ lesen und ist die schon fast kürzeste Schreibweise, die es gibt. Noch kürzer ist nur noch (+), also eine Notation bei der die Unterstriche komplett fehlen, aber diese Schreibweise würde einen Fehler verursachen. Sie bedeutet nämlich nicht (_+_), sondern +(_, _). Wir können das mit folgender Funktion ausprobieren:

def doubleAdd(i: Int, j: Int) = 2*execute(i, j)((i, j) => add(i, j))
def doubleAdd(i: Int, j: Int) = 2*execute(i, j)(add(_, _))
def doubleAdd(i: Int, j: Int) = 2*execute(i, j)(add)

scala> doubleAdd(8, 3)
res40: Int = 22

Wie zu sehen funktioniert das Platzhalter-Symbol nicht nur für Funktionen sonder auch für die Parameter einer normalen Methode. Wichtig ist dabei, dass mit dem Platzhalter-Symbol nicht die Reihenfolge der Parameter geändert werden kann. Das bedeutet, dass ein (_+_) niemals (a, b) => b+a heißen kann. Wollen wir die Parameter umdrehen müssen wir also auf die Platzhalter-Schreibweise verzichten.

Ich möchte euch die Regeln, wann und wo genau ein Unterstrich verwendet werden darf, jetzt aber nicht näher erläutern, das werde ich in einem der der weiteren Artikel nachholen. Jetzt ist wichtig, dass ihr die Schreibweise mal gesehen habt, damit ihr damit etwas anfangen könnt.

Diese Schreibweise ist zwar schön kurz, aber selbst wenn ihr sie jetzt schon komplett verstanden habt dürfte euch noch immer nicht klar sein wie man damit abstrahiert programmieren kann. Gehen wir also zum nächsten Kapitel weiter, in dem ich euch ein praktisches Beispiel zeigen werde an dem ihr erkennen könnt wozu sich Funktionen so alles einsetzen lassen.