Javascript transducers. Part two

In the first part, we stopped at the following specification: A transducer is a function that accepts the step function, and returns a new step function.

 step⁰ → step¹ 

The step function, in turn, accepts the current result and the next element, and should return the new current result. In this case, the data type of the current result is not specified.

 result⁰, item → result¹ 

To get the new current result in the step¹ function, you need to call the step⁰ function, passing in it the old current result and the new value that we want to add. If we do not want to add a value, then simply return the old result. If we want to add one value, then we call step⁰ , and then what it returns will return as a new result. If we want to add several values, then we call step⁰ several times along the chain, this is easier to show in the example of the implementation of the flatten transducer:
')

 function flatten() { return function(step) { return function(result, item) { for (var i = 0; i < item.length; i++) { result = step(result, item[i]); } return result; } } } var flattenT = flatten(); _.reduce([[1, 2], [], [3]], flattenT(append), []); // => [1, 2, 3] 

Those. you need to call step several times, each time saving the current result to a variable, and passing it the next time you call it, and at the end return the final one.

As a result, when processing each element, one step function calls another, and that next one, and so on until the last service step function, which already saves the result to the collection ( append from the first part).

So now we can:

1. Modify items (note map)
2. Skip items (approx. Filter)
3. Issue several new items for one item (approx. Flatten)

Premature termination

But what if we want to interrupt the whole process in the middle? Those. implement take , for example. To do this, Rich offers to wrap the return value in a special “reduced” wrapper.

 function Reduced(wrapped) { this._wrapped = wrapped; } Reduced.prototype.unwrap = function() { return this._wrapped; } Reduced.isReduced = function(obj) { return (obj instanceof Reduced); } function take(n) { return function(step) { var count = 0; return function(result, item) { if (count++ < n) { return step(result, item); } else { return new Reduced(result); } } } } var first5T = take(5); 

If we want to complete the process, instead of returning the next result as usual, we return the result wrapped in Reduced . Immediately update the step function signature:

 result⁰, item → result¹ | reduced(result¹) 

But the _.reduce function _.reduce no longer be able to handle this version of the transducer. We'll have to write a new one.

 function reduce(coll, fn, seed) { var result = seed; for (var i = 0; i < coll.length; i++) { result = fn(result, coll[i]); if (Reduced.isReduced(result)) { return result.unwrap(); } } return result; } 

Now you can use the first5T transducer.

 reduce([1, 2, 3, 4, 5, 6, 7], first5T(append), []); // => [1, 2, 3, 4, 5] 

You also have to add the Reduced.isReduced(result) test to transducers that call step several times (note flatten). Those. if in flatten, if we call step step, the result wrapped in Reduced will be returned to us, we must complete our loop, and return this wrapped result.

condition

Another important detail is the take transducer. He remembers how many elements already passed through him. In order for everything to work correctly, this counter needs to be created exactly in the place where it was created in the example (see var count), i.e. inside the function that returns step. If it were, for example, a global variable, then we would consider the elements for all transducers of type take in one counter, and would get the wrong result.

