-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | Data Parallel Haskell segmented arrays. (abstract interface)
--   
--   Empty implementation of flat parallel arrays. This package exists only
--   so that dph-prim-par and dph-prim-seq can provide the same interface.
@package dph-prim-interface
@version 0.6.0.1


-- | WARNING: This is an abstract interface. All the functions will just
--   <tt>error</tt> if called.
--   
--   This module provides an API for the segmented array primitives used by
--   DPH. None of the functions here have implementations.
--   
--   Client programs should use either the <tt>dph-prim-seq</tt> or
--   <tt>dph-prim-par</tt> packages, as these provide the same API and
--   contain real code.
module Data.Array.Parallel.Unlifted
class Elt a
type Array a = [a]

-- | O(1). Construct an array with no elements.
empty :: Elt a => Array a

-- | Generate a new array given its length and a function to compute each
--   element.
generate :: Elt a => Int -> (Int -> a) -> Array a

-- | O(length result). Construct a new array by replicating a single
--   element the given number of times.
replicate :: Elt a => Int -> a -> Array a

-- | O(length result). Segmented replicate.
--   
--   Elements of the array are replicated according to the lengths of the
--   segments defined by the <a>Segd</a>.
replicate_s :: Elt a => Segd -> Array a -> Array a

-- | O(length result). Regular segmented replicate.
--   
--   Like <a>replicate_s</a>, but all segments are assumed to have the
--   given length.
replicate_rs :: Elt a => Int -> Array a -> Array a

-- | O(length result). Construct an array by copying a portion of another
--   array.
repeat :: Elt a => Int -> Int -> Array a -> Array a

-- | O(length result). Tag each element of an array with its index.
--   
--   <pre>
--   indexed [42, 93, 13] = [(0, 42), (1, 93), (2, 13)]
--   </pre>
indexed :: Elt a => Array a -> Array (Int, a)

-- | O(length result). Append two arrays.
(+:+) :: Elt a => Array a -> Array a -> Array a

-- | O(length result). Segmented append.
append_s :: Elt a => Segd -> Segd -> Array a -> Segd -> Array a -> Array a

-- | O(length result). Segmented indices.
--   
--   Construct an array containing containing the segments defined by the
--   given <a>Segd</a>.
--   
--   Each segment will contain the elements <tt>[0..len-1]</tt> where
--   <tt>len</tt> is the length of that segment.
indices_s :: Segd -> Array Int
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

-- | O(1). Yield the number of elements in an array.
length :: Elt a => Array a -> Int

-- | O(1). Retrieve a numbered element from an array.
--   
--   The first argument gives a source-code location for out-of-bounds
--   errors.
index :: Elt a => String -> Array a -> Int -> a

-- | O(length result). Scattered indexing from a single <a>Array</a>.
--   
--   This is an alias for <a>bpermute</a>.
indexs :: Elt a => Array a -> Array Int -> Array a

-- | O(length result). Scattered indexing through a <a>VSegd</a>.
--   
--   The index array contains pairs of segment id and the index within that
--   segment.
--   
--   We use the <a>VSegd</a> to map the pairs to 2D indices within the
--   <a>Arrays</a>, and return an array of the resulting elements.
indexs_avs :: (Elt a, Elts a) => Arrays a -> VSegd -> Array (Int, Int) -> Array a

-- | O(length result). Extract a subrange of elements from an array.
--   
--   <pre>
--   extract [23, 42, 93, 50, 27] 1 3  = [42, 93, 50]
--   </pre>
extract :: Elt a => Array a -> Int -> Int -> Array a

-- | O(length result). Extract segments defined by a <a>SSegd</a> from a
--   vector of arrays.
--   
--   NOTE: This is a transitory interface, and will be removed in future
--   versions. Use <a>extracts_ass</a> instead.
extracts_nss :: Elt a => SSegd -> Vector (Array a) -> Array a

