Hacker News new | comments | show | ask | jobs | submit login

Isn't foldr/build fusion much closer? A collection is represented by a "build" function that takes the reducer, and list transformers become reducer transformers. The main difference is that it's applied automatically by list library using rewrite rules, so it's not as obvious, the reducer is supplied as a pair of "cons" function and "init" value rather than a variadic function, and there's no parallel fold.

http://research.microsoft.com/~simonpj/papers/deforestation-... The first paper (yes, that's a .ps.Z - check the date)

http://www.scs.stanford.edu/11au-cs240h/notes/omgwtfbbq.html some recent slides, which also include a bit about a "stream fusion" which isn't yet in the standard library

http://darcs.haskell.org/cgi-bin/gitweb.cgi?p=packages/base.... The details from GHC's libraries - it's all in the RULES.




> and there's no parallel fold.

When working up from the bottom it might seem that this is just manual stream/list fusion. But the parallelism is the key prize. We need to stop defining map/filter etc in terms of lists/sequences, and, once we do, there is nothing to fuse, no streams/thunks to avoid allocating etc, because they were never essential in the first place, just an artifact of the history of FP and its early emphasis on lists and recursion.


Yes, foldr/build is almost exactly reducibles, but not foldables.

Iterators do nothing for parallelism either.




Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | DMCA | Apply to YC | Contact

Search: