The path to transducers in pure javascript

If you have heard about the so-called “transducers”, but you still do not use them in JavaScript development, today you have a chance to find answers to the questions: “What are transducers?” And “How to use them?”. This will allow you to understand whether they are needed in your projects, and, if needed, will help to start using them.



It will be about how to write code that is designed to build data conversions that are well suited for building pipelines and does not consume too much memory. In order to properly understand the concept of transducers, we start with simpler mechanisms, reducers, or functions for convolving data.

Reductors

A reducer is a function that accepts a drive object and an object object at the input, and then puts this element into the drive. For example, here is the reducer:
')
(acc, val) => acc.concat([val]) . If the drive passed to it is an array [1, 2, 3] , and the element is the number 4 , it will return the array [1, 2, 3, 4] .

 const acc = [1, 2, 3]; const val = 4; const reducer = (acc, val) => acc.concat([val]); reducer(acc, val) ///=> 1, 2, 3, 4 

In our case, the reducer returns the result of the concatenation of the list of elements and the single element passed to it.

Here is another similar reducer: (acc, val) => acc.add(val) . It is suitable for any object that has a .add() method that, among other things, returns this object (like Set.prototype.add () ). Our reducer adds the element transferred to it to the drive using the method. add() drive.

 const acc = new Set([1, 2, 3]); const val = 4; const reducer = (acc, val) => acc.add(val); reducer(acc, val) ///=> Set{1, 2, 3, 4} 

Here is a function that creates an array from any iterated object using our concatenated reducer.

 const toArray = iterable => { const reducer = (acc, val) => acc.concat([val]); const seed = []; let accumulation = seed; for (value of iterable) {   accumulation = reducer(accumulation, value); } return accumulation; } toArray([1, 2, 3]) //=> [1, 2, 3] 

