Konsole & …: 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.

In den vergangenen Folgen wurde die reduce-Funktion bereits zweimal erwähnt: Einerseits als Funktion höherer Ordnung, andererseits im Rahmen des Currying. Doch hinter reduce steckt weitaus mehr als nur ein handliches Beispiel. Diese Funktion gehört nämlich gemeinsam mit einigen weiteren zu den grundlegenden Bausteinen der funktionalen Programmierung.

Nochmals kurz zusammengefasst vereint reduce die einzelnen Werte eines Arrays zu einem einzelnen Wert, beispielsweise um aus einer Reihe von Zahlen deren Summe zu bilden:

var sum = [ 2, 3, 5, 7, 11 ].reduce(function (left, right) {
  return left + right;
}, 0);
console.log(sum); // => 28

Doch was, wenn nicht alle Werte eines Arrays zu einem einzelnen Wert zusammengefasst werden sollen, sondern jeder Wert für sich verarbeitet werden soll?

Die map-Funktion

In diesem Fall hilft die map-Funktion, die auf jeden einzelnen Wert eines Arrays eine übergebene Funktion aufruft und die jeweiligen Ergebnisse wiederum in einem neuen Array ablegt. Ebenso wie reduce lässt sich auch die map-Funktion leicht von Hand implementieren:

var map = function (values, fn) {
  var result = [];
  for (var i = 0; i < values.length; i++) {
    result.push(fn(values[i]));
  }
  return result;
};

Anschließend kann man diese Funktion verwenden, um beispielsweise die Quadratwerte einer Reihe von Zahlen zu berechnen:

var primes = [ 2, 3, 5, 7, 11 ];
var squares = map(primes, function (prime) {
  return prime * prime;
});
console.log(squares); // => [ 4, 9, 25, 49, 121 ]

Analog zu reduce ist allerdings auch map bereits serienmäßig in JavaScript enthalten. Da die eingebaute Funktion auf dem Prototyp von Arrays definiert ist, lässt sie sich komfortabel aufrufen:

var primes = [ 2, 3, 5, 7, 11 ];
var squares = primes.map(function (prime) {
  return prime * prime;
});
console.log(squares); // => [ 4, 9, 25, 49, 121 ]

Der map-reduce-Algorithmus

Besonders interessant an map ist der kombinierte Einsatz mit reduce, wodurch auf einfachem Weg ausgesprochen leistungsfähige Funktionen entstehen. Beispielsweise lassen sich durch die Kombination von map und reduce leicht die Anzahl der Wörter eines Satzes ermitteln:

• Zunächst bildet map die einzelnen Zeichen des Satzes auf numerische Werte ab: Jedes Leerzeichen wird auf den Wert 1 abgebildet, alle anderen Zeichen auf den Wert 0.
• Anschließend bildet reduce aus diesen Werten deren Summe.
• Addiert man schließlich noch 1 hinzu, erhält man die Anzahl der Wörter des ursprünglichen Satzes.

Der folgende Codeabschnitt zeigt die Implementierung dieser Funktion in JavaScript, wobei der Initialwert der reduce-Funktion geschickt verwendet wird, um das Endergebnis um den Wert 1 zu erhöhen:

var countWords = function (text) {
  var chars = text.split('');

  var result = chars.map(function (char) {
    return char === ' ' ? 1 : 0;
  }).reduce(function (left, right) {
    return left + right;
  }, 1);

  return result;
};

var numberOfWords = countWords('the native web');
console.log(numberOfWords); // => 3

Sind map und reduce identisch?

Bemerkenswert an den beiden Funktionen map und reduce ist, dass sich die eine mit der anderen implementieren lässt, letztlich also lediglich einen Spezialfall darstellt. Der reduce-Schritt besteht dabei darin, die gewünschte Funktion auf jeden einzelnen Wert anzuwenden und die Ergebnisse nach und nach in einem Array zu speichern:

var map = function (values, fn) {
  return values.reduce(function (base, value) {
    base.push(fn(value));
    return base;
  }, []);
};

tl;dr: Die aus vergangenen Folgen bereits bekannte reduce-Funktion ist mit der nicht minder wichtigen Funktion map verwandt. Während die eine alle Werte eines Array zu einem Wert zusammenfasst, verarbeitet die andere alle Werte einzeln und erzeugt als Ergebnis ein neues Array. Letztlich stellt map allerdings lediglich einen Spezialfall von reduce dar. ()