-- | O(length result). Extract segments defined by a <a>SSegd</a>.
--   
--   Extract all the segments defined by the <a>SSegd</a> from the
--   <a>Arrays</a>, returning them concatenated in a fresh <a>Array</a>.
extracts_ass :: (Elt a, Elts a) => SSegd -> Arrays a -> Array a

-- | O(length result). Extract segments defined by a <a>VSegd</a>.
--   
--   Extract all the segments defined by the <a>VSegd</a> from the
--   <a>Arrays</a>, returning them concatenated in a fresh <a>Array</a>.
extracts_avs :: (Elt a, Elts a) => VSegd -> Arrays a -> Array a

-- | O(length result). Drop elements from the front of an array, returning
--   the latter portion.
drop :: Elt a => Int -> Array a -> Array a

-- | O(length result). Copy the source array while replacing some elements
--   by new ones in the result.
update :: Elt a => Array a -> Array (Int, a) -> Array a

-- | O(length result). Forwards permutation of array elements.
permute :: Elt a => Array a -> Array Int -> Array a

-- | O(length result). Backwards permutation of array elements.
--   
--   <pre>
--   bpermute [50, 60, 20, 30] [0, 3, 2] = [50, 30, 20]
--   </pre>
bpermute :: Elt a => Array a -> Array Int -> Array a

-- | 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.
mbpermute :: (Elt a, Elt b) => (a -> b) -> Array a -> Array Int -> Array b

-- | 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.
bpermuteDft :: Elt e => Int -> (Int -> e) -> Array (Int, e) -> Array e

-- | O(1). Zip two arrays into an array of pairs. If one array is short,
--   excess elements of the longer array are discarded.
zip :: (Elt a, Elt b) => Array a -> Array b -> Array (a, b)

-- | O(1). Zip three arrays into an array of triples. If one array is
--   short, excess elements of the longer arrays are discarded.
zip3 :: (Elt a, Elt b, Elt c) => Array a -> Array b -> Array c -> Array (a, b, c)

-- | O(1). Unzip an array of pairs into a pair of arrays.
unzip :: (Elt a, Elt b) => Array (a, b) -> (Array a, Array b)

-- | O(1). Unzip an array of triples into a triple of arrays.
unzip3 :: (Elt a, Elt b, Elt c) => Array (a, b, c) -> (Array a, Array b, Array c)

-- | O(1). Take the first elements of an array of pairs.
fsts :: (Elt a, Elt b) => Array (a, b) -> Array a

-- | O(1). Take the second elements of an array of pairs.
snds :: (Elt a, Elt b) => Array (a, b) -> Array b

-- | Apply a worker function to each element of an array, yielding a new
--   array.
map :: (Elt a, Elt b) => (a -> b) -> Array a -> Array b

-- | Apply a worker function to correponding elements of two arrays.
zipWith :: (Elt a, Elt b, Elt c) => (a -> b -> c) -> Array a -> Array b -> Array c

-- | Apply a worker function to corresponding elements of three 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 four 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

-- | Similar to <tt>foldl</tt> but return an array of the intermediate
--   states, including the final state that is computed by <tt>foldl</tt>.
scan :: Elt a => (a -> a -> a) -> a -> Array a -> Array a

-- | Undirected fold over an array.
--   
--   <ul>
--   <li>The worker function must be associative.</li>
--   <li>The provided starting element must be neutral with respect to the
--   worker. For example 0 is neutral wrt (+) and 1 is neutral wrt
--   (*).</li>
--   </ul>
fold :: Elt a => (a -> a -> a) -> a -> Array a -> a

-- | Undirected segmented fold.
--   
--   All segments are folded individually, and the result contains one
--   element for each segment.
--   
--   Same preconditions as <a>fold</a>.
fold_s :: Elt a => (a -> a -> a) -> a -> Segd -> Array a -> Array a

