Clojure není jenom o na první pohled divné syntaxi plné kulatých závorek, ale také o převratných myšlenkách. Jednou takovou myšlenkou jsou transducers, "a powerful and composable way to build algorithmic transformations". Dobře, ale... Cože?

old fashioned

Abychom pochopili význam transducerů, začněme implementací high-order funkcí map, filter a reduce tak, jak byly ještě do nedávna většinou implementované:

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

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

var reduce = function(fn, init, col) {
  for (var i = 0, result = init; i < col.length; i++)
    result = fn(result, col[i]);
  return result;
};

Jejich použití vypadá následovně:

var inc = (n) => (n + 1);
var even = (n) => (n % 2 === 0);
var add = (a, b) => (a + b);

map(inc, [1, 2, 3]);// [2, 3, 4]
filter(even, [1, 2, 3]);// [2]
reduce(add, 0, [1, 2, 3]);// 6

Svůj účel samozřejmě výborně plní, ale trpí hned dvěma nedostatky:

  • pevná svázanost s jednou datovou strukturou
  • zbytečné průchody pokud mě výsledná kolekce nezajímá celá

reduce, reduce everywhere

Řešením obou dvou problémů jsou tzv. transducery. Název transducer v sobě spojuje slova transform a reduce. A přesně tak i funguje - v jednom kroku data jak transformuje, tak redukuje.

Pro pochopení transducerů je důležité si uvědomit možnosti a důležitost funkce reduce - každou transformaci (map, filter a další) jí lze totiž nahradit. Abychom tak mohli učinit, musíme definovat redukci concat. Následující změna původní funkčnost nijak nezmění, ale z transformačních funkcí odebere znalost, jak iterovat po poli:

