Control.Monad.Par.AList

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.

The AList type and operations

data AList a

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

Constructors

ANil

ASing a

Append (AList a) (AList a)

AList [a]

Instances

Typeable1 AList

Eq a => Eq (AList a)

Show a => Show (AList a)

NFData a => NFData (AList a)

Serialize a => Serialize (AList a)

empty :: AList a

O(1) an empty AList

singleton :: a -> AList a

O(1) a singleton AList

cons :: a -> AList a -> AList a

O(1) prepend an element

head :: AList a -> a

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)

tail :: AList a -> AList a

O(n) take the tail element of an AList

length :: AList a -> Int

O(n) find the length of an AList

null :: AList a -> Bool

O(n) returns True if the AList is empty

append :: AList a -> AList a -> AList a

O(1) Append two ALists

toList :: AList a -> [a]

O(n) converts an AList to an ordinary list

fromList :: [a] -> AList a

O(1) convert an ordinary list to an AList

fromListBalanced :: [a] -> AList a

Convert an ordinary list, but do so using Append and ASing rather than AList

Regular (non-parallel) Combinators

filter :: (a -> Bool) -> AList a -> AList a

map :: (a -> b) -> AList a -> AList b

The usual map operation.

partition :: (a -> Bool) -> AList a -> (AList a, AList a)

Operations to build ALists 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

Inspect and modify the internal structure of an AList tree

depth :: AList a -> Int

balance :: AList a -> AList a

Balance the tree representation of an AList.