libghc-parallel-doc 3.2.1.0-3 / usr / share / doc / libghc-parallel-doc / html / parallel.txt

-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | Parallel programming library
--   
--   This package provides a library for parallel programming.
@package parallel
@version 3.2.1.0


-- | 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
--   <a>Control.Parallel.Strategies</a>).
module Control.Seq

-- | The type <tt><a>Strategy</a> a</tt> is <tt>a -&gt; ()</tt>. 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
infixl 0 `using`

-- | Evaluate a value using the given strategy. This is simply <a>using</a>
--   with arguments reversed.
withStrategy :: Strategy a -> a -> a

-- | <a>r0</a> performs *no* evaluation.
r0 :: Strategy a

-- | <a>rseq</a> evaluates its argument to weak head normal form.
rseq :: Strategy a

-- | <a>rdeepseq</a> fully evaluates its argument. Relies on class
--   <a>NFData</a> from module <a>Control.DeepSeq</a>.
rdeepseq :: NFData a => Strategy a

-- | Evaluate each element of a list according to the given strategy. This
--   function is a specialisation of <a>seqFoldable</a> to lists.
seqList :: Strategy a -> Strategy [a]

-- | Evaluate the first n elements of a list according to the given
--   strategy.
seqListN :: Int -> Strategy a -> Strategy [a]

-- | 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]

-- | Evaluate the elements of a foldable data structure according to the
--   given strategy.
seqFoldable :: Foldable t => Strategy a -> Strategy (t a)

-- | Evaluate the keys and values of a map according to the given
--   strategies.
seqMap :: Strategy k -> Strategy v -> Strategy (Map k v)

-- | Evaluate the elements of an array according to the given strategy.
--   Evaluation of the array bounds may be triggered as a side effect.
seqArray :: Strategy a -> Strategy (Array i a)

-- | Evaluate the bounds of an array according to the given strategy.
seqArrayBounds :: Strategy i -> Strategy (Array i a)
seqTuple2 :: Strategy a -> Strategy b -> Strategy (a, b)
seqTuple3 :: Strategy a -> Strategy b -> Strategy c -> Strategy (a, b, c)
seqTuple4 :: Strategy a -> Strategy b -> Strategy c -> Strategy d -> Strategy (a, b, c, d)
seqTuple5 :: Strategy a -> Strategy b -> Strategy c -> Strategy d -> Strategy e -> Strategy (a, b, c, d, e)
seqTuple6 :: Strategy a -> Strategy b -> Strategy c -> Strategy d -> Strategy e -> Strategy f -> Strategy (a, b, c, d, e, f)
seqTuple7 :: Strategy a -> Strategy b -> Strategy c -> Strategy d -> Strategy e -> Strategy f -> Strategy g -> Strategy (a, b, c, d, e, f, g)
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)
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)


-- | Parallel Constructs
module Control.Parallel

-- | Indicates that it may be beneficial to evaluate the first argument in
--   parallel with the second. Returns the value of the second argument.
--   
--   <tt>a `<a>par</a>` b</tt> is exactly equivalent semantically to
--   <tt>b</tt>.
--   
--   <tt>par</tt> is generally used when the value of <tt>a</tt> is likely
--   to be required later, but not immediately. Also it is a good idea to
--   ensure that <tt>a</tt> is not a trivial computation, otherwise the
--   cost of spawning it in parallel overshadows the benefits obtained by
--   running it in parallel.
--   
--   Note that actual parallelism is only supported by certain
--   implementations (GHC with the <tt>-threaded</tt> option, and GPH, for
--   now). On other implementations, <tt>par a b = b</tt>.
par :: a -> b -> b
infixr 0 `par`

-- | Semantically identical to <a>seq</a>, but with a subtle operational
--   difference: <a>seq</a> is strict in both its arguments, so the
--   compiler may, for example, rearrange <tt>a `<a>seq</a>` b</tt> into
--   <tt>b `<a>seq</a>` a `<a>seq</a>` b</tt>. This is normally no problem
--   when using <a>seq</a> 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 want to evaluate <tt>a</tt>
--   before <tt>b</tt>, because we know that <tt>b</tt> has already been
--   sparked in parallel with <a>par</a>.
--   
--   This is why we have <a>pseq</a>. In contrast to <a>seq</a>,
--   <a>pseq</a> is only 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
infixr 0 `pseq`


