Map i Reduce w JS

Napisałem artykuł o obserwablach, ale czegoś mi w nim zabrakło: Objaśnienia tak podstawowych pojęć i funkcji jak mapreduce. Observable na blogu pojawią się wkrótce, a ten krótki wpis ma na celu tylko lekkie wprowadzenie. Bardzo krótko i pobieżnie.

Jeśli oczekujesz zgłębiania programowania funkcyjnego w JS to natychmiast zamknij ten wpis. Nie jest dla Ciebie!

MapReduce to także nazwa konceptu w programowaniu, który polega na dzieleniu danych i zrównolegleniu oraz rozproszeniu wykonywanych na nich operacji map/reduce. Jest to podejście zaimplementowane m.in. w Hadoop czy nawet MongoDB. Ten wpis jednak o nich nie mówi.

mapreduce w JS

Jeśli nie używasz jeszcze funkcji map i reduce w JavaScripcie, to czas najwyższy zacząć 🙂 Wykorzystanie tych dwóch metod może sprawić, że Twój kod będzie znacznie czystszy i bardziej czytelny, a zrozumienie go będzie łatwiejsze. No i będziesz bardziej cool.

Map

Funkcja map jest jedną z bardziej rozpoznawalnych metod programowania funkcyjnego1. Służy do operowania i transformowania wszystkich elementów w tablicy.

Map przyjmuje tablicę, transformuje i zwraca tablicę o tej samej długości.

W JS ta funkcja to Array.prototype.map i wywołujemy ją np. w ten sposób:

const arr = [2, 6, 10];

arr.map(x => x * x) // [4, 36, 100]  

Tutaj tablicę z liczbami zamieniam (mapuję) na tablicę z kwadratami tych liczb.

Reduce

Reduce to fundament programowania funkcyjnego1. Podobnie do map, operuje na elementach tablicy, jednak zamiast kolejnej tablicy zwraca tylko pojedynczą wartość.

Reduce przyjmuje tablicę, transformuje i zwraca jedną wartość.

W JS ta funkcja to Array.prototype.reduce i wywołujemy ją np. w ten sposób:

const arr = [2, 6, 10];

arr.reduce((x, y) => x + y) // 18  

Tutaj obliczam sumę liczb w tablicy.

Map i reduce

Oczywiście Map i Reduce możemy łączyć (chain). Weźmy poprzedni przykład, chcemy policzyć sumę kwadratów liczb w tablicy:

const arr = [2, 6, 10];

arr  
    .map(x => x * x) // [4, 36, 100]
    .reduce((x, y) => x + y) // 140

Warto pamiętać o tym, że wewnątrz mapreduce nie powinny się dziać żadne efekty uboczne. Funkcje te służą tylko do transformacji jednych danych w drugie! Dzięki temu możliwa jest bardzo mocna optymalizacja tych metod i np. współbieżne przetwarzanie danych.

Niemutowalność

Bardzo istotnym atrybutem map i reduce jest to, że funkcje te zwracają nowe wartości i nie modyfikują przekazanej tablicy. Często jest to bardzo pożądana cecha! Dzięki temu zachowujemy oryginalną tablicę w niezmienionej formie, a inne komponenty, które mogą na niej polegać (hmm, nie powinny, ale to się często zdarza…), nie będą miały problemów z wykonywanymi przez nas operacjami. No, ale wróćmy do map/reduce, niemutowalność to trochę osobny temat, a tu miało być tylko krótkie wprowadzenie 🙂

Implementacja map w reduce

Napisałem, że reduce jest tutaj fundamentem, gdyż funkcja map jest tak naprawdę redundantna. Map można zaimplementować korzystając z reduce!

function map(array, fn) {  
    return array.reduce((newArray, el) => [...newArray, fn(el)], [])
}

map([1,2,3], x => x*x); // [1, 4, 9]  

Nie jest to pewnie najwydajniejsza implementacja, ani też wierne odwzorowanie Array.prototype.map, ale ważne, że działa. Teza udowodniona. Skoro wiemy już jak można implementować metody pomocniczne przy pomocy reduce, napiszmy bardzo przydatną funkcję flatMap, która zamienia tablicę tablic wartości w tablicę wartości (przyjmuje Array<Array<T>> i zwraca Array<U>):

// samo `reduce`
function flatMap(array, fn) {  
    return array.reduce((newArray, el) => [...newArray, ...fn(el)], [])
}

// alternatywnie `map` i `reduce`
function flatMap(array, fn) {  
    return array
      .map(x => fn(x))
      .reduce((a1, a2) => [...a1, ...a2]);
}

// alternatywnie przez `concat` i `map`
function flatMap(array, fn) {  
    return [].concat(...array.map(fn));
}

flatMap([[1,2], [3, 4]], x => x) // [1, 2, 3, 4]  
flatMap([1,2,3], x => [x,x]) // [1, 1, 2, 2, 3, 3]  

Podałem aż trzy alternatywne implementacje, żebyście mogli się bardziej oswoić z map/reduce. Która najbardziej przypada Wam do gustu?

Podobnie możemy też zaimplementować forEach, filter, czy też sum). Implementację ich pozostawiam jako ćwiczenie 🙂

Przykład z życia wzięty

