Archive for the ‘Scala’ Category

Teil 17: Fehlerbehandlung

Fehler gehören zum alltäglichen Geschäft eines jeden Entwicklers – man sollte also stets auf sie vorbereitet sein und sie einer ordentlichen Behandlung unterziehen. Geht man nicht auf ihre Bedürfnisse ein kann es schon mal passieren, dass sie die Oberhand gewinnen und die Kontrolle der Codeausführung an sich reißen. Und ehe man sich versieht findet man sich wieder in den Tiefen der Funktionsaufrufe oder im Labyrinth der Kontrollstrukturen, mit dem man doch so wenig zu tun haben möchte. Trotz dieser Gefahren vernachlässigen viele Entwickler den Aspekt der Fehlerbehandlung, weshalb eine gute Sprache sie hier ein wenig an der Hand nehmen sollte um ihnen zu zeigen wo es lang geht. Leider gehört die Beihilfe für eine ordentliche Fehlerbehandlung bei einigen Programmiersprachen zu den eher vernachlässigten Sprachbestandteilen, weshalb der Entwickler am Ende doch wieder auf all seinen Fehlern sitzenbleibt.

Dies muss aber keinesfalls so sein – funktionale Programmiersprachen versuchen schon seit jeher potenzielles Auftreten von Fehlern schon im Keim zu ersticken indem sie dem Entwickler genügend Abstraktionen in die Hand geben um sie dann mit Hilfe eines strengen Typsystems vor den damit veranstalteten Dummheiten schützen zu können. Durch den konsequenten Einsatz von abstrakten Konzepten ist es funktionalen Programmiersprachen gelungen den Entwickler zu einer deklarativen Denkweise zu erziehen, in der nur noch modelliert wird was der Code machen soll und nicht wie er es tut. Dies allein verbessert die Les- und Wartbarkeit von Code schon enorm und vermindert gleichzeitig die Anzahl potenzieller Fehlerquellen. Ein Beispiel für ein imperatives Stück Code könnte z.B. so aussehen:

def multiply(n: Int): Seq[Int] = {
  var xs = List.empty[Int]
  var i = 0
  while (i < n) {
    i += 1
    xs = n :: xs
  }
  xs
}

Dieser Code vervielfacht eine Zahl gemäß ihrer Größe und er funktioniert so weit auch wie er soll. Doch wie lange braucht man um ihn zu schreiben und wie viele Fehler könnten sich hier wohl einschleichen? So ist es z.B. möglich die Indexvariable bis zu einem falschen Wert laufen zu lassen, sie falsch hoch zu zählen oder sie gar anstelle der geforderten Zahl zur Liste hinzuzufügen. Nicht zu vergessen, dass die alte Liste auch noch jedes Mal mit der Neuen ersetzt werden muss – ein grauenvoller Code, der bei einem Fehlerfall viel Debuggingzeit erfordern kann. Von potenziellen Wutausbrüchen und ausgesprochenen Flüchen des Entwicklern und den daraus resultierenden psychischen Schäden des Computers ob der wüsten Beschimpfungen will ich gar nicht erst anfangen. Alles in allem geht man all diesen Problemen aus dem Weg wenn man sich den Paradigmen der funktionalen Programmierwelt beugt und zu einer deklarativen Vorgehensweise greift:

def multiply(n: Int): Seq[Int] =
  1 to n map (_ => n)

Natürlich ist es auch hier nicht möglich alle Fehler gleich beseitigt zu wissen, aber dieses Beispiel ist so kurz und knapp, dass man hier höchstens noch ein paar Logikfehler einbauen kann. So könnte man anstatt von eins von null zu zählen beginnen oder anstatt „map“ irgendeine andere Funktion höherer Ordnung auswählen. Vor letzterem kann uns aber der Compiler effektiv schützen, weil es sehr wahrscheinlich ist , dass es Unstimmigkeiten zwischen den Typsignaturen geben wird. Und selbst wenn der Fall eintritt und eine Funktion nicht das macht was sie machen sollte muss man hier wohl nie zu einem Debugger greifen sondern kann durch erneutes Nachdenken herausfinden wo sich der Fehler verbirgt.

Auch wenn sich Fehler niemals komplett vermeiden lassen so fühlt man sich doch gleich ein wenig besser wenn man weiß, dass der entwickelte Code unter der schützenden Hand des Compilers steht. Gehen wir nun also von den theoretischen Überlegungen weg, wie man verhindern kann, dass Fehler überhaupt erst auftreten, hin zu den Überlegungen was getan werden soll wenn ein Fehler erst einmal aufgetreten ist. Wie man einen Fehler innerhalb einer Funktion an die aufrufende Funktion meldet und wie die aufrufende Funktion mit dem Fehler umgeht sind zwei Paar Stiefel, die es getrennt zu betrachten gilt. Weiterhin gilt, dass auch die Art, wie mit einem Fehler umgegangen wird, aus zwei separaten Blickwinkeln betrachtet wird: Zum Einen gibt es die Möglichkeit einen Code zurückzugeben, der signalisiert ob alles korrekt verlaufen ist oder ob ein Fehler aufgetreten ist. Zum Anderen verfügen die meisten modernen Programmiersprachen über das Konzept der Exceptions – ein Geflecht aus Sprunganweisungen, die den Programmfluss unterbrechen und klug eingesetzt werden müssen um die Stabilität eines Programms nicht zu gefährden.

In funktionalen Programmiersprachen wird das Prinzip der Fehlercodes bevorzugt – also auch in Scala. Ich kann euch aber beruhigen, unter Fehlercode braucht ihr euch nicht das primitive und minderwertige Prinzip vorstellen, das z.B. in C vorkommt. Dort werden oft Integer-Werte zurückgegeben, die signalisieren ob eine Funktion erfolgreich durchlaufen werden konnte. In funktionalen Sprachen werden statt dessen typsichere Datentypen bzw. vollwertige Objekte zurückgegeben, die über ein zum Teil hochspezialisiertes Verhalten verfügen, mit dem die Art, wie mit dem Fehler umgegangen wird, bestimmt wird. In Scala begegnen uns diese „Fehlercodes“ in Form der Datentypen Option und Either, mit denen ich euch im Folgenden anfreunden möchte. Doch zuvor sollten wir einen Blick auf Exceptions werfen und uns verdeutlichen warum wir auf sie so gut es geht verzichten sollten.

Exceptions

Exceptions sind gleichermaßen mächtig wie gefährlich. Sie erlauben es, das eigentliche Programm zu jeder Zeit zu unterbrechen um es an einer anderen Stelle wieder fortzusetzen – was überhaupt nicht dem Sinne der strukturierten Programmierung entspricht. Falls Exceptions also zur Codeflusssteuerung genutzt werden, kann das schwere negative Folgen auf die Wartbar- und Übersichtlichkeit des Programms haben. Ob dieser Gefahren ist es sinnvoll Exceptions in erster Linie nur zur Verifizierung des Codes einzusetzen, was bedeutet, dass sie auf Programmierfehler hinweisen sollen und Laufzeitfehler, die mit I/O-Operationen zusammenhängen, aufdecken sollen.

Exceptions werden in Scala nach dem gleichen Prinzip erstellt wie in vielen anderen Sprachen auch:

def multOnlyPositive(i: Int) =
  if (i > 0) i*i else throw new UnsupportedOperationException

scala> multOnlyPositive(3)
res7: Int = 9

scala> multOnlyPositive(-3)
java.lang.UnsupportedOperationException
<stacktrace>

Das Schlüsselwort throw ist die einzige Möglichkeit ein Objekt vom Typ java.lang.Throwable durch das Programm zu „werfen“. Gefangen werden kann die Exception dann wieder mit der try-catch-expression:

def canProduceError(i: Int) = {
  val result = try multOnlyPositive(i) catch {
    case e: UnsupportedOperationException => 0
  }
  result == 0
}

scala> canProduceError(3)
res9: Boolean = false

scala> canProduceError(-3)
res10: Boolean = true

Wie jedes Konstrukt in Scala besitzt auch die try-catch-expression in Scala einen Rückgbabewert. Außerdem kann entweder ein ganzer Block oder auch nur ein einzelnes Statement an die Expression gebunden werden, wie es im Beispiel gut zu erkennen ist. Dies ermöglicht es uns die catch-expression an beliebige Funktionen zu binden:

def x: String = throw new UnsupportedOperationException
def y: String = throw new IllegalArgumentException
def z: String = throw new Exception

val handler1: PartialFunction[Throwable, String] = {
  case _: UnsupportedOperationException => "got it"
}
val handler2: PartialFunction[Throwable, String] = {
  case _: IllegalArgumentException => "and this too"
}

scala> try x catch handler1 orElse handler2
res12: String = got it

scala> try y catch handler1 orElse handler2
res13: String = and this too

scala> try z catch handler1 orElse handler2
java.lang.Exception
<stacktrace>

Das Beispiel zeigt, dass es über die übliche „orElse“-Methode einer Funktion möglich ist verschiedene Handler miteinander zu verbinden. Sollte der Fall eintreten, dass die catch-expression keinen Handler findet, der die Exception verarbeiten kann, so wird diese einfach weiter geworfen. Der Grund warum wir partielle Funktionen benötigen ist schnell erklärt: Da ein passender Exception-Handler über Pattern-Matching herausgesucht wird, würde es zu einem MatchError kommen sollte kein passender Handler gefunden werden. Da die catch-expression ein Throwable fangen kann ist es unabdingbar, dass die partielle Funktionen auch diesen Typ erwarten. Eine Spezialisierung, z.B. auf Exception, würde zu einem Typfehler führen.

Neben der try-catch-expression gibt es noch den finally-Block, den man mit einem try-catch kombinieren kann. Der finally-Block ermöglicht es Code auszuführen, der immer ausgeführt wird – egal ob eine Exception aufgetreten ist oder nicht:

def multOnlyPositive(i: Int) =
  if (i > 0) i*i else throw new UnsupportedOperationException

scala> try multOnlyPositive(-3) catch { case _ => 0 } finally println("finally is executed")
finally is executed
res4: Int = 0

scala> try multOnlyPositive(3) catch { case _ => 0 } finally println("finally is executed")
finally is executed
res5: Int = 9

Es ist zu beachten, dass der Rückgabewert von finally verworfen wird, d.h. er beeinflusst nicht die try-catch-expression. In ihm können mehr oder weniger sinnvolle Dinge getan werden wie z.B. eine Datenbankverbindung schließen nachdem bei deren Benutzung eine Exception geworfen wurde.

Anmerkung: Die try-expression kann auch ohne eine catch-expression existieren, hat dann aber keinen Zweck. Der Code wird genauso ausgeführt wie wenn die try-expression nicht existieren würde. Die catch-expression und der finally-Block dürfen dagegen niemals alleine stehen.

In den meisten Fällen, in denen Fehler im Programmcode auftreten, muss man aber keine Exceptions einsetzen. Stattdessen macht es mehr Sinn auf Scalas „Returncodes“ zu setzen, da diese über viele Methoden verfügen, die es ermöglichen einen Fehler einfach, unkompliziert und absolut typsicher zu bearbeiten.

Option

Den ersten Datentyp zur Fehlerbehandlung, den ich euch vorstellen möchte, ist Option. Er ist mehr oder weniger die funktionale Antwort auf „null“ dem grausamen Gebilde, das leider in viel zu vielen Programmiersprachen seinen Einsatz findet. Ich möchte euch im Nachfolgenden erklären, warum null so böse ist, Option dagegen einfach nur wundervoll und vor allem wie man damit vernünftig arbeitet.

Option kann zwei Typen annehmen – Some und None, wobei man letzteres mit null vergleichen kann. None ist ein Singleton, das für keinen näher bestimmten Rückgabewert steht. Demgegenüber steht Some, das den eigentlichen Rückgabewert einer Funktion in sich aufnimmt und deshalb als Container für beliebige Typen dient. Ein Beispiel zur Funktionsweise:

def valueOf(i: Int): Option[String] = {
  val db = IndexedSeq("hello", "world", "how", "are", "you")
  if (i > 0 && i < db.size) Some(db(i)) else None
}

scala> valueOf(2)
res10: Option[String] = Some(how)

scala> valueOf(5)
res11: Option[String] = None

Es gibt mehrere Wege die Typen von Option zu erstellen. Für Some geht es am einfachsten wenn man dessen apply-Methode oder dessen Konstruktor mit dem Wert, den es aufnehmen soll, aufruft. Da None nicht erzeugt werden muss, sondern genau wie bspw. Nil bereits vorhanden ist, kann man es einfach über dessen Namen referenzieren.

Eine weitere Möglichkeit ein Option zu erzeugen ist über die apply-Methode von Option. Wird diese apply-Methode mit null aufgerufen wird None zurückgegeben, ansonsten ein Some. Das ist ganz praktisch wenn eine Funktion einen Wert zurückgibt, der null sein kann, man aber lieber mit Option arbeiten möchte (was man in Scala immer möchte – sofern null nicht unbedingt benötigt wird).

Nun bleibt nur noch zu klären was es uns bringt Option einzusetzen. Wollen wir auf unsere gewrappten Werte zugreifen, bedarf es ein wenig Overhead gegenüber der Variante mit null:

val o = valueOf(2)
val v = if (o.isDefined) o.get else sys.error("not defined")

// instead of
val v = valueOf(2)
if (v == null) sys.error("not defined")

Ein klein wenig übersichtlicher wird die Variante mit Option wenn zu Pattern-Matching gegriffen wird:

val v = valueOf(2) match {
  case None => sys.error("not defined")
  case Some(v) => v
}

Aber wirklich was hermachen tut der Code noch nicht. Um die wahre Stärke von Option zu erkennen dürfen wir uns hier tatsächlich nicht mit dem Wert aufhalten, den Option beinhalten könnte. Statt dessen müssen wir Option selbst bzw. dessen Abstraktionsmöglichkeiten betrachten. Oh je, jetzt geht das schon wieder los. Immer diese Abstraktion. Ich werde euch damit aber so lange quälen bis ihr nicht mal mehr im Schlaf daran denkt etwas nicht abstrahiert (in userem Fall: funktional) zu programmieren.

Zuerst sollten wir uns überlegen ob es wirklich notwendig ist, dass wir wissen ob unser Code fehlgeschlagen ist (sprich: es wurde None zurückgegeben) oder ob uns das nicht vollkommen egal sein kann. Tatsächlich dürfte es wohl so sein, dass wir Eingabewerte haben und diese zu Ausgabewerten transformieren wollen. Meistens sieht es doch so aus, dass wir erst in dem Moment in dem wir auf die potenziellen Ausgabewerte auch tatsächlich zugreifen wollen auch wissen müssen ob wir ein zufriedenstellendes Ergebnis erhalten haben oder ob irgendwo ein Fehler aufgetreten ist. Aber müssen wir auch bei der internen Datenverarbeitung tatsächlich immer wissen was für genaue Werte in userem Programm existieren? Überlegen wir uns das mal im Detail:

scala> val xs = List(3, -2, 1, 7, 9, 4) map valueOf
xs: List[Option[String]] = List(Some(are), None, Some(world), None, None, Some(you))

Wir haben eine Liste aus Eingabewerten und wollen diese verarbeiten. Bei einigen der Werten bekommen wir nur ein None zurück, was symbolisieren soll, dass unser Programm nichts mit den Eingabewerten anfangen kann. Noch ist unsere Datenverarbeitung aber nicht abgeschlossen:

scala> xs map (opt => if (opt.isDefined) Some(opt.get+"!") else None)
res3: List[Option[java.lang.String]] = List(Some(are!), None, Some(world!), None, None, Some(you!))

scala> xs map (opt => opt map (str => str+"!"))
res4: List[Option[java.lang.String]] = List(Some(are!), None, Some(world!), None, None, Some(you!))

scala> xs map (_ map (_+"!"))
res5: List[Option[java.lang.String]] = List(Some(are!), None, Some(world!), None, None, Some(you!))

