Safe Haskell | Safe-Infered |
---|

- The
`AList`

type and operations - Regular (non-parallel) Combinators
- Operations to build
`AList`

s in the`Par`

monad - Inspect and modify the internal structure of an AList tree

This module defines the `AList`

type, a list that supports
constant-time append, and is therefore ideal for building the
result of tree-shaped parallel computations.

- data AList a
- empty :: AList a
- singleton :: a -> AList a
- cons :: a -> AList a -> AList a
- head :: AList a -> a
- tail :: AList a -> AList a
- length :: AList a -> Int
- null :: AList a -> Bool
- append :: AList a -> AList a -> AList a
- toList :: AList a -> [a]
- fromList :: [a] -> AList a
- fromListBalanced :: [a] -> AList a
- filter :: (a -> Bool) -> AList a -> AList a
- map :: (a -> b) -> AList a -> AList b
- partition :: (a -> Bool) -> AList a -> (AList a, AList a)
- parBuildThresh :: (NFData a, ParFuture f p) => Int -> InclusiveRange -> (Int -> a) -> p (AList a)
- parBuildThreshM :: (NFData a, ParFuture f p) => Int -> InclusiveRange -> (Int -> p a) -> p (AList a)
- parBuild :: (NFData a, ParFuture f p) => InclusiveRange -> (Int -> a) -> p (AList a)
- parBuildM :: (NFData a, ParFuture f p) => InclusiveRange -> (Int -> p a) -> p (AList a)
- depth :: AList a -> Int
- balance :: AList a -> AList a

# The `AList`

type and operations

data AList a

List that support constant-time append (sometimes called join-lists).

*O(n)* take the head element of an `AList`

NB. linear-time, because the list might look like this:

(((... `append` a) `append` b) `append` c)

fromListBalanced :: [a] -> AList a

# Regular (non-parallel) Combinators

# Operations to build `AList`

s in the `Par`

monad

parBuildThresh :: (NFData a, ParFuture f p) => Int -> InclusiveRange -> (Int -> a) -> p (AList a)

A parMap over an AList can result in more balanced parallelism than the default parMap over Traversable data types. parMap :: NFData b => (a -> b) -> AList a -> Par (AList b)

Build a balanced `AList`

in parallel, constructing each element as a
function of its index. The threshold argument provides control
over the degree of parallelism. It indicates under what number
of elements the build process should switch from parallel to
serial.

parBuildThreshM :: (NFData a, ParFuture f p) => Int -> InclusiveRange -> (Int -> p a) -> p (AList a)

Variant of `parBuildThresh`

in which the element-construction function is itself a `Par`

computation.

parBuild :: (NFData a, ParFuture f p) => InclusiveRange -> (Int -> a) -> p (AList a)

"Auto-partitioning" version of `parBuildThresh`

that chooses the threshold based on
the size of the range and the number of processors..

parBuildM :: (NFData a, ParFuture f p) => InclusiveRange -> (Int -> p a) -> p (AList a)

like `parBuild`

, but the construction function is monadic