JavaScript funcional: transductores

En este tercer artículo sobre programación funcional en JavaScript vamos a hablar de una operación realmente interesante: la transducción. Para ello vamos a tener que valernos de la composición de transformers que vimos anteriormente.

Composición de transformers

Las funciones map y filter que vimos en el artículo anterior tienen una diferencia respecto de las proporcionadas por Array.map y Array.filter: crean funciones que reciben un reducer y devuelven otro reducer.

language-javascript

⁠⁠⁠// map = (fn) => (reducer) => reducer

⁠const map = (mapper) => (reducer) => (acc, val) =>
⁠ reducer(acc, mapper(val));

const filter = (predicate) => (reducer) => (acc, val) =>
⁠ predicate(val) ? reducer(acc, val) : acc;

Lo que significa que nuestros transformers se pueden componer.

language-javascript

⁠(reducer) => reducer
⁠(reducer) => reducer
⁠ ⁠(reducer) => reducer ⁠...

Probemos con un ejemplo: podríamos necesitar filtrar primero aquellos elementos de un array que sean menores a 5, y calcular sus cuadrados. Creemos una función filter para la selección, y una función mapper para el cálculo de la potencia, y usémoslos con nuestra función reduce.

language-javascript
⁠⁠
⁠const data = [1, 2, 3, 4, 5];
⁠const lessThanFive = filter((x) => x < 5);
⁠const squares = map((x: number) => power(x, 2));

⁠const filteredAndSquared = reduce(
⁠ lessThanFive(squares(arrayConcat)),
⁠ data, []
⁠⁠);
⁠console.log(filteredAndSquared); // [1, 4, 9, 16]
Run me in Playground.

Y de nuevo, recordemos que dijimos que la composición es asociativa, pero no conmutativa:

f \circ g \neq g \circ f

 

De modo que podríamos sacar provecho de ello y, en caso de que fuera necesario, invertir las posiciones de lessThanFive y squares para primero calcular los cuadrados, y después obtener aquellos que son menores a cinco:

language-javascript

⁠⁠⁠const data = [1, 2, 3, 4, 5];
⁠⁠const squaredAndFiltered = reduce(
squares(lessThanFive(arrayConcat)),
⁠ data, []
⁠);
⁠console.log(squaredAndFiltered); // [1, 4]
Run me in Playground  .

O podríamos necesitar filtrar aquellos elementos cuyos cuadrados son menores que cinco:

language-javascript

⁠⁠const data = [1, 2, 3, 4, 5];
⁠const isSquareLessThanFive = filter((x) => power(x, 2) < 5);
⁠const filtered = reduce(
⁠ isSquareLessThanFive(arrayConcat),
⁠ data, ⁠[]
⁠);
⁠console.log(filtered); // [1, 2]
Run me in Playground.

E incluso obtener el cuadrado de cada elemento y reducirlo a un único valor:

language-javascript

⁠const accumulate = (a: number, b: number): number => a + b;

⁠⁠⁠const data = [1, 2, 3, 4, 5];
const filteredSquaredAndAccumulated = reduce(
⁠ lessThanFive(squares(accumulate)),
⁠ data,
⁠ 0
⁠);
⁠console.log(filteredSquaredAndAccumulated); // 30
Run me in Playground.

Y como nuestros transformers se pueden componer podemos hacer uso de nuestra función compose para todas estas operaciones:

⁠⁠language-javascript

⁠const compose = (...fns) => (items) =>
fns.reduceRight((acc, curr) => curr(acc), items);

⁠⁠⁠const data = [1, 2, 3, 4, 5];
⁠const filterAndSquare = compose(lessThanFive, squares);

⁠const filteredSquaredAndAccumulated = reduce(
⁠ filterAndSquare(accumulate), data, 0
⁠);

⁠console.log(filteredSquaredAndAccumulated); // 30
Run me in Playground.

Con esto tenemos ya todas las piezas necesarias para la operación que nos ocupa en este artículo: la transducción.

Transductores