Wir wollen an alle gefundenen Strings ein Ausrufezeichen anhängen, uns aber möglichst nicht weiter um die Datenpakete kümmern, die kein String zurückgegeben haben. Dieses Vorhaben erreichen wir viel besser indem wir abstrahieren, anstatt, wie im ersten Beispiel, jedes einzelne Ergebnis zu betrachten. Option verfügt genau wie die Klassen aus der Collection-Bibliothek über viele nützliche Funktionen höherer Ordnung, die es uns erlauben schnell und komfortabel die gewrappten Inhalte zu transformieren. Das Besondere an diesen Methoden ist, dass sie keine Exceptions werfen wenn es mal keine Daten zu verarbeiten gibt, sondern einfach wieder None zurückgeben bzw. einfach nichts machen. Dieses Verhalten erlaubt es uns ganz normal mit Option zu arbeiten, so wie wenn wir direkt mit den Werten arbeiten würden – alle lästigen null-Abfragen entfallen bzw. werden für uns von der Bibliothek übernommen. Dieses Prinzip kann in einer beliebigen Komplexitätsstufe fortgeführt werden, selbst wenn wir es mit noch so vielen potenziellen null-Werten zu tun bekommen. Wollen wir in obigem Beispiel nun an die tatsächlichen Daten herankommen reicht wieder der Einsatz einer entsprechenden Methode:

scala> val values = xs flatMap (_ map (_ + "!"))
values: List[java.lang.String] = List(are!, world!, you!)

„flatMap“ kann wie „map“ einzelne Werte zu beliebig Anderen mappen. Es kommt aber noch hinzu, dass es alle gemappten Werte auch noch auspackt und sie ohne ihre Containerklasse zur Ausgangs-Collection hinzufügt. Da es bei einem None nichts auszupacken gibt wird in unserem Fall einfach ein Nil an die Liste ergänzt, was keinen weiteren Effekt hat – somit verschwinden urplötzlich alle ungültigen Werte. Es ist genau so wie wenn die ungültigen Werte nie existiert hätten.

Im Folgenden noch ein Beispiel aus der imperativen Programmierwelt, das sich exzessive an null-Werten bedient:

case class Module(id: Int)

case class Context(modules: Map[String, Module])

def getAttribute(data: Int, config: String): String = data -> config match {
  case (1, "context") => "main_context"
  case (_, "context") => "not_defined"
  case (1, "name") => "module_ip"
  case _ => ""
}

def getContext(name: String): Context = name match {
  case "main_context" => Context(Map("module_ip" -> Module(9878624)))
  case _ => null
}

var modules: List[Module] = Nil

def resolve(data: Int) = {
  val contextName = getAttribute(data, "context")
  val name = getAttribute(data, "name")
  val module = {
    val context = getContext(contextName)
    if (context == null) null
    else {
      val result = context.modules.getOrElse(name, null)
      if (result != null) modules ::= result
      result
    }
  }
  if (module == null)
    throw new IllegalArgumentException("module is not defined")
  println(module)
}

Die Methode, auf die wir unser Augenmerk richten wollen, ist „resolve“, die wieder einmal unsere Eingabewerte verarbeiten soll (der Einfachheit halber bestehen diese Daten nur aus einem Int). Zuerst werden verschiedene Attribute geladen, die mit den Daten schon vorher verknüpft wurden. Die Verknüpfungen stehen hier – wieder der Einfachheit halber – hardcodiert im Programm. Als Nächstes soll ein Modul geladen werden, das für die eingegebenen Daten zuständig ist. Nun wird dieses Modul im else-Zweig der Verknüpfung einer Liste hinzugefügt, wenn es denn tatsächlich definiert ist. Zuletzt folgt eine Prüfung ob ein Fehler aufgetreten ist und falls dies nicht der Fall sein sollte wird das Modul weiterverarbeitet, was hier symbolisch durch die Ausgabe auf der Konsole dargestellt wurde.

Natürlich funktioniert das Programm, es ist zum Einen aber sehr hässlich und zum Anderen sind die dauernden null-Abfragen unnötig. Eine einzige Abfrage, die erst ganz zum Schluss (nämlich dann wenn wir wissen wollen ob ein Modul erfolgreich geladen werden konnte) platziert wird, sollte unseren Ansprüchen vollkommen genügen. Betreiben wir also ein wenig Refactoring um einen schöneren Code zu bekommen.

Das Laden der Attribute können wir so lassen wie es ist, da die Rückgabe von ungültigen Werten im restlichen Code jederzeit aufgefangen werden kann. Erst unseren Context wollen wir mit Option absichern, sodass ein potenziell zurückgegebenes null keine Probleme mehr verursachen kann:

scala> val context1 = Option(getContext("main_context"))
context1: Option[Context] = Some(Context(Map(module_ip -> Module(9878624))))

scala> val context2 = Option(getContext("invalid"))
context2: Option[Context] = None

Wir können wieder mit der Methode „map“ den Inhalt des zurückgegebenen Options verarbeiten:

scala> val result = context1 map (_.modules get "module_ip")
result: Option[Option[Module]] = Some(Some(Module(9878624)))

scala> val result = context1 map (_.modules get "")
result: Option[Option[Module]] = Some(None)

scala> val result = context2 map (_.modules get "")
result: Option[Option[Module]] = None

Anstatt der Methode „getOrElse“ von Map, benutzen wir nur „get“, die bereits ein Option zurückgibt. Zwar erhalten wir damit Zugriff auf das Modul, haben dafür aber nun ein Option in einem Option, was ziemlich umständlich für eine etwaige Weiterverarbeitung ist. Benutzen wir doch statt dessen die Methode „flatMap“:

scala> val result = context1 flatMap (_.modules get "module_ip")
result: Option[Module] = Some(Module(9878624))

scala> val result = context1 flatMap (_.modules get "")
result: Option[Module] = None

scala> val result = context2 flatMap (_.modules get "")
result: Option[Module] = None

Nun fehlt nur noch der Teil, bei dem das Modul zu der Liste hinzugefügt werden soll:

result forach (modules ::= _)

Wird „foreach“ auf None aufgerufen, wird die übergebene Funktion nie ausgeführt. Nun können wir ohne weitere Sorgen prüfen ob während all diesen Berechnungen irgendwo ungültige Werte vorlagen:

result match {
  case None => // throw error
  case Some(module) => // use module
}

Dies alles resultiert in einem deutlich übersichtlicheren und vor sehr sicheren Code. Durch Scalas strenges Typsystem brauchen wir uns wenig Sorgen darum machen ob wir die richtigen Methoden auf die richtigen Typen aufrufen und ob all die Typen am Schluss auch zusammenpassen. Würden sie es nicht tun, würde unser Code nicht kompilieren – hätten wir jedoch statt Option böse null-Werte eingesetzt, könnten wir nie sicher sein ob unser Code zur Laufzeit auch tatsächlich funktioniert oder ob nicht doch noch irgendwo noch ein Fehler auftreten kann. Wenn wir zur Datenmanipulation nur auf Funktionen höherer Ordnung zurückgreifen, können wir dagegen schon sehr sicher sein, dass dort außer einem Logikfehler keine weiteren Leichtsinnsfehler mehr auftreten können.

Bauen wir die einzelnen Codeteile nun zusammen, erhalten wir folgenden Code:

def resolve(data: Int) {
  val contextName = getAttribute(data, "context")
  val name = getAttribute(data, "name")
  val context = Option(getContext(contextName))
  val result = context flatMap (_.modules get name)
  result foreach (modules ::= _)
  result match {
    case None =>
      throw new IllegalArgumentException("module is not defined")
    case Some(module) =>
      println(module)
  }
}

Je nach dem was für Aufgaben von der foreach-Methode und dem Pattern-Matching ausgeführt werden müssen, besteht auch die Möglichkeit die beiden Teile zusammenzulagern (das Hinzufügen des Moduls zur Liste könnte z.B. auch im Pattern-Matching erledigt werden).

Gehen wir den Code nun noch einmal in Ruhe durch und überlegen uns was denn dazu geführt hat, dass er entstanden ist. Wir haben Schrittweise eine Transformation nach der anderen durchgeführt, bis wir am Ende das Ergebnis bekommen haben, das wir erhalten wollten. Das Aufteilen eines Algorithmus in einzelne Teilaufgaben und die danach folgende mehr oder weniger sequentielle Ausführung jener Teilaufgaben ist typisch für das funktionale Programmieren. Man findet hier wenig Code, der einzelne Aufgaben wild durcheinander ausführt, wie es bei imperativen Sprachen sehr oft der Fall ist. Diese Strukturierung wird hauptsächlich ermöglicht durch ein mächtiges Typsystem, durch Closures und durch umfangreiche Bibliotheken, die es nicht weiter erforderlich machen, dass man immer wieder das Rad neu erfindet und jede noch so kleine Funktion immer wieder neu implementiert. Strukturierung führt letztendlich zu Abstraktion, da viel öfter beschrieben wird was getan werden soll anstatt wie es getan werden soll.

Es wird am Anfang eine gewisse Zeit dauern bis man sich an die angebotenen Abstraktionen gewöhtn hat und bis man gelernt hat wie man sie richtig einsetzen kann. Ist dieser Zeitpunkt aber erst einmal gekommen möchte man diese Abstraktionen nicht mehr missen.

Either

Der Einsatz von Option bietet sich an wenn man sich im Fehlerfall nicht weiter um den Fehler kümmern möchte, aber was wenn man den Fehler doch noch benötigen sollte? In diesem Fall ist es ratsam auf Either zurückzugreifen. Im Gegensatz zu Option kann Either nicht nur einen, sondern ganze zwei Typen annehmen – einen für das erwartete Ergebnis und einen für einen eventuellen Fehler.

def calc(i: Int): Either[String, Int] =
  if (i < 0) Left("i is negative")
  else if (i < 10) Left("i is too small")
  else Right(i*i)

scala> calc(-1)
res0: Either[String,Int] = Left(i is negative)

scala> calc(12)
res1: Either[String,Int] = Right(144)

Die beiden Typen heißen – vollkommen unspektakulär – Left und Right. Da beide Typen beliebig gewählt werden können ist es im Grunde genommen egal ob die rechte oder die linke Seite den Fehlertyp repräsentiert. Es hat sich jedoch die Konvention eingebürgert, dass die linke Seite den Fehlertyp repräsentieren soll und wenn man keine Verwirrungen erzeugen möchte, sollte man sich auch an daran halten. Mit Either geht es erst einmal wenig spektakulär weiter:

def get(i: Int) = calc(i) match {
  case Left(s) => println(s); 0
  case Right(i) => i-5
}

scala> get(3)
i is too small
res35: Int = 0

scala> get(15)
res36: Int = 220

Wieder einmal kommen wir über Pattern-Matching an die internen Werte heran. Das war es aber auch schon fast, denn wenn wir in die API von Either gucken, finden wir dort nur zwei jämmerliche Methoden, mit denen wir noch einigermaßen idiomatisch auf unsere Werte zugreifen können. Dies wäre zum Einen „fold“ und zum Anderen „join“:

scala> calc(3).fold(err => "error: "+err, succ => succ.toString)
res40: String = error: i is too small

scala> calc(11).fold(err => "error: "+err, succ => succ.toString)
res41: String = 121

scala> calc(3).fold(identity, succ => succ.toString)
res44: String = i is too small

Dieses „fold“ ist mit „map“ von Option vergleichbar – nur mit dem Unteschied, dass auch für den Fehlerfall angegeben werden muss was getan werden soll. Möchte man eine der beiden Seiten nicht verändern, bietet sich der Einsatz der Identitätsfunktion an, wie im dritten Beispiel gezeigt. Die Methode „join“ liegt für beide Seiten jeweils einmal vor:

scala> val e: Either[Either[String, Int], Int] = Left(Left("error"))
e: Either[Either[String,Int],Int] = Left(Left(error))

scala> e.joinLeft
res7: Either[String,Int] = Left(error)

scala> val e: Either[String, Either[String, Int]] = Right(Right(3))
e: Either[String,Either[String,Int]] = Right(Right(3))

scala> e.joinRight
res8: Either[String,Int] = Right(3)

scala> val e: Either[String, Either[String, Int]] = Right(Left("error"))
e: Either[String,Either[String,Int]] = Right(Left(error))

scala> e.joinRight
res11: Either[String,Int] = Left(error)

scala> e.joinLeft
<console>:9: error: Cannot prove that String <:< Either[C,Either[String,Int]].
              e.joinLeft
                ^

Die Funktionsweise ist an „flatMap“ angelehnt, nur dass es kein „map“ gibt. Das innere Either wird entpackt und zurückgegeben. Dabei muss man nur aufpassen, dass man die richtige Methode aufruft – das ist immer die, die den gleichen Namen (mit dem Präfix „join“ davor) wie das äußere Either hat. Ruft man die Falsche auf, bekommt man einen unschönen Typfehler, der „übersetzt“ so viel bedeutet wie, dass der Compiler festgestellt hat, dass ein String kein Subtyp (<:<) von Either ist. Wie der Fehler genau zu Stande kommt soll uns hier erst einmal egal sein. Es ist schnell zu erkennen, dass diese Methoden lange nicht so praktisch sind wie die von Option – was dem Problem zu verdanken ist, dass man auf beide Seiten gleichermaßen zugreifen können muss.

Dennoch besteht die Möglichkeit jeweils eine der Seiten zu ändern – dafür muss man sich nur den beiden Methoden „left“ und „right“ bedienen, die jeweils nochmal einen Wrapper zurückgeben. Dieser wrappt dabei den kompletten Either und erlaubt somit mit der von Option bereits bekannten Abstraktionsstufe zu operieren:

scala> val e = calc(11)
e: Either[String,Int] = Right(121)

scala> e.left.map(_*2)
res23: Either[String,Int] with Product with Serializable = Right(121)

scala> e.right.map(_*2)
res24: Either[String,Int] with Product with Serializable = Right(242)

Eine Projektion arbeitet immer nur mit einer Seite – wollen wir also die rechte Seite manipulieren, benötigen wir auch eine „RightProjection“. Die Projektion gibt dabei wieder ein Either zurück, weshalb wir für jeden weiteren Transformationsschritt wiederum eine neue Projektion erschaffen müssen. Either eignet sich besonders gut wenn man eventuelle Fehlermeldungen stacken möchte, damit man sie gebündelt an den Aufrufer zurückgeben kann. Schauen wir uns mal wie wir das erreichen können. Zuerst passen wir unsere calc-Methode minimal an:

def calc(i: Int): Either[String, Int] =
  if (i < 0) Left("value is negative")
  else if (i < 10) Left("value is too small")
  else Right(i*i)

Nun benötigen wir noch ein paar Eingabewerte, die wir in unsere Methode einspeisen können:

scala> val calculations = List(-1, 15, 3, 11, 7) map calc
calculations: List[Either[String,Int]] = List(Left(value is negative), Right(225), Left(value is too small), Right(121), Left(value is too small))

Da es sehr viele Eingabewerte geben kann, wollen wir dem Aufrufer die Möglichkeit geben, schnell herauszufinden welche der Daten einen Fehler verursacht haben:

scala> :paste
// Entering paste mode (ctrl-D to finish)

val mappings = calculations.zipWithIndex map {
  case (calc, i) => calc.left map ("error at position "+i+": "+_)
}

// Exiting paste mode, now interpreting.

mappings: List[Either[String,Int] with Product with Serializable] = List(Left(error at position 0: value is negative), Right(225), Left(error at position 2: value is too small), Right(121), Left(error at position 4: value is too small))

Wir müssen die berechneten Werte nur mit ihrem Index verknüpfen und dann bei jedem Left die Fehlermeldung ein wenig anpassen. Nun können wir uns alle Fehlermeldungen heraussuchen:

scala> val errors = mappings collect { case Left(e) => e }
errors: List[String] = List(error at position 0: value is negative, error at position 2: value is too small, error at position 4: value is too small)

Zu guter Letzt müssen wir noch herausbekommen ob überhaupt ein Fehler aufgetreten ist. Dazu genügt eine kleine Abfrage:

if (errors.isEmpty) Right(calculations map { case Right(i) => i })
else Left(errors)

