4 ms·

So Transducers generalize the usage of Enumerable functions such as map, reduce, filter, flatMap (...). Please could someone tell me if this is conceptually di

So Transducers generalize the usage of Enumerable functions such as map, reduce, filter, flatMap (...). Please could someone tell me if this is conceptually different from ruby's Enumerable module which only needs the class its included in to implement `each` so anything can be enumerable ? Or is it a similar but just in translated to the FP world ?

moomin 12y ago
What's you're thinking of is more like ISeq in Clojure, or Foldable is Haskell. The more interesting generalisation is not between arrays, vectors and hashsets, but between data structures and event streams.
YuriNiyazov 12y ago
Yes; There are differences. 1. Transducers are parallel under the covers. Since the expectations is that the code that the predicate or mapping functions that you pass into map, filter and reduce are pure (no variables are changed, no state is modified, just a calculation that is only dependent on arguments) the parallelism is hidden away from you, but it's there. Ruby's Enumerable can't do parallelism 2. When you compose transducers, there are no intermediate sequences generated. The simplest example is this: In Ruby: [1, 2, 3].map {|x| x + 1}.map {|x| x+ 2} will generate an intermediate array [2, 3, 4] after the first map, and then will generate [4, 5, 6] when it has evaluated the whole expression. In Clojure (I am sure I got the syntax wrong for this one) (transduce (map #(+ 2 %) (map inc)) [1 2 3]) will create an intermediate mapping function that will first increment, then add 2 to its argument, and then will map once using that intermediate function.
- cfeduke 12y ago
  Transducers _can be_ parallelized (TODO) but some transducer implementations do contain state, like `take` and therefore cannot be parallelized. The big thing is no intermediate results.
  - seanmcdirmid 12y ago
    So transducers are like .Net/LINQ enumerables?
    - Skinney 12y ago
      Nah, Clojure seqs are more like .NET/LINQ enumerables. Functions that work over seqs/enumerables return a new seq/enumerable. From what I understand, and I'm sure I am wrong, a transducer receives and transforms a value, and may call the next transducer with the transformed value. The nice thing is that a transducer does not create intermediate results (a seq/enumerable), and that it doesn't make any assumptions on the underlying datastructure. So you can, for instance, send a value through a transducer and directly place it in a list, instead of creating a set of enumerables and then call .ToList on that. Since transducers can work with any value, you also aren't tied to enumerables. So transducers should be a little more universal and performant than enumerables.
      - icefox 12y ago
        A contrived example in C#/LINQ Enumerable.Range(1, 100) .Where(n => n % 2 == 0) .Select(n => n * 2) .ToList(); And as a transducer it could looks something like this? sequence( Enumerable.Range(1, 100), compose( filter(n => n %2 == 0), map(x => x + 1) ) ).ToList(); On the linq side it would create only 2 enumerable objects (one for where and select) and the ToList would result in a copy the object pointer as it was passing through each enumerable. For the transducer example rather than having 2 enumerable's we would have 2 transducer objects? I absolutely understand the case where a language's map/filter/reduce/etc results in a whole new list, but for the above case the performance/memory overhead improvement doesn't see that huge and really minor. The fact that it removes the overhead of having to support IEnumerable and as you mentioned is only dealing with functions is what seems like a win. At first I was thinking that plain old LINQ is also more readable, but my contrived c# transducer example doesn't look that bad in the end. Am I incorrect on any of this?
        ajanuary 12y ago
- charlysisto 12y ago
  Thanks for the answer. Indeed Ruby in general has the limitations inherent to its "non functional" nature. However regarding 2) Enumeration can now (in ruby 2.0) be lazy and thus take each item one after the other through the whole chain. (1..Float::INFINITY).lazy.map{|a| p a; a*10}.map{|a| p a+1} # => 1 11 2 21 etc... So it can work with streams & so on... But I know (from a Jessica Kerr presentation) it also has limitations there.
drostie 12y ago
Transducers are a different kind of thing, not just a generalized usage of enumerable functions. Clojure transducers are isomorphic to functions of type `a -> [b]`, that is, functions which take some thing and return lists of other things. You can implement map and filter in this language: tmap f a = [f a] tfilter p a = if p a then [a] else [] You can also compose two such functions: concat :: [[x]] -> [x] concat [] = [] concat (x : xs) = x ++ concat xs concatMap f list = concat (map f list) compose lb_a lc_b = \a -> concatMap lc_b (lb_a a) One reduction function (`foldr`) turns out to just be the identity function [a] -> [a], as I recall. The interesting thing about Clojure transformers is that they have a strange continuation-passing form, such that this function `compose` that I wrote above for the type `a -> [b]` is actually in Clojure just a function composition. That is, instead of `a -> [b]` we see `forall r. (b -> r -> r) -> (a -> r -> r)`, which composes with normal function composition.

