[swift-evolution] Divide & Conquer Algorithms
jhull at gbis.com
Tue Apr 18 03:02:50 CDT 2017
I would like to see Swift gain something similar to Clojure’s Reducers Library. Basically this is somewhat similar to our Sequence, but for tree-based structures instead of sequential ones. It allows a series of algorithms that operate using a divide and conquer strategy, and it is easy to massively parallelize.
One interesting property is that, because you don’t have to work sequentially, you are able to take a series of calls that do the equivalent of map/filter/flatMap, and compose the functions to make a single call on each piece of data (thus you don’t have build or recurse over intermediate sequences). Everything can be done in a single pass (and that pass can be done in parallel). It can be a big win in terms of efficiency.
Here is a blog post where someone benchmarked ‘fold’ from the reducers library (306ms) vs sequence-based reduce (1450ms):
Here is another post explaining how the idea might work in Python:
Finally here is a video one of the developers of Clojure talking about why this pattern is so great (just after the 19 min mark):
Adding something like this to Swift would be a great boon by providing generic parallelizable algorithms…
More information about the swift-evolution