Gab es keinen Fehler, wissen wir automatisch, dass alle Werte in „calculations“ ein Right sind – es genügt also diese über ein „map“ zu entpacken. Würden wir dieses Wissen nicht haben, müssten wir auf „collect“ zurückgreifen, wie im vorherigen Beispiel gezeigt, da wir sonst einen Match-Error bekommen würden. Alles in allem wollen wir diesen Code natürlich mehrmals aufrufen können. Fassen wir ihn also in einer Methode zusammen:

def calcValues(xs: List[Int]): Either[List[String], List[Int]] = {
  val calculations = xs map calc
  val mappings = calculations.zipWithIndex map {
    case (calc, i) => calc.left map ("error at position "+i+": "+_)
  }
  val errors = mappings collect { case Left(e) => e }
  if (errors.isEmpty) Right(calculations map { case Right(i) => i })
  else Left(errors)
}

scala> calcValues(List(-1, 15, 3, 11, 7))
res44: Either[List[String],List[Int]] = Left(List(error at position 0: value is negative, error at position 2: value is too small, error at position 4: value is too small))

scala> calcValues(List(15, 11))
res45: Either[List[String],List[Int]] = Right(List(225, 121))

Ein Aufrufer muss nun nur noch den Rückgabewert prüfen, was komfortabel über Pattern-Matching geht. Dieser Code zeigt deutlich, genau wie das Beispiel mit Option, dass abstrahiertes Programmieren uns viel Arbeit ersparen kann. Innerhalb von „calcValues“ brauchen wir uns niemals Gedanken darum machen ob nun irgendwo ein Fehler aufgetreten ist. Hätten wir statt auf Either auf Exceptions gesetzt, hätten wir auch überall hässliche try-catch-Expressions einbauen müssen, die den Code viel unübersichtlicher und schwerer wartbar gemacht hätten.

Zusammenfassung

Pattern-Matching, Lambdas, Typinferenz und eine mächtige Bibliothek, die viele Funktionen höherer Ordung anbietet, bilden ein mächtiges Gespann, das richtig eingesetzt der imperativen Denkweise um ein vielfaches überlegen ist. Ich hoffe, dass ich es geschafft habe, euch die funktionale Sichtweise auf Abstraktionen nochmals ein ganzes Stück näher zu bringen. Ich möchte euch noch ein paar Regeln mit auf den Weg geben, die euch helfen sollen euch an die Abstraktionen zu gewöhnen:

  • Versucht unter allen Umständen „null“ zu vermeiden.
  • Versucht bei Option und Either nur dann Pattern-Matching einzusetzen, wenn ihr auch wirklich auf die beinhalteten Werte zugreifen müsst. In der Regel ist das erst ganz am Ende der Datenverarbeitung der Fall.
  • Vermeidet bei Option und den Projektionen von Either den Aufruf von „get“ (und die meistens vorhergehenden Aufrufe von „isDefined“, „isRight“ oder „isLeft“). Benutzt statt dessen Funktionen höherer Ordung um auf die Werte zugreifen zu können.
  • Benutzt Either als Ersatz von Exceptions wenn irgendwie möglich.
  • Beim Arbeiten mit Either sind die Projektionen der weitaus wichtigere Teil – das Either selbst ist für nicht viel mehr als zum Pattern-Matching zu gebrauchen.

Die obigen Punkte sind natürlich keinesfalls so zu verstehen, dass sie immer und unter allen Umständen eingehalten werden müssen – sie bilden mehr ein Design-Pattern, bei dessen Einhaltung man Fehler durch die Entwicklung von besserem Code vermeidet. Manchmal kann es sinnvoll sein, dass man auf diese Design-Pattern verzichtet. Das ist vor allem dann der Fall wenn man von Scala aus imperativ entwickelte Java-Bibliotheken ansteuern möchte oder wenn man hocheffizienten Code benötigt, der nur imperativ geschrieben auch wirklich effizient ist. Diese Fälle treten in der Regel aber nur selten auf und generell gilt: Wenn man nicht entscheiden kann ob man imperativ programmieren muss, dann muss man es auch nicht. Daraus folgt, dass man sich an die obigen Punkte dann auch halten sollte.

Einige Schwierigkeiten, die beim Vermeiden von Abstraktionen entstehen, bekommt man durch die bereits angesprochenen Exceptions (Ich hoffe, dass die Argumente gegen sie beim Lesen des Kapitels rübergekommen sind). Auch das manuelle Heraussuchen von entsprechenden Werten aus Collections wäre eine mühselige Angelegenheit und hätte der Übersichtlichkeit wegen in weitere Methoden ausgelagert werden müssen. Vor allem fehlende Typinferenz wäre oftmals ein K.O.-Kriterium für den Einsatz von Either oder Option. Sollten diese nämlich einmal geschachtelt auftauchen und dann auch noch mit einem parametrisierten Typen als Inhalt müsste man Typen notieren, die jeden Code im Typchaos versinken lassen würden.

Zu Excepitons lässt sich noch sagen, dass wenn man mal tatsächlich mit ihnen arbeiten muss, man noch immer auf Scalas skalierbare Snytax zurückgreifen kann um sie sich vom Hals zu halten:

def catchable[A](f: => A): Either[Exception, A] =
  try Right(f) catch { case e: Exception => Left(e) }
  
scala> catchable("987".toInt)
res49: Either[Exception,Int] = Right(987)

scala> catchable("98s7".toInt)
res50: Either[Exception,Int] = Left(java.lang.NumberFormatException: For input string: "98s7")

Vor allem wenn geschweifte Klammern eingesetzt werden, sieht der Code tatsächlich so aus, wie wenn man eine in die Sprache schon eingebaute Kontrollstruktur benuzten würde:

val reslut = catchable {
  // do heavy calculation here
  // return some value
}

Als Hilfestellung beim Einsatz von Option bietet sich außerdem die Lektüre folgenden Artikels an, der die in Option eingebauten Funktionen höherer Ordnung aufschlüsselt und zeigt, was für ein Pattern-Matching Konstrukt man statt dessen nutzen müsste: scala.Option Cheat Sheet

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.

Teil 14.1: Varianzen

Mit Varianzen können Aussagen darüber gemacht werden ob die Vererbungshierarchie eines parametrisierten Typs auf eine generische Klasse übertragen werden soll. Das Hauptaugenmerk liegt dabei auf der Frage ob eine generische Klasse mit einem Typ Foo, der Untertyp von Bar ist (Foo <: Bar), auch ein Untertyp der selben generischen Klasse mit einem Typ Bar ist (GenClass[Foo] <: GenClass[Bar]).

Gehen wir einmal davon aus, dass obige Aussage zutreffen würde, dann müsste folgender Code korrekt kompilieren:

val xs: Array[Any] = Array[Int](18)
xs(0) = "hello"

Int ist ein Untertyp von Any (Int <: Any), also trifft dies auch auf die Arrays zu (Array[Int] <: Array[Any]). Da String <: Any gilt wird folglich auch die Zuweisung in der nächsten Zeile korrekt kompilieren. Sobald dieser Code jedoch ausgeführt werden würde, würden wir eine Exception bekommen, da ein String nicht in einem Int-Array abgespeichert werden kann (type-erasure gilt nicht für Arrays!).

Dies ist ein gefährlicher Fehler, vor dem uns der Scala-Compiler aber vortrefflich schützt – obiger Code würde nicht kompilieren:

scala> val xs: Array[Any] = Array[Int](18)
<console>:7: error: type mismatch;
 found   : Array[Int]
 required: Array[Any]
Note: Int <: Any, but class Array is invariant in type T.
You may wish to investigate a wildcard type such as `_ <: Any`. (SLS 3.2.10)
       val xs: Array[Any] = Array[Int](18)
                                      ^

Bei List bekommen wir diesen Fehler nicht:

scala> val xs: List[Any] = List[Int](18)
xs: List[Any] = List(18)

Der Grund, warum die Varianz der Liste nicht so funktioniert wie bei Arrays, liegt in der Unveränderlichkeit. Die Elemente einer List lassen sich nach ihrer Erstellung nicht mehr verändern, die von Array dagegen schon. Der Compiler schützt uns also davor, Schabernack mit veränderlichen Objekten zu machen.

Invarianz

Es gibt drei verschiedene Arten von Varianzen. Die Invarianz, die die Standardvarianz in Scala ist, wollen wir uns als erstes anschauen. Immer dann, wenn wir einen generischen Parameter ohne weitere Kennzeichnung erstellen, erstellen wir einen invarianten parametrisierten Typ.

Invarianz bedeutet, dass sich der Beziehungsstatus von parametrisierten Typen nicht auf die generischen Klassen überträgt. Es gilt:

A <: B => keine Beziehung zwischen C[A] und C[B]

Arrays sind in Scala wegen ihrer Veränderlichkeit invariant. Es ist uns also nicht möglich ein Array vom Typ Int auf ein Array vom Typ Any zu mappen. obwohl Int <: Any.

Wir können das invariante Verhalten von Array leicht nachbauen:

scala> case class Box[A](var a: A)
defined class Box

scala> val b1 = Box(9)
b1: Box[Int] = Box(9)

scala> val b2: Box[Any] = b1
:13: error: type mismatch;
 found   : Box[Int]
 required: Box[Any]
Note: Int You may wish to define A as +A instead. (SLS 4.5)
       val b2: Box[Any] = b1
                          ^

Kovarianz

Die zweite mögliche Form ist die Kovarianz, die es uns erlaubt den Beziehungsstatus von Typen, ganz im Gegensatz zur Invarianz, auf die generischen Klassen zu übertragen. Es gilt:

A <: B => C[A] <: C[B]

Ein Beispiel für eine invariante Datenstruktur in Scala ist List. Die Beziehung lautet List[Int] <: List[Any], da Int <: Any. Wir können unsere eigenen invarianten Datentypen erstellen, indem wir der Typisierung ein + voranstellen:

scala> case class Box[+A](a: A)
defined class Box

scala> val b: Box[Any] = Box[Int](8)
b: Box[Any] = Box(8)

Versuchen wir nun unseren Typ veränderlich zu machen, beschwert sich sofort wieder der Compiler:

scala> case class Box[+A](var a: A)
:10: error: covariant type A occurs in contravariant position in type A of value a_=
       case class Box[+A](var a: A)
                  ^

Falls dieser Code kompilieren würde, wäre nicht sicher gestellt, dass Box auch nur den Typ aufnimmt, für den es bestimmt wurde:

// does not compile
val b: Box[Any] = Box[Int](9)
b.a = "hello"

Kontravarianz

Die letzte mögliche Variante ist die Kontravarianz. Sie funktioniert genau verkehrt herum wie die Kovarianz. Es gilt:

A <: B => C[B] <: C[A]

Kontravarianz wird sehr selten eingesetzt, da es im Grunde nicht viele Anwendungsfälle dafür gibt. Ein Beispiel wäre z.B. das Folgende:

class Foo[-A] {
  def bar(a: A): Int =
    sys.error("unimplemented")
}

scala> val base = new Foo[Any]
base: Foo[Any] = Foo@e18a9e8

scala> val derived: Foo[Int] = base
derived: Foo[Int] = Foo@e18a9e8

Zu Recht stellt man sich am Anfang die Frage warum ein Foo[Any] als Foo[Int] angesprochen werden kann, schließlich ist Int <: Any. Schauen wir uns also ein paar weitere Beispiele an um die Unterschiede zwischen den einzelnen Varianzen stärker hervorzuheben.

Anwendungsfälle

Zur Invarianz sollte es nichts mehr zu sagen geben. Alle veränderlichen parametrisierten Typen sind invariant, da es sonst möglich wäre sie mit einem ungültigen Typ zu überschreiben. Bitte beachtet, dass es einen Unterschied zwischen

val xs: Array[Any] = Array(3)

und

val xs: Array[Any] = Array[Int](3)

gibt. Nur die erste Variante würde erfolgreich kompilieren, die zweite würde aufgrund des invarianten Arrays eine Fehlermeldung verursachen. Dank Scalas Typinferenz erstellt der Compiler im ersten Beispiel ein Array[Any], weist diesem aber ein Int zu. Dies funktioniert ohne Probleme, da Int <: Any. Im zweiten Beispiel würde ein Array[Int] erzeugt werden, das als Array[Any] betrachtet werden soll – das ist verboten.

Mit der Kovarianz können wir schon deutlich mehr anstellen. Das Beispiel mit List[Int] <: List[Any] wurde schon genannt. Die Frage ist jetzt nur was für einen konkreten Vorteil man davon hat eine List[Int] als List[Any] anzusprechen. Um diese Frage zu klären schauen wir uns folgenden Code an:

// does not compile

abstract class Animal
class Cow extends Animal
class Pig extends Animal

class Farm {
  
  private val cows = new Array[Cow](3)
  
  cows(0) = new Cow
  cows(1) = new Cow
  
  def animals: Array[Animal] = cows // type mismatch
}

Auf einem Bauernhof werden verschiedenen Tiere verwaltet. Intern können die Tiere korrekt angesprochen werden. Von außerhalb des Hofes wollen wir aber nicht, dass irgendjemand eines der Tiere direkt ansprechen kann, weshalb wir nur die Information weitergeben, dass zwar Tiere vorhanden sind, aber nicht welche genau. Falls dieser Code kompilieren würde, könnte jetzt jemand von außerhalb einfach so ein Schwein auf einen Bauernhof mit lauter Kühen platzieren, was aber nicht funktionieren darf, da z.B. keine Nahrung für Schweine vorhanden ist.

Ändern wir das Array zu einer List würde der Code erfolgreich kompilieren.

class Farm {
  
  private var cows = List.empty[Cow]
  
  cows :+= new Cow
  cows :+= new Cow
  
  def animals: List[Animal] = cows
}

Da List nicht veränderlich ist, würde unserem Kühe-Bauernhof auch nichts passieren wenn er durch Schweine ergänzt werden würde. Schließlich würden dadurch alle Tiere geklont werden und könnten auf einem neuen Bauernhof platziert werden – der alte Bauernhof bleibt unangetastet.

Vereinfacht gesagt erzeugt Kovarianz read-only-Datenstrukturen. Deren Daten können zwar jederzeit abgerufen aber nie verändert werden. Die Kontravarianz dagegen macht das genaue Gegenteil. Sie erzeugt write-only-Datenstrukturen. Schauen wir uns an wofür das nützlich ist:

// P = parameter value; R = return value
abstract class AnimalTransformator[-P, +R] {
  def apply(p: P): R
}

val animal2cow = new AnimalTransformator[Animal, Cow] {
  def apply(p: Animal) = /* a lot of magic here */ new Cow
}

val pig2animal: AnimalTransformator[Pig, Animal] = /* also a lot of magic here */ animal2cow

Es existieren magische Geräte, die Tiere in andere Tiere verwandeln können. Welche Tiere dabei herauskommen ist nicht immer festzustellen. Eines dieser Geräte (animal2cow) erzeugt jedoch immer eine Kuh, egal was für ein Tier es als Eingabe erhält. Ein anderes Gerät (pig2animal) erzeugt aus einem Schwein irgendein Tier. Wenn letzteres Gerät nun sein Schwein an das erste Gerät weiterreicht und dessen Kuh entgegen nimmt, dann wäre das kein Verstoß seiner Funktionsweise, da Pig <: Animal und Cow <: Animal. Das erste Gerät kann immer ein Schwein entgegen nehmen, das zweite dagegen immer eine Kuh. In Scala funktioniert das aber nur wenn wir P als kontravariant und R als kovariant markieren.

Gut, das Beispiel war jetzt sehr an den Haaren herbeigezogen, man sollte daran aber auch die Funktionsweise des Leseschutzes erkennen können. Folgender Code würde nämlich nicht funktionieren:

// in AnimalTransformator
def clone(p: P): P

// signature in our case
// clone(Animal): Animal

Diese Methode würde ein Tier klonen, was auch funktionieren darf. Das Klonen könnte theoretisch aber auch schief gehen, was zur Folge hätte, dass z.B. ein unsichtbarer Klon erzeugt werden würde. Was machen wir dann? Wir könnten nicht herausbekommen ob das Tier geklont oder fälschlicherweise transformiert wurde. Ein Tier als Eingabe würde auch ein Tier als Ausgabe produzieren – so ist unsere Spezifikation. Wir könnten unser Tier als Tier ansprechen, aber eben nicht als irgendeine Spezialisierung – der Leseschutz offenbart sich also als Hilfe, die uns daran hindert, eine Kuh als Schwein zu betrachten.

