7 ms·

Transducers for JavaScript

79 points by dahjelle 12y ago

warble 12y ago
From: http://phuu.net/2014/08/31/csp-and-transducers.html http://phuu.net/2014/08/31/csp-and-transducers.html "To me, transducers are a generic and composable way to operate on a collection of values, producing a new value or new collection of new values. The word 'transducer' itself can be split into two parts that reflect this definition: 'transform' — to produce some value from another — and 'reducer' — to combine the values of a data structure to produce a new one."
- deleted 12y ago
  [deleted]
- qubyte 12y ago
  Amazingly, I was at the asyncjs.com presentation on these and related topics by that author just yesterday! Excellent stuff.
aikah 12y ago
So I checked the definition of a transducer,but i'm not smart enough to get it. What the difference between that library and say lodash where I can bind and compose functions? because it seems like the same stuff var f=_.compose( _.partialRight(_.filter,isEven),_.partialRight(_.map,inc)) ; or something.
- icholy 12y ago
  I think it only iterates over the collection once.
  - rymohr 12y ago
    That and they're collection agnostic. I highly recommend watching Rich Hickey's talk for more background: https://www.youtube.com/watch?v=6mTbuzafcII https://www.youtube.com/watch?v=6mTbuzafcII
  - msoad 12y ago
    Then what happens to operations that access the collection? like third argument in JavaScript's native forEach?
    - aeflash 12y ago
      It's not supported. But if you're doing things right, you shouldn't need it.
    - acjohnson55 12y ago
      That's what a zipper [1] is good for. It gives you access to the rest of a collection relative to the current position. [1] http://en.wikipedia.org/wiki/Zipper_%28data_structure%29 http://en.wikipedia.org/wiki/Zipper_%28data_structure%29
- deleted 12y ago
  [deleted]
- kbeaty 12y ago
  Transducers allow the abstraction of algorithmic transformations independent from the input and output, and even the process of iteration. Whereas lodash operates on arrays and objects calculating intermediate results, transducers simply define the transformation in terms of functions similar to what you pass reduce: start with a memo, execute a function with a memo and an item, return the possibly transformed memo for the next iteration. Once you abstract the transformation away from the data, you can apply the same transformations to different processes that start with an initial value and step through a result. One benefit is that you can compute the result in one pass (without intermediate results). Another is you can use the same transformation in different contexts (lazy lists, indefinite sequence generation, CSP, event streams, etc.). The source could be anything that produces a sequences of values: streams, iterators, callbacks, immutable-js, etc. You simply have to define (external to the transducer) how you append each item to the supplied result. The "step function" that knows how to append results to values is passed to the transducer, and the transducer executes the step function when reducing over results. It's interesting you mention lodash in the context of transducers, as I have been developing my own take on transducers closely following the underscore API [1]. [1]: https://github.com/kevinbeaty/underscore-transducer https://github.com/kevinbeaty/underscore-transducer
- kbeaty 12y ago
  Transducers allow the abstraction of algorithmic transformations independent from the input and output, and even the process of iteration. Whereas lodash operates on arrays and objects calculating intermediate results, transducers simply define the transformation in terms of functions similar to what you pass reduce: start with a memo, execute a function with a memo and an item, return the possibly transformed memo for the next iteration. Once you abstract the transformation away from the data, you can apply the same transformations to different processes that start with an initial value and step through a result. One benefit is that you can compute the result in one pass (without intermediate results). Another is you can use the same transformation in different contexts (lazy lists, indefinite sequence generation, CSP, event streams, etc.). The source could be anything that produces a sequences of values: streams, iterators, callbacks, immutable-js, etc. You simply have to define (external to the transducer) how you append each item to the supplied result. The "step function" that knows how to append results to values is passed to the transducer, and the transducer executes the step function when reducing over results. It's interesting you mention lodash in the context of transducers, as I have been developing my own take on transducers closely following the underscore API [1]. [1]: https://github.com/kevinbeaty/underscore-transducer https://github.com/kevinbeaty/underscore-transducer