Como decíamos, nuestras funciones filter y map tienen sus análogos en Array.filter y Array.map. Cabría por tanto preguntarse qué sentido tendría implementar nuestras propias funciones cuando el objeto Array ya tiene estos métodos.

Pues bien, planteémonos el siguiente caso: digamos que tenemos un array de gran tamaño, de diez millones de elementos, sobre el que tenemos que realizar diversas operaciones.

language-javascript

⁠const data = Array.from({ length: 10000000 }, (_, index) => index + 1);

Para procesarlo con Array.map y Array.filter tenemos que guardar primero el array entero en memoria. Y dado que ambos métodos devuelven un nuevo array, cada vez que llamemos a uno de ellos estaremos creando una copia del mismo.

Esto para un array de algunos centenares de elementos no supone un problema. Pero significa que no es un patrón escalable, ya que cuando tengamos una lista de un tamaño relevante podríamos estar consumiendo una cantidad considerable de recursos.

Además podemos tener otro problema: si algo va mal durante el procesamiento de nuestro array, al estar guardando los datos procesados en memoria, si la aplicación sufre algún percance podríamos perder los datos ya procesados.

Todo esto sucede porque los métodos de Array se ejecutan sucesivamente sobre el array completo: esto es, si queremos aplicar Array.map y Array.filter sobre un array, primero map lo recorrerá por completo transformando todos sus elementos y devolviendo un array nuevo, y luego filter hará lo mismo seleccionando aquellos elementos que nos interesen.

language-javascript

const data = ["1", "2", "3"];

⁠const result = data
⁠ .map((x) => (console.log("map"), Number(x)))
⁠ .filter((x) => (console.log("filter"), x % 2 !== 0));
⁠console.log(result); // [1, 3]

⁠// map
⁠⁠// map
⁠⁠⁠// map
⁠⁠⁠// filter
⁠⁠⁠⁠// filter
⁠⁠⁠⁠// filter
// [1, 3]
Run me in Playground.

Sería fantástico si pudiésemos desacoplar el procesamiento de cada elemento individual respecto del procesamiento del array completo.

Para ello podríamos empezar con un cambio: en lugar de hacer pasadas sucesivas sobre el array entero, podríamos intentar realizar primero todas las acciones necesarias sobre el primer elemento, luego sobre el segundo, etc., y así hasta el último elemento.

Pues bien, para lograrlo no nos hace falta hacer nada, porque esto es precisamente lo que ya están haciendo nuestras funciones map y filter con reduce.

language-javascript

⁠const data = ["1", "2", "3"];

⁠const toInt = map((x: string) => (console.log("map"), Number(x)));
⁠const isOdd = filter((x: number) => (console.log("filter"), x % 2 !== 0));
⁠const toIntAndFilterOdds = compose(toInt, isOdd);
⁠const result = reduce(toIntAndFilterOdds(concat), data, []);

⁠console.log(result);

⁠⁠⁠// map
⁠⁠⁠// filter
⁠⁠⁠⁠// map
⁠⁠⁠// filter
⁠⁠// map
⁠⁠⁠// filter
⁠// [1, 3]
Run me in Playground.

Si bien parece una diferencia menor, no lo es, ya que nos abre la puerta para transformar reduce en una función que, en lugar de recibir un transformer con un reducer ya aplicado, los reciba por separado y los aplique dentro de sí.

De este modo, en lugar de reducir con la función reduce:

language-javascript

⁠⁠const reduce = (reducer, iterable, initialValue) => {
⁠ let acc = initialValue;

⁠ for (const item of iterable) {
⁠ acc = reducer(acc, item);
⁠ }

⁠ return acc;
⁠};

Usaríamos una nueva función transduce, que tendría el siguiente aspecto:

language-javascript

⁠const transduce = (
⁠ transformer,
⁠ reducer,
⁠iterable,
⁠ initialValue
⁠) => {
⁠⁠ let acc = initialValue;
⁠ const transformedReducer = transformer(reducer);

⁠ for (const item of iterable) {
⁠ acc = transformedReducer(acc, item);
⁠ }

⁠ return acc;
⁠};