moomin 12y ago

What's you're thinking of is more like ISeq in Clojure, or Foldable is Haskell. The more interesting generalisation is not between arrays, vectors and hashsets, but between data structures and event streams.

YuriNiyazov 12y ago

Yes; There are differences. 1. Transducers are parallel under the covers. Since the expectations is that the code that the predicate or mapping functions that you pass into map, filter and reduce are pure (no variables are changed, no state is modified, just a calculation that is only dependent on arguments) the parallelism is hidden away from you, but it's there. Ruby's Enumerable can't do parallelism 2. When you compose transducers, there are no intermediate sequences generated. The simplest example is this: In Ruby: [1, 2, 3].map {|x| x + 1}.map {|x| x+ 2} will generate an intermediate array [2, 3, 4] after the first map, and then will generate [4, 5, 6] when it has evaluated the whole expression. In Clojure (I am sure I got the syntax wrong for this one) (transduce (map #(+ 2 %) (map inc)) [1 2 3]) will create an intermediate mapping function that will first increment, then add 2 to its argument, and then will map once using that intermediate function.

cfeduke 12y ago
Transducers _can be_ parallelized (TODO) but some transducer implementations do contain state, like `take` and therefore cannot be parallelized. The big thing is no intermediate results.
- seanmcdirmid 12y ago
  So transducers are like .Net/LINQ enumerables?
  - Skinney 12y ago
    Nah, Clojure seqs are more like .NET/LINQ enumerables. Functions that work over seqs/enumerables return a new seq/enumerable. From what I understand, and I'm sure I am wrong, a transducer receives and transforms a value, and may call the next transducer with the transformed value. The nice thing is that a transducer does not create intermediate results (a seq/enumerable), and that it doesn't make any assumptions on the underlying datastructure. So you can, for instance, send a value through a transducer and directly place it in a list, instead of creating a set of enumerables and then call .ToList on that. Since transducers can work with any value, you also aren't tied to enumerables. So transducers should be a little more universal and performant than enumerables.
    - icefox 12y ago
      A contrived example in C#/LINQ Enumerable.Range(1, 100) .Where(n => n % 2 == 0) .Select(n => n * 2) .ToList(); And as a transducer it could looks something like this? sequence( Enumerable.Range(1, 100), compose( filter(n => n %2 == 0), map(x => x + 1) ) ).ToList(); On the linq side it would create only 2 enumerable objects (one for where and select) and the ToList would result in a copy the object pointer as it was passing through each enumerable. For the transducer example rather than having 2 enumerable's we would have 2 transducer objects? I absolutely understand the case where a language's map/filter/reduce/etc results in a whole new list, but for the above case the performance/memory overhead improvement doesn't see that huge and really minor. The fact that it removes the overhead of having to support IEnumerable and as you mentioned is only dealing with functions is what seems like a win. At first I was thinking that plain old LINQ is also more readable, but my contrived c# transducer example doesn't look that bad in the end. Am I incorrect on any of this?
      - ajanuary 12y ago
charlysisto 12y ago
Thanks for the answer. Indeed Ruby in general has the limitations inherent to its "non functional" nature. However regarding 2) Enumeration can now (in ruby 2.0) be lazy and thus take each item one after the other through the whole chain. (1..Float::INFINITY).lazy.map{|a| p a; a*10}.map{|a| p a+1} # => 1 11 2 21 etc... So it can work with streams & so on... But I know (from a Jessica Kerr presentation) it also has limitations there.

drostie 12y ago

Transducers are a different kind of thing, not just a generalized usage of enumerable functions. Clojure transducers are isomorphic to functions of type `a -> [b]`, that is, functions which take some thing and return lists of other things. You can implement map and filter in this language: tmap f a = [f a] tfilter p a = if p a then [a] else [] You can also compose two such functions: concat :: [[x]] -> [x] concat [] = [] concat (x : xs) = x ++ concat xs concatMap f list = concat (map f list) compose lb_a lc_b = \a -> concatMap lc_b (lb_a a) One reduction function (`foldr`) turns out to just be the identity function [a] -> [a], as I recall. The interesting thing about Clojure transformers is that they have a strange continuation-passing form, such that this function `compose` that I wrote above for the type `a -> [b]` is actually in Clojure just a function composition. That is, instead of `a -> [b]` we see `forall r. (b -> r -> r) -> (a -> r -> r)`, which composes with normal function composition.