d--b 12y ago
Why not wait for ES6, and use proper iterators and use them as they do in C#? as in var evens = [1,2,3,4].where(x => x%2 == 0).toarray() no ?
deleted 12y ago
[deleted]
tripzilch 12y ago
Friendly advice: maybe also include the output of the example code in the README.
jlongster 12y ago
It'll be interesting to look into how the Clojure people implemented this. I released the same library a few weeks ago: https://github.com/jlongster/transducers.js https://github.com/jlongster/transducers.js, and I'm about to release the next version with an API almost the same as the OP. I think mine has more integration with JS data structures and stuff like monkeypatching existing ones (like immutable-js) to work with this. We'll see how all this shakes out though; not sure if it'll be good to converge on one official library or if it's ok to have multiple.
- sriku 12y ago
  The concept is simple enough and the performance benefits common enough that it would certainly help to converge and contribute the core to one repo with compatibility and other features in supplementary optional repos ... imho.
- coding4all 12y ago
  ClojureScript?
coding4all 12y ago
Notes and examples of Transducers and Reducers https://gist.github.com/runexec/06b56a9dbd15e43145b9 https://gist.github.com/runexec/06b56a9dbd15e43145b9
zoomerang 12y ago
As somebody with more experience with Haskell and Scala than Clojure - how to Transducers differ from Functors in Haskell? On the surface they seem very similar.
gcanti 12y ago
When I see concepts like transducers I'm always torn in two: my theoretical side is really excited: reducing (pun intended) a bunch of different operations to a minimal set of basic, composable operations is an awesome intellectual challenge. I imagine how succinct, reusable and multipurpose could become my code. my pragmatic side is skeptic: in functional programming it's a little step to end up with incomprehensible code, for me and my coworkers: var inc = function(n) { return n + 1; }; var isEven = function(n) { return n % 2 == 0; }; var xf = comp(map(inc), filter(isEven)); console.log(into([], xf, [0,1,2,3,4])); // [2,4] vs var inc = function(n) { return n + 1; }; var isEven = function(n) { return n % 2 == 0; }; [0,1,2,3,4].map(inc).filter(isEven); // [2,4] The latter is comprehensible by everyone (and no additional library). Ok you iterate twice but if you really (REALLY) have performance problems, maybe you'd end up with something like this: var input = [0,1,2,3,4]; var output = []; var x; for (var i = 0, len = input.length ; i < len ; i++ ) { x = input[i] + 1; // map if (x % 2 == 0) ouput.push(x); // filter }
- pmontra 12y ago
  I agree. They are quite incomprehensible. I looked at the Ruby version https://github.com/cognitect-labs/transducers-ruby https://github.com/cognitect-labs/transducers-ruby because I'm better at Ruby than at JS and Ruby is usually more readable than JS. No way to understand it. I had to dig into the documentation and learn how it works instead of figuring it out from the way it looks. The less efficient equivalent is (1..100).select {|n| n.even?}.map {|n| n * 2}.take(5) which is self evident to anybody with a couple of days of Ruby on his back. I think tranducers are a good idea with still the wrong syntax. Probably the Ruby way to transducers would be along these lines. (1..100).transduce.select {|n| n.even?}.map {|n| n * 2}.take(5).run like we build SQL queries with AREL. Maybe this will never work but a possible implementation is adding transduce to a bunch of classes (in this case: Range), having transduce return an object (a Transduceable?) augmented with transducing equivalents of some methods, letting those methods pick sensible defaults for the composition operation and initial value based on the type of the object on the left. Maybe adding transduce to Enumerable is enough to get all the most important classes covered. Probably we need a further method call to actually run the transducing operation we built, that's why the final .run This is probably not as general as the transducer ruby gem even if we enhance it by passing the reducer and the initial value as arguments as in transduce(reducer: :push, initial_value: []) but it should cover most of the use cases and anybody would be able to read it. This makes the difference when having to urgently fix bugs in the code somebody else wrote two years before and then left the company.

