Data.Array.Parallel.Unlifted

Parallel implementation of the segmented array API defined in dph-prim-interface.

Some of them don't yet have parallel implementations, so we fall back to the sequential ones from dph-prim-seq.

WARNING: Although this library is intended to be used as a target for the DPH vectoriser, it is also fine to use it directly from non DPH programs. However, this library does not support nested parallelism by itself. If you try to run further parallel computations in the workers passed to map, zipWith, fold etc, then they will just run sequentially.

Types

class (Unbox a, DT a) => Elt a

Instances

Elt Bool

Elt Double

Elt Float

Elt Int

Elt Word8

(Unbox (a, b), DT (a, b), Elt a, Elt b) => Elt (a, b)

type Array = Vector

Arrays are stored as unboxed vectors. They have bulk-strict semantics, so demanding one element demands them all.

Constructors

empty :: Elt a => Array a

O(1). Construct an array with no elements.

generate :: Elt a => Int -> (Int -> a) -> Array a

Generate a new array given its length and a function to compute each element.

replicate :: Elt a => Int -> a -> Array a

O(length result). Construct a new array by replicating a single element the given number of times.

replicate_s :: Elt a => Segd -> Array a -> Array a

O(length result). Segmented replicate.

Elements of the array are replicated according to the lengths of the segments defined by the Segd.

replicate_rs :: Elt a => Int -> Array a -> Array a

O(length result). Regular segmented replicate.

Like replicate_s, but all segments are assumed to have the given length.

repeat

Arguments

:: Elt a

=> Int

Number of times to repeat the source.

-> Int

Length of source (can be less than the provided array).

-> Array a

Array elements to repeat.

-> Array a

O(length result). Construct an array by copying a portion of another array.

indexed :: Elt a => Array a -> Array (Int, a)

O(length result). Tag each element of an array with its index.

indexed [42, 93, 13] = [(0, 42), (1, 93), (2, 13)]

(+:+) :: Elt a => Array a -> Array a -> Array a

O(length result). Append two arrays.

append_s

Arguments

:: Elt a

=> Segd

Segment descriptor of result aarray.

-> Segd

Segment descriptor of first array.

-> Array a

Data of first array.

-> Segd

Segment descriptor of second array.

-> Array a

Data of second array.

-> Array a

O(length result). Segmented append.

append_vs

Arguments

:: (Elt a, Elts a)

=> Segd

Segment descriptor of result aarray.

-> VSegd

Segment descriptor of first array.

-> Arrays a

Data of first array.

-> VSegd

Segment descriptor of second array.

-> Arrays a

Data of second array.

-> Array a

indices_s :: Segd -> Array Int

O(length result). Segmented indices.

Construct an array containing containing the segments defined by the given Segd.

Each segment will contain the elements [0..len-1] where len is the length of that segment.

enumFromTo :: Int -> Int -> Array Int

enumFromThenTo :: Int -> Int -> Int -> Array Int

enumFromStepLen :: Int -> Int -> Int -> Array Int

enumFromStepLenEach :: Int -> Array Int -> Array Int -> Array Int -> Array Int

Projections

length :: Elt a => Array a -> Int

O(1). Yield the number of elements in an array.

index :: Elt a => String -> Array a -> Int -> a

O(1). Retrieve a numbered element from an array.

The first argument gives a source-code location for out-of-bounds errors.

indexs :: Elt a => Array a -> Array Int -> Array a

O(length result). Scattered indexing from a single Array.

This is an alias for bpermute.

indexs_avs

Arguments

:: (Elt a, Elts a)

=> Arrays a

Irregular 2D array of elements.

-> VSegd

Maps (segment id, segment index) pairs to 2D indices in the Arrays

-> Array (Int, Int)

Pairs of (segment id, segment index).

-> Array a

O(length result). Scattered indexing through a VSegd.

The index array contains pairs of segment id and the index within that segment.

We use the VSegd to map the pairs to 2D indices within the Arrays, and return an array of the resulting elements.

extract

Arguments

:: Elt a

=> Array a

Source array.

-> Int

Starting index in source array.

-> Int

Length of result array.

-> Array a

O(length result). Extract a subrange of elements from an array.

extract [23, 42, 93, 50, 27] 1 3  = [42, 93, 50]