-- | Undirected scattered segmented fold.
--   
--   Like <a>fold_s</a>, but the segments can be scattered through an
--   <a>Arrays</a>.
--   
--   Same preconditions as <a>fold</a>.
fold_ss :: (Elts a, Elt a) => (a -> a -> a) -> a -> SSegd -> Arrays a -> Array a

-- | Undirected fold over virtual segments.
--   
--   The physical segments defined by the <a>VSegd</a> are folded
--   individually, and these results are replicated according to the
--   virtual segment id table of the <a>VSegd</a>. The result contains as
--   many elements as there virtual segments.
--   
--   Same preconditions as <a>fold</a>.
fold_vs :: (Elts a, Elt a) => (a -> a -> a) -> a -> VSegd -> Arrays a -> Array a

-- | Regular segmented fold.
--   
--   All segements have the given length.
--   
--   Same preconditions as <a>fold</a>.
fold_r :: Elt a => (a -> a -> a) -> a -> Int -> Array a -> Array a

-- | Undirected fold, using the first element to initialise the state.
--   
--   <ul>
--   <li>The worker function must be associative.</li>
--   <li>The provided starting element must be neutral with respect to the
--   worker. For example 0 is neutral wrt (+) and 1 is neutral wrt
--   (*).</li>
--   <li>If the array contains no elements then you'll get a bounds check
--   <tt>error</tt>.</li>
--   </ul>
fold1 :: Elt a => (a -> a -> a) -> Array a -> a

-- | Like <a>fold_s</a>, but using the first element of each segment to
--   initialise the state of that segment.
--   
--   Same preconditions as <a>fold1</a>.
fold1_s :: Elt a => (a -> a -> a) -> Segd -> Array a -> Array a

-- | Like <a>fold_ss</a>, but using the first element of each segment to
--   intialise the state of that segment.
--   
--   Same preconditions as <a>fold1</a>.
fold1_ss :: (Elts a, Elt a) => (a -> a -> a) -> SSegd -> Arrays a -> Array a

-- | Like <a>fold_vs</a>, but using the first element of each segment to
--   initialise the state of that segment.
--   
--   Same preconditions as <a>fold1</a>.
fold1_vs :: (Elts a, Elt a) => (a -> a -> a) -> VSegd -> Arrays a -> Array a

-- | Same as <tt>fold (+) 0</tt>
sum :: (Num a, Elt a) => Array a -> a

-- | Same as <tt>fold_s (+) 0</tt>
sum_s :: (Num a, Elt a) => Segd -> Array a -> Array a

-- | Same as <tt>fold_ss (+) 0</tt>
sum_ss :: (Num a, Elts a, Elt a) => SSegd -> Arrays a -> Array a

-- | Same as <tt>fold_r (+) 0</tt>
sum_r :: (Num a, Elt a) => Int -> Array a -> Array a

-- | Count the number of elements in array that are equal to the given
--   value.
count :: (Elt a, Eq a) => Array a -> a -> Int

-- | Segmented count.
count_s :: (Elt a, Eq a) => Segd -> Array a -> a -> Array Int

-- | Scattered segmented count.
--   
--   NOTE: This is a transitory interface, and will be removed in future
--   versions.
count_ss :: (Elt a, Eq a) => SSegd -> Vector (Array a) -> a -> Array Int

-- | O(length source). Compute the conjunction of all elements in a boolean
--   array.
and :: Array Bool -> Bool

-- | O(length result). Extract elements of an array where the associated
--   flag is true.
pack :: Elt a => Array a -> Array Bool -> Array a

-- | O(length result). Select the elements of an array that have a
--   corresponding tag.
--   
--   <pre>
--   packByTag [12, 24, 42, 93] [1, 0, 0, 1] 0 = [24, 42]
--   </pre>
packByTag :: Elt a => Array a -> Array Tag -> Tag -> Array a

-- | Extract the elements from an array that match the given predicate.
filter :: Elt a => (a -> Bool) -> Array a -> Array a

