Hacker News Reader

Comment by gue5t | Hacker News Reader

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.

View on HN

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.

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#... ), 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?

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.

> 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.

You've lost me. You need to apply the function in `flatMap` to something, and `flatMap` by definition will output zero or more values.

So what do you mean?

The signature of flatMap is something like this:

    flatMap[M,A,B](cc: M[A], f: A => M[B]): M[B]

So given that you respect its signature, M[A] is not necessarily a producer of values. It can be anything and it helps if you think about it not like a collection or a container, but more like a context. For example M[A] could be a function of type S => (A, S). And then you could map and flatMap on such functions to produce other functions. This is the "state monad" btw.

On further thought, the genericism of transducers seems to hurt when you want to combine multiple streams, even somewhat trivially:

   zip_flat xs ys = zip (flatten xs) (flatten ys)

I don't see how you could implement this as a transducer, since a transducer isn't able to reason about its inputs.

I could have been clearer. By the scare-quoted "collection" I meant a value which implements the relevant collection-like interface. In Clojure this is any object `reduce` works on, in Rust is any struct implementing the `Iterator` trait etc. In all the examples discussed these transformations are lazy, only execution the composition of any number of transforms when values are requested.

Clojure transducers are different because a transducer is a function which accepts a reducing function and returns a new reducing function, adding behavior by how the input function is composed into the result function. Because the domain and range of transducers are both reducing functions, they can be chained through function composition. A chain is actually applied by transforming a reducing function then using that function to `reduce` (Rust `fold`) a collection.

The cool part is that the transformations don't refer to collections at all, not even through some highly abstract collection-like interface. This makes them applicable to other domains, like the previously-mentioned channels.

> Because the domain and range of transducers are both reducing functions, they can be chained through function composition. A chain is actually applied by transforming a reducing function then using that function to `reduce` (Rust `fold`) a collection.

For iterators:

Because the domain and range of iterator adaptors are both iterators, they can be chained through function composition. A chain is actually applied by transforming an iterator adaptor then using that iterator adaptor to "iterate" a collection.

Defining a transducer involves returing a closure wrapping some logic around calling a function of type (result, element) → result to get a function of type (result', element) → result'. All the while you're composing, I assume you don't know what this element type is?

Defining an iterator adaptor involves defining the state itself (generally you have a field for the state of the iterator you wrap, and some fields for the state of your transformation itself) and its .next() method for the Iterator impl. The .next() method has type (state, input) → (state, optional output), except that in Rust reality it mutates the state rather than returning a new one.

The difference seems to be that in Rust the output is separate from the state. You could convert an iterator adaptor into a transducer by making the optional output a field in the state.

Also, in Clojure it looks like the usage is that you compose the transducers separately from applying to an input, whereas in Rust you generally compose adaptors on top of the input iterator. I assume this is what you mean with "not referring to the collection at all". In Rust, defining the adaptor chain ahead of applying it would look like:

    let transducer = |x: Iterator| {x.map(xfrm).filter(pred).whatever()};

Which is fine, but not particularly idiomatic, and might require some work annotating types.

> makes it possible to apply such transformations to less collection-like entities such as async channels.

Like https://doc.rust-lang.org/std/sync/mpsc/struct.Receiver.html (scroll down to the trait implementations)?

Ok, bad example :-) Rust's mutable-iterator model of abstract collections supports this directly, but Clojure's functional-reduction model does not. I'll see if I can think of a better example, but it might be hard -- mutable iteration is pretty flexible (which is probably why it's what most languages do...).

That's blocking, not async. Of course you could always create a new thread, but you might want to avoid that for performance reasons...

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

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.

> 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.

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

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.

They also assume that they can always draw from their source iterator if they are called on to produce a value, which means that anything you write for them will not be reusable in scenarios where this isn't true.

Transducers don't have this problem.

Can you describe some situations in which this problem comes up? I'm having a hard time imagining when I would want/expect an iterator adaptor that does something useful on an empty/finished input.

It's not so much empty/finished, it's that values are produced at particular times, perhaps as the user clicks the mouse, or as messages come in from the network or over stdin.

Maybe you're writing some web page analytics software. Let's say you've got a stream of values representing the (x,y) positions of mouse clicks, you want to filter out any that are more than a predefined distance from a particular point, then remove any that occur 200ms or less than the last one, then every time you have 10 of them you want to post them to the server. How would you do this with iterator adaptors?

With transducers, the exact same filter that removes points further than a particular distance away in the event stream can be used on any source (e.g. an iterator).

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).

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.

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.

Reply on news.ycombinator.com