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

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

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

O(length result). Segmented replicate.

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

O(length result). Regular segmented replicate.

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

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

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

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

O(length result). Append two arrays.

O(length result). Segmented append.

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.

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

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

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

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

This is an alias for bpermute.

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.

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

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

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.

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.

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.

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

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

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

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

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

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.

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.

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

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

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

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

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

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

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

Apply a worker function to correponding elements of two arrays.

Apply a worker function to corresponding elements of three arrays.

Apply a worker function to corresponding elements of four arrays.

Apply a worker function to corresponding elements of five arrays.

Apply a worker function to corresponding elements of six arrays.

Apply a worker function to corresponding elements of seven arrays.

Apply a worker function to corresponding elements of six arrays.

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

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 (*).

Undirected segmented fold.

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

Same preconditions as fold.

Undirected scattered segmented fold.

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

Same preconditions as fold.

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.

Regular segmented fold.

All segements have the given length.

Same preconditions as fold.

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.

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

Same preconditions as fold1.

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

Same preconditions as fold1.

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

Same preconditions as fold1.

Same as fold (+) 0

Same as fold_s (+) 0

Same as fold_ss (+) 0

Same as fold_r (+) 0

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

Segmented count.

Scattered segmented count.

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

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

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

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]

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

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 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]

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

See the description of mkSel2 for how this works.

Interleave the elements of two arrays.

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

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.

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

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

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

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

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

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

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

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

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

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

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 

Check whether a Segd is well formed.

O(1). Construct an empty Segd.

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

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

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

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

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

O(1). Yield the total number of elements defined by a 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]

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.

Check whether a Segd is well formed.

O(1). Construct an empty SSegd.

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

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

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.

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

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

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

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

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

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

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

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.

Check whether a Segd is well formed.

O(1). Construct an empty SSegd.

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

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

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

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

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

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

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.

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.

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

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

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.

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

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.

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

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

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.

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.

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

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.

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

Combine two virtual segment descriptors.

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

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

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

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

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

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

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

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

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

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

Read an array from a file.

Write an array to a file.

Convert an array to a list of elements.

Convert a list of elements to an array.