libghc-monad-par-doc 0.3.4.8-3build3 / usr / share / doc / libghc-monad-par-doc / html / monad-par.txt

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


-- | A library for parallel programming based on a monad
--   
--   The <a>Par</a> monad offers a simple API for parallel programming. The
--   library works for parallelising both pure and <tt>IO</tt>
--   computations, although only the pure version is deterministic. The
--   default implementation provides a work-stealing scheduler and supports
--   forking tasks that are much lighter weight than IO-threads.
--   
--   For complete documentation see <a>Control.Monad.Par</a>.
--   
--   Some examples of use can be found in the <tt>examples/</tt> directory
--   of the source package.
--   
--   Other related packages:
--   
--   <ul>
--   <li><tt>abstract-par</tt> provides the type classes that abstract over
--   different implementations of the <tt>Par</tt> monad.</li>
--   <li><tt>monad-par-extras</tt> provides extra combinators and monad
--   transformers layered on top of the <tt>Par</tt> monad.</li>
--   </ul>
--   
--   Changes in 0.3.4 relative to 0.3:
--   
--   <ul>
--   <li>Fix bugs that cause "thread blocked indefinitely on MVar"
--   crashes.</li>
--   <li>Added <a>Control.Monad.Par.IO</a></li>
--   </ul>
@package monad-par
@version 0.3.4.8


