-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/
-- | A framework for safe, programmable, speculative parallelism
--
-- A framework for safe, programmable, speculative parallelism, loosely
-- based on
-- http://research.microsoft.com/pubs/118795/pldi026-vaswani.pdf
--
-- This package provides speculative function application and speculative
-- folds. And speculative STM actions take the place of the transactional
-- rollback machinery from the paper.
--
-- For example:
--
-- spec g f a evaluates f g while forcing
-- a, if g == a then f g is returned,
-- otherwise f a is evaluated and returned. Furthermore, if the
-- argument has already been evaluated, we skip the f g
-- computation entirely. If a good guess at the value of a is
-- available, this is one way to induce parallelism in an otherwise
-- sequential task. However, if the guess isn't available more cheaply
-- than the actual answer, then this saves no work and if the guess is
-- wrong, you risk evaluating the function twice.
--
-- The best-case timeline looks like:
--
--
-- [---- f g ----]
-- [----- a -----]
-- [-- spec g f a --]
--
--
-- The worst-case timeline looks like:
--
--
-- [---- f g ----]
-- [----- a -----]
-- [---- f a ----]
-- [------- spec g f a -----------]
--
--
-- Compare these to the timeline of f $! a:
--
--
-- [---- a -----]
-- [---- f a ----]
--
--
-- specSTM provides a similar time table for STM actions, but also
-- rolls back side-effects.
--
-- Changes in 0.3.0:
--
--
@package speculation
@version 0.4.0
module Control.Concurrent.Speculation
-- | spec g f a evaluates f g while forcing
-- a, if g == a then f g is returned.
-- Otherwise f a is evaluated.
--
-- Furthermore, if the argument has already been evaluated, we avoid
-- sparking the parallel computation at all.
--
-- If a good guess at the value of a is available, this is one
-- way to induce parallelism in an otherwise sequential task.
--
-- However, if the guess isn't available more cheaply than the actual
-- answer, then this saves no work and if the guess is wrong, you risk
-- evaluating the function twice.
--
--
-- spec a f a = f $! a
--
--
-- The best-case timeline looks like:
--
--
-- [---- f g ----]
-- [----- a -----]
-- [-- spec g f a --]
--
--
-- The worst-case timeline looks like:
--
--
-- [---- f g ----]
-- [----- a -----]
-- [---- f a ----]
-- [------- spec g f a -----------]
--
--
-- Compare these to the timeline of f $! a:
--
--
-- [---- a -----]
-- [---- f a ----]
--
spec :: (Eq a) => a -> (a -> b) -> a -> b
-- | Unlike spec, this version does not check to see if the argument
-- has already been evaluated. This can save a small amount of work when
-- you know the argument will always require computation.
spec' :: (Eq a) => a -> (a -> b) -> a -> b
-- | spec with a user defined comparison function
specBy :: (a -> a -> Bool) -> a -> (a -> b) -> a -> b
-- | spec' with a user defined comparison function
specBy' :: (a -> a -> Bool) -> a -> (a -> b) -> a -> b
-- | spec comparing by projection onto another type
specOn :: (Eq c) => (a -> c) -> a -> (a -> b) -> a -> b
-- | spec' comparing by projection onto another type
specOn' :: (Eq c) => (a -> c) -> a -> (a -> b) -> a -> b
-- | specSTM g f a evaluates f g while forcing
-- a, if g == a then f g is returned.
-- Otherwise the side-effects of the current STM transaction are rolled
-- back and f a is evaluated.
--
-- If the argument a is already evaluated, we don't bother to
-- perform f g at all.
--
-- If a good guess at the value of a is available, this is one
-- way to induce parallelism in an otherwise sequential task.
--
-- However, if the guess isn't available more cheaply than the actual
-- answer then this saves no work, and if the guess is wrong, you risk
-- evaluating the function twice.
--
--
-- specSTM a f a = f $! a
--
--
-- The best-case timeline looks like:
--
--
-- [------ f g ------]
-- [------- a -------]
-- [--- specSTM g f a ---]
--
--
-- The worst-case timeline looks like:
--
--
-- [------ f g ------]
-- [------- a -------]
-- [-- rollback --]
-- [------ f a ------]
-- [------------------ spec g f a ------------------------]
--
--
-- Compare these to the timeline of f $! a:
--
--
-- [------- a -------]
-- [------ f a ------]
--
specSTM :: (Eq a) => a -> (a -> STM b) -> a -> STM b
-- | Unlike specSTM, specSTM' doesn't check if the argument
-- has already been evaluated.
specSTM' :: (Eq a) => a -> (a -> STM b) -> a -> STM b
-- | specBySTM . on (==)'
specOnSTM :: (Eq c) => (a -> c) -> a -> (a -> STM b) -> a -> STM b
-- | specBySTM' . on (==)'
specOnSTM' :: (Eq c) => (a -> c) -> a -> (a -> STM b) -> a -> STM b
-- | specSTM using a user defined comparison function
specBySTM :: (a -> a -> Bool) -> a -> (a -> STM b) -> a -> STM b
-- | specSTM' using a user defined comparison function
specBySTM' :: (a -> a -> Bool) -> a -> (a -> STM b) -> a -> STM b
specCSTM :: (Eq a) => a -> (a -> CSTM b) -> a -> CSTM b
-- | Unlike specSTM, specSTM' doesn't check if the argument
-- has already been evaluated.
specCSTM' :: (Eq a) => a -> (a -> CSTM b) -> a -> CSTM b
-- | specByCSTM . on (==)'
specOnCSTM :: (Eq c) => (a -> c) -> a -> (a -> CSTM b) -> a -> CSTM b
-- | specByCSTM' . on (==)'
specOnCSTM' :: (Eq c) => (a -> c) -> a -> (a -> CSTM b) -> a -> CSTM b
-- | specSTM using a user defined comparison function
specByCSTM :: (a -> a -> Bool) -> a -> (a -> CSTM b) -> a -> CSTM b
-- | specCSTM' using a user defined comparison function
specByCSTM' :: (a -> a -> Bool) -> a -> (a -> CSTM b) -> a -> CSTM b
type CSTM = Codensity STM
newtype Codensity f a
Codensity :: (forall r. (a -> f r) -> f r) -> Codensity f a
runCodensity :: Codensity f a -> forall r. (a -> f r) -> f r
liftCodensity :: (Monad m) => m a -> Codensity m a
lowerCodensity :: (Monad m) => Codensity m a -> m a
instance Typeable Speculation
instance Show Speculation
instance Eq Speculation
instance Exception Speculation
module Data.Foldable.Speculation
-- | Given a valid estimate g, fold g f xs yields
-- the same answer as fold f xs.
--
-- g n should supply an estimate of the value of the monoidal
-- summation over the last n elements of the container.
--
-- If g n is accurate a reasonable percentage of the time and
-- faster to compute than the fold, then this can provide increased
-- opportunities for parallelism.
fold :: (Foldable f, Monoid m, Eq m) => (Int -> m) -> f m -> m
-- | fold using specBy
foldBy :: (Foldable f, Monoid m) => (m -> m -> Bool) -> (Int -> m) -> f m -> m
-- | Given a valid estimate g, foldMap g f xs
-- yields the same answer as foldMap f xs.
--
-- g n should supply an estimate of the value of the monoidal
-- summation over the last n elements of the container.
--
-- If g n is accurate a reasonable percentage of the time and
-- faster to compute than the fold, then this can provide increased
-- opportunities for parallelism.
foldMap :: (Foldable f, Monoid m, Eq m) => (Int -> m) -> (a -> m) -> f a -> m
foldMapBy :: (Foldable f, Monoid m) => (m -> m -> Bool) -> (Int -> m) -> (a -> m) -> f a -> m
-- | Given a valid estimator g, foldr g f z xs
-- yields the same answer as foldr' f z xs.
--
-- g n should supply an estimate of the value returned from
-- folding over the last n elements of the container.
--
-- If g n is accurate a reasonable percentage of the time and
-- faster to compute than the fold, then this can provide increased
-- opportunities for parallelism.
foldr :: (Foldable f, Eq b) => (Int -> b) -> (a -> b -> b) -> b -> f a -> b
foldrBy :: (Foldable f) => (b -> b -> Bool) -> (Int -> b) -> (a -> b -> b) -> b -> f a -> b
-- | Given a valid estimator g, foldl g f z xs
-- yields the same answer as foldl' f z xs.
--
-- g n should supply an estimate of the value returned from
-- folding over the first n elements of the container.
--
-- If g n is accurate a reasonable percentage of the time and
-- faster to compute than the fold, then this can provide increased
-- opportunities for parallelism.
foldl :: (Foldable f, Eq b) => (Int -> b) -> (b -> a -> b) -> b -> f a -> b
foldlBy :: (Foldable f) => (b -> b -> Bool) -> (Int -> b) -> (b -> a -> b) -> b -> f a -> b
foldr1 :: (Foldable f, Eq a) => (Int -> a) -> (a -> a -> a) -> f a -> a
foldr1By :: (Foldable f) => (a -> a -> Bool) -> (Int -> a) -> (a -> a -> a) -> f a -> a
foldl1 :: (Foldable f, Eq a) => (Int -> a) -> (a -> a -> a) -> f a -> a
foldl1By :: (Foldable f) => (a -> a -> Bool) -> (Int -> a) -> (a -> a -> a) -> f a -> a
-- | Map each element of a structure to an action, evaluate these actions
-- from left to right and ignore the results.
traverse_ :: (Foldable t, Applicative f, Eq (f ())) => (Int -> f c) -> (a -> f b) -> t a -> f ()
traverseBy_ :: (Foldable t, Applicative f) => (f () -> f () -> Bool) -> (Int -> f c) -> (a -> f b) -> t a -> f ()
-- | for_ is traverse_ with its arguments flipped.
for_ :: (Foldable t, Applicative f, Eq (f ())) => (Int -> f c) -> t a -> (a -> f b) -> f ()
forBy_ :: (Foldable t, Applicative f) => (f () -> f () -> Bool) -> (Int -> f c) -> t a -> (a -> f b) -> f ()
-- | Map each element of the structure to a monadic action, evaluating
-- these actions from left to right and ignore the results.
mapM_ :: (Foldable t, Monad m, Eq (m ())) => (Int -> m c) -> (a -> m b) -> t a -> m ()
mapMBy_ :: (Foldable t, Monad m) => (m () -> m () -> Bool) -> (Int -> m c) -> (a -> m b) -> t a -> m ()
-- | for_ is mapM_ with its arguments flipped.
forM_ :: (Foldable t, Monad m, Eq (m ())) => (Int -> m c) -> t a -> (a -> m b) -> m ()
forMBy_ :: (Foldable t, Monad m) => (m () -> m () -> Bool) -> (Int -> m c) -> t a -> (a -> m b) -> m ()
sequenceA_ :: (Foldable t, Applicative f, Eq (f ())) => (Int -> f b) -> t (f a) -> f ()
sequenceABy_ :: (Foldable t, Applicative f, Eq (f ())) => (f () -> f () -> Bool) -> (Int -> f b) -> t (f a) -> f ()
sequence_ :: (Foldable t, Monad m, Eq (m ())) => (Int -> m b) -> t (m a) -> m ()
sequenceBy_ :: (Foldable t, Monad m) => (m () -> m () -> Bool) -> (Int -> m b) -> t (m a) -> m ()
asum :: (Foldable t, Alternative f, Eq (f a)) => (Int -> f a) -> t (f a) -> f a
asumBy :: (Foldable t, Alternative f) => (f a -> f a -> Bool) -> (Int -> f a) -> t (f a) -> f a
msum :: (Foldable t, MonadPlus m, Eq (m a)) => (Int -> m a) -> t (m a) -> m a
msumBy :: (Foldable t, MonadPlus m) => (m a -> m a -> Bool) -> (Int -> m a) -> t (m a) -> m a
toList :: (Foldable t, Eq a) => (Int -> [a]) -> t a -> [a]
toListBy :: (Foldable t) => ([a] -> [a] -> Bool) -> (Int -> [a]) -> t a -> [a]
concat :: (Foldable t, Eq a) => (Int -> [a]) -> t [a] -> [a]
concatBy :: (Foldable t) => ([a] -> [a] -> Bool) -> (Int -> [a]) -> t [a] -> [a]
concatMap :: (Foldable t, Eq b) => (Int -> [b]) -> (a -> [b]) -> t a -> [b]
concatMapBy :: (Foldable t) => ([b] -> [b] -> Bool) -> (Int -> [b]) -> (a -> [b]) -> t a -> [b]
all :: (Foldable t) => (Int -> Bool) -> (a -> Bool) -> t a -> Bool
any :: (Foldable t) => (Int -> Bool) -> (a -> Bool) -> t a -> Bool
and :: (Foldable t) => (Int -> Bool) -> t Bool -> Bool
or :: (Foldable t) => (Int -> Bool) -> t Bool -> Bool
sum :: (Foldable t, Num a) => (Int -> a) -> t a -> a
sumBy :: (Foldable t, Num a) => (a -> a -> Bool) -> (Int -> a) -> t a -> a
product :: (Foldable t, Num a) => (Int -> a) -> t a -> a
productBy :: (Foldable t, Num a) => (a -> a -> Bool) -> (Int -> a) -> t a -> a
maximum :: (Foldable t, Ord a) => (Int -> a) -> t a -> a
maximumBy :: (Foldable t) => (a -> a -> Ordering) -> (Int -> a) -> t a -> a
minimum :: (Foldable t, Ord a) => (Int -> a) -> t a -> a
minimumBy :: (Foldable t) => (a -> a -> Ordering) -> (Int -> a) -> t a -> a
elem :: (Foldable t, Eq a) => (Int -> Bool) -> a -> t a -> Bool
elemBy :: (Foldable t) => (a -> a -> Bool) -> (Int -> Bool) -> a -> t a -> Bool
notElem :: (Foldable t, Eq a) => (Int -> Bool) -> a -> t a -> Bool
notElemBy :: (Foldable t) => (a -> a -> Bool) -> (Int -> Bool) -> a -> t a -> Bool
find :: (Foldable t, Eq a) => (Int -> Maybe a) -> (a -> Bool) -> t a -> Maybe a
findBy :: (Foldable t) => (Maybe a -> Maybe a -> Bool) -> (Int -> Maybe a) -> (a -> Bool) -> t a -> Maybe a