extracts_nss :: Elt a => SSegd -> Vector (Array a) -> Array a

O(length result). Extract segments defined by a SSegd from a vector of arrays.

NOTE: This is a transitory interface, and will be removed in future versions. Use extracts_ass instead.

extracts_ass

Arguments

:: (Elt a, Elts a)

=> SSegd

SSegd defining the slices to extract.

-> Arrays a

Source arrays.

-> Array a

O(length result). Extract segments defined by a SSegd.

Extract all the segments defined by the SSegd from the Arrays, returning them concatenated in a fresh Array.

extracts_avs

Arguments

:: (Elt a, Elts a)

=> VSegd

VSegd defining the slices to extract.

-> Arrays a

Source arrays.

-> Array a

O(length result). Extract segments defined by a VSegd.

Extract all the segments defined by the VSegd from the Arrays, returning them concatenated in a fresh Array.

drop :: Elt a => Int -> Array a -> Array a

O(length result). Drop elements from the front of an array, returning the latter portion.

Update

update

Arguments

:: Elt a

=> Array a

Source array.

-> Array (Int, a)

Index and value of new elements.

-> Array a

O(length result). Copy the source array while replacing some elements by new ones in the result.

Permutation

permute

Arguments

:: Elt a

=> Array a

Source array.

-> Array Int

Indices in the destination to copy elements to.

-> Array a

O(length result). Forwards permutation of array elements.

bpermute

Arguments

:: Elt a

=> Array a

Source array.

-> Array Int

Indices in the source to copy elements from.

-> Array a

O(length result). Backwards permutation of array elements.

bpermute [50, 60, 20, 30] [0, 3, 2] = [50, 30, 20]

mbpermute :: (Elt a, Elt b) => (a -> b) -> Array a -> Array Int -> Array b

Combination of map and bpermute.

The advantage of using this combined version is that we don't need to apply the parameter function to source elements that don't appear in the result.

bpermuteDft :: Elt e => Int -> (Int -> e) -> Array (Int, e) -> Array e

Default backwards permutation.

The values of the index-value pairs are written into the position in the result array that is indicated by the corresponding index.

All positions not covered by the index-value pairs will have the value determined by the initialiser function for that index position.

Zipping and Unzipping

zip :: (Elt a, Elt b) => Array a -> Array b -> Array (a, b)

O(1). Zip two arrays into an array of pairs. If one array is short, excess elements of the longer array are discarded.

zip3 :: (Elt a, Elt b, Elt c) => Array a -> Array b -> Array c -> Array (a, b, c)

O(1). Zip three arrays into an array of triples. If one array is short, excess elements of the longer arrays are discarded.

unzip :: (Elt a, Elt b) => Array (a, b) -> (Array a, Array b)

O(1). Unzip an array of pairs into a pair of arrays.

unzip3 :: (Elt a, Elt b, Elt c) => Array (a, b, c) -> (Array a, Array b, Array c)

O(1). Unzip an array of triples into a triple of arrays.

fsts :: (Elt a, Elt b) => Array (a, b) -> Array a

O(1). Take the first elements of an array of pairs.

snds :: (Elt a, Elt b) => Array (a, b) -> Array b

O(1). Take the second elements of an array of pairs.

Map and ZipWith

map :: (Elt a, Elt b) => (a -> b) -> Array a -> Array b

Apply a worker function to each element of an array, yielding a new array.

zipWith :: (Elt a, Elt b, Elt c) => (a -> b -> c) -> Array a -> Array b -> Array c

Apply a worker function to correponding elements of two arrays.

zipWith3 :: (Elt a, Elt b, Elt c, Elt d) => (a -> b -> c -> d) -> Array a -> Array b -> Array c -> Array d

Apply a worker function to corresponding elements of three arrays.

zipWith4 :: (Elt a, Elt b, Elt c, Elt d, Elt e) => (a -> b -> c -> d -> e) -> Array a -> Array b -> Array c -> Array d -> Array e

Apply a worker function to corresponding elements of four arrays.

zipWith5 :: (Elt a, Elt b, Elt c, Elt d, Elt e, Elt f) => (a -> b -> c -> d -> e -> f) -> Array a -> Array b -> Array c -> Array d -> Array e -> Array f