79 points by dahjelle 12y ago

From: http://phuu.net/2014/08/31/csp-and-transducers.html http://phuu.net/2014/08/31/csp-and-transducers.html "To me, transducers are a generic and composable way to operate on a collection of values, producing a new value or new collection of new values. The word 'transducer' itself can be split into two parts that reflect this definition: 'transform' — to produce some value from another — and 'reducer' — to combine the values of a data structure to produce a new one."

deleted 12y ago
[deleted]
qubyte 12y ago
Amazingly, I was at the asyncjs.com presentation on these and related topics by that author just yesterday! Excellent stuff.

aikah 12y ago

So I checked the definition of a transducer,but i'm not smart enough to get it. What the difference between that library and say lodash where I can bind and compose functions? because it seems like the same stuff var f=_.compose( _.partialRight(_.filter,isEven),_.partialRight(_.map,inc)) ; or something.

icholy 12y ago
I think it only iterates over the collection once.
- rymohr 12y ago
  That and they're collection agnostic. I highly recommend watching Rich Hickey's talk for more background: https://www.youtube.com/watch?v=6mTbuzafcII https://www.youtube.com/watch?v=6mTbuzafcII
- msoad 12y ago
  Then what happens to operations that access the collection? like third argument in JavaScript's native forEach?
  - aeflash 12y ago
    It's not supported. But if you're doing things right, you shouldn't need it.
  - acjohnson55 12y ago
    That's what a zipper [1] is good for. It gives you access to the rest of a collection relative to the current position. [1] http://en.wikipedia.org/wiki/Zipper_%28data_structure%29 http://en.wikipedia.org/wiki/Zipper_%28data_structure%29
deleted 12y ago
[deleted]
kbeaty 12y ago
Transducers allow the abstraction of algorithmic transformations independent from the input and output, and even the process of iteration. Whereas lodash operates on arrays and objects calculating intermediate results, transducers simply define the transformation in terms of functions similar to what you pass reduce: start with a memo, execute a function with a memo and an item, return the possibly transformed memo for the next iteration. Once you abstract the transformation away from the data, you can apply the same transformations to different processes that start with an initial value and step through a result. One benefit is that you can compute the result in one pass (without intermediate results). Another is you can use the same transformation in different contexts (lazy lists, indefinite sequence generation, CSP, event streams, etc.). The source could be anything that produces a sequences of values: streams, iterators, callbacks, immutable-js, etc. You simply have to define (external to the transducer) how you append each item to the supplied result. The "step function" that knows how to append results to values is passed to the transducer, and the transducer executes the step function when reducing over results. It's interesting you mention lodash in the context of transducers, as I have been developing my own take on transducers closely following the underscore API [1]. [1]: https://github.com/kevinbeaty/underscore-transducer https://github.com/kevinbeaty/underscore-transducer
kbeaty 12y ago
Transducers allow the abstraction of algorithmic transformations independent from the input and output, and even the process of iteration. Whereas lodash operates on arrays and objects calculating intermediate results, transducers simply define the transformation in terms of functions similar to what you pass reduce: start with a memo, execute a function with a memo and an item, return the possibly transformed memo for the next iteration. Once you abstract the transformation away from the data, you can apply the same transformations to different processes that start with an initial value and step through a result. One benefit is that you can compute the result in one pass (without intermediate results). Another is you can use the same transformation in different contexts (lazy lists, indefinite sequence generation, CSP, event streams, etc.). The source could be anything that produces a sequences of values: streams, iterators, callbacks, immutable-js, etc. You simply have to define (external to the transducer) how you append each item to the supplied result. The "step function" that knows how to append results to values is passed to the transducer, and the transducer executes the step function when reducing over results. It's interesting you mention lodash in the context of transducers, as I have been developing my own take on transducers closely following the underscore API [1]. [1]: https://github.com/kevinbeaty/underscore-transducer https://github.com/kevinbeaty/underscore-transducer

