import Data.Array.Parallel.Base (Tag, tagToInt, fromBool)
import qualified GHC.Base
import Prelude ((.), ($), Num(..), Eq(..), seq, snd)
import qualified Prelude
instance Elt Int
instance Elt Word8
instance Elt Bool
instance Elt Float
instance Elt Double
instance (Elt a, Elt b) => Elt (a, b)
instance Elts Int
instance Elts Word8
instance Elts Float
instance Elts Double
infixl 9 `index`
infixr 5 +:+
-- TRAGIC HACKS ===============================================================
-- These hacky rules solve the replicate problem for the SMVM benchmark,
-- with dph-lifted-copy but are very fragile and ad-hoc.
--
-- Programs written with the new dph-lifted-vseg library don't need rules like
-- this, so we should dump them at some stage.
{-# RULES
"map/zipWith (+)/enumFromStepLen" forall m n is.
map (dph_mod_index m) (zipWith ((+) :: Int -> Int -> Int)
(enumFromStepLen 0 m n) is)
= map (dph_mod_index m) is
"map dph_mod_index/enumFromStepLenEach" forall k l is n1 n2.
map (dph_mod_index k)
(enumFromStepLenEach l is (replicate n1 (GHC.Base.I# 1#)) (replicate n2 k))
= enumFromStepLenEach l (map (dph_mod_index k) is)
(replicate n1 (GHC.Base.I# 1#))
(replicate n2 k)
"map dph_mod_index/replicate_s" forall k segd xs.
map (dph_mod_index k) (replicate_s segd xs)
= replicate_s segd (map (dph_mod_index k) xs)
"map dph_mod_index/enumFromStepLen" forall k# i n.
map (dph_mod_index (GHC.Base.I# k#)) (enumFromStepLen i (GHC.Base.I# k#) n)
= replicate n i
"enumFromStepLenEach/replicate x 3" forall k m n1 n2 n3.
enumFromStepLenEach m (replicate n1 (GHC.Base.I# 0#))
(replicate n2 (GHC.Base.I# 1#))
(replicate n3 k)
= generate_cheap m (dph_mod_index k)
"bpermute/generate_cheap" forall n f xs.
bpermute (generate_cheap n f) xs
= map f xs
#-}
-- ============================================================================
-- Constructors ===============================================================
-- | O(1). Construct an array with no elements.
empty :: Elt a => Array a
{-# INLINE_BACKEND empty #-}
-- Generate ---------------------------
-- | Generate a new array given its length and a function to compute each element.
generate :: Elt a => Int -> (Int -> a) -> Array a
generate n f = map f (enumFromTo 0 (n-1))
{-# INLINE_BACKEND generate #-}
generate_cheap :: Elt a => Int -> (Int -> a) -> Array a
generate_cheap n f = map f (enumFromTo 0 (n-1))
{-# INLINE_BACKEND generate_cheap #-}
-- Replicate --------------------------
-- | O(length result).
-- Construct a new array by replicating a single element the given
-- number of times.
replicate :: Elt a => Int -> a -> Array a
{-# INLINE CONLIKE PHASE_BACKEND replicate #-}
{-# RULES
"seq/replicate" forall n x y.
seq (replicate n x) y = n `seq` x `seq` y
#-}
-- | O(length result). Segmented replicate.
--
-- Elements of the array are replicated according to the lengths of the
-- segments defined by the `Segd`.
replicate_s :: Elt a => Segd -> Array a -> Array a
{-# INLINE CONLIKE PHASE_BACKEND replicate_s #-}
-- | O(length result). Regular segmented replicate.
--
-- Like `replicate_s`, but all segments are assumed to have the given length.
replicate_rs :: Elt a => Int -> Array a -> Array a
{-# INLINE CONLIKE PHASE_BACKEND replicate_rs #-}
{-# RULES
"replicate_s/replicate"
forall segd k x
. replicate_s segd (replicate k x)
= replicate (elementsSegd segd) x
"replicate_s->replicate_rs"
forall n m idxs nm xs
. replicate_s (mkSegd (replicate n m) idxs nm) xs
= replicate_rs m xs
"replicate_rs/replicate"
forall m n x
. replicate_rs m (replicate n x) = replicate (m*n) x
#-}
-- Repeat -----------------------------
-- | O(length result). Construct an array by copying a portion of another array.
repeat :: 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
{-# INLINE_BACKEND repeat #-}
{-# RULES
"repeat/enumFromStepLen[Int]" forall i j k n len.
repeat n len (enumFromStepLen i j k)
= generate_cheap len (\m -> i + ((m `Prelude.rem` k) * j))
#-}
-- Append -----------------------------
-- | O(length result). Append two arrays.
(+:+) :: Elt a => Array a -> Array a -> Array a
{-# INLINE_BACKEND (+:+) #-}
-- | O(length result). Segmented append.
append_s
:: 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
{-# INLINE_BACKEND append_s #-}
{-# RULES
"append_s->interleave" forall n k idxs1 idxs2 idxs3 m1 m2 m3 xs ys.
append_s (mkSegd (replicate n k) idxs1 m1)
(mkSegd (replicate n (GHC.Base.I# 1#)) idxs2 m2) xs
(mkSegd (replicate n (GHC.Base.I# 1#)) idxs3 m3) ys
= interleave xs ys
#-}
append_vs
:: (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
{-# INLINE_BACKEND append_vs #-}
-- Indexed ----------------------------
-- | O(length result). Tag each element of an array with its index.
--
-- @indexed [42, 93, 13] = [(0, 42), (1, 93), (2, 13)]@
indexed :: Elt a => Array a -> Array (Int, a)
{-# INLINE_BACKEND indexed #-}
-- Indices ----------------------------
-- | 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.
indices_s :: Segd -> Array Int
{-# INLINE_BACKEND indices_s #-}
-- Enumerations -----------------------
enumFromTo :: Int -> Int -> Array Int
{-# INLINE_BACKEND enumFromTo #-}
enumFromThenTo :: Int -> Int -> Int -> Array Int
{-# INLINE_BACKEND enumFromThenTo #-}
enumFromStepLen :: Int -> Int -> Int -> Array Int
{-# INLINE_BACKEND enumFromStepLen #-}
enumFromStepLenEach :: Int -> Array Int -> Array Int -> Array Int -> Array Int
{-# INLINE_BACKEND enumFromStepLenEach #-}
-- Projections ================================================================
-- | O(1). Yield the number of elements in an array.
length :: Elt a => Array a -> Int
{-# INLINE_BACKEND length #-}
-- | 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 => Prelude.String -> Array a -> Int -> a
{-# INLINE_BACKEND index #-}
-- | O(length result). Scattered indexing from a single `Array`.
--
-- This is an alias for `bpermute`.
indexs :: Elt a
=> Array a
-> Array Int
-> Array a
{-# INLINE_BACKEND indexs #-}
-- | 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.
indexs_avs
:: (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
{-# INLINE_BACKEND indexs_avs #-}
-- | O(length result). Extract a subrange of elements from an array.
--
-- @extract [23, 42, 93, 50, 27] 1 3 = [42, 93, 50]@
extract :: Elt a
=> Array a -- ^ Source array.
-> Int -- ^ Starting index in source array.
-> Int -- ^ Length of result array.
-> Array a
{-# INLINE_BACKEND extract #-}
-- | 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_nss
:: Elt a
=> SSegd
-> VV.Vector (Array a)
-> Array a
{-# INLINE_BACKEND extracts_nss #-}
-- | 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_ass
:: (Elt a, Elts a)
=> SSegd -- ^ `SSegd` defining the slices to extract.
-> Arrays a -- ^ Source arrays.
-> Array a
{-# INLINE_BACKEND extracts_ass #-}
-- | 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`.
extracts_avs
:: (Elt a, Elts a)
=> VSegd -- ^ `VSegd` defining the slices to extract.
-> Arrays a -- ^ Source arrays.
-> Array a
{-# INLINE_BACKEND extracts_avs #-}
-- | O(length result). Drop elements from the front of an array,
-- returning the latter portion.
drop :: Elt a => Int -> Array a -> Array a
{-# INLINE_BACKEND drop #-}
{-# RULES
"indexs_avs/singletons/replicatedVSegd"
forall arr len reps srcixs
. indexs_avs (singletons arr) (replicatedVSegd len reps) srcixs
= indexs arr (map snd srcixs)
#-}
-- Update =====================================================================
-- | O(length result).
-- Copy the source array while replacing some elements by new ones in the result.
update :: Elt a
=> Array a -- ^ Source array.
-> Array (Int, a) -- ^ Index and value of new elements.
-> Array a
{-# INLINE_BACKEND update #-}
-- Permutation ================================================================
-- | O(length result). Forwards permutation of array elements.
--
permute :: Elt a
=> Array a -- ^ Source array.
-> Array Int -- ^ Indices in the destination to copy elements to.
-> Array a
{-# INLINE_BACKEND permute #-}
-- | O(length result). Backwards permutation of array elements.
--
-- @bpermute [50, 60, 20, 30] [0, 3, 2] = [50, 30, 20]@
bpermute
:: Elt a
=> Array a -- ^ Source array.
-> Array Int -- ^ Indices in the source to copy elements from.
-> Array a
{-# INLINE_BACKEND bpermute #-}
-- | 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
{-# INLINE_BACKEND mbpermute #-}
-- | 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
{-# INLINE_BACKEND bpermuteDft #-}
{-# RULES
"bpermute/repeat" forall n len xs is.
bpermute (repeat n len xs) is
= len `Prelude.seq` bpermute xs (map (dph_mod_index len) is)
"bpermute/bpermute" forall xs is js.
bpermute (bpermute xs is) js = bpermute xs (bpermute is js)
#-}
-- Zipping and Unzipping ======================================================
-- | 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)
{-# INLINE CONLIKE PHASE_BACKEND zip #-}
-- | 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)
{-# INLINE CONLIKE PHASE_BACKEND zip3 #-}
-- | O(1). Unzip an array of pairs into a pair of arrays.
unzip :: (Elt a, Elt b) => Array (a, b) -> (Array a, Array b)
{-# INLINE_BACKEND unzip #-}
-- | 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)
{-# INLINE_BACKEND unzip3 #-}
-- | O(1). Take the first elements of an array of pairs.
fsts :: (Elt a, Elt b) => Array (a, b) -> Array a
{-# INLINE_BACKEND fsts #-}
-- | O(1). Take the second elements of an array of pairs.
snds :: (Elt a, Elt b) => Array (a, b) -> Array b
{-# INLINE_BACKEND snds #-}
-- Maps and zipWith ===========================================================
-- | 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
{-# INLINE_BACKEND map #-}
-- | 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
{-# INLINE_BACKEND zipWith #-}
-- | 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
zipWith3 f xs ys zs
= zipWith (\(x, y) z -> f x y z)
(zip xs ys)
zs
{-# INLINE zipWith3 #-}
-- | 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
zipWith4 f as bs cs ds
= zipWith (\(a, b) (c, d) -> f a b c d)
(zip as bs)
(zip cs ds)
{-# INLINE zipWith4 #-}
-- | Apply a worker function to corresponding elements of five 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
{-# INLINE zipWith5 #-}
zipWith5 f as bs cs ds es
= zipWith (\(a, b) ((c, d),e) -> f a b c d e)
(zip as bs)
(zip (zip cs ds) es)
-- | Apply a worker function to corresponding elements of six 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
{-# INLINE zipWith6 #-}
zipWith6 fn as bs cs ds es fs
= zipWith (\((a, b), c) ((d, e), f) -> fn a b c d e f)
(zip (zip as bs) cs)
(zip (zip ds es) fs)
-- | Apply a worker function to corresponding elements of seven 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
{-# INLINE zipWith7 #-}
zipWith7 fn as bs cs ds es fs gs
= zipWith (\((a, b), c) ((d, e), (f, g)) -> fn a b c d e f g)
(zip (zip as bs) cs)
(zip (zip ds es) (zip fs gs))
-- | Apply a worker function to corresponding elements of six 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
{-# INLINE zipWith8 #-}
zipWith8 fn as bs cs ds es fs gs hs
= zipWith (\((a, b), (c, d)) ((e, f), (g, h)) -> fn a b c d e f g h)
(zip (zip as bs) (zip cs ds))
(zip (zip es fs) (zip gs hs))
{-# RULES
"zipWith/replicate" forall f m n x y.
zipWith f (replicate m x) (replicate n y) = replicate m (f x y)
"zipWith/plusInt0_1" forall n xs.
zipWith (+) (replicate n (GHC.Base.I# 0#)) xs = xs
"zipWith/plusInt0_2" forall n xs.
zipWith (+) xs (replicate n (GHC.Base.I# 0#)) = xs
"zipWith(plusInt)/enumFromStepLen" forall i1 k1 n1 i2 k2 n2.
zipWith ((+) :: Int -> Int -> Int)
(enumFromStepLen i1 k1 n1)
(enumFromStepLen i2 k2 n2)
= enumFromStepLen (i1+i2) (k1+k2) n1
#-}
-- Folds and Scans ============================================================
-- Scans ------------------------------
-- | Similar to `foldl` but return an array of the intermediate states, including
-- the final state that is computed by `foldl`.
scan :: Elt a => (a -> a -> a) -> a -> Array a -> Array a
{-# INLINE_BACKEND scan #-}
-- Fold -------------------------------
-- | 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 :: Elt a => (a -> a -> a) -> a -> Array a -> a
{-# INLINE_BACKEND fold #-}
-- | Undirected segmented fold.
--
-- All segments are folded individually, and the result contains one
-- element for each segment.
--
-- Same preconditions as `fold`.
fold_s :: Elt a => (a -> a -> a) -> a -> Segd -> Array a -> Array a
{-# INLINE_BACKEND fold_s #-}
-- | Undirected scattered segmented fold.
--
-- Like `fold_s`, but the segments can be scattered through an `Arrays`.
--
-- Same preconditions as `fold`.
fold_ss :: (Elts a, Elt a)
=> (a -> a -> a) -> a -> SSegd -> Arrays a -> Array a
{-# INLINE_BACKEND fold_ss #-}
-- | Regular segmented fold.
--
-- All segements have the given length.
--
-- Same preconditions as `fold`.
fold_r :: Elt a => (a -> a -> a) -> a -> Int -> Array a -> Array a
{-# INLINE_BACKEND fold_r #-}
-- | 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_vs :: (Elts a, Elt a)
=> (a -> a -> a) -> a -> VSegd -> Arrays a -> Array a
fold_vs f x vsegd arrs
= let -- Fold each physical segment individually
psegResults = fold_ss f x (takeSSegdOfVSegd vsegd) arrs
-- Replicate the physical results accorsing to the vsegids
in bpermute psegResults (takeVSegidsOfVSegd vsegd)
{-# INLINE_BACKEND fold_vs #-}
-- When we know the array data is manifest and/or contiguous then we want
-- to avoid using the extended information in the VSegd and SSegd types.
{-# RULES
"fold_ss/promoteSegdToSSegd" forall f x segd arr.
fold_ss f x (promoteSegdToSSegd segd) (singletons arr)
= fold_s f x segd arr
"fold_vs/promoteSegdToVSegd" forall f x segd arr.
fold_vs f x (promoteSegdToVSegd segd) (singletons arr)
= fold_s f x segd arr
"fold_vs/promoteSSegdToVSegd" forall f x ssegd arrs.
fold_vs f x (promoteSSegdToVSegd ssegd) arrs
= fold_ss f x ssegd arrs
#-}
-- Fold1 -------------------------------
-- | 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 :: Elt a => (a -> a -> a) -> Array a -> a
{-# INLINE_BACKEND fold1 #-}
-- | Like `fold_s`, but using the first element of each segment to initialise
-- the state of that segment.
--
-- Same preconditions as `fold1`.
fold1_s :: Elt a => (a -> a -> a) -> Segd -> Array a -> Array a
{-# INLINE_BACKEND fold1_s #-}
-- | Like `fold_ss`, but using the first element of each segment to intialise
-- the state of that segment.
--
-- Same preconditions as `fold1`.
fold1_ss :: (Elts a, Elt a)
=> (a -> a -> a) -> SSegd -> Arrays a -> Array a
{-# INLINE_BACKEND fold1_ss #-}
-- | Like `fold_vs`, but using the first element of each segment to initialise
-- the state of that segment.
--
-- Same preconditions as `fold1`.
fold1_vs :: (Elts a, Elt a)
=> (a -> a -> a) -> VSegd -> Arrays a -> Array a
fold1_vs f vsegd arrs
= let -- Fold each physical segment individually
psegResults = fold1_ss f (takeSSegdOfVSegd vsegd) arrs
-- Replicate the physical results accorsing to the vsegids
in bpermute psegResults (takeVSegidsOfVSegd vsegd)
{-# INLINE_BACKEND fold1_vs #-}
-- When we know the array data is manifest and/or contiguous then we want
-- to avoid using the extended information in the VSegd and SSegd types.
{-# RULES
"fold1_ss/promoteSegdToSSegd" forall f segd arr.
fold1_ss f (promoteSegdToSSegd segd) (singletons arr)
= fold1_s f segd arr
"fold1_vs/promoteSegdToVSegd" forall f segd arr.
fold1_vs f (promoteSegdToVSegd segd) (singletons arr)
= fold1_s f segd arr
"fold1_vs/promoteSSegdToVSegd" forall f ssegd arrs.
fold1_vs f (promoteSSegdToVSegd ssegd) arrs
= fold1_ss f ssegd arrs
#-}
-- Sums -------------------------------
-- | Same as @fold (+) 0@
sum :: (Num a, Elt a) => Array a -> a
{-# INLINE_BACKEND sum #-}
-- | Same as @fold_s (+) 0@
sum_s :: (Num a, Elt a) => Segd -> Array a -> Array a
sum_s = fold_s (Prelude.+) 0
{-# INLINE sum_s #-}
-- | Same as @fold_ss (+) 0@
sum_ss :: (Num a, Elts a, Elt a)
=> SSegd -> Arrays a -> Array a
sum_ss = fold_ss (Prelude.+) 0
{-# INLINE sum_ss #-}
-- | Same as @fold_r (+) 0@
sum_r :: (Num a, Elt a) => Int -> Array a -> Array a
{-# INLINE_BACKEND sum_r #-}
-- Count ------------------------------
-- | Count the number of elements in array that are equal to the given value.
count :: (Elt a, Eq a) => Array a -> a -> Int
count xs !x = sum (map (tagToInt . fromBool . (==) x) xs)
{-# INLINE_BACKEND count #-}
-- | Segmented count.
count_s :: (Elt a, Eq a) => Segd -> Array a -> a -> Array Int
count_s segd xs !x
= sum_s segd (map (tagToInt . fromBool . (==) x) xs)
{-# INLINE_BACKEND count_s #-}
-- | Scattered segmented count.
--
-- NOTE: This is a transitory interface, and will be removed in future versions.
--- TODO: Make this take an `Arrays` instead of a Vector.
count_ss :: (Elt a, Eq a) => SSegd -> VV.Vector (Array a) -> a -> Array Int
{-# INLINE_BACKEND count_ss #-}
count_ss ssegd xs !x
= sum_ss ssegd (fromVectors $ VV.map (map (tagToInt . fromBool . (==) x)) xs)
-- And --------------------------------
-- | O(length source). Compute the conjunction of all elements in a boolean array.
and :: Array Bool -> Bool
{-# INLINE_BACKEND and #-}
{-# RULES
"seq/sum" forall xs e.
seq (sum xs) e = seq xs e
"seq/scan<Int> (+)" forall (i :: Int) xs e.
seq (scan (+) i xs) e = i `seq` xs `seq` e
"scan/replicate" forall (z :: Int) n x.
scan (+) z (replicate n x)
= enumFromStepLen z x n
"sum/replicate_rs" forall n xs.
sum (replicate_rs n xs) = sum xs * n
"count/replicate_s" forall segd xs tag.
count (replicate_s segd xs) tag
= sum (packByTag (lengthsSegd segd) xs tag)
"fold_s/replicate1" forall f z n idxs n' xs.
fold_s f z (mkSegd (replicate n (GHC.Base.I# 1#)) idxs n') xs = xs
"fold_s/replicate" forall f z m n idxs mn xs.
fold_s f z (mkSegd (replicate m n) idxs mn) xs
= fold_r f z n xs
"count/seq" forall xs x y. seq (count xs x) y = seq xs (seq x y)
#-}
-- Pack and Filter ============================================================
-- | O(length result).
-- Extract elements of an array where the associated flag is true.
pack :: Elt a => Array a -> Array Bool -> Array a
{-# INLINE_BACKEND pack #-}
-- | 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]@
--
packByTag
:: 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
packByTag xs tags !tag
= fsts (filter (\p -> Prelude.snd p == tag) (zip xs tags))
{-# INLINE_BACKEND packByTag #-}
-- | Extract the elements from an array that match the given predicate.
filter :: Elt a => (a -> Bool) -> Array a -> Array a
{-# INLINE_BACKEND filter #-}
-- | 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]@
pick :: (Elt a, Eq a) => Array a -> a -> Array Bool
pick xs !x = map (x ==) xs
{-# INLINE pick #-}
{-# RULES
"tagZeroes" UNTIL_PHASE_BACKEND forall xs n.
map fromBool (zipWith GHC.Base.eqInt xs (replicate n (GHC.Base.I# 0#)))
= tagZeroes xs
"replicate_s/tagZeroes" forall lens idxs n.
replicate_s (mkSegd lens idxs n) (tagZeroes lens)
= replicate n 0
"packByTag/replicate" forall xs n t u.
packByTag xs (replicate n t) u = if t == u then xs else empty
"packByTag/bpermute" forall xs is tags n.
packByTag (bpermute xs is) tags n
= bpermute xs (packByTag is tags n)
#-}
-- Combine and Interleave =====================================================
-- | 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]@
combine :: Elt a => Array Bool -> Array a -> Array a -> Array a
{-# INLINE_BACKEND combine #-}
-- | Like `combine`, but use a precomputed selector to speed up the process.
--
-- See the description of `mkSel2` for how this works.
--
combine2 :: Elt a => Array Tag -> SelRep2 -> Array a -> Array a -> Array a
{-# INLINE_BACKEND combine2 #-}
-- | Interleave the elements of two arrays.
--
-- @interleave [1, 2, 3] [4, 5, 6] = [1, 4, 2, 5, 3, 6]@
interleave :: Elt a => Array a -> Array a -> Array a
{-# INLINE_BACKEND interleave #-}
-- Selectors ==================================================================
-- | 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.
--
mkSel2 :: 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
{-# INLINE CONLIKE PHASE_BACKEND mkSel2 #-}
-- | O(1). Yield the tags array of a selector.
tagsSel2 :: Sel2 -> Array Tag
{-# INLINE_BACKEND tagsSel2 #-}
-- | O(1). Yield the indices array of a selector.
indicesSel2 :: Sel2 -> Array Int
{-# INLINE_BACKEND indicesSel2 #-}
-- | O(1). Yield the number of elements that will be taken from the first array.
elementsSel2_0 :: Sel2 -> Int
{-# INLINE_BACKEND elementsSel2_0 #-}
-- | O(1). Yield the number of elements that will be taken from the second array.
elementsSel2_1 :: Sel2 -> Int
{-# INLINE_BACKEND elementsSel2_1 #-}
-- | O(1). Yield the parallel representation of a selector.
repSel2 :: Sel2 -> SelRep2
{-# INLINE_BACKEND repSel2 #-}
-- Selector Representations ===================================================
-- | 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
-- @
mkSelRep2 :: Array Tag -> SelRep2
{-# INLINE CONLIKE PHASE_BACKEND mkSelRep2 #-}
-- | O(1). Take the `indices` field from a `SelRep2`.
indicesSelRep2 :: Array Tag -> SelRep2 -> Array Int
{-# INLINE_BACKEND indicesSelRep2 #-}
-- | O(1). Yield the number of elements to take from the first array.
elementsSelRep2_0 :: Array Tag -> SelRep2 -> Int
{-# INLINE_BACKEND elementsSelRep2_0 #-}
-- | O(1). Yield the number of elements to take from the second array.
elementsSelRep2_1 :: Array Tag -> SelRep2 -> Int
{-# INLINE_BACKEND elementsSelRep2_1 #-}
-- | O(n). Compute a selector from a tags array.
tagsToSel2 :: Array Tag -> Sel2
tagsToSel2 tags
= let rep = mkSelRep2 tags
in mkSel2 tags (indicesSelRep2 tags rep)
(elementsSelRep2_0 tags rep)
(elementsSelRep2_1 tags rep)
rep
{-# INLINE tagsToSel2 #-}
{-# RULES
"tagsSel2/mkSel2"
forall ts is n0 n1 r. tagsSel2 (mkSel2 ts is n0 n1 r) = ts
"indicesSel2/mkSel2"
forall ts is n0 n1 r. indicesSel2 (mkSel2 ts is n0 n1 r) = is
"elementsSel2_0/mkSel2"
forall ts is n0 n1 r. elementsSel2_0 (mkSel2 ts is n0 n1 r) = n0
"elementsSel2_1/mkSel2"
forall ts is n0 n1 r. elementsSel2_1 (mkSel2 ts is n0 n1 r) = n1
"repSel2/mkSel2"
forall ts is n0 n1 r. repSel2 (mkSel2 ts is n0 n1 r) = r
#-}
-- Segment Descriptors ========================================================
-- | 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
-- @
---
-- * This ensures that the indices are monotonically increasing,
-- and all elements from the flat array are covered by some segment.
--
-- * We need this because in the implementation of `lengthsToSegd`, we binary
-- search the indices to determine which segment an element of the
-- flat array belongs to. It also means that the segment indices can always
-- be reconstructed from the segment lengths by `lengthsToSegd`.
--
--
mkSegd :: Array Int -- ^ (lengths) Segment lengths.
-> Array Int -- ^ (indices) Segment indices.
-> Int -- ^ Total number of elements.
-> Segd
{-# INLINE CONLIKE PHASE_BACKEND mkSegd #-}
-- | Check whether a `Segd` is well formed.
validSegd :: Segd -> Bool
{-# NOINLINE validSegd #-}
-- NOINLINE because it's only used during debugging.
-- | O(1). Construct an empty `Segd`.
emptySegd :: Segd
{-# INLINE_BACKEND emptySegd #-}
-- | O(1). Construct a `Segd` containing a single segment of the given length.
singletonSegd :: Int -> Segd
{-# INLINE_BACKEND singletonSegd #-}
-- | O(max(segs, threads) . log segs).
-- Construct a `Segd` from an array of segment lengths.
lengthsToSegd :: Array Int -> Segd
lengthsToSegd ns = mkSegd ns (scan (+) 0 ns) (sum ns)
{-# INLINE_BACKEND lengthsToSegd #-}
-- | O(1). Yield the length of a `Segd`.
lengthSegd :: Segd -> Int
{-# INLINE_BACKEND lengthSegd #-}
-- | O(1). Yield the segment lengths of a `Segd`.
lengthsSegd :: Segd -> Array Int
{-# INLINE_BACKEND lengthsSegd #-}
-- | O(1). Yield the segment starting indices of a `Segd`.
indicesSegd :: Segd -> Array Int
{-# INLINE_BACKEND indicesSegd #-}
-- | O(1). Yield the total number of elements defined by a `Segd`.
elementsSegd :: Segd -> Int
{-# INLINE_BACKEND elementsSegd #-}
-- | 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]@
--
plusSegd :: Segd -> Segd -> Segd
plusSegd segd1 segd2
= mkSegd (zipWith (+) (lengthsSegd segd1) (lengthsSegd segd2))
(zipWith (+) (indicesSegd segd1) (indicesSegd segd2))
(elementsSegd segd1 `dph_plus` elementsSegd segd2)
{-# INLINE_BACKEND plusSegd #-}
{-# RULES
"lengthsSegd/mkSegd" forall lens idxs n.
lengthsSegd (mkSegd lens idxs n) = lens
"indicesSegd/mkSegd" forall lens idxs n.
indicesSegd (mkSegd lens idxs n) = idxs
"elementsSegd/mkSegd" forall lens idxs n.
elementsSegd (mkSegd lens idxs n) = n
"seq/elementsSegd" forall segd e.
seq (elementsSegd segd) e = seq segd e
"seq/mkSegd" forall lens idxs n e.
seq (mkSegd lens idxs n) e = lens `seq` idxs `seq` n `seq` e
#-}
-- Scattered Segment Descriptors ==============================================
-- | 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.
--
mkSSegd :: 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
{-# INLINE CONLIKE PHASE_BACKEND mkSSegd #-}
-- | Check whether a `Segd` is well formed.
validSSegd :: SSegd -> Bool
{-# NOINLINE validSSegd #-}
-- NOINLINE because it's only used during debugging.
-- | O(1). Construct an empty `SSegd`.
emptySSegd :: SSegd
{-# INLINE_BACKEND emptySSegd #-}
-- | O(1). Construct a `Segd` containing a single segment of the given length.
singletonSSegd :: Int -> SSegd
{-# INLINE_BACKEND singletonSSegd #-}
-- | O(segs). Promote a `Segd` to a `SSegd`,
-- assuming all segments are contiguous and come from a single array.
promoteSegdToSSegd :: Segd -> SSegd
{-# INLINE_BACKEND promoteSegdToSSegd #-}
-- | 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.
isContiguousSSegd :: SSegd -> Bool
{-# INLINE_BACKEND isContiguousSSegd #-}
-- | O(1). Yield the length of a `SSegd`.
lengthOfSSegd :: SSegd -> Int
{-# INLINE_BACKEND lengthOfSSegd #-}
-- | O(1). Yield the segment lengths of a `SSegd`.
lengthsOfSSegd :: SSegd -> Array Int
{-# INLINE_BACKEND lengthsOfSSegd #-}
-- | O(1). Yield the indices field of a `SSegd`.
indicesOfSSegd :: SSegd -> Array Int
{-# INLINE_BACKEND indicesOfSSegd #-}
-- | O(1). Yield the starts field of a `SSegd`.
startsOfSSegd :: SSegd -> Array Int
{-# INLINE_BACKEND startsOfSSegd #-}
-- | O(1). Yield the sources field of a `SSegd`.
sourcesOfSSegd :: SSegd -> Array Int
{-# INLINE_BACKEND sourcesOfSSegd #-}
-- | O(1). Get the length, segment index, starting index, and source id of a segment.
getSegOfSSegd :: SSegd -> Int -> (Int, Int, Int, Int)
{-# INLINE_BACKEND getSegOfSSegd #-}
-- | Produce a segment descriptor that describes the result of appending two
-- segmented arrays.
appendSSegd :: SSegd -> Int -> SSegd -> Int -> SSegd
{-# INLINE_BACKEND appendSSegd #-}
-- Virtual Segment descriptors ================================================
-- | 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.
--
mkVSegd :: Array Int -- ^ (vsegids) Mapping from virtual to physical segments.
-> SSegd -- ^ Scattered Segment descriptor defining the
-- physical segments.
-> VSegd
{-# INLINE_BACKEND mkVSegd #-}
-- | Check whether a `Segd` is well formed.
validVSegd :: VSegd -> Bool
{-# NOINLINE validVSegd #-}
-- NOINLINE because it's only used during debugging.
-- | O(1). Construct an empty `SSegd`.
emptyVSegd :: VSegd
{-# INLINE_BACKEND emptyVSegd #-}
-- | O(1). Construct a `VSegd` containing a single segment of the given length.
singletonVSegd :: Int -> VSegd
{-# INLINE_BACKEND singletonVSegd #-}
-- | O(len). Construct a `VSegd` that describes an array where all virtual
-- segments point to the same physical segment.
replicatedVSegd
:: Int -- ^ Length of segment.
-> Int -- ^ Number of times replicated.
-> VSegd
{-# INLINE_BACKEND replicatedVSegd #-}
-- | O(segs). Promote a plain `Segd` to a `VSegd`.
--
-- The result contains one virtual segment for every physical segment
-- the provided `Segd`.
promoteSegdToVSegd :: Segd -> VSegd
{-# INLINE CONLIKE PHASE_BACKEND promoteSegdToVSegd #-}
-- | O(segs). Promote a plain `SSegd` to a `VSegd`.
--
-- The result contains one virtual segment for every physical segment
-- the provided `SSegd`.
promoteSSegdToVSegd :: SSegd -> VSegd
{-# INLINE CONLIKE PHASE_BACKEND promoteSSegdToVSegd #-}
-- | 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.
isManifestVSegd :: VSegd -> Bool
{-# INLINE_BACKEND isManifestVSegd #-}
-- | 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.
isContiguousVSegd :: VSegd -> Bool
{-# INLINE_BACKEND isContiguousVSegd #-}
-- | O(1). Yield the length of a `VSegd`.
lengthOfVSegd :: VSegd -> Int
{-# INLINE_BACKEND lengthOfVSegd #-}
-- | O(1). Yield the vsegids of a `VSegd`.
takeVSegidsOfVSegd :: VSegd -> Array Int
{-# INLINE_BACKEND takeVSegidsOfVSegd #-}
-- | 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.
--
takeVSegidsRedundantOfVSegd :: VSegd -> Array Int
{-# INLINE_BACKEND takeVSegidsRedundantOfVSegd #-}
-- | O(1). Yield the `SSegd` of a `VSegd`.
takeSSegdOfVSegd :: VSegd -> SSegd
{-# INLINE_BACKEND takeSSegdOfVSegd #-}
-- | 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`.
takeSSegdRedundantOfVSegd :: VSegd -> SSegd
{-# INLINE_BACKEND takeSSegdRedundantOfVSegd #-}
-- | O(1). Yield the segment lengths of a `VSegd`.
takeLengthsOfVSegd :: VSegd -> Array Int
{-# INLINE_BACKEND takeLengthsOfVSegd #-}
-- | O(1). Get the length, starting index, and source id of a segment.
getSegOfVSegd :: VSegd -> Int -> (Int, Int, Int)
{-# INLINE_BACKEND getSegOfVSegd #-}
-- | 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.
--
unsafeDemoteToSSegdOfVSegd :: VSegd -> SSegd
{-# INLINE_BACKEND unsafeDemoteToSSegdOfVSegd #-}
-- | 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`.
unsafeDemoteToSegdOfVSegd :: VSegd -> Segd
{-# INLINE_BACKEND unsafeDemoteToSegdOfVSegd #-}
-- | Update the @vsegids@ of a `VSegd`, 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
{-# INLINE_BACKEND updateVSegsOfVSegd #-}
-- | 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.
--
updateVSegsReachableOfVSegd :: (Array Int -> Array Int) -> VSegd -> VSegd
{-# INLINE_BACKEND updateVSegsReachableOfVSegd #-}
-- | Produce a virtual segment descriptor that describes the result of
-- appending two segmented arrays.
appendVSegd
:: 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
{-# INLINE_BACKEND appendVSegd #-}
-- | Combine two virtual segment descriptors.
combine2VSegd
:: 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
{-# INLINE_BACKEND combine2VSegd #-}
{-# RULES
"updateVSegsOfVSegd/updateVSegsOfVSegd"
forall f g vsegd
. updateVSegsOfVSegd f (updateVSegsOfVSegd g vsegd)
= updateVSegsOfVSegd (f . g) vsegd
"updateVSegsOfVSegd/replicate_s/replicateVSegd"
forall segd len reps
. updateVSegsOfVSegd (replicate_s segd) (replicatedVSegd len reps)
= replicatedVSegd len (elementsSegd segd)
#-}
-- Irregular 2D arrays --------------------------------------------------------
-- | O(1). Construct an empty `Arrays` with no elements.
emptys :: Arrays a
{-# INLINE_BACKEND emptys #-}
-- | O(1). Construct an `Arrays` consisting of a single `Array`.
singletons :: (Elt a, Elts a) => Array a -> Arrays a
{-# INLINE_BACKEND singletons #-}
-- | O(1). Yield the number of `Array` in an `Arrays`.
lengths :: Elts a => Arrays a -> Int
{-# INLINE_BACKEND lengths #-}
-- | O(1). Take one of the outer `Array` from an `Arrays`.
unsafeIndexs :: (Elt a, Elts a) => Arrays a -> Int -> Array a
{-# INLINE_BACKEND unsafeIndexs #-}
-- | O(1). Retrieve a single element from an `Arrays`,
-- given the outer and inner indices.
unsafeIndex2s :: (Elt a, Elts a) => Arrays a -> Int -> Int -> a
{-# INLINE_BACKEND unsafeIndex2s #-}
-- | O(n). Append two `Arrays`, using work proportional to the length
-- of the outer array.
appends :: (Elt a, Elts a) => Arrays a -> Arrays a -> Arrays a
{-# INLINE_BACKEND appends #-}
-- | O(number of inner arrays).
-- Convert a boxed vector of `Array` to an `Arrays`.
fromVectors :: (Elt a, Elts a) => VV.Vector (Array a) -> Arrays a
{-# INLINE_BACKEND fromVectors #-}
-- | O(number of inner arrays).
-- Convert an `Arrays` to a boxed vector of `Array`.
toVectors :: (Elt a, Elts a) => Arrays a -> VV.Vector (Array a)
{-# INLINE_BACKEND toVectors #-}
-- Random Arrays --------------------------------------------------------------
-- | Generate an array of the given length full of random data.
-- Good for testing.
randoms :: (Elt a, System.Random.Random a, System.Random.RandomGen g)
=> Int -> g -> Array a
{-# INLINE_BACKEND randoms #-}
-- | Generate an array of the given length full of random data.
-- Good for testing.
randomRs :: (Elt a, System.Random.Random a, System.Random.RandomGen g)
=> Int -> (a,a) -> g -> Array a
{-# INLINE_BACKEND randomRs #-}
-- Array IO -------------------------------------------------------------------
instance IOElt Int
instance IOElt Double
instance (IOElt a, IOElt b) => IOElt (a, b)
-- | Write an array to a file.
hPut :: IOElt a => Handle -> Array a -> IO ()
{-# INLINE_BACKEND hPut #-}
-- | Read an array from a file.
hGet :: IOElt a => Handle -> IO (Array a)
{-# INLINE_BACKEND hGet #-}
-- | Convert an array to a list of elements.
toList :: Elt a => Array a -> [a]
{-# INLINE_BACKEND toList #-}
-- | Convert a list of elements to an array.
fromList :: Elt a => [a] -> Array a
{-# INLINE_BACKEND fromList #-}
-- Aliases for primitive operations -------------------------------------------
-- We rename these so we can write rules based on the names, and still
-- control exactly when they get inlined.
dph_mod_index :: Int -> Int -> Int
dph_mod_index by idx = idx `GHC.Base.remInt` by
{-# INLINE_BACKEND dph_mod_index #-}
dph_plus :: Int -> Int -> Int
dph_plus x y = x Prelude.+ y
{-# INLINE_BACKEND dph_plus #-}
{-# RULES
"dph_plus" forall m n.
dph_plus (GHC.Base.I# m) (GHC.Base.I# n) = GHC.Base.I# m Prelude.+ GHC.Base.I# n
#-}
tagZeroes :: Array Int -> Array Tag
tagZeroes xs = map (\x -> fromBool (x==0)) xs
{-# INLINE CONLIKE PHASE_BACKEND tagZeroes #-}