-- | Compute an array of flags indicating which elements match a given
--   value.
--   
--   <pre>
--   pick [4, 5, 3, 6, 5, 2, 5] 5 = [F, T, F, F, T, F, T]
--   </pre>
pick :: (Elt a, Eq a) => Array a -> a -> Array Bool

-- | Combine two arrays, using a flags array to tell us where to get each
--   element from.
--   
--   <pre>
--   combine [T, F, F, T, T, F] [1, 2, 3] [4, 5, 6] = [1, 4, 5, 2, 3, 6]
--   </pre>
combine :: Elt a => Array Bool -> Array a -> Array a -> Array a

-- | Like <a>combine</a>, but use a precomputed selector to speed up the
--   process.
--   
--   See the description of <a>mkSel2</a> for how this works.
combine2 :: Elt a => Array Tag -> SelRep2 -> Array a -> Array a -> Array a

-- | Interleave the elements of two arrays.
--   
--   <pre>
--   interleave [1, 2, 3] [4, 5, 6] = [1, 4, 2, 5, 3, 6]
--   </pre>
interleave :: Elt a => Array a -> Array a -> Array a
data Sel2

-- | O(1). Construct a selector.
--   
--   A selector is a description of how to perform a <a>combine</a>
--   operation.
--   
--   Suppose we are evaluating the following expression:
--   
--   <pre>
--   combine [F,F,T,F,T,T] [1,2,3] [4,5,6] = [4,5,1,6,2,3]
--   </pre>
--   
--   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 <a>combine</a> 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:
--   
--   <pre>
--   tagsToIndices2 [F,F,T,F,T,T]   -- tags
--                = [0,1,0,2,1,2]   -- indices
--   </pre>
--   
--   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 <tt>tag</tt> and
--   <tt>indices</tt> arrays.
mkSel2 :: Array Tag -> Array Int -> Int -> Int -> SelRep2 -> Sel2

-- | O(1). Yield the tags array of a selector.
tagsSel2 :: Sel2 -> Array Tag

-- | O(1). Yield the indices array of a selector.
indicesSel2 :: Sel2 -> Array Int

-- | O(1). Yield the number of elements that will be taken from the first
--   array.
elementsSel2_0 :: Sel2 -> Int

-- | O(1). Yield the number of elements that will be taken from the second
--   array.
elementsSel2_1 :: Sel2 -> Int

-- | O(1). Yield the parallel representation of a selector.
repSel2 :: Sel2 -> SelRep2

-- | O(n). Compute a selector from a tags array.
tagsToSel2 :: Array Tag -> Sel2
type SelRep2 = ()

-- | O(n). Construct a parallel selector representation.
--   
--   A <a>SelRep2</a> describes how to distribute the two data vectors
--   corresponding to a <a>Sel2</a> across several PEs.
--   
--   Suppose we want to perform the following <a>combine</a> operation:
--   
--   <pre>
--   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]
--   </pre>
--   
--   The first array is the flags array, that says which of the data arrays
--   to get each successive element from. As <a>combine</a> 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.
--   
--   <pre>
--   flags:   [F,F,T,T,F,T,F,F,T]
--   indices: [0,1,0,1,2,2,3,4,3]
--   </pre>
--   
--   Suppose we want to distribute the combine operation across 3 PEs. It's
--   easy to split the selector like so:
--   
--   <pre>
--              PE0                PE1               PE2
--   flags:   [F,F,T]            [T,F,T]           [F,F,T] 
--   indices: [0,1,0]            [1,2,2]           [3,4,3]
--   </pre>
--   
--   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:
--   
--   <pre>
--              PE0                PE1               PE2
--   data_A:   [A0,A1]            [A2]              [A3,A4]
--   data_B:   [B0]               [B1,B2]           [B3]
--   </pre>
--   
--   The <a>SelRep2</a> contains the starting index and length of each of
--   of these slices:
--   
--   <pre>
--         PE0                PE1               PE2
--   ((0, 0), (2, 1))   ((2, 1), (1, 2))  ((3, 3), (2, 1))
--    indices   lens      indices  lens    indices  lens
--   </pre>
mkSelRep2 :: Array Tag -> SelRep2