You can make the variables reducer and seed parameters of the new function (the host, by analogy with the just considered, and the argument iterable ), getting a universal reducing function.

 const reduce = (iterable, reducer, seed) => { let accumulation = seed; for (const value of iterable) {   accumulation = reducer(accumulation, value); return accumulation; } reduce([1, 2, 3], (acc, val) => acc.concat([val]), []) //=> [1, 2, 3] 

JavaScript evolves towards a convention of writing functions, such as our reduce , the first parameter of which is the reducer. If you rewrite this function in JavaScript Allongé style, you get the following.

 const reduceWith = (reducer, seed, iterable) => { let accumulation = seed; for (const value of iterable) {   accumulation = reducer(accumulation, value); } return accumulation; } reduce([1, 2, 3], (acc, val) => acc.concat([val]), []) //=> [1, 2, 3] //    : reduceWith((acc, val) => acc.concat([val]), [], [1, 2, 3]) //=> [1, 2, 3] 

Arrays in JavaScript have a built-in .reduce method. This method behaves in the same way as the above functions reduce and reduceWith .

 [1, 2, 3].reduce((acc, val) => acc.concat([val]), []) //=> [1, 2, 3] 

Now the function (acc, val) => acc.concat([val]) creates an unnecessary load on the memory, so we can replace it with such a reducer: (acc, val) => { acc.push(val); return acc; } (acc, val) => { acc.push(val); return acc; } (acc, val) => { acc.push(val); return acc; } .

It should be noted here that the record of the form (acc, val) => (acc.push(val), acc) looks better from a semantic point of view, but the comma operator can confuse those who are not familiar with the peculiarities of its use. Usually in production code this is best avoided.

In any case, we will have a reducer that collects the elements into an array. Give it a name and try to pass it to the reduceWith function.

 const arrayOf = (acc, val) => { acc.push(val); return acc; }; reduceWith(arrayOf, [], [1, 2, 3]) //=> [1, 2, 3] 

Here is another reducer.

 const sumOf = (acc, val) => acc + val; reduceWith(sumOf, 0, [1, 2, 3]) //=> 6 

You can write reducers that collapse an iterable object of one type (say, an array) into an object of another type (for example, into a number).

Dressing up of reducer

In JavaScript, it is easy to write functions that return other functions. Here, for example, a function that allows you to create reysery.

 const joinedWith = separator =>   (acc, val) =>     acc == '' ? val : `${acc}${separator}${val}`; reduceWith(joinedWith(', '), '', [1, 2, 3]) //=> "1, 2, 3" reduceWith(joinedWith('.'), '', [1, 2, 3]) //=> "1.2.3" 

In addition, in JS it is completely natural to create functions that take other functions as arguments.

Decorators are functions that, taking a certain function as an argument, return another function that is semantically related to the argument. For example, this function takes a function with two arguments, a binary one, if we speak in the language of functional programming, and decorates it by adding one to its second argument.

 const incrementSecondArgument = binaryFn =>   (x, y) => binaryFn(x, y + 1); const power = (base, exponent) => base ** exponent; const higherPower = incrementSecondArgument(power); power(2, 3) //=> 8 higherPower(2, 3) //=> 16 

In this example, the higherPower function is a power function, decorated by adding a unit to its exponent argument. Thus, calling higherPower(2,3) gives the same result as power(2,4) . We have already worked with similar functions, our reducers are also binary functions. They can be decorated.

 reduceWith(incrementSecondArgument(arrayOf), [], [1, 2, 3]) //=> [2, 3, 4] const incremented = iterable =>   reduceWith(incrementSecondArgument(arrayOf), [], iterable); incremented([1, 2, 3]) //=> [2, 3, 4] 

Mapping functions

We have just created a function for mapping, which, taking an iterated object, returns the result of processing its values ​​by increasing each of them by one. When developing programs on JS, we constantly resort to mapping, but, of course, the functions implementing this mechanism are usually expected to be somewhat larger than the production of copies of numerical arrays, the elements of which are increased by one. Take another look at the incrementSecondArgument function.

 const incrementSecondArgument = binaryFn =>   (x, y) => binaryFn(x, y + 1); 

Since we use it for decorating reduser, we give it a more appropriate name.

 const incrementValue = reducer => (acc, val) => reducer(acc, val + 1); 

Now, when reading the code, it is immediately obvious that incrementValue takes a reducer as an argument and returns another reducer, which, before processing the element passed to it, adds one to it. The logic of "incrementing" can be made in the parameter.

 const map = fn =>   reducer =>     (acc, val) => reducer(acc, fn(val)); const incrementValue = map(x => x + 1); reduceWith(incrementValue(arrayOf), [], [1, 2, 3]) //=> [2, 3, 4] 

Although all this may look unusual for those who are not used to functions that accept functions as arguments and return other functions that, again, accept functions as arguments, we can put the map(x => x + 1) construction map(x => x + 1) everywhere, where you can use incrementValue . Thus, we can write the following.

 reduceWith(map(x => x + 1)(arrayOf), [], [1, 2, 3]) //=> [2, 3, 4] 

And, since our map decorator can decorate any reducer, it is permissible to combine the results of incrementing numbers, forming a string, or summarize them.

 reduceWith(map(x => x + 1)(joinedWith('.')), '', [1, 2, 3]) //=> "2.3.4" reduceWith(map(x => x + 1)(sumOf), 0, [1, 2, 3]) //=> 9 

Armed with the techniques described above, we will try to find the sum of squares of numbers from one to ten.

 const squares = map(x => power(x, 2)); const one2ten = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]; reduceWith(squares(sumOf), 0, one2ten) //=> 385 

As you can see, we succeeded. Now we go further - let's talk about filters.

Filters

Let's return to our first reducer.

 const arrayOf = (acc, val) => { acc.push(val); return acc; }; reduceWith(arrayOf, 0, one2ten) //=> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 

What if you want the output to get only numbers that are more than five? Make it easy.

 const bigUns = (acc, val) => { if (val > 5 ) {   acc.push(val); } return acc; }; reduceWith(bigUns, [], one2ten) //=> [6, 7, 8, 9, 10] 

Naturally, we can combine everything that has already been sorted out in order to get an array of numbers that are more than five squared.

 reduceWith(squares(bigUns), [], one2ten) //=> [9, 16, 25, 36, 49, 64, 81, 100] 

