... & Kontext: Map/Reduce

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.

Ein wesentlicher Bestandteil vieler Anwendungen sind Datenanhäufungen beliebiger Art. Auch wenn diese Collections völlig unterschiedlich strukturiert sein können, ist ihnen doch gemein, dass sie ihre Daten sammeln. Aber alle diese Daten wären nutzlos, wenn man nicht irgendetwas mit ihnen machen könnte.

In nichtfunktionalen Sprachen macht man das sehr oft mit Iteratoren, die der Reihe nach alle Elemente der Collection liefern, um so mit ihnen arbeiten zu können.

it : Iterator<T> = … ;
while (it.hasNext()) {
    doSomethingWith(it.next());
}

Diese Art der Iteration ist bei Collections, die als Listen oder Sequenzen strukturiert sind, auch unproblematisch, aber bei baumartigen oder allgemein rekursiven Strukturen eine kleine Katastrophe. Denn derartige Strukturen müssen für diese Darreichungsform erst einmal "platt gekloppt" werden. Das ist insofern tragisch, weil sich doch die rekursiven Strukturen – wie ihr Name schon sagt – so einfach rekursiv bearbeiten ließen. So benötigt man oft einen Stack, um den Zustand des Iterators korrekt zu repräsentieren; eben der Stack, der einem sonst bei einem rekursiven Durchlaufen aller Elemente geschenkt würde.

Die Verlagerung der Iteration von außen nach innen überlässt es nun der Collection selbst, wie die einzelnen Elemente erreicht werden, und mit Hilfe der Lambda-Ausdrücke können wir das, was zu erledigen ist, sozusagen hineinreichen. Ein Lambda-Ausdruck könnte so Elemente summieren, zusammenfügen, aussortieren und sonst noch alles machen, was das Herz begehrt.

Von Begehrlichkeiten der Entwickler

Wenn man sich aber die Herzenswünsche anschaut, stellt man fest, dass es tatsächlich nur ganz wenige Begehrlichkeiten sind, die befriedigt werden wollen. Und zwei davon sind das Abbilden von gegebenen Elementen auf beliebige andere (map) und das Reduzieren aller Elemente auf ein einziges (reduce).

Beim Mapping handelt es sich wirklich um beliebige Abbildungen. Interessiert man sich etwa bei einer Sammlung von Personen nur für das Alter der Personen, handelt es sich auch dabei um eine Abbildung. Kombiniert man eine solche Abbildung nun mit der map-Funktion, erhält man eine neue (nicht notwendig gleich strukturierte) Collection, die Elemente der gewünschten Zielmenge enthalten.

people : Collection<Person> = … ;
ages : Collection<Double>;
ages = people.map(p -> p.age);

Eine Collection<T> wird also mit Hilfe einer Funktion T S in eine Collection<S> umgewandelt.

Collection<T>.map(f : T -> S) -> Collection<S>

Interessant dabei ist, dass ein solches map nicht unbedingt eine Verdopplung der Datenmenge zur Folge hat. Denn es muss eigentlich zu diesem Zeitpunkt noch nicht einmal über die Collection iteriert werden. Man kann sich das Mapping – vorausgesetzt die Collection bleibt unverändert, was in funktionalen Sprachen ja immer gegeben ist – auch als Paar aus Collection und Lambda-Ausdruck vorstellen. Auch ein erneutes Mapping hätte dann auch fast keine direkten Auswirkungen, lediglich der Lamda-Ausdruck würde mit dem neuen Mapping kombiniert werden.

students : Collection<Student> = … ;
points : Collection<Double> = students.map(s -> s.points)
grades : Collection<Grade> = points.map(p -> convertToGrade(p))

oder auch kürzer

grades : Collection<Grade> = students
    .map(s -> s.points)
    .map(p -> convertToGrade(p))

Um die Punkte der Studenten in Noten umzuwandeln, hätte man natürlich auch nur eine Funktion nehmen können.

grades : Collection<Grade> = students
    .map(s -> convertToGrade(s.points))

Aber aus Sicht der funktionalen Programmierung macht das keinen Unterschied, denn das ist genau das, was das zweimalige map macht.

Über den Zeitpunkt

Wenn aber hier gar keine neue Collection entsteht, wann findet denn dann überhaupt das Mapping statt? Die Antwort ist recht einfach: Nur dann, wenn es nötig ist.

Ein Anwendungsfall, der das Mapping nötig macht, ist das Reduzieren. Soll etwa die Bestnote bestimmt werden, sucht man einfach nach dem Maximum der Punkte oder dem Minimum der Note. Das Maximum lässt sich iterativ bestimmen, indem man der Reihe nach alle Punkte durchgeht.

Double z = 0.0;
for (p : points) {
    z = max(z, p)
}    

Gibt es keine Studenten und damit keine Punkte, ist das Maximum 0. Andernfalls wird das bisherige Maximum z mit dem aktuellen Wert p aus der Collection verglichen und eventuell das Maximum korrigiert. Am Ende bleibt ein einziger Wert z: Die Collection wurde auf diesen einen Wert reduziert.