Wyobraźmy sobie, że z API otrzymujemy dane w poniższym formacie:

const users = [  
    {id: 'a1', email: 'abc@xyz', name: 'Abc'},
    {id: 'b2', email: 'def@xyz', name: 'Def'},
    {id: 'c3', email: 'ghi@xyz', name: 'Ghi'},
    {id: 'd4', email: 'jkl@xyz', name: 'Jkl'},
]

Czyli tablica obiektów reprezentujących użytkownika. Każdy obiekt zawiera losowe id, email oraz imię. Nasza aplikacja jednak oczekuje innego formatu danych. Interesuje nas tylko ID oraz email i chcielibyśmy mieć je w jednym obiekcie:

const result = {  
    a1: 'abc@xyz',
    b2: 'def@xyz',
    c3: 'ghi@xyz',
    d4: 'jkl@xyz',
}

Czy możemy tutaj skorzystać z map i reduce? Tak! Najpierw każdego „użytkownika” zmapujemy na obiekt w postaci {[id]: email}, a następnie te obiekty zredukujemy do jednego:

users  
    .map(user => ({[user.id]: user.email}))
    .reduce((obj1, obj2) => Object.assign(obj1, obj2), {})

Zobacz Pen map reduce by Michał Miszczyszyn (@mmiszy) on CodePen.

Podsumowanie

Jaka jest zaleta tego rozwiązania? Na pewno zwięzłość. Dodatkowo, jak już wspomniałem, możliwe byłoby wykonanie tutaj wszystkich operacji całkowicie równolegle! I o ile prawdopodobnie żaden silnik JavaScript tego teraz nie robi, to jednak warto o tym pamiętać w kontekście innych technologii i języków programowania. Map reduce to koncept uniwersalny i powszechnie wykorzystywany.

Jeśli rozumiesz powyższe przykłady i czujesz się swobodnie z mapreduce to prawdopodobnie Observable będą dla Ciebie łatwe do zrozumienia. O tym mój kolejny wpis:

Observable – rxjs 5

Dla dociekliwych

Pomimo, że obiecałem, że będzie prosto i pobieżnie, to jednak warto zastanowić się nad tym jak bardzo uniwersalne koncepty zostały tutaj omówione… Przykładowo, jeśli w opisie funkcji map zamiast słowa „tablica” wstawimy „funktor” to prawdopodobnie nadal wszystko co napisałem będzie prawdą.

Czym jest funktor? Funktor to koncept z teorii kategorii, bardzo abstrakcyjnej gałęzi matematyki, na której bazuje całe programowanie funkcyjne. Teraz w zasadzie nie jest do końca istotne czym funktor jest, ważne co jeszcze jest funktorem… a funktorami są np. tablica, Promise albo Observable. Wszystko co tutaj opisałem, mimo że proste, jest bardzo uniwersalne i opisuje tak naprawdę szerokie pojęcia.

Czym na przykład jest funkcja Promise.resolve? To przecież flatMap gdy wywołamy ją na innym obiekcie Promise oraz map gdy na wartości niebędącej Promise. Warto się zastanowić dlaczego i jakie są tego implikacje 🙂

  1. Opinia własna 😉
  • Jako dopowiedzenie dorzucę, że Rauschmayer napisał ostatnio dość obszerny artykuł o flatMap: http://2ality.com/2017/04/flatmap.html

    Dodatkowo flatMap istnieje jako propozycja do dodania do standardu ECMAScript: https://github.com/bterlson/proposal-flatMap

    • O! Nie wiedziałem, że ktoś pracuje nad taką specyfikacją 🙂 Fajnie.

      Aczkolwiek jeśli chodzi o przykłady zastosowania flatMap z bloga Axela, to niestety do mnie nie przemawiają. W wielu miejscach prościej byłoby użyć po prostu filter.
      A pomysł, żeby funkcja przekazywana do flatMap mogła zwracać wartość lub tablicę – IMHO bardzo nietrafiony.

      • To prawda, Twoje przykłady mnie bardziej kupiły 😉

        • flatMap okazuje się być bardzo przydatny gdy zamiast tablic mamy Promise albo Observable 🙂

  • ciekawy artykuł, szczególnie ten przykład z users. Stosujesz w metodach map i reduce funkcje arrow function. Jest to jak najbardziej oki, sam tak często robię, ale od siebie dodam tylko małą uwagę. Otóż przy użyciu arrow function w formie funkcji zwrotnej nie można stosować drugiego argumentu MAP/REDUCE, który wskazywałby na wskaźnik THIS w funkcji callback (wynika to z podstaowywch założeń arrow function, których nie będę tutaj opisywał). Osobiście rzadko mi się zdarza z tego korzystać, aczkolwiek miałem już takie przypadki i wtedy trzeba stosować „tradycyjne”: function(argumenty) {…kod}. Ale to tylko tak na marginesie 🙂 Pozdrawiam

    • Oczywiście, słuszna uwaga. Arrow functions (funkcje strzałkowe) po prostu nie mają swojego this w ogóle, mają this leksykalne 🙂

  • Pingback: Observable – rxjs 5 – Type of Web()

  • Pingback: 9 rzeczy, których nie wiesz na temat Promise • Type of Web()