How do I write a parallel reduction using strategies in Haskell?

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?

6
задан Chad Scherrer 26 October 2010 в 21:32
поделиться