-- | Parallel Evaluation Strategies, or Strategies for short, provide ways
--   to express parallel computations. Strategies have the following key
--   features:
--   
--   <ul>
--   <li>Strategies express <i>deterministic parallelism</i>: 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
--   <a>Control.Concurrent</a>.</li>
--   <li>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.</li>
--   <li>Strategies are <i>compositional</i>: larger strategies can be
--   built by gluing together smaller ones.</li>
--   <li><a>Monad</a> and <a>Applicative</a> instances are provided, for
--   quickly building strategies that involve traversing structures in a
--   regular way.</li>
--   </ul>
--   
--   For API history and changes in this release, see
--   <a>Control.Parallel.Strategies#history</a>.
module Control.Parallel.Strategies

-- | A <a>Strategy</a> is a function that embodies a parallel evaluation
--   strategy. The function traverses (parts of) its argument, evaluating
--   subexpressions in parallel or in sequence.
--   
--   A <a>Strategy</a> 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
--   <a>Strategy</a> function returns a new value equivalent to the old
--   value. The intention is that the program applies the <a>Strategy</a>
--   to a structure, and then uses the returned value, discarding the old
--   value. This idiom is expressed by the <a>using</a> function.
type Strategy a = a -> Eval a

-- | Evaluate a value using the given <a>Strategy</a>.
--   
--   <pre>
--   x `using` s = runEval (s x)
--   </pre>
using :: a -> Strategy a -> a
infixl 0 `using`

-- | evaluate a value using the given <a>Strategy</a>. This is simply
--   <a>using</a> with the arguments reversed.
withStrategy :: Strategy a -> a -> a

-- | Compose two strategies sequentially. This is the analogue to function
--   composition on strategies.
--   
--   <pre>
--   strat2 `dot` strat1 == strat2 . withStrategy strat1
--   </pre>
dot :: Strategy a -> Strategy a -> Strategy a
infixr 9 `dot`

-- | <a>r0</a> performs *no* evaluation.
--   
--   <pre>
--   r0 == evalSeq Control.Seq.r0
--   </pre>
r0 :: Strategy a

-- | <a>rseq</a> evaluates its argument to weak head normal form.
--   
--   <pre>
--   rseq == evalSeq Control.Seq.rseq
--   </pre>
rseq :: Strategy a

-- | <a>rdeepseq</a> fully evaluates its argument.
--   
--   <pre>
--   rdeepseq == evalSeq Control.Seq.rdeepseq
--   </pre>
rdeepseq :: NFData a => Strategy a

-- | <a>rpar</a> sparks its argument (for evaluation in parallel).
rpar :: Strategy a

-- | instead of saying <tt>rpar <a>dot</a> strat</tt>, you can say
--   <tt>rparWith strat</tt>. Compared to <a>rpar</a>, <a>rparWith</a>
--   
--   <ul>
--   <li>does not exit the <a>Eval</a> monad</li>
--   <li>does not have a built-in <a>rseq</a>, so for example `rparWith r0`
--   behaves as you might expect (it is a strategy that creates a spark
--   that does no evaluation).</li>
--   </ul>
rparWith :: Strategy a -> Strategy a

-- | Inject a sequential strategy (ie. coerce a sequential strategy to a
--   general strategy).
--   
--   Thanks to <a>evalSeq</a>, the type <tt>Control.Seq.Strategy a</tt> is
--   a subtype of <tt><a>Strategy</a> a</tt>.
evalSeq :: SeqStrategy a -> Strategy a

-- | A name for <tt>Control.Seq.Strategy</tt>, for documentation only.
type SeqStrategy a = Strategy a

-- | Evaluate the elements of a traversable data structure according to the
--   given strategy.
evalTraversable :: Traversable t => Strategy a -> Strategy (t a)

-- | Like <a>evalTraversable</a> but evaluates all elements in parallel.
parTraversable :: Traversable t => Strategy a -> Strategy (t a)

-- | Evaluate each element of a list according to the given strategy.
--   Equivalent to <a>evalTraversable</a> at the list type.
evalList :: Strategy a -> Strategy [a]