However, it turned out here is not what is needed. The output - the numbers, the squares of which are more than five, and not numbers that are more than five, squared. The numbers must be selected before squareing them, not after. To achieve this behavior of the system is not so difficult. The point here is that the decorator, who is responsible for filtering numbers, will help us; we can use it to decorate the reducser.

 reduceWith(squares(arrayOf), [], one2ten) //=> [1, 4, 9, 16, 25, 36, 49, 64, 81, 100] const bigUnsOf = reducer =>   (acc, val) =>     (val > 5) ? reducer(acc, val) : acc; reduceWith(bigUnsOf(squares(arrayOf)), [], one2ten) //=> [36, 49, 64, 81, 100] 

The bigUnsOf function bigUnsOf quite specific. We will do the same here as with the map , namely, we extract the predicate function and make it an argument.

 reduceWith(squares(arrayOf), [], one2ten) //=> [1, 4, 9, 16, 25, 36, 49, 64, 81, 100] const filter = fn =>   reducer =>     (acc, val) =>       fn(val) ? reducer(acc, val) : acc; reduceWith(filter(x => x > 5)(squares(arrayOf)), [], one2ten) //=> [36, 49, 64, 81, 100] 

Filters, of course, can be any. They can be given names and used multiple times, and anonymous functions can be dispensed with.

 reduceWith(filter(x => x % 2 === 1)(arrayOf), [], one2ten) //=> [1, 3, 5, 7, 9] 

Use the filter to find the sum of squares of odd numbers from one to ten.

 reduceWith(filter(x => x % 2 === 1)(squares(sumOf)), 0, one2ten) //=> 165 

Transformers and composition

The term "transformer" came in JavaScript from other programming languages. This is the name of the function that takes a certain argument and transforms it into something else. What we called above the "decorator" is a special case of the transformer. Thus, if you meet somewhere a story about a transformer function that makes another one from one reducer, it will be clear to you that we are talking about the same function that “decorates” a reducer, adding additional functionality to it, such as mapping or filtering. .

The mapping functions and filters we talked about are also transformers. In the context of this programming pattern, the most important characteristic of transformers is that they use composition to create new transformers. So, to make it clearer, the function that produces the composition of any two input functions to it.

 const plusFive = x => x + 5; const divideByTwo = x => x / 2; plusFive(3) //=> 8 divideByTow(8) //=> 4 const compose2 = (a, b) =>   (...c) =>     a(b(...c)); const plusFiveDividedByTwo = compose2(divideByTwo, plusFive); plusFiveDividedByTwo(3) //=> 4 

Transformers use the composition to create new transformers. What does this mean for compose2 ? This means that by giving it two any transformers, we will get a new transformer that transforms the reducer. Thus, we obtain the following.

 const squaresOfTheOddNumbers = compose2( filter(x => x % 2 === 1), squares ); reduceWith(squaresOfTheOddNumbers(sumOf), 0, one2ten) //=> 165 

What is hidden under the name squaresOfTheOddNumbers is a transformer that we created by applying the compose2 function to the filter and mapping functions.

Now that we have the ability to compose the decorators, we will break apart a complex code, characterized by a high degree of connectivity, into small, highly specialized blocks.

Composition using transformers

Knowing how the compose2 function compose2 , which allows you to get a composition of two functions, we will think about what to do if we need the composition of an arbitrary number of functions. The answer lies in the convolution.

compose2 , making it a compositionOf transformer.

 const compositionOf = (acc, val) => (...args) => val(acc(...args)); 

Now you can write the compose function to get the composition of an arbitrary number of functions as a reduction of its arguments:

 const compose = (...fns) => reduceWith(compositionOf, x => x, fns); 

So, we come to the most interesting.

Transducers

Consider the following entry:

 reduceWith(squaresOfTheOddNumbers(sumOf), 0, one2ten) 

Here you can select four elements. Transformer for a reducer (which can be a composition of transformers), the initial value (drive) and the object to be iterated. If we take the transformer, reducer, drive and the object being iterated into separate parameters, we get the following.

 const transduce = (transformer, reducer, seed, iterable) => { const transformedReducer = transformer(reducer); let accumulation = seed; for (const value of iterable) {   accumulation = transformedReducer(accumulation, value); } return accumulation; } transduce(squaresOfTheOddNumbers, sumOf, 0, one2ten) //=> 165 

