Ícone do site Taller

Transducers: o que são e como eles podem ajudar a otimizar o seu código funcional

Fala pessoal! Inspirado no tweet abaixo do Ben Awad (e suas reações) resolvi escrever um post explicando o que são Transducers e como eles podem ajudar a otimizar a execução do seu código.


Fonte: Twitter

Ao me deparar com o conceito de Transducers, foi algo “mind-blowing”, ao menos para mim. 

Quando programo no dia a dia tentando usar o paradigma funcional, algumas coisas sempre me deixam bugado, como o fato de precisar iterar diversas vezes sobre uma lista caso eu queira aplicar um `map` e um `filter`, por exemplo. Como minha experiência técnica era mais voltado para a programação imperativa/orientada a objetos, esse tipo de problema era resolvido com apenas um “loop”. 

Antes de continuar quero dar um aviso: este artigo exige conhecimento técnico prévio em composição de funções e higher-order functions, ele é bem extenso e exigirá um tempo grande e uma alta  dedicação de concentração também. Espero que gostem!

 

Por que usar Transducers?

Vamos a um exemplo bem simples para mostrar o principal motivo de adicionar essa ferramenta ao seu toolbox. Vamos analisar o seguinte código:

const list = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];

const double = (n) => n * 2;
const addOne = (n) => n + 1;
const isBiggerThanTen = (n) => n > 10;
const sum = (acc, value) => acc + value;
const sumList = list
  .map(addOne)
  .map(double)
  .filter(isBiggerThanTen)
  .reduce(sum, 0);

console.log(sumList);

 

Podemos ver que executamos duas vezes a função map, uma vez a função filter e, por último, a função reduce. Para cada “chaining”, ou seja, encadeamento de funções, o JS cria um novo array intermediário antes de ir para a próxima operação na cadeia de chamadas.

Para listas pequenas este tipo de abordagem não é tão problemática, mas quando temos listas com milhares de registros ou streams infinitos (Observables), esse conceito se torna importante por questões de otimização. Agora imaginem uma lista com dois milhões de registros. Isso duplicaria esses valores a cada nova chamada tendo um consumo de memória excessivo e um alto tempo de processamento/execução.

Quero mostrar aqui como os Transducers podem nos ajudar nesse tipo de situação, mas ao invés de começar pela definição conceitual do que é um Transducer, vou começar mostrando na prática como ele funciona.

Vou colocando alguns trechos de código e vamos explorando e melhorando o código passo a passo.

 

Começando com composições

Vamos começar pelo exemplo que mostrei acima. Antes de falarmos de Transducers, somente olhando o código já podemos criar uma pequena melhoria nele e fazer uma composição dessas duas funções de mapeamento. Reparem a nova versão com as funções compostas:

const R = require("ramda");
const list = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];

const double = (n) => n * 2;
const addOne = (n) => n + 1;
const isBiggerThanTen = (n) => n > 10;
const sum = (acc, value) => acc + value;
const sumList = list
  .map(addOne)
  .map(double)
  .filter(isBiggerThanTen)
  .reduce(sum, 0);

console.log(sumList);


//composição das funções addOne e double usando o compose do Ramda.
const addOneAndDouble = R.compose(double, addOne);


//mesmo resultado com uma chamada `map` a menos.
const sumListComposta = list
  .map(addOneAndDouble)
  .filter(isBiggerThanTen)
  .reduce(sum, 0);

console.log(sumListComposta);

 

Voilá, com essa pequena alteração já conseguimos remover uma chamada dos métodos map que havia no código.

 

Tentando compor mapping e filter functions

Até que foi bem fácil, certo? Mas e se tentarmos ir além e aplicarmos a mesma ideia de composição, mas agora com a função isBiggerThanTen? O que acontecerá?

const R = require("ramda");
const list = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];

const double = (n) => n * 2;
const addOne = (n) => n + 1;
const isBiggerThanTen = (n) => n > 10;
const sum = (acc, value) => acc + value;
const sumList = list
  .map(addOne)
  .map(double)
  .filter(isBiggerThanTen)
  .reduce(sum, 0);

