undefined | Better HN

0 pointsMrManatee9y ago0 comments

I agree wholeheartedly with the notion that you should rarely use reduce directly. It is much less useful than map or filter.

Suppose that you have a bunch of things implemented using map or filter. When someone writes parallelized versions of map and filter, all of the existing code gets the benefits.

Now suppose you have a bunch of basic functions implemented using reduce (sum, product, min, max, reverse, ...). Can these be parallelized? Yes - by throwing away the 'reduce' implementation, and starting from scratch.

The problem with reduce, compared to its more useful cousins map and filter, is that it is too powerful. Map and filter are more limited than reduce, but if you can express your computation in terms of maps and filters, you get something valuable in return. If you can express is in terms of reduce, you save a few keystrokes, and that's about it.

For anyone interested in this kind of stuff, I recommend Guy Steele's talk "Organizing Functional Code for Parallel Execution; or, foldl and foldr Considered Slightly Harmful": https://vimeo.com/6624203

0 comments

junke9y ago

Reduce can be parallelized when the reducing function is associative. You can split the input sequence into chunks that are reduced in parallel et merge the results with another sequential reduce.

https://lparallel.org/preduce/

MrManateeOP9y ago

I like that the function in your link is called preduce and not just reduce. Reduce has a standard definition, which doesn't require associativity. To eliminate confusion, a function that does require associativity deserves a different name, just like here.

And using these names, I would say that preduce seems much more useful to me than reduce.

j / k navigate · click thread line to collapse