It should be noted that in some programming languages ​​there is a strong desire to reduce the long names of variables or parameters. As a result, the rather long name transformer abbreviated to xform or even to xf . Do not be surprised if you see a similar construct, whose entry looks like (xf, reduce, seed, coll), or xf((val, acc) => acc) -> (val, acc) => acc . Here we can do without abbreviations, but in the production code names like xf or xform quite acceptable.

And now, actually, for the sake of what it was all written. A reducer is a function that is passed to methods like .reduce — it takes a drive object and input data, and returns a drive into which new data is placed. A transformer is a function that transforms a reducer into another reducer. A transducer (this name is the result of combining the terms "transformer" and "reducer", here it is the answer to the question: "What are redusers?"), Is a function that accepts a transformer, reducer, drive and an iterated object, and then collapses the iterated object in a certain meaning.

The elegance of the template "transducer" is that the composition of transformers naturally leads to the creation of new transformers. As a result, you can chain as many transformers as you need. This is very important, because as a result you will get one transformed reducer and you will have to walk only once on the iterated collection. No need to create intermediate copies of the data or perform multiple passes on them.

Transducers came to JavaScript from Clojure, but, as you can see, they fit perfectly into JavaScript, for their implementation are quite standard language features.

So, if someone asks us what a transducer is, we can answer this:

Note: this fragment should be highlighted.

Transducers are transformers that are suitable for composition, applied to reducers for convolving iterated objects.

Transducer in action

Above, we looked at code fragments leading to the construction of a transducer. Quite possibly, you have already reproduced them in your JS-editor and have experienced, however, here, for convenience and clarity, all of our code is collected in one place.

 const arrayOf = (acc, val) => { acc.push(val); return acc; }; const sumOf = (acc, val) => acc + val; const setOf = (acc, val) => acc.add(val); const map = fn =>   reducer =>     (acc, val) => reducer(acc, fn(val)); const filter = fn =>   reducer =>     (acc, val) =>       fn(val) ? reducer(acc, val) : acc; const compose = (...fns) => fns.reduce((acc, val) => (...args) => val(acc(...args)), x => x); const transduce = (transformer, reducer, seed, iterable) => { const transformedReducer = transformer(reducer); let accumulation = seed; for (const value of iterable) {   accumulation = transformedReducer(accumulation, value); } return accumulation; } 

This example demonstrates everything that is usually used when working with arrays, namely, these are .map , .filter , .reduce , and there are transducers suitable for composition that are not involved in creating multiple copies of the data set being processed. In fact, transducers written for real projects provide much more use .find , for example, reproducing the functionality of the .find method.

It should be noted that our transduse function transduse designed for the fact that an transduse collection will be passed to it, in addition, we must provide it with an initial value (drive) and a reducer. In most cases, both the initial value and the reducer are the same functions for all collections of the same type. This is also characteristic of the corresponding libraries.

In object-oriented programming, of course, this problem is solved through polymorphism. Collections have methods, therefore, calling the appropriate method, we get what we need at the output. Libraries that can be used to create production code provide interfaces for collections of various types, making it convenient to use transducers.

We believe that the foregoing is sufficient to understand the pattern underlying the transducer and evaluate the useful and convenient features provided by the presence of first-class functions in the language.

Transducers: processing a list of users

This material shows solutions for the following problem: there is a set of users and places they have visited, both of which are presented as a list of hash codes. The first code in each line is the user, the second is the place he visited, say, a restaurant, or a shop. The order of the data in the list is important. The challenge is to find out which transitions between places are most popular.

Namely, there is such a list:

 1a2ddc2, 5f2b932 f1a543f, 5890595 3abe124, bd11537 f1a543f, 5f2b932 f1a543f, bd11537 f1a543f, 5890595 1a2ddc2, bd11537 1a2ddc2, 5890595 3abe124, 5f2b932 f1a543f, 5f2b932 f1a543f, bd11537 f1a543f, 5890595 1a2ddc2, 5f2b932 1a2ddc2, bd11537 1a2ddc2, 5890595 ... 

