monad-par-0.1.0.3: A library for parallel programming based on a monad

Safe Haskell | None

Control.Monad.Par.AList

Contents

- The `AList` type and operations
- Operations to build `AList`s in the `Par` monad

Description

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.

Synopsis

- data AList a
  - = ANil
  - | ASing a
  - | Append (AList a) (AList a)
  - | 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
- parBuildThresh :: NFData a => Int -> InclusiveRange -> (Int -> a) -> Par (AList a)
- parBuildThreshM :: NFData a => Int -> InclusiveRange -> (Int -> Par a) -> Par (AList a)
- parBuild :: NFData a => InclusiveRange -> (Int -> a) -> Par (AList a)
- parBuildM :: NFData a => InclusiveRange -> (Int -> Par a) -> Par (AList a)

# The `AList` type and operations

data AList a Source

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

Constructors

ANil |
ASing a |
Append (AList a) (AList a) |
AList [a] |

Instances

Show a => Show (AList a) |
NFData a => NFData (AList a) |

empty :: AList aSource

O(1) an empty `AList`

singleton :: a -> AList aSource

O(1) a singleton `AList`

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

O(1) prepend an element

head :: AList a -> aSource

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 aSource

O(n) take the tail element of an `AList`

length :: AList a -> Int Source

O(n) find the length of an `AList`

null :: AList a -> Bool Source

O(n) returns `True` if the `AList` is empty

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

O(1) Append two `AList`s

toList :: AList a -> [a]Source

O(n) converts an `AList` to an ordinary list

fromList :: [a] -> AList aSource

O(1) convert an ordinary list to an `AList`

# Operations to build `AList`s in the `Par` monad

parBuildThresh :: NFData a => Int -> InclusiveRange -> (Int -> a) -> Par (AList a)Source

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 => Int -> InclusiveRange -> (Int -> Par a) -> Par (AList a)Source

Variant of `parBuildThresh` in which the element-construction function is itself a `Par` computation.

parBuild :: NFData a => InclusiveRange -> (Int -> a) -> Par (AList a)Source

"Auto-partitioning" version of `parBuildThresh` that chooses the threshold based on the size of the range and the number of processors..

parBuildM :: NFData a => InclusiveRange -> (Int -> Par a) -> Par (AList a)Source

like `parBuild`, but the construction function is monadic