Apply a worker function to corresponding elements of five arrays.

zipWith6 :: (Elt a, Elt b, Elt c, Elt d, Elt e, Elt f, Elt g) => (a -> b -> c -> d -> e -> f -> g) -> Array a -> Array b -> Array c -> Array d -> Array e -> Array f -> Array g

Apply a worker function to corresponding elements of six arrays.

zipWith7 :: (Elt a, Elt b, Elt c, Elt d, Elt e, Elt f, Elt g, Elt h) => (a -> b -> c -> d -> e -> f -> g -> h) -> Array a -> Array b -> Array c -> Array d -> Array e -> Array f -> Array g -> Array h

Apply a worker function to corresponding elements of seven arrays.

zipWith8 :: (Elt a, Elt b, Elt c, Elt d, Elt e, Elt f, Elt g, Elt h, Elt i) => (a -> b -> c -> d -> e -> f -> g -> h -> i) -> Array a -> Array b -> Array c -> Array d -> Array e -> Array f -> Array g -> Array h -> Array i

Apply a worker function to corresponding elements of six arrays.

Scans and Folds

scan :: Elt a => (a -> a -> a) -> a -> Array a -> Array a

Similar to foldl but return an array of the intermediate states, including the final state that is computed by foldl.

fold :: Elt a => (a -> a -> a) -> a -> Array a -> a

Undirected fold over an array.

• The worker function must be associative.
• The provided starting element must be neutral with respect to the worker. For example 0 is neutral wrt (+) and 1 is neutral wrt (*).

fold_s :: Elt a => (a -> a -> a) -> a -> Segd -> Array a -> Array a

Undirected segmented fold.

All segments are folded individually, and the result contains one element for each segment.

Same preconditions as fold.

fold_ss :: (Elts a, Elt a) => (a -> a -> a) -> a -> SSegd -> Arrays a -> Array a

Undirected scattered segmented fold.

Like fold_s, but the segments can be scattered through an Arrays.

Same preconditions as fold.

fold_vs :: (Elts a, Elt a) => (a -> a -> a) -> a -> VSegd -> Arrays a -> Array a

Undirected fold over virtual segments.

The physical segments defined by the VSegd are folded individually, and these results are replicated according to the virtual segment id table of the VSegd. The result contains as many elements as there virtual segments.

Same preconditions as fold.

fold_r :: Elt a => (a -> a -> a) -> a -> Int -> Array a -> Array a

Regular segmented fold.

All segements have the given length.

Same preconditions as fold.

fold1 :: Elt a => (a -> a -> a) -> Array a -> a

Undirected fold, using the first element to initialise the state.

• The worker function must be associative.
• The provided starting element must be neutral with respect to the worker. For example 0 is neutral wrt (+) and 1 is neutral wrt (*).
• If the array contains no elements then you'll get a bounds check error.

fold1_s :: Elt a => (a -> a -> a) -> Segd -> Array a -> Array a

Like fold_s, but using the first element of each segment to initialise the state of that segment.

Same preconditions as fold1.

fold1_ss :: (Elts a, Elt a) => (a -> a -> a) -> SSegd -> Arrays a -> Array a

Like fold_ss, but using the first element of each segment to intialise the state of that segment.

Same preconditions as fold1.

fold1_vs :: (Elts a, Elt a) => (a -> a -> a) -> VSegd -> Arrays a -> Array a

Like fold_vs, but using the first element of each segment to initialise the state of that segment.

Same preconditions as fold1.

sum :: (Num a, Elt a) => Array a -> a

Same as fold (+) 0

sum_s :: (Num a, Elt a) => Segd -> Array a -> Array a

Same as fold_s (+) 0

sum_ss :: (Num a, Elts a, Elt a) => SSegd -> Arrays a -> Array a

Same as fold_ss (+) 0

sum_r :: (Num a, Elt a) => Int -> Array a -> Array a

Same as fold_r (+) 0

count :: (Elt a, Eq a) => Array a -> a -> Int

Count the number of elements in array that are equal to the given value.

count_s :: (Elt a, Eq a) => Segd -> Array a -> a -> Array Int

Segmented count.

count_ss :: (Elt a, Eq a) => SSegd -> Vector (Array a) -> a -> Array Int