-- | This module exposes the internals of the <tt>Par</tt> monad so that
--   you can build your own scheduler or other extensions. Do not use this
--   module for purposes other than extending the <tt>Par</tt> monad with
--   new functionality.
module Control.Monad.Par.Scheds.TraceInternal
data Trace
Get :: (IVar a) -> (a -> Trace) -> Trace
Put :: (IVar a) -> a -> Trace -> Trace
New :: (IVarContents a) -> (IVar a -> Trace) -> Trace
Fork :: Trace -> Trace -> Trace
Done :: Trace
Yield :: Trace -> Trace
LiftIO :: (IO a) -> (a -> Trace) -> Trace
data Sched
Sched :: {-# UNPACK #-} !Int -> IORef [Trace] -> IORef [MVar Bool] -> [Sched] -> Sched
[no] :: Sched -> {-# UNPACK #-} !Int
[workpool] :: Sched -> IORef [Trace]
[idle] :: Sched -> IORef [MVar Bool]
[scheds] :: Sched -> [Sched]
newtype Par a
Par :: ((a -> Trace) -> Trace) -> Par a
[runCont] :: Par a -> (a -> Trace) -> Trace
newtype IVar a
IVar :: (IORef (IVarContents a)) -> IVar a
data IVarContents a
Full :: a -> IVarContents a
Empty :: IVarContents a
Blocked :: [a -> Trace] -> IVarContents a

-- | The main scheduler loop.
sched :: Bool -> Sched -> Trace -> IO ()

-- | Run a parallel, deterministic computation and return its result.
--   
--   Note: you must NOT return an IVar in the output of the parallel
--   computation. This is unfortunately not enforced, as it is with
--   <tt>runST</tt> or with newer libraries that export a Par monad, such
--   as <tt>lvish</tt>.
runPar :: Par a -> a

-- | A version that avoids an internal <a>unsafePerformIO</a> for calling
--   contexts that are already in the <a>IO</a> monad.
--   
--   Returning any value containing IVar is still disallowed, as it can
--   compromise type safety.
runParIO :: Par a -> IO a

-- | An asynchronous version in which the main thread of control in a Par
--   computation can return while forked computations still run in the
--   background.
runParAsync :: Par a -> a

-- | Creates a new <tt>IVar</tt>
new :: Par (IVar a)

-- | Creates a new <tt>IVar</tt> that contains a value
newFull :: NFData a => a -> Par (IVar a)

-- | Creates a new <tt>IVar</tt> that contains a value (head-strict only)
newFull_ :: a -> Par (IVar a)

-- | Read the value in an <tt>IVar</tt>. The <a>get</a> operation can only
--   return when the value has been written by a prior or parallel
--   <tt>put</tt> to the same <tt>IVar</tt>.
get :: IVar a -> Par a

-- | Like <a>put</a>, but only head-strict rather than fully-strict.
put_ :: IVar a -> a -> Par ()

-- | Put a value into an <tt>IVar</tt>. Multiple <a>put</a>s to the same
--   <tt>IVar</tt> are not allowed, and result in a runtime error.
--   
--   <a>put</a> fully evaluates its argument, which therefore must be an
--   instance of <a>NFData</a>. The idea is that this forces the work to
--   happen when we expect it, rather than being passed to the consumer of
--   the <tt>IVar</tt> and performed later, which often results in less
--   parallelism than expected.
--   
--   Sometimes partial strictness is more appropriate: see <a>put_</a>.
put :: NFData a => IVar a -> a -> Par ()
pollIVar :: IVar a -> IO (Maybe a)

-- | Allows other parallel computations to progress. (should not be
--   necessary in most cases).
yield :: Par ()
instance GHC.Base.Functor Control.Monad.Par.Scheds.TraceInternal.Par
instance GHC.Base.Monad Control.Monad.Par.Scheds.TraceInternal.Par
instance GHC.Base.Applicative Control.Monad.Par.Scheds.TraceInternal.Par
instance GHC.Classes.Eq (Control.Monad.Par.Scheds.TraceInternal.IVar a)
instance Control.DeepSeq.NFData (Control.Monad.Par.Scheds.TraceInternal.IVar a)


-- | This is the scheduler described in the paper "A Monad for
--   Deterministic Parallelism". It is based on a lazy <tt>Trace</tt> data
--   structure that separates the scheduler from the <tt>Par</tt> monad
--   method implementations.
module Control.Monad.Par.Scheds.Trace
data Par a

-- | Run a parallel, deterministic computation and return its result.
--   
--   Note: you must NOT return an IVar in the output of the parallel
--   computation. This is unfortunately not enforced, as it is with
--   <tt>runST</tt> or with newer libraries that export a Par monad, such
--   as <tt>lvish</tt>.
runPar :: Par a -> a

-- | A version that avoids an internal <a>unsafePerformIO</a> for calling
--   contexts that are already in the <a>IO</a> monad.
--   
--   Returning any value containing IVar is still disallowed, as it can
--   compromise type safety.
runParIO :: Par a -> IO a
fork :: Par () -> Par ()
data IVar a

-- | Creates a new <tt>IVar</tt>
new :: Par (IVar a)

-- | Creates a new <tt>IVar</tt> that contains a value
newFull :: NFData a => a -> Par (IVar a)

-- | Creates a new <tt>IVar</tt> that contains a value (head-strict only)
newFull_ :: a -> Par (IVar a)

-- | Read the value in an <tt>IVar</tt>. The <a>get</a> operation can only
--   return when the value has been written by a prior or parallel
--   <tt>put</tt> to the same <tt>IVar</tt>.
get :: IVar a -> Par a

-- | Put a value into an <tt>IVar</tt>. Multiple <a>put</a>s to the same
--   <tt>IVar</tt> are not allowed, and result in a runtime error.
--   
--   <a>put</a> fully evaluates its argument, which therefore must be an
--   instance of <a>NFData</a>. The idea is that this forces the work to
--   happen when we expect it, rather than being passed to the consumer of
--   the <tt>IVar</tt> and performed later, which often results in less
--   parallelism than expected.
--   
--   Sometimes partial strictness is more appropriate: see <a>put_</a>.
put :: NFData a => IVar a -> a -> Par ()

-- | Like <a>put</a>, but only head-strict rather than fully-strict.
put_ :: IVar a -> a -> Par ()
spawn :: NFData a => Par a -> Par (IVar a)
spawn_ :: Par a -> Par (IVar a)
spawnP :: NFData a => a -> Par (IVar a)
instance Control.Monad.Par.Class.ParFuture Control.Monad.Par.Scheds.TraceInternal.IVar Control.Monad.Par.Scheds.TraceInternal.Par
instance Control.Monad.Par.Class.ParIVar Control.Monad.Par.Scheds.TraceInternal.IVar Control.Monad.Par.Scheds.TraceInternal.Par


-- | This scheduler uses sparks (par/pseq) directly, but only supplies the
--   <tt>Monad.Par.Class.ParFuture</tt> interface.
module Control.Monad.Par.Scheds.Sparks
data Par a
Done :: a -> Par a
data Future a
Future :: a -> Future a
runPar :: Par a -> a
get :: Future a -> Par a
spawn :: NFData a => Par a -> Par (Future a)
spawn_ :: Par a -> Par (Future a)
spawnP :: NFData a => a -> Par (Future a)
instance GHC.Base.Monad Control.Monad.Par.Scheds.Sparks.Par
instance Control.Monad.Par.Class.ParFuture Control.Monad.Par.Scheds.Sparks.Future Control.Monad.Par.Scheds.Sparks.Par
instance GHC.Base.Functor Control.Monad.Par.Scheds.Sparks.Par
instance GHC.Base.Applicative Control.Monad.Par.Scheds.Sparks.Par


-- | A scheduler for the Par monad based on directly performing IO actions
--   when Par methods are called (i.e. without using a lazy trace data
--   structure).
module Control.Monad.Par.Scheds.Direct
data Sched
Sched :: {-# UNPACK #-} !Int -> WSDeque (Par ()) -> HotVar GenIO -> Bool -> HotVar [Session] -> HotVar [MVar Bool] -> [Sched] -> HotVar (Set SessionID) -> HotVar SessionID -> Sched
[no] :: Sched -> {-# UNPACK #-} !Int
[workpool] :: Sched -> WSDeque (Par ())
[rng] :: Sched -> HotVar GenIO
[isMain] :: Sched -> Bool
[sessions] :: Sched -> HotVar [Session]
[idle] :: Sched -> HotVar [MVar Bool]
[scheds] :: Sched -> [Sched]
[activeSessions] :: Sched -> HotVar (Set SessionID)
[sessionCounter] :: Sched -> HotVar SessionID
data Par a
newtype IVar a
IVar :: (IORef (IVarContents a)) -> IVar a
data IVarContents a
Full :: a -> IVarContents a
Empty :: IVarContents a
Blocked :: [a -> IO ()] -> IVarContents a
runPar :: Par a -> a
runParIO :: Par a -> IO a

-- | Creates a new <tt>IVar</tt>
new :: Par (IVar a)

-- | Read the value in an <tt>IVar</tt>. The <a>get</a> operation can only
--   return when the value has been written by a prior or parallel
--   <tt>put</tt> to the same <tt>IVar</tt>.
get :: IVar a -> Par a

-- | <tt>put_</tt> is a version of <tt>put</tt> that is head-strict rather
--   than fully-strict. In this scheduler, puts immediately execute woken
--   work in the current thread.
put_ :: IVar a -> a -> Par ()
fork :: Par () -> Par ()
newFull :: NFData a => a -> Par (IVar a)
newFull_ :: a -> Par (IVar a)
put :: NFData a => IVar a -> a -> Par ()
spawn :: NFData a => Par a -> Par (IVar a)
spawn_ :: Par a -> Par (IVar a)
spawnP :: NFData a => a -> Par (IVar a)
spawn1_ :: (a -> Par b) -> a -> Par (IVar b)
instance Control.DeepSeq.NFData (Control.Monad.Par.Scheds.Direct.IVar a)
instance Control.Monad.Par.Class.ParFuture Control.Monad.Par.Scheds.Direct.IVar Control.Monad.Par.Scheds.DirectInternal.Par
instance Control.Monad.Par.Class.ParIVar Control.Monad.Par.Scheds.Direct.IVar Control.Monad.Par.Scheds.DirectInternal.Par
instance Control.Monad.Par.Unsafe.ParUnsafe Control.Monad.Par.Scheds.Direct.IVar Control.Monad.Par.Scheds.DirectInternal.Par


-- | This module is an alternative version of <a>Control.Monad.Par</a> in
--   which the <a>Par</a> type provides <a>IO</a> operations, by means of
--   <a>liftIO</a>. The price paid is that only <a>runParIO</a> is
--   available, not the pure <tt>runPar</tt>.
--   
--   This module uses the same default scheduler as
--   <a>Control.Monad.Par</a>.
module Control.Monad.Par.IO

-- | A wrapper around an underlying Par type which allows IO.
data ParIO a
data IVar a

-- | A run method which allows actual IO to occur on top of the Par monad.
--   Of course this means that all the normal problems of parallel IO
--   computations are present, including nondeterminsm.
--   
--   A simple example program:
--   
--   <pre>
--   runParIO (liftIO $ putStrLn "hi" :: ParIO ())
--   </pre>
runParIO :: ParIO a -> IO a
instance Control.Monad.Par.Class.ParIVar Control.Monad.Par.Scheds.TraceInternal.IVar Control.Monad.Par.IO.ParIO
instance Control.Monad.Par.Class.ParFuture Control.Monad.Par.Scheds.TraceInternal.IVar Control.Monad.Par.IO.ParIO
instance GHC.Base.Monad Control.Monad.Par.IO.ParIO
instance GHC.Base.Applicative Control.Monad.Par.IO.ParIO
instance GHC.Base.Functor Control.Monad.Par.IO.ParIO
instance Control.Monad.IO.Class.MonadIO Control.Monad.Par.IO.ParIO


-- | The <tt>monad-par</tt> package provides a family of <tt>Par</tt>
--   monads, for speeding up pure computations using parallel processors.
--   (for a similar programming model for use with <tt>IO</tt>, see
--   <a>Control.Monad.Par.IO</a>.)
--   
--   The result of a given <tt>Par</tt> computation is always the same -
--   i.e. it is deterministic, but the computation may be performed more
--   quickly if there are processors available to share the work.
--   
--   For example, the following program fragment computes the values of
--   <tt>(f x)</tt> and <tt>(g x)</tt> in parallel, and returns a pair of
--   their results:
--   
--   <pre>
--   runPar $ do
--       fx &lt;- spawnP (f x)  -- start evaluating (f x)
--       gx &lt;- spawnP (g x)  -- start evaluating (g x)
--       a  &lt;- get fx        -- wait for fx
--       b  &lt;- get gx        -- wait for gx
--       return (a,b)        -- return results
--   </pre>
--   
--   <tt>Par</tt> can be used for specifying pure parallel computations in
--   which the order of the computation is not known beforehand. The
--   programmer specifies how information flows from one part of the
--   computation to another, but not the order in which computations will
--   be evaluated at runtime. Information flow is described using
--   "variables" called <tt>IVar</tt>s, which support <a>put</a> and
--   <a>get</a> operations. For example, suppose you have a problem that
--   can be expressed as a network with four nodes, where <tt>b</tt> and
--   <tt>c</tt> require the value of <tt>a</tt>, and <tt>d</tt> requires
--   the value of <tt>b</tt> and <tt>c</tt>:
--   
--   <pre>
--     a
--    / \               
--   b   c             
--    \ /  
--     d
--   </pre>
--   
--   Then you could express this in the <tt>Par</tt> monad like this:
--   
--   <pre>
--   runPar $ do
--       [a,b,c,d] &lt;- sequence [new,new,new,new]
--       fork $ do x &lt;- get a; put b (x+1)
--       fork $ do x &lt;- get a; put c (x+2)
--       fork $ do x &lt;- get b; y &lt;- get c; put d (x+y)
--       fork $ do put a (3 :: Int)
--       get d
--   </pre>
--   
--   The result of the above computation is always 9. The <a>get</a>
--   operation waits until its input is available; multiple <a>put</a>s to
--   the same <tt>IVar</tt> are not allowed, and result in a runtime error.
--   Values stored in <tt>IVar</tt>s are usually fully evaluated (although
--   there are ways provided to pass lazy values if necessary).
--   
--   In the above example, <tt>b</tt> and <tt>c</tt> will be evaluated in
--   parallel. In practice the work involved at each node is too small here
--   to see the benefits of parallelism though: typically each node should
--   involve much more work. The granularity is completely under your
--   control - too small and the overhead of the <tt>Par</tt> monad will
--   outweigh any parallelism benefits, whereas if the nodes are too large
--   then there might not be enough parallelism to use all the available
--   processors.
--   
--   Unlike <tt>Control.Parallel</tt>, in <tt>Control.Monad.Par</tt>
--   parallelism is not combined with laziness, so sharing and granularity
--   are completely under the control of the programmer. New units of
--   parallel work are only created by <tt>fork</tt> and a few other
--   combinators.
--   
--   The default implementation is based on a work-stealing scheduler that
--   divides the work as evenly as possible between the available
--   processors at runtime. Other schedulers are available that are based
--   on different policies and have different performance characteristics.
--   To use one of these other schedulers, just import its module instead
--   of <a>Control.Monad.Par</a>:
--   
--   <ul>
--   <li><a>Control.Monad.Par.Scheds.Trace</a></li>
--   <li><a>Control.Monad.Par.Scheds.Sparks</a></li>
--   </ul>
--   
--   For more information on the programming model, please see these
--   sources:
--   
--   <ul>
--   <li>The wiki/tutorial
--   (<a>http://www.haskell.org/haskellwiki/Par_Monad:_A_Parallelism_Tutorial</a>)</li>
--   <li>The original paper
--   (<a>http://www.cs.indiana.edu/~rrnewton/papers/haskell2011_monad-par.pdf</a>)</li>
--   <li>Tutorial slides
--   (<a>http://community.haskell.org/~simonmar/slides/CUFP.pdf</a>)</li>
--   <li>Other slides:
--   (<a>http://www.cs.ox.ac.uk/ralf.hinze/WG2.8/28/slides/simon.pdf</a>,
--   <a>http://www.cs.indiana.edu/~rrnewton/talks/2011_HaskellSymposium_ParMonad.pdf</a>)</li>
--   </ul>
module Control.Monad.Par
data Par a

-- | Run a parallel, deterministic computation and return its result.
--   
--   Note: you must NOT return an IVar in the output of the parallel
--   computation. This is unfortunately not enforced, as it is with
--   <tt>runST</tt> or with newer libraries that export a Par monad, such
--   as <tt>lvish</tt>.
runPar :: Par a -> a

-- | A version that avoids an internal <a>unsafePerformIO</a> for calling
--   contexts that are already in the <a>IO</a> monad.
--   
--   Returning any value containing IVar is still disallowed, as it can
--   compromise type safety.
runParIO :: Par a -> IO a
fork :: Par () -> Par ()
data IVar a

-- | Creates a new <tt>IVar</tt>
new :: Par (IVar a)

-- | Creates a new <tt>IVar</tt> that contains a value
newFull :: NFData a => a -> Par (IVar a)

-- | Creates a new <tt>IVar</tt> that contains a value (head-strict only)
newFull_ :: a -> Par (IVar a)

-- | Read the value in an <tt>IVar</tt>. The <a>get</a> operation can only
--   return when the value has been written by a prior or parallel
--   <tt>put</tt> to the same <tt>IVar</tt>.
get :: IVar a -> Par a

-- | Put a value into an <tt>IVar</tt>. Multiple <a>put</a>s to the same
--   <tt>IVar</tt> are not allowed, and result in a runtime error.
--   
--   <a>put</a> fully evaluates its argument, which therefore must be an
--   instance of <a>NFData</a>. The idea is that this forces the work to
--   happen when we expect it, rather than being passed to the consumer of
--   the <tt>IVar</tt> and performed later, which often results in less
--   parallelism than expected.
--   
--   Sometimes partial strictness is more appropriate: see <a>put_</a>.
put :: NFData a => IVar a -> a -> Par ()

-- | Like <a>put</a>, but only head-strict rather than fully-strict.
put_ :: IVar a -> a -> Par ()
spawn :: NFData a => Par a -> Par (IVar a)
spawn_ :: Par a -> Par (IVar a)
spawnP :: NFData a => a -> Par (IVar a)

-- | A class of types that can be fully evaluated.
class NFData a