The Eval monad and strategies

The first abstraction we will look at is the Control.Parallel.Strategies module from the parallel package. The core Strategy API consists of the following:

data Eval a
instance Monad Eval

type Strategy a = a → Eval a

runEval :: Eval a → a

using :: a → Strategy a → a

rseq :: Strategy a
rdeepseq :: NFData a => Strategy a
rpar :: Strategy a

The principle is to use using or runEval to evaluate a lazy data structure in parallel, using some strategy. Essentially we have separated the algorithm (a lazy data structure) from the parallel evaluation (a strategy).

As a simple example, consider calculating the minimum and maximum elements of many lists in parallel. We write an algorithm, which doesn't encode any parallelism, called minmax:

-- file: rows.hs
import Control.Parallel.Strategies
minmax :: [Int] -> (Int, Int)
minmax xs = (minimum xs, maximum xs)

Then we have a list of lists (matrix) and a list of minimums and maximums (minmaxes):

matrix = [ [1..1000001],...