Let's create another service function for launching transducers to more clearly show the moment where the state is created.

 function transduce(transducer, append, seed, coll) { var step = transducer(append); //       . // step    , //   (step)      //    ,   . return reduce(coll, step, seed); } transduce(first5T, append, [], [1, 2, 3, 4, 5, 6, 7]); // => [1, 2, 3, 4, 5] 

Completion

We have already talked about premature termination, but there can be a normal termination when the original collection just ends. Some transducers can somehow handle the completion.

For example, we want to break the collection into small collections of a given length, but if there are not enough elements for the last small collection, then simply return an incomplete one. We need to somehow understand that the elements will no longer exist, and return what is.

In order to be able to do this, Rich suggests adding another variant of the step function, to which the next value is not passed, but only the current result. This option will be called at the end of processing the collection, if there was no premature termination.

In clojure, these two functions are combined into one; we can do this in JavaScript too.

 function step(result, item) { if (arguments.length === 2) { //   //  step(result, item)     } if (arguments.length === 1) { //   //    step c  ,     . //     -     , //      step   ,    . //    return step(result); // -  result = step(result, -); return step(result); } } 

Update the signature of the step function, now it has two options depending on the number of arguments:

 result⁰ → result¹ * result⁰, item → result¹ | reduced(result¹) *        reduced(result¹),      .      . 

All transducers must support both operations — normal step and final call. Also, the transduce() and append() functions will have to be updated to add support for the final call.

 function transduce(transducer, append, seed, coll) { var step = transducer(append); var result = reduce(coll, step, seed); return step(result); } function append(result, item) { if (arguments.length === 2) { return result.concat([item]); } if (arguments.length === 1) { return result; } } 

So, here is the implementation of the partition (breaks the collection into small collections):

 function partition(n) { if (n < 1) { throw new Error('n     1'); } return function(step) { var cur = []; return function(result, item) { if (arguments.length === 2) { cur.push(item); if (cur.length === n) { result = step(result, cur); cur = []; return result; } else { return result; } } if (arguments.length === 1) { if (cur.length > 0) { result = step(result, cur); } return step(result); } } } } var by3ItemsT = partition(3); transduce(by3ItemsT, append, [], [1,2,3,4,5,6,7,8]); // => [[1,2,3], [4,5,6], [7,8]] 

Initialization

Rich also suggests adding the ability for transducers to create an initial empty result value. (We used an empty array everywhere for this purpose, which we explicitly passed first to reduce , and then to transduce .)

To do this, you need to add another version of the step function — no parameters at all. If step is called without parameters, it should return an initial value, for example, an empty array.

Obviously, transducers cannot create an empty array, since they are not tied to the type of collection being processed. But besides the step function in transducers, there is also an external step function, which just knows about the type of collection. In our examples, this is the append function.

Update the signature of the step function.

 → result result⁰ → result¹ result⁰, item → result¹ | reduced(result¹) 

Update the transduce() and append() functions.

 function transduce(transducer, append, coll) { var step = transducer(append); var seed = step(); var result = reduce(coll, step, seed); return step(result); } function append(result, item) { if (arguments.length === 2) { return result.concat([item]); } if (arguments.length === 1) { return result; } if (arguments.length === 0) { return []; } } 

And for example rewrite the transducer generator map.

 function map(fn) { return function(step) { return function(result, item) { if (arguments.length === 2) { return step(result, fn(item)); } if (arguments.length === 1) { return step(result); } if (arguments.length === 0) { return step(); } } } } 

It turns out we just transferred an empty array from the transduce() parameter inside append() , at first glance this is an unnecessary action, but it gave us the opportunity to create transducers that add something to the beginning of the collection (just like the ones that add to the end, just the opposite) .

Thus, all transducers must support three operations in the step function — normal step, final call, and initial call. But most of them will simply pass on the initiative to the next transducer in the last two cases.

Results

That's all. I retold the entire report of Rich Hickey . And, as I understand it, this is so far all that can be told about transducers.

Summarize once again what we got. We got a universal way to create operations on collections. These operations can: change elements (map), skip elements (filter), multiply elements (flatten), have a state (take, partition), prematurely complete processing (take), add something at the end (partition) and add something then first. We can easily combine all these operations using compose, and use them both on ordinary collections and, for example, in FRP. In addition, all this will work quickly and consume little memory, because Temporary collections are not created.

This is all cool! But how do we start using them? The problem is that in order to use transducers to the maximum, the JavaScript community must agree on a specification (and we can do it, right? :-). Then a cool scenario could be realized in which libraries for working with collections (underscore, etc.) will be able to create transducers, and other libraries that are not quite about collections (eg FRP) will simply be supported by transducers.

The specification that Rich offers, at first glance, falls quite well with JavaScript, with the exception of the details about Reduced. The fact is that Clojure already has a global Reduced (it’s been there for a long time), but not in JavaScript. It is, of course, easy to create, but each library will create its own Reduced. In the end, if I, for example, want to add support for transducers in Kefir.js, I will have to add support for transducer-underscore, transducer-LoDash, etc. Reduced is a weak point in the specification proposed by Rich.

Another scenario is the appearance of different transducer libraries, each of which will have its own specification. Then we can only get some of the benefits. There is already a library transducers.js , it has of course created its own Reduced, and so far there is no support for the final and initial calls, and it is not known in what form the author will add them.

Well, considering that many transducers do not seem to be something new and very useful, it is not clear how we will be and whether we will use them in JavaScript.