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


-- | A Library for Writing Multi-Pass Algorithms.
--   
--   The MultiPass library supports a monadic programming idiom in which
--   multi-pass algorithms are written in a single-pass style.
@package Control-Monad-MultiPass
@version 0.1.0.0


-- | This module implements the core functions, datatypes, and classes of
--   the MultiPass library. Its export list is divided into two halves. The
--   first half contains the declarations which are relevant to anyone who
--   wants to use the MultiPass library. The second contains which are only
--   relevant to people who want to implement new instruments.
module Control.Monad.MultiPass

-- | This monad is used to implement the body of a multi-pass algorithm.
data MultiPass r w tc a

-- | This monad is used to implement the prologue of a multi-pass
--   algorithm.
data MultiPassPrologue r w tc a

-- | This monad is used to implement the epilogue of a multi-pass
--   algorithm.
data MultiPassEpilogue r w tc a

-- | <a>MultiPassMain</a> is an abstract datatype containing the prologue,
--   body, and epilogue of a multi-pass algorithm. Use
--   <a>mkMultiPassMain</a> to construct an object of type
--   <a>MultiPassMain</a>.
data MultiPassMain r w tc c

-- | Combine the prologue, body, and epilogue of a multi-pass algorithm to
--   create the <a>MultiPassMain</a> object which is required by the
--   <a>run</a> function.
mkMultiPassMain :: MultiPassPrologue r w tc a -> (a -> MultiPass r w tc b) -> (b -> MultiPassEpilogue r w tc c) -> MultiPassMain r w tc c

-- | This datatype is used in conjunction with <a>PassZ</a> to package the
--   main function of the multi-pass algorithm. For an example of how they
--   are used, see the implementation of <a>repminMP</a> or any of the
--   other examples in the Example directory.
newtype PassS cont m
PassS :: (forall p. Monad p => cont (m p)) -> PassS cont m

-- | Used in conjunction with <a>PassS</a> to build a Peano number
--   corresponding to the number of passes.
newtype PassZ f
PassZ :: (forall (tc :: *). f tc) -> PassZ f

-- | The main function of a multi-pass algorithm needs to be wrapped in a
--   newtype so that it can be packaged with <a>PassS</a> and <a>PassZ</a>.
--   The newtype needs to be made an instance of <a>MultiPassAlgorithm</a>
--   so that it can unwrapped by the implementation.
class MultiPassAlgorithm a b | a -> b
unwrapMultiPassAlgorithm :: MultiPassAlgorithm a b => a -> b

-- | This function is used to run a multi-pass algorithm. Its complicated
--   type is mostly an artifact of the internal implementation, which uses
--   type classes to generate the code for each pass of the algorithm.
--   Therefore, the recommended way to learn how to use <a>run</a> is to
--   look at some of the examples in the <tt>Example</tt> sub-directory.
run :: (InstantiatePasses f f', MultiPassAlgorithm (f' tc) g, ApplyArgs r w g tc gc tc gc tc (MultiPassMain r w tc (Off out)), InitCtx tc, InitCtx gc, RunPasses r w f tc gc Off out) => f -> ST2 r w out

-- | <a>NumThreads</a> is used to specify the number of threads in
--   <a>parallelMP</a> and <a>parallelMP_</a>.
newtype NumThreads
NumThreads :: Int -> NumThreads

-- | Use <tt>m</tt> threads to run <tt>n</tt> instances of the function
--   <tt>f</tt>. The results are returned in an array of length <tt>n</tt>.
parallelMP :: (Ix i, Num i) => NumThreads -> (i, i) -> (i -> MultiPass r w tc a) -> MultiPass r w tc (ST2Array r w i a)

-- | Modified version of <a>parallelMP</a> which discards the result of the
--   function, rather than writing it to an array.
parallelMP_ :: (Ix i, Num i) => NumThreads -> (i, i) -> (i -> MultiPass r w tc a) -> MultiPass r w tc ()

-- | Read-only ST2 computations are allowed to be executed in the MultiPass
--   monad.
readOnlyST2ToMP :: (forall w. ST2 r w a) -> MultiPass r w' tc a

-- | Trivial monad, equivalent to <a>Identity</a>. Used to switch on a pass
--   of a multi-pass algorithm.
newtype On a
On :: a -> On a

-- | Trivial monad which computes absolutely nothing. It is used to switch
--   off a pass of a multi-pass algorithm.
data Off (a :: *)
Off :: Off

-- | <a>MultiPass</a>, <a>MultiPassPrologue</a>, and
--   <a>MultiPassEpilogue</a> are trivial newtype wrappers around this
--   monad. Instruments can construct computations in the
--   <a>MultiPassBase</a> monad, but then use <a>mkMultiPass</a>,
--   <a>mkMultiPassPrologue</a>, and <a>mkMultiPassEpilogue</a> to restrict
--   which of the three stages it is allowed to be used in.
data MultiPassBase r w tc a

-- | Restrict a computation so that it can only be executed during the body
--   of the algorithm (not the prologue or epilogue).
mkMultiPass :: MultiPassBase r w tc a -> MultiPass r w tc a

-- | Restrict a computation so that it can only be executed during the
--   prologue.
mkMultiPassPrologue :: MultiPassBase r w tc a -> MultiPassPrologue r w tc a

-- | Restrict a computation so that it can only be executed during the
--   epilogue.
mkMultiPassEpilogue :: MultiPassBase r w tc a -> MultiPassEpilogue r w tc a

-- | This abstract datatype is used as the result type of createInstrument.
--   Instrument authors can create it using the <a>wrapInstrument</a>
--   function, but cannot unwrap it. This ensures that instruments can only
--   be constructed by the <a>Control.Monad.MultiPass</a> library.
data WrapInstrument instr

-- | Create an object of type <a>WrapInstrument</a>. It is needed when
--   defining a new instance of the <a>Instrument</a> class.
wrapInstrument :: instr -> WrapInstrument instr

-- | This datatype is used by the back-tracking mechanism. Instruments can
--   request that the evaluator back-tracks to a specific pass number.
--   Instruments which use back-tracking store the relevant PassNumbers in
--   their global context. The current <a>PassNumber</a> is the first
--   argument of <a>nextGlobalContext</a> for this purpose.
--   <a>PassNumber</a> is an abstract datatype. Instruments should never
--   need to create a new <a>PassNumber</a> or modify an existing one, so
--   no functions that operate on <a>PassNumber</a> are exported from this
--   module.
data PassNumber