Scattered segmented count.

NOTE: This is a transitory interface, and will be removed in future versions.

and :: Array Bool -> Bool

O(length source). Compute the conjunction of all elements in a boolean array.

Pack and Filter

pack :: Elt a => Array a -> Array Bool -> Array a

O(length result). Extract elements of an array where the associated flag is true.

packByTag

Arguments

:: Elt a

=> Array a

data values

-> Array Tag

tag values

-> Tag

the tag of values to select

-> Array a

data values that had that tag

O(length result). Select the elements of an array that have a corresponding tag.

packByTag [12, 24, 42, 93] [1, 0, 0, 1] 0 = [24, 42]

filter :: Elt a => (a -> Bool) -> Array a -> Array a

Extract the elements from an array that match the given predicate.

pick :: (Elt a, Eq a) => Array a -> a -> Array Bool

Compute an array of flags indicating which elements match a given value.

pick [4, 5, 3, 6, 5, 2, 5] 5 = [F, T, F, F, T, F, T]

Combine and Interleave

combine :: Elt a => Array Bool -> Array a -> Array a -> Array a

Combine two arrays, using a flags array to tell us where to get each element from.

combine [T, F, F, T, T, F] [1, 2, 3] [4, 5, 6] = [1, 4, 5, 2, 3, 6]

combine2 :: Elt a => Array Tag -> SelRep2 -> Array a -> Array a -> Array a

Like combine, but use a precomputed selector to speed up the process.

See the description of mkSel2 for how this works.

interleave :: Elt a => Array a -> Array a -> Array a

Interleave the elements of two arrays.

interleave [1, 2, 3] [4, 5, 6] = [1, 4, 2, 5, 3, 6]

Selectors

type Sel2 = UPSel2

mkSel2

Arguments

:: Array Tag

Tags array.

-> Array Int

Indices array.

-> Int

Number of elements taken from first source array.

-> Int

Number of elements taken from second source array.

-> SelRep2

Parallel selector representation.

-> Sel2

O(1). Construct a selector.

A selector is a description of how to perform a combine operation.

Suppose we are evaluating the following expression:

combine [F,F,T,F,T,T] [1,2,3] [4,5,6] = [4,5,1,6,2,3]

This is difficult to parallelise. For each element in the result, the source array we get this element from depends on the tag values associated with all previous elements.

However, if we going to apply combine several times with the same flags array, we can precompute a selector that tells us where to get each element. The selector contains the original flags, as well as the source index telling us where to get each element for the result array.

For example:

tagsToIndices2 [F,F,T,F,T,T]   -- tags
             = [0,1,0,2,1,2]   -- indices

This says get the first element from index 0 in the second array, then from index 1 in the second array, then index 0 in the first array ...

The selector then consists of both the tag and indices arrays.

tagsSel2 :: Sel2 -> Array Tag

O(1). Yield the tags array of a selector.

indicesSel2 :: Sel2 -> Array Int

O(1). Yield the indices array of a selector.

elementsSel2_0 :: Sel2 -> Int

O(1). Yield the number of elements that will be taken from the first array.

elementsSel2_1 :: Sel2 -> Int

O(1). Yield the number of elements that will be taken from the second array.

repSel2 :: Sel2 -> SelRep2

O(1). Yield the parallel representation of a selector.

tagsToSel2 :: Array Tag -> Sel2

O(n). Compute a selector from a tags array.

Selector Representations

type SelRep2 = UPSelRep2

mkSelRep2 :: Array Tag -> SelRep2

O(n). Construct a parallel selector representation.

A SelRep2 describes how to distribute the two data vectors corresponding to a Sel2 across several PEs.

Suppose we want to perform the following combine operation:

 combine [F,F,T,T,F,T,F,F,T] [A0,A1,A2,A3,A4] [B0,B1,B2,B3] 
   = [A0,A1,B0,B1,A2,B2,A3,A4,B3]

The first array is the flags array, that says which of the data arrays to get each successive element from. As combine is difficult to compute in parallel, if we are going to perform several combines with the same flags array, we can precompute a selector that tells us where to get each element. The selector contains the original flags, as well as the source index telling us where to get each element for the result array.

 flags:   [F,F,T,T,F,T,F,F,T]
 indices: [0,1,0,1,2,2,3,4,3]

