4 ms·

As far as I can discern, transducers are exactly the same as iterator adaptors in Rust: you compose transformations on a stream and get back a computation that

by gue5t 11y ago

As far as I can discern, transducers are exactly the same as iterator adaptors in Rust: you compose transformations on a stream and get back a computation that pumps one element through the entire set of transformations on each iteration, i.e. it fuses the loops together. Then you can either run this computation and collect results into a data structure of your choosing or compose different stream transformations onto the end. The C++ implementation of this notion looks like an inscrutable, complete trainwreck, like the rest of the language.

spooningtamarin 11y ago
And fortunately for us who cannot comprehend it C++17 brings in ranges.
kybernetikos 11y ago
Transducers do not require that every element that comes out of the source results in a single element going into the destination, it can just as well be 0 or many, they also work well with mutable or immutable destinations (because they're a reduce rather than a map so they can modify the destination).
- gue5t 11y ago
  Perhaps my description was unclear or assumed too much familiarity with Rust, but iterator adaptors such as .filter() and .flat_map support the 0-/many-output use cases you describe, and Vec::extend vs .collect() are a couple of mutable and immutable (resp.) ways to choose the destination of a composition of iterator adaptors.
  - kybernetikos 11y ago
    You're right, and that description doesn't make sense. Let me see if I can explain why I said what I said: When you call next on an iterator, you expect it to give you the next value or to tell you that there will be no more values. It's not supposed to give you no value 'for now' or many values. With a transducer it can change your destination value in any way it likes according to your final reducer function. Perhaps it's better to say that iterators are controlled by their destination and so are used in a pull fashion while how reduction functions are used is defined by the source so can be used in push mode. It's easy to emulate pull mode with a push source - you just keep pumping values into one end until one comes out the other, but you can't emulate push with a pull destination, as you can't tell without running your adapters how many values will need to go into the pipe to produce your next value. Imagine you have an event source, and you want values coming out of it to go into some other data structure as they arrive via the same kind of chain of transformations as you might use on a simple data structure. It'd be pretty ugly to do this with iterator adapters (probably have to have an iterator stream of futures, but then you can't do a normal map/filter, etc.), but the reduce on the event stream can pump values through as they come in, regardless of if any of them ever make it to the end of the pipe.
llasram 11y ago
Kind of. Rust iterator adapters are closer to the previous Clojure reducers namespace and the Java 8 streams API. All three take a "collection" and return a new "collection" which includes additional behavior/transformations when ultimately iterated over. Transducers separate out the transformation processes into free-standing composable functions. This makes the transformations first-class values, and makes it possible to apply such transformations to less collection-like entities such as async channels. I'm personally still not sure if it's a good idea or not, but it is an interesting approach.
- gue5t 11y ago
  I'm not sure you're characterizing Rust iterator adaptors right. Iterator adaptors take an iterator (which usually, but not always, comes from a collection, e.g. "my_vec.into_iter()") and give you another iterator back, without allocating an intermediate collection; the iterator itself stores only the current state of the iteration process. You can apply iterator adaptors to such iterators as the receiving end of a channel ( http://doc.rust-lang.org/std/sync/mpsc/struct.Receiver.html#method.iter http://doc.rust-lang.org/std/sync/mpsc/struct.Receiver.html#... ), and you can pass around the iterator and add other computations to the end of it before you "run" the whole thing. However, I'm not sure what you mean by the transformation processes being functions. In Rust these processes (iterators) are values, and have methods that produce a derived process by appending a step; for a concrete example: let fb_chars = "foobar".chars(); //fb_chars is an iterator let not_o = fb_chars.filter(|&x| x!='o'); //not_o is an iterator; we got it by applying the filter iterator adaptor for i in not_o {println!("char: {}", i);} //run the iterator with a for loop; we could also have run it by calling .collect() and obtaining a collection What are the domain and range of the functions you mention in Clojure?
  - bad_user 11y ago
    I guess Rust's iterators are pretty standard, meaning that you keep calling "next(): T" until there are no more elements, right? Well that's pretty cool and iterators are generic, but not generic enough. If you'll look closely their protocol has certain constraints. For example the next() call is synchronous. If the next element is not ready, well, tough luck, the current thread needs to be blocked. Another constraint is that iterators produce elements, right? Well, iterators are cool and useful, but many operators like map(), filter() and flatMap() can be applied on things that don't necessarily produce values. As a side note, this is why monads are hard to understand, being a little more abstract than iterators. What transducers from Clojure are doing is to define a more generic protocol (more generic than that of Iterator) such that you can have defined operators, like map and filter, operate on whatever you want, such that you can reuse the implementation of those operators. You can also compose those operators, before applying them to something concrete.
pi-rat 11y ago
Transducers are kind of an abstraction level above what you're describing. Transducers don't care about the medium / collection / stream. The algorithm of your transformation is decoupled from the data structure, and completely reuseable. Clojure used to have (/is deprecating) what you're describing. It's being replaced by transducers to avoid having to implement the same functionality whenever there's a new paradigm/idea. I.e this week we're doing lazy seqs, the next CSP or streams - the transducer logic stays the same.
- Veedrac 11y ago
  > It's being replaced by transducers to avoid having to implement the same functionality whenever there's a new paradigm/idea. I.e this week we're doing lazy seqs, the next CSP or streams - the transducer logic stays the same. AFAICT, iterator adapters don't require you to reimplement the "transducer logic" any more than transducers do. You implement a transformation into an iterator (eg. IntoIterator) and from an iterator (eg. FromIterator) and use the standard transformations on the iterators. Since a transducer is like an iterator adapter, one is comparing these to functions Iterator<A> → Iterator<B>, which can be passed around and reused as first class citizens with no more difficulty than any other object. I'm not sure, but one difference might be that you can't give a chunk of stuff to an iterator adaptor and say "run as much of this as possible, and then suspend". Iterators are inherently pull-based, so instead you say "I want X values". I can imagine the former being more useful in some cases where the producer is deciding when computation should be performed.
- gue5t 11y ago
  Iterator adaptors such as .filter, .flat_map, etc. are all defined with no reference to/knowledge of the iterators they work on: http://doc.rust-lang.org/std/iter/trait.Iterator.html http://doc.rust-lang.org/std/iter/trait.Iterator.html They take a stream of values (i.e., an iterator, which is really only enough state to produce the stream, but not an actual collection of the values produced by that stream) and give you a different stream back, e.g. one that looks like the original stream with a function applied to each element or certain elements removed. Rust iterators are "lazy", and iterator adaptors maintain this property.

by gue5t 11y ago

spooningtamarin 11y ago

And fortunately for us who cannot comprehend it C++17 brings in ranges.

kybernetikos 11y ago

Transducers do not require that every element that comes out of the source results in a single element going into the destination, it can just as well be 0 or many, they also work well with mutable or immutable destinations (because they're a reduce rather than a map so they can modify the destination).

gue5t 11y ago
Perhaps my description was unclear or assumed too much familiarity with Rust, but iterator adaptors such as .filter() and .flat_map support the 0-/many-output use cases you describe, and Vec::extend vs .collect() are a couple of mutable and immutable (resp.) ways to choose the destination of a composition of iterator adaptors.
- kybernetikos 11y ago
  You're right, and that description doesn't make sense. Let me see if I can explain why I said what I said: When you call next on an iterator, you expect it to give you the next value or to tell you that there will be no more values. It's not supposed to give you no value 'for now' or many values. With a transducer it can change your destination value in any way it likes according to your final reducer function. Perhaps it's better to say that iterators are controlled by their destination and so are used in a pull fashion while how reduction functions are used is defined by the source so can be used in push mode. It's easy to emulate pull mode with a push source - you just keep pumping values into one end until one comes out the other, but you can't emulate push with a pull destination, as you can't tell without running your adapters how many values will need to go into the pipe to produce your next value. Imagine you have an event source, and you want values coming out of it to go into some other data structure as they arrive via the same kind of chain of transformations as you might use on a simple data structure. It'd be pretty ugly to do this with iterator adapters (probably have to have an iterator stream of futures, but then you can't do a normal map/filter, etc.), but the reduce on the event stream can pump values through as they come in, regardless of if any of them ever make it to the end of the pipe.

llasram 11y ago

Kind of. Rust iterator adapters are closer to the previous Clojure reducers namespace and the Java 8 streams API. All three take a "collection" and return a new "collection" which includes additional behavior/transformations when ultimately iterated over. Transducers separate out the transformation processes into free-standing composable functions. This makes the transformations first-class values, and makes it possible to apply such transformations to less collection-like entities such as async channels. I'm personally still not sure if it's a good idea or not, but it is an interesting approach.

gue5t 11y ago
I'm not sure you're characterizing Rust iterator adaptors right. Iterator adaptors take an iterator (which usually, but not always, comes from a collection, e.g. "my_vec.into_iter()") and give you another iterator back, without allocating an intermediate collection; the iterator itself stores only the current state of the iteration process. You can apply iterator adaptors to such iterators as the receiving end of a channel ( http://doc.rust-lang.org/std/sync/mpsc/struct.Receiver.html#method.iter http://doc.rust-lang.org/std/sync/mpsc/struct.Receiver.html#... ), and you can pass around the iterator and add other computations to the end of it before you "run" the whole thing. However, I'm not sure what you mean by the transformation processes being functions. In Rust these processes (iterators) are values, and have methods that produce a derived process by appending a step; for a concrete example: let fb_chars = "foobar".chars(); //fb_chars is an iterator let not_o = fb_chars.filter(|&x| x!='o'); //not_o is an iterator; we got it by applying the filter iterator adaptor for i in not_o {println!("char: {}", i);} //run the iterator with a for loop; we could also have run it by calling .collect() and obtaining a collection What are the domain and range of the functions you mention in Clojure?
- bad_user 11y ago
  I guess Rust's iterators are pretty standard, meaning that you keep calling "next(): T" until there are no more elements, right? Well that's pretty cool and iterators are generic, but not generic enough. If you'll look closely their protocol has certain constraints. For example the next() call is synchronous. If the next element is not ready, well, tough luck, the current thread needs to be blocked. Another constraint is that iterators produce elements, right? Well, iterators are cool and useful, but many operators like map(), filter() and flatMap() can be applied on things that don't necessarily produce values. As a side note, this is why monads are hard to understand, being a little more abstract than iterators. What transducers from Clojure are doing is to define a more generic protocol (more generic than that of Iterator) such that you can have defined operators, like map and filter, operate on whatever you want, such that you can reuse the implementation of those operators. You can also compose those operators, before applying them to something concrete.

pi-rat 11y ago

Transducers are kind of an abstraction level above what you're describing. Transducers don't care about the medium / collection / stream. The algorithm of your transformation is decoupled from the data structure, and completely reuseable. Clojure used to have (/is deprecating) what you're describing. It's being replaced by transducers to avoid having to implement the same functionality whenever there's a new paradigm/idea. I.e this week we're doing lazy seqs, the next CSP or streams - the transducer logic stays the same.

Veedrac 11y ago
> It's being replaced by transducers to avoid having to implement the same functionality whenever there's a new paradigm/idea. I.e this week we're doing lazy seqs, the next CSP or streams - the transducer logic stays the same. AFAICT, iterator adapters don't require you to reimplement the "transducer logic" any more than transducers do. You implement a transformation into an iterator (eg. IntoIterator) and from an iterator (eg. FromIterator) and use the standard transformations on the iterators. Since a transducer is like an iterator adapter, one is comparing these to functions Iterator<A> → Iterator<B>, which can be passed around and reused as first class citizens with no more difficulty than any other object. I'm not sure, but one difference might be that you can't give a chunk of stuff to an iterator adaptor and say "run as much of this as possible, and then suspend". Iterators are inherently pull-based, so instead you say "I want X values". I can imagine the former being more useful in some cases where the producer is deciding when computation should be performed.
gue5t 11y ago
Iterator adaptors such as .filter, .flat_map, etc. are all defined with no reference to/knowledge of the iterators they work on: http://doc.rust-lang.org/std/iter/trait.Iterator.html http://doc.rust-lang.org/std/iter/trait.Iterator.html They take a stream of values (i.e., an iterator, which is really only enough state to produce the stream, but not an actual collection of the values produced by that stream) and give you a different stream back, e.g. one that looks like the original stream with a function applied to each element or certain elements removed. Rust iterators are "lazy", and iterator adaptors maintain this property.