console.log(sumList);

const addOneAndDouble = R.compose(double, addOne);

const sumListComposta = list
  .map(addOneAndDouble)
  .filter(isBiggerThanTen)
  .reduce(sum, 0);

console.log(sumListComposta);

const addOneAndDoubleAndIsBiggerThan = R.compose(
  isBiggerThanTen,
  double,
  addOne
);


// Esperávamos o valor 102 mas resultado foi 6
console.log(list.map(addOneAndDoubleAndIsBiggerThan).reduce(sum, 0));

 

O resultado foi completamente diferente do esperado. Era esperado o valor 102 mas o resultado foi 6. O que aconteceu ali?

Vamos analisar de uma outra forma como a composição é feita entre as três funções sem usar o compose da biblioteca Ramda.

isBiggerThanTen(double(addOne(1)));

 

Reparem que o resultado da função é um booleano (true ou false), ao invés de trazer um novo valor numérico. No final, o reduce recebe uma lista de valores true ou false e o JavaScript faz a conversão de true para 1 e false para 0 ao realizar a soma para cada valor. 

Por que não conseguimos compor essas três funções simultaneamente?
Vamos analisar.

Se olharmos bem, podemos ver que as assinaturas das funções são diferentes. A assinatura de função é composta pelos parâmetros de entrada, os tipos de cada parâmetro (dependendo da linguagem), e o seu tipo de retorno.

As funções addOne e double possuem a mesma assinatura. Recebem a mesma quantidade de parâmetro e retornam um novo valor numérico, mas a assinatura da função isBiggerThanTen é diferente.

Ela recebe um valor da mesma forma que as outras, mas em vez de transformar em um número ela retorna um outro tipo, neste caso, um booleano.

Na realidade, por esses comportamentos, podemos classificar essas funções em dois tipos diferentes:

Refatorando em direção aos Transducers

E agora, será que tem alguma forma de resolver esse problema de composição entre diferentes tipos de funções? É aqui que entram os Transducers.

Como dito anteriormente, vamos melhorando nosso código aos poucos até atingirmos o objetivo final. 

O primeiro passo para entender esse novo conceito é alterar as funções addOne, double e isBiggerThanTen  para uma nova versão, de forma que eu consiga usar o método reduce. Quero conseguir ter o mesmo resultado tanto se chamar map(fn) ou filter(fn), quanto quando chamar reduce(fnReducer), sendo essa fnReducer  a nova versão reducer da função.  

const { double, isBiggerThanTen, sum, addOne } = require("./operations");

const list = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20];

const doubleReducer = (acc, value) => acc.concat(double(value));
const addOneReducer = (acc, value) => acc.concat(addOne(value));

const isBiggerThanTenReducer = (acc, value) =>
  isBiggerThanTen(value) ? acc.concat(value) : acc;

console.log(`double using map: ${list.map(double)}`);
console.log(`double using reduce: ${list.reduce(doubleReducer, [])}`);
console.log("\n\n");
console.log(`addOne using map: ${list.map(addOne)}`);
console.log(`addOne using reduce: ${list.reduce(addOneReducer, [])}`);
console.log("\n\n");
console.log(`isBiggerThanTen using filter: ${list.filter(isBiggerThanTen)}`);
console.log(
  `isBiggerThanTen using reduce: ${list.reduce(isBiggerThanTenReducer, [])}`
);

 

Agora demos o primeiro passo para aprender sobre os Transducers.

Antes de continuarmos, quero falar sobre mais um tipo de função existente além das mapping functions e predicate functions, que é a reducer function.

 

Agora continuando, o código ainda tem espaço para melhoria. As funções doubleReducer e addOneReducer  são praticamente idênticas, alterando somente a função que calcula o novo valor.

Vamos refatorá-las para serem usadas como uma mapReducer genérica. Ela servirá para criar funções reducers a partir de uma mapping function. Dessa forma, poderemos usar ela tanto para criar a função doubleReducer, quanto a função addOneReducer.

const { double, isBiggerThanTen, sum, addOne } = require("./operations");

