Hacker News Reader

Comment by jakestl | Hacker News Reader

In python I can do:

  filter(lambda x: x%2==0, xrange(10))

Is this basically the same concept?

View on HN

No, because chaining that with an additional filter operation will create intermediate lists.

If filter() returned an iterator instead of a list would the answer be yes?

Essentially, yes. The performance benefit that transducers provide can also be obtained by using iterator versions of map, reduce, and filter.

Unlike those traditional functions, however, transducer versions are composable. So I can put a whole bunch of maps, reducers, and filters in a row, and assign that composition to a variable. Then I can apply that composition to any type of collection and know that it only requires one pass.

Or by a sufficiently smart compiler that realises it can fuse the intermediate steps into a single loop (like GHC)?).

So, the appeal of transducers is plug-and-play fusion. Like, it takes quite a bit of work to get newly created non-list types to fuse correctly in Haskell (that being said: you can do it in Haskell, which is kind of amazing considering how ridiculously impossible this is in almost every toolset, and popular libraries already have, which is also amazing). Transducers get you stream fusion for e.g. channels in a close-to-free way (you define the stepping function, you get takeWhile, partition-by, etc. all for free, so it's O(1) instead of O(n)-O(n^2) to figure out all the combos you want to stream together).

EDIT: _part_ of the appeal. The other is concisely describing things like takeWhile in a way that's both polymorphic and doesn't require multiple implementations. Good refactor motivation in general, happens to have the above property, which is good.

in python3 filter returns an iterator.

Reply on news.ycombinator.com