⁠const data = ["1", "2", "3"];

⁠const toInt = map((x: string) => (console.log("map"), Number(x)));
⁠const isOdd = filter((x: number) => (console.log("filter"), x % 2 !== 0));
⁠const toIntAndFilterOdds = compose(toInt, isOdd);
const result = transduce(toIntAndFilterOdds, concat, data, []);

⁠console.log(result);
⁠⁠
⁠⁠⁠// map
⁠⁠⁠// filter
⁠⁠⁠⁠// map
⁠⁠⁠// filter
⁠⁠// map
⁠⁠⁠// filter
⁠// [1, 3]
Run me in Playground.

Esto ya es un transductor: una función que toma un transformer —que pueden ser una serie de transformers compuestos— y un reducer —encargado de la operación de reducción—, más un iterable y un dato inicial, y reducirá el iterable sobre el dato inicial usando el transformer y el reducer.

Los transductores tienen una notable ventaja en cuanto a eficiencia frente al encadenamiento de métodos, como sucede con los métodos de Array. Esto se puede ver claro si recuperamos el array de gran tamaño que comentábamos más arriba.

Digamos que tenemos una lista de diez millones de productos con precios diferentes que vendemos a distancia, con un coste de envío de diez dólares. Los usuarios pueden financiar el pago en doce mensualidades, pero sólo si cada cuota mensual resultante es un número entero. Nos han pedido encontrar el mayor gasto que puede hacer un comprador que desee adquirir un producto financiable.

Podemos hacerlo con los métodos de Array:

language-javascript

⁠// Array with 10.000.000 elements
⁠const data = [
⁠ { name: "Product 1", price: 73 },
⁠ ...
⁠];

⁠const addShippingCosts = (product: Product) => product.price + 10;
⁠const isEligibleForFinancing = (price: number) => price % 12 === 0;
⁠const getBiggerExpense = (a: number, b: number) => (a > b ? a : b);

⁠console.time("array_methods");
⁠const result = data
⁠ .map(addShippingCosts)
⁠ .filter(isEligibleForFinancing)
⁠ .reduce(getBiggerExpense);

console.log(result); // 120

⁠console.timeEnd("array_methods"); // 141
⁠Run me in Playground 

Bien, obtenemos el resultado correctamente. Tomemos nota del tiempo que lleva ejecutar este código: a la hora de escribir esto el Playground de TypeScript muestra 141 ms., si bien puede cambiar según la máquina donde se ejecute.

Ahora probemos usando un transductor:

language-javascript

⁠// Array with 10.000.000 elements
⁠const data = [
⁠ { name: "Product 1", price: 73 },
⁠ ...
⁠];

⁠const eligibleForFinancing = filter(isEligibleForFinancing);
⁠const priceWithShippingCosts = map(addShippingCosts);
⁠const piped = pipe(eligibleForFinancing, priceWithShippingCosts);

⁠⁠console.time("transduce");
⁠const result = transduce(piped, getBiggerExpense, data, 0);
console.log(result); // 120
⁠console.timeEnd("transduce"); // 62
⁠Run me in Playground 

Como se ve se obtiene el mismo resultado, pero con una ganancia de eficiencia notable. Esto por supuesto dependerá de la complejidad temporal y espacial de los algoritmos que se usen: pero se aprecia que, frente a los mismos algoritmos, los transductores son más eficientes que el encadenamiento de métodos.

Ahora bien, una vez llamamos a transduce, este va a intentar procesar el array entero guardándolo en memoria, con una posible sobrecarga del sistema. En otros términos: el transducer actual es evaluado ansiosamente.

Lo que nosotros buscamos en realidad es una función que nos permita procesar los datos con evaluación perezosa de modo que los datos sean procesados bajo demanda únicamente. Y si recordamos nuestro primer artículo, en él mencionamos que la evaluación perezosa en JavaScript se puede implementar con generadores.

Veamos un ejemplo de un generador:

language-javascript

⁠function* lazySum(a, b) {
⁠ yield a + b;
⁠}

⁠let result = lazySum(1, 3);
⁠console.log(result); // {} (not evaluated yet)
⁠console.log(result.next().value); // 4
Run me in Playground.

Por tanto intentemos implementar nuestro transduce para que evalue perezosamente los datos:

language-javascript

function* lazyTransduce(
⁠ transformer,
⁠ reducer,
⁠ iterable,
⁠ initialValue
⁠) {
⁠ const transformedReducer = transformer(reducer);
⁠ let acc = initialValue;

⁠ for (const item of iterable) {
⁠ acc = transformedReducer(acc, item);

⁠ yield acc;
⁠ }
⁠}

En lugar de retornar, lazyTransduce va a devolver un generador que devolverá su estado en acc por cada vez que se ejecute su método next().

language-javascript

⁠// Array with 10.000.000 elements
⁠const data = [
⁠ { name: "Product 1", price: 73 },
⁠ ...
⁠];

⁠const eligibleForFinancing = filter(isEligibleForFinancing);
⁠const priceWithShippingCosts = map(addShippingCosts);
⁠const piped = pipe(eligibleForFinancing, priceWithShippingCosts);

⁠const result = lazyTransduce(piped, getBiggerExpense, data, 0);

⁠console.log(result.next().value); // 0
⁠console.log(result.next().value); // 0
⁠console.log(result.next().value); // 0
⁠⁠console.log(result.next().value); // 120
⁠⁠⁠console.log(result.next().value); // 120
⁠⁠⁠console.log(result.next().value); // 120
⁠...
Run me in Playground 

Aquí es la evaluación perezosa la que nos va a permitir procesar los datos bajo demanda y realizar acciones sobre los mismos teniendo pleno control sobre el ritmo y periodicidad al que lo hacemos.

Por ejemplo, podríamos querer persistir los datos cada determinado número de elementos, o enviar notificaciones a servicios externos sobre los datos encontrados. Y todo esto podríamos hacerlo además sin causar ninguna sobrecarga del sistema, ya que la complejidad espacial es insignificante y sólo se utilizará la memoria necesaria para cada paso de la iteración.

Y al igual que sucedía cuando usábamos nuestra función reduce, a nuestros transductores podemos pasarles diferentes reducers para acumular los datos de distintas formas. Por ejemplo, concatenando los datos en un nuevo array con concat:

language-javascript

⁠const data = [
⁠ { name: "Product 1", price: 74 },
⁠ { name: "Product 2", price: 93 },
⁠ { name: "Product 3", price: 110 },
⁠ { name: "Product 5", price: 82 },
⁠];

⁠const eligibleForFinancing = filter(isEligibleForFinancing);
⁠const priceWithShippingCosts = map(addShippingCosts);
⁠const piped = pipe(eligibleForFinancing, priceWithShippingCosts);

const result = lazyTransduce(piped, concat, data, []);

⁠console.log(result.next().value); // [84]
⁠console.log(result.next().value); // [84]
⁠console.log(result.next().value); // [84, 20]
⁠console.log(result.next().value); // [84, 120]
⁠console.log(result.next().done); // true
Run me in Playground 

Hay mucho que decir sobre los transductores, especialmente porque hay numerosas implementaciones: se encuentran detrás de métodos ofrecidos por distintas librerías, como sucede con pipe de RxJS, o son directamente soportados como en el caso de Ramda. Sucede con ellos lo mismo que con otras utilidades: no siempre tiene sentido utilizar las propias por el trabajo y riesgo que conlleva desarrollar la implementación más eficiente posible. Sin embargo es interesante tener presente su existencia y sus fundamentos, ya que nos muestra con claridad su potencial.

Como es habitual, el código se puede ejecutar en el Playground de TypeScript, así como está disponible para descarga en git.antoniodiaz.me.

Si tienes cualquier duda o has encontrado un error no dudes en escribirme a la dirección que figura en el pie.