-- | This datatype is used by the <a>NextThreadContext</a> and
--   <a>NextGlobalContext</a> classes to specify whether the algorithm is
--   progressing to the next pass or back-tracking to a previous pass. When
--   back-tracking occurs, the current thread and global contexts are first
--   passed the <a>StepReset</a> command. Then they are passed the
--   <a>StepBackward</a> command <tt>N</tt> times, where <tt>N</tt> is the
--   number of passes that need to be revisited. Note that <tt>N</tt> can
--   be zero if only the current pass needs to be revisited, so the
--   <a>StepBackward</a> command may not be used. This is the reason why
--   the <a>StepReset</a> command is always issued first.
data StepDirection
StepForward :: StepDirection
StepReset :: StepDirection
StepBackward :: StepDirection

-- | The type of the first argument of <a>createInstrument</a>. It enables
--   instruments to run <a>ST2</a> in the <a>MultiPassBase</a> monad.
--   (Clearly the <tt>st2ToMP</tt> argument needs to be used with care.)
type ST2ToMP tc = forall r w a. ST2 r w a -> MultiPassBase r w tc a

-- | The type of the first argument of <a>createInstrument</a>. It used to
--   read and write the thread context.
type UpdateThreadContext tc tc' = forall r w. (tc' -> tc') -> MultiPassBase r w tc tc'

-- | Every instrument must define an instance of this class for each of its
--   passes. For example, the <a>Counter</a> instrument defines the
--   following instances:
--   
--   <pre>
--   instance Instrument tc () () () (Counter i r w Off Off tc)
--   
--   instance Num i =&gt;
--            Instrument tc (CounterTC1 i r) () (Counter i r w On Off tc)
--   
--   instance Num i =&gt;
--            Instrument tc (CounterTC2 i r) () (Counter i r w On On tc)
--   </pre>
--   
--   The functional dependency from <tt>instr</tt> to <tt>tc</tt> and
--   <tt>gc</tt> enables the <a>run</a> function to automatically deduce
--   the type of the thread context and global context for each pass.
class Instrument rootTC tc gc instr | instr -> tc gc
createInstrument :: Instrument rootTC tc gc instr => ST2ToMP rootTC -> UpdateThreadContext rootTC tc -> gc -> WrapInstrument instr

-- | This class is used when multiple threads are spawned.
--   <a>splitThreadContext</a> is used to create a new thread context for
--   each of the new threads and <a>mergeThreadContext</a> is used to merge
--   them back together when the parallel region ends.
class ThreadContext r w tc
splitThreadContext :: ThreadContext r w tc => Int -> Int -> tc -> ST2 r w tc
mergeThreadContext :: ThreadContext r w tc => Int -> (Int -> ST2 r w tc) -> tc -> ST2 r w tc

-- | This class is used to create the next thread context when the
--   multi-pass algorithm proceeds to the next pass or back-tracks to the
--   previous pass.
class NextThreadContext r w tc gc tc'
nextThreadContext :: NextThreadContext r w tc gc tc' => PassNumber -> StepDirection -> tc -> gc -> ST2 r w tc'

-- | This class is used to create the next global context when the
--   multi-pass algorithm proceeds to the next pass or back-tracks to the
--   previous pass.
class NextGlobalContext r w tc gc gc'
nextGlobalContext :: NextGlobalContext r w tc gc gc' => PassNumber -> StepDirection -> tc -> gc -> ST2 r w gc'

