Co to jest Transducer?

Dzisiaj przedstawię ciekawą koncepcje z programowania funkcyjnego, a mianowicie transducer, czyli według Wikipedii przetwornik.

Wstęp

Transducer’y są częścią programowania funkcyjnego. Dzięki nim możemy zawierać skomplikowane operacje, które normalnie wymagają takich funkcji jak map czy filter, które ze względu na różne sygnatury (do funkcji przekazujemy inne argumenty i co innego zwracamy), nie można składać (ang. compose). Wygląda to tak, że zapisujemy operacje map czy filter pod postacią reducer’a, czyli funkcji, którą można użyć w metodzie reduce dla tablic, lub jej odpowiednika dla innych obiektów. Jeśli mamy kilka reducer’ów, które mają być uruchomione jeden za drugim, możemy je złożyć ze sobą do postaci pojedynczego reducer’a, który możemy wtedy przekazać do metody reduce. Dzięki temu przetwarzamy tablicę/listę lub inną strukturę tylko raz, co przyspiesza działanie programu.

Jest to możliwe, ponieważ funkcja reduce jest bardzo potężna, nazywana czasami scyzorykiem szwajcarskim operacji na tablicach.

Przyjrzyj się poniższemu kodowi:

array
  .map(fn1)
  .filter(fn2)
  .reduce(fn3);

W tej funkcji operacja iteracji po elementach nastąpi 3 razy, pomyśl co się stanie, gdy tablica będzie bardzo duża, albo gdy mamy do czynienia ze strumieniem. Taka operacja jest bardzo kosztowna. Na szczęście, dzięki ludziom sprytniejszym ode mnie, mamy możliwość wykonania składania (ang. compose) tych funkcji, ale najpierw musimy je przetworzyć, aby uzyskać funkcje postaci takiej jak funkcja sum, którą można przekazać do funkcje reduce.

var sum = (accumulator, element) => accumulator + element;

Uwaga: Wszędzie w kodzie używam var zamiast const aby nie utrudniać życia gdy używa się konsoli i chce się jeszcze raz zdefiniować daną funkcje. W docelowym kodzie można użyć const dla definiowanych funkcji.

Kompozycja funkcji

Na początek w skrócie co to jest składanie. Może pamiętasz z matematyki w szkole średniej, jest to łączenie dwóch funkcji w jedną funkcje. Zazwyczaj w matematyce zaznacza się to tak:

h(x) = f ∘ g = g(f(x))

W JavaScript wygląda to tak:

function compose(f, g) {
   return function(x) {
      return g(f(x));
   }
}

var square = (x) => x * x;
var minus1 = (x) => x - 1;

gdy musimy wywołać obie funkcje wielokrotnie na różnych liczbach, np.:

minus1(square(10));
minus1(square(20));
minus1(square(30));

warto jest utworzyć jedną funkcje, która wykona obie operacje. Możemy to zrobić za pomocą funkcji compose:

var square_1 = compose(square, minus1);

square_1(10);
square_1(20);
square_1(30);

Poniżej przykład bardziej uniwersalnej funkcji compose, która działa dla wielu funkcji:

var compose = (...fns) => x => fns.reduceRight((y, f) => f(y), x);

reduceRight to funkcja, która działa jak reduce, ale zwija wyniki w odwrotnej kolejności.

Jeśli nie znasz jeszcze funkcji map, reduce oraz filter dla tablic, koniecznie przeczytaj najpierw artykuł Wszystko co powinieneś wiedzieć o funkcjach w JavaScript.

Funkcje map oraz filter jako reducer

Wracając do transducer’ów i naszego pierwszego przykładu:

array
    .map(fn1)
    .filter(fn2)
    .reduce(fn3);

Napiszmy te funkcje jako reducer’y, najpierw map:

var map = fn => (accumulator, element) => accumulator.concat(fn(element));

