Javascript transducers. Part one
Rich Hickey, the author of the Clojure language, recently came up with a new concept - Transducers . They were immediately added to Clojure, but the idea itself is universal and can be reproduced in other languages.
Immediately why this is necessary:
')
Transducers are an attempt to rethink operations on collections, such as map (), filter (), etc., to find a common idea in them, and to learn how to combine several operations together for further reuse.
We already know how to combine several operations:
But there are a number of problems:
To explain the idea of ​​transducers, you need to start with the reduce operation. If you think about it, any operation on collections can be expressed through reduce. Let's start with the map operation.
We start with an empty array, and add the results to it: pass each element of the original array through the mapFn function, and add the result to the result array.
I also added the service function append (), which simply wraps the .concat (), then it becomes clear why this is necessary.
Now we will express filter through reduce.
I hope that here, too, everything is clear.
Then I should tell you about .take (), but everything is a bit more complicated with him and I will tell about it in the second part of the article, while we deal with filter and map.
Let's now take a close look at the functions that we pass to reduce to mimic the map and filter.
They have the same type of accepted and returned values, so we have already found something in common with map and filter, and are moving in the right direction. But there is one problem, they use inside the append () function, which can only work with arrays, and as a result, these functions themselves can also work only with arrays. Let's pull out append ().
We wrapped each of these functions in an additional function that takes a certain step function (), and returns a ready-made handler for reduce. Looking ahead, I will say that this is a transducer, i.e. the function that accepts step and the returning handler is the transducer.
Let's check that while everything works.
It seems to work :-)
Here mapT and filterT mean “transducer map” and “transducer filter”.
Before moving on, let's write the functions that generate transducers of different types (for now only map and filter).
If you look at the parameters of the step () function, you can see that it has exactly the same type of parameters and return value as the functions returned by transducers (those that we pass to reduce). This is very important because it allows you to combine several transducers into one!
So, we learned how to combine functions for working with collections in a new way, and called the objects that we combine and receive as a result of the association by transducers. But whether it was possible to solve the problems declared at the beginning of the article?
1) mapFilterTake () can work only with a certain type of collections
Our addOne_lessTnan4 trannyser does not know anything about the type of collection that we force it to process.
We may use a different data type. To get the output is not an array, but for example an object
it is enough to replace the append function, and the initial value [].
To change the type of input data, instead of _.reduce (), use another function that can iterate through this type. It is also not difficult to do.
2) mapFilterTake () cannot be used in a lazy style
Since when processing a collection with a transducer, no temporary collections are created, and each element is processed from beginning to end completely, we can not handle elements that are not yet needed. Those. You can write a method similar to _.reduce (), which will not immediately give the result, but will allow you to call .getNext () to get the next processed element. Or you can organize laziness in some other way.
3) mapFilterTake () will work slowly with large collections
Obviously, transducers have everything under control here.
4) we cannot use mapFilterTake () in FRP / CSP libraries
Since transducers are not tied to the type of collection being processed and do not create intermediate results, they can even be used with such collections as the event flow or Behaviour / Property. They can also be used in CSP - an approach similar to FRP. And potentially it will be possible to use something new, which is not yet.
In the second part, I will tell you how to make take, take Whhile, etc. transducers, and what we should do with this in the JavaScript community now.
Javascript transducers. Part two
Related Links:
blog.cognitect.com/blog/2014/8/6/transducers-are-coming - first mention (if not mistaken)
phuu.net/2014/08/31/csp-and-transducers.html - about CSP and JavaScript extensions
jlongster.com/Transducers.js--A-JavaScript-Library-for-Transformation-of-Data - once again about the JavaScript extensions and a little about CSP
www.youtube.com/watch?v=6mTbuzafcII - Rich Hickey tells in detail about the trasdewsers
Immediately why this is necessary:
- transducers can improve performance because will not create temporary collections in chains of operations map.filter.takeWhile.etc
- can help reuse code
- can help integrate libraries with each other, for example, underscore / LoDash can be able to create transducers, and FRP libraries (RxJS / Bacon.js / Kefir.js ) can be able to accept them
- can simplify FRP libraries because it will be possible to throw away a bunch of methods by adding one method to support transducers
')
Transducers are an attempt to rethink operations on collections, such as map (), filter (), etc., to find a common idea in them, and to learn how to combine several operations together for further reuse.
We already know how to combine several operations:
function mapFilterTake(coll) { return _.take(_.filter(_.map(coll, mapFn), filterFn), 5); } // ( underscore.js) But there are a number of problems:
- mapFilterTake () can only work with a certain type of collections
- it cannot be used in a lazy style
- this will work slowly with large collections, because at each step a large temporary collection is created, and since at the end of .take (5), most of the work will be generally wasted
- we cannot use mapFilterTake () in FRP / CSP libraries
To explain the idea of ​​transducers, you need to start with the reduce operation. If you think about it, any operation on collections can be expressed through reduce. Let's start with the map operation.
function append(coll, item) { return coll.concat([item]); } var newColl = _.reduce(coll, function(result, item) { return append(result, mapFn(item)); }, []); // map var newColl = _.map(coll, mapFn); We start with an empty array, and add the results to it: pass each element of the original array through the mapFn function, and add the result to the result array.
I also added the service function append (), which simply wraps the .concat (), then it becomes clear why this is necessary.
Now we will express filter through reduce.
var newColl = _.reduce(coll, function(result, item) { if (filterFn(item)) { return append(result, item); } else { return result; } }, []); // filter var newColl = _.filter(coll, filterFn); I hope that here, too, everything is clear.
Then I should tell you about .take (), but everything is a bit more complicated with him and I will tell about it in the second part of the article, while we deal with filter and map.
Let's now take a close look at the functions that we pass to reduce to mimic the map and filter.
function(result, item) { return append(result, mapFn(item)); } function(result, item) { if (filterFn(item)) { return append(result, item); } else { return result; } } They have the same type of accepted and returned values, so we have already found something in common with map and filter, and are moving in the right direction. But there is one problem, they use inside the append () function, which can only work with arrays, and as a result, these functions themselves can also work only with arrays. Let's pull out append ().
function(step) { return function(result, item) { return step(result, mapFn(item)); } } function(step) { return function(result, item) { if (filterFn(item)) { return step(result, item); } else { return result; } } } We wrapped each of these functions in an additional function that takes a certain step function (), and returns a ready-made handler for reduce. Looking ahead, I will say that this is a transducer, i.e. the function that accepts step and the returning handler is the transducer.
Let's check that while everything works.
var mapT = function(step) { return function(result, item) { return step(result, mapFn(item)); } } var filterT = function(step) { return function(result, item) { if (filterFn(item)) { return step(result, item); } else { return result; } } } var newColl = _.reduce(coll, mapT(append), []); var newColl = _.reduce(coll, filterT(append), []); It seems to work :-)
Here mapT and filterT mean “transducer map” and “transducer filter”.
Before moving on, let's write the functions that generate transducers of different types (for now only map and filter).
function map(fn) { return function(step) { return function(result, item) { return step(result, fn(item)); } } } function filter(predicate) { return function(step) { return function(result, item) { if (predicate(item)) { return step(result, item); } else { return result; } } } } // var addOneT = map(function(x) {return x + 1}); var lessTnan4T = filter(function(x) {return x < 4}); _.reduce([1, 2, 3, 4], addOneT(append), []); // => [2, 3, 4, 5] _.reduce([2, 3, 4, 5], lessTnan4T(append), []); // => [2, 3] If you look at the parameters of the step () function, you can see that it has exactly the same type of parameters and return value as the functions returned by transducers (those that we pass to reduce). This is very important because it allows you to combine several transducers into one!
var addOne_lessTnan4 = function(step) { return addOneT(lessTnan4T(step)); } // , , _.compose var addOne_lessTnan4 = _.compose(addOneT, lessTnan4T); // , , _.reduce([1, 2, 3, 4], addOne_lessTnan4(append), []); // => [2, 3] So, we learned how to combine functions for working with collections in a new way, and called the objects that we combine and receive as a result of the association by transducers. But whether it was possible to solve the problems declared at the beginning of the article?
1) mapFilterTake () can work only with a certain type of collections
Our addOne_lessTnan4 trannyser does not know anything about the type of collection that we force it to process.
We may use a different data type. To get the output is not an array, but for example an object
it is enough to replace the append function, and the initial value [].
_.reduce([1, 2, 3, 4], addOne_lessTnan4(function(result, item) { result[item] = true; return result; }), {}); // => {2: true, 3: true} To change the type of input data, instead of _.reduce (), use another function that can iterate through this type. It is also not difficult to do.
2) mapFilterTake () cannot be used in a lazy style
Since when processing a collection with a transducer, no temporary collections are created, and each element is processed from beginning to end completely, we can not handle elements that are not yet needed. Those. You can write a method similar to _.reduce (), which will not immediately give the result, but will allow you to call .getNext () to get the next processed element. Or you can organize laziness in some other way.
3) mapFilterTake () will work slowly with large collections
Obviously, transducers have everything under control here.
4) we cannot use mapFilterTake () in FRP / CSP libraries
Since transducers are not tied to the type of collection being processed and do not create intermediate results, they can even be used with such collections as the event flow or Behaviour / Property. They can also be used in CSP - an approach similar to FRP. And potentially it will be possible to use something new, which is not yet.
In the second part, I will tell you how to make take, take Whhile, etc. transducers, and what we should do with this in the JavaScript community now.
Javascript transducers. Part two
Related Links:
blog.cognitect.com/blog/2014/8/6/transducers-are-coming - first mention (if not mistaken)
phuu.net/2014/08/31/csp-and-transducers.html - about CSP and JavaScript extensions
jlongster.com/Transducers.js--A-JavaScript-Library-for-Transformation-of-Data - once again about the JavaScript extensions and a little about CSP
www.youtube.com/watch?v=6mTbuzafcII - Rich Hickey tells in detail about the trasdewsers
Source: https://habr.com/ru/post/237613/
All Articles