In high-performance computing, sums, products, etc are often calculated using a "parallel reduction" that takes n elements and completes in O(log n) time (given enough parallelism). In Haskell, we usually use a fold for this kind of calculation, but evaluation time is always linear in the length of the list.
Data Parallel Haskell has some of this built in, but what about in the common framework of a list? Can we do it with Control.Parallel.Strategies
?
So, assuming f
is associative, how do we write
parFold :: (a -> a -> a) -> [a] -> a
so that parFold f xs
only needs time logarithmic in length xs
?