[swift-evolution] Divide & Conquer Algorithms

[Jonathan Hull]

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):
https://adambard.com/blog/clojure-reducers-for-mortals/

Here is another post explaining how the idea might work in Python:
https://adambard.com/blog/Reducers-explained-through-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):
https://www.infoq.com/presentations/Clojure-Design-Patterns

Adding something like this to Swift would be a great boon by providing generic parallelizable algorithms…

Thanks,
Jon