-- | Evaluate each element of a list in parallel according to given
--   strategy. Equivalent to <a>parTraversable</a> at the list type.
parList :: Strategy a -> Strategy [a]

-- | Evaluate the first n elements of a list according to the given
--   strategy.
evalListN :: Int -> Strategy a -> Strategy [a]

-- | Like <a>evalListN</a> but evaluates the first n elements in parallel.
parListN :: Int -> Strategy a -> Strategy [a]

-- | 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]

-- | Like <a>evalListN</a> but evaluates the nth element in parallel.
parListNth :: Int -> Strategy a -> Strategy [a]

-- | <tt><tt>evaListSplitAt</tt> n stratPref stratSuff</tt> evaluates the
--   prefix (of length <tt>n</tt>) of a list according to
--   <tt>stratPref</tt> and its the suffix according to <tt>stratSuff</tt>.
evalListSplitAt :: Int -> Strategy [a] -> Strategy [a] -> Strategy [a]

-- | Like <a>evalListSplitAt</a> but evaluates both sublists in parallel.
parListSplitAt :: Int -> Strategy [a] -> Strategy [a] -> Strategy [a]

-- | Divides a list into chunks, and applies the strategy
--   <tt><a>evalList</a> strat</tt> to each chunk in parallel.
--   
--   It is expected that this function will be replaced by a more generic
--   clustering infrastructure in the future.
--   
--   If the chunk size is 1 or less, <a>parListChunk</a> is equivalent to
--   <a>parList</a>
parListChunk :: Int -> Strategy a -> Strategy [a]

-- | A combination of <a>parList</a> and <a>map</a>, encapsulating a common
--   pattern:
--   
--   <pre>
--   parMap strat f = withStrategy (parList strat) . map f
--   </pre>
parMap :: Strategy b -> (a -> b) -> [a] -> [b]

-- | <a>evalBuffer</a> is a rolling buffer strategy combinator for (lazy)
--   lists.
--   
--   <a>evalBuffer</a> 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 <a>r0</a>.
--   
--   <pre>
--   evalBuffer n r0 == evalBuffer n rseq
--   </pre>
evalBuffer :: Int -> Strategy a -> Strategy [a]

-- | Like <a>evalBuffer</a> but evaluates the list elements in parallel
--   when pushing them into the buffer.
parBuffer :: Int -> Strategy a -> Strategy [a]
evalTuple2 :: Strategy a -> Strategy b -> Strategy (a, b)
evalTuple3 :: Strategy a -> Strategy b -> Strategy c -> Strategy (a, b, c)
evalTuple4 :: Strategy a -> Strategy b -> Strategy c -> Strategy d -> Strategy (a, b, c, d)
evalTuple5 :: Strategy a -> Strategy b -> Strategy c -> Strategy d -> Strategy e -> Strategy (a, b, c, d, e)
evalTuple6 :: Strategy a -> Strategy b -> Strategy c -> Strategy d -> Strategy e -> Strategy f -> Strategy (a, b, c, d, e, f)
evalTuple7 :: Strategy a -> Strategy b -> Strategy c -> Strategy d -> Strategy e -> Strategy f -> Strategy g -> Strategy (a, b, c, d, e, f, g)
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)
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)
parTuple2 :: Strategy a -> Strategy b -> Strategy (a, b)
parTuple3 :: Strategy a -> Strategy b -> Strategy c -> Strategy (a, b, c)
parTuple4 :: Strategy a -> Strategy b -> Strategy c -> Strategy d -> Strategy (a, b, c, d)
parTuple5 :: Strategy a -> Strategy b -> Strategy c -> Strategy d -> Strategy e -> Strategy (a, b, c, d, e)
parTuple6 :: Strategy a -> Strategy b -> Strategy c -> Strategy d -> Strategy e -> Strategy f -> Strategy (a, b, c, d, e, f)
parTuple7 :: Strategy a -> Strategy b -> Strategy c -> Strategy d -> Strategy e -> Strategy f -> Strategy g -> Strategy (a, b, c, d, e, f, g)
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)
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)

-- | Sequential function application. The argument is evaluated using the
--   given strategy before it is given to the function.
($|) :: (a -> b) -> Strategy a -> a -> b

-- | Parallel function application. The argument is evaluated using the
--   given strategy, in parallel with the function application.
($||) :: (a -> b) -> Strategy a -> a -> b