-- | O(1). Take the <tt>indices</tt> field from a <a>SelRep2</a>.
indicesSelRep2 :: Array Tag -> SelRep2 -> Array Int

-- | O(1). Yield the number of elements to take from the first array.
elementsSelRep2_0 :: Array Tag -> SelRep2 -> Int

-- | O(1). Yield the number of elements to take from the second array.
elementsSelRep2_1 :: Array Tag -> SelRep2 -> Int
data 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.
--   
--   <ul>
--   <li>The starting indices must be equal to <tt>init (scanl (+) 0
--   lengths)</tt></li>
--   <li>If you don't want to cover all the elements from the flat arrary
--   then use a <a>SSegd</a> instead.</li>
--   </ul>
--   
--   Example:
--   
--   <pre>
--   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 
--   </pre>
mkSegd :: Array Int -> Array Int -> Int -> Segd

-- | Check whether a <a>Segd</a> is well formed.
validSegd :: Segd -> Bool

-- | O(1). Construct an empty <a>Segd</a>.
emptySegd :: Segd

-- | O(1). Construct a <a>Segd</a> containing a single segment of the given
--   length.
singletonSegd :: Int -> Segd

-- | O(max(segs, threads) . log segs). Construct a <a>Segd</a> from an
--   array of segment lengths.
lengthsToSegd :: Array Int -> Segd

-- | O(1). Yield the length of a <a>Segd</a>.
lengthSegd :: Segd -> Int

-- | O(1). Yield the segment lengths of a <a>Segd</a>.
lengthsSegd :: Segd -> Array Int

-- | O(1). Yield the segment starting indices of a <a>Segd</a>.
indicesSegd :: Segd -> Array Int

-- | O(1). Yield the total number of elements defined by a <a>Segd</a>.
elementsSegd :: Segd -> Int

-- | O(max(segs, threads) . log segs). Add the lengths of corresponding
--   segments in two descriptors.
--   
--   <pre>
--   plusSegd [lens: 2 3 1] [lens: 3 1 1] = [lens: 5 4 2]
--   </pre>
plusSegd :: Segd -> Segd -> Segd
data SSegd

-- | Construct a Scattered Segment Descriptor.
--   
--   A <a>SSegd</a> is an extension of a <a>Segd</a> 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.
--   
--   <ul>
--   <li>The segments need not cover the entire flat array.</li>
--   <li>Different segments may point to the same elements.</li>
--   </ul>
mkSSegd :: Array Int -> Array Int -> Segd -> SSegd

-- | Check whether a <a>Segd</a> is well formed.
validSSegd :: SSegd -> Bool

-- | O(1). Construct an empty <a>SSegd</a>.
emptySSegd :: SSegd

-- | O(1). Construct a <a>Segd</a> containing a single segment of the given
--   length.
singletonSSegd :: Int -> SSegd

-- | O(segs). Promote a <a>Segd</a> to a <a>SSegd</a>, assuming all
--   segments are contiguous and come from a single array.
promoteSegdToSSegd :: Segd -> SSegd

-- | O(1). True when a <a>SSegd</a> has been constructed by promoting a
--   <a>SSegd</a>.
--   
--   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.
isContiguousSSegd :: SSegd -> Bool

-- | O(1). Yield the length of a <a>SSegd</a>.
lengthOfSSegd :: SSegd -> Int

-- | O(1). Yield the segment lengths of a <a>SSegd</a>.
lengthsOfSSegd :: SSegd -> Array Int

-- | O(1). Yield the indices field of a <a>SSegd</a>.
indicesOfSSegd :: SSegd -> Array Int

-- | O(1). Yield the starts field of a <a>SSegd</a>.
startsOfSSegd :: SSegd -> Array Int