Suppose we want to distribute the combine operation across 3 PEs. It's easy to split the selector like so:

            PE0                PE1               PE2
 flags:   [F,F,T]            [T,F,T]           [F,F,T] 
 indices: [0,1,0]            [1,2,2]           [3,4,3]

We now need to split the two data arrays. Each PE needs slices of the data arrays that correspond to the parts of the selector that were given to it. For the current example we get:

            PE0                PE1               PE2
 data_A:   [A0,A1]            [A2]              [A3,A4]
 data_B:   [B0]               [B1,B2]           [B3]

The SelRep2 contains the starting index and length of each of of these slices:

            PE0                PE1               PE2
      ((0, 0), (2, 1))   ((2, 1), (1, 2))  ((3, 3), (2, 1))
       indices   lens      indices  lens    indices  lens

indicesSelRep2 :: Array Tag -> SelRep2 -> Array Int

O(1). Take the indices field from a SelRep2.

elementsSelRep2_0 :: Array Tag -> SelRep2 -> Int

O(1). Yield the number of elements to take from the first array.

elementsSelRep2_1 :: Array Tag -> SelRep2 -> Int

O(1). Yield the number of elements to take from the second array.

Segment Descriptors

type Segd = UPSegd

mkSegd

Arguments

:: Array Int

(lengths) Segment lengths.

-> Array Int

(indices) Segment indices.

-> Int

Total number of elements.

-> Segd

O(max(segs, threads) . log segs). Construct a segment descriptor.

A segment desciptor defines an irregular 2D array based on a flat, 1D array of elements. The defined array is a nested array of segments, where every segment covers some of the elements from the flat array.

• The starting indices must be equal to init (scanl (+) 0 lengths)
• If you don't want to cover all the elements from the flat arrary then use a SSegd instead.

Example:

   flat array data: [1 2 3 4 5 6 7 8]
     (segmentation)  --- ----- - ---
     segd  lengths: [2, 3, 1, 2]
           indices: [0, 2, 5, 6]
          elements: 8 

validSegd :: Segd -> Bool

Check whether a Segd is well formed.

emptySegd :: Segd

O(1). Construct an empty Segd.

singletonSegd :: Int -> Segd

O(1). Construct a Segd containing a single segment of the given length.

lengthsToSegd :: Array Int -> Segd

O(max(segs, threads) . log segs). Construct a Segd from an array of segment lengths.

lengthSegd :: Segd -> Int

O(1). Yield the length of a Segd.

lengthsSegd :: Segd -> Array Int

O(1). Yield the segment lengths of a Segd.

indicesSegd :: Segd -> Array Int

O(1). Yield the segment starting indices of a Segd.

elementsSegd :: Segd -> Int

O(1). Yield the total number of elements defined by a Segd.

plusSegd :: Segd -> Segd -> Segd

O(max(segs, threads) . log segs). Add the lengths of corresponding segments in two descriptors.

plusSegd [lens: 2 3 1] [lens: 3 1 1] = [lens: 5 4 2]

Scattered Segment Descriptors

type SSegd = UPSSegd

mkSSegd

Arguments

:: Array Int

(starts) Starting index of each segment within its flat array.

-> Array Int

(sources) Source id of flat array to get each segment from.

-> Segd

Plain segment descriptor giving the lengths of the segments.

-> SSegd

Construct a Scattered Segment Descriptor.

A SSegd is an extension of a Segd that that allows the segments to be scattered through multiple flat arrays.

Each segment is associated with a source id that indicates what flat array it is in, along with the starting index in that flat array.

• The segments need not cover the entire flat array.
• Different segments may point to the same elements.

validSSegd :: SSegd -> Bool

Check whether a Segd is well formed.

emptySSegd :: SSegd

O(1). Construct an empty SSegd.

singletonSSegd :: Int -> SSegd

O(1). Construct a Segd containing a single segment of the given length.

promoteSegdToSSegd :: Segd -> SSegd

O(segs). Promote a Segd to a SSegd, assuming all segments are contiguous and come from a single array.

isContiguousSSegd :: SSegd -> Bool

O(1). True when a SSegd has been constructed by promoting a SSegd.