-- | Every instrument must define an instance of this class for each of its
--   passes. It is used to tell the evaluator whether it needs to
--   back-track. Instruments which do not back-track should use the default
--   implementation of backtrack which returns <a>Nothing</a> (which means
--   that no back-tracking is necessary.) If more than one instrument
--   requests that the evaluator back-tracks then the evaluator will
--   back-track to the earliest of the requested passes.
class BackTrack r w tc gc where backtrack _ _ = return Nothing
backtrack :: BackTrack r w tc gc => tc -> gc -> ST2 r w (Maybe PassNumber)
instance [safe] Functor On
instance [safe] Functor Off
instance [safe] Eq StepDirection
instance [safe] Functor (MultiPassBase r w tc)
instance [safe] Functor (MultiPassEpilogue r w tc)
instance [safe] Functor (MultiPassPrologue r w tc)
instance [safe] Functor (MultiPass r w tc)
instance [safe] Functor WrapInstrument
instance [safe] (InstantiatePasses (cont (f Off)) fPrev, MultiPassAlgorithm (fPrev tc0) gPrev, InstantiatePasses (cont (f On)) fCurr, MultiPassAlgorithm (fCurr tc1) gCurr, ApplyArgs r w gCurr tc0 gc0 tc1 gc1 tc1 (MultiPassMain r w tc1 (p out)), ApplyArgs r w gCurr tc1 gc1 tc1 gc1 tc1 (MultiPassMain r w tc1 (p out)), ApplyArgs r w gPrev tc1 gc1 tc0 gc0 tc0 (MultiPassMain r w tc0 (q out)), ThreadContext r w tc1, BackTrack r w tc1 gc1, RunPasses r w (cont (f On)) tc1 gc1 p out) => RunPasses r w (PassS k cont f) tc0 gc0 q out
instance [safe] RunPasses r w (PassZ f) tc gc On out
instance [safe] (BackTrack r w tc gc, BackTrack r w tcs gcs) => BackTrack r w (ArgCons tc tcs) (ArgCons gc gcs)
instance [safe] BackTrack r w ArgNil ArgNil
instance [safe] BackTrack r w tc ()
instance [safe] InstantiatePasses (cont (m Off)) b => InstantiatePasses (PassS k cont m) b
instance [safe] InstantiatePasses (PassZ a) a
instance [safe] (NextGlobalContext r w tc x x', NextGlobalContext r w tc y y') => NextGlobalContext r w tc (Either x y) (Either x' y')
instance [safe] (NextGlobalContext r w tc x x', NextGlobalContext r w tc y y', NextGlobalContext r w tc z z') => NextGlobalContext r w tc (x, y, z) (x', y', z')
instance [safe] (NextGlobalContext r w tc x x', NextGlobalContext r w tc y y') => NextGlobalContext r w tc (x, y) (x', y')
instance [safe] NextGlobalContext r w tc gc ()
instance [safe] (NextThreadContext r w x gc x', NextThreadContext r w y gc y') => NextThreadContext r w (Either x y) gc (Either x' y')
instance [safe] (NextThreadContext r w () gc x, NextThreadContext r w () gc y, NextThreadContext r w () gc z) => NextThreadContext r w () gc (x, y, z)
instance [safe] (NextThreadContext r w x gc x', NextThreadContext r w y gc y', NextThreadContext r w z gc z') => NextThreadContext r w (x, y, z) gc (x', y', z')
instance [safe] (NextThreadContext r w () gc x, NextThreadContext r w () gc y) => NextThreadContext r w () gc (x, y)
instance [safe] (NextThreadContext r w x gc x', NextThreadContext r w y gc y') => NextThreadContext r w (x, y) gc (x', y')
instance [safe] NextThreadContext r w tc gc ()
instance [safe] (InitCtx a, InitCtx b) => InitCtx (ArgCons a b)
instance [safe] InitCtx ArgNil
instance [safe] InitCtx ()
instance [safe] ApplyArgs r w (MultiPassMain r w rootTC a) ArgNil ArgNil ArgNil ArgNil rootTC (MultiPassMain r w rootTC a)
instance [safe] ApplyArg r w param instr f oldTC oldGC tc gc rootTC f' => ApplyArgs r w (Param param (instr -> f)) oldTC oldGC tc gc rootTC f'
instance [safe] ApplyArg r w () instr f oldTC oldGC tc gc rootTC f' => ApplyArgs r w (instr -> f) oldTC oldGC tc gc rootTC f'
instance [safe] (ApplyArgs r w f oldTCs oldGCs tcs gcs rootTC f', NextThreadContext r w oldTC oldGC tc, NextGlobalContext r w oldTC oldGC gc, Instrument rootTC tc gc instr) => ApplyArg r w param instr f (ArgCons oldTC oldTCs) (ArgCons oldGC oldGCs) (ArgCons tc tcs) (ArgCons gc gcs) rootTC f'
instance [safe] Monad WrapInstrument
instance [safe] (ThreadContext r w x, ThreadContext r w y) => ThreadContext r w (Either x y)
instance [safe] (ThreadContext r w x, ThreadContext r w y, ThreadContext r w z) => ThreadContext r w (x, y, z)
instance [safe] (ThreadContext r w x, ThreadContext r w y) => ThreadContext r w (x, y)
instance [safe] (ThreadContext r w x, ThreadContext r w y) => ThreadContext r w (ArgCons x y)
instance [safe] ThreadContext r w ArgNil
instance [safe] ThreadContext r w ()
instance [safe] Monad (MultiPassEpilogue r w tc)
instance [safe] Monad (MultiPassPrologue r w tc)
instance [safe] Monad (MultiPass r w tc)
instance [safe] Monad (MultiPassBase r w tc)
instance [safe] Monad Off
instance [safe] Monad On


-- | Utility functions for the <a>Control.Monad.MultiPass</a> library.
module Control.Monad.MultiPass.Utils

-- | This function provides a similar interface to <a>mapM</a>, but is
--   specifically for mapping over the <a>ST2Array</a> datatype in the
--   <a>MultiPass</a> monad.
mapST2ArrayMP :: (Ix i, Num i) => NumThreads -> ST2Array r w i a -> (a -> MultiPass r w tc b) -> MultiPass r w tc (ST2Array r w i b)

-- | This function provides a similar interface to <a>mapM_</a>, but is
--   specifically for mapping over the <a>ST2Array</a> datatype in the
--   <a>MultiPass</a> monad.
mapST2ArrayMP_ :: (Ix i, Num i) => NumThreads -> ST2Array r w i a -> (a -> MultiPass r w tc b) -> MultiPass r w tc ()

-- | This function provides a similar interface to <a>mapM</a>, but is
--   useful for mapping over a datatype in a specific pass of the
--   <a>MultiPass</a> monad. Note: the <tt>m</tt> type is usually the
--   <a>MultiPass</a> monad, but the implementation does not specifically
--   depend on anything from the <a>Control.Monad.MultiPass</a> library, so
--   its type is more general.
pmapM :: (Traversable t, Monad m, Monad p) => t a -> (a -> m (p b)) -> m (p (t b))


-- | For every new instrument, a number of class instances need to be
--   defined, such as <a>NextGlobalContext</a> and
--   <a>NextThreadContext</a>. The tests in this module are used to check
--   that all the necessary instances have been defined. Each test defines
--   a trivial algorithm, parameterised by an instrument of a specific
--   arity. For example, <a>testInstrument3</a> is parameterised by a
--   three-pass instrument. The test is used as follows:
--   
--   <pre>
--   instanceTest :: ST2 r w ()
--   instanceTest = run instanceTestBody
--   
--   instanceTestBody :: TestInstrument3 (MyInstrument r w) r w
--   instanceTestBody = testInstrument3
--   </pre>
--   
--   If this code does not cause any compiler errors, then all the
--   necessary instances have been defined for <tt>MyInstrument</tt>.
module Control.Monad.MultiPass.Utils.InstanceTest

-- | Test function for a one-pass instrument.
testInstrument1 :: TestInstrument1 f r w

-- | Test type for a one-pass instrument.
type TestInstrument1 f r w = PassS (PassS (PassS PassZ)) (WrappedType1 f r w)

-- | Test function for a two-pass instrument.
testInstrument2 :: TestInstrument2 f r w

-- | Test type for a two-pass instrument.
type TestInstrument2 f r w = PassS (PassS (PassS (PassS PassZ))) (WrappedType2 f r w)

-- | Test function for a three-pass instrument.
testInstrument3 :: TestInstrument3 f r w

-- | Test type for a three-pass instrument.
type TestInstrument3 f r w = PassS (PassS (PassS (PassS (PassS (PassS PassZ))))) (WrappedType3 f r w)

-- | Test function for a four-pass instrument.
testInstrument4 :: TestInstrument4 f r w

-- | Test type for a four-pass instrument.
type TestInstrument4 f r w = PassS (PassS (PassS (PassS (PassS (PassS (PassS (PassS PassZ))))))) (WrappedType4 f r w)
instance [safe] MultiPassAlgorithm (WrappedType4 f r w p1 p2 p3 p4 p5 p6 p7 p8 tc) (UnwrappedType4 f r w p1 p2 p3 p4 p5 p6 p7 p8 tc)
instance [safe] MultiPassAlgorithm (WrappedType3 f r w p1 p2 p3 p4 p5 p6 tc) (UnwrappedType3 f r w p1 p2 p3 p4 p5 p6 tc)
instance [safe] MultiPassAlgorithm (WrappedType2 f r w p1 p2 p3 p4 tc) (UnwrappedType2 f r w p1 p2 p3 p4 tc)
instance [safe] MultiPassAlgorithm (WrappedType1 f r w p1 p2 p3 tc) (UnwrappedType1 f r w p1 p2 p3 tc)


-- | Utility functions for working with the <a>UpdateThreadContext</a>
--   argument of <a>createInstrument</a>. This module is only relevant for
--   Instrument authoring.
module Control.Monad.MultiPass.Utils.UpdateCtx

-- | If the thread context is a pair then <a>updateCtxFst</a> creates a new
--   <a>UpdateThreadContext</a> function which can be used to update the
--   first element of the pair.
updateCtxFst :: UpdateThreadContext rootTC (x, y) -> UpdateThreadContext rootTC x

-- | If the thread context is a pair then <a>updateCtxSnd</a> creates a new
--   <a>UpdateThreadContext</a> function which can be used to update the
--   second element of the pair.
updateCtxSnd :: UpdateThreadContext rootTC (x, y) -> UpdateThreadContext rootTC y

-- | If the thread context is an Either of two thread contexts then
--   <a>updateCtxLeft</a> creates a new <a>UpdateThreadContext</a> function
--   which can be used to update the <a>Left</a> element. This function
--   will assert if the thread context is a <a>Right</a> element.
updateCtxLeft :: UpdateThreadContext rootTC (Either x y) -> UpdateThreadContext rootTC x

-- | If the thread context is an Either of two thread contexts then
--   <a>updateCtxRight</a> creates a new <a>UpdateThreadContext</a>
--   function which can be used to update the <a>Right</a> element. This
--   function will assert if the thread context is a <a>Left</a> element.
updateCtxRight :: UpdateThreadContext rootTC (Either x y) -> UpdateThreadContext rootTC y


-- | <a>CounterTC</a> defines a thread context which is used to generate a
--   series of unique consecutive numbers. It has two passes. The first
--   pass, <a>CounterTC1</a>, creates a log of the number of new values
--   that need to be generated in each thread. The second pass,
--   <a>CounterTC2</a>, uses the log to compute the correct starting value
--   for each thread, so that the threads appear to be incrementing a
--   single global counter, even though they are operating concurrently.
module Control.Monad.MultiPass.ThreadContext.CounterTC

-- | <a>CounterTC1</a> is used during the first pass. It builds up a log of
--   the parallel tasks that were spawned, which is used during the second
--   pass to generate a series of unique consecutive numbers.
data CounterTC1 i r

-- | Get the current value of the counter.
counterVal1 :: CounterTC1 i r -> i

-- | Increment the counter.
incrCounterTC1 :: Num i => CounterTC1 i r -> CounterTC1 i r

-- | Add <tt>k</tt> to the counter.
addkCounterTC1 :: Num i => i -> CounterTC1 i r -> CounterTC1 i r

-- | Create a new counter.
newCounterTC1 :: Num i => CounterTC1 i r

-- | <a>CounterTC2</a> is used during the second pass. It uses the log
--   which was computed by <a>CounterTC1</a> to generate a series of unique
--   consecutive numbers.
data CounterTC2 i r

-- | Get the current value of the counter.
counterVal2 :: CounterTC2 i r -> i

-- | Increment the counter.
incrCounterTC2 :: Num i => CounterTC2 i r -> CounterTC2 i r

-- | Add <tt>k</tt> to the counter.
addkCounterTC2 :: Num i => i -> CounterTC2 i r -> CounterTC2 i r

-- | Convert a <a>CounterTC1</a> to a <a>CounterTC2</a>.
newCounterTC2 :: Num i => CounterTC1 i r -> ST2 r w (CounterTC2 i r)

-- | Reset the counter to zero and rewind to the beginning of the log.
resetCounterTC2 :: Num i => CounterTC2 i r -> CounterTC2 i r
instance [safe] Num i => NextThreadContext r w (CounterTC2 i r) gc (CounterTC2 i r)
instance [safe] Num i => NextThreadContext r w (CounterTC2 i r) gc (CounterTC1 i r)
instance [safe] Num i => NextThreadContext r w (CounterTC1 i r) gc (CounterTC2 i r)
instance [safe] Num i => ThreadContext r w (CounterTC2 i r)
instance [safe] Num i => NextThreadContext r w (CounterTC1 i r) gc (CounterTC1 i r)
instance [safe] Num i => NextThreadContext r w () gc (CounterTC1 i r)
instance [safe] Num i => ThreadContext r w (CounterTC1 i r)


-- | <a>MonoidTC</a> defines a thread context which is used to gather
--   values from all the threads of the program. The values to be gathered
--   must be instances of the <a>Monoid</a> class.
module Control.Monad.MultiPass.ThreadContext.MonoidTC

-- | MonoidTC is a thread context which uses the Monoid interface to
--   combine the values from multiple threads. Instances of the Monoid
--   class are expected to be associative, so the value computed by
--   MonoidTC is invariant under changes to the number of threads that are
--   spawned.
newtype MonoidTC a
MonoidTC :: a -> MonoidTC a
unwrapMonoidTC :: MonoidTC a -> a
instance [safe] Monoid a => NextThreadContext r w tc gc (MonoidTC a)
instance [safe] Monoid a => ThreadContext r w (MonoidTC a)
instance [safe] Monoid a => Monoid (MonoidTC a)


-- | The <a>Counter</a> instrument is used to generate an increasing
--   sequence of integers. It is particularly useful when the program uses
--   parallelism, because the <a>Counter</a> instrument creates the
--   illusion of a single-threaded global counter. The first pass counts
--   how many unique integers each thread needs so that the integers can be
--   generated without the use of locks during the second pass.
module Control.Monad.MultiPass.Instrument.Counter

-- | Abstract datatype for the instrument.
data Counter i r w (p1 :: * -> *) p2 tc

-- | Get the current value of the counter.
peek :: (Num i, Monad p1, Monad p2) => Counter i r w p1 p2 tc -> MultiPass r w tc (p2 i)

-- | Add <tt>k</tt> to the counter.
addk :: (Num i, Monad p1, Monad p2) => Counter i r w p1 p2 tc -> p1 i -> MultiPass r w tc ()

-- | Increment the counter.
incr :: (Num i, Monad p1, Monad p2) => Counter i r w p1 p2 tc -> MultiPass r w tc ()

-- | Read and pre-increment the counter. For example, if the current value
--   is 17 then <a>preIncr</a> updates the value of the counter to 18 and
--   returns 18.
preIncr :: (Num i, Monad p1, Monad p2) => Counter i r w p1 p2 tc -> MultiPass r w tc (p2 i)

-- | Read and post-increment the counter. For example, if the current value
--   is 17 then <a>postIncr</a> updates the value of the counter to 18 and
--   returns 17.
postIncr :: (Num i, Monad p1, Monad p2) => Counter i r w p1 p2 tc -> MultiPass r w tc (p2 i)
instance [safe] Num i => Instrument tc (CounterTC2 i r) () (Counter i r w On On tc)
instance [safe] Num i => Instrument tc (CounterTC1 i r) () (Counter i r w On Off tc)
instance [safe] Instrument tc () () (Counter i r w Off Off tc)


-- | The <a>CreateST2Array</a> instrument is stateless and provides a
--   similar interface to <a>parallelMP</a>. The difference is that it
--   produces the new array in a specific pass.
module Control.Monad.MultiPass.Instrument.CreateST2Array

-- | Abstract datatype for the instrument.
data CreateST2Array r w p1 tc

-- | Create a new array during pass <tt>p1</tt>, using the initialisation
--   function to initialise the elements. The initialisation is done in
--   parallel, using the specified number of threads.
createST2Array :: (Ix i, Num i, Monad p1) => CreateST2Array r w p1 tc -> NumThreads -> (i, i) -> (i -> MultiPass r w tc (p1 a)) -> MultiPass r w tc (p1 (ST2Array r w i a))

-- | <a>pmapST2ArrayMP</a> is a simple application of
--   <a>createST2Array</a>. It provides a similar interface to
--   <a>mapST2ArrayMP</a>. The difference is that it only executes the map
--   operation once the specified pass is reached.
pmapST2ArrayMP :: (Ix i, Num i, Monad p1) => CreateST2Array r w p1 tc -> NumThreads -> ST2Array r w i a -> (a -> MultiPass r w tc (p1 b)) -> MultiPass r w tc (p1 (ST2Array r w i b))
instance [safe] Instrument tc () () (CreateST2Array r w On tc)
instance [safe] Instrument tc () () (CreateST2Array r w Off tc)


-- | The <a>Delay</a> instrument is stateless and its implementation is
--   trivial. Its purpose is to allow values which were computed in pass
--   <tt>p1</tt> to be used in pass <tt>p2</tt>.
module Control.Monad.MultiPass.Instrument.Delay

-- | Abstract datatype for the instrument.
data Delay p1 p2 (tc :: *)

-- | <a>delay</a> enables a value which was computed in pass <tt>p1</tt> to
--   be used in pass <tt>p2</tt>.
delay :: Delay p1 p2 tc -> p1 a -> p2 a
instance [safe] Instrument tc () () (Delay On On tc)
instance [safe] Instrument tc () () (Delay On Off tc)
instance [safe] Instrument tc () () (Delay Off Off tc)


-- | The <a>DelayedLift</a> instrument is stateless and provides a similar
--   interface to <a>readOnlyST2ToMP</a>. The difference is that it only
--   executes the read-only computation once the specified pass is reached.
module Control.Monad.MultiPass.Instrument.DelayedLift

-- | Abstract datatype for the instrument.
data DelayedLift r w p1 tc

-- | Execute the read-only computation during pass <tt>p1</tt>.
delayedLift :: Monad p1 => DelayedLift r w p1 tc -> p1 (ReadOnlyST2 r a) -> MultiPass r w tc (p1 a)

-- | <a>readST2ArrayMP</a> is a simple application of <a>delayedLift</a>.
--   It reads an index of the array during pass <tt>p1</tt>. This is
--   particularly useful if the array does not exist in earlier passes, for
--   example because it was created by the <a>CreateST2Array</a>
--   instrument.
readST2ArrayMP :: (Ix i, Monad p1) => DelayedLift r w p1 tc -> p1 (ST2Array r w i a) -> i -> MultiPass r w tc (p1 a)
instance [safe] Instrument tc () () (DelayedLift r w On tc)
instance [safe] Instrument tc () () (DelayedLift r w Off tc)


-- | The <a>EmitST2Array</a> instrument is used to emit a sequence of
--   values to an <a>ST2Array</a>. It has three passes. The first pass
--   counts the number of elements that will be written. The second pass is
--   optional: it enables the index values to be read before the actual
--   values have been written. (If this pass is not needed then the second
--   and third passes can be merged by coalescing the type variables for
--   the second and third passes: <tt>EmitST2Array p1 p2 p2</tt>.) The
--   third pass writes the values to the output array.
module Control.Monad.MultiPass.Instrument.EmitST2Array

-- | Abstract datatype for the instrument.
data EmitST2Array i a r w p1 p2 p3 tc

-- | Initialise the base index of the output array. This method is
--   optional: if it is not called then the base index defaults to zero.
setBaseIndex :: (Ix i, Num i, Monad p1, Monad p2, Monad p3) => EmitST2Array i a r w p1 p2 p3 tc -> p2 i -> MultiPassPrologue r w tc ()

-- | Write one element to the output array.
emit :: (Ix i, Num i, Monad p1, Monad p2, Monad p3) => EmitST2Array i a r w p1 p2 p3 tc -> p3 a -> MultiPass r w tc ()

-- | Write a list of elements to the output array. The length of the list
--   needs to be declared in the first pass so that the correct number of
--   elements can be allocated.
emitList :: (Ix i, Num i, Monad p1, Monad p2, Monad p3) => EmitST2Array i a r w p1 p2 p3 tc -> p1 Int -> p3 [a] -> MultiPass r w tc ()

-- | Get the current index in the output array.
getIndex :: (Ix i, Num i, Monad p1, Monad p2, Monad p3) => EmitST2Array i a r w p1 p2 p3 tc -> MultiPass r w' tc (p2 i)

-- | Get the output array.
getResult :: (Ix i, Num i, Monad p1, Monad p2, Monad p3) => EmitST2Array i a r w p1 p2 p3 tc -> MultiPassEpilogue r w tc (p3 (ST2Array r w i a))
instance [safe] NextGlobalContext r w (CounterTC2 i r) (GC3 r w i a) (GC2 r w i)
instance [safe] NextGlobalContext r w (CounterTC2 i r) (GC3 r w i a) (GC3 r w i a)
instance [safe] (Ix i, Num i) => NextGlobalContext r w (CounterTC2 i r) (GC2 r w i) (GC3 r w i a)
instance [safe] NextGlobalContext r w tc (GC2 r w i) (GC2 r w i)
instance [safe] (Ix i, Num i) => NextGlobalContext r w (CounterTC1 i r) (GC2 r w i) (GC3 r w i a)
instance [safe] Num i => NextGlobalContext r w tc () (GC2 r w i)
instance [safe] BackTrack r w (CounterTC2 i r) (GC3 r w i a)
instance [safe] BackTrack r w (CounterTC2 i r) (GC2 r w i)
instance [safe] (Ix i, Num i) => Instrument tc (CounterTC2 i r) (GC3 r w i a) (EmitST2Array i a r w On On On tc)
instance [safe] Num i => Instrument tc (CounterTC2 i r) (GC2 r w i) (EmitST2Array i a r w On On Off tc)
instance [safe] Num i => Instrument tc (CounterTC1 i r) () (EmitST2Array i a r w On Off Off tc)
instance [safe] Instrument tc () () (EmitST2Array i a r w Off Off Off tc)


-- | The <a>EmitST2ArrayFxp</a> instrument has an identical interface to
--   <a>EmitST2Array</a>. The only difference is that
--   <a>EmitST2ArrayFxp</a> includes support for back-tracking. The
--   <a>emitList</a> method of <a>EmitST2ArrayFxp</a> permits the list
--   argument to be longer than the lower bound which was specified during
--   the first pass. If it is then the algorithm will back-track to the
--   beginning of the second pass and iterate until a fixed point has been
--   reached.
module Control.Monad.MultiPass.Instrument.EmitST2ArrayFxp

-- | Abstract datatype for the instrument.
data EmitST2ArrayFxp i a r w p1 p2 p3 tc

-- | Initialise the base index of the output array. This method is
--   optional: if it is not called then the base index defaults to zero.
setBaseIndex :: (Ix i, Num i, Monad p1, Monad p2, Monad p3) => EmitST2ArrayFxp i a r w p1 p2 p3 tc -> p2 i -> MultiPassPrologue r w tc ()

-- | Write one element to the output array.
emit :: (Ix i, Num i, Monad p1, Monad p2, Monad p3) => EmitST2ArrayFxp i a r w p1 p2 p3 tc -> p3 a -> MultiPass r w tc ()

-- | Write a list of elements to the output array. The instrument uses
--   back-tracking to iterate until the length of the list has been
--   determined. It is the client's responsibility to ensure that any
--   operations which depend on the length of the list are monotonic so
--   that a fixed point will be found. The first argument is used to supply
--   a minimum length for the list (zero is always a valid input). It can
--   be used to shorten the time to convergence when a good lower bound is
--   known.
emitList :: (Ix i, Num i, Monad p1, Monad p2, Monad p3) => EmitST2ArrayFxp i a r w p1 p2 p3 tc -> p1 Int -> p3 [a] -> MultiPass r w tc ()

-- | Get the current index in the output array.
getIndex :: (Ix i, Num i, Monad p1, Monad p2, Monad p3) => EmitST2ArrayFxp i a r w p1 p2 p3 tc -> MultiPass r w' tc (p2 i)

-- | Get the output array.
getResult :: (Ix i, Num i, Monad p1, Monad p2, Monad p3) => EmitST2ArrayFxp i a r w p1 p2 p3 tc -> MultiPassEpilogue r w tc (p3 (ST2Array r w i a))
instance [safe] Eq ListIndex
instance [safe] Ord ListIndex
instance [safe] Ix ListIndex
instance [safe] NextThreadContext r w (TC3 i r) gc (TC2 i r)
instance [safe] Num i => NextThreadContext r w (TC2 i r) gc (TC3 i r)
instance [safe] NextGlobalContext r w (TC3 i r) (GC3 r w i a) (GC2 r w i)
instance [safe] (Ix i, Num i) => NextGlobalContext r w (TC3 i r) (GC3 r w i a) (GC3 r w i a)
instance [safe] (Ix i, Num i) => NextGlobalContext r w (TC2 i r) (GC2 r w i) (GC3 r w i a)
instance [safe] NextGlobalContext r w (TC2 i r) (GC2 r w i) (GC2 r w i)
instance [safe] Num i => NextGlobalContext r w (TC1 i r) () (GC2 r w i)
instance [safe] Num i => NextThreadContext r w (TC3 i r) gc (TC3 i r)
instance [safe] BackTrack r w (TC3 i r) (GC3 r w i a)
instance [safe] BackTrack r w (TC2 i r) (GC2 r w i)
instance [safe] (Ix i, Num i) => Instrument tc (TC3 i r) (GC3 r w i a) (EmitST2ArrayFxp i a r w On On On tc)
instance [safe] Num i => ThreadContext r w (TC3 i r)
instance [safe] (Ix i, Num i) => Instrument tc (TC2 i r) (GC2 r w i) (EmitST2ArrayFxp i a r w On On Off tc)
instance [safe] Num i => Instrument tc (TC1 i r) () (EmitST2ArrayFxp i a r w On Off Off tc)
instance [safe] Show ListIndex
instance [safe] Num ListIndex
instance [safe] Instrument tc () () (EmitST2ArrayFxp i a r w Off Off Off tc)


-- | The <a>Knot3</a> instrument is used for knot tying across passes. Knot
--   tying is a technique sometimes used in lazy functional programming, in
--   which the definition of a variable depends on its own value. The lazy
--   programming technique depends on an implicit two-pass ordering of the
--   computation. For example, the classic repmin program produces a pair
--   of outputs - a tree and an integer - and there is an implicit two-pass
--   ordering where the integer is computed during the first pass and the
--   tree during the second. The <a>Knot3</a> instrument allows the same
--   technique to be applied, but the ordering of the passes is managed
--   explicitly by the <a>Control.Monad.MultiPass</a> library, rather than
--   implicitly by lazy evalution.
module Control.Monad.MultiPass.Instrument.Knot3

-- | Abstract datatype for the instrument.
data Knot3 (a :: *) r w (p1 :: * -> *) p2 p3 tc

-- | Tie the knot for the supplied function.
knot3 :: (Monad p1, Monad p2, Monad p3) => Knot3 a r w p1 p2 p3 tc -> (p3 a -> MultiPass r w tc (p2 a, b)) -> MultiPass r w tc b
instance [safe] NextGlobalContext r w tc (Buffer r w a) (Buffer r w a)
instance [safe] NextGlobalContext r w (CounterTC1 Int r) () (Buffer r w a)
instance [safe] BackTrack r w tc (Buffer r w a)
instance [safe] Instrument tc (CounterTC2 Int r) (Buffer r w a) (Knot3 a r w On On On tc)
instance [safe] Instrument tc (CounterTC2 Int r) (Buffer r w a) (Knot3 a r w On On Off tc)
instance [safe] Instrument tc (CounterTC1 Int r) () (Knot3 a r w On Off Off tc)
instance [safe] Instrument tc () () (Knot3 a r w Off Off Off tc)


-- | The <a>Monoid2</a> instrument is used to accumulate a global value
--   during the first pass. During the second pass, the global value can be
--   read but not written. The value must be an instance of the
--   <a>Monoid</a> class. The names of the methods, <a>tell</a> and
--   <a>listen</a>, are taken from the <a>MonadWriter</a> class. If this
--   causes a naming conflict, then this module should be imported
--   qualified. For example:
--   
--   <pre>
--   import qualified Control.Monad.MultiPass.Instrument.Monoid2 as M
--   </pre>
module Control.Monad.MultiPass.Instrument.Monoid2

-- | Abstract datatype for the instrument.
data Monoid2 a r w p1 p2 tc

-- | Add a value to the global value, during the first pass.
tell :: (Monoid a, Monad p1, Monad p2) => Monoid2 a r w p1 p2 tc -> p1 a -> MultiPass r w tc ()

-- | Read the global value, during the second pass.
listen :: (Monoid a, Monad p1, Monad p2) => Monoid2 a r w p1 p2 tc -> MultiPass r w tc (p2 a)

-- | Add a value to the global value, during the prologue of the first
--   pass.
tellPrologue :: (Monoid a, Monad p1, Monad p2) => Monoid2 a r w p1 p2 tc -> p1 a -> MultiPassPrologue r w tc ()

-- | Read the global value, during the epilogue of the first pass.
listenEpilogue :: (Monoid a, Monad p1, Monad p2) => Monoid2 a r w p1 p2 tc -> MultiPassEpilogue r w tc (p1 a)
instance [safe] NextGlobalContext r w () (GC a) (GC a)
instance [safe] NextGlobalContext r w (MonoidTC a) () (GC a)
instance [safe] BackTrack r w () (GC a)
instance [safe] Instrument tc () (GC a) (Monoid2 a r w On On tc)
instance [safe] Monoid a => Instrument tc (MonoidTC a) () (Monoid2 a r w On Off tc)
instance [safe] Instrument tc () () (Monoid2 a r w Off Off tc)


-- | The <a>OrdCons</a> instrument uses two passes to implement
--   hash-consing. The values are added to the table during the first pass
--   and a unique index for each value is returned during the second pass.
--   
--   <a>OrdCons</a> is implemented using <a>Map</a>, so it can be used on
--   any datatype which is an instance of <a>Ord</a>.
module Control.Monad.MultiPass.Instrument.OrdCons

-- | Abstract datatype for the instrument.
data OrdCons a r w p1 p2 tc

-- | Initialise the <a>OrdCons</a> instrument with an <a>OrdConsTable</a>.
--   This method is optional. Ff this method is not used then the
--   instrument will be initialised with an empty <a>OrdConsTable</a>.
initOrdCons :: (Ord a, Monad p1, Monad p2) => OrdCons a r w p1 p2 tc -> p1 (OrdConsTable a) -> MultiPassPrologue r w tc ()

-- | Get a unique index for the value.
ordCons :: (Ord a, Monad p1, Monad p2) => OrdCons a r w p1 p2 tc -> p1 a -> MultiPass r w tc (p2 Int)

-- | Get the final <a>OrdConsTable</a>.
getOrdConsTable :: OrdCons a r w p1 p2 tc -> MultiPassEpilogue r w tc (p2 (OrdConsTable a))

-- | This datatype is a newtype around <tt><a>Map</a> a <a>Int</a></tt>. It
--   maps its keys (of type <tt>a</tt>) to a permutation of the integers
--   <tt>0..n-1</tt>, where <tt>n</tt> is the number of keys.
data OrdConsTable a

-- | Lookup an element.
lookupOrdConsTable :: Ord a => OrdConsTable a -> a -> Maybe Int

-- | Insert an element. If the element is not in the map yet, then it is
--   assigned index <tt>n</tt>, where <tt>n</tt> is the original size of
--   the table.
insertOrdConsTable :: Ord a => OrdConsTable a -> a -> OrdConsTable a

-- | Add multiple elements. The new elements are assigned indices
--   <tt>n..n+k-1</tt>, where <tt>n</tt> is the original size of the table
--   and <tt>k</tt> is the number of new elements to be added. This
--   function will assert if any of the new elements are already in the
--   table.
growOrdConsTable :: Ord a => OrdConsTable a -> Map a () -> OrdConsTable a
instance [safe] NextGlobalContext r w tc (GC2 a) (GC1 r w a)
instance [safe] NextGlobalContext r w tc (GC2 a) (GC2 a)
instance [safe] Ord a => NextGlobalContext r w (MonoidTC (OrdConsTC a)) (GC1 r w a) (GC2 a)
instance [safe] NextGlobalContext r w tc (GC1 r w a) (GC1 r w a)
instance [safe] NextGlobalContext r w () () (GC1 r w a)
instance [safe] BackTrack r w () (GC2 a)
instance [safe] BackTrack r w tc (GC1 r w a)
instance [safe] Ord a => Instrument tc () (GC2 a) (OrdCons a r w On On tc)
instance [safe] Ord a => Instrument tc (MonoidTC (OrdConsTC a)) (GC1 r w a) (OrdCons a r w On Off tc)
instance [safe] Instrument tc () () (OrdCons a r w Off Off tc)
instance [safe] Ord a => Monoid (OrdConsTC a)


-- | The <a>TopKnot</a> instrument is used for knot tying across passes. It
--   allows a value to be written during the epilogue of one pass and read
--   during the prologue of a later pass. Knot tying is a technique
--   sometimes used in lazy functional programming, in which the definition
--   of a variable depends on its own value. The lazy programming technique
--   depends on an implicit two-pass ordering of the computation. For
--   example, the classic repmin program produces a pair of outputs - a
--   tree and an integer - and there is an implicit two-pass ordering where
--   the integer is computed during the first pass and the tree during the
--   second. The <a>TopKnot</a> instrument allows the same technique to be
--   applied, but the ordering of the passes is managed explicitly by the
--   <a>Control.Monad.MultiPass</a> library, rather than implicitly by lazy
--   evalution.
module Control.Monad.MultiPass.Instrument.TopKnot

-- | Abstract datatype for the instrument.
data TopKnot a r w p1 p2 tc

-- | Load the value that was stored during the first pass.
load :: TopKnot a r w p1 p2 tc -> MultiPassPrologue r w tc (p2 a)

-- | Store a value during the epilogue of the first pass. This function
--   should be called exactly once.
store :: TopKnot a r w p1 p2 tc -> p1 a -> MultiPassEpilogue r w tc ()
instance [safe] NextGlobalContext r w () (GC r w a) (GC r w a)
instance [safe] NextGlobalContext r w () () (GC r w a)
instance [safe] BackTrack r w tc (GC r w a)
instance [safe] Instrument tc () (GC r w a) (TopKnot a r w On On tc)
instance [safe] Instrument tc () (GC r w a) (TopKnot a r w On Off tc)
instance [safe] Instrument tc () () (TopKnot a r w Off Off tc)

module Control.Monad.MultiPass.Example.Assembler
newtype LabelName
LabelName :: String -> LabelName
newtype Register
Register :: Int -> Register
data Instruction
Label :: LabelName -> Instruction
Goto :: LabelName -> Instruction
AddImm8 :: Register -> Word8 -> Instruction
assemble :: NumThreads -> ST2Array r w Int Instruction -> ST2 r w (ST2Array r w Addr Word8)
instance [safe] Eq LabelName
instance [safe] Ord LabelName
instance [safe] Show Instruction
instance [safe] Eq Addr
instance [safe] Ord Addr
instance [safe] Ix Addr
instance [safe] MultiPassAlgorithm (EmitInstrs r w p1 p2 p3 tc) (EmitInstrsType r w p1 p2 p3 tc)
instance [safe] Monoid LabelMap
instance [safe] Show Addr
instance [safe] Num Addr
instance [safe] Show Register
instance [safe] Show LabelName


-- | This example is a variation on the <a>assembler</a> example. It
--   illustrates how one might convert a control flow graph into a linear
--   sequence of instructions. The example is less complete than the
--   <a>assembler</a> example, so the output is not real machine code.
--   Instead the output is a simple serialised representation of the
--   control flow graph.
--   
--   In this example, the control flow graph is represented as a
--   <a>Array</a>, which is an immutable datatype. The example can also be
--   implemented with a mutable representation of the control flow graph,
--   as shown in <a>Control.Monad.MultiPass.Example.CFG2</a>.
module Control.Monad.MultiPass.Example.CFG
newtype Node
Node :: Int -> Node
emitCFG :: CFG -> ST2 r w (ST2Array r w Position Int)
instance [safe] Eq Node
instance [safe] Ord Node
instance [safe] Ix Node
instance [safe] Eq Position
instance [safe] Ord Position
instance [safe] Ix Position
instance [safe] MultiPassAlgorithm (EmitCFG r w p1 p2 p3 tc) (EmitCFGType r w p1 p2 p3 tc)
instance [safe] Num Position


-- | This example is a modified version of the
--   <a>Control.Monad.MultiPass.Example.CFG</a> example, which uses a
--   mutable <a>ST2Array</a> to represent the control flow graph rather
--   than an immutable <a>Array</a>. This means that it is not possible to
--   use <a>pmapM</a> to map over the array. Instead <a>pmapST2ArrayMP</a>
--   is used
module Control.Monad.MultiPass.Example.CFG2
newtype Node
Node :: Int -> Node
emitCFG :: NumThreads -> CFG r w -> ST2 r w (ST2Array r w Position Int)
instance [safe] Eq Node
instance [safe] Ord Node
instance [safe] Ix Node
instance [safe] Eq Position
instance [safe] Ord Position
instance [safe] Ix Position
instance [safe] MultiPassAlgorithm (EmitCFG r w p1 p2 p3 tc) (EmitCFGType r w p1 p2 p3 tc)
instance [safe] Num Position
instance [safe] Num Node


-- | An example of the use of the <a>Counter</a> instrument.
module Control.Monad.MultiPass.Example.Counter
data Tree r w i a
Node :: a -> (ST2Array r w i (Tree r w i a)) -> Tree r w i a
convertTree :: (Ix i, Num i) => Tree r w i a -> ST2 r w (Tree r w i (i, a))
instance [safe] MultiPassAlgorithm (ConvertTree i a r w p1 p2 tc) (ConvertTreeType i a r w p1 p2 tc)


-- | A variation on the <a>repmin</a> example. This example shows how the
--   <a>Knot3</a> can be used in a recursive algorithm.
module Control.Monad.MultiPass.Example.Localmin
data Tree a
Leaf :: !a -> Tree a
Node :: !(Tree a) -> !(Tree a) -> Tree a

-- | Version using lazy evaluation.
localmin :: Ord a => Tree a -> Tree [a]

-- | Version using the <a>Control.Monad.MultiPass</a> library.
localminMP :: Ord a => Tree a -> ST2 r w (Tree [a])
instance [safe] Eq a => Eq (Tree a)
instance [safe] Show a => Show (Tree a)
instance [safe] MultiPassAlgorithm (Localmin r w a p1 p2 p3 tc) (LocalminType r w a p1 p2 p3 tc)


-- | An example of the use of the <a>OrdCons</a> instrument.
module Control.Monad.MultiPass.Example.OrdCons
convertArray :: (Ix i, Num i, Ord a) => NumThreads -> ST2Array r w i a -> ST2 r w (ST2Array r w i Int)
instance [safe] MultiPassAlgorithm (ConvertArray i a r w p1 p2 tc) (ConvertArrayType i a r w p1 p2 tc)


-- | An implementation of the classic <tt>repmin</tt> algorithm, using the
--   <a>Control.Monad.MultiPass</a> library.
module Control.Monad.MultiPass.Example.Repmin

-- | Binary tree datatype.
data Tree a
Leaf :: !a -> Tree a
Node :: !(Tree a) -> !(Tree a) -> Tree a

-- | Original algorithm, which uses lazy evaluation.
repmin :: Ord a => Tree a -> Tree a

-- | New algorithm, using the <a>Control.Monad.MultiPass</a> library.
repminMP :: Ord a => Tree a -> ST2 r w (Tree a)

-- | Second version of the new algorithm (<a>repminMP</a>), using the
--   <a>Knot3</a> instrument, rather than <a>TopKnot</a>.
repminMP2 :: Ord a => Tree a -> ST2 r w (Tree a)

-- | Third version of the new algorithm (<a>repminMP</a>), using the
--   <a>Monoid2</a> instrument.
repminMP3 :: Ord a => Tree a -> ST2 r w (Tree a)
instance [safe] Eq a => Eq (Tree a)
instance [safe] Show a => Show (Tree a)
instance [safe] Ord a => Monoid (MinVal a)
instance [safe] MultiPassAlgorithm (Repmin3 r w a p1 p2 tc) (RepminType3 r w a p1 p2 tc)
instance [safe] MultiPassAlgorithm (Repmin2 r w a p1 p2 p3 tc) (RepminType2 r w a p1 p2 p3 tc)
instance [safe] MultiPassAlgorithm (Repmin r w a p1 p2 tc) (RepminType r w a p1 p2 tc)


-- | An example of the use of the <a>OrdCons</a> instrument. An array of
--   strings is converted to an array of integer indices, with one index
--   for each distinct string. This process is commonly known as <a>string
--   interning</a>.
module Control.Monad.MultiPass.Example.StringInterning
internStringArray :: NumThreads -> ST2Array r w Int String -> ST2 r w (ST2Array r w Int Int, OrdConsTable String)
instance [safe] MultiPassAlgorithm (InternArray r w p1 p2 tc) (InternArrayType r w p1 p2 tc)