dph-prim-interface 0.5.1.1 → 0.6.0.1

raw patch · 5 files changed

+1784/−951 lines, 5 filesdep +vectordep ~basedep ~dph-basePVP ok

version bump matches the API change (PVP)

Dependencies added: vector

Dependency ranges changed: base, dph-base

API changes (from Hackage documentation)

Files

• Data/Array/Parallel/Unlifted.hs +186/−140
• LICENSE +1/−2
• dph-prim-interface.cabal +11/−5
• interface/DPH_Header.h +119/−42
• interface/DPH_Interface.h +1467/−762

@@ -1,21 +1,19 @@ {-# LANGUAGE TypeOperators, CPP #-} --- | This module provides the API for the DPH backend. ------   These are the DPH array primitives that the vectoriser introduces when---   transforming code. The actual code in this module is fake, in the sense---   that is provides a partial reference implementation using lists to---   represent arrays, but this code isn't acually used at runtime.+-- | WARNING: +--   This is an abstract interface. All the functions will just `error` if called.  -----   The actual code used by compiled programs depends on whether @-fdph-par@ or---   @-fdph-seq@ is passed  when compiling it. Depending on the flag, the---   implementation in either the @dph-prim-par@ or @dph-prim-seq packages@ is---   swapped in. These packages export the same API, but use a more efficient, ---   and perhaps parallel implementation.+--   This module provides an API for the segmented array primitives used by DPH.+--   None of the functions here have implementations. -----   All three packages are forced to use the same API by the 'DPH_Header.h'---   and 'DPH_Interface.h' include files in @dph-prim-interface/interface@.+--   Client programs should use either the @dph-prim-seq@ or @dph-prim-par@+--   packages, as these provide the same API and contain real code. --++--   NOTE: The API is enforced by the DPH_Header.h and DPH_Interface.h headers.+--   The dph-prim-interface, dph-prim-seq, and dph-prim-par modules all import+--   the same headers so we can be sure we're presenting the same API.+ #include "DPH_Header.h"  import qualified Prelude as P@@ -23,172 +21,220 @@  #include "DPH_Interface.h" --- NOTE -------------------------------------------------------------------------- See DPH_Interface.h for documentation. ---   As these functions are defined multiple times in different packages, ---   we keep all the docs there.------ The definitions should appear in the same order as they are defined in DPH_Interface.h -#define ASSERT assert __FILE__ __LINE__+------------------------------------------------------------------------------+notImplemented :: P.String -> a+notImplemented fnName+ = P.error $ P.unlines+ [ "dph-prim-interface:Data.Array.Parallel.Unlifted." P.++ fnName+ , "This module is an abstract interface and does not contain real code."+ , "Use dph-prim-seq or dph-prim-par instead." ]+{-# NOINLINE notImplemented #-} -assert :: P.String -> Int -> Bool -> a -> a-assert file line False _-  = P.error $ file P.++ " (line " P.++ P.show line P.++ "): assertion failure"-assert _ _ _ x = x +-- Types ---------------------------------------------------------------------- class Elt a instance Elt a => Elt [a]+type Array a    = [a] -type Array a = [a] -data Segd -        = Segd -        { segd_lengths  :: [Int]-        , segd_indices  :: [Int]-        , segd_elements :: Int }+-- Constructors ---------------------------------------------------------------+empty                           = notImplemented "empty"+(+:+)                           = notImplemented "(+:+)"+append_s                        = notImplemented "append_s"+replicate                       = notImplemented "replicate"+replicate_s                     = notImplemented "replicate_s"+replicate_rs                    = notImplemented "replicate_rs"+repeat                          = notImplemented "repeat"+indexed                         = notImplemented "indexed"+indices_s                       = notImplemented "indices_s"+enumFromTo                      = notImplemented "enumFromTo"+enumFromThenTo                  = notImplemented "enumFromThenTo"+enumFromStepLen                 = notImplemented "enumFromStepLen"+enumFromStepLenEach             = notImplemented "enumFromStepLenEach" -data Sel2 -        = Sel2 -        { sel2_tags      :: [Tag]-        , sel2_indices   :: [Int]-        , sel2_elements0 :: Int-        , sel2_elements1 :: Int } -type SelRep2    = ()+-- Conversions ----------------------------------------------------------------+nest                            = notImplemented "nest"+toList                          = notImplemented "toList"+fromList                        = notImplemented "fromList"+toList_s                        = notImplemented "toList_s"+fromList_s                      = notImplemented "fromList_s"  -length          = P.length-empty           = []-replicate       = P.replicate-repeat n _ xs   = P.concat (replicate n xs)-(!:)            = (P.!!)-extract xs i n  = P.take n (P.drop i xs)-drop            = P.drop-permute         = P.error "Not implemented: dph-prim-interface:Data.Array.Parallel.Unlifted.permute"-bpermute xs ns  = map (xs !:) ns-mbpermute       = P.error "Not implemented: dph-prim-interface:Data.Array.Parallel.Unlifted.mbpermute"-bpermuteDft     = P.error "Not implemented: dph-prim-interface:Data.Array.Parallel.Unlifted.bpermuteDft"-update          = P.error "Not implemented: dph-prim-interface:Data.Array.Parallel.Unlifted.update"-(+:+)           = (P.++)-interleave xs ys = P.concat [[x,y] | (x,y) <- P.zip xs ys]+-- Projections ----------------------------------------------------------------+length                          = notImplemented "length"+index                           = notImplemented "index"+indexs                          = notImplemented "indexs"+indexs_avs                      = notImplemented "indexs_avs"+extract                         = notImplemented "extract"+extracts_nss                    = notImplemented "extract_nss"+extracts_ass                    = notImplemented "extract_ass"+extracts_avs                    = notImplemented "extract_avs"+drop                            = notImplemented "drop" -pack xs bs      = [x | (x,b) <- P.zip xs bs, b] -combine [] [] [] = []-combine (True  : bs) (x : xs) ys       = x : combine bs xs ys-combine (False : bs) xs       (y : ys) = y : combine bs xs ys+-- Update ---------------------------------------------------------------------+update                          = notImplemented "update" -combine2 tags _ xs ys = go tags xs ys-  where-    go [] [] [] = []-    go (0 : bs) (x : xs) ys = x : go bs xs ys-    go (1 : bs) xs (y : ys) = y : go bs xs ys -map             = P.map-filter          = P.filter-zip             = P.zip-zip3            = P.zip3-unzip           = P.unzip-unzip3          = P.unzip3-fsts            = map P.fst-snds            = map P.snd-zipWith         = P.zipWith+-- Permutation ----------------------------------------------------------------+permute                         = notImplemented "permute"+bpermute                        = notImplemented "bpermute"+mbpermute                       = notImplemented "mbpermute"+bpermuteDft                     = notImplemented "bpermuteDft" -fold            = P.foldr-fold1           = P.foldr1-and             = P.and-sum             = P.sum -scan f z        = P.init . P.scanl f z+-- Zipping and Unzipping ------------------------------------------------------+zip                             = notImplemented "zip"+zip3                            = notImplemented "zip3"+unzip                           = notImplemented "unzip"+unzip3                          = notImplemented "unzip3"+fsts                            = notImplemented "fsts"+snds                            = notImplemented "snds" -indexed xs              = zip [0 .. length xs - 1] xs-enumFromTo m n          = [m .. n]-enumFromThenTo m n s    = [m, n..s] -enumFromStepLen i k 0   = []-enumFromStepLen i k n   = i : enumFromStepLen (i+k) k (n-1)+-- Map and zipWith ------------------------------------------------------------+map                             = notImplemented "map"+zipWith                         = notImplemented "zipWith" -enumFromStepLenEach size starts steps lens-  = ASSERT (size == sum lens)-    P.concat-  $ P.zipWith3 (\x y z -> P.enumFromThenTo x (x+y) (x+y*z)) starts steps lens -replicate_s segd xs-        = P.concat-        $ zipWith replicate (lengthsSegd segd) xs+-- Scans and Folds -----------------------------------------------------------+scan                            = notImplemented "scan"+fold                            = notImplemented "fold"+fold_s                          = notImplemented "fold_s"+fold_ss                         = notImplemented "fold_ss"+fold_r                          = notImplemented "fold_r"+fold1                           = notImplemented "fold1"+fold1_s                         = notImplemented "fold1_s"+fold1_ss                        = notImplemented "fold1_ss"+sum                             = notImplemented "sum"+sum_r                           = notImplemented "sum_r"+and                             = notImplemented "and" -replicate_rs n xs-        = P.concat-        $ P.map (P.replicate n) xs -append_s _ xd xs yd ys -        = P.concat (P.zipWith (P.++) (nest xd xs) (nest yd ys))+-- Packing and Combining ------------------------------------------------------+pack                            = notImplemented "pack"+filter                          = notImplemented "filter"+combine                         = notImplemented "combine"+combine2                        = notImplemented "combine2"+interleave                      = notImplemented "interleave" -fold_s  f z segd xs-        = P.map (P.foldr f z) (nest segd xs) -fold1_s f   segd xs-        = P.map (P.foldr1 f)  (nest segd xs)+-- Selectors ------------------------------------------------------------------+data Sel2 +        = Sel2 +        { sel2_tags      :: [Tag]+        , sel2_indices   :: [Int]+        , sel2_elements0 :: Int+        , sel2_elements1 :: Int } -fold_r  f z segSize xs -        = P.error "FIXME GABI PLEASE PLEASE PLEASE"+type SelRep2    = () -sum_r segSize xs -        = P.error "FIXME GABI PLEASE PLEASE PLEASE" +mkSel2                          = notImplemented "mkSel2"+tagsSel2                        = notImplemented "tagsSel2"+indicesSel2                     = notImplemented "indicesSel2"+elementsSel2_0                  = notImplemented "elementsSel2_0"+elementsSel2_1                  = notImplemented "elementsSel2_1"+repSel2                         = notImplemented "repSel2" -indices_s segd-        = P.concat [[0 .. n-1] | n <- segd_lengths segd] +mkSelRep2                       = notImplemented "mkSelRep2"+indicesSelRep2                  = notImplemented "indicesSelRep2"+elementsSelRep2_0               = notImplemented "elementsSelRep2_0"+elementsSelRep2_1               = notImplemented "elementsSelRep2_1" -lengthSegd      = length . lengthsSegd-lengthsSegd     = segd_lengths-indicesSegd     = segd_indices-elementsSegd    = segd_elements-mkSegd          = Segd +-- Segment Descriptors --------------------------------------------------------+data Segd +        = Segd +        { segd_lengths  :: [Int]+        , segd_indices  :: [Int]+        , segd_elements :: Int } -mkSel2 tags idxs n0 n1 _ -        = Sel2 tags idxs n0 n1+mkSegd                          = notImplemented "mkSegd"+emptySegd                       = notImplemented "emptySegd"+singletonSegd                   = notImplemented "singletonSegd"+validSegd                       = notImplemented "validSegd"+lengthSegd                      = notImplemented "lengthSegd"+lengthsSegd                     = notImplemented "lengthsSegd"+indicesSegd                     = notImplemented "indicesSegd"+elementsSegd                    = notImplemented "elementsSegd" -tagsSel2        = sel2_tags-indicesSel2     = sel2_indices-elementsSel2_0  = sel2_elements0-elementsSel2_1  = sel2_elements1-repSel2 _       = () -mkSelRep2 _     = ()+-- Scattered Segment Descriptors ----------------------------------------------+data SSegd+        = SSegd+        { ssegd_starts  :: [Int]+        , ssegd_sources :: [Int]+        , ssegd_segd    :: Segd } -indicesSelRep2 tags _ -  = P.zipWith pick tags-  $ P.init-  $ P.scanl add (0,0) tags-  where-    pick 0 (i,j) = i-    pick 1 (i,j) = j+mkSSegd                         = notImplemented "mkSSegd"+validSSegd                      = notImplemented "validSSegd"+emptySSegd                      = notImplemented "emptySSegd"+singletonSSegd                  = notImplemented "singletonSSegd"+promoteSegdToSSegd              = notImplemented "promoteSegdToSSegd"+isContiguousSSegd               = notImplemented "isContiguousSSegd"+lengthOfSSegd                   = notImplemented "lengthOfSSegd"+lengthsOfSSegd                  = notImplemented "lenghtsOfSSegd"+indicesOfSSegd                  = notImplemented "indicesOfSSegd"+startsOfSSegd                   = notImplemented "startsOfSSegd"+sourcesOfSSegd                  = notImplemented "sourcesOfSSegd"+getSegOfSSegd                   = notImplemented "getSegOfSSegd"+appendSSegd                     = notImplemented "appendSSegd" -    add (i,j) 0 = (i+1,j)-    add (i,j) 1 = (i,j+1) -elementsSelRep2_0 tags _ = P.length [() | 0 <- tags]-elementsSelRep2_1 tags _ = P.length [() | 1 <- tags]+-- Virtual Segment Descriptors ------------------------------------------------+data VSegd+        = VSegd+        { vsegd_vsegids :: [Int]+        , vsegd_ssegd   :: SSegd } -randoms n       = P.take n . System.Random.randoms+mkVSegd                         = notImplemented "mkVSegd"+validVSegd                      = notImplemented "validSSegd"       +emptyVSegd                      = notImplemented "emptyVSegd"+singletonVSegd                  = notImplemented "singletonVSegd"+replicatedVSegd                 = notImplemented "replicatedVSegd"+promoteSegdToVSegd              = notImplemented "promoteSegdToVSegd"+promoteSSegdToVSegd             = notImplemented "promoteSSegdToVSegd"+isContiguousVSegd               = notImplemented "isContiguousVSegd"+isManifestVSegd                 = notImplemented "isManifestVSegd"+lengthOfVSegd                   = notImplemented "lengthOfVSegd"+takeVSegidsOfVSegd              = notImplemented "takeVSegidsOfVSegd"+takeVSegidsRedundantOfVSegd     = notImplemented "takeVSegidsRedundantOfVSegd"+takeSSegdOfVSegd                = notImplemented "takeSSegdOfVSegd"+takeSSegdRedundantOfVSegd       = notImplemented "takeSSegdRedundantOfVSegd"+takeLengthsOfVSegd              = notImplemented "takeLengthsOfVSegd"+getSegOfVSegd                   = notImplemented "getSegOfVSegd"+unsafeDemoteToSSegdOfVSegd      = notImplemented "unsafeDemoteToSSegdOfVSegd"+unsafeDemoteToSegdOfVSegd       = notImplemented "unsafeDemoteToSegdOfVSegd"+updateVSegsOfVSegd              = notImplemented "updateVSegsOfVSegd"+updateVSegsReachableOfVSegd     = notImplemented "updateVSegsReachableOfVSegd"+appendVSegd                     = notImplemented "appendVSegd"+combine2VSegd                   = notImplemented "combine2VSegd" -randomRs n r    = P.take n . System.Random.randomRs r -nest :: Segd -> [a] -> [[a]]-nest (Segd ns is _) xs = go ns xs-  where-    go [] [] = []-    go (n : ns) xs = let (ys, zs) = P.splitAt n xs-                     in ys : go ns zs+-- Irregular two dimensional arrays -------------------------------------------+class Elts a+type Arrays a+        = [[a]] -class Elt a => IOElt a-hPut            = P.error "Not implemented: dph-prim-interface:Data.Array.Parallel.Unlifted.hPut"-hGet            = P.error "Not implemented: dph-prim-interface:Data.Array.Parallel.Unlifted.hGet"+emptys                          = notImplemented "emptys"+lengths                         = notImplemented "lengths"+singletons                      = notImplemented "singletons"+unsafeIndexs                    = notImplemented "unsafeIndexs"+unsafeIndex2s                   = notImplemented "unsafeIndex2s"+appends                         = notImplemented "appends"+fromVectors                     = notImplemented "fromVectors"+toVectors                       = notImplemented "toVectors" -toList x        = x-fromList x      = x -toList_s x      = x-fromList_s x    = x+-- Random Arrays --------------------------------------------------------------+randoms n                       = notImplemented "randoms"+randomRs n r                    = notImplemented "randomRs"+++-- Array IO -------------------------------------------------------------------+class Elt a => IOElt a+hPut                            = notImplemented "hPut"+hGet                            = notImplemented "hGet"+

@@ -1,5 +1,4 @@-Copyright (c) 2001-2011, The DPH Team-All rights reserved.+Copyright (c) 2001-2012, The DPH Team  The DPH Team is:   Manuel M T Chakravarty

@@ -1,12 +1,15 @@ Name:           dph-prim-interface-Version:        0.5.1.1+Version:        0.6.0.1 License:        BSD3 License-File:   LICENSE Author:         The DPH Team Maintainer:     Ben Lippmeier <benl@cse.unsw.edu.au> Homepage:       http://www.haskell.org/haskellwiki/GHC/Data_Parallel_Haskell Category:       Data Structures-Synopsis:       Backend Interface for Data Parallel Haskell+Synopsis:       Data Parallel Haskell segmented arrays. (abstract interface)+Description:    Empty implementation of flat parallel arrays. +                This package exists only so that dph-prim-par and dph-prim-seq+                can provide the same interface.  Cabal-Version:  >= 1.6 Build-Type:     Simple@@ -26,10 +29,13 @@    Extensions: BangPatterns -  GHC-Options: -Odph -funbox-strict-fields -fcpr-off+  GHC-Options:+        -Odph+        -funbox-strict-fields -fcpr-off    Build-Depends: -        base     == 4.4.*,+        base     == 4.5.*,         random   == 1.0.*,-        dph-base == 0.5.*+        dph-base == 0.6.*,+        vector   == 0.9.* 

@@ -2,74 +2,151 @@ #include "fusion-phases.h"  module Data.Array.Parallel.Unlifted (-  -- * Basics-  Elt, Array,  -  length,+  -- * Types+  Elt,  Array,      -- * Constructors   empty,-  (+:+),   generate,-  replicate, repeat,+  replicate, replicate_s, replicate_rs,+  repeat,   indexed,-  enumFromTo, enumFromThenTo, enumFromStepLen, enumFromStepLenEach,+  (+:+),     append_s,+  indices_s,+  enumFromTo,+  enumFromThenTo,+  enumFromStepLen,+  enumFromStepLenEach,    -- * Projections-  (!:),-  extract, drop,-  filter,+  length,+  index,+  indexs,+  indexs_avs,++  extract,+  extracts_nss,+  extracts_ass,+  extracts_avs,+  drop,   +  -- * Update+  update,+   -- * Permutation   permute,   bpermute,   mbpermute,   bpermuteDft,-  -  -- * Update-  update,-  -  -- * Packing and Combining-  pack,-  combine, combine2,-  interleave,+      +  -- * Zipping and Unzipping+  zip,   zip3,+  unzip, unzip3,+  fsts,  snds,    -- * Map and ZipWith   map, zipWith, zipWith3, zipWith4, -  -- * Zipping and Unzipping-  zip, unzip, fsts, snds,-    -  -- * Folds-  fold, fold1,-  and, sum, scan,---  -- * Segmented Constructors-  append_s, replicate_s, replicate_rs, +  -- * Scans and Folds+  scan,+  fold,  fold_s,  fold_ss,   fold_vs, fold_r,  +  fold1, fold1_s, fold1_ss,  fold1_vs,+  sum,   sum_s,   sum_ss,    sum_r,  +  count, count_s, count_ss,+  and,  -  -- * Segmented Folds-  fold_s, fold1_s, fold_r, sum_s,  sum_r,+  -- * Pack and Filter+  pack,+  packByTag,+  filter,+  pick,   -  -- * Segment Descriptors-  Segd,-  indices_s,-  lengthSegd, lengthsSegd, indicesSegd, elementsSegd, lengthsToSegd,-  mkSegd, plusSegd,+  -- * Combine and Interleave+  combine, combine2,+  interleave,    -- * Selectors   Sel2,   mkSel2, -  tagsSel2, indicesSel2, elementsSel2_0, elementsSel2_1, repSel2,+  tagsSel2,+  indicesSel2,+  elementsSel2_0,+  elementsSel2_1,+  repSel2,   tagsToSel2,   -  mkSelRep2, indicesSelRep2, elementsSelRep2_0, elementsSelRep2_1,+  -- * Selector Representations+  SelRep2,+  mkSelRep2,+  indicesSelRep2,+  elementsSelRep2_0,+  elementsSelRep2_1,+    +  -- * Segment Descriptors+  Segd,+  mkSegd,+  validSegd,+  emptySegd,+  singletonSegd,+  lengthsToSegd,+  lengthSegd,+  lengthsSegd,+  indicesSegd,+  elementsSegd,+  plusSegd, ++  -- * Scattered Segment Descriptors+  SSegd,+  mkSSegd,+  validSSegd,+  emptySSegd,+  singletonSSegd,+  promoteSegdToSSegd,+  isContiguousSSegd,+  lengthOfSSegd,+  lengthsOfSSegd,+  indicesOfSSegd,+  startsOfSSegd,+  sourcesOfSSegd,+  getSegOfSSegd,+  appendSSegd,   -  -- * Packing and picking-  packByTag, pick,+  -- * Virtual Segment Descriptors+  VSegd,+  mkVSegd,+  validVSegd,+  emptyVSegd,+  singletonVSegd,+  replicatedVSegd,+  promoteSegdToVSegd,+  promoteSSegdToVSegd,+  isManifestVSegd,+  isContiguousVSegd,+  lengthOfVSegd,+  takeVSegidsOfVSegd,+  takeVSegidsRedundantOfVSegd,+  takeSSegdOfVSegd,+  takeSSegdRedundantOfVSegd,+  takeLengthsOfVSegd,+  getSegOfVSegd,+  unsafeDemoteToSSegdOfVSegd,+  unsafeDemoteToSegdOfVSegd,+  updateVSegsOfVSegd,+  updateVSegsReachableOfVSegd,+  appendVSegd,+  combine2VSegd,   -  -- * Counting-  count, count_s,-+  -- * Irregular two dimensional arrays+  Elts, Arrays,+  emptys,+  singletons,+  lengths,+  unsafeIndexs,+  unsafeIndex2s,+  appends,+  fromVectors,+  toVectors,+     -- * Random arrays   randoms, randomRs,   @@ -83,4 +160,4 @@ import Data.Word                  (Word8) import qualified System.Random import qualified Prelude-+import qualified Data.Vector       as VV

@@ -1,762 +1,1467 @@-import Data.Array.Parallel.Base ( Tag, tagToInt, fromBool )-import qualified GHC.Base-import Prelude ((.), ($), Num(..), Eq(..), seq)-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)--infixl 9 !:-infixr 5 +:+---- Basics ------------------------------------------------------------------------ | O(1). Take the number of elements in an array.-length :: Elt a => Array a -> Int-{-# INLINE_BACKEND length #-}----- Constructors ------------------------------------------------------------------ | An array with no elements.-empty :: Elt a => Array a-{-# INLINE_BACKEND empty #-}----- | O(n). Append two arrays.-(+:+) :: Elt a => Array a -> Array a -> Array a-{-# INLINE_BACKEND (+:+) #-}----- | Generate a new array given its length and a function to compute each element.-generate :: Elt a => Int -> (Int -> a) -> Array a-{-# INLINE_BACKEND generate #-}-generate n f = map f (enumFromTo 0 (n-1))--generate_cheap :: Elt a => Int -> (Int -> a) -> Array a-{-# INLINE_BACKEND generate_cheap #-}-generate_cheap n f = map f (enumFromTo 0 (n-1))---- | O(n). Produce 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-- #-}----- | Produce 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 #-}----- | Tag each element of an array with its index.------   Example: @indexed [:42, 93, 13:] = [:(0, 42), (1, 93), (2, 13):]@ -indexed :: Elt a => Array a -> Array (Int, a)-{-# INLINE_BACKEND indexed #-}----- | Generate a range of @Int@s.-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 #-}---{-# 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))--  #-}----- Projections ------------------------------------------------------------------- | O(1). Retrieve a numbered element from an array.-(!:) :: Elt a => Array a -> Int -> a-{-# INLINE_BACKEND (!:) #-}----- | O(n). Extract a subrange of elements from an array.---   Example: @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(n). Drop some elements from the front of an array, ---         returning the latter portion.-drop :: Elt a => Int -> Array a -> Array a-{-# INLINE_BACKEND drop #-}----- Permutation ------------------------------------------------------------------- | O(n). 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(n). Backwards permutation of array elements.------   Example @bpermute [:50, 60, 20, 30:] 3 [: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 dont need---   to apply the parameter function to source elements that dont 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)--  #-}----- Update ------------------------------------------------------------------------ | O(n). Copy the source array in the destination, using new values for the given indices.-update :: Elt a => Array a -> Array (Int, a) -> Array a-{-# INLINE_BACKEND update #-}----- Packing and Combining -------------------------------------------------------- | Extract the elements from an array that match the given predicate.-filter :: Elt a => (a -> Bool) -> Array a -> Array a-{-# INLINE_BACKEND filter #-}----- | Extract elements of an array where the associated flag is true.-pack :: Elt a => Array a -> Array Bool -> Array a-{-# INLINE_BACKEND pack #-}----- | Combine two arrays, using a tag array to tell us where to get each element from.------   Example: @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 dph-prim-seq:"Data.Array.Parallel.Unlifted.Sequential.Segmented.USel"---   for a description of how this works.---   -combine2 :: Elt a => Array Tag -> SelRep2 -> Array a -> Array a -> Array a-{-# INLINE_BACKEND combine2 #-}----- | Interleave the elements of two arrays.--- ---   Example: @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 #-}----- Zipping and Unzipping --------------------------------------------------------- | O(1). Takes two arrays and returns an array of corresponding 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). Transform an array into an array of the first components,---         and an array of the second components.-unzip :: (Elt a, Elt b) => Array (a, b) -> (Array a, Array b)-{-# INLINE_BACKEND unzip #-}----- | 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 #-}----- | zipWith generalises zip by zipping with the function given as the first---         argument, instead of a tupling function.-zipWith :: (Elt a, Elt b, Elt c)-        => (a -> b -> c) -> Array a -> Array b -> Array c-{-# INLINE_BACKEND zipWith #-}---zipWith3 :: (Elt a, Elt b, Elt c, Elt d)-          => (a -> b -> c -> d) -> Array a -> Array b -> Array c -> Array d-{-# INLINE zipWith3 #-}-zipWith3 f xs ys zs-        = zipWith (\(x, y) z -> f x y z)-                  (zip xs ys)-                  zs--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-{-# INLINE zipWith4 #-}-zipWith4 f as bs cs ds-         = zipWith (\(a, b) (c, d) -> f a b c d)-                   (zip as bs)-                   (zip cs ds)----- Generally useful rules --------------{-# 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 GHC.Base.plusInt (replicate n (GHC.Base.I# 0#)) xs = xs--"zipWith/plusInt0_2" forall n xs.-  zipWith GHC.Base.plusInt xs (replicate n (GHC.Base.I# 0#)) = xs--"zipWith(plusInt)/enumFromStepLen" forall i1 k1 n1 i2 k2 n2.-  zipWith GHC.Base.plusInt (enumFromStepLen i1 k1 n1)-                           (enumFromStepLen i2 k2 n2)-    = enumFromStepLen (i1+i2) (k1+k2) n1-  #-}----- FIXME: These are the SMVM rules. They are intentionally quite specific and--- we want to get rid of the ASAP.--{-# RULES--"map/zipWith (+)/enumFromStepLen" forall m n is.-  map (dph_mod_index m) (zipWith GHC.Base.plusInt (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- #-}-              - --- The following rules fuse arithmetic operations that shouldnt have been---  vectorised in the first place. For example, with  z = x * y + a, the vectoriser---  will lift * and + to vector operations. The result of the  the multiply will be---  written to a vector, and then read back to do the addition.------  Adding the zipWith rules ensures that the multiply and addition are performed---  in one go. On the other hand, they can break fusion in the backend library.------ NOTE: These rules are only temporary, they should go away when we have ---       vectorisation avoidance for scalar operations.--{- RULES  **************** DISABLED--"zipWith/zipWith/zipWith" forall f g h as bs cs ds.-  zipWith f (zipWith g as bs) (zipWith h cs ds)-   = zipWith4 (\a b c d -> f (g a b) (h c d)) as bs cs ds--"zipWith/zipWith_left"  forall f g as bs cs.-  zipWith f (zipWith g as bs) cs-   = zipWith3 (\a b c ->   f (g a b) c) as bs cs--"zipWith/zipWith_right" forall f g as bs cs.-  zipWith f as (zipWith g bs cs)-   = zipWith3 (\a b c ->   f a (g b c)) as bs cs--  -}----- More rules to recover from the lack of vectorisation avoidance.--- The regular form of the rules shows why we really dont want to do it this way.--{- RULES  ****************** DISABLED--"map/zipWith" forall f g xs ys.-  map f (zipWith g xs ys)-   = zipWith (\x y -> f (g x y)) xs ys--"zipWith3/map_1" forall f g xs ys zs.-  zipWith3 f (map g xs) ys zs-   = zipWith3 (\x y z -> f (g x) y z) xs ys zs--"zipWith3/map_2" forall f g xs ys zs.-  zipWith3 f xs (map g ys) zs-   = zipWith3 (\x y z -> f x (g y) z) xs ys zs--"zipWith3/map_3" forall f g xs ys zs.-  zipWith3 f xs ys (map g zs)-   = zipWith3 (\x y z -> f x y (g z)) xs ys zs--  -}----- Folds -------------------------------------------------------------------------- | Left fold over an array.-fold :: Elt a => (a -> a -> a) -> a -> Array a -> a-{-# INLINE_BACKEND fold #-}---- | Left fold over an array, using the first element to initialise the state.-fold1 :: Elt a => (a -> a -> a) -> Array a -> a-{-# INLINE_BACKEND fold1 #-}----- | Compute the conjunction of all elements in a boolean array.-and :: Array Bool -> Bool-{-# INLINE_BACKEND and #-}---- | Compute the sum of an array of numbers.-sum :: (Num a, Elt a) => Array a -> a-{-# INLINE_BACKEND sum #-}---- | 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 #-}---{-# RULES--"seq/sum" forall xs e.-  seq (sum xs) e = seq xs e--"seq/scan<Int> (+)" forall i xs e.-  seq (scan GHC.Base.plusInt i xs) e = i `seq` xs `seq` e--"scan/replicate" forall z n x.-  scan GHC.Base.plusInt z (replicate n x)-    = enumFromStepLen z x n--  #-}----- Segmented Constructors ------------------------------------------------------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 first array-        -> Array a-{-# INLINE_BACKEND append_s #-}---replicate_s :: Elt a => Segd -> Array a -> Array a-{-# INLINE CONLIKE PHASE_BACKEND replicate_s #-}---replicate_rs :: Elt a => Int -> Array a -> Array a-{-# INLINE CONLIKE PHASE_BACKEND replicate_rs #-}---{-# 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--  #-}--{-# 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--"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)-- #-}----- Segmented Folds -------------------------------------------------------------fold_s :: Elt a => (a -> a -> a) -> a -> Segd -> Array a -> Array a-{-# INLINE_BACKEND fold_s #-}--fold1_s :: Elt a => (a -> a -> a) -> Segd -> Array a -> Array a-{-# INLINE_BACKEND fold1_s #-}--fold_r :: Elt a => (a -> a -> a) -> a -> Int -> Array a -> Array a-{-# INLINE_BACKEND fold_r #-}--sum_s :: (Num a, Elt a) => Segd -> Array a -> Array a-{-# INLINE sum_s #-}-sum_s = fold_s (Prelude.+) 0--sum_r :: (Num a, Elt a) => Int ->Array a -> Array a-{-# INLINE_BACKEND sum_r #-}--{-# RULES--"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--  #-}----- Operations on Segment Descriptors -------------------------------------------indices_s :: Segd -> Array Int-{-# INLINE_BACKEND indices_s #-}--lengthSegd :: Segd -> Int-{-# INLINE_BACKEND lengthSegd #-}--lengthsSegd :: Segd -> Array Int-{-# INLINE_BACKEND lengthsSegd #-}--indicesSegd :: Segd -> Array Int-{-# INLINE_BACKEND indicesSegd #-}--elementsSegd :: Segd -> Int-{-# INLINE_BACKEND elementsSegd #-}--lengthsToSegd :: Array Int -> Segd-{-# INLINE lengthsToSegd #-}-lengthsToSegd ns = mkSegd ns (scan (+) 0 ns) (sum ns)--mkSegd :: Array Int -> Array Int -> Int -> Segd-{-# INLINE CONLIKE PHASE_BACKEND mkSegd #-}--plusSegd :: Segd -> Segd -> Segd-{-# INLINE plusSegd #-}-plusSegd segd1 segd2-  = mkSegd (zipWith (+) (lengthsSegd segd1) (lengthsSegd segd2))-           (zipWith (+) (indicesSegd segd1) (indicesSegd segd2))-           (elementsSegd segd1 `dph_plus` elementsSegd segd2)---{-# 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-- #-}----- Operations on Selectors -------------------------------------------------------- | O(1). Construct a selector. Selectors are used to speed up the `combine2` operation.------   See dph-prim-seq:"Data.Array.Parallel.Unlifted.Sequential.Segmented.USel"---   for a description of how this works.-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      -        -> Sel2-{-# INLINE CONLIKE PHASE_BACKEND mkSel2 #-}----- | O(1). Get the tags array of a selector.-tagsSel2 :: Sel2 -> Array Tag-{-# INLINE_BACKEND tagsSel2 #-}----- | O(1). Get the indices array of a selector.-indicesSel2 :: Sel2 -> Array Int-{-# INLINE_BACKEND indicesSel2 #-}----- | O(1). Get the number of elements that will be taken from the first array.-elementsSel2_0 :: Sel2 -> Int-{-# INLINE_BACKEND elementsSel2_0 #-}----- | O(1). Get the number of elements that will be taken from the second array.-elementsSel2_1 :: Sel2 -> Int-{-# INLINE_BACKEND elementsSel2_1 #-}--repSel2 :: Sel2 -> SelRep2-{-# INLINE_BACKEND repSel2 #-}--mkSelRep2 :: Array Tag -> SelRep2-{-# INLINE CONLIKE PHASE_BACKEND mkSelRep2 #-}--indicesSelRep2 :: Array Tag -> SelRep2 -> Array Int-{-# INLINE_BACKEND indicesSelRep2 #-}--elementsSelRep2_0 :: Array Tag -> SelRep2 -> Int-{-# INLINE_BACKEND elementsSelRep2_0 #-}--elementsSelRep2_1 :: Array Tag -> SelRep2 -> Int-{-# INLINE_BACKEND elementsSelRep2_1 #-}----- | O(n), Compute a selector from a tags array.-tagsToSel2 :: Array Tag -> Sel2-{-# INLINE tagsToSel2 #-}-tagsToSel2 tags = let rep = mkSelRep2 tags-                  in-                  mkSel2 tags (indicesSelRep2    tags rep)-                              (elementsSelRep2_0 tags rep)-                              (elementsSelRep2_1 tags rep)-                              rep--{-# 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--  #-}----- Packing and Picking ------------------------------------------------------------ | 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--{-# INLINE_BACKEND packByTag #-}-packByTag xs tags !tag-        = fsts (filter (\p -> Prelude.snd p == tag) (zip xs tags))---pick :: (Elt a, Eq a) => Array a -> a -> Array Bool-{-# INLINE pick #-}-pick xs !x = map (x==) xs--{-# 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-- #-}--{-# RULES--"packByTag/bpermute" forall xs is tags n.-  packByTag (bpermute xs is) tags n-    = bpermute xs (packByTag is tags n)--  #-}------- Counting ---------------------------------------------------------------------- | Count the number of elements in array that are equal to the given value.-count :: (Elt a, Eq a) => Array a -> a -> Int-{-# INLINE_BACKEND count #-}-count xs !x = sum (map (tagToInt . fromBool . (==) x) xs)----- | Count the number of elements in segments that are equal to the given value.-count_s :: (Elt a, Eq a) => Segd -> Array a -> a -> Array Int-{-# INLINE_BACKEND count_s #-}-count_s segd xs !x = sum_s segd (map (tagToInt . fromBool . (==) x) xs)---{-# RULES--"count/seq" forall xs x y. seq (count xs x) y = seq xs (seq x y)--  #-}----- Random Arrays ---------------------------------------------------------------randoms :: (Elt a, System.Random.Random a, System.Random.RandomGen g)-        => Int -> g -> Array a-{-# INLINE_BACKEND randoms #-}--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 --------------------------------------------dph_mod_index :: Int -> Int -> Int-{-# INLINE_BACKEND dph_mod_index #-}-dph_mod_index by idx = idx `GHC.Base.remInt` by--dph_plus :: Int -> Int -> Int-{-# INLINE_BACKEND dph_plus #-}-dph_plus x y = x Prelude.+ y--{-# 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--  #-}--dph_mult :: Int -> Int -> Int-{-# INLINE_BACKEND dph_mult #-}-dph_mult x y = x Prelude.* y---tagZeroes :: Array Int -> Array Tag-{-# INLINE CONLIKE PHASE_BACKEND tagZeroes #-}-tagZeroes xs = map (\x -> fromBool (x==0)) xs------------------------------------------------------------------------------------- Currently disabled rules----------------------------------------------------------------------------------{- RULES--"packByTag/combine2ByTag" forall tags1 xs ys tags2 n.-  packByTag (combine2ByTag tags1 xs ys) tags2 n-    = combine2ByTag (packByTag tags1 tags2 n)-                    (packByTag xs (packByTag tags2 tags1 0) n)-                    (packByTag ys (packByTag tags2 tags1 1) n)--  -}+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 GHC.Base.plusInt (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++  #-}+++-- 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 #-}+++{-# 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 GHC.Base.plusInt (replicate n (GHC.Base.I# 0#)) xs = xs++"zipWith/plusInt0_2" forall n xs.+  zipWith GHC.Base.plusInt xs (replicate n (GHC.Base.I# 0#)) = xs++"zipWith(plusInt)/enumFromStepLen" forall i1 k1 n1 i2 k2 n2.+  zipWith GHC.Base.plusInt (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 xs e.+  seq (scan GHC.Base.plusInt i xs) e = i `seq` xs `seq` e++"scan/replicate" forall z n x.+  scan GHC.Base.plusInt 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 #-}+