d--b 12y ago

Why not wait for ES6, and use proper iterators and use them as they do in C#? as in var evens = [1,2,3,4].where(x => x%2 == 0).toarray() no ?

deleted 12y ago

[deleted]

tripzilch 12y ago

Friendly advice: maybe also include the output of the example code in the README.

jlongster 12y ago

It'll be interesting to look into how the Clojure people implemented this. I released the same library a few weeks ago: https://github.com/jlongster/transducers.js https://github.com/jlongster/transducers.js, and I'm about to release the next version with an API almost the same as the OP. I think mine has more integration with JS data structures and stuff like monkeypatching existing ones (like immutable-js) to work with this. We'll see how all this shakes out though; not sure if it'll be good to converge on one official library or if it's ok to have multiple.

sriku 12y ago
The concept is simple enough and the performance benefits common enough that it would certainly help to converge and contribute the core to one repo with compatibility and other features in supplementary optional repos ... imho.
coding4all 12y ago
ClojureScript?

coding4all 12y ago

Notes and examples of Transducers and Reducers https://gist.github.com/runexec/06b56a9dbd15e43145b9 https://gist.github.com/runexec/06b56a9dbd15e43145b9

zoomerang 12y ago

As somebody with more experience with Haskell and Scala than Clojure - how to Transducers differ from Functors in Haskell? On the surface they seem very similar.

gcanti 12y ago

When I see concepts like transducers I'm always torn in two: my theoretical side is really excited: reducing (pun intended) a bunch of different operations to a minimal set of basic, composable operations is an awesome intellectual challenge. I imagine how succinct, reusable and multipurpose could become my code. my pragmatic side is skeptic: in functional programming it's a little step to end up with incomprehensible code, for me and my coworkers: var inc = function(n) { return n + 1; }; var isEven = function(n) { return n % 2 == 0; }; var xf = comp(map(inc), filter(isEven)); console.log(into([], xf, [0,1,2,3,4])); // [2,4] vs var inc = function(n) { return n + 1; }; var isEven = function(n) { return n % 2 == 0; }; [0,1,2,3,4].map(inc).filter(isEven); // [2,4] The latter is comprehensible by everyone (and no additional library). Ok you iterate twice but if you really (REALLY) have performance problems, maybe you'd end up with something like this: var input = [0,1,2,3,4]; var output = []; var x; for (var i = 0, len = input.length ; i < len ; i++ ) { x = input[i] + 1; // map if (x % 2 == 0) ouput.push(x); // filter }

pmontra 12y ago
I agree. They are quite incomprehensible. I looked at the Ruby version https://github.com/cognitect-labs/transducers-ruby https://github.com/cognitect-labs/transducers-ruby because I'm better at Ruby than at JS and Ruby is usually more readable than JS. No way to understand it. I had to dig into the documentation and learn how it works instead of figuring it out from the way it looks. The less efficient equivalent is (1..100).select {|n| n.even?}.map {|n| n * 2}.take(5) which is self evident to anybody with a couple of days of Ruby on his back. I think tranducers are a good idea with still the wrong syntax. Probably the Ruby way to transducers would be along these lines. (1..100).transduce.select {|n| n.even?}.map {|n| n * 2}.take(5).run like we build SQL queries with AREL. Maybe this will never work but a possible implementation is adding transduce to a bunch of classes (in this case: Range), having transduce return an object (a Transduceable?) augmented with transducing equivalents of some methods, letting those methods pick sensible defaults for the composition operation and initial value based on the type of the object on the left. Maybe adding transduce to Enumerable is enough to get all the most important classes covered. Probably we need a further method call to actually run the transducing operation we built, that's why the final .run This is probably not as general as the transducer ruby gem even if we enhance it by passing the reducer and the initial value as arguments as in transduce(reducer: :push, initial_value: []) but it should cover most of the use cases and anybody would be able to read it. This makes the difference when having to urgently fix bugs in the code somebody else wrote two years before and then left the company.