Als kleine Merkhilfe kann die Position eines Typs dienen. Parameter von Methoden können kontravariant, jedoch nie kovariant sein. Die Rückgabewerte dürfen dagegen nie kontravariant sein. Warum das so ist solltet ihr aufgrund den obigen Erklärungen nun verstanden haben. Falls dem noch nicht so ist, geht die Beispiele noch einmal durch, baut euch eure eigene Beispiele und überlegt nochmal, was passieren würde wenn kovariante Parametertypen und kontravariante Rückgabetypen erlaubt wären.

Ausnahmefälle

Mit Collections gibt es einen schönen Anwendungsfall, bei dem wir kovariante Typen benötigen, diese aber auch als Parameter verwenden müssen. Nehmen wir als Collection-Beispiel die altbekannte List von der wir schon im Kapitel über Extraktoren eine eigene Implementierung geschrieben haben. Diese wollen wir nun zu einer generischen Liste ausbauen, damit wir sie für alle Typen nutzen können und nicht nur für Int. Damit wir keine Namensprobleme mit der Liste aus den Scala-Collections bekommen, werden wir einen anderen Namen wählen:

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

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

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

Die einzige Neuerung sollte in diesem Codebeispiel der Typ „Nothing“ sein. Nothing ist ein Untertyp jedes anderen Typs (A => Nothing <: A) und kann somit als Typisierung der List verwendet werden. Einem object können wir keinen Typparameter mitgeben, weshalb wir auf Nothing angewiesen sind.

Einziges Problem ist jetzt die Erstellung einer geeigneten Liste:

scala> val xs = 1 :: 2 :: 3 :: LNil
<console>:13: error: type mismatch;
 found   : x$1.type (with underlying type Int)
 required: Nothing
       val xs = 1 :: 2 :: 3 :: LNil
                            ^

Unsere List ist invariant, weshalb der Compiler es nicht akzeptiert eine LinkedList[Nothing] an eine LinkedList[Int] zu hängen, obwohl Nothing <: Int. Führen wir also Kovarianz ein:

abstract class LinkedList[+A] { ... }

Leider taucht nun eine weitere Fehlermeldung auf:

<console>:19: error: covariant type A occurs in contravariant position in type A of value a
         def :: (a: A): LinkedList[A] =
                 ^

Ein kovarianter Paramertyp – das geht verständlicherweise nicht. Aber was machen wir da jetzt? Die Lösung liegt in der Benutzung eines weiteren Typparameters:

// in class LinkedList
def :: [B >: A](b: B): LinkedList[B] =
  new ::(b, this)

Die Bedeutung dieses Konstrukts zu verstehen ist jetzt auch nicht mehr viel komplizierter als der Rest von Varianzen. Unser Ausgangspunkt zur Erstellung einer LinkedList ist LNil. Dieses Objekt ist mit Nothing parametrisiert. Die Typsignatur der Methodenaufrufe würde also so aussehen:

LinkedList[Nothing].::(Int).::(Int).::(Int): LinkedList[Int]

Um von einer LinkedList[Nothing] zu einer LinkedList[Int] zu kommen benötigt es einem Lower-Bound (B >: A => Int >: Nothing). Nichts anderes sagt der zusätzliche Parameter in der Konkatenations-Methode aus, die eine LinkedList mit dem höherwertigen Typ zurück gibt.

Ich denke, dass es angebracht ist euch an dieser Stelle zu beruhigen. Falls ihr bisher noch nie mit Varianzen zu tun hattet, dann werdet ihr ihre praktische Bedeutung vermutlich nicht vollständig verstanden haben (wenn ihr überhaupt irgendetwas verstanden habt ;)). Varianzen gehören aber nun mal zur Typ-Theorie dazu, weshalb man sich damit früher oder später beschäftigen sollte. Falls euch das alles also ein wenig zu kompliziert war, dann kommt zu einem späteren Zeitpunkt darauf zurück.

Teil 14: Generische Typen

Dieser Artikel ist eigentlich schon längst überfällig, doch musste ich ihn immer wieder zurückstellen, da andere Themen zuerst erklärt werden wollten. Generische Typen haben wir schon zu Genüge kennen gelernt, wir finden sie z.B. bei Collections:

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

scala> List[String]("foo", "bar")
res1: List[String] = List(foo, bar)

In diesem Fall wird auch von einem parametrisierten Typ gesprochen. Ein parametrisierter Typ kann ein Typ sein über den man zur Zeit der Codeentwicklung noch nicht Bescheid weiß. Er kann beliebige Typen repräsentieren und ermöglicht uns wiederverwendbaren Code zu schreiben. In obigem Beispiel können wir unsere Liste z.B. mit Ints oder mit Strings kreieren. Der Typparameter wird in Scala durch eckige Klammern repräsentiert und steht immer vor runden oder geschweiften Klammern. Nach dem Typparameter kann z.B. ein Konstruktoraufruf, eine Parameterliste oder eine Blockdefinition kommen. Dank Scalas Typinferenz müssen wir die Typparameter unserer Objekte jedoch nur selten notieren. Typen, die einen oder mehrere Typparameter besitzen, werden auch als generische Typen bezeichnet. Wie an obigem Codebeispiel zu erkennen gibt uns die REPL die Typparameter nur am statischen Typ, nicht jedoch am Runtime-Typ aus. Das liegt daran, dass Scala der „type erasure“ der JVM unterliegt, die besagt, dass alle Informationen zu Typparametern zur Laufzeit nicht mehr vorhanden sind. Die JVM ersetzt alle Typparameter durch Object, dem Typ, dem alle Objekte auf der JVM unterliegen. Zur Laufzeit ist eine List[Int] also identisch mit einer List[String], da sie beide nur noch als List[Object] repräsentiert werden. Wirklich stören tut die „type erasure“ der JVM aber selten, da der Scala-Compiler dafür sorgt, dass wir überall auch die richtigen Typen einsetzen. Natürlich gibt es auch Anwendungsfälle, bei denen es schön wäre, wenn die Typinformationen zur Laufzeit vorhanden wäre. Scala stellt uns hierfür aber ein paar „Tricks“ zur Verfügung, mit denen wir uns in einem solchen Fall weiterhelfen können, aber dazu später mehr.

Fangen wir damit an unseren eigenen Code mit Typparametern zu schreiben.

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

Bisher haben wir unseren Code meistens auf Basis von List[Int] geschrieben. Mit obigem Code ändert sich das. Die Methode erwartet nun eine List[A]. A steht als Platzhalter für irgendeinen Typ, der uns jetzt noch nicht bekannt ist. Da es den Typ A aber noch nicht gibt müssen wir ihn irgendwo definieren – in Scala tun wir dies indem wir ihn in eckigen Klammern nach dem Methodennamen schreiben. Damit erzeugen wir für den Gültigkeitsbereich der Methode eben jenen Typparameter und können ihn fortan verwenden. Wir müssen im Folgenden nur dafür Sorge tragen, dass wir den definierten Typ überall dort verwenden wo wir ansonsten einen konkreten Typ (wie Int oder String) notiert hätten. Haben wir alles richtig gemacht, sollte unser Code für jegliche Listen funktionieren:

scala> size(List(1,2,3))
res0: Int = 3

scala> size(List('a','b'))
res1: Int = 2

Der Compiler sucht für uns alle Vorkommnisse von A heraus und füllt die benötigten Typen ein. Das macht sich dann bemerkbar wenn wir einen generischen Rückgabetyp definieren:

def reverse[A](xs: List[A]): List[A] = {
  def loop(xs: List[A], ys: List[A]): List[A] =
    if (xs.isEmpty) ys else loop(xs.tail, xs.head :: ys)
  loop(xs, Nil)
}

scala> reverse(List(1, 2, 3))
res4: List[Int] = List(3, 2, 1)

scala> reverse(List("a", "b", "c"))
res5: List[java.lang.String] = List(c, b, a)

Wie unschwer zu erkennen, besitzt die zurückgegebene Liste immer den richtigen Typparameter. Der Name des Typparameters ist im Übrigen frei wählbar. Eingebürgert hat sich aber, dass ein ein einzelner großer Buchstabe verwendet wird, beginnend mit A. Je nach dem in welchem Kontext der Typ benutzt wird, sieht man auch oft mehrere Zeichen umfassende Symbole, wie CC für Collection oder Ret für einen Rückgabetyp. Wollen wir mehr als einen Typparameter haben, so müssen wir diese durch ein Komma trennen:

def print[A, B](a: A, b: B) {
  println(a)
  println(b)
}

scala> print(5, "hello")
5
hello

Nach der gleichen Vorgehensweise wie bei Methoden können wir auch Klassen mit Typparametern versehen:

scala> case class Box[A](a: A)
defined class Box

scala> Box(3)
res0: Box[Int] = Box(3)

scala> Box("Hello")
res1: Box[java.lang.String] = Box(Hello)

Type bounds

Manchmal wollen wir aber keinen Code für beliebige Typen schreiben, sondern Code für Typen mit einer bestimmten Eigenschaft. Die Frage ist jetzt nur was eine solche Eigenschaft sein könnte. Wie wäre es wenn wir die Objekte eines Typs miteinander vergleichen könnten? Der Compiler ist so freundlich und implementiert uns für Fallklassen die equals-Methode:

scala> Box(3) == Box(3)
res4: Boolean = true

scala> Box(3) == Box(7)
res5: Boolean = false

Bei den größer- und kleiner-Methoden sieht es da schon schlechter aus:

scala> Box(3) < Box(9)
<console>:10: error: value < is not a member of Box[Int]
              Box(3) < Box(9)
                     ^

scala> Box(3) > Box(9)
<console>:10: error: value > is not a member of Box[Int]
              Box(3) > Box(9)
                     ^

Das ist auch der Grund weshalb sich die Objekte nicht sortieren lassen, da sie einfach keine Wertigkeit besitzen:

scala> import collection.immutable._
import collection.immutable._

scala> SortedSet(Box(3), Box(9))
:13: error: No implicit Ordering defined for Box[Int].
              SortedSet(Box(3), Box(9))
                       ^

Die Fehlermeldung des Compilers gibt uns den Hinweis, dass wir eine Sortierungsmöglichkeit noch einbauen müssen. In Scala sieht die Standardvorgehensweise dafür so aus, dass die zu sortierende Klasse den Typ „Ordered“ implementieren müssen:

scala> case class IntBox(i: Int) extends Ordered[IntBox]
:12: error: class IntBox needs to be abstract, since method compare in trait Ordered of type (that: IntBox)Int is not defined
       case class IntBox(i: Int) extends Ordered[IntBox]
                  ^

Ordering definiert eine Methode namens „compare“, die wir noch implementieren müssen:

case class IntBox(i: Int) extends Ordered[IntBox] {
  def compare(x: IntBox) =
    this.i-x.i
}

scala> SortedSet(IntBox(3), IntBox(9), IntBox(1))
res18: scala.collection.immutable.SortedSet[IntBox] = TreeSet(IntBox(1), IntBox(3), IntBox(9))

scala> IntBox(7) < IntBox(3) res19: Boolean = false scala> IntBox(7) > IntBox(3)
res20: Boolean = true

scala> IntBox(3) >= IntBox(3)
res21: Boolean = true

Das Verhalten ist genau so wie wir es erwarten. Ordered definiert alle Vergleichsmethoden, die es in Scala gibt. Wir müssen uns nur noch darum kümmern, dass die Vergleichsmethoden auch richtig arbeiten was durch durch die Implementierung der compare-Methode sicher stellen können. Die Parametrisierung von Ordered bestimmt den Typ des Parameters den die compare-Methode erwartet. Wer wissen möchte wie Ordered genau funktioniert, kann in dessen Sourcen gucken.

Euch dürfte aufgefallen sein, dass ich im letzten Beispiel keine parametrisierte Box benutzt habe. Ich hätte es gerne getan, nur leider besitzt ein generischer Typ keine Subtraktionsmethode, mit deren Hilfe wir die Wertigkeit des Objekts errechnen könnten. In Scala gibt es einen weiteren Type namens „Ordering“, der es uns erlaubt eine Wertigkeit auch für parametrisierte Typen anzugeben. Um Ordering korrekt benutzen zu können benötigt ihr aber noch ein wenig mehr Wissen über Scalas implizite Typen. Da das aber Stoff für ein weiteres Kapitel ist, werden wir uns hier nicht weiter mit Ordering befassen. Die einzigen, die wir auf einen parametrisierten Typ aufrufen können, sind die, die wir auch auf den Typ Object aufrufen können. Es besteht also die Möglichkeit, dass wir den Hash-Code miteinander vergleichen:

case class Box[A](a: A) extends Ordered[A] {
  def compare(a: A) =
    this.hashCode-a.hashCode
}

Diese Lösung erfordert aber eine korrekt implementierte hashCode-Methode und sollte daher nicht immer das erste Mittel der Wahl sein.

Kommen wir lieber wieder zu den Eigenschaften zurück, die wir den parametrisierten Typen mitgeben wollen:

class Sorter[A <: Ordered[A]]

Das <:-Symbol bedeutet, dass A ein Untertyp von Ordered[A] sein muss. Versuchen wir fortan eine Instanz vor Sorter mit einem Parameter zu erzeugen, der nicht sortiert werden kann, erhalten wir eine Fehlermeldung:

scala> new Sorter[IntBox]
res17: Sorter[IntBox] = Sorter@3eadff2f

scala> val x = new Sorter[Boolean]
<console>:8: error: type arguments [Boolean] do not conform to class Sorter's type parameter bounds [A <: Ordered[A]]
       val x = new Sorter[Boolean]
           ^
<console>:8: error: type arguments [Boolean] do not conform to class Sorter's type parameter bounds [A <: Ordered[A]]
       val x = new Sorter[Boolean]
                   ^

scala> val x = new Sorter[Int]
<console>:8: error: type arguments [Int] do not conform to class Sorter's type parameter bounds [A <: Ordered[A]]
       val x = new Sorter[Int]
           ^
<console>:8: error: type arguments [Int] do not conform to class Sorter's type parameter bounds [A <: Ordered[A]]
       val x = new Sorter[Int]
                   ^

Int besitzt definitiv Vergleichsmethoden, implementiert aber nicht den Typ Ordered, weshalb unser Code auch nicht kompiliert. Tatsächlich haben wir mit Ordered ein paar Krücken gewählt, die eher für Notsituation zu gebrauchen sind. Was wir wirklich brauchen ist nicht Ordered, sondern Ordering, das wir ja aber noch nicht verwenden können. Ok ok, ich bin nachsichtig und strecke euch den benötigten Code vor, gebe aber keine Garantie darauf, dass ihr ihn auch versteht.

class Sorter[A](implicit ord: Ordering[A])

case class Box[A](a: A)
object Box {
  implicit def ord[A]: Ordering[Box[A]] =
    new Ordering[Box[A]] {
      def compare(x: Box[A], y: Box[A]) =
        y.a.hashCode-x.a.hashCode
    }
}

Der implizite Parameter stellt sicher, dass eine Sorter-Instanz auch nur für Typen erstellt werden kann, die über eine geeignete Vergleichsmöglichkeit verfügen. Wir können den Code nun erfolgreich nutzen:

scala> new Sorter[Box[Int]]
res0: Sorter[Box[Int]] = Sorter@32a88bc2

scala> new Sorter[Int]
res1: Sorter[Int] = Sorter@5e3b8219

scala> new Sorter[Boolean]
res2: Sorter[Boolean] = Sorter@37f2ae62

scala> class X
defined class X

scala> new Sorter[X]
:10: error: No implicit Ordering defined for X.
              new Sorter[X]
              ^

Falls ihr das Beispiel oben ausprobiert dabei aber nicht das gleiche Ergebnis erhaltet habt müsst ihr die implizite Methode noch importieren (je nach dem wo und wie ihr den Code definiert hab wird er automatisch vom Compiler gefunden):

import Box._