mając taką funkcje, możemy zamiast Array::map, użyć Array::reduce, w celu uzyskania takiego samego efektu jak Array::map:

[0, 1, 2, 3, 4, 5, 6].reduce(map((x) => x * x), []);
// [0, 1, 4, 9, 16, 25, 36]

kolejna funkcja to filter jako reducer:

const filter = fn => (accumulator, element) =>
    fn(element) ? accumulator.concat(element) : accumulator;

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10].reduce(filter((x) => x % 2 == 0, []);
// [2, 4, 6, 8, 10]

Mając te dwie funkcje, możemy je połączyć:

0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
    .reduce(map(x => x + 1), [])
    .reduce(filter(x => x % 2 === 0), []);
    // [2, 4, 6, 8, 10]

W obu reducer’ach mamy operacje, która łączy element z akumulatorem czyli wynikową wartością, która rośnie w miarę wykonywania reducer’a:

var map = fn => (accumulator, element) => accumulator.concat(fn(element));

var filter = fn => (accumulator, element) =>
    fn(element) ? accumulator.concat(element) : accumulator;

Powyższe funkcje wyglądają tak samo jest funkcja sum:

const sum = (akumulator, element) => akumulator + element;

w tym przypadku sum, operatorem jest + natomiast w naszych funkcjach, jest to Array::concat. Możemy wyciągnąć tą operacje na zewnątrz i umieścić w funkcji, którą przekażemy jako argument:

// Ważna jest kolejność, najpierw funkcja a potem łącznik
var map = f => reducing => (result, input) =>
    reducing(result, f(input));

var filter =  predicate => reducing => (result, input) =>
    predicate(input) ? reducing(result, input) : result;

Mając takie funkcje możemy ich użyć w taki sposób:

var concat = (xs, x) => xs.concat(x);

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
    .reduce(map(x => x + 1)(concat), [])
    .reduce(filter(x => x % 2 === 0)(concat), []);
    // [2, 4, 6, 8, 10]

Łączenie reducer’ów

Zauważ że sygnatura funkcji concat, która występuje jako parametr reducing, czyli nasz łącznik wynikowy:

var concat = (xs, x) => xs.concat(x);

ma postać

(result, element) => result

tak samo jak reducer (funkcja przekazywane do reduce) tak samo jak i w funkcji map czy funkcji filter. Dlatego też można zastąpić funkcję concat innym reducer’em np.:

var reducer = filter(x => x % 2 === 0)(concat);
map(x => x + 1)(reducer);

Można to zapisać w jednej linijce. Sygnatura takiej funkcji jest dokładnie taka sama jak:

map(x => x + 1)(concat)

można więc ją użyć w funkcji reduce:

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
    .reduce(map(x => x + 1)(filter(x => x % 2 === 0)(concat)), [])
// [2, 4, 6, 8, 10]

teraz już jest fajniej, ponieważ mamy tylko jedną iteracje po tablicy.

Transducer

Możemy uprościć ten kod używając funkcji compose:

var transducer = compose(map(x => x + 1), filter(x => x % 2 === 0));

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
    .reduce(transducer(concat), []);
// [2, 4, 6, 8, 10]

Więc czym dokładnie jest transducer? Jest to funkcja, która opisuje jakiś algorytm, utworzona za pomocą pojedynczej funkcji lub za pomocą ich składania (ang. function composition). Transducer jest uniwersalny i abstrakcyjny ponieważ dopiero funkcja z jaką go wywołamy określa co transducer przetwarza. W tym przykładzie transducer został wywołany z funkcją concat i operuje na tablicach, ale nic nie szkodzi na przeszkodzie, aby transducer operował np. na obietnicach. Oto przykład:

var promise_resolver => (acc, promise) => {
    return acc.then(x => promise.then(y => x + y));
}

var filter =  fn => reducing => async (result, input) =>
    await fn(input) ? reducing(result, input) : result;

var transducer = compose(
    map(async (x) => (await x) + 1),
    filter(async (x) => (await x) % 2 === 0)
);

// jeśli korzystasz z konsoli w Google Chrome możesz pominąć wrapper async.
(async function() {
    // przygotowanie tablicy obietnic
    var promises = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9].map(n => Promise.resolve(n));

    var result = await promises.reduce(transducer(promise_resolver), Promise.resolve(0));
    console.log(result); // 30
})();