Das funktioniert natürlich auch allgemein und – was noch viel wichtiger ist – lässt sich zustandslos implementieren. Allgemein gibt es also einen Anfangswert z, der typischerweise das neutrale Element der Reduktion beschreibt. Würde man etwa die Summe aller Punkte bilden wollen, so wäre das 0; bräuchte man das Produkt, so wäre das 1. Dann ruft man eine beliebige (aber passende) Funktion mit dem ersten Element der Collection und diesem Startwert auf und nimmt dann deren Ergebnis als neuen Startwert.

Collection<T>.reduce(z : S, f : (S, T) -> S) -> S

Mit Hilfe einer Funktion, die ein beliebiges Originalelement vom Typ T mit einem Startwert z vom Typ S kombiniert wird eine Collection<T> zu einem einzigen Wert S reduziert.

points.reduce(0, max)

Wird nun die Collection mit Hilfe der reduce-Funktion auf das Maximum reduziert, muss natürlich auch das Mapping stattfinden. Jetzt erst müssen die Punkte aus den Studenten extrahiert werden. Analog muss bei

best : Grade = students
    .map(s -> s.points)
    .map(p -> convertToGrade(p))
    .reduce(0, min)

erst mit dem reduce der Aufwand für die Berechnungen der Mappings betrieben werden. Aber zusätzlicher Speicher wird dafür nicht benötigt, da bei der Ausführung der map-Funktion keine Zwischenergebnisse in Form von Collections angelegt werden müssen.

Nicht, dass ein falscher Eindruck entsteht, aber bei diesen einzelnen Ergebnissen bei der Reduktion kann es sich durchaus auch wieder um Collections oder kompliziertere Ergebnisse handeln. Auch wenn obige Beispiele dazu verleiten könnten, anzunehmen, dass S und T von der gleichen Art sein müssen, können sie beliebige Formen annehmen. So können mit map und reduce genauso Textdokumente und Tabellen aus Personaldaten erstellt werden wie auch Summen und Jahresabschlüsse.

Fork/Join

Übrigens lassen sich – unter der Voraussetzung, dass die Collections unveränderlich sind – Daten mit map und reduce in den meisten Fällen sogar parallel verarbeiten. Das kann man etwa durch einen Fork/Join-Algorithmus erreichen. Bei dem wird die zu reduzierende Menge einfach in zwei gleich große Teile zerlegt und diese dann von zwei Threads unabhängig voneinander bearbeitet (Fork). Liegt das Ergebnis beider Threads vor, werden diese beiden noch zu einer reduziert (Join). Diese Halbierung kann man natürlich rekursiv beliebig oft fortsetzen, bis die Zahl der verfügbaren Threads erschöpft ist oder eine weitere Zerlegung aus Performanzsicht nicht mehr sinnvoll erscheint.

Abschließend sei noch bemerkt, dass die Funktion reduce oft auch fold genannt wird, von denen jeweils die Varianten reduceLeft und reduceRight bzw. foldLeft und foldRight angeboten werden. Die Unterscheidung für reduce und fold kommt dadurch zustande, dass auch reduziert werden kann, ohne einen Startwert zur Hilfe zu nehmen. So lässt sich etwa die Summe von Zahlen auch ohne neutrales Anfangselement aus allen Zahlen einer Collection berechnen.

Collection<T>.foldLeft(z : S, f : (S, T) -> S) -> S
Collection<T>.reduceLeft(f : (S, T) -> S) -> S

So ist etwa in Scala das reduce eine Funktion ohne Startwert, während fold einen Startwert hat. So gesehen ist für nicht leere Collection reduce ein Spezialfall von fold, indem der erste Wert der Collection als Startwert genommen wird und der verbleibende Rest dann mit Hilfe des fold reduziert wird.

Dass darüber hinaus noch zwischen reduceLeft und reduceRight unterschieden werden muss, ist dem Umstand geschuldet, dass es durchaus darauf ankommen kann, ob die Werte von links nach rechts oder von rechts nach links reduziert. So liefert ja die einfache Reduktion der Liste [1, 2, 3] mit Minus entweder

von links nach rechts ((1 - 2) - 3) = -4
von rechts nach links (1 - (2 - 3)) = 2

was ja etwas völlig anderes ist.

Mit map und reduce ist so ein einfaches Arbeiten möglich, unter dem auch die Lesbarkeit nicht leiden muss. Im Grunde genommen können auch alle Probleme mit Hilfe dieser Verfahren gelöst werden, aber darf dabei natürlich nicht vergessen, dass wir nicht ohne Grund seit einigen Jahrzehnten eher objektorientiert programmieren. Trotzdem hat das Funktionale in seiner Domäne unschlagbare Vorteile gegenüber dem Objektorientierten. Und wer einmal mit der funktionalen Programmierung angefangen hat, der will in der Regel nie wieder zurück.

PS: Setzt man das funktionale Paradigma mit der Oper gleich, könnte man es auch mit den Worten von Edward Lewis aus Pretty Woman sagen: People's reactions to opera the first time they see it is very dramatic; they either love it or they hate it. If they love it, they will always love it. If they don't, they may learn to appreciate it, but it will never become part of their soul. ()