Carefully reviewing this list, we may find that user 1a2ddc2 visited places with codes 5f2b932 , bd11537 , 5890595 , 5f2b932 , bd11537 , and 5890595 . At the same time, user f1a543f visited places 5890595 , 5f2b932 , bd11537 , 5890595 , 5f2b932 , bd11537 , and 5890595 . And so on.

Suppose you need to find out where people usually go, you need to find the most popular transitions from “place A” to “place B”. We know that the user's travel history 1a2ddc2 as follows: 5f2b932 , bd11537 , 5890595 , 5f2b932 , bd11537 , 5890595 . This means that for him it is possible to build such a scheme of transitions from place to place:

 5f2b932 -> bd11537 bd11537 -> 5890595 5890595 -> 5f2b932 5f2b932 -> bd11537 bd11537 -> 5890595 

Please note that we need to build a similar list for each user. When this is done, you need to find the most popular transitions. Here is what a similar calculation might look like:

The transition 5f2b932 -> bd11537 appears in the list twice.
The transition bd11537 -> 5890595 also occurs twice.
The transition 5890595 -> 5f2b932 met only once.

Now all you have to do is count the number of clicks on all users and find the most popular ones. Here is a solution to this problem using transducers.

 const logContents = `1a2ddc2, 5f2b932 f1a543f, 5890595 3abe124, bd11537 f1a543f, 5f2b932 f1a543f, bd11537 f1a543f, 5890595 1a2ddc2, bd11537 1a2ddc2, 5890595 3abe124, 5f2b932 f1a543f, 5f2b932 f1a543f, bd11537 f1a543f, 5890595 1a2ddc2, 5f2b932 1a2ddc2, bd11537 1a2ddc2, 5890595`; 

 const asStream = function * (iterable) { yield * iterable; }; const lines = str => str.split('\n'); const streamOfLines = asStream(lines(logContents)); const datums = str => str.split(', '); const datumize = map(datums); const userKey = ([user, _]) => user; const pairMaker = () => { let wip = []; return reducer =>   (acc, val) => {     wip.push(val);     if (wip.length === 2) {       const pair = wip;       wip = wip.slice(1);       return reducer(acc, pair);     } else {       return acc;     } } } const sortedTransformation = (xfMaker, keyFn) => {   const decoratedReducersByKey = new Map();   return reducer =>     (acc, val) => {       const key = keyFn(val);       let decoratedReducer;       if (decoratedReducersByKey.has(key)) {         decoratedReducer = decoratedReducersByKey.get(key);       } else {         decoratedReducer = xfMaker()(reducer);         decoratedReducersByKey.set(key, decoratedReducer);       }       return decoratedReducer(acc, val);     } } const userTransitions = sortedTransformation(pairMaker, userKey); const justLocations = map(([[u1, l1], [u2, l2]]) => [l1, l2]); const stringify = map(transition => transition.join(' -> ')); const transitionKeys = compose( stringify, justLocations, userTransitions, datumize ); const countsOf = (acc, val) => {   if (acc.has(val)) {     acc.set(val, 1 + acc.get(val));   } else {     acc.set(val, 1);   }   return acc; } const greatestValue = inMap => Array.from(inMap.entries()).reduce(   ([wasKeys, wasCount], [transitionKey, count]) => {     if (count < wasCount) {       return [wasKeys, wasCount];     } else if (count > wasCount) {       return [new Set([transitionKey]), count];     } else {       wasKeys.add(transitionKey);       return [wasKeys, wasCount];     }   }   , [new Set(), 0] ); greatestValue( transduce(transitionKeys, countsOf, new Map(), streamOfLines) ) //=>   [     "5f2b932 -> bd11537",     "bd11537 -> 5890595"   ],   4 

Results

We hope this material will help everyone to make transducers their permanent tool. If you want to delve into their study, here is a good material about transducers, and here is the transdusers-js library on GitHub.

Dear readers! Do you use transducers in your JavaScript projects?