const list = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20];

// função que cria funções map-reducers a partir de uma função “mapping”
const mapReducer = (map) => (acc, value) => acc.concat(map(value));


// versão reducer do double criada a partir da função genérica mapReducer
const doubleReducer = mapReducer(double);

// versão reducer do addOne criada a partir da função genérica mapReducer
const addOneReducer = mapReducer(addOne);

const isBiggerThanTenReducer = (acc, value) =>
  isBiggerThanTen(value) ? acc.concat(value) : acc;

console.log(`double using map: ${list.map(double)}`);
console.log(`double using reduce: ${list.reduce(doubleReducer, [])}`);
console.log("\n\n");
console.log(`addOne using map: ${list.map(addOne)}`);
console.log(`addOne using reduce: ${list.reduce(addOneReducer, [])}`);
console.log("\n\n");
console.log(`isBiggerThanTen using filter: ${list.filter(isBiggerThanTen)}`);
console.log(
  `isBiggerThanTen using reduce: ${list.reduce(isBiggerThanTenReducer, [])}`
);

 

Agora, uma breve explicação. Criamos a nova função mapReducer que recebe 3 parâmetros, mas para facilitar a composição de funções futuramente, utilizei a técnica conhecida como currying, onde ao passar a função de mapeamento como primeiro argumento, a função mapReducer retornará uma nova versão reducer das funções double ou addOne.

Vamos aplicar o mesmo princípio, mas agora, para criar uma função que crie funções filter reducers. Da mesma forma que a mapReducer, a função filterReducer será usada para criar a versão reducer da função isBiggerThanTen.

const { double, isBiggerThanTen, sum, addOne } = require("./operations");

const list = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20];
const mapReducer = (map) => (acc, value) => acc.concat(map(value));

// função que cria funções filterReducers a partir de uma função “predicate”
const filterReducer = (predicate) => (acc, value) =>
  predicate(value) ? acc.concat(value) : acc;

const doubleReducer = mapReducer(double);
const addOneReducer = mapReducer(addOne);


// versão reducer do isBiggerThanTen criada a partir do filterReducer
const isBiggerThanTenReducer = filterReducer(isBiggerThanTen);

console.log(`double using map: ${list.map(double)}`);
console.log(`double using reduce: ${list.reduce(doubleReducer, [])}`);
console.log("\n\n");
console.log(`addOne using map: ${list.map(addOne)}`);
console.log(`addOne using reduce: ${list.reduce(addOneReducer, [])}`);
console.log("\n\n");
console.log(`isBiggerThanTen using filter: ${list.filter(isBiggerThanTen)}`);
console.log(
  `isBiggerThanTen using reduce: ${list.reduce(isBiggerThanTenReducer, [])}`
);

 

Já fizemos bastante coisa, mas será que existe alguma outra refatoração que podemos aplicar aqui? A resposta é: sim!

Ainda existe um comportamento em comum entre as funções filterReducer e mapReducer. Que comportamento é esse?

Em ambas as funções, existe um código que pega o valor, o adiciona ao final do array e retorna o array com o novo item adicionado ao final. Podemos dizer que esse trecho de código “combina” dois valores em um.

No nosso caso, recebe uma lista e um valor, e adiciona o valor ao final da lista. Vamos refatorar e extrair essa lógica também, pois ela faz um papel importante nesse conceito, mas falaremos sobre isso com maiores detalhes depois.

Para essa refatoração vamos precisar criar a função combinator, a qual faz a combinação entre dois valores, e alterar as funções mapReducer e filterReducer para que elas utilizem essa nova lógica.

const { double, isBiggerThanTen, sum, addOne } = require("./operations");

const list = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20];


//nova função criada a partir da lógica em comum entre as funções mapReducer e filterReducer
const combinator = (acc, value) => acc.concat(value);


// alterado mapReducer para receber a função combinator
const mapReducer = (map) => (combinator) => (acc, value) =>
  combinator(acc, map(value));

// alterado filterReducer para receber a função combinator
const filterReducer = (predicate) => (combinator) => (acc, value) =>
  predicate(value) ? combinator(acc, value) : acc;