-- | O(1). Yield the sources field of a <a>SSegd</a>.
sourcesOfSSegd :: SSegd -> Array Int

-- | O(1). Get the length, segment index, starting index, and source id of
--   a segment.
getSegOfSSegd :: SSegd -> Int -> (Int, Int, Int, Int)

-- | Produce a segment descriptor that describes the result of appending
--   two segmented arrays.
appendSSegd :: SSegd -> Int -> SSegd -> Int -> SSegd
data VSegd

-- | Construct a Virtual Segment Descriptor.
--   
--   A <a>VSegd</a> is an extension of a <a>SSegd</a> 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.
--   
--   <ul>
--   <li>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 <a>fold_ss</a> segmented fold have the right
--   complexity.</li>
--   <li>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.</li>
--   </ul>
mkVSegd :: Array Int -> SSegd -> VSegd

-- | Check whether a <a>Segd</a> is well formed.
validVSegd :: VSegd -> Bool

-- | O(1). Construct an empty <a>SSegd</a>.
emptyVSegd :: VSegd

-- | O(1). Construct a <a>VSegd</a> containing a single segment of the
--   given length.
singletonVSegd :: Int -> VSegd

-- | O(len). Construct a <a>VSegd</a> that describes an array where all
--   virtual segments point to the same physical segment.
replicatedVSegd :: Int -> Int -> VSegd

-- | O(segs). Promote a plain <a>Segd</a> to a <a>VSegd</a>.
--   
--   The result contains one virtual segment for every physical segment the
--   provided <a>Segd</a>.
promoteSegdToVSegd :: Segd -> VSegd

-- | O(segs). Promote a plain <a>SSegd</a> to a <a>VSegd</a>.
--   
--   The result contains one virtual segment for every physical segment the
--   provided <a>SSegd</a>.
promoteSSegdToVSegd :: SSegd -> VSegd

-- | O(1). If true then the segments are all unshared, and the
--   <tt>vsegids</tt> field be just <tt>[0..len-1]</tt>.
--   
--   Consumers can check this field to avoid demanding the <tt>vsegids</tt>
--   field. This can avoid the need for it to be constructed in the first
--   place, due to lazy evaluation.
isManifestVSegd :: VSegd -> Bool

-- | O(1). If true then the <tt>starts</tt> field is identical to the
--   <tt>indices</tt> 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.
isContiguousVSegd :: VSegd -> Bool

-- | O(1). Yield the length of a <a>VSegd</a>.
lengthOfVSegd :: VSegd -> Int

-- | O(1). Yield the vsegids of a <a>VSegd</a>.
takeVSegidsOfVSegd :: VSegd -> Array Int

-- | O(1). Yield the vsegids of a <a>VSegd</a>, 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 <tt>vsegids</tt>, thus
--   reducing the cost attributed to that prior computation.
takeVSegidsRedundantOfVSegd :: VSegd -> Array Int

-- | O(1). Yield the <a>SSegd</a> of a <a>VSegd</a>.
takeSSegdOfVSegd :: VSegd -> SSegd

-- | O(1). Yield the <a>SSegd</a> of a <a>VSegd</a>, but don't require that
--   every physical segment is referenced by some virtual segment.
--   
--   See the note in <a>takeVSegidsRedundantOfVSegd</a>.
takeSSegdRedundantOfVSegd :: VSegd -> SSegd

-- | O(1). Yield the segment lengths of a <a>VSegd</a>.
takeLengthsOfVSegd :: VSegd -> Array Int

-- | O(1). Get the length, starting index, and source id of a segment.
getSegOfVSegd :: VSegd -> Int -> (Int, Int, Int)

-- | O(segs). Yield a <a>SSegd</a> that describes each segment of a
--   <a>VSegd</a> individually.
--   
--   By doing this we lose information about which virtual segments
--   correspond to the same physical segments.
--   
--   <i>WARNING</i>: Trying to take the <a>SSegd</a> 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.
unsafeDemoteToSSegdOfVSegd :: VSegd -> SSegd

