10 ms·
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 map
by bjoli 9y ago
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
- tathougies 9y agoTo be fair, in Haskell at least, these repeated maps, filters, and folds are translated to single passes
- Sharlin 9y agoAnd 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.
- zawerf 9y agoAre 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-stream-fusion https://stackoverflow.com/questions/578063/what-is-haskells-...
- kazagistar 9y agoIt'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.
- sid-kap 9y agoRegardless of stream fusion, it will always be one pass in Haskell because of laziness.
- tathougies 9y agoStream 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.