4 ms·
Doesn't building map with a fold hide its inherent parallelizability? The nice thing about map, as opposed to fold, is that you don't need to know the result o
by carlob 14y ago
Doesn't building map with a fold hide its inherent parallelizability?
The nice thing about map, as opposed to fold, is that you don't need to know the result of the ith step to do the i+1th.
- Martijn 14y agoNot really. There's a really nice paper by Graham Hutton, "A tutorial on the universality and expressiveness of fold" which goes into a bit more depth than OP does. Your question is answered directly in section 3.2, "The fusion property of fold". Basically, a sequence of multiple folds can be fused to a single fold. See http://www.cs.nott.ac.uk/~gmh/fold.pdf http://www.cs.nott.ac.uk/~gmh/fold.pdf
- drudru11 14y agoAwesome - I had the same question. I was basically wondering how to inform the system of the opportunity to parallelize. BTW, Hutton's book on Haskell is just so excellent.
- carlob 14y agoThe article you linked proves the universality of fold, that I never doubted for one second. What I was trying to say is that map is not universal, in that all function evaluations can be performed in parallel, because you can't use the result of the ith to compute the i+1th. In this respect map is in fact a restriction of fold.
- deleted 14y ago[deleted]
- DougWebb 14y agoThat depends on your map function, for most languages. If your map function includes external state (like a variable from an outer scope) then the execution sequence could change the map function's output. Eg, in C#: var i = 5; var result = input.select(item => { var val = item.v + i; i = val; return val; }); This would be an awful programming practice, but it serves as an example that map isn't necessarily parrallelizable.