-- 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.5.0: -- -- @package speculation @version 0.5.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) => STM a -> (a -> STM b) -> a -> STM b -- | Unlike specSTM, specSTM' doesn't check if the argument -- has already been evaluated. specSTM' :: (Eq a) => STM a -> (a -> STM b) -> a -> STM b -- | specBySTM . on (==)' specOnSTM :: (Eq c) => (a -> c) -> STM a -> (a -> STM b) -> a -> STM b -- | specBySTM' . on (==)' specOnSTM' :: (Eq c) => (a -> c) -> STM a -> (a -> STM b) -> a -> STM b -- | specSTM using a user defined comparison function specBySTM :: (a -> a -> Bool) -> STM a -> (a -> STM b) -> a -> STM b -- | specSTM' using a user defined comparison function specBySTM' :: (a -> a -> Bool) -> STM a -> (a -> STM b) -> a -> STM b 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 foldrM :: (Foldable f, Monad m, Eq (m b)) => (Int -> m b) -> (a -> b -> m b) -> m b -> f a -> m b foldrByM :: (Foldable f, Monad m) => (m b -> m b -> Bool) -> (Int -> m b) -> (a -> b -> m b) -> m b -> f a -> m b foldlM :: (Foldable f, Monad m, Eq (m b)) => (Int -> m b) -> (b -> a -> m b) -> m b -> f a -> m b foldlByM :: (Foldable f, Monad m) => (m b -> m b -> Bool) -> (Int -> m b) -> (b -> a -> m b) -> m b -> f a -> m b foldrSTM :: (Foldable f, Eq b) => (Int -> STM b) -> (a -> b -> STM b) -> STM b -> f a -> STM b foldrBySTM :: (Foldable f) => (b -> b -> Bool) -> (Int -> STM b) -> (a -> b -> STM b) -> STM b -> f a -> STM b foldlSTM :: (Foldable f, Eq a) => (Int -> STM a) -> (a -> b -> STM a) -> STM a -> f b -> STM a foldlBySTM :: (Foldable f) => (a -> a -> Bool) -> (Int -> STM a) -> (a -> b -> STM a) -> STM a -> f b -> STM 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 () sequenceA_ :: (Foldable t, Applicative f, Eq (f ())) => (Int -> f b) -> t (f a) -> f () sequenceByA_ :: (Foldable t, Applicative f, Eq (f ())) => (f () -> f () -> Bool) -> (Int -> f b) -> t (f a) -> f () 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 -- | Map each element of the structure to a monadic action, evaluating -- these actions from left to right and ignoring the results. mapM_ :: (Foldable t, Monad m, Eq (m ())) => (Int -> m c) -> (a -> m b) -> t a -> m () mapByM_ :: (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 () forByM_ :: (Foldable t, Monad m) => (m () -> m () -> Bool) -> (Int -> m c) -> t a -> (a -> m b) -> m () 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 () 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 -- | Map each element of the structure to a monadic action, evaluating -- these actions from left to right and ignoring the results, while -- transactional side-effects from mis-speculated actions are rolled -- back. mapSTM_ :: (Foldable t) => (Int -> STM c) -> (a -> STM b) -> t a -> STM () -- | for_ is mapM_ with its arguments flipped. forSTM_ :: (Foldable t) => (Int -> STM c) -> t a -> (a -> STM b) -> STM () sequenceSTM_ :: (Foldable t) => (Int -> STM a) -> t (STM b) -> STM () 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