第43回　criterionでプログラムの性能を測定する

-- Strategies

-- | A 'Strategy' is a function that embodies a parallel evaluation strategy.
-- The function traverses (parts of) its argument, evaluating subexpressions
-- in parallel or in sequence.
-- 
-- A 'Strategy' may do an arbitrary amount of evaluation of its
-- argument, but should not return a value different from the one it
-- was passed.
--
-- Parallel computations may be discarded by the runtime system if the
-- program no longer requires their result, which is why a 'Strategy'
-- function returns a new value equivalent to the old value.  The
-- intention is that the program applies the 'Strategy' to a
-- structure, and then uses the returned value, discarding the old
-- value.  This idiom is expressed by the 'using' function.
-- 
type Strategy a = a -> Eval a

-- A class of types that can be fully evaluated.
class NFData a where
    -- | rnf should reduce its argument to normal form (that is, fully
    -- evaluate all sub-components), and then return '()'.
    -- 
    -- The default implementation of 'rnf' is 
    --
    -- > rnf a = a `seq` ()
    -- 
    -- which may be convenient when defining instances for data types with
    -- no unevaluated fields (e.g. enumerations).
    rnf :: a -> ()
    rnf a = a `seq` ()

-- | 'rdeepseq' fully evaluates its argument.
--
-- > rdeepseq == evalSeq Control.Seq.rdeepseq
--
rdeepseq :: NFData a => Strategy a
rdeepseq x = rnf x `pseq` return x

qsortPar :: (Ord a, NFData a) => [a] -> [a]
qsortPar []     = []
qsortPar [x]    = [x]
qsortPar (x:xs) = losort ++ (x:hisort) `using` strategy
     where
         losort = qsortPar [ y | y <- xs, y < x]
         hisort = qsortPar [ y | y <- xs, y >= x]
         strategy result = rdeepseq losort `par`
                                    rdeepseq hisort `pseq`
                                    rdeepseq result

primes :: (NFData a, Integral a) => [a]
primes = sieve [2..]
sieve (p:ps) = (p :) $|| rdeepseq
             $ sieve $|| rdeepseq
             $ [q | q <- ps, q `mod` p /= 0]

-- | evaluate a value using the given 'Strategy'.  This is simply
-- 'using' with the arguments reversed.
-- 
withStrategy :: Strategy a -> a -> a
withStrategy = flip using