//versão reducer double usando nova lógica combinator
const doubleReducer = mapReducer(double)(combinator);

//versão reducer addOne usando nova lógica combinator
const addOneReducer = mapReducer(addOne)(combinator);


//versão reducer isBiggerThanTen usando nova lógica combinator
const isBiggerThanTenReducer = filterReducer(isBiggerThanTen)(combinator);

console.log(`double using map: ${list.map(double)}`);
console.log(`double using reduce: ${list.reduce(doubleReducer, [])}`);
console.log("\n\n");
console.log(`addOne using map: ${list.map(addOne)}`);
console.log(`addOne using reduce: ${list.reduce(addOneReducer, [])}`);
console.log("\n\n");
console.log(`isBiggerThanTen using filter: ${list.filter(isBiggerThanTen)}`);
console.log(
  `isBiggerThanTen using reduce: ${list.reduce(isBiggerThanTenReducer, [])}`
);

 

Vamos às explicações: a função combinator tem somente a tarefa de pegar 2 valores e retornar um só. Que tipo de função se encaixa nessa descrição?

Isso mesmo, uma reducer function. Então podemos dizer que  a função combinator é uma reducer function.

Além disso, adicionamos mais um parâmetro as funções mapReducer e filterReducer. Esse parâmetro indica que função de combinação será utilizada dentro do reducer. Usamos o currying aqui também para facilitar a composição de funções.

Agora vamos parar um pouco e revisar tudo o que já fizemos até agora. 

Criamos as funções utilitárias mapReducer e filterReducer, e com elas somos capazes de produzir reducer functions que fazem tanto o mapeamento de um valor, quanto a filtragem de valores.

Para se ter uma função reducer capaz de fazer o trabalho do map ou do filter, a partir destas novas funções, devemos informar dois parâmetros. Primeiro a função de mapping ou predicate, e segundo a função que faz a combinação dos valores. Vamos passar esses parâmetros em passos diferentes para visualizar melhor o que está acontecendo.

const {
  double,
  isBiggerThanTen,
  addOne,
  combinator,
  mapReducer,
  filterReducer,
} = require("./operations");


// nesse primeiro passo é gerada uma função intermediária
// que ainda não está pronta para ser usada como uma reducer function
const doubleIntermediateReducer = mapReducer(double);
const addOneIntermediateReducer = mapReducer(addOne);
const isBiggerIntermediateReducer = filterReducer(isBiggerThanTen);



// segundo passo - para termos uma função reducer ainda precisamos
// aplicar o combinator
const doubleReducer = doubleIntermediateReducer(combinator);
const addOneReducer = addOneIntermediateReducer(combinator);
const isBiggerReducer = isBiggerIntermediateReducer(combinator);

 

Reparem bem na assinatura da funções Intermediate. Todas elas recebem uma função que combina os valores e retorna uma função reducer.

Lembra-se quando disse lá atrás que não era possível fazer composição das funções addOne e isBiggerThanTen porque suas assinaturas não eram compatíveis? Aqui conseguimos alinhar as funções para que elas recebam e retornem os mesmos tipos. Já que conseguimos alinhar essas assinaturas, será possível fazer a composição? Vamos tentar agora.

const {
  double,
  isBiggerThanTen,
  addOne,
  combinator,
  mapReducer,
  filterReducer,
} = require("./operations");
const { compose } = require("ramda");

const doubleIntermediateReducer = mapReducer(double);
const addOneIntermediateReducer = mapReducer(addOne);
const isBiggerIntermediateReducer = filterReducer(isBiggerThanTen);

// para termos uma função reducer que possa ser usada, ainda precisamos // aplicar o combinator
const doubleReducer = doubleIntermediateReducer(combinator);
const addOneReducer = addOneIntermediateReducer(combinator);
const isBiggerReducer = isBiggerIntermediateReducer(combinator);

const addOneAndDoubleReducerAndIsBiggerThanTen = compose(
  addOneIntermediateReducer,
  doubleIntermediateReducer,
  isBiggerIntermediateReducer
)(combinator);

console.log([1, 2, 3, 4, 5, 6].reduce(addOneAndDoubleReducerAndIsBiggerThanTen, []));

 

Conseguiram ver?  Agora que as funções intermediárias possuem a mesma assinatura é possível realizar a composição facilmente. Podemos dizer que essas funções intermediárias são funções “higher-order reducers”, ou seja, recebem um parâmetro e retornam uma nova função reducer.

Conseguimos executar todas as três etapas em uma única chamada ao método reduce, com isso, podemos dizer que já atingimos nosso objetivo parcial.

Isso é o Transducer. Conceitualmente falando, podemos dizer que o Transducer é uma composição de higher-order reducer functions, ou ainda, uma função que recebe uma função reducer e retorna outra função reducer.

É importante ressaltar aqui que, apesar do compose funcionar da direita para esquerda, deve-se colocar a ordem correta do que deve ser executado. Isso acontece devido a forma como as funções são compostas. Vamos ver abaixo como funciona na prática. 

A primeira função a ser executada durante a composição é a isBiggerIntermediateReducer. A função espera o parâmetro combinator, neste caso vamos passar a própria a função combinator que criamos como argumento. 

Ao chamar a função isBiggerIntermediateReducer com o parâmetro combinator será retornada a função reducer da função isBiggerThanTen. Vamos chamar de reducerIsBigger. O código desta função reducer será algo como o seguinte:

return function reducerIsBigger(acc, value) {
  return isBiggerThanTen(value) ? combinator(acc, value) : acc;
};

 

Continuando, a segunda função a ser chamada será a função doubleIntermediateReducer, que também espera receber um combinator. Neste caso, ela receberá a função reducerIsBigger que é o resultado da chamada da função anterior com o combinator. Ao executar, será retornada a versão reducer da função double. Vamos chamá-la de reducerDouble. O código será algo como o seguinte:

return function reducerDouble(acc, value) {
  return reducerIsBigger(acc, double(value))
}

 

E finalmente, será executada a função addOneIntermediateReducer. Como as outras, ela também espera receber um combinator como parâmetro. Agora ela receberá a função reducerDouble que foi o resultado da chamada anterior. Vamos ver como ficou a composição final:

return function reducerAddOne(acc, value) {
  return reducerDouble(acc, addOne(value))
},

 

Reparem que cada função Intermediate, primeiro sua lógica de filtro ou mapeamento é executado para depois chamar a função combinator

Olhando como fica a composição final das funções podemos ver que primeiro será adicionado 1 aos valores e depois será chamada a função reducerDouble, a qual duplica os valores e, ao final, será chamada a função reducerIsBigger que filtra os valores que não atendem ao critério.

Ou seja, apesar de ser o último da composição, primeiro será executado o addOne, depois será executado o double, para finalmente chamar o isBiggerThanTen.

Aliás, sempre que houver composição de funções que são higher-order functions, isto é, composição de funções que retornam funções, a execução será da esquerda para direita.

Certo, além de todo esse conceito que já é muito legal, nesse exemplo simples conseguimos substituir a chamada de um map e um filter em uma única chamada reduce

Voltando ao exemplo inicial, após aplicar os mapping e filters era feito uma soma de todos os valores. Vamos atualizar o código com todo nosso novo aprendizado:

const {
  double,
  isBiggerThanTen,
  addOne,
  combinator,
  sum,
  mapReducer,
  filterReducer,
} = require("./operations");
const { compose } = require("ramda");

const doubleIntermediateReducer = mapReducer(double);
const addOneIntermediateReducer = mapReducer(addOne);
const isBiggerIntermediateReducer = filterReducer(isBiggerThanTen);

const addOneAndDoubleAndIsBiggerThanTenReducer = compose(
  addOneIntermediateReducer,
  doubleIntermediateReducer,
  isBiggerIntermediateReducer
)(combinator);

const list = [1, 2, 3, 4, 5, 6];

const total = list.reduce(addOneAndDoubleAndIsBiggerThanTenReducer, []).reduce(sum, 0);

console.log(total);

 

