parallel 1.1.0.1 → 3.3.0.0
raw patch · 5 files changed
Files
- Control/Parallel.hs +31/−53
- Control/Parallel/Strategies.hs +989/−605
- Control/Seq.hs +204/−0
- changelog.md +52/−0
- parallel.cabal +64/−17
Control/Parallel.hs view
@@ -1,71 +1,46 @@+{-# LANGUAGE CPP #-}+ ----------------------------------------------------------------------------- -- | -- Module : Control.Parallel -- Copyright : (c) The University of Glasgow 2001 -- License : BSD-style (see the file libraries/base/LICENSE)--- +-- -- Maintainer : libraries@haskell.org--- Stability : experimental--- Portability : non-portable+-- Stability : stable+-- Portability : portable ----- Parallel Constructs+-- Parallel constructs. --+-- A common pattern to evaluate two values in parallel is:+--+-- > x `par` y `pseq` someFunc x y+--+-- The effect of this pattern is to cause @x@ to be evaluated in+-- parallel with @y@. When the evaluation of @y@ is complete, computation+-- proceeds by evaluating @someFunc x y@.+-- ----------------------------------------------------------------------------- module Control.Parallel (- par, pseq,- seq, -- for backwards compatibility, 6.6 exported this-#if defined(__GRANSIM__)- , parGlobal, parLocal, parAt, parAtAbs, parAtRel, parAtForNow -#endif+ par, pseq ) where -import Prelude- #ifdef __GLASGOW_HASKELL__-import qualified GHC.Conc ( par, pseq )--infixr 0 `par`, `pseq`+import qualified GHC.Conc (par, pseq) #endif -#if defined(__GRANSIM__)-import PrelBase-import PrelErr ( parError )-import PrelGHC ( parGlobal#, parLocal#, parAt#, parAtAbs#, parAtRel#, parAtForNow# )--infixr 0 `par`--{-# INLINE parGlobal #-}-{-# INLINE parLocal #-}-{-# INLINE parAt #-}-{-# INLINE parAtAbs #-}-{-# INLINE parAtRel #-}-{-# INLINE parAtForNow #-}-parGlobal :: Int -> Int -> Int -> Int -> a -> b -> b-parLocal :: Int -> Int -> Int -> Int -> a -> b -> b-parAt :: Int -> Int -> Int -> Int -> a -> b -> c -> c-parAtAbs :: Int -> Int -> Int -> Int -> Int -> a -> b -> b-parAtRel :: Int -> Int -> Int -> Int -> Int -> a -> b -> b-parAtForNow :: Int -> Int -> Int -> Int -> a -> b -> c -> c--parGlobal (I# w) (I# g) (I# s) (I# p) x y = case (parGlobal# x w g s p y) of { 0# -> parError; _ -> y }-parLocal (I# w) (I# g) (I# s) (I# p) x y = case (parLocal# x w g s p y) of { 0# -> parError; _ -> y }--parAt (I# w) (I# g) (I# s) (I# p) v x y = case (parAt# x v w g s p y) of { 0# -> parError; _ -> y }-parAtAbs (I# w) (I# g) (I# s) (I# p) (I# q) x y = case (parAtAbs# x q w g s p y) of { 0# -> parError; _ -> y }-parAtRel (I# w) (I# g) (I# s) (I# p) (I# q) x y = case (parAtRel# x q w g s p y) of { 0# -> parError; _ -> y }-parAtForNow (I# w) (I# g) (I# s) (I# p) v x y = case (parAtForNow# x v w g s p y) of { 0# -> parError; _ -> y }--#endif+infixr 0 `par`, `pseq` -- Maybe parIO and the like could be added here later. -- | Indicates that it may be beneficial to evaluate the first -- argument in parallel with the second. Returns the value of the -- second argument.--- --- @a `par` b@ is exactly equivalent semantically to @b@. --+-- The result of @a ``par`` b@ is always @b@, regardless of whether+-- @a@ evaluates to a bottom, so for example @par undefined x = x@.+-- -- @par@ is generally used when the value of @a@ is likely to be -- required later, but not immediately. Also it is a good idea to -- ensure that @a@ is not a trivial computation, otherwise the cost of@@ -73,20 +48,24 @@ -- running it in parallel. -- -- Note that actual parallelism is only supported by certain--- implementations (GHC with the @-threaded@ option, and GPH, for--- now). On other implementations, @par a b = b@.---+-- implementations (GHC with the @-threaded@ option, for now).+-- On other implementations, @par a b = b@. par :: a -> b -> b #ifdef __GLASGOW_HASKELL__ par = GHC.Conc.par #else--- For now, Hugs does not support par properly.+-- For now, Hugs and MicroHs don't support par properly. par a b = b #endif --- | Semantically identical to 'seq', but with a subtle operational--- difference: 'seq' is strict in both its arguments, so the compiler--- may, for example, rearrange @a `seq` b@ into @b `seq` a `seq` b@.+-- | Like 'seq' but ensures that the first argument is evaluated before returning.+--+-- @a ``pseq`` b@ evaluates @a@ to weak head normal form (WHNF)+-- before returning @b@.+--+-- This is similar to 'seq', but with a subtle difference:+-- 'seq' is strict in both its arguments, so the compiler+-- may, for example, rearrange @a ``seq`` b@ into @b ``seq`` a ``seq`` b@. -- This is normally no problem when using 'seq' to express strictness, -- but it can be a problem when annotating code for parallelism, -- because we need more control over the order of evaluation; we may@@ -97,7 +76,6 @@ -- strict in its first argument (as far as the compiler is concerned), -- which restricts the transformations that the compiler can do, and -- ensures that the user can retain control of the evaluation order.--- pseq :: a -> b -> b #ifdef __GLASGOW_HASKELL__ pseq = GHC.Conc.pseq
Control/Parallel/Strategies.hs view
@@ -1,605 +1,989 @@--------------------------------------------------------------------------------- |--- Module : Control.Parallel.Strategies--- Copyright : (c) The University of Glasgow 2001--- License : BSD-style (see the file libraries/base/LICENSE)--- --- Maintainer : libraries@haskell.org--- Stability : experimental--- Portability : non-portable------ Parallel strategy combinators. See--- <http://www.macs.hw.ac.uk/~dsg/gph/papers/html/Strategies/strategies.html>--- for more information.------ Original authors:--- Phil Trinder, Hans-Wolfgang Loidl, Kevin Hammond et al. ----------------------------------------------------------------------------------module Control.Parallel.Strategies (- -- * Strategy Type, Application and Semantics- Done, Strategy,- (>|), (>||),- using, demanding, sparking,- -- * Basic Strategies - r0, rwhnf, NFData(..),- -- * Strategic Function Application- ($|), ($||),- (.|), (.||),- (-|), (-||),- -- * Tuples- seqPair, parPair,- seqTriple, parTriple,- -- * Lists: Parallel Strategies- parList, parListN, parListNth, parListChunk, - parMap, parFlatMap, parZipWith,- -- * Lists: Sequential Strategies- seqList, seqListN, seqListNth, parBuffer,- -- * Arrays- seqArr, parArr,- -- * Deprecated types and functions- sPar, sSeq,- Assoc(..),- fstPairFstList, force, sforce- ) where---- based on hslibs/concurrent/Strategies.lhs; see it for more detailed--- code comments. --import Control.Parallel as Parallel (par, pseq)-import Data.Array-import Data.Complex-import Data.Int-import qualified Data.IntMap (IntMap, toList)-import qualified Data.IntSet (IntSet, toList)-import qualified Data.Map (Map, toList)-import qualified Data.Set (Set, toList)-import qualified Data.Tree (Tree(..))-import Data.Word--import Prelude hiding (seq)-import qualified Prelude (seq)---- not a terribly portable way of getting at Ratio rep.-#ifdef __GLASGOW_HASKELL__-import GHC.Real (Ratio(..)) -- The basic defns for Ratio-#endif--#ifdef __HUGS__-import Hugs.Prelude(Ratio(..) )-#endif--#ifdef __NHC__-import Ratio (Ratio(..) )-#endif--infixl 0 `using`,`demanding`,`sparking` -- weakest precedence!--infixr 2 >|| -- another name for par-infixr 3 >| -- another name for seq-infixl 6 $||, $| -- strategic function application (seq and par)-infixl 9 .|, .||, -|, -|| -- strategic (inverse) function composition--infixl 0 `seq`---- We need 'pseq', not the Prelude 'seq' here. See the documentation--- with 'pseq' in Control.Parallel.-seq = Parallel.pseq----------------------------------------------------------------------------------- * Strategy Type, Application and Semantics ---------------------------------------------------------------------------------{--The basic combinators for strategies are 'par' and 'seq' but with types that -indicate that they only combine the results of a strategy application. --NB: This version can be used with Haskell 1.4 (GHC 2.05 and beyond), *but*- you won't get strategy checking on seq (only on par)!--The operators >| and >|| are alternative names for `seq` and `par`.-With the introduction of a Prelude function `seq` separating the Prelude -function from the Strategy function becomes a pain. The notation also matches-the notation for strategic function application.--}--type Done = ()---- | A strategy takes a value and returns a 'Done' value to indicate that--- the specifed evaluation has been performed.-type Strategy a = a -> Done----- | Evaluates the first argument before the second.-(>|) :: Done -> Done -> Done -{-# INLINE (>|) #-}-(>|) = Prelude.seq---- | Evaluates the first argument in parallel with the second.-(>||) :: Done -> Done -> Done -{-# INLINE (>||) #-}-(>||) = Parallel.par----- | Takes a value and a strategy, and applies the strategy to the--- value before returning the value. Used to express data-oriented --- parallelism. @x \`using\` s@ is a projection on @x@, i.e. both:------ [a retraction] @x \`using\` s@ ⊑ @x@------ [idempotent] @(x \`using\` s) \`using\` s@ = @x \`using\` s@----using :: a -> Strategy a -> a-using x s = s x `seq` x----- | Evaluates the second argument before the first.--- Used to express control-oriented parallelism. The second--- argument is usually a strategy application.-demanding :: a -> Done -> a-demanding = flip seq----- | Evaluates the second argument in parallel with the first.--- Used to express control-oriented--- parallelism. The second argument is usually a strategy application.-sparking :: a -> Done -> a-sparking = flip Parallel.par--- Sparking should only be used--- with a singleton sequence as it is not necessarily executed.---- | A strategy corresponding to 'par': --- @x \`par\` e@ = @e \`using\` sPar x@.------ 'sPar' has been superceded by 'sparking'.--- Replace @e \`using\` sPar x@ with @e \`sparking\` rwhnf x@.-{-# DEPRECATED sPar "Use sparking instead." #-}-sPar :: a -> Strategy b-sPar x y = x `par` ()---- | A strategy corresponding to 'seq': --- @x \`seq\` e@ = @e \`using\` sSeq x@.------ 'sSeq' has been superceded by 'demanding'. --- Replace @e \`using\` sSeq x@ with @e \`demanding\` rwhnf x@.-{-# DEPRECATED sSeq "Use demanding instead." #-}-sSeq :: a -> Strategy b-sSeq x y = x `seq` ()---------------------------------------------------------------------------------- * Basic Strategies ---------------------------------------------------------------------------------- | Performs /no/ evaluation of its argument.-r0 :: Strategy a -r0 x = ()---- | Reduces its argument to weak head normal form.-rwhnf :: Strategy a -rwhnf x = x `seq` () --class NFData a where- -- | Reduces its argument to (head) normal form.- rnf :: Strategy a- -- Default method. Useful for base types. A specific method is necessay for- -- constructed types- rnf = rwhnf--class (NFData a, Integral a) => NFDataIntegral a-class (NFData a, Ord a) => NFDataOrd a----------------------------------------------------------------------------------- * Strategic Function Application---------------------------------------------------------------------------------{--These are very-handy when writing pipeline parallelism asa sequence of @$@, @$|@ and-@$||@'s. There is no need of naming intermediate values in this case. The-separation of algorithm from strategy is achieved by allowing strategies-only as second arguments to @$|@ and @$||@.--}---- | Sequential function application. The argument is evaluated using--- the given strategy before it is given to the function.-($|) :: (a -> b) -> Strategy a -> a -> b-f $| s = \ x -> f x `demanding` s x---- | Parallel function application. The argument is evaluated using--- the given strategy, in parallel with the function application.-($||) :: (a -> b) -> Strategy a -> a -> b-f $|| s = \ x -> f x `sparking` s x---- | Sequential function composition. The result of--- the second function is evaluated using the given strategy, --- and then given to the first function.-(.|) :: (b -> c) -> Strategy b -> (a -> b) -> (a -> c)-(.|) f s g = \ x -> let gx = g x - in f gx `demanding` s gx---- | Parallel function composition. The result of the second--- function is evaluated using the given strategy,--- in parallel with the application of the first function.-(.||) :: (b -> c) -> Strategy b -> (a -> b) -> (a -> c)-(.||) f s g = \ x -> let gx = g x - in f gx `sparking` s gx---- | Sequential inverse function composition, --- for those who read their programs from left to right.--- The result of the first function is evaluated using the --- given strategy, and then given to the second function.-(-|) :: (a -> b) -> Strategy b -> (b -> c) -> (a -> c)-(-|) f s g = \ x -> let fx = f x - in g fx `demanding` s fx---- | Parallel inverse function composition,--- for those who read their programs from left to right.--- The result of the first function is evaluated using the --- given strategy, in parallel with the application of the --- second function.-(-||) :: (a -> b) -> Strategy b -> (b -> c) -> (a -> c)-(-||) f s g = \ x -> let fx = f x - in g fx `sparking` s fx ----------------------------------------------------------------------------------- Marking a Strategy---------------------------------------------------------------------------------{--Marking a strategy.--Actually, @markStrat@ sticks a label @n@ into the sparkname field of the-thread executing strategy @s@. Together with a runtime-system that supports-propagation of sparknames to the children this means that this strategy and-all its children have the sparkname @n@ (if the static sparkname field in-the @parGlobal@ annotation contains the value 1). Note, that the @SN@ field-of starting the marked strategy itself contains the sparkname of the parent-thread. The END event contains @n@ as sparkname.--}--#if 0-markStrat :: Int -> Strategy a -> Strategy a -markStrat n s x = unsafePerformPrimIO (- _casm_ ``%r = set_sparkname(CurrentTSO, %0);'' n `thenPrimIO` \ z ->- returnPrimIO (s x))-#endif---------------------------------------------------------------------------------- Strategy Instances and Functions ---------------------------------------------------------------------------------------------------------------------------------------------------------------- * Tuples--------------------------------------------------------------------------------{--We currently support up to 9-tuples. If you need longer tuples you have to -add the instance explicitly to your program.--}--instance (NFData a, NFData b) => NFData (a,b) where- rnf (x,y) = rnf x `seq` rnf y--instance (NFData a, NFData b, NFData c) => NFData (a,b,c) where- rnf (x,y,z) = rnf x `seq` rnf y `seq` rnf z --instance (NFData a, NFData b, NFData c, NFData d) => NFData (a,b,c,d) where- rnf (x1,x2,x3,x4) = rnf x1 `seq` - rnf x2 `seq` - rnf x3 `seq` - rnf x4 --instance (NFData a1, NFData a2, NFData a3, NFData a4, NFData a5) => - NFData (a1, a2, a3, a4, a5) where- rnf (x1, x2, x3, x4, x5) =- rnf x1 `seq`- rnf x2 `seq`- rnf x3 `seq`- rnf x4 `seq`- rnf x5--instance (NFData a1, NFData a2, NFData a3, NFData a4, NFData a5, NFData a6) => - NFData (a1, a2, a3, a4, a5, a6) where- rnf (x1, x2, x3, x4, x5, x6) =- rnf x1 `seq`- rnf x2 `seq`- rnf x3 `seq`- rnf x4 `seq`- rnf x5 `seq`- rnf x6--instance (NFData a1, NFData a2, NFData a3, NFData a4, NFData a5, NFData a6, NFData a7) => - NFData (a1, a2, a3, a4, a5, a6, a7) where- rnf (x1, x2, x3, x4, x5, x6, x7) =- rnf x1 `seq`- rnf x2 `seq`- rnf x3 `seq`- rnf x4 `seq`- rnf x5 `seq`- rnf x6 `seq`- rnf x7--instance (NFData a1, NFData a2, NFData a3, NFData a4, NFData a5, NFData a6, NFData a7, NFData a8) => - NFData (a1, a2, a3, a4, a5, a6, a7, a8) where- rnf (x1, x2, x3, x4, x5, x6, x7, x8) =- rnf x1 `seq`- rnf x2 `seq`- rnf x3 `seq`- rnf x4 `seq`- rnf x5 `seq`- rnf x6 `seq`- rnf x7 `seq`- rnf x8--instance (NFData a1, NFData a2, NFData a3, NFData a4, NFData a5, NFData a6, NFData a7, NFData a8, NFData a9) => - NFData (a1, a2, a3, a4, a5, a6, a7, a8, a9) where- rnf (x1, x2, x3, x4, x5, x6, x7, x8, x9) =- rnf x1 `seq`- rnf x2 `seq`- rnf x3 `seq`- rnf x4 `seq`- rnf x5 `seq`- rnf x6 `seq`- rnf x7 `seq`- rnf x8 `seq`- rnf x9---- | Apply two strategies to the elements of a pair sequentially--- from left to right.-seqPair :: Strategy a -> Strategy b -> Strategy (a,b)-seqPair strata stratb (x,y) = strata x `seq` stratb y ---- | Apply two strategies to the elements of a pair in parallel.-parPair :: Strategy a -> Strategy b -> Strategy (a,b)-parPair strata stratb (x,y) = strata x `par` stratb y `par` ()--- The reason for the last 'par' is so that the strategy terminates --- quickly. This is important if the strategy is used as the 1st --- argument of a seq---- | Apply three strategies to the elements of a triple in sequentially--- from left to right.-seqTriple :: Strategy a -> Strategy b -> Strategy c -> Strategy (a,b,c)-seqTriple strata stratb stratc p@(x,y,z) = - strata x `seq` - stratb y `seq`- stratc z ---- | Apply three strategies to the elements of a triple in parallel.-parTriple :: Strategy a -> Strategy b -> Strategy c -> Strategy (a,b,c)-parTriple strata stratb stratc (x,y,z) = - strata x `par` - stratb y `par` - stratc z `par`- ()---------------------------------------------------------------------------------- Atomic types--------------------------------------------------------------------------------{--Weak head normal form and normal form are identical for integers, so the -default rnf is sufficient. --}-instance NFData Int -instance NFData Integer-instance NFData Float-instance NFData Double--instance NFData Int8-instance NFData Int16-instance NFData Int32-instance NFData Int64--instance NFData Word8-instance NFData Word16-instance NFData Word32-instance NFData Word64--instance NFDataIntegral Int-instance NFDataOrd Int----Rational and complex numbers.--instance (Integral a, NFData a) => NFData (Ratio a) where- rnf (x:%y) = rnf x `seq` - rnf y `seq`- ()--instance (RealFloat a, NFData a) => NFData (Complex a) where- rnf (x:+y) = rnf x `seq` - rnf y `seq`- ()--instance NFData Char-instance NFData Bool-instance NFData ()---------------------------------------------------------------------------------- Various library types --------------------------------------------------------------------------------instance NFData a => NFData (Maybe a) where- rnf Nothing = ()- rnf (Just x) = rnf x--instance (NFData a, NFData b) => NFData (Either a b) where- rnf (Left x) = rnf x- rnf (Right y) = rnf y--instance (NFData k, NFData a) => NFData (Data.Map.Map k a) where- rnf = rnf . Data.Map.toList--instance NFData a => NFData (Data.Set.Set a) where- rnf = rnf . Data.Set.toList--instance NFData a => NFData (Data.Tree.Tree a) where- rnf (Data.Tree.Node r f) = rnf r `seq` rnf f--instance NFData a => NFData (Data.IntMap.IntMap a) where- rnf = rnf . Data.IntMap.toList--instance NFData Data.IntSet.IntSet where- rnf = rnf . Data.IntSet.toList---------------------------------------------------------------------------------- Lists --------------------------------------------------------------------------------instance NFData a => NFData [a] where- rnf [] = ()- rnf (x:xs) = rnf x `seq` rnf xs--------------------------------------------------------------------------------- * Lists: Parallel Strategies--------------------------------------------------------------------------------- | Applies a strategy to every element of a list in parallel.-parList :: Strategy a -> Strategy [a]-parList strat [] = ()-parList strat (x:xs) = strat x `par` (parList strat xs)---- | Applies a strategy to the first @n@ elements of a list in parallel.-parListN :: (Integral b) => b -> Strategy a -> Strategy [a]-parListN n strat [] = ()-parListN 0 strat xs = ()-parListN n strat (x:xs) = strat x `par` (parListN (n-1) strat xs)---- | Evaluates @n@ elements of the spine of the argument list and applies--- the given strategy to the @n@th element (if there is one) in parallel with--- the result. E.g. @parListNth 2 [e1, e2, e3]@ evaluates @e3@.-parListNth :: Int -> Strategy a -> Strategy [a]-parListNth n strat xs - | null rest = ()- | otherwise = strat (head rest) `par` ()- where- rest = drop n xs---- | Splits a list into chunks (sub-sequences) of length @n@,--- and applies a strategy sequentially to the elements in each--- chunk. The chunks are evaluated in parallel.--- This is useful for increasing the grain size.-parListChunk :: Int -> Strategy a -> Strategy [a]-parListChunk n strat [] = ()-parListChunk n strat xs = seqListN n strat xs `par` - parListChunk n strat (drop n xs)---- | Applies a function to each element of a list and --- and evaluates the result list in parallel,--- using the given strategy for each element.-parMap :: Strategy b -> (a -> b) -> [a] -> [b]-parMap strat f xs = map f xs `using` parList strat---- | Uses 'parMap' to apply a list-valued function to each--- element of a list in parallel, and concatenates the results.-parFlatMap :: Strategy [b] -> (a -> [b]) -> [a] -> [b]-parFlatMap strat f xs = concat (parMap strat f xs)---- | Zips together two lists using a function,--- and evaluates the result list in parallel.-parZipWith :: Strategy c -> (a -> b -> c) -> [a] -> [b] -> [c]-parZipWith strat z as bs = - zipWith z as bs `using` parList strat--------------------------------------------------------------------------------- * Lists: Sequential Strategies--------------------------------------------------------------------------------- | Sequentially applies a strategy to each element of a list.-seqList :: Strategy a -> Strategy [a]-seqList strat [] = ()-seqList strat (x:xs) = strat x `seq` (seqList strat xs)---- | Sequentially applies a strategy to the first n elements of a list.-{-# SPECIALISE seqListN :: Int -> Strategy b -> Strategy [b] #-}-seqListN :: (Integral a) => a -> Strategy b -> Strategy [b]-seqListN n strat [] = ()-seqListN 0 strat xs = ()-seqListN n strat (x:xs) = strat x `seq` (seqListN (n-1) strat xs)---- | Applies a strategy to the @n@th element of a list--- (if there is one) before returning the result. --- E.g. @seqListNth 2 [e1, e2, e3]@ evaluates @e3@.-seqListNth :: Int -> Strategy b -> Strategy [b]-seqListNth n strat xs - | null rest = ()- | otherwise = strat (head rest) - where- rest = drop n xs---- | Applies a strategy to the nth element of list when the head is demanded.--- More precisely:------ * semantics: @parBuffer n s = id :: [a] -> [a]@------ * dynamic behaviour: evalutates the nth element of the list when the--- head is demanded.------ The idea is to provide a `rolling buffer' of length n.------ 'parBuffer' has been added for the revised version of the strategies--- paper and supersedes the older @fringeList@.-parBuffer :: Int -> Strategy a -> [a] -> [a]-parBuffer n s xs = - return xs (start n xs)- where- return (x:xs) (y:ys) = (x:return xs ys) `sparking` s y- return xs [] = xs-- start n [] = []- start 0 ys = ys- start n (y:ys) = start (n-1) ys `sparking` s y--{-- 'fringeList' implements a `rolling buffer' of length n, i.e.applies a- strategy to the nth element of list when the head is demanded. More- precisely:-- semantics: fringeList n s = id :: [b] -> [b]- dynamic behaviour: evalutates the nth element of the list when the- head is demanded.- - The idea is to provide a `rolling buffer' of length n.-fringeList :: (Integral a) => a -> Strategy b -> [b] -> [b]-fringeList n strat [] = []-fringeList n strat (r:rs) = - seqListNth n strat rs `par`- r:fringeList n strat rs--}----------------------------------------------------------------------------------- * Arrays--------------------------------------------------------------------------------instance (Ix a, NFData a, NFData b) => NFData (Array a b) where- rnf x = rnf (bounds x) `seq` seqList rnf (elems x) `seq` ()---- | Apply a strategy to all elements of an array sequentially.-seqArr :: (Ix b) => Strategy a -> Strategy (Array b a)-seqArr s arr = seqList s (elems arr)---- | Apply a strategy to all elements of an array in parallel.-parArr :: (Ix b) => Strategy a -> Strategy (Array b a)-parArr s arr = parList s (elems arr)--{-# DEPRECATED Assoc "Does not belong in Control.Parallel.Strategies" #-}-data Assoc a b = a := b deriving ()--instance (NFData a, NFData b) => NFData (Assoc a b) where- rnf (x := y) = rnf x `seq` rnf y `seq` ()----------------------------------------------------------------------------------- * Some strategies specific for Lolita ---------------------------------------------------------------------------------{-# DEPRECATED fstPairFstList "This was just an example. Write your own." #-}-fstPairFstList :: (NFData a) => Strategy [(a,b)]-fstPairFstList = seqListN 1 (seqPair rwhnf r0)---- Some HACKs for Lolita. AFAIK force is just another name for our rnf and--- sforce is a shortcut (definition here is identical to the one in Force.lhs)--{-# DEPRECATED force, sforce "Lolita-specific hacks." #-}-force :: (NFData a) => a -> a -sforce :: (NFData a) => a -> b -> b--force = id $| rnf-sforce x y = force x `seq` y+{-# LANGUAGE BangPatterns, CPP, MagicHash, UnboxedTuples #-}+{-# LANGUAGE GeneralizedNewtypeDeriving #-}+{-# LANGUAGE RecursiveDo #-}+-----------------------------------------------------------------------------+-- |+-- Module : Control.Parallel.Strategies+-- Copyright : (c) The University of Glasgow 2001-2010+-- License : BSD-style (see the file libraries/base/LICENSE)+--+-- Maintainer : libraries@haskell.org+-- Stability : experimental+-- Portability : portable+--+-- Parallel evaluation strategies, or strategies for short, provide+-- ways to express parallel computations. Strategies have the following+-- key features:+--+-- * Strategies express /deterministic parallelism/:+-- the result of the program is unaffected by evaluating in parallel.+-- The parallel tasks evaluated by a strategy may have no side effects.+-- For non-deterministic parallel programming, see "Control.Concurrent".+--+-- * Strategies let you separate the description of the parallelism from the+-- logic of your program, enabling modular parallelism. The basic idea+-- is to build a lazy data structure representing the computation, and+-- then write a strategy that describes how to traverse the data structure+-- and evaluate components of it sequentially or in parallel.+--+-- * Strategies are /compositional/: larger strategies can be built+-- by gluing together smaller ones.+--+-- * The 'Eval' monad is provided, for quickly building+-- strategies that involve traversing structures in a regular way.+--+-- For API history and changes in this release, see "Control.Parallel.Strategies#history".++-----------------------------------------------------------------------------++module Control.Parallel.Strategies (+ -- * The strategy type+ Strategy++ -- * Application of strategies+ , using -- :: a -> Strategy a -> a+ , withStrategy -- :: Strategy a -> a -> a+ , usingIO -- :: a -> Strategy a -> IO a+ , withStrategyIO -- :: Strategy a -> a -> IO a++ -- * Composition of strategies+ , dot -- :: Strategy a -> Strategy a -> Strategy a++ -- * Basic strategies+ , r0 -- :: Strategy a+ , rseq+ , rdeepseq -- :: NFData a => Strategy a+ , rpar -- :: Strategy a+ , rparWith -- :: Strategy a -> Strategy a++ -- * Injection of sequential strategies+ , evalSeq -- :: Seq.Strategy a -> Strategy a+ , SeqStrategy++ -- * Strategies for traversable data types+ , evalTraversable -- :: Traversable t => Strategy a -> Strategy (t a)+ , parTraversable+ , parFmap++ -- * Strategies for lists+ , evalList -- :: Strategy a -> Strategy [a]+ , parList+ , evalListN -- :: Int -> Strategy a -> Strategy [a]+ , parListN+ , evalListNth -- :: Int -> Strategy a -> Strategy [a]+ , parListNth+ , evalListSplitAt -- :: Int -> Strategy [a] -> Strategy [a] -> Strategy [a]+ , parListSplitAt+ , parListChunk+ , parMap++ -- ** Strategies for lazy lists+ , evalBuffer -- :: Int -> Strategy a -> Strategy [a]+ , parBuffer++ -- * Strategies for tuples++ -- | Evaluate the components of a tuple according to the+ -- given strategies.++ , evalTuple2 -- :: Strategy a -> ... -> Strategy (a,...)+ , evalTuple3+ , evalTuple4+ , evalTuple5+ , evalTuple6+ , evalTuple7+ , evalTuple8+ , evalTuple9+++ -- | Evaluate the components of a tuple in parallel according to+ -- the given strategies.++ , parTuple2 -- :: Strategy a -> ... -> Strategy (a,...)+ , parTuple3+ , parTuple4+ , parTuple5+ , parTuple6+ , parTuple7+ , parTuple8+ , parTuple9++ -- * Strategic function application+ , ($|) -- :: (a -> b) -> Strategy a -> a -> b+ , ($||)+ , (.|) -- :: (b -> c) -> Strategy b -> (a -> b) -> a -> c+ , (.||)+ , (-|) -- :: (a -> b) -> Strategy b -> (b -> c) -> a -> c+ , (-||)++ -- * For Strategy programmers+ , Eval -- instances: Monad, Functor, Applicative+ , parEval -- :: Eval a -> Eval a+ , runEval -- :: Eval a -> a+ , runEvalIO -- :: Eval a -> IO a+ ,++ -- * API History++ -- $history++ -- * Backwards compatibility++ -- | These functions and types are all deprecated, and will be+ -- removed in a future release. In all cases they have been+ -- either renamed or replaced with equivalent functionality.++ Done, demanding, sparking, (>|), (>||),+ rwhnf, unEval,+ seqTraverse, parTraverse,+ seqList,+ seqPair, parPair,+ seqTriple, parTriple,++ -- * For API completeness++ -- | So that users of 'rdeepseq' aren't required to import @Control.DeepSeq@:+ NFData+ ) where++#if defined(__MHS__) || !MIN_VERSION_base(4,8,0)+import Data.Traversable+#endif+#if !MIN_VERSION_base(4,8,0)+import Control.Applicative+#endif+import Control.Parallel+import Control.DeepSeq (NFData(rnf))+import Control.Monad.Fix (MonadFix (..))++#if defined(__GLASGOW_HASKELL__) && MIN_VERSION_base(4,4,0)+import System.IO.Unsafe (unsafeDupablePerformIO)+import Control.Exception (evaluate)+#else+import System.IO.Unsafe (unsafePerformIO)+import Control.Monad+#endif++import qualified Control.Seq++#ifdef __GLASGOW_HASKELL__+import GHC.Exts+import GHC.IO (IO (..))+#endif++infixr 9 `dot` -- same as (.)+infixl 0 `using` -- lowest precedence and associate to the left+infixl 0 `usingIO` -- lowest precedence and associate to the left++-- -----------------------------------------------------------------------------+-- Eval monad (isomorphic to Lift monad from MonadLib 3.6.1)++-- | 'Eval' is a monad that makes it easier to define parallel+-- strategies. It is a strict identity monad, that is, in+--+-- > m >>= f+--+-- @m@ is evaluated before the result is passed to @f@.+--+-- > instance Monad Eval where+-- > return = Done+-- > m >>= k = case m of+-- > Done x -> k x+--+-- If you wanted to construct a 'Strategy' for a pair that sparked the+-- first component in parallel and then evaluated the second+-- component, you could write+--+-- > myStrat :: Strategy (a,b)+-- > myStrat (a,b) = do { a' <- rpar a; b' <- rseq b; return (a',b') }+--+-- Alternatively, you could write this more compactly using the+-- Applicative style as+--+-- > myStrat (a,b) = (,) <$> rpar a <*> rseq b+--+-- More examples, using the Applicative instance:+--+-- > parList :: Strategy a -> Strategy [a]+-- > parList strat = traverse (rpar `dot` strat))+--+-- > evalPair :: Strategy a -> Strategy b -> Strategy (a,b)+-- > evalPair f g (a,b) = pure (,) <$> f a <*> g b+--++#if __GLASGOW_HASKELL__ >= 702++newtype Eval a = Eval {unEval_ :: IO a}+ deriving (Functor, Applicative, Monad)+ -- GHC 7.2.1 added the seq# and spark# primitives, that we use in+ -- the Eval monad implementation in order to get the correct+ -- strictness behaviour.++-- | Run the evaluation.+runEval :: Eval a -> a+# if MIN_VERSION_base(4,4,0)+runEval = unsafeDupablePerformIO . unEval_+# else+runEval = unsafePerformIO . unEval_+# endif++-- | Run the evaluation in the 'IO' monad. This allows sequencing of+-- evaluations relative to 'IO' actions.+runEvalIO :: Eval a -> IO a+runEvalIO = unEval_++-- We don't use GND to derive MonadFix from the IO instance. The IO instance+-- has to be very careful to ensure that lazy blackholing doesn't cause IO+-- actions to be duplicated in case of an infinite loop. This has a small+-- performance cost. Eval computations are always assumed to be pure, so+-- duplicating them is okay. What about ST computations embedded in Eval ones?+-- Those also shouldn't be a problem: the ST computations are "closed", so it's+-- safe to duplicate them, and the RTS already takes care to avoid resuming+-- a computation paused by an asynchronous exception in multiple threads.+-- Lazy ST takes care of itself with noDuplicate#, so we don't really need+-- to think about it too much.+--+-- Note:+-- mfix f = let res = runEval (Lift <$> f (unLift res))+-- in case res of Lift r -> return r+-- data Lift a = Lift a+instance MonadFix Eval where+ -- Borrowed from the instance for ST+ mfix k = Eval $ IO $ \ s ->+ let ans = liftEv (k r) s+ Evret _ r = ans+ in+ case ans of Evret s' x -> (# s', x #)++data Evret a = Evret (State# RealWorld) a++-- liftEv is useful when we want a lifted result from an Eval computation. It+-- is used to implement mfix.+liftEv :: Eval a -> State# RealWorld -> Evret a+liftEv (Eval (IO m)) = \s -> case m s of (# s', r #) -> Evret s' r++#else++data Eval a = Done a++-- | Pull the result out of the monad.+runEval :: Eval a -> a+runEval (Done x) = x++-- | Run the evaluation in the 'IO' monad. This allows sequencing of+-- evaluations relative to 'IO' actions.+runEvalIO :: Eval a -> IO a+runEvalIO (Done x) = return x++instance Functor Eval where+ fmap = liftM++instance Applicative Eval where+ pure = Done+ (<*>) = ap++instance Monad Eval where+ return = pure+# ifdef __GLASGOW_HASKELL__+ Done x >>= k = lazy (k x) -- Note: pattern 'Done x' makes '>>=' strict+# else+ Done x >>= k = k x+# endif++instance MonadFix Eval where+ mfix f = let r = f (runEval r) in r++{-# RULES "lazy Done" forall x . lazy (Done x) = Done x #-}++-- The Eval monad satisfies the monad laws.+--+-- (1) Left identity:+-- return x >>= f ==> Done x >>= f ==> f x+--+-- (2) Right identity:+-- (i) m >>= return =*> Done u >>= return+-- ==> return u+-- ==> Done u <*= m+-- (ii) m >>= return =*> undefined >>= return+-- ==> undefined <*= m+--+-- (3) Associativity:+-- (i) (m >>= f) >>= g =*> (Done u >>= f) >>= g+-- ==> f u >>= g <== (\x -> f x >>= g) u+-- <== Done u >>= (\x -> f x >>= g)+-- <*= m >>= (\x -> f x >>= g)+-- (ii) (m >>= f) >>= g =*> (undefined >>= f) >>= g+-- ==> undefined >>= g+-- ==> undefined <== undefined >>= (\x -> f x >>= g)+-- <*= m >>= (\x -> f x >>= g)++#endif+++-- -----------------------------------------------------------------------------+-- 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++-- | Evaluate a value using the given 'Strategy'.+--+-- > x `using` s = runEval (s x)+--+using :: a -> Strategy a -> a+x `using` strat = runEval (strat x)++-- | Evaluate a value using the given 'Strategy'. This is simply+-- 'using' with the arguments reversed.+--+withStrategy :: Strategy a -> a -> a+withStrategy = flip using++-- | Evaluate a value using the given 'Strategy' inside the 'IO' monad. See+-- also 'runEvalIO'.+--+-- > x `usingIO` s = runEvalIO (s x)+--+usingIO :: a -> Strategy a -> IO a+x `usingIO` strat = runEvalIO (strat x)++-- | Evaluate a value using the given 'Strategy' inside the 'IO' monad. This+-- is simply 'usingIO' with the arguments reversed.+--+withStrategyIO :: Strategy a -> a -> IO a+withStrategyIO = flip usingIO++-- | Compose two strategies.+--+-- > strat2 `dot` strat1 == strat2 . withStrategy strat1+--+-- 'dot' is associative:+--+-- > (strat1 `dot` strat2) `dot` strat3 == strat1 `dot` (strat2 `dot` strat3)+--+-- 'r0' and 'rseq' are one-sided identities of 'dot':+--+-- > strat `dot` r0 == strat+-- > strat `dot` rseq == strat+{-# DEPRECATED dot "'dot' is an unintuitive composition operator. Use 'Control.Monad.<=<` instead." #-}+dot :: Strategy a -> Strategy a -> Strategy a+strat2 `dot` strat1 = strat2 . runEval . strat1++-- Note [dot proofs]+-- ~~~~~~~~~~~~~~~~~+-- Proof of strat2 `dot` strat1 == strat2 . withStrategy strat1+--+-- strat2 . withStrategy strat1+-- == \x -> strat2 (withStrategy strat1 x)+-- == \x -> strat2 (x `using` strat1)+-- == \x -> strat2 (runEval (strat1 x))+-- == \x -> (strat2 . runEval . strat1) x+-- == strat2 `dot` strat1+--+-- Proof of associativity+--+-- (strat1 `dot` strat2) `dot` strat3+-- == (strat1 . runEval . strat2) . runEval . strat3+-- == strat1 . runEval . strat2 . runEval . strat3+-- == strat1 . runEval . (strat2 . runEval . strat3)+-- == strat1 `dot` (strat2 `dot` strat3)++-- | Inject a sequential strategy (i.e., coerce a sequential strategy+-- to a general strategy).+--+-- Thanks to 'evalSeq', the type @'SeqStrategy' a@ is a subtype+-- of @'Strategy' a@.+evalSeq :: SeqStrategy a -> Strategy a+evalSeq strat x = strat x `pseq` return x++-- | A name for @Control.Seq.Strategy@, for documentation only.+type SeqStrategy a = Control.Seq.Strategy a++-- --------------------------------------------------------------------------+-- Basic strategies (some imported from SeqStrategies)++-- | 'r0' performs /no/ evaluation.+--+-- > r0 == evalSeq Control.Seq.r0+--+r0 :: Strategy a+r0 x = return x++-- Proof of r0 == evalSeq Control.Seq.r0+--+-- evalSeq Control.Seq.r0+-- == \x -> Control.Seq.r0 x `pseq` return x+-- == \x -> Control.Seq.Done `pseq` return x+-- == \x -> return x+-- == r0++-- | 'rseq' evaluates its argument to weak head normal form.+--+-- > rseq == evalSeq Control.Seq.rseq+--+rseq :: Strategy a+#if __GLASGOW_HASKELL__ >= 702+rseq x = Eval (evaluate x)+#else+rseq x = x `seq` return x+#endif+-- Staged NOINLINE so we can match on rseq in RULES+{-# NOINLINE [1] rseq #-}+++-- Proof of rseq == evalSeq Control.Seq.rseq+--+-- evalSeq Control.Seq.rseq+-- == \x -> Control.Seq.rseq x `pseq` return x+-- == \x -> (x `seq` Control.Seq.Done) `pseq` return x+-- == \x -> x `pseq` return x+-- == rseq++-- | 'rdeepseq' fully evaluates its argument.+--+-- > rdeepseq == evalSeq Control.Seq.rdeepseq+--+rdeepseq :: NFData a => Strategy a+rdeepseq x = do rseq (rnf x); return x++-- Proof of rdeepseq == evalSeq Control.Seq.rdeepseq+--+-- evalSeq Control.Seq.rdeepseq+-- == \x -> Control.Seq.rdeepseq x `pseq` return x+-- == \x -> (x `deepseq` Control.Seq.Done) `pseq` return x+-- == \x -> (rnf x `seq` Control.Seq.Done) `pseq` return x+-- == \x -> rnf x `pseq` return x+-- == rdeepseq++-- | 'rpar' sparks its argument (for evaluation in parallel).+rpar :: Strategy a+#ifdef __GLASGOW_HASKELL__+#if __GLASGOW_HASKELL__ >= 702+rpar x = Eval $ IO $ \s -> spark# x s+#else+rpar x = case (par# x) of _ -> Done x+#endif+#else+rpar x = case par x () of () -> Done x+#endif+{-# INLINE rpar #-}++-- | Perform a computation in parallel using a strategy.+--+-- @+-- rparWith strat x+-- @+--+-- will spark @strat x@. Note that @rparWith strat@ is /not/ the+-- same as @rpar ``dot`` strat@. Specifically, @rpar ``dot`` strat@+-- always sparks a computation to reduce the result of the+-- strategic computation to WHNF, while @rparWith strat@ need+-- not.+--+-- > rparWith r0 = r0+-- > rparWith rpar = rpar+-- > rparWith rseq = rpar+--+-- @rparWith rpar x@ creates a spark that immediately creates another+-- spark to evaluate @x@. We consider this equivalent to @rpar@ because+-- there isn't any real additional parallelism. However, it is always+-- less efficient because there's a bit of extra work to create the+-- first (useless) spark. Similarly, @rparWith r0@ creates a spark+-- that does precisely nothing. No real parallelism is added, but there+-- is a bit of extra work to do nothing.+rparWith :: Strategy a -> Strategy a+rparWith strat = parEval . strat++-- | 'parEval' sparks the computation of its argument for evaluation in+-- parallel. Unlike @'rpar' . 'runEval'@, 'parEval'+--+-- * does not exit the `Eval` monad+--+-- * does not have a built-in `rseq`, so for example @'parEval' ('r0' x)@+-- behaves as you might expect (it creates a spark that does no+-- evaluation).+--+-- It is related to 'rparWith' by the following equality:+--+-- > parEval . strat = rparWith strat+--+parEval :: Eval a -> Eval a+-- The intermediate `Lift` box is necessary, in order to avoid a built-in+-- `rseq` in `parEval`. In particular, we want @parEval . r0 = r0@, not+-- @parEval . r0 = rpar@.+parEval m = do+ l <- rpar r+ return (case l of Lift x -> x)++ where+ r = runEval (Lift <$> m)++data Lift a = Lift a++-- --------------------------------------------------------------------------+-- Strategy combinators for Traversable data types++-- | Evaluate the elements of a traversable data structure+-- according to the given strategy.+evalTraversable :: Traversable t => Strategy a -> Strategy (t a)+evalTraversable = traverse+{-# INLINE evalTraversable #-}++-- | Like 'evalTraversable', but evaluates all elements in parallel.+parTraversable :: Traversable t => Strategy a -> Strategy (t a)+parTraversable strat = evalTraversable (rparWith strat)+{-# INLINE parTraversable #-}++-- --------------------------------------------------------------------------+-- Strategies for lists++-- | Evaluate each element of a list according to the given strategy.+-- Equivalent to 'evalTraversable' at the list type.+--+-- __Warning:__ This strategy evaluates the spine of the list+-- and thus does not work on infinite lists.+evalList :: Strategy a -> Strategy [a]+evalList = evalTraversable+-- Alternative explicitly recursive definition:+-- evalList strat [] = return []+-- evalList strat (x:xs) = strat x >>= \x' ->+-- evalList strat xs >>= \xs' ->+-- return (x':xs')++-- | Evaluate each element of a list in parallel according to given strategy.+-- Equivalent to 'parTraversable' at the list type.+--+-- __Warning:__ This strategy evaluates the spine of the list+-- and thus does not work on infinite lists.+parList :: Strategy a -> Strategy [a]+parList = parTraversable+-- Alternative definition via evalList:+-- parList strat = evalList (rparWith strat)++-- | @'evaListSplitAt' n stratPref stratSuff@ evaluates the prefix+-- (of length @n@) of a list according to @stratPref@ and the suffix+-- according to @stratSuff@.+evalListSplitAt :: Int -> Strategy [a] -> Strategy [a] -> Strategy [a]+evalListSplitAt n stratPref stratSuff xs+ = let (ys,zs) = splitAt n xs in+ stratPref ys >>= \ys' ->+ stratSuff zs >>= \zs' ->+ return (ys' ++ zs')++-- | Like 'evalListSplitAt', but evaluates both sublists in parallel.+parListSplitAt :: Int -> Strategy [a] -> Strategy [a] -> Strategy [a]+parListSplitAt n stratPref stratSuff = evalListSplitAt n (rparWith stratPref) (rparWith stratSuff)++-- | Evaluate the first n elements of a list according to the given strategy.+evalListN :: Int -> Strategy a -> Strategy [a]+evalListN n strat = evalListSplitAt n (evalList strat) r0++-- | Like 'evalListN', but evaluates the first n elements in parallel.+parListN :: Int -> Strategy a -> Strategy [a]+parListN n strat = evalListN n (rparWith strat)++-- | Evaluate the nth element of a list (if there is such) according to+-- the given strategy.+-- This nth is 0-based. For example, @[1, 2, 3, 4, 5] ``using`` evalListNth 4 rseq@+-- will eval @5@, not @4@.+-- The spine of the list up to the nth element is evaluated as a side effect.+evalListNth :: Int -> Strategy a -> Strategy [a]+evalListNth n strat = evalListSplitAt n r0 (evalListN 1 strat)++-- | Like 'evalListNth', but evaluates the nth element in parallel.+parListNth :: Int -> Strategy a -> Strategy [a]+parListNth n strat = evalListNth n (rparWith strat)++-- | Divides a list into chunks, and applies the strategy+-- @'evalList' strat@ to each chunk in parallel.+--+-- If the chunk size is 1 or less, 'parListChunk' is equivalent to+-- 'parList'+--+-- This function may be replaced by a more+-- generic clustering infrastructure in the future.+--+-- __Warning:__ This strategy evaluates the spine of the list+-- and thus does not work on infinite lists.+parListChunk :: Int -> Strategy a -> Strategy [a]+parListChunk n strat+ | n <= 1 = parList strat+ | otherwise = go+ where+ go [] = pure []+ go as = mdo+ -- Calculate the first chunk in parallel, passing it the result+ -- of calculating the rest+ bs <- rpar $ runEval $ evalChunk strat more n as++ -- Calculate the rest+ more <- go (drop n as)+ return bs++-- | @evalChunk strat end n as@ uses @strat@ to evaluate the first @n@+-- elements of @as@ (ignoring the rest) and appends @end@ to the result.+evalChunk :: Strategy a -> [a] -> Int -> Strategy [a]+evalChunk strat = \end ->+ let+ go !_n [] = pure end+ go 0 _ = pure end+ go n (a:as) = (:) <$> strat a <*> go (n - 1) as+ in go++-- --------------------------------------------------------------------------+-- Convenience++-- | A combination of 'parList' and 'map', encapsulating a common pattern:+--+-- > parMap strat f = withStrategy (parList strat) . map f+--+-- __Warning:__ This function evaluates the spine of the list+-- and thus does not work on infinite lists.+parMap :: Strategy b -> (a -> b) -> [a] -> [b]+parMap strat f = (`using` parList strat) . map f+++-- | A generalisation of 'parMap' using 'parTraversable' and `fmap`:+--+-- > parFmap strat g = withStrategy (parTraversable strat) . fmap f+--+parFmap :: Traversable t => Strategy b -> (a -> b) -> t a -> t b+parFmap strat f = (`using` parTraversable strat) . fmap f++-- --------------------------------------------------------------------------+-- Strategies for lazy lists++-- | 'evalBuffer' is a rolling buffer strategy combinator for lazy lists.+-- Pattern matching on the result of @evalBuffer n strat xs@ will evaluate the+-- first @n+1@ elements of @xs@ using @strat@. Pattern matching on each+-- additional list cons will evaluate an additional element using @strat@.+evalBuffer :: Int -> Strategy a -> Strategy [a]+evalBuffer n0 strat xs0 = return (ret tied (drop n0 tied))+ where+ -- This is the heart of the strategy. The idea is to tie the evaluation+ -- of each cons (to WHNF) to the evaluation of its contents (according+ -- to strat). Walking the spine of the result will thus perform+ -- the requested Eval actions.+ tied = foldr go [] xs0+ where+ go x r = runEval ((: r) <$> strat x)++ ret (x : xs) (_y : ys) = x : ret xs ys+ ret xs _ = xs++-- | 'parBuffer' is a rolling buffer strategy combinator for lazy lists.+-- Pattern matching on the result of @parBuffer n s xs@ sparks+-- computations to evaluate the first @n+1@ elements of @xs@ using the+-- strategy @s@. Pattern matching on each additional list cons will+-- spark an additional computation.+--+-- @parBuffer n strat = 'evalBuffer' n ('rparWith' strat)@+parBuffer :: Int -> Strategy a -> Strategy [a]+parBuffer n strat = evalBuffer n (rparWith strat)++-- --------------------------------------------------------------------------+-- Strategies for tuples++evalTuple2 :: Strategy a -> Strategy b -> Strategy (a,b)+evalTuple2 strat1 strat2 (x1,x2) =+ pure (,) <*> strat1 x1 <*> strat2 x2++evalTuple3 :: Strategy a -> Strategy b -> Strategy c -> Strategy (a,b,c)+evalTuple3 strat1 strat2 strat3 (x1,x2,x3) =+ pure (,,) <*> strat1 x1 <*> strat2 x2 <*> strat3 x3++evalTuple4 :: Strategy a -> Strategy b -> Strategy c -> Strategy d -> Strategy (a,b,c,d)+evalTuple4 strat1 strat2 strat3 strat4 (x1,x2,x3,x4) =+ pure (,,,) <*> strat1 x1 <*> strat2 x2 <*> strat3 x3 <*> strat4 x4++evalTuple5 :: Strategy a -> Strategy b -> Strategy c -> Strategy d -> Strategy e -> Strategy (a,b,c,d,e)+evalTuple5 strat1 strat2 strat3 strat4 strat5 (x1,x2,x3,x4,x5) =+ pure (,,,,) <*> strat1 x1 <*> strat2 x2 <*> strat3 x3 <*> strat4 x4 <*> strat5 x5++evalTuple6 :: Strategy a -> Strategy b -> Strategy c -> Strategy d -> Strategy e -> Strategy f -> Strategy (a,b,c,d,e,f)+evalTuple6 strat1 strat2 strat3 strat4 strat5 strat6 (x1,x2,x3,x4,x5,x6) =+ pure (,,,,,) <*> strat1 x1 <*> strat2 x2 <*> strat3 x3 <*> strat4 x4 <*> strat5 x5 <*> strat6 x6++evalTuple7 :: Strategy a -> Strategy b -> Strategy c -> Strategy d -> Strategy e -> Strategy f -> Strategy g -> Strategy (a,b,c,d,e,f,g)+evalTuple7 strat1 strat2 strat3 strat4 strat5 strat6 strat7 (x1,x2,x3,x4,x5,x6,x7) =+ pure (,,,,,,) <*> strat1 x1 <*> strat2 x2 <*> strat3 x3 <*> strat4 x4 <*> strat5 x5 <*> strat6 x6 <*> strat7 x7++evalTuple8 :: Strategy a -> Strategy b -> Strategy c -> Strategy d -> Strategy e -> Strategy f -> Strategy g -> Strategy h -> Strategy (a,b,c,d,e,f,g,h)+evalTuple8 strat1 strat2 strat3 strat4 strat5 strat6 strat7 strat8 (x1,x2,x3,x4,x5,x6,x7,x8) =+ pure (,,,,,,,) <*> strat1 x1 <*> strat2 x2 <*> strat3 x3 <*> strat4 x4 <*> strat5 x5 <*> strat6 x6 <*> strat7 x7 <*> strat8 x8++evalTuple9 :: Strategy a -> Strategy b -> Strategy c -> Strategy d -> Strategy e -> Strategy f -> Strategy g -> Strategy h -> Strategy i -> Strategy (a,b,c,d,e,f,g,h,i)+evalTuple9 strat1 strat2 strat3 strat4 strat5 strat6 strat7 strat8 strat9 (x1,x2,x3,x4,x5,x6,x7,x8,x9) =+ pure (,,,,,,,,) <*> strat1 x1 <*> strat2 x2 <*> strat3 x3 <*> strat4 x4 <*> strat5 x5 <*> strat6 x6 <*> strat7 x7 <*> strat8 x8 <*> strat9 x9++parTuple2 :: Strategy a -> Strategy b -> Strategy (a,b)+parTuple2 strat1 strat2 =+ evalTuple2 (rparWith strat1) (rparWith strat2)++parTuple3 :: Strategy a -> Strategy b -> Strategy c -> Strategy (a,b,c)+parTuple3 strat1 strat2 strat3 =+ evalTuple3 (rparWith strat1) (rparWith strat2) (rparWith strat3)++parTuple4 :: Strategy a -> Strategy b -> Strategy c -> Strategy d -> Strategy (a,b,c,d)+parTuple4 strat1 strat2 strat3 strat4 =+ evalTuple4 (rparWith strat1) (rparWith strat2) (rparWith strat3) (rparWith strat4)++parTuple5 :: Strategy a -> Strategy b -> Strategy c -> Strategy d -> Strategy e -> Strategy (a,b,c,d,e)+parTuple5 strat1 strat2 strat3 strat4 strat5 =+ evalTuple5 (rparWith strat1) (rparWith strat2) (rparWith strat3) (rparWith strat4) (rparWith strat5)++parTuple6 :: Strategy a -> Strategy b -> Strategy c -> Strategy d -> Strategy e -> Strategy f -> Strategy (a,b,c,d,e,f)+parTuple6 strat1 strat2 strat3 strat4 strat5 strat6 =+ evalTuple6 (rparWith strat1) (rparWith strat2) (rparWith strat3) (rparWith strat4) (rparWith strat5) (rparWith strat6)++parTuple7 :: Strategy a -> Strategy b -> Strategy c -> Strategy d -> Strategy e -> Strategy f -> Strategy g -> Strategy (a,b,c,d,e,f,g)+parTuple7 strat1 strat2 strat3 strat4 strat5 strat6 strat7 =+ evalTuple7 (rparWith strat1) (rparWith strat2) (rparWith strat3) (rparWith strat4) (rparWith strat5) (rparWith strat6) (rparWith strat7)++parTuple8 :: Strategy a -> Strategy b -> Strategy c -> Strategy d -> Strategy e -> Strategy f -> Strategy g -> Strategy h -> Strategy (a,b,c,d,e,f,g,h)+parTuple8 strat1 strat2 strat3 strat4 strat5 strat6 strat7 strat8 =+ evalTuple8 (rparWith strat1) (rparWith strat2) (rparWith strat3) (rparWith strat4) (rparWith strat5) (rparWith strat6) (rparWith strat7) (rparWith strat8)++parTuple9 :: Strategy a -> Strategy b -> Strategy c -> Strategy d -> Strategy e -> Strategy f -> Strategy g -> Strategy h -> Strategy i -> Strategy (a,b,c,d,e,f,g,h,i)+parTuple9 strat1 strat2 strat3 strat4 strat5 strat6 strat7 strat8 strat9 =+ evalTuple9 (rparWith strat1) (rparWith strat2) (rparWith strat3) (rparWith strat4) (rparWith strat5) (rparWith strat6) (rparWith strat7) (rparWith strat8) (rparWith strat9)++-- --------------------------------------------------------------------------+-- Strategic function application++{-+These are very handy when writing pipeline parallelism as a sequence of+@$@, @$|@ and @$||@'s. There is no need of naming intermediate values+in this case. The separation of algorithm from strategy is achieved by+allowing strategies only as second arguments to @$|@ and @$||@.+-}++-- | Sequential function application. The argument is evaluated using+-- the given strategy before it is given to the function.+($|) :: (a -> b) -> Strategy a -> a -> b+f $| s = \x -> runEval (f <$> s x)++-- | Parallel function application. The argument is evaluated using+-- the given strategy, in parallel with the function application.+($||) :: (a -> b) -> Strategy a -> a -> b+f $|| s = \x -> runEval (f <$> rparWith s x)++-- | Sequential function composition. The result of+-- the second function is evaluated using the given strategy,+-- and then given to the first function.+(.|) :: (b -> c) -> Strategy b -> (a -> b) -> (a -> c)+(.|) f s g = \x -> runEval (f <$> s (g x))++-- | Parallel function composition. The result of the second+-- function is evaluated using the given strategy,+-- in parallel with the application of the first function.+(.||) :: (b -> c) -> Strategy b -> (a -> b) -> (a -> c)+(.||) f s g = \x -> runEval (f <$> rparWith s (g x))++-- | Sequential inverse function composition,+-- for those who read their programs from left to right.+-- The result of the first function is evaluated using the+-- given strategy, and then given to the second function.+(-|) :: (a -> b) -> Strategy b -> (b -> c) -> (a -> c)+(-|) f s g = \x -> runEval (g <$> s (f x))++-- | Parallel inverse function composition,+-- for those who read their programs from left to right.+-- The result of the first function is evaluated using the+-- given strategy, in parallel with the application of the+-- second function.+(-||) :: (a -> b) -> Strategy b -> (b -> c) -> (a -> c)+(-||) f s g = \x -> runEval (g <$> rparWith s (f x))++-- -----------------------------------------------------------------------------+-- Old/deprecated stuff++{-# DEPRECATED Done "The Strategy type is now a -> Eval a, not a -> Done" #-}+type Done = ()++{-# DEPRECATED demanding "Use 'pseq' or '$|' instead" #-}+demanding :: a -> Done -> a+demanding = flip pseq++{-# DEPRECATED sparking "Use 'par' or '$||' instead" #-}+sparking :: a -> Done -> a+sparking = flip par++{-# DEPRECATED (>|) "Use 'pseq' or '$|' instead" #-}+(>|) :: Done -> Done -> Done+(>|) = Prelude.seq++{-# DEPRECATED (>||) "Use 'par' or '$||' instead" #-}+(>||) :: Done -> Done -> Done+(>||) = par++{-# DEPRECATED rwhnf "renamed to 'rseq'" #-}+rwhnf :: Strategy a+rwhnf = rseq++{-# DEPRECATED seqTraverse "renamed to 'evalTraversable'" #-}+seqTraverse :: Traversable t => Strategy a -> Strategy (t a)+seqTraverse = evalTraversable++{-# DEPRECATED parTraverse "renamed to 'parTraversable'" #-}+parTraverse :: Traversable t => Strategy a -> Strategy (t a)+parTraverse = parTraversable++{-# DEPRECATED seqList "renamed to 'evalList'" #-}+seqList :: Strategy a -> Strategy [a]+seqList = evalList++{-# DEPRECATED seqPair "renamed to 'evalTuple2'" #-}+seqPair :: Strategy a -> Strategy b -> Strategy (a,b)+seqPair = evalTuple2++{-# DEPRECATED parPair "renamed to 'parTuple2'" #-}+parPair :: Strategy a -> Strategy b -> Strategy (a,b)+parPair = parTuple2++{-# DEPRECATED seqTriple "renamed to 'evalTuple3'" #-}+seqTriple :: Strategy a -> Strategy b -> Strategy c -> Strategy (a,b,c)+seqTriple = evalTuple3++{-# DEPRECATED parTriple "renamed to 'parTuple3'" #-}+parTriple :: Strategy a -> Strategy b -> Strategy c -> Strategy (a,b,c)+parTriple = parTuple3++{-# DEPRECATED unEval "renamed to 'runEval'" #-}+unEval :: Eval a -> a+unEval = runEval++{- $history #history#++The strategies library has a long history. What follows is a+summary of how the current design evolved, and is mostly of+interest to those who are familiar with an older version, or need+to adapt old code to use the newer API.++=== Version 1.x++ The original Strategies design is described in [/Algorithm + Strategy = Parallelism/](https://www.macs.hw.ac.uk/~dsg/gph/papers/html/Strategies/strategies.html)+ and the code was written by+ Phil Trinder, Hans-Wolfgang Loidl, Kevin Hammond et al.++=== Version 2.x++Later, during work on the shared-memory implementation of+parallelism in GHC, we discovered that the original formulation of+Strategies had some problems, in particular it lead to space leaks+and difficulties expressing speculative parallelism. Details are in+the paper [/Runtime Support for Multicore Haskell/](https://www.microsoft.com/en-us/research/wp-content/uploads/2009/09/multicore-ghc.pdf).++This module has been rewritten in version 2. The main change is to+the @'Strategy' a@ type synonym, which was previously @a -> Done@ and+is now @a -> Eval a@. This change helps to fix the space leak described+in \"Runtime Support for Multicore Haskell\". The problem is that+the runtime will currently retain the memory referenced by all+sparks, until they are evaluated. Hence, we must arrange to+evaluate all the sparks eventually, just in case they aren't+evaluated in parallel, so that they don't cause a space leak. This+is why we must return a \"new\" value after applying a 'Strategy',+so that the application can evaluate each spark created by the+'Strategy'.++The simple rule is this: you /must/ use the result of applying+a 'Strategy' if the strategy creates parallel sparks, and you+should probably discard the original value. If you don't+do this, currently it may result in a space leak. In the+future (GHC 6.14), it will probably result in lost parallelism+instead, as we plan to change GHC so that unreferenced sparks+are discarded rather than retained (we can't make this change+until most code is switched over to this new version of+Strategies, because code using the old verison of Strategies+would be broken by the change in policy).++The other changes in version 2.x are:++ * Strategies can now be defined using a convenient Monad/Applicative+ type, 'Eval'. e.g. @parList s = traverse (rpar . (``using`` s))@++ * 'parList' has been generalised to 'parTraverse', which works on+ any 'Traversable' type, and similarly 'seqList' has been generalised+ to 'seqTraverse'++ * 'parList' and 'parBuffer' have versions specialised to 'rwhnf',+ and there are transformation rules that automatically translate+ e.g. @parList rwnhf@ into a call to the optimised version.++ * 'NFData' has been moved to @Control.DeepSeq@ in the @deepseq@+ package. Note that since the 'Strategy' type changed, 'rnf'+ is no longer a 'Strategy': use 'rdeepseq' instead.++Version 2.1 moved 'NFData' into a separate package, @deepseq@.++Version 2.2 changed the type of Strategy to @a -> Eval a@, and+re-introduced the @r0@ strategy which was missing in version 2.1.++Version 2.3 simplified the @Eval@ type, so that @Eval@ is now just+the strict identity monad. This change and various other+improvements and refactorings are thanks to Patrick Maier who+noticed that @Eval@ didn't satisfy the monad laws, and that a+simpler version would fix that problem.++(Version 2.3 was not released on Hackage.)++=== Version 3.x++Version 3 introduced a major overhaul of the API, to match what is+presented in the paper++ [/Seq no More: Better Strategies for Parallel Haskell/]+ (https://simonmar.github.io/bib/papers/strategies.pdf)++The major differences in the API are:++ * The addition of sequential strategies ("Control.Seq") as+ a composable means for specifying sequential evaluation.++ * Changes to the naming scheme: 'rwhnf' renamed to 'rseq',+ 'seqList' renamed to 'evalList', 'seqPair' renamed to+ 'evalTuple2'.++The naming scheme is now as follows:++ * Basic polymorphic strategies (of type @'Strategy' a@) are called @r...@.+ Examples: 'r0', 'rseq', 'rpar', 'rdeepseq'.++ * A strategy combinator for a particular type constructor+ or constructor class @T@ is called @evalT...@, @parT...@ or @seqT...@.++ * The @seqT...@ combinators (residing in module+ "Control.Seq") yield sequential strategies.+ Thus, @seqT...@ combinators cannot spark, nor can the sequential+ strategies to which they may be applied.+ Examples: 'seqTuple2', 'seqListN', 'seqFoldable'.++ * The @evalT...@ combinators do not spark themselves, yet they may+ be applied to strategies that do spark. (They may also be applied+ to non-sparking strategies; however, in that case the corresponding+ @seqT...@ combinator might be a better choice.)+ Examples: 'evalTuple2', 'evalListN', 'evalTraversable'.++ * The @parT...@ combinators, which are derived from their @evalT...@+ counterparts, do spark. They may be applied to all strategies,+ whether sparking or not.+ Examples: 'parTuple2', 'parListN', 'parTraversable'.++ * An exception to the type driven naming scheme are 'evalBuffer' and+ 'parBuffer', which are not named after their type constructor (lists)+ but after their function (rolling buffer of fixed size).+-}
+ Control/Seq.hs view
@@ -0,0 +1,204 @@+{-# LANGUAGE BangPatterns #-}+{-# LANGUAGE CPP #-}++-----------------------------------------------------------------------------+-- |+-- Module : Control.Parallel.SeqStrategies+-- Copyright : (c) The University of Glasgow 2001-2009+-- License : BSD-style (see the file libraries/base/LICENSE)+--+-- Maintainer : libraries@haskell.org+-- Stability : experimental+-- Portability : portable+--+-- Sequential strategies provide ways to compositionally specify+-- the degree of evaluation of a data type between the extremes of+-- no evaluation and full evaluation.+-- Sequential strategies may be viewed as complementary to the parallel+-- ones (see module "Control.Parallel.Strategies").+--++module Control.Seq+ (+ -- * The sequential strategy type+ Strategy++ -- * Application of sequential strategies+ , using -- :: a -> Strategy a -> a+ , withStrategy -- :: Strategy a -> a -> a++ -- * Basic sequential strategies+ , r0 -- :: Strategy a+ , rseq+ , rdeepseq -- :: NFData a => Strategy a++ -- * Sequential strategies for lists+ , seqList -- :: Strategy a -> Strategy [a]+ , seqListN -- :: Int -> Strategy a -> Strategy [a]+ , seqListNth++ -- * Sequential strategies for foldable data types+ , seqFoldable -- :: Foldable t => Strategy a -> Strategy (t a)+ , seqMap -- :: Strategy k -> Strategy v -> Strategy (Map k v)+ , seqArray -- :: Ix i => Strategy a -> Strategy (Array i a)+ , seqArrayBounds -- :: Ix i => Strategy i -> Strategy (Array i a)++ -- * Sequential strategies for tuples++ -- | Evaluate the components of a tuple according to the given strategies.+ -- No guarantee is given as to the order of evaluation.++ , seqTuple2 -- :: Strategy a -> ... -> Strategy (a,...)+ , seqTuple3+ , seqTuple4+ , seqTuple5+ , seqTuple6+ , seqTuple7+ , seqTuple8+ , seqTuple9+ ) where++import Control.DeepSeq (NFData, deepseq)+#if defined(__GLASGOW_HASKELL__) && MIN_VERSION_base(4,8,0)+import Data.Foldable (toList)+#else+import Data.Foldable (Foldable, toList)+#endif+import Data.Map (Map)+import qualified Data.Map (toList)+#if !((__GLASGOW_HASKELL__ >= 711) && MIN_VERSION_array(0,5,1))+import Data.Ix (Ix)+#endif+import Data.Array (Array)+import qualified Data.Array (bounds, elems)++infixl 0 `using` -- lowest precedence and associate to the left++-- --------------------------------------------------------------------------+-- Sequential strategies++-- | The type @'Strategy' a@ is @a -> ()@.+-- Thus, a strategy is a function whose sole purpose it is to evaluate+-- its argument (either in full or in part).+type Strategy a = a -> ()++-- | Evaluate a value using the given strategy.+using :: a -> Strategy a -> a+x `using` strat = strat x `seq` x++-- | Evaluate a value using the given strategy.+-- This is simply 'using' with arguments reversed.+withStrategy :: Strategy a -> a -> a+withStrategy = flip using++-- --------------------------------------------------------------------------+-- Basic sequential strategies++-- | 'r0' performs /no/ evaluation.+r0 :: Strategy a+r0 _ = ()++-- | 'rseq' evaluates its argument to weak head normal form.+rseq :: Strategy a+rseq x = x `seq` ()++-- | 'rdeepseq' fully evaluates its argument.+-- Relies on class 'NFData' from module "Control.DeepSeq".+rdeepseq :: NFData a => Strategy a+rdeepseq x = x `deepseq` ()+++-- --------------------------------------------------------------------------+-- Sequential strategies for lists++-- | Evaluate each element of a list according to the given strategy.+-- This function is a specialisation of 'seqFoldable' to lists.+seqList :: Strategy a -> Strategy [a]+seqList _strat [] = ()+seqList strat (x:xs) = strat x `seq` seqList strat xs+-- Alternative definition via seqFoldable:+-- seqList = seqFoldable++-- | Evaluate the first n elements of a list according to the given strategy.+seqListN :: Int -> Strategy a -> Strategy [a]+seqListN 0 _strat _ = ()+seqListN !_ _strat [] = ()+seqListN !n strat (x:xs) = strat x `seq` seqListN (n-1) strat xs++-- | Evaluate the nth element of a list (if there is such) according to+-- the given strategy.+-- The spine of the list up to the nth element is evaluated as a side effect.+seqListNth :: Int -> Strategy a -> Strategy [a]+seqListNth 0 strat (x:_) = strat x+seqListNth !_ _strat [] = ()+seqListNth !n strat (_:xs) = seqListNth (n-1) strat xs+++-- --------------------------------------------------------------------------+-- Sequential strategies for foldable data types++-- | Evaluate the elements of a foldable data structure according to+-- the given strategy.+seqFoldable :: Foldable t => Strategy a -> Strategy (t a)+seqFoldable strat = seqList strat . toList+-- Alternative definition via foldl':+-- seqFoldable strat = foldl' (const strat) ()++{-# SPECIALISE seqFoldable :: Strategy a -> Strategy [a] #-}++-- | Evaluate the elements of an array according to the given strategy.+-- Evaluation of the array bounds may be triggered as a side effect.+#if (__GLASGOW_HASKELL__ >= 711) && MIN_VERSION_array(0,5,1)+seqArray :: Strategy a -> Strategy (Array i a)+#else+seqArray :: Ix i => Strategy a -> Strategy (Array i a)+#endif+seqArray strat = seqList strat . Data.Array.elems++-- | Evaluate the bounds of an array according to the given strategy.+#if (__GLASGOW_HASKELL__ >= 711) && MIN_VERSION_array(0,5,1)+seqArrayBounds :: Strategy i -> Strategy (Array i a)+#else+seqArrayBounds :: Ix i => Strategy i -> Strategy (Array i a)+#endif+seqArrayBounds strat = seqTuple2 strat strat . Data.Array.bounds++-- | Evaluate the keys and values of a map according to the given strategies.+seqMap :: Strategy k -> Strategy v -> Strategy (Map k v)+seqMap stratK stratV = seqList (seqTuple2 stratK stratV) . Data.Map.toList+++-- --------------------------------------------------------------------------+-- Sequential strategies for tuples++seqTuple2 :: Strategy a -> Strategy b -> Strategy (a,b)+seqTuple2 strat1 strat2 (x1,x2) =+ strat1 x1 `seq` strat2 x2++seqTuple3 :: Strategy a -> Strategy b -> Strategy c -> Strategy (a,b,c)+seqTuple3 strat1 strat2 strat3 (x1,x2,x3) =+ strat1 x1 `seq` strat2 x2 `seq` strat3 x3++seqTuple4 :: Strategy a -> Strategy b -> Strategy c -> Strategy d -> Strategy (a,b,c,d)+seqTuple4 strat1 strat2 strat3 strat4 (x1,x2,x3,x4) =+ strat1 x1 `seq` strat2 x2 `seq` strat3 x3 `seq` strat4 x4++seqTuple5 :: Strategy a -> Strategy b -> Strategy c -> Strategy d -> Strategy e -> Strategy (a,b,c,d,e)+seqTuple5 strat1 strat2 strat3 strat4 strat5 (x1,x2,x3,x4,x5) =+ strat1 x1 `seq` strat2 x2 `seq` strat3 x3 `seq` strat4 x4 `seq` strat5 x5++seqTuple6 :: Strategy a -> Strategy b -> Strategy c -> Strategy d -> Strategy e -> Strategy f -> Strategy (a,b,c,d,e,f)+seqTuple6 strat1 strat2 strat3 strat4 strat5 strat6 (x1,x2,x3,x4,x5,x6) =+ strat1 x1 `seq` strat2 x2 `seq` strat3 x3 `seq` strat4 x4 `seq` strat5 x5 `seq` strat6 x6++seqTuple7 :: Strategy a -> Strategy b -> Strategy c -> Strategy d -> Strategy e -> Strategy f -> Strategy g -> Strategy (a,b,c,d,e,f,g)+seqTuple7 strat1 strat2 strat3 strat4 strat5 strat6 strat7 (x1,x2,x3,x4,x5,x6,x7) =+ strat1 x1 `seq` strat2 x2 `seq` strat3 x3 `seq` strat4 x4 `seq` strat5 x5 `seq` strat6 x6 `seq` strat7 x7++seqTuple8 :: Strategy a -> Strategy b -> Strategy c -> Strategy d -> Strategy e -> Strategy f -> Strategy g -> Strategy h -> Strategy (a,b,c,d,e,f,g,h)+seqTuple8 strat1 strat2 strat3 strat4 strat5 strat6 strat7 strat8 (x1,x2,x3,x4,x5,x6,x7,x8) =+ strat1 x1 `seq` strat2 x2 `seq` strat3 x3 `seq` strat4 x4 `seq` strat5 x5 `seq` strat6 x6 `seq` strat7 x7 `seq` strat8 x8++seqTuple9 :: Strategy a -> Strategy b -> Strategy c -> Strategy d -> Strategy e -> Strategy f -> Strategy g -> Strategy h -> Strategy i -> Strategy (a,b,c,d,e,f,g,h,i)+seqTuple9 strat1 strat2 strat3 strat4 strat5 strat6 strat7 strat8 strat9 (x1,x2,x3,x4,x5,x6,x7,x8,x9) =+ strat1 x1 `seq` strat2 x2 `seq` strat3 x3 `seq` strat4 x4 `seq` strat5 x5 `seq` strat6 x6 `seq` strat7 x7 `seq` strat8 x8 `seq` strat9 x9
+ changelog.md view
@@ -0,0 +1,52 @@+# Changelog for [`parallel` package](http://hackage.haskell.org/package/parallel)++## 3.3.0.0 *Oct 2025*++* Bump dependency bounds+* Support MicroHs ([#81](https://github.com/haskell/parallel/pull/81))+* Make rolling buffer strategies compositional ([#77](https://github.com/haskell/parallel/pull/77))+* Deprecate `dot` ([#75](https://github.com/haskell/parallel/pull/75))+* Make strategic function application operators handle strategies correctly ([#61](https://github.com/haskell/parallel/pull/61))+* Add `parFmap` ([#53](https://github.com/haskell/parallel/pull/53))+* Make `parListChunk` more efficient ([#45](https://github.com/haskell/parallel/issues/45))+* Update documentation++## 3.2.2.0 *Jul 2018*++* Bump dependency bounds+* Add `parEval`+* Add a `MonadFix Eval` instance++## 3.2.1.1 *Apr 2017*++* Compatibility with `deepseq-1.4.3`+* Minor documentation clarifications++## 3.2.1.0 *Jan 2016*++* Support `base-4.9.0.0`+* Add `{-# NOINLINE[1] rseq #-}` to make the `RULE` more robust+* Fix broken links to papers in Haddock+* Make `rpar` type signature consistent with `rseq` via type synonym+* Drop redundant `Ix`-constraint on `seqArray`/`seqArrayBounds` for GHC >= 8.0++## 3.2.0.6 *Dec 2014*++* Make `-Wall` message free for all supported `base` versions++## 3.2.0.5 *Dec 2014*++* Support `base-4.8.0.0`/`deepseq-1.4.0.0` (and thus GHC 7.10)++## 3.2.0.4 *Nov 2013*++* Update package description to Cabal 1.10 format+* Add support for GHC 7.8+* Drop support for GHCs older than GHC 7.0.1+* Add NOINLINE pragmas to `parBuffer`, `parList`, and `evalBuffer`+ to make RULEs more likely to fire++## Older versions++* This package has a long history which is described in the Haddock documentation+ in the ["API History" section](./docs/Control-Parallel-Strategies.html#history)
parallel.cabal view
@@ -1,23 +1,70 @@-name: parallel-version: 1.1.0.1-license: BSD3-license-file: LICENSE-maintainer: libraries@haskell.org-synopsis: parallel programming library+cabal-version: >=1.10+name: parallel+version: 3.3.0.0+-- NOTE: Don't forget to update ./changelog.md+license: BSD3+license-file: LICENSE+maintainer: libraries@haskell.org+bug-reports: https://github.com/haskell/parallel/issues+synopsis: Parallel programming library+category: Control, Parallelism+build-type: Simple++tested-with:+ GHC == 9.12.2+ GHC == 9.10.1+ GHC == 9.8.4+ GHC == 9.6.7+ GHC == 9.4.8+ GHC == 9.2.8+ GHC == 9.0.2+ GHC == 8.10.7+ GHC == 8.8.4+ GHC == 8.6.5+ GHC == 8.4.4+ GHC == 8.2.2+ GHC == 8.0.2+ MHS+ description: This package provides a library for parallel programming.-build-type: Simple-cabal-version: >=1.2+ .+ For documentation, start from the "Control.Parallel.Strategies"+ module below.+ .+ For more tutorial documentation, see the book <https://simonmar.github.io/pages/pcph.html Parallel and Concurrent Programming in Haskell>.+ .+ To understand the principles behind the library, see+ <https://simonmar.github.io/bib/papers/strategies.pdf Seq no more: Better Strategies for Parallel Haskell>. -library {- exposed-modules:++extra-source-files: changelog.md++source-repository head+ type: git+ location: https://github.com/haskell/parallel.git++library+ default-language: Haskell2010+ other-extensions:+ BangPatterns+ CPP+ MagicHash+ UnboxedTuples++ exposed-modules:+ Control.Seq Control.Parallel Control.Parallel.Strategies- extensions: CPP- build-depends: base >= 3, containers, array - if impl(ghc >= 6.11) {- -- To improve parallel performance:- ghc-options: -feager-blackholing- }-}+ build-depends:+ array >= 0.3 && < 0.6,+ base >= 4.3 && < 4.22,+ containers >= 0.4 && < 0.9,+ deepseq >= 1.1 && < 1.6++ ghc-options: -Wall++ if impl(ghc >= 6.11)+ -- To improve parallel performance:+ ghc-options: -feager-blackholing