var concat = (a, b) => (a.concat([b]);

var map = function(fn, col) {
  return reduce(function(prev, current) {
    return concat(prev, fn(current));
  }, [], col);
};

var filter = function(fn, col) {
  return reduce(function(prev, current) {
    return fn(current) ? concat(prev, current) : prev;
  }, [], col);
};

Lepší, ale jen tak na půl cesty. Stále je transformace svázaná s jednou strukturou. Co kdybychom chtěli transformovat něco jiného než pole, třeba strom? Implementujeme další map speciálně pro strom? A pro set, ...? Přesně tohle je hlavní myšlenka a důvod vzniku transducerů - ještě větší znovupoužitelnost základních transformačních funkcí. Pojďme z transformace vyhodit závislost na reduce:

var map = function(fn) {
  return function(prev, current) {
    return concat(prev, fn(current));
  };
}

reduce(map(inc), [], [1, 2, 3]);// [2, 3, 4]

Zase o trochu lepší, ale stále ne ideální. Datovou strukturu si už sice dáváme z venku, ale stále jsme omezeni možnostmi funkce concat. Co kdybychom chtěli třeba přidávat na začátek?

composable

Druhou myšlenkou transducerů je možnost kompozice:

var map = function(fn) {
  return function(reducer) {
    return function(prev, current) {
      return reducer(prev, fn(current));
    };
  };
};

var filter = function(fn) {
  return function(reducer) {
    return function(prev, current) {
      return fn(current) ? reducer(prev, current) : prev;
    };
  };
};

reduce(map(inc)(concat), [], [1, 2, 3]);// [2, 3, 4]
reduce(filter(even)(map(inc)(concat)), [], [1, 2, 3]);// [3]

Výborně! Právě jsme vytvořili dva tranducery, které jsou nezávislé jak na redukci, tak na datové struktuře. Akorát to použití ztratilo glanc. Pojďme to napravit zavedením funkce transduce, která přijímá čtyři argumenty (transducer, redukci, počáteční hodnotu redukce a kolekci) a vrací ztransredukovanou strukturu:

var transduce = function(xf, fn, init, col) {
  return reduce(xf(fn), init, col);
};

transduce(compose(filter(even), map(inc)), add, 0, [1, 2, 3, 4, 5]);// 8

lazy

-Kdybyste se měl popsat třemi slovy? -Líný.

Řekněme, že máme pole s několika tisíci položkami, které chceme prohnat jedním filtrem a jednou transformací, ale zároveň nás zajímá jenom prvních pět položek z výsledku. S klasickou implementací zpracování probíhá následovně: Pole s n položkami vejde do filtru, filter vrátí pole s m položkami, které je následně ztransformováno a vráceno jako nové pole s m položkami, načež se z něj použije jenom 5 položek! Klasické pojetí totiž vytváří tzv. mezivýsledky, které jsou zbytečné a zároveň omezující. Co kdybychom chtěli tu samou použít transformaci na generátor?

Transducery žádné mezivýsledky nevytváří a díky jejich nezávislosti můžeme stejnou kompozici použít jak na pole, tak třeba na ten generátor. Fungují tak, že kolekce se projde prvek po prvku a každý jednotlivý prvek se prožene celou kompozicí. V případě malých kolekcí rozdíl téměř nepoznáte, avšak při velkých kolekcích je rozdíl násobný. Obě řešení mají složitost O(n), ale zatímco transducery provedou vždy jen (maximálně, mohou být totiž lazy) n průchodů, klasické řešení jich v nejhorším případě udělá n * počet prvků v kompozici. Jediná nevýhoda oproti klasickému řešení je ta, že se volá více funkcí.

Začněme definicí našeho cíle:

transduce(compose(filter(even), map(double), take(2)), concat, [], [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);// [4, 16]
// počet volání:
// - filter: 4
// - map: 2
// - take: 2
// - concat 2

Potřebujeme definovat funkci take - transducer, který po n voláních vydá pokyn k zastavení redukce. Uděláme to tak, že si v kompozici budeme předávat nějaký wrapper, objekt s hodnotou a stavem (pokračuj, skonči):

var wrap = function(value, done) {
  return {value: value, done: done};
};

var take = function(amount) {
  return function(reducer) {
    var taken = 0;
    return function(prev, current) {
      return reducer(wrap(prev.value, ++taken >= amount), current);
    };
  };
};

Fungovat to ale zatím nebude, protože kromě funkce take s wrapperem nikdo nepočítá. Pojďme to změnit! Nejprve upravíme vstupní bod tak, že úvodní hodnotu redukce obalíme wrapperem:

var reduce = function(fn, init, col) {
  for (var i = 0, result = init; i < col.length; i++)
    result = fn(wrap(result, false), col[i]).value;
  return result;
};

Druhou nutnou úpravou je změna funkce concat na var concat = (a, b) => (a.value.concat([b]);. Teď by to mělo fungovat, ale stále to není lazy a definice redukcí je nehezká.

Předposledním krokem odstraníme value z redukce:

var xwrap = function(reducer) {
  return function(prev, current) {
    return wrap(reducer(prev.value, current), prev.done);
  };
};

var reduce = function(fn, init, col) {
  for (var i = 0, result = init; i < col.length; i++)
    result = xwrap(fn)(wrap(result, false), col[i]).value;
  return result;
};

var concat = (a, b) => (a.concat([b]);// <--

A posledním krokem uděláme funkci transduce "línou", čímž dosáhneme kýženého výsledku. Jednoduše budeme sledovat, jestli wrapper nezměnil stav na done = true. Jakmile se tak stane, redukování ukončíme a vrátíme výsledek:

var transduce = function(xf, fn, init, col) {
  for (var i = 0, reduce = xf(xwrap(fn)), result = init; i < col.length; i++) {
    result = reduce(wrap(result, false), col[i]);
    if (result.done) return result.value;// <--
    result = result.value;
  }
  return result;
};

Dalším krokem může být naučení transduce jak pracovat s generátorem a/nebo objektem.