!"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~                                  ! " # $ % & ' ( ) * + , - . / 0 1 2 3 4 5 6 7 8 9 : ; < = > ? @ A B C D E F G H I J K L M N O P Q R S T U V W X Y Z [ \ ] ^ _ ` a b c d e f g h i j k l m n o p q r s t u v w x y z { | } ~                    None5 Create an 1$ with the given number of elements. 6Write a  to an 3. 7Write a  to a 3. 8Read a  from a 3. 9 Index an 1 of s. : Freeze a 3 into a plain 1. ;Freeze a nested 3 into an 1. <Copy an ArrayArray 123456789:;< 123456789:;< 341256789:;< 123456789:;<None=A 2-dimensional array, : where the inner arrays can all have different lengths. ?-Class of element types that can be used in a = @Construct an empty = with no arrays of no elements. A Construct a =. containing data from a single unboxed array. B!Yield the number of vectors in a =. C%Take one of the outer vectors from a =. D%Take one of the outer vectors from a =, with bounds checking E!Retrieve a single element from a =, & given the outer and inner indices. F!Retrieve a single element from a =, < given the outer and inner indices, with bounds checking. GRetrieve an inner array from a =, returning the array data, 2 starting index in the data, and vector length. HAppending two = uses work proportional to # the length of the outer arrays. I/Convert a boxed vector of unboxed vectors to a =. J Convert a =' to a boxed vector of unboxed vectors. MUnpack an unboxed vector into array data, starting index, and vector length. =>?@ABCDsource position EFsource position GHIJ=>?@ABCDEFGHIJ=>?@ABDFCEGHIJ=>?@ABCDEFGHIJ NoneK=Tag each element of an stream with its index in that stream.   indexed [42,93,13]  = [(0,42), (1,93), (2,13)] L:Given a stream of pairs containing a count an an element, = replicate element the number of times given by the count. @The first parameter sets the size hint of the resulting stream.  ) replicateEach 10 [(2,10), (5,20), (3,30)] # = [10,10,20,20,20,20,20,30,30,30] M=Repeat each element in the stream the given number of times.   replicateEach 2 [10,20,30]  = [10,10,20,20,30,30] "Multiply a size hint by a scalar. NGInterleave the elements of two streams. We alternate between the first + and second streams, stopping when we can't find a matching element.   interleave [2,3,4] [10,20,30] = [2,10,3,20,4,30]  interleave [2,3] [10,20,30] = [2,10,3,20]  interleave [2,3,4] [10,20] = [2,10,3,20,4] OECombine two streams, using a tag stream to tell us which of the data * streams to take the next element from. GIf there are insufficient elements in the data strams for the provided  tag stream then .   combine2ByTag [0,1,1,0,0,1] [1,2,3] [4,5,6]  = [1,4,5,2,3,6] PSegmented Stream combine. Like O, except that the tags select T entire segments of each data stream, instead of selecting one element at a time.   1 combineSS [True, True, False, True, False, False]  [2,1,3] [10,20,30,40,50,60]  [1,2,3] [11,22,33,44,55,66] ( = [10,20,30,11,40,50,60,22,33,44,55,66] MThis says take two elements from the first stream, then another one element N from the first stream, then one element from the second stream, then three % elements from the first stream... QACreate a stream of integer ranges. The pairs in the input stream 0 give the first and last value of each range. BThe first parameter gives the size hint for the resulting stream.  + enumFromToEach 11 [(2,5), (10,16), (20,22)] * = [2,3,4,5,10,11,12,13,14,15,16,20,21,22] RCCreate a stream of integer ranges. The triples in the input stream : give the first value, increment, length of each range. BThe first parameter gives the size hint for the resulting stream.  1 enumFromStepLenEach [(1,1,5), (10,2,4), (20,3,5)] ) = [1,2,3,4,5,10,12,14,16,20,23,26,29,32] SISegmented Stream fold. Take segments from the given stream and fold each 5 using the supplied function and initial element.   foldSS (+) 0 [2, 3, 2] [10, 20, 30, 40, 50, 60, 70]  = [30,120,130] TLike S8, but use the first member of each chunk as the initial  element for the fold. U4Segmented Stream fold, with a fixed segment length. Like S* but use a fixed length for each segment.  Divide a size hint by a scalar. VHSegmented Strem append. Append corresponding segments from each stream.   appendSS [2, 1, 3] [10, 20, 30, 40, 50, 60]  [1, 3, 2] [11, 22, 33, 44, 55, 66] ( = [10,20,11,30,22,33,44,40,50,60,55,66] WSegmented Stream indices.    indicesSS 15 4 [3, 5, 7] " = [4,5,6,0,1,2,3,4,0,1,2,3,4,5,6] KNote that we can set the starting value of the first segment independently L via the second argument of indicesSS. We use this when distributing arrays # across worker threads, as a thread'$s chunk may not start exactly at a + segment boundary, so the index of a thread' s first data element may not be  zero. KLMNOP tag values &segment lengths for first data stream first data stream 'segment lengths for second data stream second data stream QRSfunction to perform the fold initial element of each fold stream of segment lengths stream of input data stream of fold results TUfunction to perform the fold initial element for fold length of each segment  data stream V&segment lengths for first data stream first data stream 'segment lengths for second data stream second data stream W KLMNOPQRSTUVWKLMNOPQRSTUVWNoneCXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~`  !"#$%&'()*+,-./0XYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~`.-,0/+*%$ ]#c^_`abde)('&hijklmnopsqrtuvwxy |}z{~"![\gfXYZAXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~NoneSegment descriptor. Length of each segment.  Starting index of each segment. ,Total number of elements in the flat array. *O(1). Construct a new segment descriptor. >O(1). Check the internal consistency of a segment descriptor. GAs the indices and elemens field can be generated based on the segment E lengths, we check the consistency by rebuilding these fields and 5 comparing the rebuilt ones against the originals. KO(1). Construct an empty segment descriptor, with no elements or segments. 0O(1). Construct a singleton segment descriptor. ; The single segment covers the given number of elements. HO(segs). Convert an array of segment lengths into a segment descriptor. CThe array contains the length of each segment, and we compute the  indices from that. ,O(1). Yield the overall number of segments. 4O(1). Yield the lengths of the individual segments. 9O(1). Yield the segment indices of a segment descriptor. )O(1). Yield the number of data elements. 4O(1). Get the length and segment index of a segment NO(segs). Produce a segment descriptor that describes the result of appending  two arrays. RO(segs) Extract a slice of a segment descriptor, avoiding copying where possible. HWe can share the segment lengths with the original segment descriptor, C but still need to recompute the starting indices of each. Hence < runtime is O(segs) in the number of segments sliced out. =Extract a slice of a segment descriptor, copying everything. In contrast to %, this function copies the array of H segment lengths as well as recomputing the starting indices of each. Length of each segment.  Starting index of each segment. ,Total number of elements in the flat array. Source segment descriptor. Index of first segment. !Number of segments to slice out. Source segment desciptor. Undex of the first segment. #Number of segments to extract out. NoneScattered Segment Descriptor. >True when the starts are identical to the usegd indices field ! and the sources are all 0's. >In this case all the data elements are in one contiguous flat A array, and consumers can avoid looking at the real starts and  sources fields. 2Starting index of each segment in its flat array. ?IMPORTANT: this field is lazy so we can avoid creating it when , the flat array is contiguous. ,Which flat array to take each segment from. ?IMPORTANT: this field is lazy so we can avoid creating it when , the flat array is contiguous. 9Segment descriptor relative to a contiguous index space. , This defines the length of each segment. 4O(1). Construct a new scattered segment descriptor. 7 All the provided arrays must have the same lengths. HO(1). Check the internal consistency of a scattered segment descriptor. KO(1). Construct an empty segment descriptor, with no elements or segments. 0O(1). Construct a singleton segment descriptor. J The single segment covers the given number of elements in a flat array  with sourceid 0. O(segs). Promote a plain  to a . G All segments are assumed to come from a flat array with sourceid 0. HO(1). True when the starts are identical to the usegd indices field and  the sources are all 0's. >In this case all the data elements are in one contiguous flat A array, and consumers can avoid looking at the real starts and  sources fields. ,O(1). Yield the overall number of segments. O(1). Yield the  of a . -O(1). Yield the lengths of the segments of a . %O(1). Yield the segment indices of a . 6O(1). Yield the total number of elements covered by a . &O(1). Yield the starting indices of a .  O(1). Yield the source ids of a . QO(1). Get the length, segment index, starting index, and source id of a segment. JO(n). Produce a segment descriptor that describes the result of appending  two arrays. Cull the segments of a , down to only those reachable from an array  of vsegids, and also update the vsegids to point to the same segments  in the result. .Pretty print the physical representation of a UVSegd 2Starting index of each segment in its flat array. 'Which array to take each segment from. Contiguous segment descriptor. *Segment descriptor of first nested array. ANumber of flat data arrays used to represent first nested array. ,Segment descriptor of second nested array. BNumber of flat data arrays used to represent second nested array.  None>Take a stream of virtual segment and segment element indices, O and convert it to a stream of physical segment and segment element indices. 6Take a stream of segment and segment element indices, B and convert it to a stream of chunk and chunk element indices. None  Selector. Number of tags with value 0. Number of tags with value 1. O(1). Construct a selector. ?O(1). Get the number of elements represented by this selector. 5 This is the length of the array returned by m. (O(1). Get the tags array of a selector. +O(1). Get the indices array of a selector. JO(1). Get the number of elements that will be taken from the first array. KO(1). Get the number of elements that will be taken from the second array. EO(n). Compute the source index for each element of the result array.  Tags array. Indices array +Number of elements taken from first array. ,Number of elements taken from second array.  NoneVirtual segment descriptor. $When the vsegids field holds a lazy (U.enumFromTo 0 (len - 1)) F then this field is True. This lets us perform some operations like  demoteToUPSSegd without actually creating it. @Virtual segment identifiers that indicate what physical segment $ to use for each virtual segment. @Scattered segment descriptor that defines how physical segments  are layed out in memory. KO(1). Check the internal consistency of a virutal segmentation descriptor. 2O(1). Construct a new virtual segment descriptor. 7 All the provided arrays must have the same lengths. O(segs). Promote a plain  to a . CThe result contains one virtual segment for every physical segment  the provided Segd. O(segs). Promote a plain Segd to a VSegd. CThe result contains one virtual segment for every physical segment  the provided SSegd. KO(1). Construct an empty segment descriptor, with no elements or segments. 0O(1). Construct a singleton segment descriptor. J The single segment covers the given number of elements in a flat array  with sourceid 0. O(1). Construct a 0 that describes an array created by replicating # a single segment several times. =O(1). Checks whether all the segments are manifest (unshared / non-virtual). @ If this is the case, then the vsegids field will be [0..len-1]. CConsumers can check this field, avoid demanding the vsegids field. M This can avoid the need for it to be generated in the first place, due to  lazy evaluation. MO(1). Checks whether the starts are identical to the usegd indices field and  the sourceids are all 0's. >In this case all the data elements are in one contiguous flat A array, and consumers can avoid looking at the real starts and  sources fields. O(1). Yield the vsegids of a  O(1). Take the vsegids of a  , but don't require that every physical 2 segment is referenced by some virtual segment. If you'#re just performing indexing and don't need the invariant that all L physical segments are reachable from some virtual segment, then use this  version as it'@s faster. This sidesteps the code that maintains the invariant. IThe stated O(1) complexity assumes that the array has already been fully M evalauted. If this is not the case then we can avoid demanding the result L of a prior computation on the vsegids, thus reducing the cost attributed  to that prior computation. O(1). Yield the  of a . O(1). Take the UPSSegd of a UPVSegd , but don't require that every physical 2 segment is referenced by some virtual segment. See the note in . :O(1). Yield the overall number of segments described by a . :O(segs). Yield the lengths of the segments described by a . BO(1). Get the length, starting index, and source id of a segment. O(segs). Yield a " that describes each segment of a   individually. H By doing this we lose information about virtual segments corresponding $ to the same physical segments. E This operation is used in concatPR as the first step in eliminating ' segmentation from a nested array. O(segs). Yield a " that describes each segment of a  B individually, assuming all segments have been concatenated to  remove scattering. WARNING: Trying to take the UPSegd! of a nested array that has been H constructed with replication can cause index space overflow. This is I because the virtual size of the corresponding flat data can be larger B than physical memory. If this happens then indices fields and 0 element count in the result will be invalid. Update the vsegids of UPVSegd, and then cull the physical G segment descriptor so that all phsyical segments are reachable from  some virtual segment. MThis function lets you perform filtering operations on the virtual segments, M while maintaining the invariant that all physical segments are referenced  by some virtual segment. Update the vsegids of UPVSegd, where the result covers  all physical segments. 9 The resulting vsegids must cover all physical segments. G If they do not then there will be physical segments that are not I reachable from some virtual segment, and performing operations like % segmented fold will waste work. ) Using this version saves performing the cull operation which J discards unreachable physical segments. This is O(result segments), - but can be expensive in absolute terms. O(n) O Produce a segment descriptor describing the result of appending two arrays. /O(n). Combine two virtual segment descriptors. 5(vsegids) Mapping from virtual to physical segments. +Scattered Segment descriptor defining the  physical segments. Length of segment. Number of times replicated. Descriptor of first array. 5Number of flat physical arrays for first descriptor. Descriptor of second array. 6Number of flat physical arrays for second descriptor. $Selector for the combine operation. Descriptor of first array. 5Number of flat physical arrays for first descriptor. Descriptor of second array. 6Number of flat physical arrays for second descriptor.  NoneTake a stream of indices, ! look them up from a vector, & and produce a stream of elements. 3Take a stream of chunk and chunk element indices, % look them up from some vectors, & and produce a stream of elements. ;Take a stream of virtual segment ids and element indices,  pass them through a / to get physical segment and element indices, % and produce a stream of elements. None5Stream some physical segments from many data arrays. Stream segments from a =. + There must be at least one segment in the , but this is not checked. $ No bounds checking is done for the . Stream segments from a =. + There must be at least one segment in the , but this is not checked. $ No bounds checking is done for the . Source arrays. =Segment descriptor defining segments base on source vectors. Vectors holding source data. Scattered segment descriptor Vectors holding source data. Scattered segment descriptor Vectors holding source data. Scattered segment descriptor Segmap Vectors holding source data. Scattered segment descriptor Virtual segment ids Segmap NoneKLMNOPQRSTUVWKLMNOPQRSTUVWNoneESegmented replicate of a vector based on the lengths of the segments  of the provided . Regular sgemented replicate. Segmented append. Segmented indices. None 3Segmented array reduction proceeding from the left 4Segmented array reduction proceeding from the left.  For scattered segments. CSegmented array reduction that requires an associative combination  function with its unit CSegmented array reduction that requires an associative combination 3 function with its unit. For scattered segments. KSegmented array reduction from left to right with non-empty subarrays only LSegmented array reduction from left to right with non-empty subarrays only.  For scattered segments. FSegmented array reduction with non-empty subarrays and an associative  combination function. FSegmented array reduction with non-empty subarrays and an associative 1 combination function. For scattered segments. Regular arrar reduction 3Merge two segmented arrays according to flag array  None>Compute the boolean AND of all segments in a segmented array. =Compute the boolean OR of all segments in a segmented array. 2Compute the segmented sum of an array of numerals 6Compute the segmented product of an array of numerals /Determine the maximum element in each subarray /Determine the minimum element in each subarray 2Compute the segmented sum of an array of numerals NoneLookup elements from a -. Lookup elements from some = through a UPVSegd. Copy segments from a =', concatenating them into a new array. Copy segments from a =', concatenating them into a new array. Copy segments from a =', concatenating them into a new array. &Copy segments defined by a segmap and  into a new array.  None None'Arrays are stored as unboxed vectors. O They have bulk-strict semantics, so demanding one element demands them all. NGenerate a new array given its length and a function to compute each element.  CApply a worker function to corresponding elements of three arrays.  BApply a worker function to corresponding elements of four arrays.  BApply a worker function to corresponding elements of five arrays.  AApply a worker function to corresponding elements of six arrays.  CApply a worker function to corresponding elements of seven arrays. AApply a worker function to corresponding elements of six arrays. 'Undirected fold over virtual segments. %The physical segments defined by the  are folded individually, E and these results are replicated according to the virtual segment  id table of the 0. The result contains as many elements as there  virtual segments. Same preconditions as @. Like =, but using the first element of each segment to initialise  the state of that segment. Same preconditions as D. Same as  fold_s (+) 0 Same as  fold_ss (+) 0 ICount the number of elements in array that are equal to the given value. Segmented count. Scattered segmented count. NNOTE: This is a transitory interface, and will be removed in future versions. O(length result). B Select the elements of an array that have a corresponding tag. packByTag [12, 24, 42, 93] [1, 0, 0, 1] 0 = [24, 42]ICompute 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],O(n). Compute a selector from a tags array. #O(max(segs, threads) . log segs).  Construct a # from an array of segment lengths. #O(max(segs, threads) . log segs). A Add the lengths of corresponding segments in two descriptors. plusSegd [lens: 2 3 1] [lens: 3 1 1] = [lens: 5 4 2]+O(1). Construct an array with no elements. %O(length result). Append two arrays. $O(length result). Segmented append. O(length result). C Construct a new array by replicating a single element the given  number of times.  'O(length result). Segmented replicate. FElements of the array are replicated according to the lengths of the  segments defined by the . !/O(length result). Regular segmented replicate. Like  9, but all segments are assumed to have the given length. "LO(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). Segmented indices. EConstruct an array containing containing the segments defined by the  given . 'Each segment will contain the elements  [0..len-1] where len is the  length of that segment. )0O(1). Yield the number of elements in an array. *1O(1). Retrieve a numbered element from an array. JThe first argument gives a source-code location for out-of-bounds errors. +3O(length result). Scattered indexing from a single . This is an alias for 4. ,/O(length result). Scattered indexing through a . HThe index array contains pairs of segment id and the index within that  segment.  We use the + to map the pairs to 2D indices within the , 2 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].0O(length result). Extract segments defined by a  from a vector of arrays. NNOTE: This is a transitory interface, and will be removed in future versions.  Use / instead. /0O(length result). Extract segments defined by a . (Extract all the segments defined by the  from the , * returning them concatenated in a fresh . 00O(length result). Extract segments defined by a . (Extract all the segments defined by the  from the , * returning them concatenated in a fresh . 1=O(length result). Drop elements from the front of an array, ' returning the latter portion. 2O(length result). R Copy the source array while replacing some elements by new ones in the result. 3:O(length result). Forwards permutation of array elements. 4;O(length result). Backwards permutation of array elements. bpermute [50, 60, 20, 30] [0, 3, 2] = [50, 30, 20]5!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. 6Default backwards permutation. IThe values of the index-value pairs are written into the position in the > result array that is indicated by the corresponding index. GAll positions not covered by the index-value pairs will have the value C determined by the initialiser function for that index position. 7-O(1). Zip two arrays into an array of pairs. M If one array is short, excess elements of the longer array are discarded. 81O(1). Zip three arrays into an array of triples. N If one array is short, excess elements of the longer arrays are discarded. 95O(1). Unzip an array of pairs into a pair of arrays. :9O(1). Unzip an array of triples into a triple of arrays. ;4O(1). Take the first elements of an array of pairs. <5O(1). Take the second elements of an array of pairs. =KApply a worker function to each element of an array, yielding a new array. >@Apply a worker function to correponding elements of two 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. K The provided starting element must be neutral with respect to the worker. @ For example 0 is neutral wrt (+) and 1 is neutral wrt (*). AUndirected segmented fold. BAll segments are folded individually, and the result contains one  element for each segment. Same preconditions as @. B%Undirected scattered segmented fold. Like A/, but the segments can be scattered through an . Same preconditions as @. CRegular segmented fold. %All segements have the given length. Same preconditions as @. DBUndirected fold, using the first element to initialise the state. * The worker function must be associative. K 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. ELike A<, but using the first element of each segment to initialise  the state of that segment. Same preconditions as D. FLike B<, but using the first element of each segment to intialise  the state of that segment. Same preconditions as D. GSame as  fold (+) 0 HSame as  fold_r (+) 0 INO(length source). Compute the conjunction of all elements in a boolean array. JO(length result). C Extract elements of an array where the associated flag is true. KCExtract the elements from an array that match the given predicate. LCombine two arrays, C 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]MLike L:, but use a precomputed selector to speed up the process. See the description of O for how this works. N'Interleave the elements of two arrays. interleave [1, 2, 3] [4, 5, 6] = [1, 4, 2, 5, 3, 6]OO(1). Construct a selector. 0A selector is a description of how to perform a L operation. 4Suppose 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]FThis is difficult to parallelise. For each element in the result, the N source array we get this element from depends on the tag values associated  with all previous elements. However, if we going to apply L+ several times with the same flags array, J we can precompute a selector that tells us where to get each element. Q The selector contains the original flags, as well as the source index telling 6 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 CThis 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. P*O(1). Yield the tags array of a selector. Q-O(1). Yield the indices array of a selector. RLO(1). Yield the number of elements that will be taken from the first array. SMO(1). Yield the number of elements that will be taken from the second array. T7O(1). Yield the parallel representation of a selector. U4O(n). Construct a parallel selector representation. A 2 describes how to distribute the two data vectors  corresponding to a  across several PEs. )Suppose we want to perform the following L 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] JThe first array is the flags array, that says which of the data arrays to ( get each successive element from. As L is difficult to compute J in parallel, if we are going to perform several combines with the same M flags array, we can precompute a selector that tells us where to get each L element. The selector contains the original flags, as well as the source D 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] DSuppose we want to distribute the combine operation across 3 PEs. It's & easy to split the selector like so:   5 PE0 PE1 PE2  flags: [F,F,T] [T,F,T] [F,F,T]  indices: [0,1,0] [1,2,2] [3,4,3] KWe now need to split the two data arrays. Each PE needs slices of the data M arrays that correspond to the parts of the selector that were given to it. " For the current example we get:   5 PE0 PE1 PE2  data_A: [A0,A1] [A2] [A3,A4]  data_B: [B0] [B1,B2] [B3] The < contains the starting index and length of each of of these  slices:  5 PE0 PE1 PE2 < ((0, 0), (2, 1)) ((2, 1), (1, 2)) ((3, 3), (2, 1)) : indices lens indices lens indices lens VO(1). Take the indices field from a . WAO(1). Yield the number of elements to take from the first array. XBO(1). Yield the number of elements to take from the second array. YBO(max(segs, threads) . log segs). Construct a segment descriptor. LA segment desciptor defines an irregular 2D array based on a flat, 1D array M 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  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 ZCheck whether a  is well formed. [O(1). Construct an empty . \O(1). Construct a 2 containing a single segment of the given length. ]O(1). Yield the length of a . ^%O(1). Yield the segment lengths of a . _.O(1). Yield the segment starting indices of a . `6O(1). Yield the total number of elements defined by a . a*Construct a Scattered Segment Descriptor. A  is an extension of a % that that allows the segments to be + scattered through multiple flat arrays. AEach segment is associated with a source id that indicates what J flat array it is in, along with the starting index in that flat array. 4 The segments need not cover the entire flat array. 4 Different segments may point to the same elements. bCheck whether a  is well formed. cO(1). Construct an empty . dO(1). Construct a 2 containing a single segment of the given length. eO(segs). Promote a  to a , F assuming all segments are contiguous and come from a single array. fO(1). True when a % has been constructed by promoting a . >In this case all the data elements are in one contiguous flat A array, and consumers can avoid looking at the real starts and  sources fields. gO(1). Yield the length of a . h%O(1). Yield the segment lengths of a . i#O(1). Yield the indices field of a . j"O(1). Yield the starts field of a . k#O(1). Yield the sources field of a . lQO(1). Get the length, segment index, starting index, and source id of a segment. mHProduce a segment descriptor that describes the result of appending two  segmented arrays. n(Construct a Virtual Segment Descriptor. A  is an extension of a & that allows data from the underlying R flat array to be shared between segments. For example, you can define an array J of 10 virtual segments that all have the same length and elements as a  single physical segment. I Internally we maintain the invariant that all physical segments must be Q reachable by some virtual segment. This is needed to ensure that operations  such as B, segmented fold have the right complexity.  If you don'9t need the invariant then you can sidestep the code that O maintains it by using the redundant versions of the following operators, $ and sometimes get faster code. oCheck whether a  is well formed. pO(1). Construct an empty . qO(1). Construct a 2 containing a single segment of the given length. rO(len). Construct a , that describes an array where all virtual 0 segments point to the same physical segment. sO(segs). Promote a plain  to a . CThe result contains one virtual segment for every physical segment  the provided . tO(segs). Promote a plain  to a . CThe result contains one virtual segment for every physical segment  the provided . u:O(1). If true then the segments are all unshared, and the vsegids field  be just  [0..len-1]. 6Consumers can check this field to avoid demanding the vsegids field. I This can avoid the need for it to be constructed in the first place,  due to lazy evaluation. vO(1). If true then the starts field is identical to the indices field ' and the sourceids are all 0s. IIn this case all the data elements are in one contiguous flat array, and F consumers can avoid looking at the real starts and sources fields. wO(1). Yield the length of a . xO(1). Yield the vsegids of a . yO(1). Yield the vsegids of a  , but don't require that every physical 2 segment is referenced by some virtual segment. If you'#re just performing indexing and don't need the invariant that all L physical segments are reachable from some virtual segment, then use this  version as it'@s faster. This sidesteps the code that maintains the invariant. IThe stated O(1) complexity assumes that the array has already been fully M 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. zO(1). Yield the  of a . {O(1). Yield the  of a  , but don't require that every physical 2 segment is referenced by some virtual segment. See the note in y. |%O(1). Yield the segment lengths of a . }BO(1). Get the length, starting index, and source id of a segment. ~ O(segs).  Yield a " that describes each segment of a  individually. ?By doing this we lose information about which virtual segments - correspond to the same physical segments. WARNING: Trying to take the ! of a nested array that has been H constructed with replication can cause index space overflow. This is I because the virtual size of the corresponding flat data can be larger B than physical memory. If this happens then indices fields and 0 element count in the result will be invalid. O(segs). Yield a " that describes each segment of a  individually. ?By doing this we lose information about which virtual segments - correspond to the same physical segments. See the warning in ~.  Update the vsegids of a , and then cull the physical G segment descriptor so that all physical segments are reachable from  some virtual segment.  Update the vsegids of $, where the result is guaranteed to  cover all physical segments. )Using this version avoids performing the cull operation which + discards unreachable physical segments. 9 The resulting vsegids must cover all physical segments. G If they do not then there will be physical segments that are not D reachable from some virtual segment, and subsequent operations  like fold_ss& will have the wrong work complexity. CProduce a virtual segment descriptor that describes the result of # appending two segmented arrays. )Combine two virtual segment descriptors. O(1). Construct an empty  with no elements. O(1). Yield the number of  in an . O(1). Construct an  consisting of a single . O(1). Take one of the outer  from an . (O(1). Retrieve a single element from an , + given the outer and inner indices. O(n). Append two (, using work proportional to the length  of the outer array. O(number of inner arrays).  Convert a boxed vector of  to an . O(number of inner arrays).  Convert an  to a boxed vector of . <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. Write an array to a file. Read an array from a file. (Convert an array to a list of elements. (Convert a list of elements to an array.       data values  tag values the tag of values to select data values that had that tag %Segment descriptor of result aarray. #Segment descriptor of first array. Data of first array. $Segment descriptor of second array. Data of second array. %Segment descriptor of result aarray. #Segment descriptor of first array. Data of first array. $Segment descriptor of second array. Data of second array.  !"&Number of times to repeat the source. 8Length of source (can be less than the provided array). Array elements to repeat. #$%&'()*+, Irregular 2D array of elements. (Maps (segment id, segment index) pairs  to 2D indices in the  &Pairs of (segment id, segment index). -Source array.  Starting index in source array. Length of result array. ./! defining the slices to extract. Source arrays. 0! defining the slices to extract. Source arrays. 12Source array. !Index and value of new elements. 3Source array. 0Indices in the destination to copy elements to. 4Source array. -Indices in the source to copy elements from. 56789:;<=>?@ABCDEFGHIJKLMNO Tags array. Indices array. 2Number of elements taken from first source array. 3Number of elements taken from second source array. "Parallel selector representation. PQRSTUVWXY(lengths) Segment lengths. (indices) Segment indices. Total number of elements. Z[\]^_`a@(starts) Starting index of each segment within its flat array. =(sources) Source id of flat array to get each segment from. ,Plain segment descriptor giving the lengths  of the segments. bcdefghijklmn5(vsegids) Mapping from virtual to physical segments. +Scattered Segment descriptor defining the  physical segments. opqrLength of segment. Number of times replicated. stuvwxyz{|}~Descriptor of first array. 5Number of flat physical arrays for first descriptor. Descriptor of second array. 6Number of flat physical arrays for second descriptor. $Selector for the combine operation. Descriptor of first array. 5Number of flat physical arrays for first descriptor. Descriptor of second array. 6Number of flat physical arrays for second descriptor.       !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~ !"#$%&'()*+,-./0123456789:;<=>     ?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~ !"#$%&'()*+,-./0123456789:;<=>?@ABCBDBEFGFHIIJJKLMNOPQRSST;:AUVWXYZ[\ ] ^ _ ` a b c d e f g h ijklmnopqrstVuvwxyz{|}~;:AZsu;:A ;:A            /                 ;    9   q 2  8 7 A V   u    = 4 y z { | 1 0      %  ' } . ~ p ! " # $ % & ' ( ) * + , - . / 0 1 2 3 4 5 6 7 8 9 : ; < = > ? @ A B C D E F G H I J K L M N O P Q R S T U V W X Y Z [ \ ] ^ _ k l  `ab`acdefghi jklm nopqrstuvwxyz{|}~ooo                 dph-prim-seq-0.7.0.1.Data.Array.Parallel.Unlifted.Sequential.Vector'Data.Array.Parallel.Unlifted.ArrayArray$Data.Array.Parallel.Unlifted.Vectors#Data.Array.Parallel.Unlifted.Stream-Data.Array.Parallel.Unlifted.Sequential.USegd.Data.Array.Parallel.Unlifted.Sequential.USSegd,Data.Array.Parallel.Unlifted.Sequential.USel.Data.Array.Parallel.Unlifted.Sequential.UVSegd'Data.Array.Parallel.Unlifted.SequentialData.Array.Parallel.Unlifted-Data.Array.Parallel.Unlifted.Stream.Segmented'Data.Array.Parallel.Unlifted.Stream.Ixs)Data.Array.Parallel.Unlifted.Stream.Elems,Data.Array.Parallel.Unlifted.Stream.Segments.Data.Array.Parallel.Unlifted.Sequential.Basics3Data.Array.Parallel.Unlifted.Sequential.Combinators,Data.Array.Parallel.Unlifted.Sequential.Sums0Data.Array.Parallel.Unlifted.Sequential.Extractsvector-0.10.0.1Data.Vector.Unboxed.MutablewritereadData.Vector.Unboxedcopy unsafeFreezefromListtoList minIndexByminIndex maxIndexBymaxIndex minimumByminimum maximumBymaximumproductsumorandanyall findIndexfindnotElemelemfilterzipWith3zipWithmapindexedreverseupdate++consenumFromThenTo enumFromTo replicate singletonemptysplitAtdroptaketailnulllengthData.Vector.Unboxed.BaseMVectorVectorUnboxData.Vector.Genericunstreamstream ArrayArrayMutableArrayArray newArrayArraywriteArrayArrayMutwriteArrayArrayreadArrayArrayindexArrayArrayunsafeFreezeArrayArrayunsafeDeepFreezeArrayArraycopyArrayArrayVectorsUnboxes unsafeIndexindex unsafeIndex2index2unsafeIndexUnpackappend fromVectortoVectorindexedSreplicateEachSreplicateEachRS interleaveScombine2ByTagS combineSSenumFromToEachSenumFromStepLenEachSfoldSSfold1SS foldValuesRappendSS indicesSSUIOhPuthGetnewnewMunits interleaverepeatrepeatSslice unsafeSliceextract unsafeExtractmupdatempermutepermutebpermute mbpermute bpermuteDftpackcombine combine2ByTagfoldlfoldl1foldfold1 foldl1Maybe fold1Maybescanlscanl1scanscan1scanResfstssndszipunzipzip3unzip3enumFromStepLenenumFromToEachenumFromStepLenEachrandomrandomRmdropmsliceUSegd usegd_lengths usegd_indicesusegd_elementsmkUSegdvalid fromLengths takeLengths takeIndices takeElementsgetSegUSSegdussegd_contiguous ussegd_startsussegd_sources ussegd_usegdmkUSSegd fromUSegd isContiguous takeUSegd takeStarts takeSources appendWith cullOnVSegidsstreamSrcIxsThroughVSegidsstreamSrcIxsThroughUSSegdUSel2 usel2_tags usel2_indicesusel2_elements0usel2_elements1mkUSel2 lengthUSel2 tagsUSel2 indicesUSel2elementsUSel2_0elementsUSel2_1tagsToIndices2UVSegduvsegd_manifestuvsegd_vsegids_redundantuvsegd_vsegids_culleduvsegd_ussegd_redundantuvsegd_ussegd_culledmkUVSegd fromUSSegd replicated isManifest takeVSegidstakeVSegidsRedundant takeUSSegdtakeUSSegdRedundantunsafeDemoteToUSSegdunsafeDemoteToUSegd updateVSegsupdateVSegsReachablecombine2streamElemsFromVectorstreamElemsFromVectorsstreamElemsFromVectorsVSegdstreamSegsFromNestedUSSegdstreamSegsFromVectorsUSSegdstreamSegsFromVectorsUVSegd!streamSegsFromVectorsUSSegdSegmap!streamSegsFromVectorsUSSegd_split replicateSU replicateRSUappendSU indicesSU indicesSU'foldlSUfoldlSSUfoldSUfoldSSUfoldl1SU foldl1SSUfold1SUfold1SSUfoldlRU combineSUandSUorSUsumSU productSU maximumSU minimumSUsumRUindexsFromVectorindexsFromVectorsUVSegdextractsFromNestedUSSegdextractsFromVectorsUSSegdextractsFromVectorsUVSegdIOEltArraysEltsVSegdSSegdSegdSelRep2Sel2ArrayEltgeneratezipWith4zipWith5zipWith6zipWith7zipWith8fold_vsfold1_vssum_ssum_sscountcount_scount_ss packByTagpick tagsToSel2 lengthsToSegdplusSegd+:+append_s append_vs replicate_s replicate_rs indices_sindexs indexs_avs extracts_nss extracts_ass extracts_avsfold_sfold_ssfold_rfold1_sfold1_sssum_rmkSel2tagsSel2 indicesSel2elementsSel2_0elementsSel2_1repSel2 mkSelRep2indicesSelRep2elementsSelRep2_0elementsSelRep2_1mkSegd validSegd emptySegd singletonSegd lengthSegd lengthsSegd indicesSegd elementsSegdmkSSegd validSSegd emptySSegdsingletonSSegdpromoteSegdToSSegdisContiguousSSegd lengthOfSSegdlengthsOfSSegdindicesOfSSegd startsOfSSegdsourcesOfSSegd getSegOfSSegd appendSSegdmkVSegd validVSegd emptyVSegdsingletonVSegdreplicatedVSegdpromoteSegdToVSegdpromoteSSegdToVSegdisManifestVSegdisContiguousVSegd lengthOfVSegdtakeVSegidsOfVSegdtakeVSegidsRedundantOfVSegdtakeSSegdOfVSegdtakeSSegdRedundantOfVSegdtakeLengthsOfVSegd getSegOfVSegdunsafeDemoteToSSegdOfVSegdunsafeDemoteToSegdOfVSegdupdateVSegsOfVSegdupdateVSegsReachableOfVSegd appendVSegd combine2VSegdemptyslengths singletons unsafeIndexs unsafeIndex2sappends fromVectors toVectorsrandomsrandomRsprimitive-0.5.0.1Data.Primitive.ByteArrayMutableByteArray ByteArray unpackUVector $fShowVectors$fUnboxesDouble$fUnboxesFloat$fUnboxesWord8 $fUnboxesIntmultSizebaseGHC.ErrerrordivSizehere bpermuteS mbpermuteSrandomSrandomRS hGetStorable hPutStorableprimPutprimGet fromOrdering toOrdering$fVectorVectorInteger$fMVectorMVectorInteger$fUnboxInteger$fVectorVectorOrdering$fMVectorMVectorOrdering$fUnboxOrdering$fUIO(,) $fUIODouble$fUIOInt$fPprPhysicalUSegd$fPprPhysicalUSSegd mapAccumS$fPprPhysicalUVSegdextractsFromVectorsUSSegdSegmapgenerate_cheap dph_mod_indexdph_plus tagZeroes $fIOElt(,) $fIOEltDouble $fIOEltInt $fEltsDouble $fEltsFloat $fEltsWord8 $fEltsInt$fElt(,) $fEltDouble $fEltFloat $fEltBool $fEltWord8$fEltInt