In this case all the data elements are in one contiguous flat array, and consumers can avoid looking at the real starts and sources fields.

lengthOfSSegd :: SSegd -> Int

O(1). Yield the length of a SSegd.

lengthsOfSSegd :: SSegd -> Array Int

O(1). Yield the segment lengths of a SSegd.

indicesOfSSegd :: SSegd -> Array Int

O(1). Yield the indices field of a SSegd.

startsOfSSegd :: SSegd -> Array Int

O(1). Yield the starts field of a SSegd.

sourcesOfSSegd :: SSegd -> Array Int

O(1). Yield the sources field of a SSegd.

getSegOfSSegd :: SSegd -> Int -> (Int, Int, Int, Int)

O(1). Get the length, segment index, starting index, and source id of a segment.

appendSSegd :: SSegd -> Int -> SSegd -> Int -> SSegd

Produce a segment descriptor that describes the result of appending two segmented arrays.

Virtual Segment Descriptors

type VSegd = UPVSegd

mkVSegd

Arguments

:: Array Int

(vsegids) Mapping from virtual to physical segments.

-> SSegd

Scattered Segment descriptor defining the physical segments.

-> VSegd

Construct a Virtual Segment Descriptor.

A VSegd is an extension of a SSegd that allows data from the underlying flat array to be shared between segments. For example, you can define an array of 10 virtual segments that all have the same length and elements as a single physical segment.

• Internally we maintain the invariant that all physical segments must be reachable by some virtual segment. This is needed to ensure that operations such as fold_ss segmented fold have the right complexity.
• If you don't need the invariant then you can sidestep the code that maintains it by using the redundant versions of the following operators, and sometimes get faster code.

validVSegd :: VSegd -> Bool

Check whether a Segd is well formed.

emptyVSegd :: VSegd

O(1). Construct an empty SSegd.

singletonVSegd :: Int -> VSegd

O(1). Construct a VSegd containing a single segment of the given length.

replicatedVSegd

Arguments

:: Int

Length of segment.

-> Int

Number of times replicated.

-> VSegd

O(len). Construct a VSegd that describes an array where all virtual segments point to the same physical segment.

promoteSegdToVSegd :: Segd -> VSegd

O(segs). Promote a plain Segd to a VSegd.

The result contains one virtual segment for every physical segment the provided Segd.

promoteSSegdToVSegd :: SSegd -> VSegd

O(segs). Promote a plain SSegd to a VSegd.

The result contains one virtual segment for every physical segment the provided SSegd.

isManifestVSegd :: VSegd -> Bool

O(1). If true then the segments are all unshared, and the vsegids field be just [0..len-1].

Consumers can check this field to avoid demanding the vsegids field. This can avoid the need for it to be constructed in the first place, due to lazy evaluation.

isContiguousVSegd :: VSegd -> Bool

O(1). If true then the starts field is identical to the indices field and the sourceids are all 0s.

In this case all the data elements are in one contiguous flat array, and consumers can avoid looking at the real starts and sources fields.

lengthOfVSegd :: VSegd -> Int

O(1). Yield the length of a VSegd.

takeVSegidsOfVSegd :: VSegd -> Array Int

O(1). Yield the vsegids of a VSegd.

takeVSegidsRedundantOfVSegd :: VSegd -> Array Int

O(1). Yield the vsegids of a VSegd, but don't require that every physical segment is referenced by some virtual segment.

If you're just performing indexing and don't need the invariant that all physical segments are reachable from some virtual segment, then use this version as it's faster. This sidesteps the code that maintains the invariant.

The stated O(1) complexity assumes that the array has already been fully evalauted. If this is not the case then we can avoid demanding the result of a prior computation on the vsegids, thus reducing the cost attributed to that prior computation.

takeSSegdOfVSegd :: VSegd -> SSegd

O(1). Yield the SSegd of a VSegd.

takeSSegdRedundantOfVSegd :: VSegd -> SSegd

O(1). Yield the SSegd of a VSegd, but don't require that every physical segment is referenced by some virtual segment.

See the note in takeVSegidsRedundantOfVSegd.

takeLengthsOfVSegd :: VSegd -> Array Int

O(1). Yield the segment lengths of a VSegd.

