speculation-1.3: A framework for safe, programmable, speculative parallelism

Portability portable provisional Edward Kmett

Control.Concurrent.Speculation.List

Contents

Description

Synopsis

# Speculative scans

scan :: (Monoid m, Eq m) => (Int -> m) -> [m] -> [m]Source

Given a valid estimator `g`, `scan g xs` converts `xs` into a list of the prefix sums.

`g n` should supply an estimate of the value of the monoidal summation 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 prefix sum, then this can provide increased opportunities for parallelism.

scanBy :: Monoid m => (m -> m -> Bool) -> (Int -> m) -> [m] -> [m]Source

`scan` using `specBy`

scanMap :: (Monoid m, Eq m) => (Int -> m) -> (a -> m) -> [a] -> [m]Source

Given a valid estimator `g`, `scanMap g f xs` converts `xs` into a list of the prefix sums.

`g n` should supply an estimate of the value of the monoidal summation 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 scan, then this can provide increased opportunities for parallelism.

``` scan = scanMap id
scanMap = scanMapBy (==)
```

scanMapBy :: Monoid m => (m -> m -> Bool) -> (Int -> m) -> (a -> m) -> [a] -> [m]Source

scanr :: Eq b => (Int -> b) -> (a -> b -> b) -> b -> [a] -> [b]Source

Given a valid estimator `g`, `scanr g f z xs` yields the same answer as `scanr' f z xs`.

`g n` should supply an estimate of the value returned from scanning 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 scan, then this can provide increased opportunities for parallelism.

scanrBy :: (b -> b -> Bool) -> (Int -> b) -> (a -> b -> b) -> b -> [a] -> [b]Source

scanl :: Eq b => (Int -> b) -> (b -> a -> b) -> b -> [a] -> [b]Source

scanlBy :: (b -> b -> Bool) -> (Int -> b) -> (b -> a -> b) -> b -> [a] -> [b]Source

scanr1 :: Eq a => (Int -> a) -> (a -> a -> a) -> [a] -> [a]Source

scanr1By :: (a -> a -> Bool) -> (Int -> a) -> (a -> a -> a) -> [a] -> [a]Source

scanl1 :: Eq a => (Int -> a) -> (a -> a -> a) -> [a] -> [a]Source

scanl1By :: (a -> a -> Bool) -> (Int -> a) -> (a -> a -> a) -> [a] -> [a]Source