… & Kontext: Werkzeugkasten

Inhaltsverzeichnis

"Konsole & Kontext" ist eine gemeinsame Serie von Golo Roden und Michael Wiedeking, in der sich die beiden regelmäßig mit Konzepten der (funktionalen) Programmierung beschäftigen. Während "Konsole & …" die praktische Anwendung dieser Konzepte in JavaScript und Node.js zeigt, erläutert "... & Kontext" deren jeweiligen eher theoretischen Hintergrund.

In der letzten Folge wurde über die Funktionen map und reduce gesprochen. Dabei wurde zwar beschrieben, was die Funktionen leisten, aber nicht genau geklärt, wie diese implementiert sind. Dort wurde auch schon erwähnt, dass ein Iterator für diese Aufgabe nur bedingt geeignet ist, insbesondere dann, wenn es sich um rekursive Strukturen handelt.

Traversieren mit foreach

Deshalb bietet es sich doch an, von allen Collections eine foreach-Methode zu fordern, die es der Collection selbst überlässt, darüber zu entscheiden, wie über die Elemente iteriert werden soll.

  abstract class Collection<T> {
    …
    abstract function foreach(f : T -> ()) -> ()
  }

Der Funktion kann so ein Lambda-Ausdruck übergeben werden, der nacheinander für alle in der Collection enthaltenen Elemente aufgerufen wird. Bei einem Array könnte das etwa über eine Schleife geschehen.

  class ArrayList<T> extends Collection<T> {
    private data : Array<T>
    …
    function foreach(f : T -> ()) -> () {
      for (datum : data) {
        f(datum)
      }
    }
    …
  }

Bei einer (binären) Baumstruktur (Tree<T>), die beispielsweise aus Knoten (Node<T>) mit zwei Elementen besteht, die entweder Blätter (Leaf<T>) oder wieder Knoten sind, dann würde man das eher rekursiv machen.

  abstract class Tree<T> implements Collection<T> {
    …
  }

  class Leaf<T> extends Tree<T> {
    protected value : T
    …
    function foreach(f : T -> ()) -> () {
      f(value)
    }
  }

  class Node<T> extends Leaf<T> {
    private left : Leaf<T>
    private right : Leaf<T>
    …
    function foreach(f : T -> ()) -> () {
      left.foreach(f)
      right.foreach(f)
      f(value)
    }
  }

Diese Variante traversiert den Baum derart, dass das tiefste Element eines Teilbaums immer zuerst bearbeitet wird, wobei der linke Teil jedes Wurzelknotens immer zuerst vollständig durchlaufen wird, bevor sein rechter Teil angegangen wird, und noch bevor das im Knoten enthaltene Element bearbeitet wird. Wie der Baum genau durchlaufen wird, mag aber noch von anderen Faktoren abhängig sein, die aber nach außen hin verborgen sind.

Existiert eine solche foreach-Funktion in der Collection-Klasse, so kann man alles Mögliche und Nötige damit machen: Eine Funktion forall definieren, die genau dann true liefert, wenn alle in der Collection enthaltenen Elemente einer als Lambda-Ausdruck übergebenen Eigenschaft p genügen; oder eine exists-Funktion, die nur dann true liefert, wenn mindestens ein Element die gegebene Eigenschaft p erfüllt.

  class Collection<T> {
    …
    function forall(p : T -> Boolean) -> Boolean {
      b : Boolean = true
      foreach((e) -> b = b & p(e))
      return b
    }

    function exists(p : T -> Boolean) -> Boolean {
      b : Boolean = false
      foreach((e) -> b = b | p(e))
      return b
    }
  }

Hierzu wird jeweils eine Lambda-Funktion erzeugt, die die in den Funktionen definierte Boolesche Variable manipuliert. Dazu wird das übergebene Prädikat an jedem der Elemente geprüft und das Ergebnis mit der Variablen verknüpft.

Abbruchprobleme

Hierbei tauchen zwei Probleme auf. Das erste Problem betrifft die Möglichkeit, ob die Boolesche Variable b überhaupt im Lambda-Ausdruck manipuliert werden kann. In Java beispielsweise können nur diejenigen Variablen in Lambda-Ausdrücken verwendet werden, die effektiv final sind, also eben nicht geändert werden können. In diesem Fall müsste man erst ein veränderbares Objekt definieren, dessen Referenz dann final ist, aber der Inhalt sehr wohl änderbar ist.

Das zweite Problem betrifft den Umstand, dass immer über alle Elemente traversiert wird, obwohl das ja gar nicht mehr nötig ist, sobald etwa im Falle von forall das Prädikat das erste Mal false wird. Aus funktionaler Sicht ist das zwar irrelevant, aber aus Sicht der Performanz nicht akzeptabel.

Jetzt könnte man die Schnittstelle von foreach derart ändern, dass statt Void ein Boolean geliefert wird. Wenn dann das neue foreach ein false liefert, wird die Iteration beendet indem dieses false bis zum Aufrufer heraufgereicht wird. Um aber entscheiden zu können, ob ein Element dem Endekriterium genügt, muss der Lambda-Ausdruck also ein Boolean liefern.

Der Lambda-Ausdruck für dieses neue forall würde sich dann dementsprechend wie folgt ändern:

  (e) -> {
    b = b & p(e)
    return b
  }

Dann muss noch die foreach-Methode in den Collections angepasst werden, um den Booleschen Wert für das Abbruchkriterium weiter zu reichen. Beispielsweise würde sich dann die Methode für die Node in obigem Binärbaum wie nachstehend ändern müssen:

  function foreach(f : T -> Boolean) -> Boolean {
    if (!left.foreach(f)) {
      return false
    }
    if (!right.foreach(f)) {
      return false
    }
    return f(value)
  }

