3 ms·

How are transducers different than iterators in C++ or Rust or streams in Java?

nextaccountic 3y ago
My reading is that a transducer is a map, that is, something that transforms iterators Like something that receives myiterator and returns myiterator.map(|x| x + 2) in rust But other than focusing on the map rather than on the iterator, I think it's the same thing
- fiddlerwoaroof 3y ago
  The power it has on top of map is it can skip items and change the shape of the container: that is, it’s a decomposition of a fold and not just a composable map. So, you can consume a vector and produce a subset of the vector as a map. Finally, transducers separate the element-wise processing from both the construction of the final sequence and the details of iterating over the input.
  - nextaccountic 3y ago
    A map that can skip itens is normally called a filter_map But can it produce more than one item as well? So it's like, for each item of the iterator/stream/sequence, it can produce 0, 1, or any number of items? Then it's like Haskell's bind (the >>= of the Monad instance) for lists, or Rust's flat_map for iterators, and flatMap in javascript as well
    - fiddlerwoaroof 3y ago
      It’s more than bind, because a monad requires that the input monad be the same as the output one (if you consume a list, you can only produce a list). Clojure’s Transducers are as powerful as foldr because the output type can be different. E.g.: (into {} (map (fn [k] [(/ k 2) k])) [1 2 3 4]) ;; {1 2, 2 4} (A difference between fold and transducers is that transducers can work in infinite input types like core.async channels) Here’s a bit of code I put together to show the relation to fold: https://github.com/fiddlerwoaroof/lisp-sandbox/blob/580980236bc55441af7d821c1f81b8c351a5474f/transduce-steps.lisp#L26 https://github.com/fiddlerwoaroof/lisp-sandbox/blob/58098023... The other way I think of this is “explicit stream fusion”: transducers work by passing an explicit continuation around and you call that continuation to add results to the output: but, crucially, you don’t have to know what the output type is, you just say “add this to it”.
      - nextaccountic 3y ago
        > the output type can be different That's interesting. But every such type must have the same "shape" - a sequence of things. So it's the same as bind, plus an optional conversion at the end. Which is the same as Rust's flat_map, because in Rust when you operate with iterators you can end up collecting into another type, like, myvec.into_iter().flat_map(|x| ..).collect() converts from a Vec<T> into SomeType<U>, where SomeType is any type that represents a sequence, and T to U is the type conversion from the map > (A difference between fold and transducers is that transducers can work in infinite input types like core.async channels) Ok so transducers are just lazy folds (I mean folds can work with infinite data in Haskell as well)
        fiddlerwoaroof 3y ago
        > it's the same as bind, plus an optional conversion at the end. The mapcat transducer (flatMap in other languages) is equivalent to bind. The “optional conversion at the end” would defeat the whole point of transducers because it would force you to materialize an intermediate sequence before building up the result. The result type is a superset of monads, I’m fairly sure: it’s anything that can be the result of a two argument function with the signature `a -> b -> a`: there’s nothing in theory preventing using a transducer to sum up a list of integers.
twic 3y ago
Okay, so you know streams in Java. You know a Collector? A transducer is roughly a Function<Collector, Collector> (with some more type variables to make that valid). Given a Collector, a transducer will make another Collector which does some stuff to its input and delegates to the underlying Collector. The nice thing about this is that you can implement all the non-terminal operations on Stream in terms of this. Mapping is passing each input element through a function before passing it on. Filtering is testing each element with a predicate, and only passing it on if it passes. Flat mapping is passing the element through a function to get a number of new elements, then passing them all on one by one. But you can do more! You can write a transducer which batches elements, a bit like the inverse of flat mapping. You can't do that with the existing Streams API at all! The things transducers operate on, which Clojure calls reducing functions, end up being a bit different to Collectors: their accumulate operation returns a boolean to control early stopping, which lets them implement take while, limit, and so on, and that means they can't be parallel. But the vibes are exactly the same.
- tadfisher 3y ago
  A similar mechanism in another JVM language is Kotlin's sequences, which can also do windowed/chunked/batched operations by holding a little bit of intermediate state. Combine that with coroutines and it's pretty trivial to perform a parallel map/flatmap and saturate all cores. I'm surprised Streams can't do this.
  - twic 3y ago
    In case what i wrote wasnt clear: Java's streams are (or can be) parallel, and can saturate as many cores as you like. But parallelism is not compatible with early stopping at any stage - early stopping is inherently serial! - and transducers choose allowing any stage to stop early over being parallel.