Überraschen sollte euch hier, dass der Code auch für Int und Boolean funktioniert. Weshalb er es tut will ich hier aber nicht näher erläutern – dafür müsst ihr euch noch bis zu einem der nächsten Kapitel gedulden.

Wir können einen Typparameter auch nach oben hin beschränken:

class Bar
class Baz extends Bar
class Buz extends Baz
class Boz extends Buz

class Foo[A >: Buz]

Dies führt dazu, dass nur Obertypen von Buz erlaubt sind, bei allen anderen bekommen wir eine Fehlermeldung:

scala> new Foo[Bar]
res8: Foo[Bar] = Foo@4e7f3159

scala> new Foo[Baz]
res9: Foo[Baz] = Foo@caa6635

scala> new Foo[Buz]
res10: Foo[Buz] = Foo@48b91881

scala> new Foo[Boz]
:12: error: type arguments [Boz] do not conform to class Foo's type parameter bounds [A >: Buz]
       val res11 =
           ^
:13: error: type arguments [Boz] do not conform to class Foo's type parameter bounds [A >: Buz]
              new Foo[Boz]
                  ^

Es ist sogar möglich beide Beschränkungen miteinander zu kombinieren:

class Foo[A >: Bar <: Baz]

Hier darf Foo nur mit Obertypen von Bar instanziiert werden, die gleichzeitig auch Untertypen von Baz sind.

Abstrakte Typen

Neben parametrisierten Typen bietet Scala auch sogenannte abstrakte Typen, die eine weitere Möglichkeit darstellen wie man generisch programmieren kann.

abstract class Box {
  type A
  val value: A
}

scala> new Box { type A = Int; val value = 13 }
res0: Box{type A = Int} = $anon$1@61735602

scala> new Box { type A = String; val value = "hello" }
res1: Box{type A = String} = $anon$1@20dbd794

Zur Deklaration eines abstrakten Typs wird das type-Schlüsselwort verwendet, das wir auch zum späteren Binden eines konkreten Typs benötigen.

Genau wie die parametrisierten Typen können auch die abstrakten Typen mit Beschränkungen versehen werden:

type A <: B
type A >: B
type A >: B <: C

Die semantische Bedeutung der Symbole habe ich weiter oben schon erklärt und kann dort nachgeschlagen werden falls ihr sie noch nicht verinnerlicht haben solltet.

Kleine Bemerkung am Rande: ein gebundener abstrakter Typ ist immer ein Untertyp des jeweiligen deklarierten Typs. Es gilt also:

C { type A = SomeType } <: C

Abstrakte Typen unterscheiden sich auf den ersten Blick nicht sonderlich von parametrisierten Typen. Tatsächlich wird man in den meisten Fällen die parametrisierten Typen auch bevorzugen, da sie nicht so langatmig zu notieren sind und sie dank Typinferenz oft auch gar nicht erst notiert werden müssen. Der große Vorteil von abstrakten Typen ist, dass sie vererbt werden können und somit typisierte Ableitungen erlauben.

trait Suite {
  type A
}
trait StringBuilderSuite extends Suite {
  type A = StringBuilder
}
class DefSuite extends Suite with StringBuilderSuite

Dieser Code bietet zuerst einmal etwas Neues: Traits. Was sie genau machen und wie sie sich von Klassen unterscheiden möchte ich euch im nächsten Kapitel beschreiben. Für den Rest dieses Kapitels reicht es zu wissen, dass man mit ihnen (und mit dem with-Schlüsselwort) eine Art Mehrfachvererbung erzeugen kann und dass sie abstrakte Typen sind und deshalb nicht so ohne weiteres instanziiert werden können:

scala> new Suite
<console>:9: error: trait Suite is abstract; cannot be instantiated
              new Suite
              ^

In obigem Code haben wir uns die Vererbung der abstrakten Typen zu Nutze gemacht und uns so ein wenig Schreibarbeit erspart. Wenn wir parametrisierte Typen benutzen fällt der Unterschied sofort auf:

trait Suite[A]
trait StringBuilderSuite extends Suite[StringBuilder]
class DefSuite extends Suite[StringBuilder] with StringBuilderSuite

Die Klasse DefSuite muss nun zwangsläufig noch einmal parametrisiert werden, obwohl die Parametrisierung schon im Trait StringBuilderSuite festgelegt wurde. Ohne die erneute Parametrisierung würde der Code nicht kompilieren:

scala> class DefSuite extends Suite with StringBuilderSuite
<console>:9: error: trait Suite takes type parameters
       class DefSuite extends Suite with StringBuilderSuite
                              ^

Abstrakte Typen bieten keine großen Vorteile gegenüber den Parametrisierten, runden Scalas Typsystem aber noch ein wenig ab – einen Anwendungsfall für sie kann man immer mal wieder finden.

Scalas generische Typen bieten noch ein paar Feinheiten, die ich hier noch nicht genannt habe und auch nicht mehr nennen möchte. Manches werde ich – wenn es angebracht ist – im weiteren Verlauf des Tutorials irgendwo einpflegen, manch anderem – wie z.B. Varianzen – gebe ich noch ein eigenes Kapitel, damit sie in der Menge von Scalas Möglichkeiten nicht untergehen.

StackOverflow Scala Tutorial

Da ich auf StackOverflow im Scala-Bereich sehr aktiv bin, hatte ich irgendwann mal angefangen mir die besten Fragen und Antworten aufzuschreiben, damit sie leicht wiederzufinden sind. Mit der Zeit ist daraus eine der umfangreichsten Scala-Wissenssammlungen entstanden, die das Internet momentan zu bieten hat.

All die gesammelten Links habe ich nun als geordnete Liste unter dem Scala-Tag Wiki veröffentlicht.

Viel Spaß beim Lesen!

Teil 13: Fallklassen

Im letzten Kapitel haben wir Extraktoren kennen gelernt. Ich habe euch bereits ein paar Möglichkeiten gezeigt wie man sie einsetzen kann, tatsächlich gibt es aber noch viel mehr Möglichkeiten wie man sie noch einsetzen kann. Durch ihre Hilfe ist es uns z.B. möglich komplexe Ausdrücke komfortabel auszuwerten, typsichere Aufzählungen zu kreieren oder Objekte miteinander kommunizieren zu lassen. Durch die Vielzahl an Möglichkeiten wie man sie einsetzen kann wurde Scala durch sogenannte Fallklassen (engl.: case class) aufgewertet, die „normale“ Klassen durch syntaktischen Zucker erweitern und uns die Arbeit erleichtern.

Schauen wir uns noch einmal das Personen-Beispiel an:

class Person(val name: String, val age: Int, val address: Address)
object Person {
  def unapply(p: Person) = Some(p.name, p.age, p.address)
}
class Address(val city: String, val zip: Int, val street: String)
object Address {
  def unapply(a: Address) = Some(a.city, a.zip, a.street)
}

Wir mussten wir für unsere Klassen die Extraktoren erzeugen. Wenn wir wollten, könnten wir auch noch eine apply-Methode erstellen. Es gibt jedoch viel zu viele Anwendungsfälle bei denen wir von Extraktoren Gebrauch machen können, folglich haben wir unnötig viel Code-Duplikation. Genau aus diesem Grund gibt es Fallklassen, die denkbar einfach zu erstellen sind.

case class Person(name: String, age: Int, address: Address)
case class Address(city: String, zip: Int, street: String)

Es genügt das Schlüsselwort case vor die Klasse zu schreiben. Schauen wir uns gleich mal an, was uns das bringt:

scala> val p = Person("franz", 43, Address("gornau", 12345, "rabenweg"))
p: Person = Person(franz,43,Address(gornau,12345,rabenweg))

scala> val Person(name, age, address @ Address(city, zip, street)) = p
name: String = franz
age: Int = 43
address: Address = Address(gornau,12345,rabenweg)
city: String = gornau
zip: Int = 12345
street: String = rabenweg

scala> p.name
res0: String = franz

scala> p.address.zip
res1: Int = 12345

Wie zu erkennen entfällt die Erstellung einer apply- und unapply-Methode. Der Compiler erstellt für uns ein Companion-Objekt und erzeugt die genannten Methoden. Weiterhin implementiert er noch eine Reihe weiterer Methoden für unsere Fallklassen. Dazu gehören z.B. toString(), equals() und hashCode(). Erstere gibt uns eine ansehnliche Stringrepräsentation unserer Klasse zurück, die beiden anderen ermöglichen uns Objekte miteinander zu vergleichen.
Weiterhin erzeugt uns der Compiler auch noch Getter für unsere Attribute ohne dass wir dies explizit durch ein val angeben müssten.

Schauen wir uns noch an wie wir all diese Methoden nutzen können.

scala> class IntHolder(i: Int)
defined class IntHolder

