parallel 2.2.0.1 → 3.0.0.0
raw patch · 4 files changed
+863/−269 lines, 4 files
Files
- Control/Parallel.hs +1/−37
- Control/Parallel/Strategies.hs +649/−231
- Control/Seq.hs +211/−0
- parallel.cabal +2/−1
Control/Parallel.hs view
@@ -13,49 +13,13 @@ ----------------------------------------------------------------------------- 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`-#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 -- Maybe parIO and the like could be added here later.
Control/Parallel/Strategies.hs view
@@ -1,114 +1,135 @@ ----------------------------------------------------------------------------- -- | -- Module : Control.Parallel.Strategies--- Copyright : (c) The University of Glasgow 2001-2009+-- 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, specify a--- way to evaluate a structure with components in sequence or in--- parallel.------ Strategies are for expressing /deterministic parallelism/:--- the result of the program is unaffected by evaluating in parallel.--- For non-deterministic parallel programming, see--- "Control.Concurrent".--- --- Strategies let you separate the description of parallelism from the--- logic of your program, enabling modular parallelism.------ Version 1.x+-- Parallel Evaluation Strategies, or Strategies for short, provide+-- ways to express parallel computations. Strategies have the following+-- key features: ----- The original Strategies design is described in--- <http://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. +-- * 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". ----- Version 2.x+-- * 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. ----- 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\" <http://www.haskell.org/~simonmar/papers/multicore-ghc.pdf>.+-- * Strategies are /compositional/: larger strategies can be built+-- by gluing together smaller ones. ----- 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'.+-- * 'Monad' and 'Applicative' instances are provided, for quickly building+-- strategies that involve traversing structures in a regular way. -- --- 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 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 (Par . (``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.+-- For API history and changes in this release, see "Control.Parallel.Strategies#history". ----------------------------------------------------------------------------- module Control.Parallel.Strategies (- -- * Strategy type and basic operations- Strategy,- using,- withStrategy,- rwhnf, rdeepseq, r0, rpar,- -- * Tuple strategies- seqPair, parPair,- seqTriple, parTriple,- -- * General traversals- seqTraverse,- parTraverse,- -- * List strategies- parList, seqList,- parListN, parListChunk,- parMap,- parBuffer,- -- * Simple list strategies- parListWHNF,- parBufferWHNF,- -- * Strategy composition operators- ($|), ($||),- (.|), (.||),- (-|), (-||),- -- * Building strategies- Eval(..), unEval,+ -- * The strategy type+ Strategy - -- * re-exported for backwards compatibility- NFData(..), + -- * Application of strategies+ , using -- :: a -> Strategy a -> a+ , withStrategy -- :: Strategy a -> a -> a - -- * Deprecated functionality+ -- * Composition of strategies+ , dot -- :: Strategy a -> Strategy a -> Strategy a++ -- * Basic strategies+ , r0 -- :: Strategy a+ , rseq+ , rdeepseq -- :: NFData a => Strategy a+ , rpar -- :: 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++ -- * 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(Done) -- instances: Monad, Functor, Applicative+ , runEval -- :: Eval a -> 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 ) where import Data.Traversable@@ -117,47 +138,88 @@ import Control.DeepSeq import Control.Monad +import qualified Control.Seq++infixr 9 `dot` -- same as (.)+infixl 0 `using` -- lowest precedence and associate to the left+ -- -------------------------------------------------------------------------------- Eval+-- Eval monad (isomorphic to Lift monad from MonadLib 3.6.1) --- | `Eval` is an Applicative Functor that makes it easier to define--- parallel strategies that involve traversing structures.+-- | 'Eval' is a Monad that makes it easier to define parallel+-- strategies. It is a strict identity monad: that is, in ----- a 'Seq' value will be evaluated strictly in sequence in its context,--- whereas a 'Par' value wraps an expression that may be evaluated in--- parallel. The Applicative instance allows sequential composition,--- making it possible to describe an evaluateion strategy by composing--- 'Par' and 'Seq' with '<*>'.+-- > m >>= f ----- For example,+-- @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 (Par . (`using` strat))+-- > parList strat = traverse (rpar `dot` strat)) ----- > seqPair :: Strategy a -> Strategy b -> Strategy (a,b)--- > seqPair f g (a,b) = pure (,) <$> f a <*> g b+-- > evalPair :: Strategy a -> Strategy b -> Strategy (a,b)+-- > evalPair f g (a,b) = pure (,) <$> f a <*> g b ---data Eval a = Seq a | Par a | Lazy a -unEval :: Eval a -> a-unEval (Seq a) = a-unEval (Par a) = a-unEval (Lazy a) = a+data Eval a = Done a +-- | Pull the result out of the monad.+runEval :: Eval a -> a+runEval (Done x) = x++instance Monad Eval where+ return x = Done x+ Done x >>= k = k x -- Note: pattern 'Done x' makes '>>=' strict+ instance Functor Eval where- fmap f x = x >>= return . f+ fmap = liftM instance Applicative Eval where- pure a = return a (<*>) = ap+ pure = return -instance Monad Eval where- return = Lazy- m >>= k = case m of- Seq a -> a `pseq` k a- Par a -> a `par` k a- Lazy a -> k a +-- 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)++ -- ----------------------------------------------------------------------------- -- Strategies @@ -178,176 +240,356 @@ -- type Strategy a = a -> Eval a --- | evaluate a value using the given 'Strategy'.+-- | Evaluate a value using the given 'Strategy'. ----- > using x s = s x+-- > x `using` s = runEval (s x) -- using :: a -> Strategy a -> a-using x s = unEval (s x)+x `using` strat = runEval (strat x) -- | evaluate a value using the given 'Strategy'. This is simply--- 'using' with the arguments reversed, and is equal to '($)'.+-- 'using' with the arguments reversed. -- withStrategy :: Strategy a -> a -> a withStrategy = flip using --- | A 'Strategy' that does no evaluation of its argument+-- | Compose two strategies sequentially. +-- This is the analogue to function composition on strategies.+--+-- > strat2 `dot` strat1 == strat2 . withStrategy strat1+--+dot :: Strategy a -> Strategy a -> Strategy a+strat2 `dot` strat1 = strat2 . runEval . strat1++-- 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++-- One might be tempted to think that 'dot' is equivalent to '(<=<)',+-- the right-to-left Kleisli composition in the Eval monad, because+-- '(<=<)' can take the type @Strategy a -> Strategy a -> Strategy a@+-- and intuitively does what 'dot' does: First apply the strategy to the+-- right then the one to the left. However, there is a subtle difference+-- in strictness, witnessed by the following example:+--+-- > (r0 `dot` rseq) undefined == Done undefined+-- > (r0 <=< rseq) undefined == undefined+--++-- | Inject a sequential strategy (ie. coerce a sequential strategy+-- to a general strategy).+--+-- Thanks to 'evalSeq', the type @Control.Seq.Strategy 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 documetnation 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 = Lazy+r0 x = return x --- | A 'Strategy' that simply evaluates its argument to Weak Head Normal--- Form (i.e. evaluates it as far as the topmost constructor).-rwhnf :: Strategy a-rwhnf = Seq+-- 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 --- | A 'Strategy' that evaluates its argument in parallel-rpar :: Strategy a-rpar = Par+-- | 'rseq' evaluates its argument to weak head normal form.+--+-- > rseq == evalSeq Control.Seq.rseq+--+rseq :: Strategy a+rseq x = x `pseq` return x --- | A 'Strategy' that fully evaluates its argument--- --- > rdeepseq a = rnf a `pseq` a+-- 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 a = Seq (rnf a `pseq` a)+rdeepseq x = rnf x `pseq` return x --- -------------------------------------------------------------------------------- Tuples+-- 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 -seqPair :: Strategy a -> Strategy b -> Strategy (a,b)-seqPair f g (a,b) = pure (,) <*> f a <*> g b+-- | 'rpar' sparks its argument (for evaluation in parallel).+rpar :: Strategy a+rpar x = x `par` return x -parPair :: Strategy a -> Strategy b -> Strategy (a,b)-parPair f g (a,b) = do- a' <- Par (a `using` f)- b' <- Par (b `using` g)- return (a',b') -seqTriple :: Strategy a -> Strategy b -> Strategy c -> Strategy (a,b,c)-seqTriple f g h (a,b,c) = pure (,,) <*> f a <*> g b <*> h c--parTriple :: Strategy a -> Strategy b -> Strategy c -> Strategy (a,b,c)-parTriple f g h (a,b,c) = do- a' <- Par (a `using` f)- b' <- Par (b `using` g)- c' <- Par (c `using` h)- return (a',b',c')+-- --------------------------------------------------------------------------+-- Strategy combinators for Traversable data types --- -------------------------------------------------------------------------------- General sequential/parallel traversals+-- | Evaluate the elements of a traversable data structure +-- according to the given strategy.+evalTraversable :: Traversable t => Strategy a -> Strategy (t a)+evalTraversable = traverse --- | A strategy that traverses a container data type with an instance--- of 'Traversable', and sparks each of the elements using the supplied--- strategy.-parTraverse :: Traversable t => Strategy a -> Strategy (t a)-parTraverse strat = traverse (Par . (`using` strat))+-- | Like 'evalTraversable' but evaluates all elements in parallel.+parTraversable :: Traversable t => Strategy a -> Strategy (t a)+parTraversable strat = evalTraversable (rpar `dot` strat) --- | A strategy that traverses a container data type with an instance--- of 'Traversable', and evaluates each of the elements in left-to-right--- sequence using the supplied strategy.-seqTraverse :: Traversable t => Strategy a -> Strategy (t a)-seqTraverse = traverse+{-# SPECIALISE evalTraversable :: Strategy a -> Strategy (Maybe a) #-}+{-# SPECIALISE parTraversable :: Strategy a -> Strategy (Maybe a) #-}+{-# SPECIALISE evalTraversable :: Strategy a -> Strategy [a] #-}+{-# SPECIALISE parTraversable :: Strategy a -> Strategy [a] #-} -{-# SPECIALISE parTraverse :: Strategy a -> Strategy [a] #-}-{-# SPECIALISE seqTraverse :: Strategy a -> Strategy [a] #-}+-- --------------------------------------------------------------------------+-- Strategies for lists --- -------------------------------------------------------------------------------- Lists+-- | Evaluate each element of a list according to the given strategy.+-- Equivalent to 'evalTraversable' at the list type.+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') --- | Spark each of the elements of a list using the given strategy.--- Equivalent to 'parTraverse' at the list type.+-- | Evaluate each element of a list in parallel according to given strategy.+-- Equivalent to 'parTraversable' at the list type. parList :: Strategy a -> Strategy [a]-parList = parTraverse+parList = parTraversable+-- Alternative definition via evalList:+-- parList strat = evalList (rpar `dot` strat) --- | Evaluate each of the elements of a list sequentially from left to right--- using the given strategy. Equivalent to 'seqTraverse' at the list type.-seqList :: Strategy a -> Strategy [a]-seqList = traverse+-- | @'evaListSplitAt' n stratPref stratSuff@ evaluates the prefix+-- (of length @n@) of a list according to @stratPref@ and its 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 (rpar `dot` stratPref) (rpar `dot` 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 0 _strat xs = return xs-parListN !_n _strat [] = return []-parListN !n strat (x:xs) = do- x' <- Par (x `using` strat)- xs' <- parListN (n-1) strat xs- return (x':xs')+parListN n strat = evalListN n (rpar `dot` strat) +-- | 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.+evalListNth :: Int -> Strategy a -> Strategy [a]+evalListNth n strat = evalListSplitAt n r0 (evalListN 1 strat)++-- | Like 'evalListN' but evaluates the nth element in parallel.+parListNth :: Int -> Strategy a -> Strategy [a]+parListNth n strat = evalListNth n (rpar `dot` strat)++-- | Divides a list into chunks, and applies the strategy+-- @'evalList' strat@ to each chunk in parallel.+--+-- It is expected that this function will be replaced by a more+-- generic clustering infrastructure in the future.+-- parListChunk :: Int -> Strategy a -> Strategy [a] parListChunk n strat xs =- concat `fmap` parList (seqList strat) (chunk n xs)+ concat `fmap` parList (evalList strat) (chunk n xs) chunk :: Int -> [a] -> [[a]] chunk _ [] = [] chunk n xs = as : chunk n bs where (as,bs) = splitAt n xs +-- Non-compositional version of 'parList', evaluating list elements+-- to weak head normal form.+-- Not to be exported; used for optimisation.++-- | DEPRECATED: use @'parList' 'rseq'@ instead+parListWHNF :: Strategy [a]+parListWHNF xs = go xs `pseq` return xs+ where -- go :: [a] -> [a]+ go [] = []+ go (y:ys) = y `par` go ys++-- The non-compositional 'parListWHNF' might be more efficient than its+-- more compositional counterpart; use RULES to do the specialisation.++{-# RULES + "parList/rseq" parList rseq = parListWHNF+ #-}++-- --------------------------------------------------------------------------+-- Convenience++-- | A combination of 'parList' and 'map', encapsulating a common pattern:+--+-- > parMap strat f = withStrategy strat . map f+-- parMap :: Strategy b -> (a -> b) -> [a] -> [b] parMap strat f = (`using` parList strat) . map f --- -------------------------------------------------------------------------------- parBuffer+-- --------------------------------------------------------------------------+-- Strategies for lazy lists --- | Applies a strategy to the nth element of list when the head is demanded.--- More precisely:------ * semantics: @parBuffer n s = id :: [a] -> [a]@+-- List-based non-compositional rolling buffer strategy, evaluating list+-- elements to weak head normal form.+-- Not to be exported; used in evalBuffer and for optimisation.+evalBufferWHNF :: Int -> Strategy [a]+evalBufferWHNF n0 xs0 = return (ret xs0 (start n0 xs0))+ where -- ret :: [a] -> [a] -> [a]+ ret (x:xs) (y:ys) = y `pseq` (x : ret xs ys)+ ret xs _ = xs++ -- start :: Int -> [a] -> [a]+ start 0 ys = ys+ start !_n [] = []+ start !n (y:ys) = y `pseq` start (n-1) ys++-- | 'evalBuffer' is a rolling buffer strategy combinator for (lazy) lists. ----- * dynamic behaviour: evalutates the nth element of the list when the--- head is demanded.+-- 'evalBuffer' is not as compositional as the type suggests. In fact,+-- it evaluates list elements at least to weak head normal form,+-- disregarding a strategy argument 'r0'.+-- +-- > evalBuffer n r0 == evalBuffer n rseq ----- The idea is to provide a `rolling buffer' of length n. It is a--- better than 'parList' for a lazy stream, because p'arList' will--- evaluate the entire list, whereas 'parBuffer' will only evaluate a--- fixed number of elements ahead.+evalBuffer :: Int -> Strategy a -> Strategy [a]+evalBuffer n strat = evalBufferWHNF n . map (withStrategy strat) -parBuffer :: Int -> Strategy a -> [a] -> [a]-parBuffer n strat xs = map (`using` strat) xs `using` parBufferWHNF n+-- Like evalBufferWHNF but sparks the list elements when pushing them+-- into the buffer.+-- Not to be exported; used in parBuffer and for optimisation.+parBufferWHNF :: Int -> Strategy [a]+parBufferWHNF n0 xs0 = return (ret xs0 (start n0 xs0))+ where -- ret :: [a] -> [a] -> [a]+ ret (x:xs) (y:ys) = y `par` (x : ret xs ys)+ ret xs _ = xs --- -------------------------------------------------------------------------------- Simple strategies+ -- start :: Int -> [a] -> [a]+ start 0 ys = ys+ start !_n [] = []+ start !n (y:ys) = y `par` start (n-1) ys --- These are non-compositional strategies that might be more efficient--- than their more general counterparts. We use RULES to do the--- specialisation. +-- | Like 'evalBuffer' but evaluates the list elements in parallel when+-- pushing them into the buffer.+parBuffer :: Int -> Strategy a -> Strategy [a]+parBuffer n strat = parBufferWHNF n . map (withStrategy strat)+-- Alternative definition via evalBuffer (may compromise firing of RULES):+-- parBuffer n strat = evalBuffer n (rpar `dot` strat)++-- Deforest the intermediate list in parBuffer/evalBuffer when it is+-- unnecessary:+ {-# RULES -"parList/rwhnf" parList rwhnf = parListWHNF-"parBuffer/rwhnf" forall n . parBuffer n rwhnf = (`using` parBufferWHNF n)+"evalBuffer/rseq" forall n . evalBuffer n rseq = evalBufferWHNF n+"parBuffer/rseq" forall n . parBuffer n rseq = parBufferWHNF n #-} --- | version of 'parList' specialised to 'rwhnf'. This version is--- much simpler, and may be faster than 'parList rwhnf'. You should--- never need to use this directly, since 'parList rwhnf' is--- automatically optimised to 'parListWHNF'. It is here for--- experimentation purposes only.-parListWHNF :: Strategy [a]-parListWHNF xs = go xs `pseq` return xs- where go [] = []- go (y:ys) = y `par` go ys+-- --------------------------------------------------------------------------+-- Strategies for tuples --- | version of 'parBuffer' specialised to 'rwhnf'. You should--- never need to use this directly, since 'parBuffer rwhnf' is--- automatically optimised to 'parBufferWHNF'. It is here for--- experimentation purposes only.-parBufferWHNF :: Int -> Strategy [a]-parBufferWHNF n0 xs0 = return (ret xs0 (start n0 xs0))- where- ret (x:xs) (y:ys) = y `par` (x : ret xs ys)- ret xs _ = xs+evalTuple2 :: Strategy a -> Strategy b -> Strategy (a,b)+evalTuple2 strat1 strat2 (x1,x2) =+ pure (,) <*> strat1 x1 <*> strat2 x2 - start _ [] = []- start 0 ys = ys- start n (y:ys) = y `par` start (n-1) ys+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 ---------------------------------------------------------------------------------- * Strategic Function Application-------------------------------------------------------------------------------+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 (rpar `dot` strat1) (rpar `dot` strat2)++parTuple3 :: Strategy a -> Strategy b -> Strategy c -> Strategy (a,b,c)+parTuple3 strat1 strat2 strat3 =+ evalTuple3 (rpar `dot` strat1) (rpar `dot` strat2) (rpar `dot` strat3)++parTuple4 :: Strategy a -> Strategy b -> Strategy c -> Strategy d -> Strategy (a,b,c,d)+parTuple4 strat1 strat2 strat3 strat4 =+ evalTuple4 (rpar `dot` strat1) (rpar `dot` strat2) (rpar `dot` strat3) (rpar `dot` 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 (rpar `dot` strat1) (rpar `dot` strat2) (rpar `dot` strat3) (rpar `dot` strat4) (rpar `dot` 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 (rpar `dot` strat1) (rpar `dot` strat2) (rpar `dot` strat3) (rpar `dot` strat4) (rpar `dot` strat5) (rpar `dot` 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 (rpar `dot` strat1) (rpar `dot` strat2) (rpar `dot` strat3) (rpar `dot` strat4) (rpar `dot` strat5) (rpar `dot` strat6) (rpar `dot` 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 (rpar `dot` strat1) (rpar `dot` strat2) (rpar `dot` strat3) (rpar `dot` strat4) (rpar `dot` strat5) (rpar `dot` strat6) (rpar `dot` strat7) (rpar `dot` 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 (rpar `dot` strat1) (rpar `dot` strat2) (rpar `dot` strat3) (rpar `dot` strat4) (rpar `dot` strat5) (rpar `dot` strat6) (rpar `dot` strat7) (rpar `dot` strat8) (rpar `dot` strat9)++-- --------------------------------------------------------------------------+-- 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 @$||@.+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@@ -394,21 +636,197 @@ -- ----------------------------------------------------------------------------- -- Old/deprecated stuff -{-# DEPRECATED Done "The Strategy type is now a -> a, not a -> Done" #-}+{-# DEPRECATED Done "The Strategy type is now a -> Eval a, not a -> Done" #-}+-- | DEPRECCATED: replaced by the 'Eval' monad type Done = () {-# DEPRECATED demanding "Use pseq or $| instead" #-}+-- | DEPRECATED: Use 'pseq' or '$|' instead demanding :: a -> Done -> a demanding = flip pseq {-# DEPRECATED sparking "Use par or $|| instead" #-}+-- | DEPRECATED: Use 'par' or '$||' instead sparking :: a -> Done -> a sparking = flip par {-# DEPRECATED (>|) "Use pseq or $| instead" #-}+-- | DEPRECATED: Use 'pseq' or '$|' instead (>|) :: Done -> Done -> Done (>|) = Prelude.seq {-# DEPRECATED (>||) "Use par or $|| instead" #-}+-- | DEPRECATED: Use 'par' or '$||' instead (>||) :: Done -> Done -> Done (>||) = par++{-# DEPRECATED rwhnf "renamed to rseq" #-}+-- | DEPRECATED: renamed to 'rseq'+rwhnf :: Strategy a+rwhnf = rseq++{-# DEPRECATED seqTraverse "renamed to evalTraversable" #-}+-- | DEPRECATED: renamed to 'evalTraversable'+seqTraverse :: Traversable t => Strategy a -> Strategy (t a)+seqTraverse = evalTraversable++{-# DEPRECATED parTraverse "renamed to parTraversable" #-}+-- | DEPRECATED: renamed to 'parTraversable'+parTraverse :: Traversable t => Strategy a -> Strategy (t a)+parTraverse = parTraversable++{-# DEPRECATED parListWHNF "use (parList rseq) instead" #-}++{-# DEPRECATED seqList "renamed to evalList" #-}+-- | DEPRECATED: renamed to 'evalList'+seqList :: Strategy a -> Strategy [a]+seqList = evalList++{-# DEPRECATED seqPair "renamed to evalTuple2" #-}+-- | DEPRECATED: renamed to 'evalTuple2'+seqPair :: Strategy a -> Strategy b -> Strategy (a,b)+seqPair = evalTuple2++{-# DEPRECATED parPair "renamed to parTuple2" #-}+-- | DEPRECATED: renamed to 'parTuple2'+parPair :: Strategy a -> Strategy b -> Strategy (a,b)+parPair = parTuple2++{-# DEPRECATED seqTriple "renamed to evalTuple3" #-}+-- | DEPRECATED: renamed to 'evalTuple3'+seqTriple :: Strategy a -> Strategy b -> Strategy c -> Strategy (a,b,c)+seqTriple = evalTuple3++{-# DEPRECATED parTriple "renamed to parTuple3" #-}+-- | DEPRECATED: renamed to 'parTuple3'+parTriple :: Strategy a -> Strategy b -> Strategy c -> Strategy (a,b,c)+parTriple = parTuple3++{-# DEPRECATED unEval "renamed to runEval" #-}+-- | DEPRECATED: 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/ <http://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/ <http://www.haskell.org/~simonmar/papers/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 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 (Par . (``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 introduced a major overhaul of the API, to match what is+presented in the paper ++ /Seq no More: Better Strategies for Parallel Haskell/+ <http://www.haskell.org/~simonmar/papers/strategies.pdf>++The major differenes 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).++ * A strategy combinator that is not as compositional as its type+ suggests is suffixed with @'@.+ Examples: 'evalFunctor'', 'parBuffer''.+-}+
+ Control/Seq.hs view
@@ -0,0 +1,211 @@+{-# LANGUAGE BangPatterns #-}++-----------------------------------------------------------------------------+-- |+-- 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 complimentary 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++ -- * Composition of sequential strategies+ , dot -- :: Strategy a -> Strategy a -> Strategy 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+ , seqTuple2 -- :: Strategy a -> ... -> Strategy (a,...)+ , seqTuple3+ , seqTuple4+ , seqTuple5+ , seqTuple6+ , seqTuple7+ , seqTuple8+ , seqTuple9+ ) where++import Prelude+import Control.DeepSeq (NFData, deepseq)+import Data.Foldable (Foldable, toList)+import Data.Map (Map)+import qualified Data.Map (toList)+import Data.Ix (Ix)+import Data.Array (Array)+import qualified Data.Array (bounds, elems)++infixr 9 `dot` -- same as function composition (.)+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++-- | Compose two strategies sequentially.+-- This is the analogue to function composition on strategies.+-- (Probably not very useful; provided because "Control.Parallel.Strategies"+-- provides the same function.)+--+-- > strat2 `dot` strat1 == strat2 . withStrategy strat1+--+dot :: Strategy a -> Strategy a -> Strategy a+(strat2 `dot` strat1) x = strat1 x `seq` strat2 x+ +-- More reasons for removing dot:+-- * It is inefficient: Traverses 'x' twice.+-- * It does not satisfy the property that 'Strategies.dot' has; there is +-- a counter-example to the equation+-- > strat2 `dot` strat1 == strat2 . withStrategy strat1+-- Try strat2 = r0 and strat1 = rseq and apply to 'undefined';+-- the LHS will diverge while the RHS will evaluate to '()'.+++-- --------------------------------------------------------------------------+-- 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.+seqArray :: Ix i => Strategy a -> Strategy (Array i a)+seqArray strat = seqList strat . Data.Array.elems++-- | Evaluate the bounds of an array according to the given strategy.+seqArrayBounds :: Ix i => Strategy i -> Strategy (Array i a)+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++-- | 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 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
parallel.cabal view
@@ -1,5 +1,5 @@ name: parallel-version: 2.2.0.1+version: 3.0.0.0 license: BSD3 license-file: LICENSE maintainer: libraries@haskell.org@@ -16,6 +16,7 @@ library { exposed-modules:+ Control.Seq Control.Parallel Control.Parallel.Strategies extensions: CPP BangPatterns