Das sieht leider nicht nur nicht mehr so schön aus, sondern auch gibt es jetzt nun noch eine Vermischung zwischen dem Traversieren und der Ablaufsteuerung. Das ist inakzeptabel, weil aus etwas relativ Einfachem jetzt etwas Kompliziertes und Fehleranfälliges wird.

Es wäre also schön, wenn es eine Möglichkeit gäbe, mehrere geschachtelte Funktionen mit einem einzigen Sprung zu verlassen. Und diese gibt es, wenngleich sie wohl einige Herzen zum Rasen bringen wird: Man kann einfach eine Ausnahme werfen.

Ein noch nicht einmal lokales goto

Bietet man eine spezielle Funktion (beispielsweise eine namens break) an, so könnte diese vergleichbar zum Verlassen einer Schleife dazu verwendet werden, um an einen wohldefinierten Punkt zurückzuspringen.

  function break() -> () {
    throw new BreakException()
  end

Da der Name foreach schon belegt ist, wählen wir eine neue Funktion traverse, die jene umschließt und eine eventuell geworfene BreakException abfängt.

  function traverse(f : T -> ()) -> () {
    try {
      foreach(f)
    } catch (BreakException e) {
      ;
    }
  }

Damit müssen Collection-Klassen nach wie vor nur die foreach-Methode implementieren, können aber mit einem break das vorzeitige Beenden beim Traversieren erreichen.

  function forall(p : T -> Boolean) -> Boolean{
    b : Boolean = true
    traverse((e) -> {
      b = b & p(e);
      if (!b) {
        break();
      }
    })
    return b
  }

Mit einer derartigen Kontrolle lassen sich auch Funktionen wie take(n) oder takeWhile(p) definieren, die eine Collection nur so lange durchläuft, bis die ersten n Elemente durchlaufen sind bzw. solange die Bedingung p erfüllt ist.

Bevor sich wieder irgendjemand aufregt, sei an dieser Stelle gleich erwähnt, dass ein derartiges break vom Prinzip her nichts anderes ist, als ein break in einer Schleife. Der Unterschied ist lediglich, dass nicht über Schleifengrenzen, sondern über Funktionsgrenzen hinweg gesprungen wird. Außerdem ist dieser Sprung ein Implementierungsdetail, das vor dem Programmierer verborgen werden kann, sodass er nicht in Versuchung kommt, selbst einen solchen "Schweinkram" zu machen.

Unabhängig davon muss man sich im Klaren darüber sein, dass der Aufwand für einen derartigen Sprung verhältnismäßig kostspielig sein kann und deshalb aus Performanzsicht nur dann in Frage kommt, wenn die Einsparungen im Mittel den zusätzliche Aufwand rechtfertigen. Aus Programmiersicht hat es der Programmierer aber auf jeden Fall einfacher.

Wie dem auch sei: Die foreach-Methode bietet so oder so eine schöne Basis für die Implementierung sämtlich erdenklicher Funktionen, die sich auf alle Elemente einer Collection beziehen – mit der Möglichkeit eines vorzeitigen Abbruchs.

Die Qual der Wahl

Ein klitzekleines Problem bleibt allerdings immer noch, das sich exemplarisch schön an der filter-Funktion demonstrieren lässt.

  class Collection<T> {
    …
    function filter(p : T -> Boolean) -> Collection<T>
  }

Diese liefert nämlich, wie die ihr verwandten Methoden, eine neue Collection zurück. Diese enthält im Falle von filter glücklicherweise nur diejenigen Elemente, für die das angegebene Prädikat p erfüllt ist.

  function filter(p : T -> Boolean) -> Collection<T> {
    collection : Collection<T>
    collection = new …
    traverse((e) -> {
      if (p(e)) {
        collection.add(e)
      }
    })
    return collection
  }

Hier stellt sich natürlich die Frage, welche konkrete Collection denn bei new geliefert werden soll? Handelt es sich beispielsweise um eine Menge ganzer Zahlen, so muss sicher wieder eine Menge ganzer Zahlen geliefert werden. Ist diese Zahlmenge sehr effizient als BitSet definiert, so würde es sich anbieten, hier als Ergebnis auch wieder ein BitSet zu liefern, da beim Filtern ja nur Elemente entfernt werden und somit ein BitSet wieder bestens geeignet wäre.

Selbiges gilt übrigens bei der map-Funktion nicht unbedingt, da dort beispielsweise die in dem BitSet gespeicherten Zahlen mit

  (x) -> 1000 * x

skaliert werden könnten. Damit würde sich aber mit der Vergrößerung der Zahlen auch der Speicherplatz eines resultierenden BitSets um das Tausendfache vergrößern, während die Größe bei den meisten anderen Set-Implementierungen gleich bliebe. Es ist also eine echte Kunst, für alle Transformationen einer Collection die richtige Ergebnisrepräsentation zu finden.

Fazit

Das Arbeiten mit Collections erleichtert die typischen Aufgaben auf Sammlungen von Objekten ungemein. Durch die Verkettung mit den Funktionen aus dem Werkzeugkasten á la filter, map und reduce können auch komplizierteste Anforderungen elegant und effizient umgesetzt werden. Der Umgang damit mag zwar anfangs etwas ungewöhnlich sein, aber mit der Zeit gewöhnt man sich schon daran.

Abschließend sei aber noch erwähnt, dass es für viele dieser Funktionen auch parallele Varianten gibt. Sind nämlich die nötigen Voraussetzungen erfüllt, so kann die Collection in mehrere Einzelteile zerlegt werden, um diese dann unabhängig voneinander, parallel zu bearbeiten. Abschließend müssen nur noch die Teilergebnisse gemäß ihrer Funktion zusammengefasst werden. Voilà! ()