getSegOfVSegd :: VSegd -> Int -> (Int, Int, Int)

O(1). Get the length, starting index, and source id of a segment.

unsafeDemoteToSSegdOfVSegd :: VSegd -> SSegd

O(segs). Yield a SSegd that describes each segment of a VSegd individually.

By doing this we lose information about which virtual segments correspond to the same physical segments.

WARNING: Trying to take the SSegd of a nested array that has been constructed with replication can cause index space overflow. This is because the virtual size of the corresponding flat data can be larger than physical memory. If this happens then indices fields and element count in the result will be invalid.

unsafeDemoteToSegdOfVSegd :: VSegd -> Segd

O(segs). Yield a Segd that describes each segment of a VSegd individually.

By doing this we lose information about which virtual segments correspond to the same physical segments.

See the warning in unsafeDemoteToSSegdOfVSegd.

updateVSegsOfVSegd :: (Array Int -> Array Int) -> VSegd -> VSegd

Update the vsegids of a VSegd, and then cull the physical segment descriptor so that all physical segments are reachable from some virtual segment.

updateVSegsReachableOfVSegd :: (Array Int -> Array Int) -> VSegd -> VSegd

Update the vsegids of VSegd, where the result is guaranteed to cover all physical segments.

Using this version avoids performing the cull operation which discards unreachable physical segments.

• The resulting vsegids must cover all physical segments. If they do not then there will be physical segments that are not reachable from some virtual segment, and subsequent operations like fold_ss will have the wrong work complexity.

appendVSegd

Arguments

:: VSegd

Descriptor of first array.

-> Int

Number of flat physical arrays for first descriptor.

-> VSegd

Descriptor of second array.

-> Int

Number of flat physical arrays for second descriptor.

-> VSegd

Produce a virtual segment descriptor that describes the result of appending two segmented arrays.

combine2VSegd

Arguments

:: Sel2

Selector for the combine operation.

-> VSegd

Descriptor of first array.

-> Int

Number of flat physical arrays for first descriptor.

-> VSegd

Descriptor of second array.

-> Int

Number of flat physical arrays for second descriptor.

-> VSegd

Combine two virtual segment descriptors.

Irregular two dimensional arrays

class (Unboxes a, DT a) => Elts a

Instances

Elts Double

Elts Float

Elts Int

Elts Word8

type Arrays = Vectors

emptys :: Arrays a

O(1). Construct an empty Arrays with no elements.

singletons :: (Elt a, Elts a) => Array a -> Arrays a

O(1). Construct an Arrays consisting of a single Array.

lengths :: Elts a => Arrays a -> Int

O(1). Yield the number of Array in an Arrays.

unsafeIndexs :: (Elt a, Elts a) => Arrays a -> Int -> Array a

O(1). Take one of the outer Array from an Arrays.

unsafeIndex2s :: (Elt a, Elts a) => Arrays a -> Int -> Int -> a

O(1). Retrieve a single element from an Arrays, given the outer and inner indices.

appends :: (Elt a, Elts a) => Arrays a -> Arrays a -> Arrays a

O(n). Append two Arrays, using work proportional to the length of the outer array.

fromVectors :: (Elt a, Elts a) => Vector (Array a) -> Arrays a

O(number of inner arrays). Convert a boxed vector of Array to an Arrays.

toVectors :: (Elt a, Elts a) => Arrays a -> Vector (Array a)

O(number of inner arrays). Convert an Arrays to a boxed vector of Array.

Random arrays

randoms :: (Elt a, Random a, RandomGen g) => Int -> g -> Array a

Generate an array of the given length full of random data. Good for testing.

randomRs :: (Elt a, Random a, RandomGen g) => Int -> (a, a) -> g -> Array a

Generate an array of the given length full of random data. Good for testing.

Array IO

class UIO a => IOElt a

Instances

IOElt Double

IOElt Int

(UIO (a, b), IOElt a, IOElt b) => IOElt (a, b)

hGet :: IOElt a => Handle -> IO (Array a)

Read an array from a file.

hPut :: IOElt a => Handle -> Array a -> IO ()

Write an array to a file.

toList :: Elt a => Array a -> [a]

Convert an array to a list of elements.

fromList :: Elt a => [a] -> Array a

Convert a list of elements to an array.