Z powyższego kodu uzyskamy wynik 30 czyli tyle samo co:

var transducer = compose(mapping(x => x + 1), filtering(x => x % 2 === 0));

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
    .reduce(transducer((a,b) => a + b), 0);
    // 30

niestety funkcja filter wymagała przepisania na funkcje asynchroniczną, ponieważ predykat zwraca Obietnicę. Nie musimy natomiast nic więcej robić z funkcją map oraz wywołaniem funkcji reducing w funkcji filter, ponieważ kontroluje go nasz łącznik (funkcja concat).

Można także poprawić obie funkcje oraz łącznik, aby operowały na obietnicach i aby działały tak samo na liczbach jak i na obietnicach. Oto jakby wykładał taki kod:

var map = fn => reducing => async (result, input) =>
    await reducing(result, fn(await input));

var filter =  fn => reducing => async (result, input) =>
    await fn(await input) ? await reducing(result, input) : result;

var concat = async (xs, x) => (await xs).concat(await x);

Mając powyższy kod, można użyć naszego pierwszego złączonego transducer’a:

var transducer = compose(map(x => x + 1), filter(x => x % 2 === 0));

(async function() {
    var result = await [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
        .reduce(transducer(concat), []);
    console.log(result); // [2, 4, 6, 8, 10]
})();

tak samo będzie wyglądał kod dla obietnic

(async function() {
    var promises = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9].map(n => Promise.resolve(n));

    var result = await promises.reduce(transducer(concat), Promise.resolve([]));
    console.log(result); // [2, 4, 6, 8, 10]
})();

Niestety dla zwykłych liczb wynikiem także będzie obietnica.

Jeśli nie znasz jeszcze składni async..await, albo nie znasz jeszcze obietnic możesz przeczytać o nich w artykułach o asynchronicznym kodzie w JavaScript.

Poniżej przedstawiam trochę bardziej skomplikowany kod, który sprawdza typ i nie zwraca obietnicy, gdy wartością nie są obietnice:

// funkcja pomocnicza wyższego rzędu, wywołująca funkcje fn z aktualną wartością
var resolve = (value, fn) => {
    if (value instanceof Promise) {
         return value.then(fn);
    } else {
        return fn(value);
    }
};

var map = fn => reducing => (result, input) => {
    return reducing(result, resolve(input, fn));
};

var filter =  predicate => reducing => (result, input) => {
    const next = cond => cond ? reducing(result, input) : result;
    return resolve(resolve(input, predicate), next);
}

// connector to też funkcja wyższego rzędu,
// która upraszcza pisanie asynchronicznych funkcji łącznikowych

var connector = fn => (accumulator, element) => {
   return resolve(accumulator, (acc) => {
      return resolve(element, (e) => fn(acc, e));
   });
}

var concat = connector((acc, item) => acc.concat(item));
var sum = connector((a, b) => a + b);

// standardowy transducer
var transducer = compose(map(x => x + 1), filter(x => x % 2 === 0));

// kod asynchroniczny
(async function() {
   var promises = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9].map(n => Promise.resolve(n));

   var result = await promises.reduce(transducer(concat), Promise.resolve([]));
   console.log(result); // [2, 4, 6, 8, 10]
})();

// kod dla zwykłej tablicy
var result = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
    .reduce(transducer(concat), []);
console.log(result); // [2, 4, 6, 8, 10]

Na koniec demo na CodePen, na którym możesz poeksperymentować.