-- | O(segs). Yield a <a>Segd</a> that describes each segment of a
--   <a>VSegd</a> individually.
--   
--   By doing this we lose information about which virtual segments
--   correspond to the same physical segments.
--   
--   See the warning in <a>unsafeDemoteToSSegdOfVSegd</a>.
unsafeDemoteToSegdOfVSegd :: VSegd -> Segd

-- | Update the <tt>vsegids</tt> of a <a>VSegd</a>, and then cull the
--   physical segment descriptor so that all physical segments are
--   reachable from some virtual segment.
updateVSegsOfVSegd :: (Array Int -> Array Int) -> VSegd -> VSegd

-- | Update the <tt>vsegids</tt> of <a>VSegd</a>, where the result is
--   guaranteed to cover all physical segments.
--   
--   Using this version avoids performing the <tt>cull</tt> operation which
--   discards unreachable physical segments.
--   
--   <ul>
--   <li>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 <tt>fold_ss</tt>
--   will have the wrong work complexity.</li>
--   </ul>
updateVSegsReachableOfVSegd :: (Array Int -> Array Int) -> VSegd -> VSegd

-- | Produce a virtual segment descriptor that describes the result of
--   appending two segmented arrays.
appendVSegd :: VSegd -> Int -> VSegd -> Int -> VSegd

-- | Combine two virtual segment descriptors.
combine2VSegd :: Sel2 -> VSegd -> Int -> VSegd -> Int -> VSegd
class Elts a
type Arrays a = [[a]]

-- | O(1). Construct an empty <a>Arrays</a> with no elements.
emptys :: Arrays a

-- | O(1). Construct an <a>Arrays</a> consisting of a single <a>Array</a>.
singletons :: (Elt a, Elts a) => Array a -> Arrays a

-- | O(1). Yield the number of <a>Array</a> in an <a>Arrays</a>.
lengths :: Elts a => Arrays a -> Int

-- | O(1). Take one of the outer <a>Array</a> from an <a>Arrays</a>.
unsafeIndexs :: (Elt a, Elts a) => Arrays a -> Int -> Array a

-- | O(1). Retrieve a single element from an <a>Arrays</a>, given the outer
--   and inner indices.
unsafeIndex2s :: (Elt a, Elts a) => Arrays a -> Int -> Int -> a

-- | O(n). Append two <a>Arrays</a>, using work proportional to the length
--   of the outer array.
appends :: (Elt a, Elts a) => Arrays a -> Arrays a -> Arrays a

-- | O(number of inner arrays). Convert a boxed vector of <a>Array</a> to
--   an <a>Arrays</a>.
fromVectors :: (Elt a, Elts a) => Vector (Array a) -> Arrays a

-- | O(number of inner arrays). Convert an <a>Arrays</a> to a boxed vector
--   of <a>Array</a>.
toVectors :: (Elt a, Elts a) => Arrays a -> Vector (Array a)

-- | Generate an array of the given length full of random data. Good for
--   testing.
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
class Elt a => IOElt a

-- | Read an array from a file.
hGet :: IOElt a => Handle -> IO (Array a)

-- | Write an array to a file.
hPut :: IOElt a => Handle -> Array a -> IO ()

-- | Convert an array to a list of elements.
toList :: Elt a => Array a -> [a]

-- | Convert a list of elements to an array.
fromList :: Elt a => [a] -> Array a
instance Elt a => Elt [a]
instance (IOElt a, IOElt b) => IOElt (a, b)
instance IOElt Double
instance IOElt Int
instance Elts Double
instance Elts Float
instance Elts Word8
instance Elts Int
instance (Elt a, Elt b) => Elt (a, b)
instance Elt Double
instance Elt Float
instance Elt Bool
instance Elt Word8
instance Elt Int