Beautiful folds in Haskell (2016) | Hacker News Reader

Beautiful folds in Haskell (2016)

github.com

63 pointsfanf29 comments

This seems to be a transcript of a talk but it wasn't linked to: https://www.youtube.com/watch?v=6a5Ti0r8Q2s

Coming from a scheme world I find it pretty common that people don't know that a left fold is the fundamental list iterator.

You often find people chaining maps and folds and doing all kinds of strange things when a single fold would suffice.

I can live with people not grokking unfold, but the amount of time wasted because people emulate fold using at least 2 passes over a list is probably close to my own petty 30 year lifetime

To be fair, in Haskell at least, these repeated maps, filters, and folds are translated to single passes

And in Clojure, Rust, Scala, Java... With sequence combinators being lazy in almost all languages that have them, writing complex folds isn’t usually a very good idea if the same thing can be achieved in discrete map/filter/etc steps.

Are they? I tried understanding how that worked a few years ago and it led me to something called "stream fusion" which seems like a magical set of code rewriting rules that wasn't even on by default in haskell[1].

For example if you did a map of x times 2 then map again with x times 2, I expect a single map of x times 4 without using temporary buffers or multiple passes for the intermediate map (this is a simple example, but gets more complicate once you throw in other stream operators).

I know java didn't do this when I was looking at their collectors source code back then.

[1] https://stackoverflow.com/questions/578063/what-is-haskells-...

It's not direct, as in Haskell, but it's there and used. Java has Streams, Kotlin has sequences, Scale has Seq, Rust has iter, etc. Lazyness is useful for iteration so languages with reasonable modernization make it readily availible in that context.

Regardless of stream fusion, it will always be one pass in Haskell because of laziness.

Stream fusion is only necessary for otherwise strict data types (like text, bytestring, vector, etc). Regular haskell lists will be 'fused' by default due to laziness, although the standard library does also fuse repeated list operations into an even more streamlined representation. However, this can be seen as more of a compiler optimization than anything, as it doesn't change the runtime complexity or the space complexity. Mapping over a list however many times always takes O(1) space, due to laziness.

Collectors in Java >= 8 are quite reminiscent of these "beautiful folds", so much that I have wondered why the standard library lacks a proper Applicative-like composition method, which is so useful for avoiding multiple traversals of the data.

Something like it can be defined: https://stackoverflow.com/questions/30210547/grouping-by-obj... although the signature is a bit ugly.

Reply on news.ycombinator.com