Estão vendo que ainda temos 2 reducers? Oh gosh, como a gente consegue transformar isso em um só? O segredo está na função combinator.

Vamos olhar atentamente e comparar ela com a função sum. Se olharmos bem podemos ver que, apesar dos tipos serem diferentes, ela fazem a mesma coisa, ou seja, recebem dois valores e retornam um só. Ambas são consideradas reducer functions.

Vamos tentar substituir pela sum, para ver o que acontece:

const {
  double,
  isBiggerThanTen,
  addOne,
  combinator,
  sum,
  mapReducer,
  filterReducer,
} = require("./operations");
const { compose } = require("ramda");

const doubleIntermediateReducer = mapReducer(double);
const addOneIntermediateReducer = mapReducer(addOne);
const isBiggerIntermediateReducer = filterReducer(isBiggerThanTen);

const addOneAndDoubleReducer = compose(
  addOneIntermediateReducer,
  doubleIntermediateReducer,
  isBiggerIntermediateReducer
)(combinator);

const sumReducer = compose(
  addOneIntermediateReducer,
  doubleIntermediateReducer,
  isBiggerIntermediateReducer
)(sum);

const list = [1, 2, 3, 4, 5, 6];

const total = list.reduce(addOneAndDoubleReducer, []).reduce(sum, 0);

console.log(list.reduce(sumReducer, 0));
console.log(total);

 

Uau, funcionou! Não sei vocês conseguem ver a beleza disso, mas ao mesmo tempo estamos fazendo uma composição das funções e somando seus valores.

O que essa alteração quer dizer para nós? Ela nos diz que é possível fazer composição de funções reducers usando outras funções reducers. Vamos visualizar outro exemplo:

const {
  double,
  isBiggerThanTen,
  addOne,
  combinator,
  sum,
  mapReducer,
  filterReducer,
} = require("./operations");
const { compose } = require("ramda");

const strConcat = (a, b) => a + " - " + b;

const doubleIntermediateReducer = mapReducer(double);
const addOneIntermediateReducer = mapReducer(addOne);
const isBiggerIntermediateReducer = filterReducer(isBiggerThanTen);

const Transducer = compose(
  addOneIntermediateReducer,
  doubleIntermediateReducer,
  isBiggerIntermediateReducer
);

const list = [1, 2, 3, 4, 5, 6];
console.log(list.reduce(Transducer(strConcat), ""));

 

Neste caso, eu fiz uma concatenação dos valores existentes na lista e os transformei numa string somente trocando a função que uso para combinação.

Espero que vocês tenham conseguido chegar até aqui comigo. Tentei mostrar de forma simples o que é o Transducer e como aplicar ele. Tirando a função compose que estamos usando do Ramda, o restante do conceito foi todo mostrando usando vanilla JS. Dá um certo trabalho montar tudo isso né?

Agora vou mostrar como faz usando Ramda e deixando alguns comentários para fins de entendimento.


const R = require("ramda");
const list = [1, 2, 3, 4, 5, 6];

const Transducer2 = R.compose(
  //map reducer da função addOneAndDouble
  R.map(
    //composição addOne e double
    R.compose(R.multiply(2), R.add(1))
  ),
  //filter reducer da função isBiggerThanTen
  R.filter(
    //função isBiggerThanTen
    R.flip(R.gt)(10)
  )
);


// realizar o reduce dos Transducers gerando a lista no final
console.log(R.transduce(Transducer2, R.flip(R.append), [], list));

// realizar o reduce dos Transducers gerando a soma
console.log(R.transduce(Transducer2, R.add, 0, list));


Bom, chegamos ao fim na deste artigo e espero que vocês tenham gostado! Coloquei alguns links abaixo como referência de onde aprendi sobre Transducers. Se quiserem ter uma visão ainda mais aprofundada sobre esse assunto eu altamente recomendo a leitura dos links.

Podem ficar a vontade para escreverem nos comentário ou qualquer dúvida também, podem me perguntar no Twitter, meu perfil é @arthuralmeidap.

 

Referências sobre Transducers:

 

Sair da versão mobile