scala> new IntHolder(17) == new IntHolder(17)
<console>:9: warning: comparing a fresh object using `==' will always yield false
              new IntHolder(17) == new IntHolder(17)
                                ^
res0: Boolean = false

scala> case class IntHolder(i: Int)
defined class IntHolder

scala> IntHolder(17) == IntHolder(17)
res1: Boolean = true

scala> IntHolder(17) == IntHolder(3)
res2: Boolean = false

Das Vergleichen unserer Objekte funktioniert perfekt. Der Compiler sorgt dafür, dass wir keine Fehler bei den Vergleichsmethoden machen können. So können wir Fallklassen auch in ein Set einfügen und sicher gehen, dass auch wirklich keine Duplikate enthalten sind:

scala> class IntHolder(i: Int)
defined class IntHolder

scala> Set(new IntHolder(23), new IntHolder(23))
res6: scala.collection.immutable.Set[IntHolder] = Set(IntHolder@b3f451d, IntHolder@66d278af)

scala> case class IntHolder(i: Int)
defined class IntHolder

scala> Set(IntHolder(23), IntHolder(23))
res7: scala.collection.immutable.Set[IntHolder] = Set(IntHolder(23))

Sehr schön ist auch die Erstellung einer copy-Methode, die es uns erlaubt unveränderliche Objekte komfortabel zu kopieren:

scala> case class X(i: Int, s: String)
defined class X

scala> val x1 = X(8, "hello")
x1: X = X(8,hello)

scala> val x2 = x1.copy(s = "world")
x2: X = X(8,world)

Durch benannte Argumente können wir nur das Attribut angeben, das geändert werden soll. Manchmal ganz nützlich ist eine Methode namens productIterator, mit der wir über alle Elemente unserer Klasse iterieren können:

scala> for (x <- x1.productIterator) println(x)
8
hello

Wenn das alles so einfach geht, warum habe ich euch dann im letzten Kapitel mit Extraktoren gequält? Der Grund ist keinesfalls meine Boshaftigkeit 😉 oder weil ich nach dem Motto „Warum einfach wenn es auch kompliziert geht?“ lebe, sondern einfach damit ihr es mal gesehen habt. In den meisten Anwendungsfällen werden Fallklassen vollkommen ausreichen, manchmal muss man aber eben doch noch selbst Hand anlegen und dann ist es nicht schlecht wenn man weiß was man machen muss.

Da es zu Fallklassen eigentlich nicht mehr viel zu sagen gibt wollen wir uns gleich ein paar Anwendugsgebiete anschauen.

Algebraische Datentypen (ADT)

Den Anfang macht erst einmal eine Erklärung zu ADTs. Oh Gott, das hört sich wieder kompliziert an, was ist das wieder für eine neue Teufelei? Ich kann euch beruhigen, ADT ist nur der Name eines Pattern, das ihr sogar schon kennen gelernt habt. Von einem ADT wird immer dann gesprochen wenn ein Datentyp die Gestalt eines Typs aus einer Menge von mehreren zusammengehörenden Typen ist. Hört sich kompliziert an? Für den Anfang ja, aber schauen wir uns ein Beispiel an und quälen uns nicht mit der Theorie herum:

data Bool = True | False

Betrachten wir den Typ, der mit data spezifiziert wird (hier Bool) als ein Typ, der die Formen True oder False annehmen kann (wobei der senkrechte Strich ein Oder symbolisiert). In Scala ist es leider nicht möglich ADTs so kurz und praktisch wie oben gezeigt zu notieren (obiger Code wäre valider Haskell-Code), durch Fallklassen hält sich der Overhead an Code aber in Grenzen:

abstract class Bool
case object True extends Bool
case object False extends Bool

Durch die Repräsentation des ADT mit einer geeigneten Vererbungshierarchie dürftet ihr es leichter haben euch das Typensystem vorzustellen. Wir haben einen abstrakten Obertyp, der durch mehrere Unterobjekte repräsentiert werden kann. In Scala besitzen wir die Möglichkeit durch ein object zu spezifizieren, dass ein Typ nur einmal existieren darf bzw. soll. Mehrere unterschiedliche True- oder False-Werte würden keinen Sinn machen, wir unterbinden also die Möglichkeit sie mehrfach zu erstellen. Den List-ADT habt ihr bereits kennen gelernt:

data IntList = Cons Int IntList | IntNil

abstract class IntList
case class Cons(head: Int, tail: IntList) extends IntList
case object IntNil extends IntList

ADTs sind in Scala lang nicht so schön zu implementieren wie z.B. in Haskell. Das liegt nicht nur daran, dass der syntaktische Overhead größer ist, sondern auch daran, dass wir jederzeit die Möglichkeit haben weitere Typen zu ergänzen. In Scala hindert uns niemand daran noch weitere Klassen zu erstellen, die von Bool erben. In Haskell wäre dies nach der Spezifizierung von Bool nicht mehr möglich. Der Grund warum wir nicht möchten, dass weitere Typen ergänzt werden ist Typsicherheit. Um zu verdeutlichen was für Probleme entstehen könnten schauen wir uns am besten folgendes Beispiel an:

def determine(b: Bool) = b match {
  case True => "true"
  case False => "false"
}

scala> determine(True)
res0: java.lang.String = true

scala> determine(False)
res1: java.lang.String = false

Durch Pattern Matching können wir bestimmen was für ein genauer Typ Bool zur Laufzeit hat. Wie zu erkennen besitzt die Methode keinen Default-Wert. Würden wir also einen anderen Typ als True oder False übergeben bekämen wir einen MatchError:

scala> case object X extends Bool
defined module X

scala> determine(X)
scala.MatchError: X (of class X$)
<stack trace>

In Haskell könnte der Code niemals fehl schlagen, da es ja keine Möglichkeit gibt nachträglich noch Typen zu ergänzen. In Scala müssen wir damit leben, dass uns der Compiler diese Typsicherheit nicht bieten kann. Falls also die Möglichkeit besteht, dass eines unserer Programme durch dieses Manko instabil bzw. manipuliert werden könnte, dann müssen wir wohl oder übel Default-Fälle einbauen.

Ein weiteres Beispiel für einen ADT wäre Int:

data Int = -2147483648 | ... | -1 | 0 | 1 | ... | 2147483647

Int kann als minimaler Wert -2³¹ und als maximaler Wert 2³¹-1 annehmen. Int wäre also immer ein Typ aus der Menge dieser Int-Literale.

Wenn wir die theoretische Seite der ADTs noch ein wenig genauer betrachten, dann stellen wir fest, dass ein ADT nur durch andere Typen der selben Menge aufgebaut werden kann und dass dessen Werte durch Pattern Matching extrahiert werden können. Was genau das bedeutet, soll uns wieder ein Beispiel erklären:

abstract class Shape
case class Point(x: Float, y: Float) extends Shape
case class Circle(p: Point, r: Float) extends Shape
case class Rectangle(p: Point, h: Float, w: Float) extends Shape

import math._

def area(s: Shape) = s match {
  case Point(_, _) => 0
  case Circle(_, r) => Pi*r*r
  case Rectangle(_, h, w) => h*w
}

def pointIntersectWith(p: Point, s: Shape) = p -> s match {
  case (Point(x1, y1), Point(x2, y2)) =>
    x1 == x2 && y1 == y2
  case (Point(x1, y1), Circle(Point(x2, y2), r)) =>
    (x1 >= x2-r && x1 <= x2+r) && (y1 >= y2-r && y1 <= y2+r)
  case (Point(x1, y1), Rectangle(Point(x2, y2), h, w)) =>
    (x1 >= x2 && x1 <= x2+w) && (y1 >= y2 && y1 <= y2+h)
}

In diesem Beispiel haben wir mehrere zweidimensional Figuren. Innerhalb der Methoden bauen wir uns die ADTs mit Hilfe der Extraktoren auseinander. Für alle Werte, die wir nicht benötigen, setzen wir den Unterstrich ein. Es ist sehr gut zu erkennen, dass einzelne Figuren auf anderen basieren. So benötigt ein Rechteck einen Punkt, der dessen Position im Koordinatensystem angibt. Testen wir den Code auf seine Funktionsweise:

scala> val c = Circle(Point(6, 7), 2)
c: Circle = Circle(Point(6.0,7.0),2.0)

scala> val r = Rectangle(Point(1, 2), 5, 3)
r: Rectangle = Rectangle(Point(1.0,2.0),5.0,3.0)

scala> area(c)
res5: Double = 12.566370614359172

scala> area(r)
res6: Double = 15.0

scala> pointIntersectWith(Point(1, 2), r)
res7: Boolean = true

scala> pointIntersectWith(Point(8, 8), c)
res8: Boolean = true

scala> pointIntersectWith(Point(8, 12), c)
res9: Boolean = false

Konstruktion und Extraktion erfordern eine nahezu identische Syntax, aber das ist uns bereits bekannt. Der Code funktioniert zwar, ist aber nicht besonders schön. Dank Scalas Objektorientierung können wir die benötigten Methoden auch in die ADTs verschieben:

abstract class Shape {
  def area: Float
  def intersectWith(s: Shape): Boolean
}
case class Point(x: Float, y: Float) extends Shape {
  def area = 0
  def intersectWith(s: Shape)= s match {
    case Point(x, y) =>
      this.x == x && this.y == y
    case Circle(Point(x, y), r) =>
      (this.x >= x-r && this.x <= x+r) && (this.y >= y-r && this.y <= y+r)
    case Rectangle(Point(x, y), h, w) =>
      (this.x >= x && this.x <= x+w) && (this.y >= y && this.y <= y+h)
  }
}
case class Circle(p: Point, r: Float) extends Shape {
  import math._
  def area = (Pi*r*r).toFloat
  def intersectWith(s: Shape) =
    throw new UnsupportedOperationException("circle.intersectWith")
}
case class Rectangle(p: Point, h: Float, w: Float) extends Shape {
  def area = h*w
  def intersectWith(s: Shape) =
    throw new UnsupportedOperationException("rectangle.intersectWith")
}

Die Objektorientierung erlaubt uns die Operator-Notation zu gebrauchen und den Code, der zu einem Objekt gehört, einfacher zu verwalten. Weiterhin gewinnen wir ein wenig Performance, da dank reduziertem Pattern Matching weniger Überprüfungen zur Laufzeit stattfinden müssen. Zwei der Methoden hab ich noch nicht implementiert und deshalb mit einer Exception versehen. Ich werde in einem späteren Artikel noch genauer auf Exceptions eingehen, momentan reicht es zu wissen, dass der String, der an die Exception übergeben wird, später im Stack-Trace stehen wird und dass die Exception mit dem Schlüsselwort throw aus der Methode geworfen wird. Exceptions sind in Scala Untertypen eines jeden Typs weshalb kein weiterer Rückgabetyp für die Methode angegeben werden muss.

scala> val r = Rectangle(Point(1, -2), 6, 3)
r: Rectangle = Rectangle(Point(1.0,-2.0),6.0,3.0)

scala> Point(3, 4) intersectWith r
res16: Boolean = true

scala> val c = Circle(Point(7, 3), 5)
c: Circle = Circle(Point(7.0,3.0),5.0)

scala> c.area
res17: Float = 78.53982

scala> r intersectWith c
java.lang.UnsupportedOperationException: rectangle.intersectWith

Der Code funktioniert wie erwartet und sollte keine weiteren Erklärungen mehr benötigen.

Ein Problem auf das man immer wieder stoßen kann, ist dass man vergisst auf bestimmte Typen zu prüfen. Die Wahrscheinlichkeit dafür steigt, umso größer die Menge an verfügbaren Typen ist. Scala stellt uns deswegen das Schlüsselwort sealed zur Verfügung, das den Compiler anweist zu überprüfen ob wir innerhalb der Pattern auch auf alle Typen überprüfen:

sealed abstract class Weekday
case object Mo extends Weekday
case object Tu extends Weekday
case object We extends Weekday
case object Th extends Weekday
case object Fr extends Weekday
case object Sa extends Weekday
case object Su extends Weekday

def isWeekend(w: Weekday) = w match {
  case Sa | Su => true
  case _ => false
}

def doTask(w: Weekday) = w match {
  case Sa | Su => "sleep very long"
  case Mo | Fr => "work less"
  case We | Th => "work hard"
}

Bei der Methode doTask erhalten wir vom Compiler eine Warnung:

<console>:17: warning: match is not exhaustive!
missing combination             Tu

       def doTask(w: Weekday) = w match {
                                ^
doTask: (w: Weekday)java.lang.String

Diese verschwindet erst nachdem wir für den Dienstag eine entsprechende Tätigkeit definiert haben. Obiges Beispiel ist eine Aufzählung, die wir in Scala anstatt von Enums verwenden können. Scala selbst bietet sowohl die Möglichkeit ADTs oder die klassischen Enums als Aufzählungstyp zu verwenden. Einen Enum erstellen wir indem wir ein Objekt von der Klasse Enumeration erben lassen und allen Aufzählungstypen den Value-Wert zuweisen:

object Weekday extends Enumeration {
  val Mo, Tu, We, Th, Fr, Sa, Su = Value
}

import Weekday._

def isWeekend(w: Weekday.Value) = w match {
  case Sa | Su => true
  case _ => false
}

scala> isWeekend(Tu)
res19: Boolean = false

scala> for(w <- Weekday.values) println(w)
Mo
Tu
We
Th
Fr
Sa
Su

scala> Weekday withName "Mo"
res25: Weekday.Value = Mo

Ob man sich nun für Enums oder für ADTs entscheidet hängt ganz vom Anwendungsfall ab. Enums besitzen ein paar nützliche Methoden, die es ermöglichen ein Enum anhand eines Strings zu bestimmen oder mit denen man über alle Werte iterieren kann. Dafür lassen sie sich nicht objektorientiert nutzen, da sie nicht durch Klassen, sondern durch eine Variable repräsentiert werden. Werden also Aufzählungen mit verschiedenen Verhaltensweisen benötigt empfiehlt es sich auf ADTs zu setzen.

Hinweis:
Wir müssen nicht unbedingt ein ‚case‘ vor ein ‚object‘ setzten wenn wir es innerhalb von Pattern Matchings benutzen wollen. Das ‚case‘ hat tatsächlich nur ein geringen Nutzen, da für ein ‚object‘ keine apply-, unapply- und all die anderen Methoden generiert werden müssen. Die einzige Methode, die uns durch das ‚case‘ geschenkt wird und die auch von Nutzen ist, ist toString(), die den Namen des ‚object‘ zurück gibt.

Syntaxbäume

Eine weitere Möglichkeit ADTs einzusetzen ergibt sich bei der Erstellung von Syntaxbäumen. Ein Syntaxbaum besteht aus lauter Expressions, die sich in Terme, Faktoren, Literale und andere Symbole gliedern lassen. Versuchen wir dies in Scala abzubilden:

sealed abstract class Exp
case class Lit(v: BigDecimal) extends Exp
case class Add(n1: Exp, n2: Exp) extends Exp
case class Sub(n1: Exp, n2: Exp) extends Exp
case class Mul(n1: Exp, n2: Exp) extends Exp
case class Div(n1: Exp, n2: Exp) extends Exp

def eval(n: Exp): BigDecimal = n match {
  case Lit(v) => v
  case Add(n1, n2) => eval(n1)+eval(n2)
  case Sub(n1, n2) => eval(n1)-eval(n2)
  case Mul(n1, n2) => eval(n1)*eval(n2)
  case Div(n1, n2) => eval(n1)/eval(n2)
}

Anhand der dargestellten Datentypen können wir bequem einen Syntaxbaum aufbauen und durch die eval-Methode evaluieren:

scala> val e1 = Mul(Add(Lit(3), Lit(4)), Sub(Lit(9), Lit(2)))
e1: Mul = Mul(Add(Lit(3),Lit(4)),Sub(Lit(9),Lit(2)))

scala> eval(e1)
res10: BigDecimal = 49

scala> (3+4)*(9-2)
res11: Int = 49

scala> val e2 = Div(Lit(7), Sub(Add(Lit(3), Lit(4)), Lit(3)))
e2: Div = Div(Lit(7),Sub(Add(Lit(3),Lit(4)),Lit(3)))

scala> eval(e2)
res12: BigDecimal = 1.75

scala> val e3 = Mul(Lit(BigDecimal("8643356779865464.5")), Lit(BigDecimal("78953642.159865456879")))
e3: Mul = Mul(Lit(8643356779865464.5),Lit(78953642.159865456879))

scala> eval(e3)
res14: BigDecimal = 682424498257544872878103.7104460553

Durch den Einsatz von BigDecimal als Datentyp können wir Zahlen beliebiger Genauigkeit nutzen. Möchten wir maximale Präzision beim errechnen der Zahlen, müssen wir BigDecimal mit einem String konstruieren. Bei der Eingabe von Int-Literalen müssen wir die apply-Methode von BigDecimal nicht explizit aufrufen. Die eval-Methode könnten wir dank Scalas Syntaxzucker auch so schreiben:

def eval(n: Exp): BigDecimal = n match {
  case Lit(v) => v
  case n1 Add n2 => eval(n1)+eval(n2)
  case n1 Sub n2 => eval(n1)-eval(n2)
  case n1 Mul n2 => eval(n1)*eval(n2)
  case n1 Div n2 => eval(n1)/eval(n2)
}

Das mag der ein oder andere ein wenig schöner finden als der normale Aufruf der Extraktoren. Ich möchte noch einmal daran erinnern, dass Scala objektorientiert ist, es steht uns also frei die eval-Methode direkt an den ADT zu heften:

sealed abstract class Exp {
  def eval: BigDecimal
}
case class Lit(v: BigDecimal) extends Exp {
  def eval = v
}
case class Add(n1: Exp, n2: Exp) extends Exp {
  def eval = n1.eval+n2.eval
}
case class Sub(n1: Exp, n2: Exp) extends Exp {
  def eval = n1.eval-n2.eval
}
case class Mul(n1: Exp, n2: Exp) extends Exp {
  def eval = n1.eval*n2.eval
}
case class Div(n1: Exp, n2: Exp) extends Exp {
  def eval = n1.eval/n2.eval
}

Wieder entfällt der Runtime-Overhead durch das Pattern Matching weil die Methoden polymorph aufgerufen werden können:

scala> Mul(Add(Lit(3), Lit(4)), Sub(Lit(9), Lit(2))).eval
res16: scala.math.BigDecimal = 49

scala> Div(Lit(7), Sub(Add(Lit(3), Lit(4)), Lit(3))).eval
res17: scala.math.BigDecimal = 1.75

Hörst du mich?

Das letzte Einsatzgebiet für Fallklassen, das ich euch zeigen möchte, ist die Objektkommunikation. Die einfachste Möglichkeit um Objekte miteinander kommunizieren zu lassen ist über dessen Methoden.

case class Person(name: String)

case class Computer(name: String) {
  
  private var isRunning = false
  
  def sayHello(p: Person) {
    if (isRunning)
      println("hello '%s'" format p.name)
  }
  
  def start() {
    println("starting up '%s'" format name)
    isRunning = true
  }
  
  def stop() {
    println("'%s' is now sleeping" format name)
    isRunning = false
  }
}

An diesem Code ist nichts Besonderes. Die Klasse Computer stellt verschiedene Methoden bereit über die man mit der Klasse kommunizieren kann. Das Vorgehen ist bekannt und funktioniert auch prächtig:

scala> val p = Person("lara")
p: Person = Person(lara)

scala> val c = Computer("wudiwutz")
c: Computer = Computer(wudiwutz)

scala> c.start()
starting up 'wudiwutz'

scala> c sayHello p
hello 'lara'

scala> c.stop()
'wudiwutz' is now sleeping

Komplizierter wird dieses Vorgehen dann, wenn mehrere Parameter an eine Methode übergeben werden sollen. Der Einfachheit halber würde man versuchen aus diesen Parametern ein Objekt zu bilden, das an die Methode übergeben werden kann. Dies hätte weiterhin den Vorteil, dass dem Objekt wiederum Verhalten mitgegeben werden kann. Durch Fallklassen besteht in Scala die Möglichkeit die Kommunikation über Objekte nicht nur zu wählen wenn einzelne Parameter unnötiger Aufwand wären. Schauen wir uns das an:

sealed abstract class Msg
case class Greeting(p: Person) extends Msg
case object Start extends Msg
case object Stop extends Msg

Für alle Methoden, die Computer bereitstellt, wurde ein dazugehöriges Objekt definiert. Start- und Stop-Signale soll es nur ein Mal geben, die Begrüßung soll beliebig oft erfolgen können – wir benutzen für sie also eine Klasse und kein object. Alle unsere Objekte sind zu einem ADT zusammengefasst, damit wir später auch nur mit diesem arbeiten müssen. Damit unser Computer nun mit den Nachrichten etwas anfangen kann müssen wir ihn ein wenig anpassen:

case class Computer(name: String) {
  
  private var isRunning = false
  
  def send(msg: Msg) = msg match {
    case Start => start()
    case Stop => stop()
    case Greeting(p) => sayHello(p)
  }
  
  private def sayHello(p: Person) {
    if (isRunning)
      println("hello '%s'" format p.name)
  }
  
  private def start() {
    println("starting up '%s'" format name)
    isRunning = true
  }
  
  private def stop() {
    println("'%s' is now sleeping" format name)
    isRunning = false
  }
}

Unsere bisherigen Methoden haben wir auf private gesetzt, damit sie von außen nicht mehr erreichbar sind. Sie sollen fortan nur noch zur Übersicht des Codes dienen. Die wichtigste Methode ist nun send, die eine Nachricht erwartet. Sie prüft welche Nachricht genau vorliegt und wählt dann die entsprechenden Aktionen aus.

scala> val p = Person("lara")
p: Person = Person(lara)

scala> val c = Computer("wudiwutz")
c: Computer = Computer(wudiwutz)

scala> c send Start
starting up 'wudiwutz'

scala> c send Greeting(p)
hello 'lara'

scala> c send Stop
'wudiwutz' is now sleeping

Wie unschwer zu erkennen hat sich die API unseres Objektes deutlich verkleinert. Das ganze System wirkt nun auch ein wenig objektorientierter, da Nachrichten nun nicht mehr nur Methoden, sondern ebenfalls Objekte sind. Dies ist mit ein klein wenig Laufzeit-Overhead verbunden, über den wir uns aber nicht groß zu kümmern brauchen, sofern wir keine zeitkritische Anwendungen schreiben müssen. Wollen wir, dass unser Computer auch antworten kann, benötigen wir weiter Objekte zum verschicken und eine Methode um diese zu empfangen:

case class ThrottleCpuPower(percent: Int) extends Msg

sealed abstract class Response extends Msg
case class CpuPower(power: Option[Int]) extends Response
case object NoResponse extends Response

Mit dem ADT Response können wir die Antworten des Computers spezialisieren um später nicht auf alle Nachrichten matchen zu müssen.

case class Person(name: String) {
  def reply(res: Response) = res match {
    case CpuPower(power) =>
      if (power.isDefined) println("new cpu power is %d%%" format power.get)
      else println("nothing changed")
    case NoResponse =>
  }
}

Unsere Personen-Klasse erhält eine Methode über die sie mit Nachrichten versorgt werden kann. Wir müssen auch unseren Computer anpassen, da dieser ja mit Nachrichten antworten soll:

// in class Computer
private var cpuPower = 80

def send(msg: Msg) = msg match {
  case Start => start()
  case Stop => stop()
  case Greeting(p) => sayHello(p)
  case _ =>
}

def sendAndResponse(msg: Msg) = msg match {
  case ThrottleCpuPower(percent) => owner reply CpuPower(throttle(percent))
  case _ => owner reply NoResponse
}

private def throttle(percent: Int) =
  if (cpuPower-percent < 20) None
  else {
    cpuPower -= percent
    Some(cpuPower)
  }

Es gibt eine neue öffentliche Methode namens sendAndResponse, an die alle Nachrichten geschickt werden, auf die geantwortet werden soll. In unserem Fall wollen wir nach einer Drosselung der CPU-Geschwindigkeit eine Rückmeldung mit der neuen Geschwindigkeit erhalten. Als Antwort wird ein Option gesendet. Damit haben wir die Möglichkeit das Signal über den Änderungszustand weiter anzupassen. Unser Computer soll bspw. immer erreichbar sein, was wir dadurch erreichen, dass eine Mindestmarke nie unterschritten werden darf. Ist dies der Fall soll nichts geändert werden. Die Antwort geht nun an einen mysteriösen owner, aber woher kommt dieser? Die einfachste Möglichkeit ist sicherlich ihn einfach über den Konstruktor zu injizieren:

case class Computer(name: String, owner: Person) {...}

Beachtet bitte, dass die send-Methode nun ein Default-Fall benötigt, andernfalls erhaltet ihr eine Warnung vom Compiler.

scala> val p = Person("lara")
p: Person = Person(lara)

scala> val c = Computer("wudiwutz", p)
c: Computer = Computer(wudiwutz,Person(lara))

scala> c send Start
starting up 'wudiwutz'

scala> c send Greeting(p)
hello 'lara'

scala> c sendAndResponse ThrottleCpuPower(30)
new cpu power is 50%

scala> c sendAndResponse ThrottleCpuPower(60)
nothing changed

scala> c send Stop
'wudiwutz' is now sleeping

Der Code funktioniert so wie erwartet. Wir erhalten unterschiedliche Ausgaben nachdem unser Computer eine Antwort verschickt hat.

Die Frage ist nun: Haben wir mit dieser Vorgehensweise im Vergleich zum kommunizieren mit Methoden etwas erreicht? In obigem Code halten sich die Vorteile in Grenzen. Unser System ist ein wenig objektorientierter, vielleicht auch ein wenig übersichtlicher. Das war es aber auch schon. Die wahren Stärken dieser Vorgehensweise können sich erst durch ein Framework entfalten, wie z.B. Akka:

case class Computer(name: String) extends Actor {
  def receive = {
    case Msg => self reply Response
  }
}

Akka ist ein Actor-Framework und ermöglicht eine parallele Abarbeitung unserer Nachrichten. Actoren sind nichts besonderes, man kann sie sich als Menschen vorstellen, die Nachrichten (z.B. gesprochenen Wörter) empfangen („hören“) und auch verschicken („sprechen“) können – und das alle auf einmal. Sie können dabei nicht wissen was für einen Zustand die Anderen gerade besitzen („Gedanken“) und es steht ihnen frei wie sie auf Nachrichten reagieren. Akka stellt so ein Actoren-Modell zur Verfügung und lässt uns damit komfortabel arbeiten. Wenn wir uns die receive-Methode angucken stellen wir fest, dass kein Default-Fall mehr angegeben ist und auch das match-Statement, das eine Nachricht matcht, ist nirgends zu erblicken. Weiterhin kann auf ein self-Objekt geantwortet werden, dessen Definition für uns verborgen bleibt. Wir haben hier schönen kurzen Code, der jedoch weitaus komplexer als unser obiges Beispiel ist. Dafür ist er aber auch einfacher zu benutzen und zu verstehen – sofern man die benutzten Konzepte verstanden hat.

Ich werde im Zuge dieses Tutorials näher auf Actoren und auch auf Akka eingeben und euch all das Wissen vermitteln, das ihr braucht um obigen Code ebenfalls korrekt anwenden zu können.

Lösungen: Extraktoren

  1. Wenn wir den Extraktor über eine Klasse erstellen können wir sein Verhalten anpassen.
    class Nth(n: Int) {
      def unapply(xs: Seq[Int]) = if (n < xs.size) Some(xs(n)) else None
    }
    val isSecond_? = new Nth(1)
    val isThird_? = new Nth(2)
    Vector(9, 13, 3, 73, 52) match {
      case isSecond_?(12) => println("second is twelve")
      case isThird_?(3) => println("third is three")
      case _ => println("nothing special found")
    }
    
  2. Der &-Extraktor ist sehr einfach. Es genügt, einfach einen Tuple2 mit dem Eingabestring zurückzugeben.
    object & {
      def unapply(a: String) = Some(a, a)
    }
    object StartsWith {
      def unapply(s: String) = s.headOption
    }
    object EndsWith {
      def unapply(s: String) = s.lastOption
    }
    
    "Hello World" match {
      case StartsWith('H') & EndsWith('d') => "yes"
      case _ => "no"
    }
    "Hello World" match {
      case StartsWith('g') | EndsWith('d') => "yes"
      case _ => "no"
    }
    
  3. Die Baumrepräsentation ähnelt der von IntList. Die Extraktoren sollten kein Problem mehr sein.
    
    abstract class IntTree
    
    class Node(val left: IntTree, val right: IntTree) extends IntTree
    object Node {
      def apply(left: IntTree, right: IntTree) = new Node(left, right)
      def unapply(n: Node) = Some(n.left, n.right)
    }
    
    class Leaf(val i: Int) extends IntTree
    object Leaf {
      def apply(i: Int) = new Leaf(i)
      def unapply(l: Leaf) = Some(l.i)
    }
    
    object Empty extends IntTree
    
    val tree: IntTree = Node(Leaf(8), Node(Node(Leaf(9), Empty), Node(Leaf(9), Empty)))
    tree match {
      case Node(Leaf(i @ 8), Node(Node(Leaf(j @ 9), Empty), _)) => "found:"+i+","+j
      case _ => "nothing found"
    }
    

Übungen: Extraktoren

  1. Erzeuge einen Extraktor, der es erlaubt mit Hilfe eines Indexes auf ein Element einer Seq zuzugreifen. Der Code
    Vector(8,2,5) match {
      case isSecond_?(2) => "yes"
      case _ => "no"
    }
    

    soll beispielsweise „yes“ ausgeben. Tipp: Benutze eine Klasse als Extraktor

  2. Die match-Expression erlaubt es mehrere Fälle zu „verodern“, sie aber nicht zu „verunden“. Folgendes ist möglich:
    "Hello World" match {
      case StartsWith('g') | EndsWith('d') => "yes"
      case _ => "no"
    }
    

    Dies hier aber nicht:

    "Hello World" match {
      case StartsWith('H') & EndsWith('d') => "yes"
      case _ => "no"
    }
    

    Finde einen Weg bei einer Eingabe von Strings, mehrere Extraktoren (hier: StartsWith und EndsWith) miteinander zu „verunden“. Tipp: & ist ebenfalls ein Extraktor.

  3. Schreibe Extraktoren für eine Baumrepräsentation:
    val tree: IntTree = Node(Leaf(8), Node(Node(Leaf(9), Empty), Node(Leaf(9), Empty)))
    tree match {
      case Node(Leaf(i @ 8), Node(Node(Leaf(j @ 9), Empty), _)) => "found:"+i+","+j
      case _ => "nothing found"
    }
    

    Entnehme die benötigten Klassen dem obigen Code.

Hier geht es zu den Lösungen.

Teil 12: Extraktoren

Wir haben in einem früheren Artikel bereits das Pattern Matching kennen gelernt. In dem dortigen Artikel musste ich euch für die Erklärungen, wie genau Pattern Matching nun funktioniert, auf einen späteren Zeitpunkt verweisen. In diesem Artikel werde ich euch die nötigen Erklärungen geben und nebenbei noch viele Beispiele bringen was wir mit Pattern Matching noch so alles machen können.

Einfache Extraktoren

Ein Beispiel, das ich schon gebracht habe, gab uns die Möglichkeit durch Pattern Matching einen Wert an Variablen zu binden:

def heavyCalculation() = {
  val memoryUsage = 50
  val cpuUsage = 91
  val networkUsage = 31
  (memoryUsage, cpuUsage, networkUsage)
}

scala> val (memoryUsage, cpuUsage, networkUsage) = heavyCalculation()
memoryUsage: Int = 50
cpuUsage: Int = 91
networkUsage:
 Int = 31

Die Funktionsweise des obigen Codes obliegt keinesfalls nur den Fähigkeiten des Compilers daraus Variablenzuweisungen zu generieren. Wir können aktiv in diesen Prozess eingreifen und festlegen was wir haben wollen. Hierfür benötigen wir nur einen sogenannten Extraktor. Ein Extraktor ist syntaktischer Zucker des Compilers – wir können ihn durch eine unapply-Methode innerhalb eines object erstellen und dann auf ihn zugreifen:

object StringExtractor {
  def unapply(s: String): Option[String] = s(0) match {
    case 'u' => Some(s.substring(1).toUpperCase)
    case 'l' => Some(s.substring(1).toLowerCase)
    case _ => None
  }
}

Wir können den Extraktor bequem aufrufen indem wir in Klammern das zu extrahierende Objekt übergeben:

scala> val StringExtractor(s) = "uHello"
s: String = HELLO

Der Compiler sorgt dann dafür, dass die unapply-Methode aufgerufen wird. Auf welche Typen ein Extraktor angewendet werden kann hängt vom Typ des Parameters der unapply-Methode ab – in unserem Beispiel wäre es ein String. Der Typ unserer Variable, die durch den Extraktor erzeugt wird hängt vom Rückgabetyp der unapply-Methode ab. Zum besseren Verständnis hier der Code, den der Compiler aus dem Extraktor erzeugen würde:

scala> val s = StringExtractor.unapply("uHello") match {
     |   case Some(s) => s
     |   case None => throw new MatchError
     | }
s: String = HELLO

Versuchen wir unseren Extraktor mit einem anderen Typ zu füttern, bekommen wir vom Compiler direkt eine Fehlermeldung:

scala> val StringExtractor(s) = 5
<console>:13: error: scrutinee is incompatible with pattern type;
 found   : String
 required: Int
       val StringExtractor(s) = 5
                          ^

Der Extraktor selbst funktioniert sehr einfach. Er prüft ob der erste Buchstaben eines Strings ein u oder ein l ist und wenn ja wird der restliche Stringinhalt in lauter Groß- oder Kleinbuchstaben umgewandelt. Die unapply-Methode gibt dann das extrahierte Objekt in einem Option verpackt zurück. Option haben wir schon früher kennen gelernt. Es gibt unserem Compiler die Möglichkeit zu erkennen ob ein Extraktor erfolgreich war oder nicht. Geben wir ein Some mit Inhalt zurück, so war der Extrahiervoragng erfolgreich. Haben wir nichts zu extrahieren müssen wir ein None zurückgeben. Würden wir nur das extrahierte Objekt zurück geben hätte der Compiler keine Möglichkeit festzustellen ob der Extraktionsvorgang erfolgreich war. Das ist insofern problematisch, da nach einem fehlgeschlagenen Pattern direkt zum nächsten Pattern gesprungen wird. Wenn also die Möglichkeit besteht, dass unser Extraktor fehlschlagen kann, dann müssen wir einen Default-Fall festlegen:

def extract(s: String) = s match {
  case StringExtractor(s) => s
  case _ => s
}

scala> extract("lHello World")
res4: String = hello world

scala> extract("uHello World")
res5: String = HELLO WORLD

scala> extract("hello")
res6: String = hello

Hätten wir keinen Default-Fall würde unser Code zur Laufzeit einen MatchError werfen:

scala> val StringExtractor(s) = "hello"
scala.MatchError: hello (of class java.lang.String)
<stack trace>

Anmerkung:
Der Extraktor muss mit einem Großbuchstaben anfangen, bei einem Kleinbuchstaben würde er nicht erkannt werden. Warum das so ist hab ich im Artikel über Pattern Matching bereits geschrieben.

Der Compiler hat hier keine Möglichkeit zu überprüfen ob der Code zur Laufzeit auch funktionieren wird. Er könnte zwar herausfinden was der Extraktor genau macht, er kann aber nicht wissen was für Eingabewerte er erhält. In obigem Beispiel haben wir einen statisch festgelegten String, aber was wenn der String durch eine Benutzereingabe erzeugt wird oder aus einer Datenbank kommt? Um zu vermeiden, dass unser Code hier einen potenziellen Fehler erzeugt, müssen wir unseren Extraktor ändern:

object StringExtractor {
  def unapply(s: String) = s(0) match {
    case 'u' => Some(s.substring(1).toUpperCase)
    case 'l' => Some(s.substring(1).toLowerCase)
    case _ => Some(s)
  }
}

Wir haben den Rückgabewert der unapply-Methode geändert. Anstatt ein Option erhalten wir nun nur noch ein Some. Dadurch funktioniert unser Code immer und wir können uns die Hilfsmethode zum Extrahieren ersparen:

scala> val StringExtractor(s) = "hello"
s: java.lang.String = hello

scala> val StringExtractor(s) = "uhello"
s: java.lang.String = HELLO

Mehrfache Extraktoren

Unser Code funktioniert jetzt für einen einzigen Parameter, wenn wir uns aber an das Tuple-Beispiel zurück erinnern, dann hatten wir dort aber mehrere Parameter:

scala> val (a, b) = (5, "hello")
a: Int = 5
b: java.lang.String = hello

Es ist gar nicht schwer dieses Verhalten selbst nachzubauen, wir müssen nur die Signatur der unapply-Methode ändern:

class Pair(val a: Int, val b: Int)
object Pair {
  def unapply(p: Pair): Option[(Int, Int)] = Some((p.a, p.b))
}

scala> val Pair(a, b) = new Pair(8, 12)
a: Int = 8
b: Int = 12

Die unapply-Methode erwartet jetzt ein Pair-Objekt. Zurückgeben tut sie dann alle zu extrahierenden Parameter in Tuple-Form (wieder gepackt in ein Option). Unsere Pair-Klasse können wir hier leider nur mit zwei Ints aufrufen. Wollen wir sie lieber mit einem String aufrufen wie beim Tuple Beispiel gezeigt, müssten wir den Parametertyp ändern, was jedoch sehr umständlich ist. In einem späteren Kapitel über parametrisierte Typen werde ich euch aber zeigen wie man dieses Problem geschickt lösen kann.

Anmerkung:
Wir können beim Erzeugen eines Tuples die runden Klammern weglassen wenn die Parameter schon in runden Klammern stehen. Das Codestück

Some((p.a, p.b))

können wir also auch

Some(p.a, p.b)

schreiben. Ihr glaubt es nicht? Dann probiert es aus!

Im Artikel über Pattern Matching habe ich euch versprochen folgenden Code zum Laufen zu bekommen:

val Person(name, address @ Address(city, zip, street)) = ...

Die Implementierungen sind wieder nicht besonders schwer:

class Person(val name: String, val age: Int, val address: Address)
object Person {
  def unapply(p: Person) = Some(p.name, p.age, p.address)
}
class Address(val city: String, val zip: Int, val street: String)
object Address {
  def unapply(a: Address) = Some(a.city, a.zip, a.street)
}

Das Extrahieren beschränkt sich dann auf bereits bekannte Sachen:

scala> val p = new Person("helen", 31, new Address("musterstadt", 12345, "musterstraße"))
p: Person = Person@22f49424

scala> val Person(name, age, address @ Address(city, zip, street)) = p
name: String = helen
age: Int = 31
address: Address = Address@68e2cd6f
city: String = musterstadt
zip: Int = 12345
street: String = musterstraße

Mit Hilfe des @-Zeichen können wir gleichzeitig die Adresse extrahieren aber auch deren Instanz an eine Variable binden.

Unsere Extraktor müssen wir übrigens nicht zwingend an ein object binden, wir können sie auch durch Klassen erzeugen:

class StringExtractor(u: Char = 'u', l: Char = 'l') {
  def unapply(s: String) = s(0) match {
    case `u` => Some(s.substring(1).toUpperCase)
    case `l` => Some(s.substring(1).toLowerCase)
    case _ => Some(s)
  }
}

Dies erlaubt uns unsere Extraktoren ein wenig anzupassen. Wir können bei der Objekterzeugung nämlich angeben auf welche Buchstaben der Extraktor prüfen soll.

scala> val SE1 = new StringExtractor()
SE1: StringExtractor = StringExtractor@7137f424

scala> val SE1(s) = "uhello"
s: java.lang.String = HELLO

scala> val SE2 = new StringExtractor('a', 'b')
SE2: StringExtractor = StringExtractor@1752b8b

scala> val SE2(s) = "ahello"
s: java.lang.String = HELLO

scala> val SE2(s) = "uhello"
s: java.lang.String = uhello

Beachtet hier bitte wieder dass, die Extraktoren innerhalb einer match-Expression groß geschrieben sein müssen und dass die Variablen mit Backticks referenziert werden müssen. Die mit val definierten Extraktoren dürfen wir auch kein schreiben.

Sequenzielle Extraktoren

Wir wissen jetzt wie wir einen Extraktor mit einem Parameter und auch mit mehreren Parametern erstellen, aber was ist wenn wir die Anzahl der Parameter gar nicht wissen? Das ist bspw. dann der Fall wenn wir eine Liste haben:

scala> val List(head, tail @ _*) = List(1, 2, 3)
head: Int = 1
tail: Seq[Int] = List(2, 3)

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

Die Liste kann eine beliebige Anzahl an Elementen besitzen, unsere unapply-Methode müsste also ein Option mit einer Seq zurückgeben. Schreiben wir den dazugehörigen Code:

class Container(val x: Int*)
object Container {
  def unapply(p: Container): Option[Seq[Int]] = Some(p.x)
}

Varargs sind in Scala nichts anderes als eine Seq, wir können sie also direkt zurückgeben. Testen wir den Code gleich noch:

scala> val Container(x1, x2, x3) = new Container(45, 32, 107)
<console>:9: error: wrong number of arguments for object Container
       val Container(x1, x2, x3) = new Container(45, 32, 107)
                    ^
<console>:9: error: recursive value x$1 needs type
       val Container(x1, x2, x3) = new Container(45, 32, 107)
                     ^

scala> val Container(x) = new Container(45, 32, 107)
x: Seq[Int] = WrappedArray(45, 32, 107)

Hm, das ist aber nicht das was wir erwartet haben. Aber es ist das spezifizierte Verhalten. Was haben wir denn genau hingeschrieben? Unsere unapply-Methode gibt eine Seq zurück. So weit so gut, aber woher soll der Compiler wissen ob wir durch das Pattern Matching eine Seq oder aber die Elemente der Seq erhalten wollen? Er kann es nicht wissen, deshalb können wir auch nur auf eine Seq matchen und nicht auf einzelne Elemente. Und da wir nur ein Element zurückgeben – nämlich die Seq – erhalten wir auch eine Fehlermeldung wenn wir versuchen den Extraktor mit mehreren Parametern aufzurufen. Bei List funktioniert es aber doch auch. Was ist dort anders? Tatsächlich kennt der Scala Compiler nicht nur eine unapply-Methode, sondern deren zwei. Die zweite nennt sich unapplySeqund kann als Ersatz zur normalen unapply-Methode genutzt werden. Wie der Name schon suggeriert ermöglicht sie uns nicht nur eine Seq zurückzugeben, sondern auch deren Elemente.

class Container(val x: Int*)
object Container {
  def unapplySeq(p: Container): Option[Seq[Int]] = Some(p.x)
}

scala> val Container(x) = new Container(45, 32, 107)
scala.MatchError: Container@16b5d4e1 (of class Container)
<stack trace>

scala> val Container(x @ _*) = new Container(45, 32, 107)
x: Seq[Int] = WrappedArray(45, 32, 107)

scala> val Container(head, tail @ _*) = new Container(45, 32, 107)
head: Int = 45
tail: Seq[Int] = WrappedArray(32, 107)

scala> val Container(x1, x2, x3) = new Container(45, 32, 107)
x1: Int = 45
x2: Int = 32
x3: Int = 107

Toll, nicht wahr? Es funktioniert alles so wie erwartet. Die unapplySeq-Methode unterliegt nur einer kleinen Einschränkung: Wir dürfen sie nicht zusammen mit einer unapply-Methode bereitstellen. Sollten beide Methoden existieren, so wird der Compiler nur die unapply-Methode auswählen und die andere nicht weiter beachten.

Jetzt haben wir für den Schluss aber noch etwas, das gerne besprochen werden möchte:

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

Diese Schreibweise unterscheidet sich von den Vorherigen. Wir müssen hier nicht mehr umständlich unseren Extraktor definieren. Stattdessen sieht es eher so aus wie wenn wir auf die Prepend-Methode von List zurückgreifen würden:

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

Der einzige Unterschied ist, dass das Nil am Schluss fehlt. Aber warum fehlt es? Die Antwort darauf wird ein wenig klarerer wenn wir unseren Code ein wenig umändern:

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

Huch, was war das? Es war mal wieder syntaktischer Zucker des Compilers, der uns hier das Leben erleichtert. Immer dann wenn eine Klasse zwei Typparameter erwartet (die wir später im Detail kennen lernen werden) oder einen Konstruktor mit zwei Parametern besitzt, besteht die Möglichkeit, dass wir sie nicht in der Form

Class(obj1, obj2)

sondern als

obj1 Class obj2

aufrufen können. Das Gleiche haben wir oben beim extrahieren der List-Elemente gemacht. Diese Schreibweise wird uns aber nur bei Typparameter und Konstruktoren erlaubt und sonst nirgends. Aber wieso funktioniert unser Code dann? Das Symbol :: ist doch eine Methode in List? Ja, es ist eine Methode aber auch der Aufruf eines Extraktors. Genau genommen existiert :: zwei Mal – einmal als Methode und einmal als Klasse. Die Klasse :: stellt einen geeigneten Konstruktor bereit, der uns diese Schreibweise erlaubt. Hier die Klassendefinition von scala.collection.immutable.:::

final case class ::[B](
  private var hd: B,
  private[scala] var tl: List[B])
extends List[B] {...}

Die Klassendefinition ist für den Anfang ein wenig verwirrend und genau deshalb werden wir uns jetzt eine eigene List schreiben. Das hilft uns nicht nur zu verstehen wann genau die Methode :: und wann das Objekt :: aufgerufen wird – es hilft uns vor allem auch die Stärken und Schwächen von List kennen zu lernen. Fangen wir damit also gleich an. Und danach gibt es noch ein paar Übungsaufgaben bei denen ihr testen könnt ob ihr auch alles verstanden habt und ohne meine Hilfe zurechtkommt.

Praxisbeispiel: Implementierung von List

Eine List ist eine einfach verkette Liste. Jedes Stück der List besitzt neben dem Element, das es aufnimmt noch eine Referenz auf das nächste Stück der Liste. Daraus folgt ein einfacher Konstruktor:

class IntList(val head: Int, val tail: IntList)
object IntList {
  def apply(head: Int, tail: IntList) = new IntList(head, tail)
}

Wir beschränken unsere Listimplementierung darauf, dass sie nur Ints aufnehmen kann, dann müssen wir uns noch nicht mit parametrisierten Typen herumschlagen. Durch die Implementierung einer apply-Methode können wir uns fortan gleich noch das new sparen. Wir können nun schon eine List erstellen:

scala> val xs = IntList(1, IntList(2, IntList(3, null)))
xs: IntList = IntList@7137f424

Das null ist uns jetzt noch ein Dorn im Auge. Es ist nicht typsicher und kann zu NullPointerExceptions führen. Versuchen wir es also zu umgehen:

class IntNil extends IntList(0, null)
object IntNil {
  def apply(): IntList = new IntNil
}

scala> val xs = IntList(1, IntList(2, IntList(3, IntNil())))
xs: IntList = IntList@57a68215

Aber wirklich besser ist das auch nicht. Wir haben das null jetzt nur vom Anwendungscode in die Bibliothek verlagert. Außerdem erzeugen wir bei jedem Aufruf von IntNil ein neues Objekt. Daraus folgt:

scala> IntNil() != IntNil()
res4: Boolean = true

Anmerkung:
Achtet darauf, dass ihr IntNil() aufruft und nicht nur IntNil. Wenn ihr die Klammern weg lässt referenziert ihr nicht die apply-Methode sondern den Typ IntNil. Dessen genaue Bedeutung kann uns im Moment egal sein, es muss nur klar sein, dass er existiert.

Wir dürfen also nur eine Instanz von IntNil besitzen. Wir erreichen das am besten wenn wir unseren Code ein wenig umbauen:

abstract class IntList {
  def head: Int
  def tail: IntList
}

class Cons(val head: Int, val tail: IntList) extends IntList
object Cons {
  def apply(head: Int, tail: IntList) = new Cons(head, tail)
}

object IntNil extends IntList {
  def head = throw new UnsupportedOperationException("nil head")
  def tail = throw new UnsupportedOperationException("nil tail")
}

Anstatt Verhalten durch IntNil auszutauschen haben wir nun eine polymorphe Datenstruktur, deren genaues Verhalten von den Subklassen abhängen. Scala erlaubt uns das Überschreiben von Methoden durch Attribute (so geschehen in Cons), da der Compiler für die Attribute entsprechende Zugriffsmethoden erzeugt.
Das null ist einer Exception gewichen, welche direkt durch die Methoden head und tail zurückgegeben wird. Die Codeerzeugung unterscheidet sich nicht groß von der vorherigen Version:

scala> val xs = Cons(1, Cons(2, Cons(3, IntNil)))
xs: Cons = Cons@4f86f5f

Ergänzen wir unseren Code durch eine vernünftige String-Repräsentation:

abstract class IntList {
  def head: Int
  def tail: IntList
  def isEmpty: Boolean

  override final def toString = {
    val sb = StringBuilder.newBuilder
    sb append "IntList("
    sb append head

    var xs = tail
    while (!xs.isEmpty) {
      sb append ", "
      sb append xs.head
      xs = xs.tail
    }

    sb append ")"
    sb.toString
  }
}

class Cons(val head: Int, val tail: IntList) extends IntList {
  def isEmpty = false
}
object Cons {
  def apply(head: Int, tail: IntList) = new Cons(head, tail)
}

object IntNil extends IntList {
  def head = throw new UnsupportedOperationException("nil head")
  def tail = throw new UnsupportedOperationException("nil tail")
  def isEmpty = true
}

Die isEpmty-Methode spart uns einen Vergleich auf IntNil, welchen man jetzt aber durchaus machen könnte, da es nur eine Instanz davon gibt. Die Ausgabe ist gleich zufriedenstellender.

scala> val xs = Cons(1, Cons(2, Cons(3, IntNil)))
xs: Cons = IntList(1, 2, 3)

Die Erzeugung der List sieht noch nicht besonders elegant aus. Ändern wir das:

// in IntList
def :: (i: Int) = new Cons(i, this)

scala> val xs = 1 :: 2 :: 3 :: IntNil
xs: Cons = IntList(1, 2, 3)

Als nächstes wollen wir auf die tolle Konkatenationsschreibweise zurückgreifen:

// in object Cons
def unapply(c: Cons) = Some(c.head, c.tail)

scala> val x1 Cons (x2 Cons x3) = 1 :: 2 :: 3 :: IntNil
x1: Int = 1
x2: Int = 2
x3: IntList = IntList(3)

Die Klammern werden leider benötigt da der Compiler sonst durch die Auswertungsreihenfolge (von links nach rechts) durcheinander kommt. Wir können das ändern indem wir der Cons-Klasse einen Namen geben, der mit einem Doppelpunkt endet.

class :: (val head: Int, val tail: IntList) extends IntList {
  def isEmpty = false
}
object :: {
  def apply(head: Int, tail: IntList) = new ::(head, tail)
  def unapply(c: ::) = Some(c.head, c.tail)
}

Wenn wir alle Vorkommen von Cons durch :: ersetzen, dann können wir durch die umgekehrte Auswertungsreihenfolge die Klammern weglassen:

scala> val head :: tail = 1 :: 2 :: 3 :: IntNil
head: Int = 1
tail: IntList = IntList(2, 3)

scala> val x1 :: x2 :: x3 :: IntNil = 1 :: 2 :: 3 :: IntNil
x1: Int = 1
x2: Int = 2
x3: Int = 3

Das war sie schon. Die ganze „Magie“ der Extraktoren. Zu Schluss noch eine Extraktor-Implementierung für unsere IntList:

object IntList {
  def apply(a: Int*) = {
    def loop(xs: Seq[Int], ys: IntList): IntList =
      if (xs.isEmpty) ys else loop(xs.tail, xs.head :: ys)
    loop(a, IntNil).reverse
  }

  def unapplySeq(a: IntList) = {
    def loop(xs: IntList, ys: List[Int]): List[Int] =
      if (xs.isEmpty) ys else loop(xs.tail, xs.head :: ys)
    Some(loop(a, Nil).reverse)
  }
}

// in IntList
def reverse: IntList = {
  def loop(xs: IntList, ys: IntList): IntList =
    if (xs.isEmpty) ys else loop(xs.tail, xs.head :: ys)
  loop(this, IntNil)
}

Der Code ist ein wenig umständlich. Wir müssen zuerst die Listen aufbauen und sie dann umdrehen. Wir haben leider keine Möglichkeit eine Liste direkt rückwärts aufzubauen, da sie nur einfach verkettet ist. Aber zumindest funktioniert der Code:

scala> val xs = IntList(1,2,3)
xs: IntList = IntList(1, 2, 3)

scala> val xs = IntList(1,2,3)
xs: IntList = IntList(1, 2, 3)

scala> val IntList(head, tail @ _*) = IntList(1, 2, 3)
head: Int = 1
tail: Seq[Int] = List(2, 3)

scala> val IntList(head, tail @ _*) = IntList(1 to 3: _*)
head: Int = 1
tail: Seq[Int] = List(2, 3)

Ihr erinnert euch doch hoffentlich noch an Ranges, die man im dritten Beispiel bewundern kann.

Die apply-Methode könnte man übrigens auch so schreiben:

// in object IntList
def apply(a: Int*) = (a :\ (IntNil: IntList)) { _ :: _ }

Das wäre die funktionale Herangehensweise an die Erzeugung einer geeigneten Liste. Das will ich aber nicht erklären, sonder mal nur so in den Raum werfen, damit ihr wisst was euch erwartet wenn ihr mir treu bleibt und fleißig weiter lest. 😉

Zum Abschluss noch die komplette Implementierung von IntList:

object IntList {
  def apply(a: Int*) = {
    def loop(xs: Seq[Int], ys: IntList): IntList =
      if (xs.isEmpty) ys else loop(xs.tail, xs.head :: ys)
    loop(a, IntNil).reverse
  }

  def unapplySeq(a: IntList) = {
    def loop(xs: IntList, ys: List[Int]): List[Int] =
      if (xs.isEmpty) ys else loop(xs.tail, xs.head :: ys)
    Some(loop(a, Nil).reverse)
  }
}

abstract class IntList {
  def head: Int
  def tail: IntList
  def isEmpty: Boolean

  def :: (i: Int) = new ::(i, this)

  def reverse: IntList = {
    def loop(xs: IntList, ys: IntList): IntList =
      if (xs.isEmpty) ys else loop(xs.tail, xs.head :: ys)
    loop(this, IntNil)
  }

  override final def toString = {
    val sb = StringBuilder.newBuilder
    sb append "IntList("
    sb append head

    var xs = tail
    while (!xs.isEmpty) {
      sb append ", "
      sb append xs.head
      xs = xs.tail
    }

    sb append ")"
    sb.toString
  }
}

class :: (val head: Int, val tail: IntList) extends IntList {
  def isEmpty = false
}
object :: {
  def apply(head: Int, tail: IntList) = new ::(head, tail)
  def unapply(c: ::) = Some(c.head, c.tail)
}

object IntNil extends IntList {
  def head = throw new UnsupportedOperationException("nil head")
  def tail = throw new UnsupportedOperationException("nil tail")
  def isEmpty = true
}