- dataangel 3y ago
  This still just sounds like boring old iterators. Rust and C++ iterators both do all of this.

My reading is that a transducer is a map, that is, something that transforms iterators Like something that receives myiterator and returns myiterator.map(|x| x + 2) in rust But other than focusing on the map rather than on the iterator, I think it's the same thing

fiddlerwoaroof 3y ago
The power it has on top of map is it can skip items and change the shape of the container: that is, it’s a decomposition of a fold and not just a composable map. So, you can consume a vector and produce a subset of the vector as a map. Finally, transducers separate the element-wise processing from both the construction of the final sequence and the details of iterating over the input.
- nextaccountic 3y ago
  A map that can skip itens is normally called a filter_map But can it produce more than one item as well? So it's like, for each item of the iterator/stream/sequence, it can produce 0, 1, or any number of items? Then it's like Haskell's bind (the >>= of the Monad instance) for lists, or Rust's flat_map for iterators, and flatMap in javascript as well
  - fiddlerwoaroof 3y ago
    It’s more than bind, because a monad requires that the input monad be the same as the output one (if you consume a list, you can only produce a list). Clojure’s Transducers are as powerful as foldr because the output type can be different. E.g.: (into {} (map (fn [k] [(/ k 2) k])) [1 2 3 4]) ;; {1 2, 2 4} (A difference between fold and transducers is that transducers can work in infinite input types like core.async channels) Here’s a bit of code I put together to show the relation to fold: https://github.com/fiddlerwoaroof/lisp-sandbox/blob/580980236bc55441af7d821c1f81b8c351a5474f/transduce-steps.lisp#L26 https://github.com/fiddlerwoaroof/lisp-sandbox/blob/58098023... The other way I think of this is “explicit stream fusion”: transducers work by passing an explicit continuation around and you call that continuation to add results to the output: but, crucially, you don’t have to know what the output type is, you just say “add this to it”.
    - nextaccountic 3y ago
      > the output type can be different That's interesting. But every such type must have the same "shape" - a sequence of things. So it's the same as bind, plus an optional conversion at the end. Which is the same as Rust's flat_map, because in Rust when you operate with iterators you can end up collecting into another type, like, myvec.into_iter().flat_map(|x| ..).collect() converts from a Vec<T> into SomeType<U>, where SomeType is any type that represents a sequence, and T to U is the type conversion from the map > (A difference between fold and transducers is that transducers can work in infinite input types like core.async channels) Ok so transducers are just lazy folds (I mean folds can work with infinite data in Haskell as well)
      - fiddlerwoaroof 3y ago
        > it's the same as bind, plus an optional conversion at the end. The mapcat transducer (flatMap in other languages) is equivalent to bind. The “optional conversion at the end” would defeat the whole point of transducers because it would force you to materialize an intermediate sequence before building up the result. The result type is a superset of monads, I’m fairly sure: it’s anything that can be the result of a two argument function with the signature `a -> b -> a`: there’s nothing in theory preventing using a transducer to sum up a list of integers.

twic 3y ago

Okay, so you know streams in Java. You know a Collector? A transducer is roughly a Function<Collector, Collector> (with some more type variables to make that valid). Given a Collector, a transducer will make another Collector which does some stuff to its input and delegates to the underlying Collector. The nice thing about this is that you can implement all the non-terminal operations on Stream in terms of this. Mapping is passing each input element through a function before passing it on. Filtering is testing each element with a predicate, and only passing it on if it passes. Flat mapping is passing the element through a function to get a number of new elements, then passing them all on one by one. But you can do more! You can write a transducer which batches elements, a bit like the inverse of flat mapping. You can't do that with the existing Streams API at all! The things transducers operate on, which Clojure calls reducing functions, end up being a bit different to Collectors: their accumulate operation returns a boolean to control early stopping, which lets them implement take while, limit, and so on, and that means they can't be parallel. But the vibes are exactly the same.

tadfisher 3y ago
A similar mechanism in another JVM language is Kotlin's sequences, which can also do windowed/chunked/batched operations by holding a little bit of intermediate state. Combine that with coroutines and it's pretty trivial to perform a parallel map/flatmap and saturate all cores. I'm surprised Streams can't do this.
- twic 3y ago
  In case what i wrote wasnt clear: Java's streams are (or can be) parallel, and can saturate as many cores as you like. But parallelism is not compatible with early stopping at any stage - early stopping is inherently serial! - and transducers choose allowing any stage to stop early over being parallel.
dataangel 3y ago
This still just sounds like boring old iterators. Rust and C++ iterators both do all of this.