-- | 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)

-- | 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)

-- | 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)

-- | 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)

-- | <a>Eval</a> is a Monad that makes it easier to define parallel
--   strategies. It is a strict identity monad: that is, in
--   
--   <pre>
--   m &gt;&gt;= f
--   </pre>
--   
--   <tt>m</tt> is evaluated before the result is passed to <tt>f</tt>.
--   
--   <pre>
--   instance Monad Eval where
--     return  = Done
--     m &gt;&gt;= k = case m of
--                 Done x -&gt; k x
--   </pre>
--   
--   If you wanted to construct a <a>Strategy</a> for a pair that sparked
--   the first component in parallel and then evaluated the second
--   component, you could write
--   
--   <pre>
--   myStrat :: Strategy (a,b)
--   myStrat (a,b) = do { a' &lt;- rpar a; b' &lt;- rseq b; return (a',b') }
--   </pre>
--   
--   Alternatively, you could write this more compactly using the
--   Applicative style as
--   
--   <pre>
--   myStrat (a,b) = (,) &lt;$&gt; rpar a &lt;*&gt; rseq b
--   </pre>
data Eval a

-- | Pull the result out of the monad.
runEval :: Eval a -> a

-- | DEPRECCATED: replaced by the <a>Eval</a> monad

-- | <i>Deprecated: The Strategy type is now a -&gt; Eval a, not a -&gt;
--   Done</i>
type Done = ()

-- | DEPRECATED: Use <a>pseq</a> or <a>$|</a> instead

-- | <i>Deprecated: Use pseq or $| instead</i>
demanding :: a -> Done -> a

-- | DEPRECATED: Use <a>par</a> or <a>$||</a> instead

-- | <i>Deprecated: Use par or $|| instead</i>
sparking :: a -> Done -> a

-- | DEPRECATED: Use <a>pseq</a> or <a>$|</a> instead

-- | <i>Deprecated: Use pseq or $| instead</i>
(>|) :: Done -> Done -> Done

-- | DEPRECATED: Use <a>par</a> or <a>$||</a> instead

-- | <i>Deprecated: Use par or $|| instead</i>
(>||) :: Done -> Done -> Done

-- | DEPRECATED: renamed to <a>rseq</a>

-- | <i>Deprecated: renamed to rseq</i>
rwhnf :: Strategy a

-- | DEPRECATED: renamed to <a>runEval</a>

-- | <i>Deprecated: renamed to runEval</i>
unEval :: Eval a -> a

-- | DEPRECATED: renamed to <a>evalTraversable</a>

-- | <i>Deprecated: renamed to evalTraversable</i>
seqTraverse :: Traversable t => Strategy a -> Strategy (t a)

-- | DEPRECATED: renamed to <a>parTraversable</a>

-- | <i>Deprecated: renamed to parTraversable</i>
parTraverse :: Traversable t => Strategy a -> Strategy (t a)

-- | DEPRECATED: renamed to <a>evalList</a>

-- | <i>Deprecated: renamed to evalList</i>
seqList :: Strategy a -> Strategy [a]

-- | DEPRECATED: renamed to <a>evalTuple2</a>

-- | <i>Deprecated: renamed to evalTuple2</i>
seqPair :: Strategy a -> Strategy b -> Strategy (a, b)

-- | DEPRECATED: renamed to <a>parTuple2</a>

-- | <i>Deprecated: renamed to parTuple2</i>
parPair :: Strategy a -> Strategy b -> Strategy (a, b)

-- | DEPRECATED: renamed to <a>evalTuple3</a>

-- | <i>Deprecated: renamed to evalTuple3</i>
seqTriple :: Strategy a -> Strategy b -> Strategy c -> Strategy (a, b, c)

-- | DEPRECATED: renamed to <a>parTuple3</a>

-- | <i>Deprecated: renamed to parTuple3</i>
parTriple :: Strategy a -> Strategy b -> Strategy c -> Strategy (a, b, c)

-- | A class of types that can be fully evaluated.
class NFData a
instance GHC.Base.Functor Control.Parallel.Strategies.Eval
instance GHC.Base.Applicative Control.Parallel.Strategies.Eval
instance GHC.Base.Monad Control.Parallel.Strategies.Eval