-- Hoogle documentation, generated by Haddock -- See Hoogle, http://www.haskell.org/hoogle/ -- | An embedded language for accelerated array processing -- -- Data.Array.Accelerate defines an embedded array language for -- computations for high-performance computing in Haskell. Computations -- on multi-dimensional, regular arrays are expressed in the form of -- parameterised collective operations, such as maps, reductions, and -- permutations. These computations may then be online compiled and -- executed on a range of architectures. -- -- -- -- As a simple example, consider the computation of a dot product of two -- vectors of floating point numbers: -- -- 
--   dotp :: Acc (Vector Float) -> Acc (Vector Float) -> Acc (Scalar Float)
--   dotp xs ys = fold (+) 0 (zipWith (*) xs ys)
--
-- -- Except for the type, this code is almost the same as the corresponding -- Haskell code on lists of floats. The types indicate that the -- computation may be online-compiled for performance - for example, -- using Data.Array.Accelerate.LLVM.PTX it may be on-the-fly -- off-loaded to the GPU. -- -- See the Data.Array.Accelerate module for further information. -- -- -- -- The following supported add-ons are available as separate packages. -- Install them from Hackage with cabal install <package> -- -- -- -- -- -- Haddock documentation is included in the package -- -- The accelerate-examples package demonstrates a range of -- computational kernels and several complete applications, including: -- -- -- -- lulesh-accelerate is an implementation of the Livermore -- Unstructured Lagrangian Explicit Shock Hydrodynamics (LULESH) -- mini-app. LULESH represents a typical hydrodynamics code such as -- ALE3D, but is highly simplified and hard-coded to solve the Sedov -- blast problem on an unstructured hexahedron mesh. -- -- -- -- @package accelerate @version 1.3.0.0 -- | Operations which may be unsafe. Use with care. module Data.Array.Accelerate.Unsafe class Coerce a b -- | The function coerce allows you to convert a value between any -- two types whose underlying representations have the same bit size at -- each component. -- -- For example: -- -- 
--   coerce (x :: Exp Double)         :: Exp Word64
--   coerce (x :: Exp (Int64,Float))  :: Exp (Complex Float, Word32)
--
-- -- Furthermore, as we typically declare newtype wrappers similarly to: -- -- 
--   type instance EltR (Sum a) = ((), EltR a)
--
-- -- This can be used instead of the newtype constructor, to go from the -- newtype's abstract type to the concrete type by dropping the extra -- () from the representation, and vice-versa. -- -- The type class Coerce assures that there is a coercion between -- the two types. coerce :: Coerce (EltR a) (EltR b) => Exp a -> Exp b -- | undef can be used anywhere a constant is expected, and -- indicates that the consumer of the value can receive an unspecified -- bit pattern. -- -- This is useful because a store of an undefined value can be assumed to -- not have any effect; we can assume that the value is overwritten with -- bits that happen to match what was already there. However, a store -- to an undefined location could clobber arbitrary memory, -- therefore, its use in such a context would introduce undefined -- behaviour. -- -- There are (at least) two cases where you may want to use this: -- --
    --
  1. The permute function requires an array of default values, -- into which the new values are combined. However, if you are sure the -- default values are not used, and will (eventually) be completely -- overwritten, then filling an array with this value will give -- you a new uninitialised array.
    2. --
  2. In the definition of sum data types. See for example -- Data.Array.Accelerate.Data.Maybe and -- Data.Array.Accelerate.Data.Either.
    3. --
undef :: forall e. Elt e => Exp e -- | This interpreter is meant to be a reference implementation of the -- semantics of the embedded array language. The emphasis is on defining -- the semantics clearly, not on performance. module Data.Array.Accelerate.Interpreter -- | Accelerate is an embedded language that distinguishes between -- vanilla arrays (e.g. in Haskell memory on the CPU) and embedded arrays -- (e.g. in device memory on a GPU), as well as the computations on both -- of these. Since Accelerate is an embedded language, programs written -- in Accelerate are not compiled by the Haskell compiler (GHC). Rather, -- each Accelerate backend is a runtime compiler which generates -- and executes parallel SIMD code of the target language at application -- runtime. -- -- The type constructor Acc represents embedded collective array -- operations. A term of type Acc a is an Accelerate program -- which, once executed, will produce a value of type a (an -- Array or a tuple of Arrays). Collective operations of -- type Acc a comprise many scalar expressions, wrapped -- in type constructor Exp, which will be executed in parallel. -- Although collective operations comprise many scalar operations -- executed in parallel, scalar operations cannot initiate new -- collective operations: this stratification between scalar operations -- in Exp and array operations in Acc helps statically -- exclude nested data parallelism, which is difficult to execute -- efficiently on constrained hardware such as GPUs. -- -- -- -- As a simple example, to compute a vector dot product we can write: -- -- 
--   dotp :: Num a => Vector a -> Vector a -> Acc (Scalar a)
--   dotp xs ys =
--     let
--         xs' = use xs
--         ys' = use ys
--     in
--     fold (+) 0 ( zipWith (*) xs' ys' )
--
-- -- The function dotp consumes two one-dimensional arrays -- (Vectors) of values, and produces a single (Scalar) -- result as output. As the return type is wrapped in the type -- Acc, we see that it is an embedded Accelerate computation - it -- will be evaluated in the object language of dynamically -- generated parallel code, rather than the meta language of -- vanilla Haskell. -- -- As the arguments to dotp are plain Haskell arrays, to make -- these available to Accelerate computations they must be embedded with -- the use function. -- -- An Accelerate backend is used to evaluate the embedded computation and -- return the result back to vanilla Haskell. Calling the run -- function of a backend will generate code for the target architecture, -- compile, and execute it. For example, the following backends are -- available: -- -- -- -- See also Exp, which encapsulates embedded scalar -- computations. -- -- -- -- As mentioned above, embedded scalar computations of type Exp -- can not initiate further collective operations. -- -- Suppose we wanted to extend our above dotp function to -- matrix-vector multiplication. First, let's rewrite our dotp -- function to take Acc arrays as input (which is typically what -- we want): -- -- 
--   dotp :: Num a => Acc (Vector a) -> Acc (Vector a) -> Acc (Scalar a)
--   dotp xs ys = fold (+) 0 ( zipWith (*) xs ys )
--
-- -- We might then be inclined to lift our dot-product program to the -- following (incorrect) matrix-vector product, by applying dotp -- to each row of the input matrix: -- -- 
--   mvm_ndp :: Num a => Acc (Matrix a) -> Acc (Vector a) -> Acc (Vector a)
--   mvm_ndp mat vec =
--     let Z :. rows :. cols  = unlift (shape mat)  :: Z :. Exp Int :. Exp Int
--     in  generate (index1 rows)
--                  (\row -> the $ dotp vec (slice mat (lift (row :. All))))
--
-- -- Here, we use generate to create a one-dimensional vector by -- applying at each index a function to slice out the -- corresponding row of the matrix to pass to the dotp -- function. However, since both generate and slice are -- data-parallel operations, and moreover that slice depends -- on the argument row given to it by the generate -- function, this definition requires nested data-parallelism, and is -- thus not permitted. The clue that this definition is invalid is that -- in order to create a program which will be accepted by the type -- checker, we must use the function the to retrieve the result of -- the dotp operation, effectively concealing that dotp -- is a collective array computation in order to match the type expected -- by generate, which is that of scalar expressions. Additionally, -- since we have fooled the type-checker, this problem will only be -- discovered at program runtime. -- -- In order to avoid this problem, we can make use of the fact that -- operations in Accelerate are rank polymorphic. The fold -- operation reduces along the innermost dimension of an array of -- arbitrary rank, reducing the rank (dimensionality) of the array by -- one. Thus, we can replicate the input vector to as many -- rows there are in the input matrix, and perform the -- dot-product of the vector with every row simultaneously: -- -- 
--   mvm :: A.Num a => Acc (Matrix a) -> Acc (Vector a) -> Acc (Vector a)
--   mvm mat vec =
--     let Z :. rows :. cols = unlift (shape mat) :: Z :. Exp Int :. Exp Int
--         vec'              = A.replicate (lift (Z :. rows :. All)) vec
--     in
--     A.fold (+) 0 ( A.zipWith (*) mat vec' )
--
-- -- Note that the intermediate, replicated array vec' is never -- actually created in memory; it will be fused directly into the -- operation which consumes it. We discuss fusion next. -- -- -- -- Array computations of type Acc will be subject to array -- fusion; Accelerate will combine individual Acc computations -- into a single computation, which reduces the number of traversals over -- the input data and thus improves performance. As such, it is often -- useful to have some intuition on when fusion should occur. -- -- The main idea is to first partition array operations into two -- categories: -- --
    --
  1. Element-wise operations, such as map, generate, and -- backpermute. Each element of these operations can be computed -- independently of all others.
    2. --
  2. Collective operations such as fold, scanl, and -- stencil. To compute each output element of these operations -- requires reading multiple elements from the input array(s).
    3. --
-- -- Element-wise operations fuse together whenever the consumer operation -- uses a single element of the input array. Element-wise operations can -- both fuse their inputs into themselves, as well be fused into later -- operations. Both these examples should fuse into a single loop: -- -- -- -- If the consumer operation uses more than one element of the input -- array (typically, via generate indexing an array multiple -- times), then the input array will be completely evaluated first; no -- fusion occurs in this case, because fusing the first operation into -- the second implies duplicating work. -- -- On the other hand, collective operations can fuse their input arrays -- into themselves, but on output always evaluate to an array; collective -- operations will not be fused into a later step. For example: -- -- -- Here the element-wise sequence (use + generate + -- zipWith) will fuse into a single operation, which then fuses -- into the collective fold operation. At this point in the -- program the fold must now be evaluated. In the final step the -- map reads in the array produced by fold. As there is no -- fusion between the fold and map steps, this program -- consists of two "loops"; one for the use + generate + -- zipWith + fold step, and one for the final map -- step. -- -- You can see how many operations will be executed in the fused program -- by Show-ing the Acc program, or by using the debugging -- option -ddump-dot to save the program as a graphviz DOT file. -- -- As a special note, the operations unzip and reshape, -- when applied to a real array, are executed in constant time, so in -- this situation these operations will not be fused. -- -- -- -- data Acc a -- | The Arrays class characterises the types which can appear in -- collective Accelerate computations of type Acc. -- -- Arrays consists of nested tuples of individual Arrays, -- currently up to 16-elements wide. Accelerate computations can thereby -- return multiple results. class Arrays a -- | Run a complete embedded array program using the reference interpreter. run :: (HasCallStack, Arrays a) => Acc a -> a -- | This is runN specialised to an array program of one argument. run1 :: (HasCallStack, Arrays a, Arrays b) => (Acc a -> Acc b) -> a -> b -- | Prepare and execute an embedded array program. runN :: forall f. (HasCallStack, Afunction f) => f -> AfunctionR f -- | A functor performs a uniform action over a parameterised type -- -- This is essentially the same as the standard Haskell Functor -- class, lifted to Accelerate Exp terms. module Data.Array.Accelerate.Data.Functor -- | The Functor class is used for scalar types which can be mapped -- over. Instances of Functor should satisfy the following laws: -- -- 
--   fmap id      == id
--   fmap (f . g) == fmap f . fmap g
--
class Functor f fmap :: (Functor f, Elt a, Elt b, Elt (f a), Elt (f b)) => (Exp a -> Exp b) -> Exp (f a) -> Exp (f b) -- | Replace all locations in the input with the same value. The default -- definition is fmap . const, but this may be overridden with a -- more efficient version. (<$) :: (Functor f, Elt a, Elt b, Elt (f a), Elt (f b)) => Exp a -> Exp (f b) -> Exp (f a) infixl 4 <$ -- | An infix synonym for fmap -- -- The name of this operator is an allusion to $. Note the -- similarities between their types: -- -- 
--    ($)  ::              (Exp a -> Exp b) -> Exp a     -> Exp b
--   (<$>) :: Functor f => (Exp a -> Exp b) -> Exp (f a) -> Exp (f b)
--
-- -- Whereas $ is function application, <$> is function -- application lifted over a Functor. (<$>) :: (Functor f, Elt a, Elt b, Elt (f a), Elt (f b)) => (Exp a -> Exp b) -> Exp (f a) -> Exp (f b) infixl 4 <$> -- | A flipped version of (<$). ($>) :: (Functor f, Elt a, Elt b, Elt (f a), Elt (f b)) => Exp (f a) -> Exp b -> Exp (f b) infixl 4 $> -- | void value discards or ignores the result of -- evaluation. void :: (Functor f, Elt a, Elt (f a), Elt (f ())) => Exp (f a) -> Exp (f ()) instance Data.Array.Accelerate.Data.Functor.Functor Data.Semigroup.Internal.Sum instance Data.Array.Accelerate.Data.Functor.Functor Data.Semigroup.Internal.Product instance Data.Array.Accelerate.Data.Functor.Functor Data.Semigroup.Min instance Data.Array.Accelerate.Data.Functor.Functor Data.Semigroup.Max -- | Bitwise operations for signed and unsigned integer expressions. module Data.Array.Accelerate.Data.Bits -- | The Bits class defines bitwise operations over integral scalar -- expression types. As usual, bits are numbered from zero, with zero -- being the least significant bit. class Eq a => Bits a -- | Bitwise "and" (.&.) :: Bits a => Exp a -> Exp a -> Exp a -- | Bitwise "or" (.|.) :: Bits a => Exp a -> Exp a -> Exp a -- | Bitwise "xor" xor :: Bits a => Exp a -> Exp a -> Exp a -- | Reverse all bits in the argument complement :: Bits a => Exp a -> Exp a -- | shift x i shifts x left by i bits if -- i is positive, or right by -i bits otherwise. Right -- shifts perform sign extension on signed number types; i.e. they fill -- the top bits with 1 if the x is negative and with 0 -- otherwise. shift :: Bits a => Exp a -> Exp Int -> Exp a -- | rotate x i rotates x left by i bits -- if i is positive, or right by -i bits otherwise. rotate :: Bits a => Exp a -> Exp Int -> Exp a -- | The value with all bits unset zeroBits :: Bits a => Exp a -- | bit i is a value with the ith bit set -- and all other bits clear. bit :: Bits a => Exp Int -> Exp a -- | x `setBit` i is the same as x .|. bit i setBit :: Bits a => Exp a -> Exp Int -> Exp a -- | x `clearBit` i is the same as x .&. complement (bit -- i) clearBit :: Bits a => Exp a -> Exp Int -> Exp a -- | x `complementBit` i is the same as x `xor` bit i complementBit :: Bits a => Exp a -> Exp Int -> Exp a -- | Return True if the nth bit of the argument is 1 testBit :: Bits a => Exp a -> Exp Int -> Exp Bool -- | Return True if the argument is a signed type. isSigned :: Bits a => Exp a -> Exp Bool -- | Shift the argument left by the specified number of bits (which must be -- non-negative). shiftL :: Bits a => Exp a -> Exp Int -> Exp a -- | Shift the argument left by the specified number of bits. The result is -- undefined for negative shift amounts and shift amounts greater or -- equal to the finiteBitSize. unsafeShiftL :: Bits a => Exp a -> Exp Int -> Exp a -- | Shift the first argument right by the specified number of bits (which -- must be non-negative). -- -- Right shifts perform sign extension on signed number types; i.e. they -- fill the top bits with 1 if x is negative and with 0 -- otherwise. shiftR :: Bits a => Exp a -> Exp Int -> Exp a -- | Shift the first argument right by the specified number of bits. The -- result is undefined for negative shift amounts and shift amounts -- greater or equal to the finiteBitSize. unsafeShiftR :: Bits a => Exp a -> Exp Int -> Exp a -- | Rotate the argument left by the specified number of bits (which must -- be non-negative). rotateL :: Bits a => Exp a -> Exp Int -> Exp a -- | Rotate the argument right by the specified number of bits (which must -- be non-negative). rotateR :: Bits a => Exp a -> Exp Int -> Exp a -- | Return the number of set bits in the argument. This number is known as -- the population count or the Hamming weight. popCount :: Bits a => Exp a -> Exp Int infixl 7 .&. infixl 5 .|. infixl 6 `xor` infixl 8 `shift` infixl 8 `rotate` infixl 8 `shiftL` infixl 8 `shiftR` infixl 8 `rotateL` infixl 8 `rotateR` class Bits b => FiniteBits b -- | Return the number of bits in the type of the argument. finiteBitSize :: FiniteBits b => Exp b -> Exp Int -- | Count the number of zero bits preceding the most significant set bit. -- This can be used to compute a base-2 logarithm via: -- -- 
--   logBase2 x = finiteBitSize x - 1 - countLeadingZeros x
--
countLeadingZeros :: FiniteBits b => Exp b -> Exp Int -- | Count the number of zero bits following the least significant set bit. -- The related find-first-set operation can be expressed in terms -- of this as: -- -- 
--   findFirstSet x = 1 + countTrailingZeros x
--
countTrailingZeros :: FiniteBits b => Exp b -> Exp Int instance Data.Array.Accelerate.Data.Bits.FiniteBits GHC.Types.Bool instance Data.Array.Accelerate.Data.Bits.FiniteBits GHC.Types.Int instance Data.Array.Accelerate.Data.Bits.FiniteBits GHC.Int.Int8 instance Data.Array.Accelerate.Data.Bits.FiniteBits GHC.Int.Int16 instance Data.Array.Accelerate.Data.Bits.FiniteBits GHC.Int.Int32 instance Data.Array.Accelerate.Data.Bits.FiniteBits GHC.Int.Int64 instance Data.Array.Accelerate.Data.Bits.FiniteBits GHC.Types.Word instance Data.Array.Accelerate.Data.Bits.FiniteBits GHC.Word.Word8 instance Data.Array.Accelerate.Data.Bits.FiniteBits GHC.Word.Word16 instance Data.Array.Accelerate.Data.Bits.FiniteBits GHC.Word.Word32 instance Data.Array.Accelerate.Data.Bits.FiniteBits GHC.Word.Word64 instance Data.Array.Accelerate.Data.Bits.FiniteBits Foreign.C.Types.CInt instance Data.Array.Accelerate.Data.Bits.FiniteBits Foreign.C.Types.CUInt instance Data.Array.Accelerate.Data.Bits.FiniteBits Foreign.C.Types.CLong instance Data.Array.Accelerate.Data.Bits.FiniteBits Foreign.C.Types.CULong instance Data.Array.Accelerate.Data.Bits.FiniteBits Foreign.C.Types.CLLong instance Data.Array.Accelerate.Data.Bits.FiniteBits Foreign.C.Types.CULLong instance Data.Array.Accelerate.Data.Bits.FiniteBits Foreign.C.Types.CShort instance Data.Array.Accelerate.Data.Bits.FiniteBits Foreign.C.Types.CUShort instance Data.Array.Accelerate.Data.Bits.FiniteBits Foreign.C.Types.CChar instance Data.Array.Accelerate.Data.Bits.FiniteBits Foreign.C.Types.CSChar instance Data.Array.Accelerate.Data.Bits.FiniteBits Foreign.C.Types.CUChar instance Data.Array.Accelerate.Data.Bits.Bits GHC.Types.Bool instance Data.Array.Accelerate.Data.Bits.Bits GHC.Types.Int instance Data.Array.Accelerate.Data.Bits.Bits GHC.Int.Int8 instance Data.Array.Accelerate.Data.Bits.Bits GHC.Int.Int16 instance Data.Array.Accelerate.Data.Bits.Bits GHC.Int.Int32 instance Data.Array.Accelerate.Data.Bits.Bits GHC.Int.Int64 instance Data.Array.Accelerate.Data.Bits.Bits GHC.Types.Word instance Data.Array.Accelerate.Data.Bits.Bits GHC.Word.Word8 instance Data.Array.Accelerate.Data.Bits.Bits GHC.Word.Word16 instance Data.Array.Accelerate.Data.Bits.Bits GHC.Word.Word32 instance Data.Array.Accelerate.Data.Bits.Bits GHC.Word.Word64 instance Data.Array.Accelerate.Data.Bits.Bits Foreign.C.Types.CInt instance Data.Array.Accelerate.Data.Bits.Bits Foreign.C.Types.CUInt instance Data.Array.Accelerate.Data.Bits.Bits Foreign.C.Types.CLong instance Data.Array.Accelerate.Data.Bits.Bits Foreign.C.Types.CULong instance Data.Array.Accelerate.Data.Bits.Bits Foreign.C.Types.CLLong instance Data.Array.Accelerate.Data.Bits.Bits Foreign.C.Types.CULLong instance Data.Array.Accelerate.Data.Bits.Bits Foreign.C.Types.CShort instance Data.Array.Accelerate.Data.Bits.Bits Foreign.C.Types.CUShort instance Data.Array.Accelerate.Data.Bits.Bits Foreign.C.Types.CChar instance Data.Array.Accelerate.Data.Bits.Bits Foreign.C.Types.CSChar instance Data.Array.Accelerate.Data.Bits.Bits Foreign.C.Types.CUChar -- | Standard functions on rational numbers module Data.Array.Accelerate.Data.Ratio -- | Rational numbers, with numerator and denominator of some -- Integral type. -- -- Note that Ratio's instances inherit the deficiencies from the -- type parameter's. For example, Ratio Natural's Num -- instance has similar problems to Natural's. data Ratio a -- | Form the ratio of two integral numbers (%) :: Integral a => Exp a -> Exp a -> Exp (Ratio a) infixl 7 % pattern (:%) :: Elt a => Exp a -> Exp a -> Exp (Ratio a) numerator :: Exp (Ratio a) -> Elt a => Exp a denominator :: Exp (Ratio a) -> Elt a => Exp a instance Data.Array.Accelerate.Sugar.Elt.Elt a => Data.Array.Accelerate.Sugar.Elt.Elt (GHC.Real.Ratio a) instance Data.Array.Accelerate.Classes.Integral.Integral a => Data.Array.Accelerate.Classes.Eq.Eq (GHC.Real.Ratio a) instance Data.Array.Accelerate.Classes.Integral.Integral a => Data.Array.Accelerate.Classes.Ord.Ord (GHC.Real.Ratio a) instance Data.Array.Accelerate.Classes.Integral.Integral a => GHC.Num.Num (Data.Array.Accelerate.Smart.Exp (GHC.Real.Ratio a)) instance Data.Array.Accelerate.Classes.Integral.Integral a => GHC.Real.Fractional (Data.Array.Accelerate.Smart.Exp (GHC.Real.Ratio a)) instance (Data.Array.Accelerate.Classes.Integral.Integral a, Data.Array.Accelerate.Classes.FromIntegral.FromIntegral a GHC.Int.Int64) => Data.Array.Accelerate.Classes.RealFrac.RealFrac (GHC.Real.Ratio a) instance (Data.Array.Accelerate.Classes.Integral.Integral a, Data.Array.Accelerate.Classes.ToFloating.ToFloating a b) => Data.Array.Accelerate.Classes.ToFloating.ToFloating (GHC.Real.Ratio a) b instance (Data.Array.Accelerate.Classes.FromIntegral.FromIntegral a b, Data.Array.Accelerate.Classes.Integral.Integral b) => Data.Array.Accelerate.Classes.FromIntegral.FromIntegral a (GHC.Real.Ratio b) instance Data.Array.Accelerate.Classes.Integral.Integral a => GHC.Enum.Enum (Data.Array.Accelerate.Smart.Exp (GHC.Real.Ratio a)) -- | Semigroup instances for Accelerate module Data.Array.Accelerate.Data.Semigroup -- | The class of semigroups (types with an associative binary operation). -- -- Instances should satisfy the following: -- -- class Semigroup a -- | An associative operation. -- -- 
--   >>> [1,2,3] <> [4,5,6]
--   [1,2,3,4,5,6]
--
(<>) :: Semigroup a => a -> a -> a -- | Reduce a non-empty list with <> -- -- The default definition should be sufficient, but this can be -- overridden for efficiency. -- -- 
--   >>> import Data.List.NonEmpty
--   
--   >>> sconcat $ "Hello" :| [" ", "Haskell", "!"]
--   "Hello Haskell!"
--
sconcat :: Semigroup a => NonEmpty a -> a -- | Repeat a value n times. -- -- Given that this works on a Semigroup it is allowed to fail if -- you request 0 or fewer repetitions, and the default definition will do -- so. -- -- By making this a member of the class, idempotent semigroups and -- monoids can upgrade this to execute in <math> by picking -- stimes = stimesIdempotent or stimes = -- stimesIdempotentMonoid respectively. -- -- 
--   >>> stimes 4 [1]
--   [1,1,1,1]
--
stimes :: (Semigroup a, Integral b) => b -> a -> a infixr 6 <> newtype Min a Min :: a -> Min a [getMin] :: Min a -> a pattern Min_ :: Elt a => Exp a -> Exp (Min a) newtype Max a Max :: a -> Max a [getMax] :: Max a -> a pattern Max_ :: Elt a => Exp a -> Exp (Max a) instance Data.Array.Accelerate.Sugar.Elt.Elt a => Data.Array.Accelerate.Sugar.Elt.Elt (Data.Semigroup.Min a) instance (Data.Array.Accelerate.Lift.Lift Data.Array.Accelerate.Smart.Exp a, Data.Array.Accelerate.Sugar.Elt.Elt (Data.Array.Accelerate.Lift.Plain a)) => Data.Array.Accelerate.Lift.Lift Data.Array.Accelerate.Smart.Exp (Data.Semigroup.Min a) instance Data.Array.Accelerate.Sugar.Elt.Elt a => Data.Array.Accelerate.Lift.Unlift Data.Array.Accelerate.Smart.Exp (Data.Semigroup.Min (Data.Array.Accelerate.Smart.Exp a)) instance Data.Array.Accelerate.Classes.Bounded.Bounded a => GHC.Enum.Bounded (Data.Array.Accelerate.Smart.Exp (Data.Semigroup.Min a)) instance Data.Array.Accelerate.Classes.Num.Num a => GHC.Num.Num (Data.Array.Accelerate.Smart.Exp (Data.Semigroup.Min a)) instance Data.Array.Accelerate.Classes.Eq.Eq a => Data.Array.Accelerate.Classes.Eq.Eq (Data.Semigroup.Min a) instance Data.Array.Accelerate.Classes.Ord.Ord a => Data.Array.Accelerate.Classes.Ord.Ord (Data.Semigroup.Min a) instance Data.Array.Accelerate.Classes.Ord.Ord a => GHC.Base.Semigroup (Data.Array.Accelerate.Smart.Exp (Data.Semigroup.Min a)) instance (Data.Array.Accelerate.Classes.Ord.Ord a, Data.Array.Accelerate.Classes.Bounded.Bounded a) => GHC.Base.Monoid (Data.Array.Accelerate.Smart.Exp (Data.Semigroup.Min a)) instance Data.Array.Accelerate.Sugar.Elt.Elt a => Data.Array.Accelerate.Sugar.Elt.Elt (Data.Semigroup.Max a) instance (Data.Array.Accelerate.Lift.Lift Data.Array.Accelerate.Smart.Exp a, Data.Array.Accelerate.Sugar.Elt.Elt (Data.Array.Accelerate.Lift.Plain a)) => Data.Array.Accelerate.Lift.Lift Data.Array.Accelerate.Smart.Exp (Data.Semigroup.Max a) instance Data.Array.Accelerate.Sugar.Elt.Elt a => Data.Array.Accelerate.Lift.Unlift Data.Array.Accelerate.Smart.Exp (Data.Semigroup.Max (Data.Array.Accelerate.Smart.Exp a)) instance Data.Array.Accelerate.Classes.Bounded.Bounded a => GHC.Enum.Bounded (Data.Array.Accelerate.Smart.Exp (Data.Semigroup.Max a)) instance Data.Array.Accelerate.Classes.Num.Num a => GHC.Num.Num (Data.Array.Accelerate.Smart.Exp (Data.Semigroup.Max a)) instance Data.Array.Accelerate.Classes.Eq.Eq a => Data.Array.Accelerate.Classes.Eq.Eq (Data.Semigroup.Max a) instance Data.Array.Accelerate.Classes.Ord.Ord a => Data.Array.Accelerate.Classes.Ord.Ord (Data.Semigroup.Max a) instance Data.Array.Accelerate.Classes.Ord.Ord a => GHC.Base.Semigroup (Data.Array.Accelerate.Smart.Exp (Data.Semigroup.Max a)) instance (Data.Array.Accelerate.Classes.Ord.Ord a, Data.Array.Accelerate.Classes.Bounded.Bounded a) => GHC.Base.Monoid (Data.Array.Accelerate.Smart.Exp (Data.Semigroup.Max a)) instance GHC.Base.Semigroup (Data.Array.Accelerate.Smart.Exp ()) instance (Data.Array.Accelerate.Sugar.Elt.Elt a, Data.Array.Accelerate.Sugar.Elt.Elt b, GHC.Base.Semigroup (Data.Array.Accelerate.Smart.Exp a), GHC.Base.Semigroup (Data.Array.Accelerate.Smart.Exp b)) => GHC.Base.Semigroup (Data.Array.Accelerate.Smart.Exp (a, b)) instance (Data.Array.Accelerate.Sugar.Elt.Elt a, Data.Array.Accelerate.Sugar.Elt.Elt b, Data.Array.Accelerate.Sugar.Elt.Elt c, GHC.Base.Semigroup (Data.Array.Accelerate.Smart.Exp a), GHC.Base.Semigroup (Data.Array.Accelerate.Smart.Exp b), GHC.Base.Semigroup (Data.Array.Accelerate.Smart.Exp c)) => GHC.Base.Semigroup (Data.Array.Accelerate.Smart.Exp (a, b, c)) instance (Data.Array.Accelerate.Sugar.Elt.Elt a, Data.Array.Accelerate.Sugar.Elt.Elt b, Data.Array.Accelerate.Sugar.Elt.Elt c, Data.Array.Accelerate.Sugar.Elt.Elt d, GHC.Base.Semigroup (Data.Array.Accelerate.Smart.Exp a), GHC.Base.Semigroup (Data.Array.Accelerate.Smart.Exp b), GHC.Base.Semigroup (Data.Array.Accelerate.Smart.Exp c), GHC.Base.Semigroup (Data.Array.Accelerate.Smart.Exp d)) => GHC.Base.Semigroup (Data.Array.Accelerate.Smart.Exp (a, b, c, d)) instance (Data.Array.Accelerate.Sugar.Elt.Elt a, Data.Array.Accelerate.Sugar.Elt.Elt b, Data.Array.Accelerate.Sugar.Elt.Elt c, Data.Array.Accelerate.Sugar.Elt.Elt d, Data.Array.Accelerate.Sugar.Elt.Elt e, GHC.Base.Semigroup (Data.Array.Accelerate.Smart.Exp a), GHC.Base.Semigroup (Data.Array.Accelerate.Smart.Exp b), GHC.Base.Semigroup (Data.Array.Accelerate.Smart.Exp c), GHC.Base.Semigroup (Data.Array.Accelerate.Smart.Exp d), GHC.Base.Semigroup (Data.Array.Accelerate.Smart.Exp e)) => GHC.Base.Semigroup (Data.Array.Accelerate.Smart.Exp (a, b, c, d, e)) -- | Monoid instances for Accelerate module Data.Array.Accelerate.Data.Monoid -- | The class of monoids (types with an associative binary operation that -- has an identity). Instances should satisfy the following: -- -- -- -- The method names refer to the monoid of lists under concatenation, but -- there are many other instances. -- -- Some types can be viewed as a monoid in more than one way, e.g. both -- addition and multiplication on numbers. In such cases we often define -- newtypes and make those instances of Monoid, e.g. -- Sum and Product. -- -- NOTE: Semigroup is a superclass of Monoid since -- base-4.11.0.0. class Semigroup a => Monoid a -- | Identity of mappend -- -- 
--   >>> "Hello world" <> mempty
--   "Hello world"
--
mempty :: Monoid a => a -- | An associative operation -- -- NOTE: This method is redundant and has the default -- implementation mappend = (<>) since -- base-4.11.0.0. Should it be implemented manually, since -- mappend is a synonym for (<>), it is expected that -- the two functions are defined the same way. In a future GHC release -- mappend will be removed from Monoid. mappend :: Monoid a => a -> a -> a -- | Fold a list using the monoid. -- -- For most types, the default definition for mconcat will be -- used, but the function is included in the class definition so that an -- optimized version can be provided for specific types. -- -- 
--   >>> mconcat ["Hello", " ", "Haskell", "!"]
--   "Hello Haskell!"
--
mconcat :: Monoid a => [a] -> a -- | An associative operation. -- -- 
--   >>> [1,2,3] <> [4,5,6]
--   [1,2,3,4,5,6]
--
(<>) :: Semigroup a => a -> a -> a infixr 6 <> -- | Monoid under addition. -- -- 
--   >>> getSum (Sum 1 <> Sum 2 <> mempty)
--   3
--
newtype Sum a Sum :: a -> Sum a [getSum] :: Sum a -> a pattern Sum_ :: Elt a => Exp a -> Exp (Sum a) -- | Monoid under multiplication. -- -- 
--   >>> getProduct (Product 3 <> Product 4 <> mempty)
--   12
--
newtype Product a Product :: a -> Product a [getProduct] :: Product a -> a pattern Product_ :: Elt a => Exp a -> Exp (Product a) instance Data.Array.Accelerate.Sugar.Elt.Elt a => Data.Array.Accelerate.Sugar.Elt.Elt (Data.Semigroup.Internal.Sum a) instance (Data.Array.Accelerate.Lift.Lift Data.Array.Accelerate.Smart.Exp a, Data.Array.Accelerate.Sugar.Elt.Elt (Data.Array.Accelerate.Lift.Plain a)) => Data.Array.Accelerate.Lift.Lift Data.Array.Accelerate.Smart.Exp (Data.Semigroup.Internal.Sum a) instance Data.Array.Accelerate.Sugar.Elt.Elt a => Data.Array.Accelerate.Lift.Unlift Data.Array.Accelerate.Smart.Exp (Data.Semigroup.Internal.Sum (Data.Array.Accelerate.Smart.Exp a)) instance Data.Array.Accelerate.Classes.Bounded.Bounded a => GHC.Enum.Bounded (Data.Array.Accelerate.Smart.Exp (Data.Semigroup.Internal.Sum a)) instance Data.Array.Accelerate.Classes.Num.Num a => GHC.Num.Num (Data.Array.Accelerate.Smart.Exp (Data.Semigroup.Internal.Sum a)) instance Data.Array.Accelerate.Classes.Eq.Eq a => Data.Array.Accelerate.Classes.Eq.Eq (Data.Semigroup.Internal.Sum a) instance Data.Array.Accelerate.Classes.Ord.Ord a => Data.Array.Accelerate.Classes.Ord.Ord (Data.Semigroup.Internal.Sum a) instance Data.Array.Accelerate.Classes.Num.Num a => GHC.Base.Monoid (Data.Array.Accelerate.Smart.Exp (Data.Semigroup.Internal.Sum a)) instance Data.Array.Accelerate.Classes.Num.Num a => GHC.Base.Semigroup (Data.Array.Accelerate.Smart.Exp (Data.Semigroup.Internal.Sum a)) instance Data.Array.Accelerate.Sugar.Elt.Elt a => Data.Array.Accelerate.Sugar.Elt.Elt (Data.Semigroup.Internal.Product a) instance (Data.Array.Accelerate.Lift.Lift Data.Array.Accelerate.Smart.Exp a, Data.Array.Accelerate.Sugar.Elt.Elt (Data.Array.Accelerate.Lift.Plain a)) => Data.Array.Accelerate.Lift.Lift Data.Array.Accelerate.Smart.Exp (Data.Semigroup.Internal.Product a) instance Data.Array.Accelerate.Sugar.Elt.Elt a => Data.Array.Accelerate.Lift.Unlift Data.Array.Accelerate.Smart.Exp (Data.Semigroup.Internal.Product (Data.Array.Accelerate.Smart.Exp a)) instance Data.Array.Accelerate.Classes.Bounded.Bounded a => GHC.Enum.Bounded (Data.Array.Accelerate.Smart.Exp (Data.Semigroup.Internal.Product a)) instance Data.Array.Accelerate.Classes.Num.Num a => GHC.Num.Num (Data.Array.Accelerate.Smart.Exp (Data.Semigroup.Internal.Product a)) instance Data.Array.Accelerate.Classes.Eq.Eq a => Data.Array.Accelerate.Classes.Eq.Eq (Data.Semigroup.Internal.Product a) instance Data.Array.Accelerate.Classes.Ord.Ord a => Data.Array.Accelerate.Classes.Ord.Ord (Data.Semigroup.Internal.Product a) instance Data.Array.Accelerate.Classes.Num.Num a => GHC.Base.Monoid (Data.Array.Accelerate.Smart.Exp (Data.Semigroup.Internal.Product a)) instance Data.Array.Accelerate.Classes.Num.Num a => GHC.Base.Semigroup (Data.Array.Accelerate.Smart.Exp (Data.Semigroup.Internal.Product a)) instance GHC.Base.Monoid (Data.Array.Accelerate.Smart.Exp ()) instance (Data.Array.Accelerate.Sugar.Elt.Elt a, Data.Array.Accelerate.Sugar.Elt.Elt b, GHC.Base.Monoid (Data.Array.Accelerate.Smart.Exp a), GHC.Base.Monoid (Data.Array.Accelerate.Smart.Exp b)) => GHC.Base.Monoid (Data.Array.Accelerate.Smart.Exp (a, b)) instance (Data.Array.Accelerate.Sugar.Elt.Elt a, Data.Array.Accelerate.Sugar.Elt.Elt b, Data.Array.Accelerate.Sugar.Elt.Elt c, GHC.Base.Monoid (Data.Array.Accelerate.Smart.Exp a), GHC.Base.Monoid (Data.Array.Accelerate.Smart.Exp b), GHC.Base.Monoid (Data.Array.Accelerate.Smart.Exp c)) => GHC.Base.Monoid (Data.Array.Accelerate.Smart.Exp (a, b, c)) instance (Data.Array.Accelerate.Sugar.Elt.Elt a, Data.Array.Accelerate.Sugar.Elt.Elt b, Data.Array.Accelerate.Sugar.Elt.Elt c, Data.Array.Accelerate.Sugar.Elt.Elt d, GHC.Base.Monoid (Data.Array.Accelerate.Smart.Exp a), GHC.Base.Monoid (Data.Array.Accelerate.Smart.Exp b), GHC.Base.Monoid (Data.Array.Accelerate.Smart.Exp c), GHC.Base.Monoid (Data.Array.Accelerate.Smart.Exp d)) => GHC.Base.Monoid (Data.Array.Accelerate.Smart.Exp (a, b, c, d)) instance (Data.Array.Accelerate.Sugar.Elt.Elt a, Data.Array.Accelerate.Sugar.Elt.Elt b, Data.Array.Accelerate.Sugar.Elt.Elt c, Data.Array.Accelerate.Sugar.Elt.Elt d, Data.Array.Accelerate.Sugar.Elt.Elt e, GHC.Base.Monoid (Data.Array.Accelerate.Smart.Exp a), GHC.Base.Monoid (Data.Array.Accelerate.Smart.Exp b), GHC.Base.Monoid (Data.Array.Accelerate.Smart.Exp c), GHC.Base.Monoid (Data.Array.Accelerate.Smart.Exp d), GHC.Base.Monoid (Data.Array.Accelerate.Smart.Exp e)) => GHC.Base.Monoid (Data.Array.Accelerate.Smart.Exp (a, b, c, d, e)) module Data.Array.Accelerate.Data.Maybe -- | The Maybe type encapsulates an optional value. A value of type -- Maybe a either contains a value of type a -- (represented as Just a), or it is empty (represented -- as Nothing). Using Maybe is a good way to deal with -- errors or exceptional cases without resorting to drastic measures such -- as error. -- -- The Maybe type is also a monad. It is a simple kind of error -- monad, where all errors are represented by Nothing. A richer -- error monad can be built using the Either type. data Maybe a Nothing :: Maybe a Just :: a -> Maybe a pattern Nothing_ :: forall a_11. (HasCallStack, Elt a_11) => Exp (Maybe a_11) pattern Just_ :: forall a_11. (HasCallStack, Elt a_11) => Exp a_11 -> Exp (Maybe a_11) -- | The maybe function takes a default value, a function, and a -- Maybe value. If the Maybe value is nothing, the default -- value is returned; otherwise, it applies the function to the value -- inside the Just and returns the result maybe :: (Elt a, Elt b) => Exp b -> (Exp a -> Exp b) -> Exp (Maybe a) -> Exp b -- | Returns True if the argument is of the form Just _ isJust :: Elt a => Exp (Maybe a) -> Exp Bool -- | Returns True if the argument is Nothing isNothing :: Elt a => Exp (Maybe a) -> Exp Bool -- | The fromMaybe function takes a default value and a Maybe -- value. If the Maybe is Nothing, the default value is -- returned; otherwise, it returns the value contained in the -- Maybe. fromMaybe :: Elt a => Exp a -> Exp (Maybe a) -> Exp a -- | The fromJust function extracts the element out of the -- Just constructor. If the argument was actually Nothing, -- you will get an undefined value instead. fromJust :: Elt a => Exp (Maybe a) -> Exp a -- | Extract from an array all of the Just values, together with a -- segment descriptor indicating how many elements along each dimension -- were returned. justs :: (Shape sh, Slice sh, Elt a) => Acc (Array (sh :. Int) (Maybe a)) -> Acc (Vector a, Array sh Int) instance Data.Array.Accelerate.Data.Functor.Functor GHC.Maybe.Maybe instance Data.Array.Accelerate.Classes.Eq.Eq a => Data.Array.Accelerate.Classes.Eq.Eq (GHC.Maybe.Maybe a) instance Data.Array.Accelerate.Classes.Ord.Ord a => Data.Array.Accelerate.Classes.Ord.Ord (GHC.Maybe.Maybe a) instance (GHC.Base.Monoid (Data.Array.Accelerate.Smart.Exp a), Data.Array.Accelerate.Sugar.Elt.Elt a) => GHC.Base.Monoid (Data.Array.Accelerate.Smart.Exp (GHC.Maybe.Maybe a)) instance (GHC.Base.Semigroup (Data.Array.Accelerate.Smart.Exp a), Data.Array.Accelerate.Sugar.Elt.Elt a) => GHC.Base.Semigroup (Data.Array.Accelerate.Smart.Exp (GHC.Maybe.Maybe a)) instance (Data.Array.Accelerate.Lift.Lift Data.Array.Accelerate.Smart.Exp a, Data.Array.Accelerate.Sugar.Elt.Elt (Data.Array.Accelerate.Lift.Plain a)) => Data.Array.Accelerate.Lift.Lift Data.Array.Accelerate.Smart.Exp (GHC.Maybe.Maybe a) -- | Combine folds in Applicative style to generate multiple results -- with a single pass over the array. Based on Max Rabkin's "Beautiful -- Folding" [1] and talks by Gabriel Gonzalez [2]. -- --
    -- --
  1. http://squing.blogspot.com/2008/11/beautiful-folding.html
    2. --
  2. https://www.youtube.com/watch?v=6a5Ti0r8Q2s
    3. --
module Data.Array.Accelerate.Data.Fold -- | Fold describes how to process data of some input type -- into some output type, via a reduction using some -- intermediate Monoid w. For example, both sum and -- length below use the Sum monoid: -- -- 
--   sum = Fold (lift . Sum) (getSum . unlift)
--   length = Fold (\_ -> 1) (getSum . unlift)
--
-- -- The key is that Folds can be combined using Applicative -- in order to produce multiple outputs from a single reduction of -- the array. For example: -- -- 
--   average = (/) <$> sum <*> length
--
-- -- This computes both the sum of the array as well as its length in a -- single traversal, then combines both results to compute the average. -- -- Because Fold has some numeric instances, this can also be -- defined more succinctly as: -- -- 
--   average = sum / length
--
-- -- A more complex example: -- -- 
--   sumOfSquares = Fold (lift . Sum . (^2)) (getSum . unlift)
--   standardDeviation = sqrt ((sumOfSquares / length) - (sum / length) ^ 2)
--
-- -- These will all execute with a single reduction kernel and a single map -- to summarise (combine) the results. data Fold i o [Fold] :: (Elt w, Monoid (Exp w)) => (i -> Exp w) -> (Exp w -> o) -> Fold i o -- | Apply a Fold to an array. runFold :: (Shape sh, Elt i, Elt o) => Fold (Exp i) (Exp o) -> Acc (Array (sh :. Int) i) -> Acc (Array sh o) instance GHC.Base.Functor (Data.Array.Accelerate.Data.Fold.Fold i) instance GHC.Base.Applicative (Data.Array.Accelerate.Data.Fold.Fold i) instance Data.Array.Accelerate.Classes.Num.Num b => GHC.Num.Num (Data.Array.Accelerate.Data.Fold.Fold a (Data.Array.Accelerate.Smart.Exp b)) instance Data.Array.Accelerate.Classes.Fractional.Fractional b => GHC.Real.Fractional (Data.Array.Accelerate.Data.Fold.Fold a (Data.Array.Accelerate.Smart.Exp b)) instance Data.Array.Accelerate.Classes.Floating.Floating b => GHC.Float.Floating (Data.Array.Accelerate.Data.Fold.Fold a (Data.Array.Accelerate.Smart.Exp b)) module Data.Array.Accelerate.Data.Either -- | The Either type represents values with two possibilities: a -- value of type Either a b is either Left -- a or Right b. -- -- The Either type is sometimes used to represent a value which is -- either correct or an error; by convention, the Left constructor -- is used to hold an error value and the Right constructor is -- used to hold a correct value (mnemonic: "right" also means "correct"). -- --

Examples

-- -- The type Either String Int is the type -- of values which can be either a String or an Int. The -- Left constructor can be used only on Strings, and the -- Right constructor can be used only on Ints: -- -- 
--   >>> let s = Left "foo" :: Either String Int
--   
--   >>> s
--   Left "foo"
--   
--   >>> let n = Right 3 :: Either String Int
--   
--   >>> n
--   Right 3
--   
--   >>> :type s
--   s :: Either String Int
--   
--   >>> :type n
--   n :: Either String Int
--
-- -- The fmap from our Functor instance will ignore -- Left values, but will apply the supplied function to values -- contained in a Right: -- -- 
--   >>> let s = Left "foo" :: Either String Int
--   
--   >>> let n = Right 3 :: Either String Int
--   
--   >>> fmap (*2) s
--   Left "foo"
--   
--   >>> fmap (*2) n
--   Right 6
--
-- -- The Monad instance for Either allows us to chain -- together multiple actions which may fail, and fail overall if any of -- the individual steps failed. First we'll write a function that can -- either parse an Int from a Char, or fail. -- -- 
--   >>> import Data.Char ( digitToInt, isDigit )
--   
--   >>> :{
--       let parseEither :: Char -> Either String Int
--           parseEither c
--             | isDigit c = Right (digitToInt c)
--             | otherwise = Left "parse error"
--   
--   >>> :}
--
-- -- The following should work, since both '1' and '2' -- can be parsed as Ints. -- -- 
--   >>> :{
--       let parseMultiple :: Either String Int
--           parseMultiple = do
--             x <- parseEither '1'
--             y <- parseEither '2'
--             return (x + y)
--   
--   >>> :}
--
-- -- 
--   >>> parseMultiple
--   Right 3
--
-- -- But the following should fail overall, since the first operation where -- we attempt to parse 'm' as an Int will fail: -- -- 
--   >>> :{
--       let parseMultiple :: Either String Int
--           parseMultiple = do
--             x <- parseEither 'm'
--             y <- parseEither '2'
--             return (x + y)
--   
--   >>> :}
--
-- -- 
--   >>> parseMultiple
--   Left "parse error"
--
data Either a b Left :: a -> Either a b Right :: b -> Either a b pattern Left_ :: forall a_ac3a b_ac3b. (HasCallStack, Elt a_ac3a, Elt b_ac3b) => Exp a_ac3a -> Exp (Either a_ac3a b_ac3b) pattern Right_ :: forall a_ac3a b_ac3b. (HasCallStack, Elt a_ac3a, Elt b_ac3b) => Exp b_ac3b -> Exp (Either a_ac3a b_ac3b) -- | The either function performs case analysis on the Either -- type. If the value is Left a, apply the first function -- to a; if it is Right b, apply the second -- function to b. either :: (Elt a, Elt b, Elt c) => (Exp a -> Exp c) -> (Exp b -> Exp c) -> Exp (Either a b) -> Exp c -- | Return True if the argument is a Left-value isLeft :: (Elt a, Elt b) => Exp (Either a b) -> Exp Bool -- | Return True if the argument is a Right-value isRight :: (Elt a, Elt b) => Exp (Either a b) -> Exp Bool -- | The fromLeft function extracts the element out of the -- Left constructor. If the argument was actually Right, -- you will get an undefined value instead. fromLeft :: (Elt a, Elt b) => Exp (Either a b) -> Exp a -- | The fromRight function extracts the element out of the -- Right constructor. If the argument was actually Left, -- you will get an undefined value instead. fromRight :: (Elt a, Elt b) => Exp (Either a b) -> Exp b -- | Extract from the array of Either all of the Left -- elements, together with a segment descriptor indicating how many -- elements along each dimension were returned. lefts :: (Shape sh, Slice sh, Elt a, Elt b) => Acc (Array (sh :. Int) (Either a b)) -> Acc (Vector a, Array sh Int) -- | Extract from the array of Either all of the Right -- elements, together with a segment descriptor indicating how many -- elements along each dimension were returned. rights :: (Shape sh, Slice sh, Elt a, Elt b) => Acc (Array (sh :. Int) (Either a b)) -> Acc (Vector b, Array sh Int) instance Data.Array.Accelerate.Sugar.Elt.Elt a => Data.Array.Accelerate.Data.Functor.Functor (Data.Either.Either a) instance (Data.Array.Accelerate.Classes.Eq.Eq a, Data.Array.Accelerate.Classes.Eq.Eq b) => Data.Array.Accelerate.Classes.Eq.Eq (Data.Either.Either a b) instance (Data.Array.Accelerate.Classes.Ord.Ord a, Data.Array.Accelerate.Classes.Ord.Ord b) => Data.Array.Accelerate.Classes.Ord.Ord (Data.Either.Either a b) instance (Data.Array.Accelerate.Sugar.Elt.Elt a, Data.Array.Accelerate.Sugar.Elt.Elt b) => GHC.Base.Semigroup (Data.Array.Accelerate.Smart.Exp (Data.Either.Either a b)) instance (Data.Array.Accelerate.Lift.Lift Data.Array.Accelerate.Smart.Exp a, Data.Array.Accelerate.Lift.Lift Data.Array.Accelerate.Smart.Exp b, Data.Array.Accelerate.Sugar.Elt.Elt (Data.Array.Accelerate.Lift.Plain a), Data.Array.Accelerate.Sugar.Elt.Elt (Data.Array.Accelerate.Lift.Plain b)) => Data.Array.Accelerate.Lift.Lift Data.Array.Accelerate.Smart.Exp (Data.Either.Either a b) -- | Complex numbers, stored in the usual C-style array-of-struct -- representation, for easy interoperability. module Data.Array.Accelerate.Data.Complex -- | Complex numbers are an algebraic type. -- -- For a complex number z, abs z is a number -- with the magnitude of z, but oriented in the positive real -- direction, whereas signum z has the phase of -- z, but unit magnitude. -- -- The Foldable and Traversable instances traverse the real -- part first. -- -- Note that Complex's instances inherit the deficiencies from the -- type parameter's. For example, Complex Float's Ord -- instance has similar problems to Float's. data Complex a -- | forms a complex number from its real and imaginary rectangular -- components. (:+) :: !a -> !a -> Complex a infix 6 :+ pattern (::+) :: Elt a => Exp a -> Exp a -> Exp (Complex a) infix 6 ::+ -- | Return the real part of a complex number real :: Elt a => Exp (Complex a) -> Exp a -- | Return the imaginary part of a complex number imag :: Elt a => Exp (Complex a) -> Exp a -- | Form a complex number from polar components of magnitude and phase. mkPolar :: forall a. Floating a => Exp a -> Exp a -> Exp (Complex a) -- | cis t is a complex value with magnitude 1 and -- phase t (modulo 2*pi). cis :: forall a. Floating a => Exp a -> Exp (Complex a) -- | The function polar takes a complex number and returns a -- (magnitude, phase) pair in canonical form: the magnitude is -- non-negative, and the phase in the range (-pi, -- pi]; if the magnitude is zero, then so is the phase. polar :: RealFloat a => Exp (Complex a) -> Exp (a, a) -- | The non-negative magnitude of a complex number magnitude :: RealFloat a => Exp (Complex a) -> Exp a -- | As magnitude, but ignore floating point rounding and use the -- traditional (simpler to evaluate) definition. magnitude' :: RealFloat a => Exp (Complex a) -> Exp a -- | The phase of a complex number, in the range (-pi, -- pi]. If the magnitude is zero, then so is the phase. phase :: RealFloat a => Exp (Complex a) -> Exp a -- | Return the complex conjugate of a complex number, defined as -- -- 
--   conjugate(Z) = X - iY
--
conjugate :: Num a => Exp (Complex a) -> Exp (Complex a) instance Data.Array.Accelerate.Sugar.Elt.Elt a => Data.Array.Accelerate.Sugar.Elt.Elt (Data.Complex.Complex a) instance (Data.Array.Accelerate.Lift.Lift Data.Array.Accelerate.Smart.Exp a, Data.Array.Accelerate.Sugar.Elt.Elt (Data.Array.Accelerate.Lift.Plain a)) => Data.Array.Accelerate.Lift.Lift Data.Array.Accelerate.Smart.Exp (Data.Complex.Complex a) instance Data.Array.Accelerate.Sugar.Elt.Elt a => Data.Array.Accelerate.Lift.Unlift Data.Array.Accelerate.Smart.Exp (Data.Complex.Complex (Data.Array.Accelerate.Smart.Exp a)) instance Data.Array.Accelerate.Classes.Eq.Eq a => Data.Array.Accelerate.Classes.Eq.Eq (Data.Complex.Complex a) instance Data.Array.Accelerate.Classes.RealFloat.RealFloat a => GHC.Num.Num (Data.Array.Accelerate.Smart.Exp (Data.Complex.Complex a)) instance Data.Array.Accelerate.Classes.RealFloat.RealFloat a => GHC.Real.Fractional (Data.Array.Accelerate.Smart.Exp (Data.Complex.Complex a)) instance Data.Array.Accelerate.Classes.RealFloat.RealFloat a => GHC.Float.Floating (Data.Array.Accelerate.Smart.Exp (Data.Complex.Complex a)) instance (Data.Array.Accelerate.Classes.FromIntegral.FromIntegral a b, Data.Array.Accelerate.Classes.Num.Num b, Data.Array.Accelerate.Sugar.Elt.Elt (Data.Complex.Complex b)) => Data.Array.Accelerate.Classes.FromIntegral.FromIntegral a (Data.Complex.Complex b) instance Data.Array.Accelerate.Data.Functor.Functor Data.Complex.Complex -- | Data.Array.Accelerate defines an embedded language of array -- computations for high-performance computing in Haskell. Computations -- on multi-dimensional, regular arrays are expressed in the form of -- parameterised collective operations such as maps, reductions, and -- permutations. These computations are online compiled and can be -- executed on a range of architectures. -- -- -- -- The types representing array computations are only exported -- abstractly; client code can generate array computations and submit -- them for execution, but it cannot inspect these computations. This is -- to allow for more flexibility for future extensions of this library. -- -- -- -- Accelerate distinguishes the types of collective operations Acc -- from the type of scalar operations Exp to achieve a stratified -- language. Collective operations comprise many scalar computations that -- are executed in parallel, but scalar computations can not -- contain collective operations. This separation excludes nested, -- irregular data-parallelism statically; instead, Accelerate is -- limited to flat data-parallelism involving only regular, -- multi-dimensional arrays. -- -- -- -- Accelerate uses a number of scalar and array optimisations, including -- array fusion, in order to improve the performance of programs. -- Fusing a program entails combining successive traversals (loops) over -- an array into a single traversal, which reduces memory traffic and -- eliminates intermediate arrays. -- -- -- -- Several backends are available which can be used to evaluate -- accelerate programs: -- -- -- -- -- -- -- -- -- -- Accelerate and its associated packages are available on both Hackage -- and Stackage. A project template is available to help create a new -- projects using the stack build tool. To create a new project -- using the template: -- -- 
--   stack new PROJECT_NAME https://github.com/AccelerateHS/accelerate/raw/stable/accelerate.hsfiles
--
-- -- -- -- -- -- -- -- -- -- -- -- Accelerate tends to stress GHC's garbage collector, so it helps to -- increase the default GC allocation sizes. This can be done when -- running an executable by specifying RTS options on the command line, -- for example: -- -- 
--   ./foo +RTS -A64M -n2M -RTS
--
-- -- You can make these settings the default by adding the following -- ghc-options to your .cabal file or similar: -- -- 
--   ghc-options: -with-rtsopts=-n2M -with-rtsopts=-A64M
--
-- -- To specify RTS options you will also need to compile your program with -- -rtsopts. module Data.Array.Accelerate -- | Accelerate is an embedded language that distinguishes between -- vanilla arrays (e.g. in Haskell memory on the CPU) and embedded arrays -- (e.g. in device memory on a GPU), as well as the computations on both -- of these. Since Accelerate is an embedded language, programs written -- in Accelerate are not compiled by the Haskell compiler (GHC). Rather, -- each Accelerate backend is a runtime compiler which generates -- and executes parallel SIMD code of the target language at application -- runtime. -- -- The type constructor Acc represents embedded collective array -- operations. A term of type Acc a is an Accelerate program -- which, once executed, will produce a value of type a (an -- Array or a tuple of Arrays). Collective operations of -- type Acc a comprise many scalar expressions, wrapped -- in type constructor Exp, which will be executed in parallel. -- Although collective operations comprise many scalar operations -- executed in parallel, scalar operations cannot initiate new -- collective operations: this stratification between scalar operations -- in Exp and array operations in Acc helps statically -- exclude nested data parallelism, which is difficult to execute -- efficiently on constrained hardware such as GPUs. -- -- -- -- As a simple example, to compute a vector dot product we can write: -- -- 
--   dotp :: Num a => Vector a -> Vector a -> Acc (Scalar a)
--   dotp xs ys =
--     let
--         xs' = use xs
--         ys' = use ys
--     in
--     fold (+) 0 ( zipWith (*) xs' ys' )
--
-- -- The function dotp consumes two one-dimensional arrays -- (Vectors) of values, and produces a single (Scalar) -- result as output. As the return type is wrapped in the type -- Acc, we see that it is an embedded Accelerate computation - it -- will be evaluated in the object language of dynamically -- generated parallel code, rather than the meta language of -- vanilla Haskell. -- -- As the arguments to dotp are plain Haskell arrays, to make -- these available to Accelerate computations they must be embedded with -- the use function. -- -- An Accelerate backend is used to evaluate the embedded computation and -- return the result back to vanilla Haskell. Calling the run -- function of a backend will generate code for the target architecture, -- compile, and execute it. For example, the following backends are -- available: -- -- -- -- See also Exp, which encapsulates embedded scalar -- computations. -- -- -- -- As mentioned above, embedded scalar computations of type Exp -- can not initiate further collective operations. -- -- Suppose we wanted to extend our above dotp function to -- matrix-vector multiplication. First, let's rewrite our dotp -- function to take Acc arrays as input (which is typically what -- we want): -- -- 
--   dotp :: Num a => Acc (Vector a) -> Acc (Vector a) -> Acc (Scalar a)
--   dotp xs ys = fold (+) 0 ( zipWith (*) xs ys )
--
-- -- We might then be inclined to lift our dot-product program to the -- following (incorrect) matrix-vector product, by applying dotp -- to each row of the input matrix: -- -- 
--   mvm_ndp :: Num a => Acc (Matrix a) -> Acc (Vector a) -> Acc (Vector a)
--   mvm_ndp mat vec =
--     let Z :. rows :. cols  = unlift (shape mat)  :: Z :. Exp Int :. Exp Int
--     in  generate (index1 rows)
--                  (\row -> the $ dotp vec (slice mat (lift (row :. All))))
--
-- -- Here, we use generate to create a one-dimensional vector by -- applying at each index a function to slice out the -- corresponding row of the matrix to pass to the dotp -- function. However, since both generate and slice are -- data-parallel operations, and moreover that slice depends -- on the argument row given to it by the generate -- function, this definition requires nested data-parallelism, and is -- thus not permitted. The clue that this definition is invalid is that -- in order to create a program which will be accepted by the type -- checker, we must use the function the to retrieve the result of -- the dotp operation, effectively concealing that dotp -- is a collective array computation in order to match the type expected -- by generate, which is that of scalar expressions. Additionally, -- since we have fooled the type-checker, this problem will only be -- discovered at program runtime. -- -- In order to avoid this problem, we can make use of the fact that -- operations in Accelerate are rank polymorphic. The fold -- operation reduces along the innermost dimension of an array of -- arbitrary rank, reducing the rank (dimensionality) of the array by -- one. Thus, we can replicate the input vector to as many -- rows there are in the input matrix, and perform the -- dot-product of the vector with every row simultaneously: -- -- 
--   mvm :: A.Num a => Acc (Matrix a) -> Acc (Vector a) -> Acc (Vector a)
--   mvm mat vec =
--     let Z :. rows :. cols = unlift (shape mat) :: Z :. Exp Int :. Exp Int
--         vec'              = A.replicate (lift (Z :. rows :. All)) vec
--     in
--     A.fold (+) 0 ( A.zipWith (*) mat vec' )
--
-- -- Note that the intermediate, replicated array vec' is never -- actually created in memory; it will be fused directly into the -- operation which consumes it. We discuss fusion next. -- -- -- -- Array computations of type Acc will be subject to array -- fusion; Accelerate will combine individual Acc computations -- into a single computation, which reduces the number of traversals over -- the input data and thus improves performance. As such, it is often -- useful to have some intuition on when fusion should occur. -- -- The main idea is to first partition array operations into two -- categories: -- --
    --
  1. Element-wise operations, such as map, generate, and -- backpermute. Each element of these operations can be computed -- independently of all others.
    2. --
  2. Collective operations such as fold, scanl, and -- stencil. To compute each output element of these operations -- requires reading multiple elements from the input array(s).
    3. --
-- -- Element-wise operations fuse together whenever the consumer operation -- uses a single element of the input array. Element-wise operations can -- both fuse their inputs into themselves, as well be fused into later -- operations. Both these examples should fuse into a single loop: -- -- -- -- If the consumer operation uses more than one element of the input -- array (typically, via generate indexing an array multiple -- times), then the input array will be completely evaluated first; no -- fusion occurs in this case, because fusing the first operation into -- the second implies duplicating work. -- -- On the other hand, collective operations can fuse their input arrays -- into themselves, but on output always evaluate to an array; collective -- operations will not be fused into a later step. For example: -- -- -- Here the element-wise sequence (use + generate + -- zipWith) will fuse into a single operation, which then fuses -- into the collective fold operation. At this point in the -- program the fold must now be evaluated. In the final step the -- map reads in the array produced by fold. As there is no -- fusion between the fold and map steps, this program -- consists of two "loops"; one for the use + generate + -- zipWith + fold step, and one for the final map -- step. -- -- You can see how many operations will be executed in the fused program -- by Show-ing the Acc program, or by using the debugging -- option -ddump-dot to save the program as a graphviz DOT file. -- -- As a special note, the operations unzip and reshape, -- when applied to a real array, are executed in constant time, so in -- this situation these operations will not be fused. -- -- -- -- data Acc a -- | Dense, regular, multi-dimensional arrays. -- -- The Array is the core computational unit of Accelerate; all -- programs in Accelerate take zero or more arrays as input and produce -- one or more arrays as output. The Array type has two type -- parameters: -- -- -- -- Array data is store unboxed in an unzipped struct-of-array -- representation. Elements are laid out in row-major order (the -- right-most index of a Shape is the fastest varying). The -- allowable array element types are members of the Elt class, -- which roughly consists of: -- -- -- -- Note that Array itself is not an allowable element type---there -- are no nested arrays in Accelerate, regular arrays only! -- -- If device and host memory are separate, arrays will be transferred to -- the device when necessary (possibly asynchronously and in parallel -- with other tasks) and cached on the device if sufficient memory is -- available. Arrays are made available to embedded language computations -- via use. -- -- Section "Getting data in" lists functions for getting data into and -- out of the Array type. data Array sh e -- | The Arrays class characterises the types which can appear in -- collective Accelerate computations of type Acc. -- -- Arrays consists of nested tuples of individual Arrays, -- currently up to 16-elements wide. Accelerate computations can thereby -- return multiple results. class Arrays a type Scalar = Array DIM0 " Scalar arrays hold a single element" type Vector = Array DIM1 " Vectors are one-dimensional arrays" type Matrix = Array DIM2 " Matrices are two-dimensional arrays" -- | Segment descriptor (vector of segment lengths) -- -- To represent nested one-dimensional arrays, we use a flat array of -- data values in conjunction with a segment descriptor, which -- stores the lengths of the sub-arrays. type Segments = Vector -- | The Elt class characterises the allowable array element types, -- and hence the types which can appear in scalar Accelerate expressions -- of type Exp. -- -- Accelerate arrays consist of simple atomic types as well as nested -- tuples thereof, stored efficiently in memory as consecutive unpacked -- elements without pointers. It roughly consists of: -- -- -- -- Adding new instances for Elt consists of explaining to -- Accelerate how to map between your data type and a (tuple of) -- primitive values. For examples see: -- -- -- -- For simple types it is possible to derive Elt automatically, -- for example: -- -- 
--   data Point = Point Int Float
--     deriving (Generic, Elt)
--
-- -- 
--   data Option a = None | Just a
--     deriving (Generic, Elt)
--
-- -- See the function match for details on how to use sum types in -- embedded code. class Elt a -- | Rank-0 index data Z Z :: Z -- | Increase an index rank by one dimension. The :. operator is -- used to construct both values and types. data tail :. head (:.) :: !tail -> !head -> (:.) tail head infixl 3 :. infixl 3 :. type DIM0 = Z type DIM1 = DIM0 :. Int type DIM2 = DIM1 :. Int type DIM3 = DIM2 :. Int type DIM4 = DIM3 :. Int type DIM5 = DIM4 :. Int type DIM6 = DIM5 :. Int type DIM7 = DIM6 :. Int type DIM8 = DIM7 :. Int type DIM9 = DIM8 :. Int -- | Shapes and indices of multi-dimensional arrays class (Elt sh, Elt (Any sh), FullShape sh ~ sh, CoSliceShape sh ~ sh, SliceShape sh ~ Z) => Shape sh -- | Slices, aka generalised indices, as n-tuples and mappings of -- slice indices to slices, co-slices, and slice dimensions class (Elt sl, Shape (SliceShape sl), Shape (CoSliceShape sl), Shape (FullShape sl)) => Slice sl where { type family SliceShape sl :: Type; type family CoSliceShape sl :: Type; type family FullShape sl :: Type; } sliceIndex :: Slice sl => SliceIndex (EltR sl) (EltR (SliceShape sl)) (EltR (CoSliceShape sl)) (EltR (FullShape sl)) -- | Marker for entire dimensions in slice and replicate -- descriptors. -- -- Occurrences of All indicate the dimensions into which the -- array's existing extent will be placed unchanged. -- -- See slice and replicate for examples. data All All :: All -- | Marker for arbitrary dimensions in slice and replicate -- descriptors. -- -- Any can be used in the leftmost position of a slice instead of -- Z, indicating that any dimensionality is admissible in that -- position. -- -- See slice and replicate for examples. data Any sh Any :: Any sh -- | Multidimensional array indexing. Extract the value from an array at -- the specified zero-based index. -- -- 
--   >>> let mat = fromList (Z:.5:.10) [0..] :: Matrix Int
--   
--   >>> mat
--   Matrix (Z :. 5 :. 10)
--     [  0,  1,  2,  3,  4,  5,  6,  7,  8,  9,
--       10, 11, 12, 13, 14, 15, 16, 17, 18, 19,
--       20, 21, 22, 23, 24, 25, 26, 27, 28, 29,
--       30, 31, 32, 33, 34, 35, 36, 37, 38, 39,
--       40, 41, 42, 43, 44, 45, 46, 47, 48, 49]
--
-- -- 
--   >>> runExp $ use mat ! constant (Z:.1:.2)
--   12
--
(!) :: forall sh e. (Shape sh, Elt e) => Acc (Array sh e) -> Exp sh -> Exp e infixl 9 ! -- | Extract the value from an array at the specified linear index. -- Multidimensional arrays in Accelerate are stored in row-major order -- with zero-based indexing. -- -- 
--   >>> let mat = fromList (Z:.5:.10) [0..] :: Matrix Int
--   
--   >>> mat
--   Matrix (Z :. 5 :. 10)
--     [  0,  1,  2,  3,  4,  5,  6,  7,  8,  9,
--       10, 11, 12, 13, 14, 15, 16, 17, 18, 19,
--       20, 21, 22, 23, 24, 25, 26, 27, 28, 29,
--       30, 31, 32, 33, 34, 35, 36, 37, 38, 39,
--       40, 41, 42, 43, 44, 45, 46, 47, 48, 49]
--
-- -- 
--   >>> runExp $ use mat !! 12
--   12
--
(!!) :: forall sh e. (Shape sh, Elt e) => Acc (Array sh e) -> Exp Int -> Exp e infixl 9 !! -- | Extract the element of a singleton array. -- -- 
--   the xs  ==  xs ! Z
--
the :: Elt e => Acc (Scalar e) -> Exp e -- | Test whether an array is empty. null :: (Shape sh, Elt e) => Acc (Array sh e) -> Exp Bool -- | Get the length of a vector. length :: Elt e => Acc (Vector e) -> Exp Int -- | Extract the shape (extent) of an array. shape :: forall sh e. (Shape sh, Elt e) => Acc (Array sh e) -> Exp sh -- | The number of elements in the array size :: (Shape sh, Elt e) => Acc (Array sh e) -> Exp Int -- | The number of elements that would be held by an array of the given -- shape. shapeSize :: forall sh. Shape sh => Exp sh -> Exp Int -- | Make an array from vanilla Haskell available for processing within -- embedded Accelerate computations. -- -- Depending upon which backend is used to eventually execute array -- computations, use may entail data transfer (e.g. to a GPU). -- -- use is overloaded so that it can accept tuples of -- Arrays: -- -- 
--   >>> let vec = fromList (Z:.10) [0..] :: Vector Int
--   
--   >>> vec
--   Vector (Z :. 10) [0,1,2,3,4,5,6,7,8,9]
--
-- -- 
--   >>> let mat = fromList (Z:.5:.10) [0..] :: Matrix Int
--   
--   >>> mat
--   Matrix (Z :. 5 :. 10)
--     [  0,  1,  2,  3,  4,  5,  6,  7,  8,  9,
--       10, 11, 12, 13, 14, 15, 16, 17, 18, 19,
--       20, 21, 22, 23, 24, 25, 26, 27, 28, 29,
--       30, 31, 32, 33, 34, 35, 36, 37, 38, 39,
--       40, 41, 42, 43, 44, 45, 46, 47, 48, 49]
--
-- -- 
--   >>> let vec' = use vec         :: Acc (Vector Int)
--   
--   >>> let mat' = use mat         :: Acc (Matrix Int)
--   
--   >>> let tup  = use (vec, mat)  :: Acc (Vector Int, Matrix Int)
--
use :: forall arrays. Arrays arrays => arrays -> Acc arrays -- | Construct a singleton (one element) array from a scalar value (or -- tuple of scalar values). unit :: forall e. Elt e => Exp e -> Acc (Scalar e) -- | Construct a new array by applying a function to each index. -- -- For example, the following will generate a one-dimensional array -- (Vector) of three floating point numbers: -- -- 
--   >>> run $ generate (I1 3) (\_ -> 1.2) :: Vector Float
--   Vector (Z :. 3) [1.2,1.2,1.2]
--
-- -- Or equivalently: -- -- 
--   >>> run $ fill (constant (Z :. 3)) 1.2 :: Vector Float
--   Vector (Z :. 3) [1.2,1.2,1.2]
--
-- -- The following will create a vector with the elements [1..10]: -- -- 
--   >>> run $ generate (I1 10) (\(I1 i) -> i + 1) :: Vector Int
--   Vector (Z :. 10) [1,2,3,4,5,6,7,8,9,10]
--
-- -- -- -- Using generate, it is possible to introduce nested data -- parallelism, which will cause the program to fail. -- -- If the index given by the scalar function is then used to dispatch -- further parallel work, whose result is returned into Exp terms -- by array indexing operations such as (!) or the, the -- program will fail with the error: -- ./Data/Array/Accelerate/Trafo/Sharing.hs:447 (convertSharingExp): -- inconsistent valuation @ shared 'Exp' tree .... generate :: forall sh a. (Shape sh, Elt a) => Exp sh -> (Exp sh -> Exp a) -> Acc (Array sh a) -- | Create an array where all elements are the same value. -- -- 
--   >>> run $ fill (constant (Z:.10)) 0 :: Vector Float
--   Vector (Z :. 10) [0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0]
--
fill :: (Shape sh, Elt e) => Exp sh -> Exp e -> Acc (Array sh e) -- | Create an array of the given shape containing the values x, -- x+1, etc. (in row-major order). -- -- 
--   >>> run $ enumFromN (constant (Z:.5:.10)) 0 :: Matrix Int
--   Matrix (Z :. 5 :. 10)
--     [  0,  1,  2,  3,  4,  5,  6,  7,  8,  9,
--       10, 11, 12, 13, 14, 15, 16, 17, 18, 19,
--       20, 21, 22, 23, 24, 25, 26, 27, 28, 29,
--       30, 31, 32, 33, 34, 35, 36, 37, 38, 39,
--       40, 41, 42, 43, 44, 45, 46, 47, 48, 49]
--
enumFromN :: (Shape sh, Num e, FromIntegral Int e) => Exp sh -> Exp e -> Acc (Array sh e) -- | Create an array of the given shape containing the values x, -- x+y, x+y+y etc. (in row-major order). -- -- 
--   >>> run $ enumFromStepN (constant (Z:.5:.10)) 0 0.5 :: Matrix Float
--   Matrix (Z :. 5 :. 10)
--     [  0.0,  0.5,  1.0,  1.5,  2.0,  2.5,  3.0,  3.5,  4.0,  4.5,
--        5.0,  5.5,  6.0,  6.5,  7.0,  7.5,  8.0,  8.5,  9.0,  9.5,
--       10.0, 10.5, 11.0, 11.5, 12.0, 12.5, 13.0, 13.5, 14.0, 14.5,
--       15.0, 15.5, 16.0, 16.5, 17.0, 17.5, 18.0, 18.5, 19.0, 19.5,
--       20.0, 20.5, 21.0, 21.5, 22.0, 22.5, 23.0, 23.5, 24.0, 24.5]
--
enumFromStepN :: (Shape sh, Num e, FromIntegral Int e) => Exp sh -> Exp e -> Exp e -> Acc (Array sh e) -- | Concatenate innermost component of two arrays. The extent of the lower -- dimensional component is the intersection of the two arrays. -- -- 
--   >>> let m1 = fromList (Z:.5:.10) [0..] :: Matrix Int
--   
--   >>> m1
--   Matrix (Z :. 5 :. 10)
--     [  0,  1,  2,  3,  4,  5,  6,  7,  8,  9,
--       10, 11, 12, 13, 14, 15, 16, 17, 18, 19,
--       20, 21, 22, 23, 24, 25, 26, 27, 28, 29,
--       30, 31, 32, 33, 34, 35, 36, 37, 38, 39,
--       40, 41, 42, 43, 44, 45, 46, 47, 48, 49]
--
-- -- 
--   >>> let m2 = fromList (Z:.10:.3) [0..] :: Matrix Int
--   
--   >>> m2
--   Matrix (Z :. 10 :. 3)
--     [  0,  1,  2,
--        3,  4,  5,
--        6,  7,  8,
--        9, 10, 11,
--       12, 13, 14,
--       15, 16, 17,
--       18, 19, 20,
--       21, 22, 23,
--       24, 25, 26,
--       27, 28, 29]
--
-- -- 
--   >>> run $ use m1 ++ use m2
--   Matrix (Z :. 5 :. 13)
--     [  0,  1,  2,  3,  4,  5,  6,  7,  8,  9,  0,  1,  2,
--       10, 11, 12, 13, 14, 15, 16, 17, 18, 19,  3,  4,  5,
--       20, 21, 22, 23, 24, 25, 26, 27, 28, 29,  6,  7,  8,
--       30, 31, 32, 33, 34, 35, 36, 37, 38, 39,  9, 10, 11,
--       40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 12, 13, 14]
--
(++) :: (Shape sh, Elt e) => Acc (Array (sh :. Int) e) -> Acc (Array (sh :. Int) e) -> Acc (Array (sh :. Int) e) infixr 5 ++ -- | Generalised version of (++) where the argument Lens' -- specifies which dimension to concatenate along. -- -- Appropriate lenses are available from lens-accelerate. -- -- 
--   >>> let m1 = fromList (Z:.5:.10) [0..] :: Matrix Int
--   
--   >>> m1
--   Matrix (Z :. 5 :. 10)
--     [  0,  1,  2,  3,  4,  5,  6,  7,  8,  9,
--       10, 11, 12, 13, 14, 15, 16, 17, 18, 19,
--       20, 21, 22, 23, 24, 25, 26, 27, 28, 29,
--       30, 31, 32, 33, 34, 35, 36, 37, 38, 39,
--       40, 41, 42, 43, 44, 45, 46, 47, 48, 49]
--
-- -- 
--   >>> let m2 = fromList (Z:.10:.5) [0..] :: Matrix Int
--   
--   >>> m2
--   Matrix (Z :. 10 :. 5)
--     [  0,  1,  2,  3,  4,
--        5,  6,  7,  8,  9,
--       10, 11, 12, 13, 14,
--       15, 16, 17, 18, 19,
--       20, 21, 22, 23, 24,
--       25, 26, 27, 28, 29,
--       30, 31, 32, 33, 34,
--       35, 36, 37, 38, 39,
--       40, 41, 42, 43, 44,
--       45, 46, 47, 48, 49]
--
-- -- 
--   >>> run $ concatOn _1 (use m1) (use m2)
--   Matrix (Z :. 5 :. 15)
--     [  0,  1,  2,  3,  4,  5,  6,  7,  8,  9,  0,  1,  2,  3,  4,
--       10, 11, 12, 13, 14, 15, 16, 17, 18, 19,  5,  6,  7,  8,  9,
--       20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 10, 11, 12, 13, 14,
--       30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 15, 16, 17, 18, 19,
--       40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 20, 21, 22, 23, 24]
--
-- -- 
--   >>> run $ concatOn _2 (use m1) (use m2)
--   Matrix (Z :. 15 :. 5)
--     [  0,  1,  2,  3,  4,
--       10, 11, 12, 13, 14,
--       20, 21, 22, 23, 24,
--       30, 31, 32, 33, 34,
--       40, 41, 42, 43, 44,
--        0,  1,  2,  3,  4,
--        5,  6,  7,  8,  9,
--       10, 11, 12, 13, 14,
--       15, 16, 17, 18, 19,
--       20, 21, 22, 23, 24,
--       25, 26, 27, 28, 29,
--       30, 31, 32, 33, 34,
--       35, 36, 37, 38, 39,
--       40, 41, 42, 43, 44,
--       45, 46, 47, 48, 49]
--
concatOn :: (Shape sh, Elt e) => Lens' (Exp sh) (Exp Int) -> Acc (Array sh e) -> Acc (Array sh e) -> Acc (Array sh e) -- | A recipe for generating flattened implementations of some kinds of -- irregular nested parallelism. Given two functions that: -- --
    --
  1. for each source element, determine how many target elements it -- expands into; and
    2. --
  2. computes a particular target element based on a source element and -- the target element index associated with the source
    3. --
-- -- The following example implements the Sieve of Eratosthenes, a -- contraction style algorithm which first computes all primes less than -- sqrt n, then uses this intermediate result to sieve away all -- numbers in the range [sqrt n .. n]. The expand function -- is used to calculate and flatten the sieves. For each prime p -- and upper limit c2, function sz computes the number of -- contributions in the sieve. Then, for each prime p and sieve -- index i, the function get computes the sieve -- contribution. The final step produces all the new primes in the -- interval [c1 .. c2]. -- -- 
--   >>> :{
--     primes :: Exp Int -> Acc (Vector Int)
--     primes n = afst loop
--       where
--         c0    = unit 2
--         a0    = use $ fromList (Z:.0) []
--         limit = truncate (sqrt (fromIntegral (n+1) :: Exp Float))
--         loop  = awhile
--                   (\(T2 _   c) -> map (< n+1) c)
--                   (\(T2 old c) ->
--                     let c1 = the c
--                         c2 = c1 < limit ? ( c1*c1, n+1 )
--                         --
--                         sieves =
--                           let sz p    = (c2 - p) `quot` p
--                               get p i = (2+i)*p
--                           in
--                           map (subtract c1) (expand sz get old)
--                         --
--                         new =
--                           let m     = c2-c1
--                               put i = let s = sieves ! i
--                                        in s >= 0 && s < m ? (Just_ (I1 s), Nothing_)
--                           in
--                           afst
--                             $ filter (> 0)
--                             $ permute const (enumFromN (I1 m) c1) put
--                             $ fill (shape sieves) 0
--                      in
--                      T2 (old ++ new) (unit c2))
--                   (T2 a0 c0)
--   :}
--
-- -- 
--   >>> run $ primes 100
--   Vector (Z :. 25) [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]
--
-- -- Inspired by the paper Data-Parallel Flattening by Expansion by -- Martin Elsman, Troels Henriksen, and Niels Gustav Westphal Serup, -- ARRAY'19. expand :: (Elt a, Elt b) => (Exp a -> Exp Int) -> (Exp a -> Exp Int -> Exp b) -> Acc (Vector a) -> Acc (Vector b) -- | Infix version of acond. If the predicate evaluates to -- True, the first component of the tuple is returned, else the -- second. -- -- Enabling the RebindableSyntax extension will allow you to use -- the standard if-then-else syntax instead. (?|) :: Arrays a => Exp Bool -> (Acc a, Acc a) -> Acc a infix 0 ?| -- | An array-level if-then-else construct. -- -- Enabling the RebindableSyntax extension will allow you to use -- the standard if-then-else syntax instead. acond :: Arrays a => Exp Bool -> Acc a -> Acc a -> Acc a -- | An array-level while construct. Continue to apply the given -- function, starting with the initial value, until the test function -- evaluates to False. awhile :: forall a. Arrays a => (Acc a -> Acc (Scalar Bool)) -> (Acc a -> Acc a) -> Acc a -> Acc a -- | For use with -XRebindableSyntax, this class provides -- ifThenElse lifted to both scalar and array types. class IfThenElse t where { type family EltT t a :: Constraint; } ifThenElse :: (IfThenElse t, EltT t a) => Exp Bool -> t a -> t a -> t a -- | Pipelining of two array computations. The first argument will be fully -- evaluated before being passed to the second computation. This can be -- used to prevent the argument being fused into the function, for -- example. -- -- Denotationally, we have -- -- 
--   (acc1 >-> acc2) arrs = let tmp = acc1 arrs
--                          in  tmp `seq` acc2 tmp
--
-- -- For an example use of this operation see the compute function. (>->) :: forall a b c. (Arrays a, Arrays b, Arrays c) => (Acc a -> Acc b) -> (Acc b -> Acc c) -> Acc a -> Acc c infixl 1 >-> -- | Force an array expression to be evaluated, preventing it from fusing -- with other operations. Forcing operations to be computed to memory, -- rather than being fused into their consuming function, can sometimes -- improve performance. For example, computing a matrix transpose -- could provide better memory locality for the subsequent operation. -- Preventing fusion to split large operations into several simpler steps -- could also help by reducing register pressure. -- -- Preventing fusion also means that the individual operations are -- available to be executed concurrently with other kernels. In -- particular, consider using this if you have a series of operations -- that are compute bound rather than memory bound. -- -- Here is the synthetic example: -- -- 
--   loop :: Exp Int -> Exp Int
--   loop ticks =
--     let clockRate = 900000   -- kHz
--     in  while (\i -> i < clockRate * ticks) (+1) 0
--   
--   test :: Acc (Vector Int)
--   test =
--     zip3
--       (compute $ map loop (use $ fromList (Z:.1) [10]))
--       (compute $ map loop (use $ fromList (Z:.1) [10]))
--       (compute $ map loop (use $ fromList (Z:.1) [10]))
--
-- -- Without the use of compute, the operations are fused together -- and the three long-running loops are executed sequentially in a single -- kernel. Instead, the individual operations can now be executed -- concurrently, potentially reducing overall runtime. compute :: Arrays a => Acc a -> Acc a -- | Pair each element with its index -- -- 
--   >>> let xs = fromList (Z:.5) [0..] :: Vector Float
--   
--   >>> run $ indexed (use xs)
--   Vector (Z :. 5) [(Z :. 0,0.0),(Z :. 1,1.0),(Z :. 2,2.0),(Z :. 3,3.0),(Z :. 4,4.0)]
--
-- -- 
--   >>> let mat = fromList (Z:.3:.4) [0..] :: Matrix Float
--   
--   >>> run $ indexed (use mat)
--   Matrix (Z :. 3 :. 4)
--     [ (Z :. 0 :. 0,0.0), (Z :. 0 :. 1,1.0),  (Z :. 0 :. 2,2.0),  (Z :. 0 :. 3,3.0),
--       (Z :. 1 :. 0,4.0), (Z :. 1 :. 1,5.0),  (Z :. 1 :. 2,6.0),  (Z :. 1 :. 3,7.0),
--       (Z :. 2 :. 0,8.0), (Z :. 2 :. 1,9.0), (Z :. 2 :. 2,10.0), (Z :. 2 :. 3,11.0)]
--
indexed :: (Shape sh, Elt a) => Acc (Array sh a) -> Acc (Array sh (sh, a)) -- | Apply the given function element-wise to an array. Denotationally we -- have: -- -- 
--   map f [x1, x2, ... xn] = [f x1, f x2, ... f xn]
--
-- -- 
--   >>> let xs = fromList (Z:.10) [0..] :: Vector Int
--   
--   >>> xs
--   Vector (Z :. 10) [0,1,2,3,4,5,6,7,8,9]
--
-- -- 
--   >>> run $ map (+1) (use xs)
--   Vector (Z :. 10) [1,2,3,4,5,6,7,8,9,10]
--
map :: forall sh a b. (Shape sh, Elt a, Elt b) => (Exp a -> Exp b) -> Acc (Array sh a) -> Acc (Array sh b) -- | Apply a function to every element of an array and its index imap :: (Shape sh, Elt a, Elt b) => (Exp sh -> Exp a -> Exp b) -> Acc (Array sh a) -> Acc (Array sh b) -- | Apply the given binary function element-wise to the two arrays. The -- extent of the resulting array is the intersection of the extents of -- the two source arrays. -- -- 
--   >>> let xs = fromList (Z:.3:.5) [0..] :: Matrix Int
--   
--   >>> xs
--   Matrix (Z :. 3 :. 5)
--     [  0,  1,  2,  3,  4,
--        5,  6,  7,  8,  9,
--       10, 11, 12, 13, 14]
--
-- -- 
--   >>> let ys = fromList (Z:.5:.10) [1..] :: Matrix Int
--   
--   >>> ys
--   Matrix (Z :. 5 :. 10)
--     [  1,  2,  3,  4,  5,  6,  7,  8,  9, 10,
--       11, 12, 13, 14, 15, 16, 17, 18, 19, 20,
--       21, 22, 23, 24, 25, 26, 27, 28, 29, 30,
--       31, 32, 33, 34, 35, 36, 37, 38, 39, 40,
--       41, 42, 43, 44, 45, 46, 47, 48, 49, 50]
--
-- -- 
--   >>> run $ zipWith (+) (use xs) (use ys)
--   Matrix (Z :. 3 :. 5)
--     [  1,  3,  5,  7,  9,
--       16, 18, 20, 22, 24,
--       31, 33, 35, 37, 39]
--
zipWith :: forall sh a b c. (Shape sh, Elt a, Elt b, Elt c) => (Exp a -> Exp b -> Exp c) -> Acc (Array sh a) -> Acc (Array sh b) -> Acc (Array sh c) -- | Zip three arrays with the given function, analogous to zipWith. zipWith3 :: (Shape sh, Elt a, Elt b, Elt c, Elt d) => (Exp a -> Exp b -> Exp c -> Exp d) -> Acc (Array sh a) -> Acc (Array sh b) -> Acc (Array sh c) -> Acc (Array sh d) -- | Zip four arrays with the given function, analogous to zipWith. zipWith4 :: (Shape sh, Elt a, Elt b, Elt c, Elt d, Elt e) => (Exp a -> Exp b -> Exp c -> Exp d -> Exp e) -> Acc (Array sh a) -> Acc (Array sh b) -> Acc (Array sh c) -> Acc (Array sh d) -> Acc (Array sh e) -- | Zip five arrays with the given function, analogous to zipWith. zipWith5 :: (Shape sh, Elt a, Elt b, Elt c, Elt d, Elt e, Elt f) => (Exp a -> Exp b -> Exp c -> Exp d -> Exp e -> Exp f) -> Acc (Array sh a) -> Acc (Array sh b) -> Acc (Array sh c) -> Acc (Array sh d) -> Acc (Array sh e) -> Acc (Array sh f) -- | Zip six arrays with the given function, analogous to zipWith. zipWith6 :: (Shape sh, Elt a, Elt b, Elt c, Elt d, Elt e, Elt f, Elt g) => (Exp a -> Exp b -> Exp c -> Exp d -> Exp e -> Exp f -> Exp g) -> Acc (Array sh a) -> Acc (Array sh b) -> Acc (Array sh c) -> Acc (Array sh d) -> Acc (Array sh e) -> Acc (Array sh f) -> Acc (Array sh g) -- | Zip seven arrays with the given function, analogous to zipWith. zipWith7 :: (Shape sh, Elt a, Elt b, Elt c, Elt d, Elt e, Elt f, Elt g, Elt h) => (Exp a -> Exp b -> Exp c -> Exp d -> Exp e -> Exp f -> Exp g -> Exp h) -> Acc (Array sh a) -> Acc (Array sh b) -> Acc (Array sh c) -> Acc (Array sh d) -> Acc (Array sh e) -> Acc (Array sh f) -> Acc (Array sh g) -> Acc (Array sh h) -- | Zip eight arrays with the given function, analogous to zipWith. zipWith8 :: (Shape sh, Elt a, Elt b, Elt c, Elt d, Elt e, Elt f, Elt g, Elt h, Elt i) => (Exp a -> Exp b -> Exp c -> Exp d -> Exp e -> Exp f -> Exp g -> Exp h -> Exp i) -> Acc (Array sh a) -> Acc (Array sh b) -> Acc (Array sh c) -> Acc (Array sh d) -> Acc (Array sh e) -> Acc (Array sh f) -> Acc (Array sh g) -> Acc (Array sh h) -> Acc (Array sh i) -- | Zip nine arrays with the given function, analogous to zipWith. zipWith9 :: (Shape sh, Elt a, Elt b, Elt c, Elt d, Elt e, Elt f, Elt g, Elt h, Elt i, Elt j) => (Exp a -> Exp b -> Exp c -> Exp d -> Exp e -> Exp f -> Exp g -> Exp h -> Exp i -> Exp j) -> Acc (Array sh a) -> Acc (Array sh b) -> Acc (Array sh c) -> Acc (Array sh d) -> Acc (Array sh e) -> Acc (Array sh f) -> Acc (Array sh g) -> Acc (Array sh h) -> Acc (Array sh i) -> Acc (Array sh j) -- | Zip two arrays with a function that also takes the element index izipWith :: (Shape sh, Elt a, Elt b, Elt c) => (Exp sh -> Exp a -> Exp b -> Exp c) -> Acc (Array sh a) -> Acc (Array sh b) -> Acc (Array sh c) -- | Zip three arrays with a function that also takes the element index, -- analogous to izipWith. izipWith3 :: (Shape sh, Elt a, Elt b, Elt c, Elt d) => (Exp sh -> Exp a -> Exp b -> Exp c -> Exp d) -> Acc (Array sh a) -> Acc (Array sh b) -> Acc (Array sh c) -> Acc (Array sh d) -- | Zip four arrays with the given function that also takes the element -- index, analogous to zipWith. izipWith4 :: (Shape sh, Elt a, Elt b, Elt c, Elt d, Elt e) => (Exp sh -> Exp a -> Exp b -> Exp c -> Exp d -> Exp e) -> Acc (Array sh a) -> Acc (Array sh b) -> Acc (Array sh c) -> Acc (Array sh d) -> Acc (Array sh e) -- | Zip five arrays with the given function that also takes the element -- index, analogous to zipWith. izipWith5 :: (Shape sh, Elt a, Elt b, Elt c, Elt d, Elt e, Elt f) => (Exp sh -> Exp a -> Exp b -> Exp c -> Exp d -> Exp e -> Exp f) -> Acc (Array sh a) -> Acc (Array sh b) -> Acc (Array sh c) -> Acc (Array sh d) -> Acc (Array sh e) -> Acc (Array sh f) -- | Zip six arrays with the given function that also takes the element -- index, analogous to zipWith. izipWith6 :: (Shape sh, Elt a, Elt b, Elt c, Elt d, Elt e, Elt f, Elt g) => (Exp sh -> Exp a -> Exp b -> Exp c -> Exp d -> Exp e -> Exp f -> Exp g) -> Acc (Array sh a) -> Acc (Array sh b) -> Acc (Array sh c) -> Acc (Array sh d) -> Acc (Array sh e) -> Acc (Array sh f) -> Acc (Array sh g) -- | Zip seven arrays with the given function that also takes the element -- index, analogous to zipWith. izipWith7 :: (Shape sh, Elt a, Elt b, Elt c, Elt d, Elt e, Elt f, Elt g, Elt h) => (Exp sh -> Exp a -> Exp b -> Exp c -> Exp d -> Exp e -> Exp f -> Exp g -> Exp h) -> Acc (Array sh a) -> Acc (Array sh b) -> Acc (Array sh c) -> Acc (Array sh d) -> Acc (Array sh e) -> Acc (Array sh f) -> Acc (Array sh g) -> Acc (Array sh h) -- | Zip eight arrays with the given function that also takes the element -- index, analogous to zipWith. izipWith8 :: (Shape sh, Elt a, Elt b, Elt c, Elt d, Elt e, Elt f, Elt g, Elt h, Elt i) => (Exp sh -> Exp a -> Exp b -> Exp c -> Exp d -> Exp e -> Exp f -> Exp g -> Exp h -> Exp i) -> Acc (Array sh a) -> Acc (Array sh b) -> Acc (Array sh c) -> Acc (Array sh d) -> Acc (Array sh e) -> Acc (Array sh f) -> Acc (Array sh g) -> Acc (Array sh h) -> Acc (Array sh i) -- | Zip nine arrays with the given function that also takes the element -- index, analogous to zipWith. izipWith9 :: (Shape sh, Elt a, Elt b, Elt c, Elt d, Elt e, Elt f, Elt g, Elt h, Elt i, Elt j) => (Exp sh -> Exp a -> Exp b -> Exp c -> Exp d -> Exp e -> Exp f -> Exp g -> Exp h -> Exp i -> Exp j) -> Acc (Array sh a) -> Acc (Array sh b) -> Acc (Array sh c) -> Acc (Array sh d) -> Acc (Array sh e) -> Acc (Array sh f) -> Acc (Array sh g) -> Acc (Array sh h) -> Acc (Array sh i) -> Acc (Array sh j) -- | Combine the elements of two arrays pairwise. The shape of the result -- is the intersection of the two argument shapes. -- -- 
--   >>> let m1 = fromList (Z:.5:.10) [0..] :: Matrix Int
--   
--   >>> let m2 = fromList (Z:.10:.5) [0..] :: Matrix Float
--   
--   >>> run $ zip (use m1) (use m2)
--   Matrix (Z :. 5 :. 5)
--     [   (0,0.0),   (1,1.0),   (2,2.0),   (3,3.0),   (4,4.0),
--        (10,5.0),  (11,6.0),  (12,7.0),  (13,8.0),  (14,9.0),
--       (20,10.0), (21,11.0), (22,12.0), (23,13.0), (24,14.0),
--       (30,15.0), (31,16.0), (32,17.0), (33,18.0), (34,19.0),
--       (40,20.0), (41,21.0), (42,22.0), (43,23.0), (44,24.0)]
--
zip :: (Shape sh, Elt a, Elt b) => Acc (Array sh a) -> Acc (Array sh b) -> Acc (Array sh (a, b)) -- | Take three arrays and return an array of triples, analogous to zip. zip3 :: (Shape sh, Elt a, Elt b, Elt c) => Acc (Array sh a) -> Acc (Array sh b) -> Acc (Array sh c) -> Acc (Array sh (a, b, c)) -- | Take four arrays and return an array of quadruples, analogous to zip. zip4 :: (Shape sh, Elt a, Elt b, Elt c, Elt d) => Acc (Array sh a) -> Acc (Array sh b) -> Acc (Array sh c) -> Acc (Array sh d) -> Acc (Array sh (a, b, c, d)) -- | Take five arrays and return an array of five-tuples, analogous to zip. zip5 :: (Shape sh, Elt a, Elt b, Elt c, Elt d, Elt e) => Acc (Array sh a) -> Acc (Array sh b) -> Acc (Array sh c) -> Acc (Array sh d) -> Acc (Array sh e) -> Acc (Array sh (a, b, c, d, e)) -- | Take six arrays and return an array of six-tuples, analogous to zip. zip6 :: (Shape sh, Elt a, Elt b, Elt c, Elt d, Elt e, Elt f) => Acc (Array sh a) -> Acc (Array sh b) -> Acc (Array sh c) -> Acc (Array sh d) -> Acc (Array sh e) -> Acc (Array sh f) -> Acc (Array sh (a, b, c, d, e, f)) -- | Take seven arrays and return an array of seven-tuples, analogous to -- zip. zip7 :: (Shape sh, Elt a, Elt b, Elt c, Elt d, Elt e, Elt f, Elt g) => Acc (Array sh a) -> Acc (Array sh b) -> Acc (Array sh c) -> Acc (Array sh d) -> Acc (Array sh e) -> Acc (Array sh f) -> Acc (Array sh g) -> Acc (Array sh (a, b, c, d, e, f, g)) -- | Take seven arrays and return an array of seven-tuples, analogous to -- zip. zip8 :: (Shape sh, Elt a, Elt b, Elt c, Elt d, Elt e, Elt f, Elt g, Elt h) => Acc (Array sh a) -> Acc (Array sh b) -> Acc (Array sh c) -> Acc (Array sh d) -> Acc (Array sh e) -> Acc (Array sh f) -> Acc (Array sh g) -> Acc (Array sh h) -> Acc (Array sh (a, b, c, d, e, f, g, h)) -- | Take seven arrays and return an array of seven-tuples, analogous to -- zip. zip9 :: (Shape sh, Elt a, Elt b, Elt c, Elt d, Elt e, Elt f, Elt g, Elt h, Elt i) => Acc (Array sh a) -> Acc (Array sh b) -> Acc (Array sh c) -> Acc (Array sh d) -> Acc (Array sh e) -> Acc (Array sh f) -> Acc (Array sh g) -> Acc (Array sh h) -> Acc (Array sh i) -> Acc (Array sh (a, b, c, d, e, f, g, h, i)) -- | The converse of zip, but the shape of the two results is -- identical to the shape of the argument. -- -- If the argument array is manifest in memory, unzip is a no-op. unzip :: (Shape sh, Elt a, Elt b) => Acc (Array sh (a, b)) -> (Acc (Array sh a), Acc (Array sh b)) -- | Take an array of triples and return three arrays, analogous to -- unzip. unzip3 :: (Shape sh, Elt a, Elt b, Elt c) => Acc (Array sh (a, b, c)) -> (Acc (Array sh a), Acc (Array sh b), Acc (Array sh c)) -- | Take an array of quadruples and return four arrays, analogous to -- unzip. unzip4 :: (Shape sh, Elt a, Elt b, Elt c, Elt d) => Acc (Array sh (a, b, c, d)) -> (Acc (Array sh a), Acc (Array sh b), Acc (Array sh c), Acc (Array sh d)) -- | Take an array of 5-tuples and return five arrays, analogous to -- unzip. unzip5 :: (Shape sh, Elt a, Elt b, Elt c, Elt d, Elt e) => Acc (Array sh (a, b, c, d, e)) -> (Acc (Array sh a), Acc (Array sh b), Acc (Array sh c), Acc (Array sh d), Acc (Array sh e)) -- | Take an array of 6-tuples and return six arrays, analogous to -- unzip. unzip6 :: (Shape sh, Elt a, Elt b, Elt c, Elt d, Elt e, Elt f) => Acc (Array sh (a, b, c, d, e, f)) -> (Acc (Array sh a), Acc (Array sh b), Acc (Array sh c), Acc (Array sh d), Acc (Array sh e), Acc (Array sh f)) -- | Take an array of 7-tuples and return seven arrays, analogous to -- unzip. unzip7 :: (Shape sh, Elt a, Elt b, Elt c, Elt d, Elt e, Elt f, Elt g) => Acc (Array sh (a, b, c, d, e, f, g)) -> (Acc (Array sh a), Acc (Array sh b), Acc (Array sh c), Acc (Array sh d), Acc (Array sh e), Acc (Array sh f), Acc (Array sh g)) -- | Take an array of 8-tuples and return eight arrays, analogous to -- unzip. unzip8 :: (Shape sh, Elt a, Elt b, Elt c, Elt d, Elt e, Elt f, Elt g, Elt h) => Acc (Array sh (a, b, c, d, e, f, g, h)) -> (Acc (Array sh a), Acc (Array sh b), Acc (Array sh c), Acc (Array sh d), Acc (Array sh e), Acc (Array sh f), Acc (Array sh g), Acc (Array sh h)) -- | Take an array of 9-tuples and return nine arrays, analogous to -- unzip. unzip9 :: (Shape sh, Elt a, Elt b, Elt c, Elt d, Elt e, Elt f, Elt g, Elt h, Elt i) => Acc (Array sh (a, b, c, d, e, f, g, h, i)) -> (Acc (Array sh a), Acc (Array sh b), Acc (Array sh c), Acc (Array sh d), Acc (Array sh e), Acc (Array sh f), Acc (Array sh g), Acc (Array sh h), Acc (Array sh i)) -- | Change the shape of an array without altering its contents. The -- size of the source and result arrays must be identical. -- -- 
--   precondition: shapeSize sh == shapeSize sh'
--
-- -- If the argument array is manifest in memory, reshape is a -- no-op. If the argument is to be fused into a subsequent operation, -- reshape corresponds to an index transformation in the fused -- code. reshape :: forall sh sh' e. (Shape sh, Shape sh', Elt e) => Exp sh -> Acc (Array sh' e) -> Acc (Array sh e) -- | Flatten the given array of arbitrary dimension into a one-dimensional -- vector. As with reshape, this operation performs no work. flatten :: forall sh e. (Shape sh, Elt e) => Acc (Array sh e) -> Acc (Vector e) -- | Replicate an array across one or more dimensions as specified by the -- generalised array index provided as the first argument. -- -- For example, given the following vector: -- -- 
--   >>> let vec = fromList (Z:.10) [0..] :: Vector Int
--   
--   >>> vec
--   Vector (Z :. 10) [0,1,2,3,4,5,6,7,8,9]
--
-- -- ...we can replicate these elements to form a two-dimensional array -- either by replicating those elements as new rows: -- -- 
--   >>> run $ replicate (constant (Z :. (4::Int) :. All)) (use vec)
--   Matrix (Z :. 4 :. 10)
--     [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
--       0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
--       0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
--       0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
--
-- -- ...or as columns: -- -- 
--   >>> run $ replicate (lift (Z :. All :. (4::Int))) (use vec)
--   Matrix (Z :. 10 :. 4)
--     [ 0, 0, 0, 0,
--       1, 1, 1, 1,
--       2, 2, 2, 2,
--       3, 3, 3, 3,
--       4, 4, 4, 4,
--       5, 5, 5, 5,
--       6, 6, 6, 6,
--       7, 7, 7, 7,
--       8, 8, 8, 8,
--       9, 9, 9, 9]
--
-- -- Replication along more than one dimension is also possible. Here we -- replicate twice across the first dimension and three times across the -- third dimension: -- -- 
--   >>> run $ replicate (constant (Z :. (2::Int) :. All :. (3::Int))) (use vec)
--   Array (Z :. 2 :. 10 :. 3) [0,0,0,1,1,1,2,2,2,3,3,3,4,4,4,5,5,5,6,6,6,7,7,7,8,8,8,9,9,9,0,0,0,1,1,1,2,2,2,3,3,3,4,4,4,5,5,5,6,6,6,7,7,7,8,8,8,9,9,9]
--
-- -- The marker Any can be used in the slice specification to -- match against some arbitrary dimension. For example, here Any -- matches against whatever shape type variable sh takes. -- -- 
--   >>> :{
--     let rep0 :: (Shape sh, Elt e) => Exp Int -> Acc (Array sh e) -> Acc (Array (sh :. Int) e)
--         rep0 n a = replicate (lift (Any :. n)) a
--   :}
--
-- -- 
--   >>> let x = unit 42 :: Acc (Scalar Int)
--   
--   >>> run $ rep0 10 x
--   Vector (Z :. 10) [42,42,42,42,42,42,42,42,42,42]
--
-- -- 
--   >>> run $ rep0 5 (use vec)
--   Matrix (Z :. 10 :. 5)
--     [ 0, 0, 0, 0, 0,
--       1, 1, 1, 1, 1,
--       2, 2, 2, 2, 2,
--       3, 3, 3, 3, 3,
--       4, 4, 4, 4, 4,
--       5, 5, 5, 5, 5,
--       6, 6, 6, 6, 6,
--       7, 7, 7, 7, 7,
--       8, 8, 8, 8, 8,
--       9, 9, 9, 9, 9]
--
-- -- Of course, Any and All can be used together. -- -- 
--   >>> :{
--     let rep1 :: (Shape sh, Elt e) => Exp Int -> Acc (Array (sh :. Int) e) -> Acc (Array (sh :. Int :. Int) e)
--         rep1 n a = replicate (lift (Any :. n :. All)) a
--   :}
--
-- -- 
--   >>> run $ rep1 5 (use vec)
--   Matrix (Z :. 5 :. 10)
--     [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
--       0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
--       0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
--       0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
--       0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
--
replicate :: forall slix e. (Slice slix, Elt e) => Exp slix -> Acc (Array (SliceShape slix) e) -> Acc (Array (FullShape slix) e) -- | Index an array with a generalised array index, supplied as the -- second argument. The result is a new array (possibly a singleton) -- containing the selected dimensions (Alls) in their entirety. -- -- slice is the opposite of replicate, and can be used to -- cut out entire dimensions. For example, for the two dimensional -- array mat: -- -- 
--   >>> let mat = fromList (Z:.5:.10) [0..] :: Matrix Int
--   
--   >>> mat
--   Matrix (Z :. 5 :. 10)
--     [  0,  1,  2,  3,  4,  5,  6,  7,  8,  9,
--       10, 11, 12, 13, 14, 15, 16, 17, 18, 19,
--       20, 21, 22, 23, 24, 25, 26, 27, 28, 29,
--       30, 31, 32, 33, 34, 35, 36, 37, 38, 39,
--       40, 41, 42, 43, 44, 45, 46, 47, 48, 49]
--
-- -- ...will can select a specific row to yield a one dimensional result by -- fixing the row index (2) while allowing the column index to vary (via -- All): -- -- 
--   >>> run $ slice (use mat) (constant (Z :. (2::Int) :. All))
--   Vector (Z :. 10) [20,21,22,23,24,25,26,27,28,29]
--
-- -- A fully specified index (with no Alls) returns a single -- element (zero dimensional array). -- -- 
--   >>> run $ slice (use mat) (constant (Z :. 4 :. 2 :: DIM2))
--   Scalar Z [42]
--
-- -- The marker Any can be used in the slice specification to -- match against some arbitrary (lower) dimension. Here Any -- matches whatever shape type variable sh takes: -- -- 
--   >>> :{
--     let
--         sl0 :: (Shape sh, Elt e) => Acc (Array (sh:.Int) e) -> Exp Int -> Acc (Array sh e)
--         sl0 a n = slice a (lift (Any :. n))
--   :}
--
-- -- 
--   >>> let vec = fromList (Z:.10) [0..] :: Vector Int
--   
--   >>> run $ sl0 (use vec) 4
--   Scalar Z [4]
--
-- -- 
--   >>> run $ sl0 (use mat) 4
--   Vector (Z :. 5) [4,14,24,34,44]
--
-- -- Of course, Any and All can be used together. -- -- 
--   >>> :{
--     let sl1 :: (Shape sh, Elt e) => Acc (Array (sh:.Int:.Int) e) -> Exp Int -> Acc (Array (sh:.Int) e)
--         sl1 a n = slice a (lift (Any :. n :. All))
--   :}
--
-- -- 
--   >>> run $ sl1 (use mat) 4
--   Vector (Z :. 10) [40,41,42,43,44,45,46,47,48,49]
--
-- -- 
--   >>> let cube = fromList (Z:.3:.4:.5) [0..] :: Array DIM3 Int
--   
--   >>> cube
--   Array (Z :. 3 :. 4 :. 5) [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59]
--
-- -- 
--   >>> run $ sl1 (use cube) 2
--   Matrix (Z :. 3 :. 5)
--     [ 10, 11, 12, 13, 14,
--       30, 31, 32, 33, 34,
--       50, 51, 52, 53, 54]
--
slice :: forall slix e. (Slice slix, Elt e) => Acc (Array (FullShape slix) e) -> Exp slix -> Acc (Array (SliceShape slix) e) -- | Yield all but the elements in the last index of the innermost -- dimension. -- -- 
--   >>> let mat = fromList (Z:.5:.10) [0..] :: Matrix Int
--   
--   >>> mat
--   Matrix (Z :. 5 :. 10)
--     [  0,  1,  2,  3,  4,  5,  6,  7,  8,  9,
--       10, 11, 12, 13, 14, 15, 16, 17, 18, 19,
--       20, 21, 22, 23, 24, 25, 26, 27, 28, 29,
--       30, 31, 32, 33, 34, 35, 36, 37, 38, 39,
--       40, 41, 42, 43, 44, 45, 46, 47, 48, 49]
--
-- -- 
--   >>> run $ init (use mat)
--   Matrix (Z :. 5 :. 9)
--     [  0,  1,  2,  3,  4,  5,  6,  7,  8,
--       10, 11, 12, 13, 14, 15, 16, 17, 18,
--       20, 21, 22, 23, 24, 25, 26, 27, 28,
--       30, 31, 32, 33, 34, 35, 36, 37, 38,
--       40, 41, 42, 43, 44, 45, 46, 47, 48]
--
init :: (Shape sh, Elt e) => Acc (Array (sh :. Int) e) -> Acc (Array (sh :. Int) e) -- | Yield all but the first element along the innermost dimension of an -- array. The innermost dimension must not be empty. -- -- 
--   >>> let mat = fromList (Z:.5:.10) [0..] :: Matrix Int
--   
--   >>> mat
--   Matrix (Z :. 5 :. 10)
--     [  0,  1,  2,  3,  4,  5,  6,  7,  8,  9,
--       10, 11, 12, 13, 14, 15, 16, 17, 18, 19,
--       20, 21, 22, 23, 24, 25, 26, 27, 28, 29,
--       30, 31, 32, 33, 34, 35, 36, 37, 38, 39,
--       40, 41, 42, 43, 44, 45, 46, 47, 48, 49]
--
-- -- 
--   >>> run $ tail (use mat)
--   Matrix (Z :. 5 :. 9)
--     [  1,  2,  3,  4,  5,  6,  7,  8,  9,
--       11, 12, 13, 14, 15, 16, 17, 18, 19,
--       21, 22, 23, 24, 25, 26, 27, 28, 29,
--       31, 32, 33, 34, 35, 36, 37, 38, 39,
--       41, 42, 43, 44, 45, 46, 47, 48, 49]
--
tail :: (Shape sh, Elt e) => Acc (Array (sh :. Int) e) -> Acc (Array (sh :. Int) e) -- | Yield the first n elements in the innermost dimension of the -- array (plus all lower dimensional elements). -- -- 
--   >>> let mat = fromList (Z:.5:.10) [0..] :: Matrix Int
--   
--   >>> mat
--   Matrix (Z :. 5 :. 10)
--     [  0,  1,  2,  3,  4,  5,  6,  7,  8,  9,
--       10, 11, 12, 13, 14, 15, 16, 17, 18, 19,
--       20, 21, 22, 23, 24, 25, 26, 27, 28, 29,
--       30, 31, 32, 33, 34, 35, 36, 37, 38, 39,
--       40, 41, 42, 43, 44, 45, 46, 47, 48, 49]
--
-- -- 
--   >>> run $ take 5 (use mat)
--   Matrix (Z :. 5 :. 5)
--     [  0,  1,  2,  3,  4,
--       10, 11, 12, 13, 14,
--       20, 21, 22, 23, 24,
--       30, 31, 32, 33, 34,
--       40, 41, 42, 43, 44]
--
take :: (Shape sh, Elt e) => Exp Int -> Acc (Array (sh :. Int) e) -> Acc (Array (sh :. Int) e) -- | Yield all but the first n elements along the innermost -- dimension of the array (plus all lower dimensional elements). -- -- 
--   >>> let mat = fromList (Z:.5:.10) [0..] :: Matrix Int
--   
--   >>> mat
--   Matrix (Z :. 5 :. 10)
--     [  0,  1,  2,  3,  4,  5,  6,  7,  8,  9,
--       10, 11, 12, 13, 14, 15, 16, 17, 18, 19,
--       20, 21, 22, 23, 24, 25, 26, 27, 28, 29,
--       30, 31, 32, 33, 34, 35, 36, 37, 38, 39,
--       40, 41, 42, 43, 44, 45, 46, 47, 48, 49]
--
-- -- 
--   >>> run $ drop 7 (use mat)
--   Matrix (Z :. 5 :. 3)
--     [  7,  8,  9,
--       17, 18, 19,
--       27, 28, 29,
--       37, 38, 39,
--       47, 48, 49]
--
drop :: (Shape sh, Elt e) => Exp Int -> Acc (Array (sh :. Int) e) -> Acc (Array (sh :. Int) e) -- | Yield a slit (slice) of the innermost indices of an array. -- Denotationally, we have: -- -- 
--   slit i n = take n . drop i
--
slit :: (Shape sh, Elt e) => Exp Int -> Exp Int -> Acc (Array (sh :. Int) e) -> Acc (Array (sh :. Int) e) -- | Generalised version of init where the argument Lens' -- specifies which dimension to operate over. -- -- Appropriate lenses are available from lens-accelerate. initOn :: (Shape sh, Elt e) => Lens' (Exp sh) (Exp Int) -> Acc (Array sh e) -> Acc (Array sh e) -- | Generalised version of tail where the argument Lens' -- specifies which dimension to operate over. -- -- Appropriate lenses are available from lens-accelerate. tailOn :: (Shape sh, Elt e) => Lens' (Exp sh) (Exp Int) -> Acc (Array sh e) -> Acc (Array sh e) -- | Generalised version of take where the argument Lens' -- specifies which dimension to operate over. -- -- Appropriate lenses are available from lens-accelerate. takeOn :: (Shape sh, Elt e) => Lens' (Exp sh) (Exp Int) -> Exp Int -> Acc (Array sh e) -> Acc (Array sh e) -- | Generalised version of drop where the argument Lens' -- specifies which dimension to operate over. -- -- Appropriate lenses are available from lens-accelerate. dropOn :: (Shape sh, Elt e) => Lens' (Exp sh) (Exp Int) -> Exp Int -> Acc (Array sh e) -> Acc (Array sh e) -- | Generalised version of drop where the argument Lens' -- specifies which dimension to operate over. -- -- Appropriate lenses are available from lens-accelerate. slitOn :: (Shape sh, Elt e) => Lens' (Exp sh) (Exp Int) -> Exp Int -> Exp Int -> Acc (Array sh e) -> Acc (Array sh e) -- | Generalised forward permutation operation (array scatter). -- -- Forward permutation specified by a function mapping indices from the -- source array to indices in the result array. The result array is -- initialised with the given defaults and any further values that are -- permuted into the result array are added to the current value using -- the given combination function. -- -- The combination function must be associative and -- commutative. Elements for which the permutation function -- returns Nothing are dropped. -- -- The combination function is given the new value being permuted as its -- first argument, and the current value of the array as its second. -- -- For example, we can use permute to compute the occurrence count -- (histogram) for an array of values in the range [0,10): -- -- 
--   >>> :{
--     let histogram :: Acc (Vector Int) -> Acc (Vector Int)
--         histogram xs =
--           let zeros = fill (constant (Z:.10)) 0
--               ones  = fill (shape xs)         1
--           in
--           permute (+) zeros (\ix -> Just_ (I1 (xs!ix))) ones
--   :}
--
-- -- 
--   >>> let xs = fromList (Z :. 20) [0,0,1,2,1,1,2,4,8,3,4,9,8,3,2,5,5,3,1,2] :: Vector Int
--   
--   >>> run $ histogram (use xs)
--   Vector (Z :. 10) [2,4,4,3,2,2,0,0,2,1]
--
-- -- As a second example, note that the dimensionality of the source and -- destination arrays can differ. In this way, we can use permute -- to create an identity matrix by overwriting elements along the -- diagonal: -- -- 
--   >>> :{
--     let identity :: Num a => Exp Int -> Acc (Matrix a)
--         identity n =
--           let zeros = fill (I2 n n) 0
--               ones  = fill (I1 n)   1
--           in
--           permute const zeros (\(I1 i) -> Just_ (I2 i i)) ones
--   :}
--
-- -- 
--   >>> run $ identity 5 :: Matrix Int
--   Matrix (Z :. 5 :. 5)
--     [ 1, 0, 0, 0, 0,
--       0, 1, 0, 0, 0,
--       0, 0, 1, 0, 0,
--       0, 0, 0, 1, 0,
--       0, 0, 0, 0, 1]
--
-- -- -- -- Regarding array fusion: -- --
    --
  1. The permute operation will always be evaluated; it can not -- be fused into a later step.
    2. --
  2. Since the index permutation function might not cover all positions -- in the output array (the function is not surjective), the array of -- default values must be evaluated. However, other operations may fuse -- into this.
    3. --
  3. The array of source values can fuse into the permutation -- operation.
    4. --
  4. If the array of default values is only used once, it will be -- updated in-place. This behaviour can be disabled this with -- -fno-inplace.
    5. --
-- -- Regarding the defaults array: -- -- If you are sure that the default values are not necessary---they are -- not used by the combination function and every element will be -- overwritten---a default array created by filling with the value -- undef will give you a new uninitialised array. -- -- Regarding the combination function: -- -- The function const can be used to replace elements of the -- defaults array with the new values. If the permutation function maps -- multiple values to the same location in the results array (the -- function is not injective) then this operation is non-deterministic. -- -- Since Accelerate uses an unzipped struct-of-array representation, -- where the individual components of product types (for example, pairs) -- are stored in separate arrays, storing values of product type requires -- multiple store instructions. -- -- Accelerate prior to version 1.3.0.0 performs this operation -- atomically, to ensure that the stored values are always consistent -- (each component of the product type is written by the same thread). -- Later versions relax this restriction, but this behaviour can be -- disabled with -fno-fast-permute-const. permute :: forall sh sh' a. (Shape sh, Shape sh', Elt a) => (Exp a -> Exp a -> Exp a) -> Acc (Array sh' a) -> (Exp sh -> Exp (Maybe sh')) -> Acc (Array sh a) -> Acc (Array sh' a) -- | Overwrite elements of the destination by scattering the values of the -- source array according to the given index mapping. -- -- Note that if the destination index appears more than once in the -- mapping the result is undefined. -- -- 
--   >>> let to    = fromList (Z :. 6) [1,3,7,2,5,8] :: Vector Int
--   
--   >>> let input = fromList (Z :. 7) [1,9,6,4,4,2,5] :: Vector Int
--   
--   >>> run $ scatter (use to) (fill (constant (Z:.10)) 0) (use input)
--   Vector (Z :. 10) [0,1,4,9,0,4,0,6,2,0]
--
scatter :: Elt e => Acc (Vector Int) -> Acc (Vector e) -> Acc (Vector e) -> Acc (Vector e) -- | Generalised backward permutation operation (array gather). -- -- Backward permutation specified by a function mapping indices in the -- destination array to indices in the source array. Elements of the -- output array are thus generated by reading from the corresponding -- index in the source array. -- -- For example, backpermute can be used to transpose a matrix; at -- every index Z:.y:.x in the result array, we get the value at -- that index by reading from the source array at index Z:.x:.y: -- -- 
--   >>> :{
--     let swap :: Exp DIM2 -> Exp DIM2
--         swap = lift1 f
--           where
--             f :: Z :. Exp Int :. Exp Int -> Z :. Exp Int :. Exp Int
--             f (Z:.y:.x) = Z :. x :. y
--   :}
--
-- -- 
--   >>> let mat = fromList (Z:.5:.10) [0..] :: Matrix Int
--   
--   >>> mat
--   Matrix (Z :. 5 :. 10)
--     [  0,  1,  2,  3,  4,  5,  6,  7,  8,  9,
--       10, 11, 12, 13, 14, 15, 16, 17, 18, 19,
--       20, 21, 22, 23, 24, 25, 26, 27, 28, 29,
--       30, 31, 32, 33, 34, 35, 36, 37, 38, 39,
--       40, 41, 42, 43, 44, 45, 46, 47, 48, 49]
--
-- -- 
--   >>> let mat' = use mat
--   
--   >>> run $ backpermute (swap (shape mat')) swap mat'
--   Matrix (Z :. 10 :. 5)
--     [ 0, 10, 20, 30, 40,
--       1, 11, 21, 31, 41,
--       2, 12, 22, 32, 42,
--       3, 13, 23, 33, 43,
--       4, 14, 24, 34, 44,
--       5, 15, 25, 35, 45,
--       6, 16, 26, 36, 46,
--       7, 17, 27, 37, 47,
--       8, 18, 28, 38, 48,
--       9, 19, 29, 39, 49]
--
backpermute :: forall sh sh' a. (Shape sh, Shape sh', Elt a) => Exp sh' -> (Exp sh' -> Exp sh) -> Acc (Array sh a) -> Acc (Array sh' a) -- | Gather elements from a source array by reading values at the given -- indices. -- -- 
--   >>> let input = fromList (Z:.9) [1,9,6,4,4,2,0,1,2] :: Vector Int
--   
--   >>> let from  = fromList (Z:.6) [1,3,7,2,5,3] :: Vector Int
--   
--   >>> run $ gather (use from) (use input)
--   Vector (Z :. 6) [9,4,1,6,2,4]
--
gather :: (Shape sh, Elt e) => Acc (Array sh Int) -> Acc (Vector e) -> Acc (Array sh e) -- | Reverse the elements of a vector. reverse :: Elt e => Acc (Vector e) -> Acc (Vector e) -- | Transpose the rows and columns of a matrix. transpose :: Elt e => Acc (Array DIM2 e) -> Acc (Array DIM2 e) -- | Generalised version of reverse where the argument Lens' -- specifies which dimension to reverse. -- -- Appropriate lenses are available from lens-accelerate. -- -- 
--   >>> let mat = fromList (Z:.5:.10) [0..] :: Matrix Int
--   
--   >>> mat
--   Matrix (Z :. 5 :. 10)
--     [  0,  1,  2,  3,  4,  5,  6,  7,  8,  9,
--       10, 11, 12, 13, 14, 15, 16, 17, 18, 19,
--       20, 21, 22, 23, 24, 25, 26, 27, 28, 29,
--       30, 31, 32, 33, 34, 35, 36, 37, 38, 39,
--       40, 41, 42, 43, 44, 45, 46, 47, 48, 49]
--
-- -- 
--   >>> run $ reverseOn _1 (use mat)
--   Matrix (Z :. 5 :. 10)
--     [  9,  8,  7,  6,  5,  4,  3,  2,  1,  0,
--       19, 18, 17, 16, 15, 14, 13, 12, 11, 10,
--       29, 28, 27, 26, 25, 24, 23, 22, 21, 20,
--       39, 38, 37, 36, 35, 34, 33, 32, 31, 30,
--       49, 48, 47, 46, 45, 44, 43, 42, 41, 40]
--
-- -- 
--   >>> run $ reverseOn _2 (use mat)
--   Matrix (Z :. 5 :. 10)
--     [ 40, 41, 42, 43, 44, 45, 46, 47, 48, 49,
--       30, 31, 32, 33, 34, 35, 36, 37, 38, 39,
--       20, 21, 22, 23, 24, 25, 26, 27, 28, 29,
--       10, 11, 12, 13, 14, 15, 16, 17, 18, 19,
--        0,  1,  2,  3,  4,  5,  6,  7,  8,  9]
--
reverseOn :: (Shape sh, Elt e) => Lens' (Exp sh) (Exp Int) -> Acc (Array sh e) -> Acc (Array sh e) -- | Generalised version of transpose where the argument -- Lens's specify which two dimensions to transpose. -- -- Appropriate lenses are available from lens-accelerate. -- -- 
--   >>> let mat = fromList (Z:.5:.10) [0..] :: Matrix Int
--   
--   >>> mat
--   Matrix (Z :. 5 :. 10)
--     [  0,  1,  2,  3,  4,  5,  6,  7,  8,  9,
--       10, 11, 12, 13, 14, 15, 16, 17, 18, 19,
--       20, 21, 22, 23, 24, 25, 26, 27, 28, 29,
--       30, 31, 32, 33, 34, 35, 36, 37, 38, 39,
--       40, 41, 42, 43, 44, 45, 46, 47, 48, 49]
--
-- -- 
--   >>> run $ transposeOn _1 _2 (use mat)
--   Matrix (Z :. 10 :. 5)
--     [ 0, 10, 20, 30, 40,
--       1, 11, 21, 31, 41,
--       2, 12, 22, 32, 42,
--       3, 13, 23, 33, 43,
--       4, 14, 24, 34, 44,
--       5, 15, 25, 35, 45,
--       6, 16, 26, 36, 46,
--       7, 17, 27, 37, 47,
--       8, 18, 28, 38, 48,
--       9, 19, 29, 39, 49]
--
-- -- 
--   >>> let box = fromList (Z:.2:.3:.5) [0..] :: Array DIM3 Int
--   
--   >>> box
--   Array (Z :. 2 :. 3 :. 5) [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29]
--
-- -- 
--   >>> run $ transposeOn _1 _2 (use box)
--   Array (Z :. 2 :. 5 :. 3) [0,5,10,1,6,11,2,7,12,3,8,13,4,9,14,15,20,25,16,21,26,17,22,27,18,23,28,19,24,29]
--
-- -- 
--   >>> run $ transposeOn _2 _3 (use box)
--   Array (Z :. 3 :. 2 :. 5) [0,1,2,3,4,15,16,17,18,19,5,6,7,8,9,20,21,22,23,24,10,11,12,13,14,25,26,27,28,29]
--
-- -- 
--   >>> run $ transposeOn _1 _3 (use box)
--   Array (Z :. 5 :. 3 :. 2) [0,15,5,20,10,25,1,16,6,21,11,26,2,17,7,22,12,27,3,18,8,23,13,28,4,19,9,24,14,29]
--
transposeOn :: (Shape sh, Elt e) => Lens' (Exp sh) (Exp Int) -> Lens' (Exp sh) (Exp Int) -> Acc (Array sh e) -> Acc (Array sh e) -- | Drop elements that do not satisfy the predicate. Returns the elements -- which pass the predicate, together with a segment descriptor -- indicating how many elements along each outer dimension were valid. -- -- 
--   >>> let vec = fromList (Z :. 10) [1..10] :: Vector Int
--   
--   >>> vec
--   Vector (Z :. 10) [1,2,3,4,5,6,7,8,9,10]
--
-- -- 
--   >>> run $ filter even (use vec)
--   (Vector (Z :. 5) [2,4,6,8,10],Scalar Z [5])
--
-- -- 
--   >>> let mat = fromList (Z :. 4 :. 10) [1,2,3,4,5,6,7,8,9,10,1,1,1,1,1,2,2,2,2,2,2,4,6,8,10,12,14,16,18,20,1,3,5,7,9,11,13,15,17,19] :: Matrix Int
--   
--   >>> mat
--   Matrix (Z :. 4 :. 10)
--     [ 1, 2, 3, 4,  5,  6,  7,  8,  9, 10,
--       1, 1, 1, 1,  1,  2,  2,  2,  2,  2,
--       2, 4, 6, 8, 10, 12, 14, 16, 18, 20,
--       1, 3, 5, 7,  9, 11, 13, 15, 17, 19]
--
-- -- 
--   >>> run $ filter odd (use mat)
--   (Vector (Z :. 20) [1,3,5,7,9,1,1,1,1,1,1,3,5,7,9,11,13,15,17,19],Vector (Z :. 4) [5,5,0,10])
--
filter :: (Shape sh, Elt e) => (Exp e -> Exp Bool) -> Acc (Array (sh :. Int) e) -> Acc (Vector e, Array sh Int) -- | As filter, but with separate arrays for the data elements and -- the flags indicating which elements of that array should be kept. compact :: forall sh e. (Shape sh, Elt e) => Acc (Array (sh :. Int) Bool) -> Acc (Array (sh :. Int) e) -> Acc (Vector e, Array sh Int) -- | Reduction of the innermost dimension of an array of arbitrary rank. -- -- The shape of the result obeys the property: -- -- 
--   shape (fold f z xs) == indexTail (shape xs)
--
-- -- The first argument needs to be an associative function to -- enable an efficient parallel implementation. The initial element does -- not need to be an identity element of the combination function. -- -- 
--   >>> let mat = fromList (Z:.5:.10) [0..] :: Matrix Int
--   
--   >>> mat
--   Matrix (Z :. 5 :. 10)
--     [  0,  1,  2,  3,  4,  5,  6,  7,  8,  9,
--       10, 11, 12, 13, 14, 15, 16, 17, 18, 19,
--       20, 21, 22, 23, 24, 25, 26, 27, 28, 29,
--       30, 31, 32, 33, 34, 35, 36, 37, 38, 39,
--       40, 41, 42, 43, 44, 45, 46, 47, 48, 49]
--
-- -- 
--   >>> run $ fold (+) 42 (use mat)
--   Vector (Z :. 5) [87,187,287,387,487]
--
-- -- Reductions with non-commutative operators are supported. For example, -- the following computes the maximum segment sum problem along each -- innermost dimension of the array. -- -- https://en.wikipedia.org/wiki/Maximum_subarray_problem -- -- 
--   >>> :{
--     let maximumSegmentSum
--             :: forall sh e. (Shape sh, Num e, Ord e)
--             => Acc (Array (sh :. Int) e)
--             -> Acc (Array sh e)
--         maximumSegmentSum
--           = map (\(T4 x _ _ _) -> x)
--           . fold1 f
--           . map g
--           where
--             f :: (Num a, Ord a) => Exp (a,a,a,a) -> Exp (a,a,a,a) -> Exp (a,a,a,a)
--             f x y =
--               let T4 mssx misx mcsx tsx = x
--                   T4 mssy misy mcsy tsy = y
--               in
--               T4 (mssx `max` (mssy `max` (mcsx+misy)))
--                  (misx `max` (tsx+misy))
--                  (mcsy `max` (mcsx+tsy))
--                  (tsx+tsy)
--             --
--             g :: (Num a, Ord a) => Exp a -> Exp (a,a,a,a)
--             g x = let y = max x 0
--                    in T4 y y y x
--   :}
--
-- -- 
--   >>> let vec = fromList (Z:.10) [-2,1,-3,4,-1,2,1,-5,4,0] :: Vector Int
--   
--   >>> run $ maximumSegmentSum (use vec)
--   Scalar Z [6]
--
-- -- See also Fold, which can be a useful way to compute multiple -- results from a single reduction. fold :: forall sh a. (Shape sh, Elt a) => (Exp a -> Exp a -> Exp a) -> Exp a -> Acc (Array (sh :. Int) a) -> Acc (Array sh a) -- | Variant of fold that requires the innermost dimension of the -- array to be non-empty and doesn't need an default value. -- -- The shape of the result obeys the property: -- -- 
--   shape (fold f z xs) == indexTail (shape xs)
--
-- -- The first argument needs to be an associative function to -- enable an efficient parallel implementation, but does not need to be -- commutative. fold1 :: forall sh a. (Shape sh, Elt a) => (Exp a -> Exp a -> Exp a) -> Acc (Array (sh :. Int) a) -> Acc (Array sh a) -- | Reduction of an array of arbitrary rank to a single scalar value. The -- first argument needs to be an associative function to enable -- efficient parallel implementation. The initial element does not need -- to be an identity element. -- -- 
--   >>> let vec = fromList (Z:.10) [0..] :: Vector Float
--   
--   >>> run $ foldAll (+) 42 (use vec)
--   Scalar Z [87.0]
--
-- -- 
--   >>> let mat = fromList (Z:.5:.10) [0..] :: Matrix Float
--   
--   >>> run $ foldAll (+) 0 (use mat)
--   Scalar Z [1225.0]
--
foldAll :: (Shape sh, Elt a) => (Exp a -> Exp a -> Exp a) -> Exp a -> Acc (Array sh a) -> Acc (Scalar a) -- | Variant of foldAll that requires the reduced array to be -- non-empty and does not need a default value. The first argument must -- be an associative function. fold1All :: (Shape sh, Elt a) => (Exp a -> Exp a -> Exp a) -> Acc (Array sh a) -> Acc (Scalar a) -- | Segmented reduction along the innermost dimension of an array. The -- segment descriptor specifies the lengths of the logical sub-arrays, -- each of which is reduced independently. The innermost dimension must -- contain at least as many elements as required by the segment -- descriptor (sum thereof). -- -- 
--   >>> let seg = fromList (Z:.4) [1,4,0,3] :: Segments Int
--   
--   >>> seg
--   Vector (Z :. 4) [1,4,0,3]
--
-- -- 
--   >>> let mat = fromList (Z:.5:.10) [0..] :: Matrix Int
--   
--   >>> mat
--   Matrix (Z :. 5 :. 10)
--     [  0,  1,  2,  3,  4,  5,  6,  7,  8,  9,
--       10, 11, 12, 13, 14, 15, 16, 17, 18, 19,
--       20, 21, 22, 23, 24, 25, 26, 27, 28, 29,
--       30, 31, 32, 33, 34, 35, 36, 37, 38, 39,
--       40, 41, 42, 43, 44, 45, 46, 47, 48, 49]
--
-- -- 
--   >>> run $ foldSeg (+) 0 (use mat) (use seg)
--   Matrix (Z :. 5 :. 4)
--     [  0,  10, 0,  18,
--       10,  50, 0,  48,
--       20,  90, 0,  78,
--       30, 130, 0, 108,
--       40, 170, 0, 138]
--
foldSeg :: forall sh e i. (Shape sh, Elt e, Elt i, i ~ EltR i, IsIntegral i) => (Exp e -> Exp e -> Exp e) -> Exp e -> Acc (Array (sh :. Int) e) -> Acc (Segments i) -> Acc (Array (sh :. Int) e) -- | Variant of foldSeg that requires all segments of the -- reduced array to be non-empty, and does not need a default value. The -- segment descriptor species the length of each of the logical -- sub-arrays. fold1Seg :: forall sh e i. (Shape sh, Elt e, Elt i, i ~ EltR i, IsIntegral i) => (Exp e -> Exp e -> Exp e) -> Acc (Array (sh :. Int) e) -> Acc (Segments i) -> Acc (Array (sh :. Int) e) -- | Segmented reduction along the innermost dimension of an array. The -- segment descriptor specifies the starting index (offset) along the -- innermost dimension to the beginning of each logical sub-array. -- -- The value in the output array at index i is the reduction of values -- between the indices of the segment descriptor at index i and (i+1). -- -- We have that: -- -- 
--   foldSeg f z xs seg  ==  foldSeg' f z xs (scanl (+) 0 seg)
--
foldSeg' :: forall sh a i. (Shape sh, Elt a, Elt i, IsIntegral i, i ~ EltR i) => (Exp a -> Exp a -> Exp a) -> Exp a -> Acc (Array (sh :. Int) a) -> Acc (Segments i) -> Acc (Array (sh :. Int) a) -- | Variant of foldSeg' that requires all segments of the -- reduced array to be non-empty, and doesn't need a default value. The -- segment descriptor specifies the offset to the beginning of each of -- the logical sub-arrays. fold1Seg' :: forall sh a i. (Shape sh, Elt a, Elt i, IsIntegral i, i ~ EltR i) => (Exp a -> Exp a -> Exp a) -> Acc (Array (sh :. Int) a) -> Acc (Segments i) -> Acc (Array (sh :. Int) a) -- | Check if all elements along the innermost dimension satisfy a -- predicate. -- -- 
--   >>> let mat = fromList (Z :. 4 :. 10) [1,2,3,4,5,6,7,8,9,10,1,1,1,1,1,2,2,2,2,2,2,4,6,8,10,12,14,16,18,20,1,3,5,7,9,11,13,15,17,19] :: Matrix Int
--   
--   >>> mat
--   Matrix (Z :. 4 :. 10)
--     [ 1, 2, 3, 4,  5,  6,  7,  8,  9, 10,
--       1, 1, 1, 1,  1,  2,  2,  2,  2,  2,
--       2, 4, 6, 8, 10, 12, 14, 16, 18, 20,
--       1, 3, 5, 7,  9, 11, 13, 15, 17, 19]
--
-- -- 
--   >>> run $ all even (use mat)
--   Vector (Z :. 4) [False,False,True,False]
--
all :: (Shape sh, Elt e) => (Exp e -> Exp Bool) -> Acc (Array (sh :. Int) e) -> Acc (Array sh Bool) -- | Check if any element along the innermost dimension satisfies the -- predicate. -- -- 
--   >>> let mat = fromList (Z :. 4 :. 10) [1,2,3,4,5,6,7,8,9,10,1,1,1,1,1,2,2,2,2,2,2,4,6,8,10,12,14,16,18,20,1,3,5,7,9,11,13,15,17,19] :: Matrix Int
--   
--   >>> mat
--   Matrix (Z :. 4 :. 10)
--     [ 1, 2, 3, 4,  5,  6,  7,  8,  9, 10,
--       1, 1, 1, 1,  1,  2,  2,  2,  2,  2,
--       2, 4, 6, 8, 10, 12, 14, 16, 18, 20,
--       1, 3, 5, 7,  9, 11, 13, 15, 17, 19]
--
-- -- 
--   >>> run $ any even (use mat)
--   Vector (Z :. 4) [True,True,True,False]
--
any :: (Shape sh, Elt e) => (Exp e -> Exp Bool) -> Acc (Array (sh :. Int) e) -> Acc (Array sh Bool) -- | Check if all elements along the innermost dimension are True. and :: Shape sh => Acc (Array (sh :. Int) Bool) -> Acc (Array sh Bool) -- | Check if any element along the innermost dimension is True. or :: Shape sh => Acc (Array (sh :. Int) Bool) -> Acc (Array sh Bool) -- | Compute the sum of elements along the innermost dimension of the -- array. To find the sum of the entire array, flatten it first. -- -- 
--   >>> let mat = fromList (Z:.2:.5) [0..] :: Matrix Int
--   
--   >>> run $ sum (use mat)
--   Vector (Z :. 2) [10,35]
--
sum :: (Shape sh, Num e) => Acc (Array (sh :. Int) e) -> Acc (Array sh e) -- | Compute the product of the elements along the innermost dimension of -- the array. To find the product of the entire array, flatten it -- first. -- -- 
--   >>> let mat = fromList (Z:.2:.5) [0..] :: Matrix Int
--   
--   >>> run $ product (use mat)
--   Vector (Z :. 2) [0,15120]
--
product :: (Shape sh, Num e) => Acc (Array (sh :. Int) e) -> Acc (Array sh e) -- | Yield the minimum element along the innermost dimension of the array. -- To find find the minimum element of the entire array, flatten -- it first. -- -- The array must not be empty. See also fold1. -- -- 
--   >>> let mat = fromList (Z :. 3 :. 4) [1,4,3,8, 0,2,8,4, 7,9,8,8] :: Matrix Int
--   
--   >>> mat
--   Matrix (Z :. 3 :. 4)
--     [ 1, 4, 3, 8,
--       0, 2, 8, 4,
--       7, 9, 8, 8]
--
-- -- 
--   >>> run $ minimum (use mat)
--   Vector (Z :. 3) [1,0,7]
--
minimum :: (Shape sh, Ord e) => Acc (Array (sh :. Int) e) -> Acc (Array sh e) -- | Yield the maximum element along the innermost dimension of the array. -- To find the maximum element of the entire array, flatten it -- first. -- -- The array must not be empty. See also fold1. -- -- 
--   >>> let mat = fromList (Z :. 3 :. 4) [1,4,3,8, 0,2,8,4, 7,9,8,8] :: Matrix Int
--   
--   >>> mat
--   Matrix (Z :. 3 :. 4)
--     [ 1, 4, 3, 8,
--       0, 2, 8, 4,
--       7, 9, 8, 8]
--
-- -- 
--   >>> run $ maximum (use mat)
--   Vector (Z :. 3) [8,8,9]
--
maximum :: (Shape sh, Ord e) => Acc (Array (sh :. Int) e) -> Acc (Array sh e) -- | Data.List style left-to-right scan along the innermost dimension of an -- arbitrary rank array. The first argument needs to be an -- associative function to enable efficient parallel -- implementation. The initial value (second argument) may be arbitrary. -- -- 
--   >>> let vec = fromList (Z :. 10) [0..] :: Vector Int
--   
--   >>> run $ scanl (+) 10 (use vec)
--   Vector (Z :. 11) [10,10,11,13,16,20,25,31,38,46,55]
--
-- -- 
--   >>> let mat = fromList (Z :. 4 :. 10) [0..] :: Matrix Int
--   
--   >>> run $ scanl (+) 0 (use mat)
--   Matrix (Z :. 4 :. 11)
--     [ 0,  0,  1,  3,   6,  10,  15,  21,  28,  36,  45,
--       0, 10, 21, 33,  46,  60,  75,  91, 108, 126, 145,
--       0, 20, 41, 63,  86, 110, 135, 161, 188, 216, 245,
--       0, 30, 61, 93, 126, 160, 195, 231, 268, 306, 345]
--
scanl :: forall sh a. (Shape sh, Elt a) => (Exp a -> Exp a -> Exp a) -> Exp a -> Acc (Array (sh :. Int) a) -> Acc (Array (sh :. Int) a) -- | Data.List style left-to-right scan along the innermost dimension -- without an initial value (aka inclusive scan). The innermost dimension -- of the array must not be empty. The first argument must be an -- associative function. -- -- 
--   >>> let mat = fromList (Z:.4:.10) [0..] :: Matrix Int
--   
--   >>> run $ scanl1 (+) (use mat)
--   Matrix (Z :. 4 :. 10)
--     [  0,  1,  3,   6,  10,  15,  21,  28,  36,  45,
--       10, 21, 33,  46,  60,  75,  91, 108, 126, 145,
--       20, 41, 63,  86, 110, 135, 161, 188, 216, 245,
--       30, 61, 93, 126, 160, 195, 231, 268, 306, 345]
--
scanl1 :: forall sh a. (Shape sh, Elt a) => (Exp a -> Exp a -> Exp a) -> Acc (Array (sh :. Int) a) -> Acc (Array (sh :. Int) a) -- | Variant of scanl, where the last element (final reduction -- result) along each dimension is returned separately. Denotationally we -- have: -- -- 
--   scanl' f e arr = (init res, unit (res!len))
--     where
--       len = shape arr
--       res = scanl f e arr
--
-- -- 
--   >>> let vec       = fromList (Z:.10) [0..] :: Vector Int
--   
--   >>> let (res,sum) = run $ scanl' (+) 0 (use vec)
--   
--   >>> res
--   Vector (Z :. 10) [0,0,1,3,6,10,15,21,28,36]
--   
--   >>> sum
--   Scalar Z [45]
--
-- -- 
--   >>> let mat        = fromList (Z:.4:.10) [0..] :: Matrix Int
--   
--   >>> let (res,sums) = run $ scanl' (+) 0 (use mat)
--   
--   >>> res
--   Matrix (Z :. 4 :. 10)
--     [ 0,  0,  1,  3,   6,  10,  15,  21,  28,  36,
--       0, 10, 21, 33,  46,  60,  75,  91, 108, 126,
--       0, 20, 41, 63,  86, 110, 135, 161, 188, 216,
--       0, 30, 61, 93, 126, 160, 195, 231, 268, 306]
--   
--   >>> sums
--   Vector (Z :. 4) [45,145,245,345]
--
scanl' :: forall sh a. (Shape sh, Elt a) => (Exp a -> Exp a -> Exp a) -> Exp a -> Acc (Array (sh :. Int) a) -> Acc (Array (sh :. Int) a, Array sh a) -- | Right-to-left variant of scanl. scanr :: forall sh a. (Shape sh, Elt a) => (Exp a -> Exp a -> Exp a) -> Exp a -> Acc (Array (sh :. Int) a) -> Acc (Array (sh :. Int) a) -- | Right-to-left variant of scanl1. scanr1 :: forall sh a. (Shape sh, Elt a) => (Exp a -> Exp a -> Exp a) -> Acc (Array (sh :. Int) a) -> Acc (Array (sh :. Int) a) -- | Right-to-left variant of scanl'. scanr' :: forall sh a. (Shape sh, Elt a) => (Exp a -> Exp a -> Exp a) -> Exp a -> Acc (Array (sh :. Int) a) -> Acc (Array (sh :. Int) a, Array sh a) -- | Left-to-right pre-scan (aka exclusive scan). As for scan, the -- first argument must be an associative function. Denotationally, -- we have: -- -- 
--   prescanl f e = afst . scanl' f e
--
-- -- 
--   >>> let vec = fromList (Z:.10) [1..10] :: Vector Int
--   
--   >>> run $ prescanl (+) 0 (use vec)
--   Vector (Z :. 10) [0,1,3,6,10,15,21,28,36,45]
--
prescanl :: (Shape sh, Elt a) => (Exp a -> Exp a -> Exp a) -> Exp a -> Acc (Array (sh :. Int) a) -> Acc (Array (sh :. Int) a) -- | Left-to-right post-scan, a variant of scanl1 with an initial -- value. As with scanl1, the array must not be empty. -- Denotationally, we have: -- -- 
--   postscanl f e = map (e `f`) . scanl1 f
--
-- -- 
--   >>> let vec = fromList (Z:.10) [1..10] :: Vector Int
--   
--   >>> run $ postscanl (+) 42 (use vec)
--   Vector (Z :. 10) [43,45,48,52,57,63,70,78,87,97]
--
postscanl :: (Shape sh, Elt a) => (Exp a -> Exp a -> Exp a) -> Exp a -> Acc (Array (sh :. Int) a) -> Acc (Array (sh :. Int) a) -- | Right-to-left pre-scan (aka exclusive scan). As for scan, the -- first argument must be an associative function. Denotationally, -- we have: -- -- 
--   prescanr f e = afst . scanr' f e
--
prescanr :: (Shape sh, Elt a) => (Exp a -> Exp a -> Exp a) -> Exp a -> Acc (Array (sh :. Int) a) -> Acc (Array (sh :. Int) a) -- | Right-to-left postscan, a variant of scanr1 with an initial -- value. Denotationally, we have: -- -- 
--   postscanr f e = map (e `f`) . scanr1 f
--
postscanr :: (Shape sh, Elt a) => (Exp a -> Exp a -> Exp a) -> Exp a -> Acc (Array (sh :. Int) a) -> Acc (Array (sh :. Int) a) -- | Segmented version of scanl along the innermost dimension of an -- array. The innermost dimension must have at least as many elements as -- the sum of the segment descriptor. -- -- 
--   >>> let seg = fromList (Z:.4) [1,4,0,3] :: Segments Int
--   
--   >>> seg
--   Vector (Z :. 4) [1,4,0,3]
--
-- -- 
--   >>> let mat = fromList (Z:.5:.10) [0..] :: Matrix Int
--   
--   >>> mat
--   Matrix (Z :. 5 :. 10)
--     [  0,  1,  2,  3,  4,  5,  6,  7,  8,  9,
--       10, 11, 12, 13, 14, 15, 16, 17, 18, 19,
--       20, 21, 22, 23, 24, 25, 26, 27, 28, 29,
--       30, 31, 32, 33, 34, 35, 36, 37, 38, 39,
--       40, 41, 42, 43, 44, 45, 46, 47, 48, 49]
--
-- -- 
--   >>> run $ scanlSeg (+) 0 (use mat) (use seg)
--   Matrix (Z :. 5 :. 12)
--     [ 0,  0, 0,  1,  3,   6,  10, 0, 0,  5, 11,  18,
--       0, 10, 0, 11, 23,  36,  50, 0, 0, 15, 31,  48,
--       0, 20, 0, 21, 43,  66,  90, 0, 0, 25, 51,  78,
--       0, 30, 0, 31, 63,  96, 130, 0, 0, 35, 71, 108,
--       0, 40, 0, 41, 83, 126, 170, 0, 0, 45, 91, 138]
--
scanlSeg :: forall sh e i. (Shape sh, Slice sh, Elt e, Integral i, Bits i, FromIntegral i Int) => (Exp e -> Exp e -> Exp e) -> Exp e -> Acc (Array (sh :. Int) e) -> Acc (Segments i) -> Acc (Array (sh :. Int) e) -- | Segmented version of scanl1 along the innermost dimension. -- -- As with scanl1, the total number of elements considered, in -- this case given by the sum of segment descriptor, must not be -- zero. The input vector must contain at least this many elements. -- -- Zero length segments are allowed, and the behaviour is as if those -- entries were not present in the segment descriptor; that is: -- -- 
--   scanl1Seg f xs [n,0,0] == scanl1Seg f xs [n]   where n /= 0
--
-- -- 
--   >>> let seg = fromList (Z:.4) [1,4,0,3] :: Segments Int
--   
--   >>> seg
--   Vector (Z :. 4) [1,4,0,3]
--
-- -- 
--   >>> let mat = fromList (Z:.5:.10) [0..] :: Matrix Int
--   
--   >>> mat
--   Matrix (Z :. 5 :. 10)
--     [  0,  1,  2,  3,  4,  5,  6,  7,  8,  9,
--       10, 11, 12, 13, 14, 15, 16, 17, 18, 19,
--       20, 21, 22, 23, 24, 25, 26, 27, 28, 29,
--       30, 31, 32, 33, 34, 35, 36, 37, 38, 39,
--       40, 41, 42, 43, 44, 45, 46, 47, 48, 49]
--
-- -- 
--   >>> run $ scanl1Seg (+) (use mat) (use seg)
--   Matrix (Z :. 5 :. 8)
--     [  0,  1,  3,   6,  10,  5, 11,  18,
--       10, 11, 23,  36,  50, 15, 31,  48,
--       20, 21, 43,  66,  90, 25, 51,  78,
--       30, 31, 63,  96, 130, 35, 71, 108,
--       40, 41, 83, 126, 170, 45, 91, 138]
--
scanl1Seg :: (Shape sh, Slice sh, Elt e, Integral i, Bits i, FromIntegral i Int) => (Exp e -> Exp e -> Exp e) -> Acc (Array (sh :. Int) e) -> Acc (Segments i) -> Acc (Array (sh :. Int) e) -- | Segmented version of scanl' along the innermost dimension of an -- array. The innermost dimension must have at least as many elements as -- the sum of the segment descriptor. -- -- The first element of the resulting tuple is a vector of scanned -- values. The second element is a vector of segment scan totals and has -- the same size as the segment vector. -- -- 
--   >>> let seg = fromList (Z:.4) [1,4,0,3] :: Segments Int
--   
--   >>> seg
--   Vector (Z :. 4) [1,4,0,3]
--
-- -- 
--   >>> let mat = fromList (Z:.5:.10) [0..] :: Matrix Int
--   
--   >>> mat
--   Matrix (Z :. 5 :. 10)
--     [  0,  1,  2,  3,  4,  5,  6,  7,  8,  9,
--       10, 11, 12, 13, 14, 15, 16, 17, 18, 19,
--       20, 21, 22, 23, 24, 25, 26, 27, 28, 29,
--       30, 31, 32, 33, 34, 35, 36, 37, 38, 39,
--       40, 41, 42, 43, 44, 45, 46, 47, 48, 49]
--
-- -- 
--   >>> let (res,sums) = run $ scanl'Seg (+) 0 (use mat) (use seg)
--   
--   >>> res
--   Matrix (Z :. 5 :. 8)
--     [ 0, 0,  1,  3,   6, 0,  5, 11,
--       0, 0, 11, 23,  36, 0, 15, 31,
--       0, 0, 21, 43,  66, 0, 25, 51,
--       0, 0, 31, 63,  96, 0, 35, 71,
--       0, 0, 41, 83, 126, 0, 45, 91]
--   
--   >>> sums
--   Matrix (Z :. 5 :. 4)
--     [  0,  10, 0,  18,
--       10,  50, 0,  48,
--       20,  90, 0,  78,
--       30, 130, 0, 108,
--       40, 170, 0, 138]
--
scanl'Seg :: forall sh e i. (Shape sh, Slice sh, Elt e, Integral i, Bits i, FromIntegral i Int) => (Exp e -> Exp e -> Exp e) -> Exp e -> Acc (Array (sh :. Int) e) -> Acc (Segments i) -> Acc (Array (sh :. Int) e, Array (sh :. Int) e) -- | Segmented version of prescanl. prescanlSeg :: (Shape sh, Slice sh, Elt e, Integral i, Bits i, FromIntegral i Int) => (Exp e -> Exp e -> Exp e) -> Exp e -> Acc (Array (sh :. Int) e) -> Acc (Segments i) -> Acc (Array (sh :. Int) e) -- | Segmented version of postscanl. postscanlSeg :: (Shape sh, Slice sh, Elt e, Integral i, Bits i, FromIntegral i Int) => (Exp e -> Exp e -> Exp e) -> Exp e -> Acc (Array (sh :. Int) e) -> Acc (Segments i) -> Acc (Array (sh :. Int) e) -- | Segmented version of scanr along the innermost dimension of an -- array. The innermost dimension must have at least as many elements as -- the sum of the segment descriptor. -- -- 
--   >>> let seg = fromList (Z:.4) [1,4,0,3] :: Segments Int
--   
--   >>> seg
--   Vector (Z :. 4) [1,4,0,3]
--
-- -- 
--   >>> let mat = fromList (Z:.5:.10) [0..] :: Matrix Int
--   
--   >>> mat
--   Matrix (Z :. 5 :. 10)
--     [  0,  1,  2,  3,  4,  5,  6,  7,  8,  9,
--       10, 11, 12, 13, 14, 15, 16, 17, 18, 19,
--       20, 21, 22, 23, 24, 25, 26, 27, 28, 29,
--       30, 31, 32, 33, 34, 35, 36, 37, 38, 39,
--       40, 41, 42, 43, 44, 45, 46, 47, 48, 49]
--
-- -- 
--   >>> run $ scanrSeg (+) 0 (use mat) (use seg)
--   Matrix (Z :. 5 :. 12)
--     [  2, 0,  18,  15, 11,  6, 0, 0,  24, 17,  9, 0,
--       12, 0,  58,  45, 31, 16, 0, 0,  54, 37, 19, 0,
--       22, 0,  98,  75, 51, 26, 0, 0,  84, 57, 29, 0,
--       32, 0, 138, 105, 71, 36, 0, 0, 114, 77, 39, 0,
--       42, 0, 178, 135, 91, 46, 0, 0, 144, 97, 49, 0]
--
scanrSeg :: forall sh e i. (Shape sh, Slice sh, Elt e, Integral i, Bits i, FromIntegral i Int) => (Exp e -> Exp e -> Exp e) -> Exp e -> Acc (Array (sh :. Int) e) -> Acc (Segments i) -> Acc (Array (sh :. Int) e) -- | Segmented version of scanr1. -- -- 
--   >>> let seg = fromList (Z:.4) [1,4,0,3] :: Segments Int
--   
--   >>> seg
--   Vector (Z :. 4) [1,4,0,3]
--
-- -- 
--   >>> let mat = fromList (Z:.5:.10) [0..] :: Matrix Int
--   
--   >>> mat
--   Matrix (Z :. 5 :. 10)
--     [  0,  1,  2,  3,  4,  5,  6,  7,  8,  9,
--       10, 11, 12, 13, 14, 15, 16, 17, 18, 19,
--       20, 21, 22, 23, 24, 25, 26, 27, 28, 29,
--       30, 31, 32, 33, 34, 35, 36, 37, 38, 39,
--       40, 41, 42, 43, 44, 45, 46, 47, 48, 49]
--
-- -- 
--   >>> run $ scanr1Seg (+) (use mat) (use seg)
--   Matrix (Z :. 5 :. 8)
--     [  0,  10,   9,  7,  4,  18, 13,  7,
--       10,  50,  39, 27, 14,  48, 33, 17,
--       20,  90,  69, 47, 24,  78, 53, 27,
--       30, 130,  99, 67, 34, 108, 73, 37,
--       40, 170, 129, 87, 44, 138, 93, 47]
--
scanr1Seg :: (Shape sh, Slice sh, Elt e, Integral i, Bits i, FromIntegral i Int) => (Exp e -> Exp e -> Exp e) -> Acc (Array (sh :. Int) e) -> Acc (Segments i) -> Acc (Array (sh :. Int) e) -- | Segmented version of scanr'. -- -- 
--   >>> let seg = fromList (Z:.4) [1,4,0,3] :: Segments Int
--   
--   >>> seg
--   Vector (Z :. 4) [1,4,0,3]
--
-- -- 
--   >>> let mat = fromList (Z:.5:.10) [0..] :: Matrix Int
--   
--   >>> mat
--   Matrix (Z :. 5 :. 10)
--     [  0,  1,  2,  3,  4,  5,  6,  7,  8,  9,
--       10, 11, 12, 13, 14, 15, 16, 17, 18, 19,
--       20, 21, 22, 23, 24, 25, 26, 27, 28, 29,
--       30, 31, 32, 33, 34, 35, 36, 37, 38, 39,
--       40, 41, 42, 43, 44, 45, 46, 47, 48, 49]
--
-- -- 
--   >>> let (res,sums) = run $ scanr'Seg (+) 0 (use mat) (use seg)
--   
--   >>> res
--   Matrix (Z :. 5 :. 8)
--     [ 0,  15, 11,  6, 0, 17,  9, 0,
--       0,  45, 31, 16, 0, 37, 19, 0,
--       0,  75, 51, 26, 0, 57, 29, 0,
--       0, 105, 71, 36, 0, 77, 39, 0,
--       0, 135, 91, 46, 0, 97, 49, 0]
--   
--   >>> sums
--   Matrix (Z :. 5 :. 4)
--     [  2,  18, 0,  24,
--       12,  58, 0,  54,
--       22,  98, 0,  84,
--       32, 138, 0, 114,
--       42, 178, 0, 144]
--
scanr'Seg :: forall sh e i. (Shape sh, Slice sh, Elt e, Integral i, Bits i, FromIntegral i Int) => (Exp e -> Exp e -> Exp e) -> Exp e -> Acc (Array (sh :. Int) e) -> Acc (Segments i) -> Acc (Array (sh :. Int) e, Array (sh :. Int) e) -- | Segmented version of prescanr. prescanrSeg :: (Shape sh, Slice sh, Elt e, Integral i, Bits i, FromIntegral i Int) => (Exp e -> Exp e -> Exp e) -> Exp e -> Acc (Array (sh :. Int) e) -> Acc (Segments i) -> Acc (Array (sh :. Int) e) -- | Segmented version of postscanr. postscanrSeg :: (Shape sh, Slice sh, Elt e, Integral i, Bits i, FromIntegral i Int) => (Exp e -> Exp e -> Exp e) -> Exp e -> Acc (Array (sh :. Int) e) -> Acc (Segments i) -> Acc (Array (sh :. Int) e) -- | Map a stencil over an array. In contrast to map, the domain of -- a stencil function is an entire neighbourhood of each array -- element. Neighbourhoods are sub-arrays centred around a focal point. -- They are not necessarily rectangular, but they are symmetric and have -- an extent of at least three along each axis. Due to the symmetry -- requirement the extent is necessarily odd. The focal point is the -- array position that is determined by the stencil. -- -- For those array positions where the neighbourhood extends past the -- boundaries of the source array, a boundary condition determines the -- contents of the out-of-bounds neighbourhood positions. -- -- Stencil neighbourhoods are specified via nested tuples, where the -- nesting depth is equal to the dimensionality of the array. For -- example, a 3x1 stencil for a one-dimensional array: -- -- 
--   s31 :: Stencil3 a -> Exp a
--   s31 (l,c,r) = ...
--
-- -- ...where c is the focal point of the stencil, and l -- and r represent the elements to the left and right of the -- focal point, respectively. Similarly, a 3x3 stencil for a -- two-dimensional array: -- -- 
--   s33 :: Stencil3x3 a -> Exp a
--   s33 ((_,t,_)
--       ,(l,c,r)
--       ,(_,b,_)) = ...
--
-- -- ...where c is again the focal point and t, -- b, l and r are the elements to the top, -- bottom, left, and right of the focal point, respectively (the diagonal -- elements have been elided). -- -- For example, the following computes a 5x5 Gaussian blur as a -- separable 2-pass operation. -- -- 
--   type Stencil5x1 a = (Stencil3 a, Stencil5 a, Stencil3 a)
--   type Stencil1x5 a = (Stencil3 a, Stencil3 a, Stencil3 a, Stencil3 a, Stencil3 a)
--   
--   convolve5x1 :: Num a => [Exp a] -> Stencil5x1 a -> Exp a
--   convolve5x1 kernel (_, (a,b,c,d,e), _)
--     = Prelude.sum $ Prelude.zipWith (*) kernel [a,b,c,d,e]
--   
--   convolve1x5 :: Num a => [Exp a] -> Stencil1x5 a -> Exp a
--   convolve1x5 kernel ((_,a,_), (_,b,_), (_,c,_), (_,d,_), (_,e,_))
--     = Prelude.sum $ Prelude.zipWith (*) kernel [a,b,c,d,e]
--   
--   gaussian = [0.06136,0.24477,0.38774,0.24477,0.06136]
--   
--   blur :: Num a => Acc (Matrix a) -> Acc (Matrix a)
--   blur = stencil (convolve5x1 gaussian) clamp
--        . stencil (convolve1x5 gaussian) clamp
--
-- -- -- -- Since accelerate-1.3.0.0, we allow the source array to fuse into the -- stencil operation. However, since a stencil computation (typically) -- requires multiple values from the source array, this means that the -- work of the fused operation will be duplicated for each element in the -- stencil pattern. -- -- For example, suppose we write: -- -- 
--   blur . map f
--
-- -- The operation f will be fused into each element of the first -- Gaussian blur kernel, resulting in a stencil equivalent to: -- -- 
--   f_and_convolve1x5 :: Num a => (Exp a -> Exp b) -> [Exp b] -> Stencil1x5 a -> Exp b
--   f_and_convolve1x5 f kernel ((_,a,_), (_,b,_), (_,c,_), (_,d,_), (_,e,_))
--     = Prelude.sum $ Prelude.zipWith (*) kernel [f a, f b, f c, f d, f e]
--
-- -- This duplication is often beneficial, however you may choose to -- instead force the array to be evaluated first, preventing fusion, -- using the compute operation. Benchmarking should reveal which -- approach is best for your application. stencil :: forall sh stencil a b. (Stencil sh a stencil, Elt b) => (stencil -> Exp b) -> Boundary (Array sh a) -> Acc (Array sh a) -> Acc (Array sh b) -- | Map a binary stencil of an array. The extent of the resulting array is -- the intersection of the extents of the two source arrays. This is the -- stencil equivalent of zipWith. stencil2 :: forall sh stencil1 stencil2 a b c. (Stencil sh a stencil1, Stencil sh b stencil2, Elt c) => (stencil1 -> stencil2 -> Exp c) -> Boundary (Array sh a) -> Acc (Array sh a) -> Boundary (Array sh b) -> Acc (Array sh b) -> Acc (Array sh c) class Stencil sh e stencil -- | Boundary condition specification for stencil operations data Boundary t -- | Boundary condition where elements of the stencil which would be -- out-of-bounds are instead clamped to the edges of the array. -- -- In the following 3x3 stencil, the out-of-bounds element b -- will instead return the value at position c: -- -- 
--    +------------+
--    |a           |
--   b|cd          |
--    |e           |
--    +------------+
--
clamp :: Boundary (Array sh e) -- | Stencil boundary condition where coordinates beyond the array extent -- are instead mirrored -- -- In the following 5x3 stencil, the out-of-bounds element c -- will instead return the value at position d, and similarly -- the element at b will return the value at e: -- -- 
--     +------------+
--     |a           |
--   bc|def         |
--     |g           |
--     +------------+
--
mirror :: Boundary (Array sh e) -- | Stencil boundary condition where coordinates beyond the array extent -- instead wrap around the array (circular boundary conditions). -- -- In the following 3x3 stencil, the out of bounds elements will be read -- as in the pattern on the right. -- -- 
--   a bc
--    +------------+      +------------+
--   d|ef          |      |ef         d|
--   g|hi          |  ->  |hi         g|
--    |            |      |bc         a|
--    +------------+      +------------+
--
wrap :: Boundary (Array sh e) -- | Stencil boundary condition where the given function is applied to any -- outlying coordinates. -- -- The function is passed the out-of-bounds index, so you can use it to -- specify different boundary conditions at each side. For example, the -- following would clamp out-of-bounds elements in the y-direction to -- zero, while having circular boundary conditions in the x-direction. -- -- 
--   ring :: Acc (Matrix Float) -> Acc (Matrix Float)
--   ring xs = stencil f boundary xs
--     where
--       boundary :: Boundary (Matrix Float)
--       boundary = function $ \(unlift -> Z :. y :. x) ->
--         if y < 0 || y >= height
--           then 0
--           else if x < 0
--                  then xs ! index2 y (width+x)
--                  else xs ! index2 y (x-width)
--   
--       f :: Stencil3x3 Float -> Exp Float
--       f = ...
--   
--       Z :. height :. width = unlift (shape xs)
--
function :: forall sh e. (Shape sh, Elt e) => (Exp sh -> Exp e) -> Boundary (Array sh e) type Stencil3 a = (Exp a, Exp a, Exp a) type Stencil5 a = (Exp a, Exp a, Exp a, Exp a, Exp a) type Stencil7 a = (Exp a, Exp a, Exp a, Exp a, Exp a, Exp a, Exp a) type Stencil9 a = (Exp a, Exp a, Exp a, Exp a, Exp a, Exp a, Exp a, Exp a, Exp a) type Stencil3x3 a = (Stencil3 a, Stencil3 a, Stencil3 a) type Stencil5x3 a = (Stencil5 a, Stencil5 a, Stencil5 a) type Stencil3x5 a = (Stencil3 a, Stencil3 a, Stencil3 a, Stencil3 a, Stencil3 a) type Stencil5x5 a = (Stencil5 a, Stencil5 a, Stencil5 a, Stencil5 a, Stencil5 a) type Stencil3x3x3 a = (Stencil3x3 a, Stencil3x3 a, Stencil3x3 a) type Stencil5x3x3 a = (Stencil5x3 a, Stencil5x3 a, Stencil5x3 a) type Stencil3x5x3 a = (Stencil3x5 a, Stencil3x5 a, Stencil3x5 a) type Stencil3x3x5 a = (Stencil3x3 a, Stencil3x3 a, Stencil3x3 a, Stencil3x3 a, Stencil3x3 a) type Stencil5x5x3 a = (Stencil5x5 a, Stencil5x5 a, Stencil5x5 a) type Stencil5x3x5 a = (Stencil5x3 a, Stencil5x3 a, Stencil5x3 a, Stencil5x3 a, Stencil5x3 a) type Stencil3x5x5 a = (Stencil3x5 a, Stencil3x5 a, Stencil3x5 a, Stencil3x5 a, Stencil3x5 a) type Stencil5x5x5 a = (Stencil5x5 a, Stencil5x5 a, Stencil5x5 a, Stencil5x5 a, Stencil5x5 a) -- | The type Exp represents embedded scalar expressions. The -- collective operations of Accelerate Acc consist of many scalar -- expressions executed in data-parallel. -- -- Note that scalar expressions can not initiate new collective -- operations: doing so introduces nested data parallelism, which -- is difficult to execute efficiently on constrained hardware such as -- GPUs, and is thus currently unsupported. data Exp t data Vec (n :: Nat) a type VecElt a = (Elt a, Prim a, IsSingle a, EltR a ~ a) -- | The Eq class defines equality == and inequality -- /= for scalar Accelerate expressions. -- -- For convenience, we include Elt as a superclass. class Elt a => Eq a (==) :: Eq a => Exp a -> Exp a -> Exp Bool (/=) :: Eq a => Exp a -> Exp a -> Exp Bool infix 4 == infix 4 /= -- | The Ord class for totally ordered datatypes class Eq a => Ord a (<) :: Ord a => Exp a -> Exp a -> Exp Bool (>) :: Ord a => Exp a -> Exp a -> Exp Bool (<=) :: Ord a => Exp a -> Exp a -> Exp Bool (>=) :: Ord a => Exp a -> Exp a -> Exp Bool min :: Ord a => Exp a -> Exp a -> Exp a max :: Ord a => Exp a -> Exp a -> Exp a compare :: Ord a => Exp a -> Exp a -> Exp Ordering infix 4 >= infix 4 > infix 4 <= infix 4 < data Ordering LT :: Ordering EQ :: Ordering GT :: Ordering pattern LT_ :: HasCallStack => Exp Ordering pattern EQ_ :: HasCallStack => Exp Ordering pattern GT_ :: HasCallStack => Exp Ordering -- | Operations over sequentially ordered types type Enum a = Enum (Exp a) -- | the successor of a value. For numeric types, succ adds 1. succ :: Enum a => a -> a -- | the predecessor of a value. For numeric types, pred subtracts -- 1. pred :: Enum a => a -> a -- | Name the upper and lower limits of a type. Types which are not totally -- ordered may still have upper and lower bounds. type Bounded a = (Elt a, Bounded (Exp a)) minBound :: Bounded a => a maxBound :: Bounded a => a -- | Conversion from an Integer. -- -- An integer literal represents the application of the function -- fromInteger to the appropriate value of type -- Integer. We export this specialised version where the return -- type is fixed to an Exp term in order to improve type checking -- in Accelerate modules when RebindableSyntax is enabled. -- -- fromInteger :: Num a => Integer -> Exp a fromInteger = -- P.fromInteger -- -- Basic numeric class type Num a = (Elt a, Num (Exp a)) (+) :: Num a => a -> a -> a infixl 6 + (-) :: Num a => a -> a -> a infixl 6 - (*) :: Num a => a -> a -> a infixl 7 * -- | Unary negation. negate :: Num a => a -> a -- | Absolute value. abs :: Num a => a -> a -- | Sign of a number. The functions abs and signum should -- satisfy the law: -- -- 
--   abs x * signum x == x
--
-- -- For real numbers, the signum is either -1 (negative), -- 0 (zero) or 1 (positive). signum :: Num a => a -> a -- | Conversion from an Integer. An integer literal represents the -- application of the function fromInteger to the appropriate -- value of type Integer, so such literals have type -- (Num a) => a. fromInteger :: Num a => Integer -> a -- | Integral numbers, supporting integral division type Integral a = (Enum a, Ord a, Num a, Integral (Exp a)) -- | integer division truncated toward zero quot :: Integral a => a -> a -> a infixl 7 `quot` -- | integer remainder, satisfying -- -- 
--   (x `quot` y)*y + (x `rem` y) == x
--
rem :: Integral a => a -> a -> a infixl 7 `rem` -- | integer division truncated toward negative infinity div :: Integral a => a -> a -> a infixl 7 `div` -- | integer modulus, satisfying -- -- 
--   (x `div` y)*y + (x `mod` y) == x
--
mod :: Integral a => a -> a -> a infixl 7 `mod` -- | simultaneous quot and rem quotRem :: Integral a => a -> a -> (a, a) -- | simultaneous div and mod divMod :: Integral a => a -> a -> (a, a) -- | Numbers which can be expressed as the quotient of two integers. -- -- Accelerate does not have an arbitrary precision Integer type, however -- fixed-length large integers are provide by the -- accelerate-bignum package. class (Num a, Ord a) => Rational a -- | Convert a number to the quotient of two integers toRational :: (Rational a, FromIntegral Int64 b, Integral b) => Exp a -> Exp (Ratio b) -- | Conversion from a Rational. -- -- A floating point literal representations the application of the -- function fromRational to a value of type Rational. -- We export this specialised version where the return type is fixed to -- an Exp term in order to improve type checking in Accelerate -- modules when RebindableSyntax is enabled. -- -- fromRational :: Fractional a => Rational -> Exp a fromRational = -- P.fromRational -- -- Fractional numbers, supporting real division type Fractional a = (Num a, Fractional (Exp a)) -- | Fractional division. (/) :: Fractional a => a -> a -> a infixl 7 / -- | Reciprocal fraction. recip :: Fractional a => a -> a -- | Conversion from a Rational (that is Ratio -- Integer). A floating literal stands for an application of -- fromRational to a value of type Rational, so such -- literals have type (Fractional a) => a. fromRational :: Fractional a => Rational -> a -- | Trigonometric and hyperbolic functions and related functions type Floating a = (Fractional a, Floating (Exp a)) pi :: Floating a => a sin :: Floating a => a -> a cos :: Floating a => a -> a tan :: Floating a => a -> a asin :: Floating a => a -> a acos :: Floating a => a -> a atan :: Floating a => a -> a sinh :: Floating a => a -> a cosh :: Floating a => a -> a tanh :: Floating a => a -> a asinh :: Floating a => a -> a acosh :: Floating a => a -> a atanh :: Floating a => a -> a exp :: Floating a => a -> a sqrt :: Floating a => a -> a log :: Floating a => a -> a (**) :: Floating a => a -> a -> a infixr 8 ** logBase :: Floating a => a -> a -> a -- | Extracting components of fractions. class (Ord a, Fractional a) => RealFrac a -- | The function properFraction takes a real fractional number -- x and returns a pair (n,f) such that x = -- n+f, and: -- -- -- -- The default definitions of the ceiling, floor, -- truncate and round functions are in terms of -- properFraction. properFraction :: (RealFrac a, Integral b, FromIntegral Int64 b) => Exp a -> (Exp b, Exp a) -- | truncate x returns the integer nearest x between -- zero and x truncate :: (RealFrac a, Integral b, FromIntegral Int64 b) => Exp a -> Exp b -- | round x returns the nearest integer to x; the -- even integer if x is equidistant between two integers round :: (RealFrac a, Integral b, FromIntegral Int64 b) => Exp a -> Exp b -- | ceiling x returns the least integer not less than -- x ceiling :: (RealFrac a, Integral b, FromIntegral Int64 b) => Exp a -> Exp b -- | floor x returns the greatest integer not greater than -- x floor :: (RealFrac a, Integral b, FromIntegral Int64 b) => Exp a -> Exp b -- | Generalisation of div to any instance of RealFrac div' :: (RealFrac a, FromIntegral Int64 b, Integral b) => Exp a -> Exp a -> Exp b -- | Generalisation of mod to any instance of RealFrac mod' :: (Floating a, RealFrac a, ToFloating Int64 a) => Exp a -> Exp a -> Exp a -- | Generalisation of divMod to any instance of RealFrac divMod' :: (Floating a, RealFrac a, Integral b, FromIntegral Int64 b, ToFloating b a) => Exp a -> Exp a -> (Exp b, Exp a) -- | Efficient, machine-independent access to the components of a -- floating-point number class (RealFrac a, Floating a) => RealFloat a -- | The radix of the representation (often 2) (constant) floatRadix :: RealFloat a => Exp a -> Exp Int64 -- | The radix of the representation (often 2) (constant) floatRadix :: (RealFloat a, RealFloat a) => Exp a -> Exp Int64 -- | The number of digits of floatRadix in the significand -- (constant) floatDigits :: RealFloat a => Exp a -> Exp Int -- | The number of digits of floatRadix in the significand -- (constant) floatDigits :: (RealFloat a, RealFloat a) => Exp a -> Exp Int -- | The lowest and highest values the exponent may assume (constant) floatRange :: RealFloat a => Exp a -> (Exp Int, Exp Int) -- | The lowest and highest values the exponent may assume (constant) floatRange :: (RealFloat a, RealFloat a) => Exp a -> (Exp Int, Exp Int) -- | Return the significand and an appropriately scaled exponent. If -- (m,n) = decodeFloat x then x = m*b^^n, where -- b is the floating-point radix (floatRadix). -- Furthermore, either m and n are both zero, or -- b^(d-1) <= abs m < b^d, where d = -- floatDigits x. decodeFloat :: RealFloat a => Exp a -> (Exp Int64, Exp Int) -- | Inverse of decodeFloat encodeFloat :: RealFloat a => Exp Int64 -> Exp Int -> Exp a -- | Inverse of decodeFloat encodeFloat :: (RealFloat a, FromIntegral Int a, FromIntegral Int64 a) => Exp Int64 -> Exp Int -> Exp a -- | Corresponds to the second component of decodeFloat exponent :: RealFloat a => Exp a -> Exp Int -- | Corresponds to the first component of decodeFloat significand :: RealFloat a => Exp a -> Exp a -- | Multiply a floating point number by an integer power of the radix scaleFloat :: RealFloat a => Exp Int -> Exp a -> Exp a -- | True if the argument is an IEEE "not-a-number" (NaN) value isNaN :: RealFloat a => Exp a -> Exp Bool -- | True if the argument is an IEEE infinity or negative-infinity isInfinite :: RealFloat a => Exp a -> Exp Bool -- | True if the argument is too small to be represented in -- normalized format isDenormalized :: RealFloat a => Exp a -> Exp Bool -- | True if the argument is an IEEE negative zero isNegativeZero :: RealFloat a => Exp a -> Exp Bool -- | True if the argument is an IEEE floating point number isIEEE :: RealFloat a => Exp a -> Exp Bool -- | True if the argument is an IEEE floating point number isIEEE :: (RealFloat a, RealFloat a) => Exp a -> Exp Bool -- | A version of arctangent taking two real floating-point arguments. For -- real floating x and y, atan2 y x -- computes the angle (from the positive x-axis) of the vector from the -- origin to the point (x,y). atan2 y x returns -- a value in the range [-pi, pi]. atan2 :: RealFloat a => Exp a -> Exp a -> Exp a -- | Accelerate lacks a most-general lossless Integer type, which -- the standard fromIntegral function uses as an intermediate -- value when coercing from integral types. Instead, we use this class to -- capture a direct coercion between two types. class FromIntegral a b -- | General coercion from integral types fromIntegral :: (FromIntegral a b, Integral a) => Exp a -> Exp b -- | Accelerate lacks an arbitrary-precision Rational type, which -- the standard realToFrac uses as an intermediate value when -- coercing to floating-point types. Instead, we use this class to -- capture a direct coercion between two types. class ToFloating a b -- | General coercion to floating types toFloating :: (ToFloating a b, Num a, Floating b) => Exp a -> Exp b -- | The class of types e which can be lifted into c. class Lift c e where { -- | An associated-type (i.e. a type-level function) that strips all -- instances of surface type constructors c from the input type -- e. -- -- For example, the tuple types (Exp Int, Int) and (Int, Exp -- Int) have the same "Plain" representation. That is, the following -- type equality holds: -- -- 
    --   Plain (Exp Int, Int) ~ (Int,Int) ~ Plain (Int, Exp Int)
    --
type family Plain e; } -- | Lift the given value into a surface type c --- either -- Exp for scalar expressions or Acc for array -- computations. The value may already contain subexpressions in -- c. lift :: Lift c e => e -> c (Plain e) -- | A limited subset of types which can be lifted, can also be unlifted. class Lift c e => Unlift c e -- | Unlift the outermost constructor through the surface type. This is -- only possible if the constructor is fully determined by its type - -- i.e., it is a singleton. unlift :: Unlift c e => c (Plain e) -> e -- | Lift a unary function into Exp. lift1 :: (Unlift Exp a, Lift Exp b) => (a -> b) -> Exp (Plain a) -> Exp (Plain b) -- | Lift a binary function into Exp. lift2 :: (Unlift Exp a, Unlift Exp b, Lift Exp c) => (a -> b -> c) -> Exp (Plain a) -> Exp (Plain b) -> Exp (Plain c) -- | Lift a ternary function into Exp. lift3 :: (Unlift Exp a, Unlift Exp b, Unlift Exp c, Lift Exp d) => (a -> b -> c -> d) -> Exp (Plain a) -> Exp (Plain b) -> Exp (Plain c) -> Exp (Plain d) -- | Lift a unary function to a computation over rank-1 indices. ilift1 :: (Exp Int -> Exp Int) -> Exp DIM1 -> Exp DIM1 -- | Lift a binary function to a computation over rank-1 indices. ilift2 :: (Exp Int -> Exp Int -> Exp Int) -> Exp DIM1 -> Exp DIM1 -> Exp DIM1 -- | Lift a ternary function to a computation over rank-1 indices. ilift3 :: (Exp Int -> Exp Int -> Exp Int -> Exp Int) -> Exp DIM1 -> Exp DIM1 -> Exp DIM1 -> Exp DIM1 -- | A pattern synonym for working with (product) data types. You can -- declare your own pattern synonyms based off of this. pattern Pattern :: forall b a context. IsPattern context a b => b -> context a pattern T2 :: IsPattern con (x0, x1) (con x0, con x1) => con x0 -> con x1 -> con (x0, x1) pattern T3 :: IsPattern con (x0, x1, x2) (con x0, con x1, con x2) => con x0 -> con x1 -> con x2 -> con (x0, x1, x2) pattern T4 :: IsPattern con (x0, x1, x2, x3) (con x0, con x1, con x2, con x3) => con x0 -> con x1 -> con x2 -> con x3 -> con (x0, x1, x2, x3) pattern T5 :: IsPattern con (x0, x1, x2, x3, x4) (con x0, con x1, con x2, con x3, con x4) => con x0 -> con x1 -> con x2 -> con x3 -> con x4 -> con (x0, x1, x2, x3, x4) pattern T6 :: IsPattern con (x0, x1, x2, x3, x4, x5) (con x0, con x1, con x2, con x3, con x4, con x5) => con x0 -> con x1 -> con x2 -> con x3 -> con x4 -> con x5 -> con (x0, x1, x2, x3, x4, x5) pattern T7 :: IsPattern con (x0, x1, x2, x3, x4, x5, x6) (con x0, con x1, con x2, con x3, con x4, con x5, con x6) => con x0 -> con x1 -> con x2 -> con x3 -> con x4 -> con x5 -> con x6 -> con (x0, x1, x2, x3, x4, x5, x6) pattern T8 :: IsPattern con (x0, x1, x2, x3, x4, x5, x6, x7) (con x0, con x1, con x2, con x3, con x4, con x5, con x6, con x7) => con x0 -> con x1 -> con x2 -> con x3 -> con x4 -> con x5 -> con x6 -> con x7 -> con (x0, x1, x2, x3, x4, x5, x6, x7) pattern T9 :: IsPattern con (x0, x1, x2, x3, x4, x5, x6, x7, x8) (con x0, con x1, con x2, con x3, con x4, con x5, con x6, con x7, con x8) => con x0 -> con x1 -> con x2 -> con x3 -> con x4 -> con x5 -> con x6 -> con x7 -> con x8 -> con (x0, x1, x2, x3, x4, x5, x6, x7, x8) pattern T10 :: IsPattern con (x0, x1, x2, x3, x4, x5, x6, x7, x8, x9) (con x0, con x1, con x2, con x3, con x4, con x5, con x6, con x7, con x8, con x9) => con x0 -> con x1 -> con x2 -> con x3 -> con x4 -> con x5 -> con x6 -> con x7 -> con x8 -> con x9 -> con (x0, x1, x2, x3, x4, x5, x6, x7, x8, x9) pattern T11 :: IsPattern con (x0, x1, x2, x3, x4, x5, x6, x7, x8, x9, x10) (con x0, con x1, con x2, con x3, con x4, con x5, con x6, con x7, con x8, con x9, con x10) => con x0 -> con x1 -> con x2 -> con x3 -> con x4 -> con x5 -> con x6 -> con x7 -> con x8 -> con x9 -> con x10 -> con (x0, x1, x2, x3, x4, x5, x6, x7, x8, x9, x10) pattern T12 :: IsPattern con (x0, x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11) (con x0, con x1, con x2, con x3, con x4, con x5, con x6, con x7, con x8, con x9, con x10, con x11) => con x0 -> con x1 -> con x2 -> con x3 -> con x4 -> con x5 -> con x6 -> con x7 -> con x8 -> con x9 -> con x10 -> con x11 -> con (x0, x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11) pattern T13 :: IsPattern con (x0, x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12) (con x0, con x1, con x2, con x3, con x4, con x5, con x6, con x7, con x8, con x9, con x10, con x11, con x12) => con x0 -> con x1 -> con x2 -> con x3 -> con x4 -> con x5 -> con x6 -> con x7 -> con x8 -> con x9 -> con x10 -> con x11 -> con x12 -> con (x0, x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12) pattern T14 :: IsPattern con (x0, x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13) (con x0, con x1, con x2, con x3, con x4, con x5, con x6, con x7, con x8, con x9, con x10, con x11, con x12, con x13) => con x0 -> con x1 -> con x2 -> con x3 -> con x4 -> con x5 -> con x6 -> con x7 -> con x8 -> con x9 -> con x10 -> con x11 -> con x12 -> con x13 -> con (x0, x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13) pattern T15 :: IsPattern con (x0, x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14) (con x0, con x1, con x2, con x3, con x4, con x5, con x6, con x7, con x8, con x9, con x10, con x11, con x12, con x13, con x14) => con x0 -> con x1 -> con x2 -> con x3 -> con x4 -> con x5 -> con x6 -> con x7 -> con x8 -> con x9 -> con x10 -> con x11 -> con x12 -> con x13 -> con x14 -> con (x0, x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14) pattern T16 :: IsPattern con (x0, x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15) (con x0, con x1, con x2, con x3, con x4, con x5, con x6, con x7, con x8, con x9, con x10, con x11, con x12, con x13, con x14, con x15) => con x0 -> con x1 -> con x2 -> con x3 -> con x4 -> con x5 -> con x6 -> con x7 -> con x8 -> con x9 -> con x10 -> con x11 -> con x12 -> con x13 -> con x14 -> con x15 -> con (x0, x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15) -- | Pattern synonyms for indices, which may be more convenient to use than -- lift and unlift. pattern Z_ :: Exp DIM0 pattern Ix :: (Elt a, Elt b) => Exp a -> Exp b -> Exp (a :. b) infixl 3 `Ix` pattern (::.) :: (Elt a, Elt b) => Exp a -> Exp b -> Exp (a :. b) infixl 3 ::. pattern I0 :: () => Exp Z pattern I1 :: Elt x0 => Exp x0 -> Exp ((:.) Z x0) pattern I2 :: (Elt x0, Elt x1) => Exp x0 -> Exp x1 -> Exp ((:.) ((:.) Z x0) x1) pattern I3 :: (Elt x0, Elt x1, Elt x2) => Exp x0 -> Exp x1 -> Exp x2 -> Exp ((:.) ((:.) ((:.) Z x0) x1) x2) pattern I4 :: (Elt x0, Elt x1, Elt x2, Elt x3) => Exp x0 -> Exp x1 -> Exp x2 -> Exp x3 -> Exp ((:.) ((:.) ((:.) ((:.) Z x0) x1) x2) x3) pattern I5 :: (Elt x0, Elt x1, Elt x2, Elt x3, Elt x4) => Exp x0 -> Exp x1 -> Exp x2 -> Exp x3 -> Exp x4 -> Exp ((:.) ((:.) ((:.) ((:.) ((:.) Z x0) x1) x2) x3) x4) pattern I6 :: (Elt x0, Elt x1, Elt x2, Elt x3, Elt x4, Elt x5) => Exp x0 -> Exp x1 -> Exp x2 -> Exp x3 -> Exp x4 -> Exp x5 -> Exp ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) Z x0) x1) x2) x3) x4) x5) pattern I7 :: (Elt x0, Elt x1, Elt x2, Elt x3, Elt x4, Elt x5, Elt x6) => Exp x0 -> Exp x1 -> Exp x2 -> Exp x3 -> Exp x4 -> Exp x5 -> Exp x6 -> Exp ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) Z x0) x1) x2) x3) x4) x5) x6) pattern I8 :: (Elt x0, Elt x1, Elt x2, Elt x3, Elt x4, Elt x5, Elt x6, Elt x7) => Exp x0 -> Exp x1 -> Exp x2 -> Exp x3 -> Exp x4 -> Exp x5 -> Exp x6 -> Exp x7 -> Exp ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) Z x0) x1) x2) x3) x4) x5) x6) x7) pattern I9 :: (Elt x0, Elt x1, Elt x2, Elt x3, Elt x4, Elt x5, Elt x6, Elt x7, Elt x8) => Exp x0 -> Exp x1 -> Exp x2 -> Exp x3 -> Exp x4 -> Exp x5 -> Exp x6 -> Exp x7 -> Exp x8 -> Exp ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) ((:.) Z x0) x1) x2) x3) x4) x5) x6) x7) x8) pattern Vec2 :: Prim a => a -> a -> Vec2 a pattern V2 :: IsVector con vec (con x0, con x1) => con x0 -> con x1 -> con vec pattern Vec3 :: Prim a => a -> a -> a -> Vec3 a pattern V3 :: IsVector con vec (con x0, con x1, con x2) => con x0 -> con x1 -> con x2 -> con vec pattern Vec4 :: Prim a => a -> a -> a -> a -> Vec4 a pattern V4 :: IsVector con vec (con x0, con x1, con x2, con x3) => con x0 -> con x1 -> con x2 -> con x3 -> con vec pattern Vec8 :: Prim a => a -> a -> a -> a -> a -> a -> a -> a -> Vec8 a pattern V8 :: IsVector con vec (con x0, con x1, con x2, con x3, con x4, con x5, con x6, con x7) => con x0 -> con x1 -> con x2 -> con x3 -> con x4 -> con x5 -> con x6 -> con x7 -> con vec pattern Vec16 :: Prim a => a -> a -> a -> a -> a -> a -> a -> a -> a -> a -> a -> a -> a -> a -> a -> a -> Vec16 a -- | Specialised pattern synonyms for tuples, which may be more convenient -- to use than lift and unlift. For example, to construct a -- pair: -- -- 
--   let a = 4        :: Exp Int
--   let b = 2        :: Exp Float
--   let c = T2 a b   -- :: Exp (Int, Float); equivalent to 'lift (a,b)'
--
-- -- Similarly they can be used to destruct values: -- -- 
--   let T2 x y = c   -- x :: Exp Int, y :: Exp Float; equivalent to 'let (x,y) = unlift c'
--
-- -- These pattern synonyms can be used for both Exp and Acc -- terms. -- -- Similarly, we have patterns for constructing and destructing indices -- of a given dimensionality: -- -- 
--   let ix = Ix 2 3    -- :: Exp DIM2
--   let I2 y x = ix    -- y :: Exp Int, x :: Exp Int
--
pattern V16 :: IsVector con vec (con x0, con x1, con x2, con x3, con x4, con x5, con x6, con x7, con x8, con x9, con x10, con x11, con x12, con x13, con x14, con x15) => con x0 -> con x1 -> con x2 -> con x3 -> con x4 -> con x5 -> con x6 -> con x7 -> con x8 -> con x9 -> con x10 -> con x11 -> con x12 -> con x13 -> con x14 -> con x15 -> con vec -- | Generate pattern synonyms for the given simple (Haskell'98) sum or -- product data type. -- -- Constructor and record selectors are renamed to add a trailing -- underscore if it does not exist, or to remove it if it does. For infix -- constructors, the name is prepended with a colon :. For -- example: -- -- 
--   data Point = Point { xcoord_ :: Float, ycoord_ :: Float }
--     deriving (Generic, Elt)
--
-- -- Will create the pattern synonym: -- -- 
--   Point_ :: Exp Float -> Exp Float -> Exp Point
--
-- -- together with the selector functions -- -- 
--   xcoord :: Exp Point -> Exp Float
--   ycoord :: Exp Point -> Exp Float
--
mkPattern :: Name -> DecsQ -- | As mkPattern, but for a list of types mkPatterns :: [Name] -> DecsQ -- | Scalar expression inlet: make a Haskell value available for processing -- in an Accelerate scalar expression. -- -- Note that this embeds the value directly into the expression. -- Depending on the backend used to execute the computation, this might -- not always be desirable. For example, a backend that does external -- code generation may embed this constant directly into the generated -- code, which means new code will need to be generated and compiled -- every time the value changes. In such cases, consider instead lifting -- scalar values into (singleton) arrays so that they can be passed as an -- input to the computation and thus the value can change without the -- need to generate fresh code. constant :: forall e. (HasCallStack, Elt e) => e -> Exp e -- | Extract the first component of a scalar pair. fst :: (Elt a, Elt b) => Exp (a, b) -> Exp a -- | Extract the first component of an array pair. afst :: (Arrays a, Arrays b) => Acc (a, b) -> Acc a -- | Extract the second component of a scalar pair. snd :: (Elt a, Elt b) => Exp (a, b) -> Exp b -- | Extract the second component of an array pair asnd :: (Arrays a, Arrays b) => Acc (a, b) -> Acc b -- | Converts an uncurried function to a curried function. curry :: Lift f (f a, f b) => (f (Plain (f a), Plain (f b)) -> f c) -> f a -> f b -> f c -- | Converts a curried function to a function on pairs. uncurry :: Unlift f (f a, f b) => (f a -> f b -> f c) -> f (Plain (f a), Plain (f b)) -> f c -- | An infix version of cond. If the predicate evaluates to -- True, the first component of the tuple is returned, else the -- second. -- -- Enabling the RebindableSyntax extension will allow you to use -- the standard if-then-else syntax instead. (?) :: Elt t => Exp Bool -> (Exp t, Exp t) -> Exp t infix 0 ? -- | The match operation is the core operation which enables -- embedded pattern matching. It is applied to an n-ary scalar function, -- and generates the necessary case-statements in the embedded code for -- each argument. For example, given the function: -- -- 
--   example1 :: Exp (Maybe Bool) -> Exp Int
--   example1 Nothing_ = 0
--   example1 (Just_ False_) = 1
--   example1 (Just_ True_) = 2
--
-- -- In order to use this function it must be applied to the match -- operator: -- -- 
--   match example1
--
-- -- Using the infix-flip operator (&), we can also write case -- statements inline. For example, instead of this: -- -- 
--   example2 x = case f x of
--     Nothing_ -> ...      -- error: embedded pattern synonym...
--     Just_ y  -> ...      -- ...used outside of 'match' context
--
-- -- This can be written instead as: -- -- 
--   example3 x = f x & match \case
--     Nothing_ -> ...
--     Just_ y  -> ...
--
-- -- And utilising the LambdaCase and BlockArguments -- syntactic extensions. -- -- The Template Haskell splice mkPattern (or mkPatterns) -- can be used to generate the pattern synonyms for a given Haskell'98 -- sum or product data type. For example: -- -- 
--   data Option a = None | Some a
--     deriving (Generic, Elt)
--   
--   mkPattern ''Option
--
-- -- Which can then be used such as: -- -- 
--   isNone :: Elt a => Exp (Option a) -> Exp Bool
--   isNone = match \case
--     None_   -> True_
--     Some_{} -> False_
--
match :: Matching f => f -> f -- | A scalar-level if-then-else construct. -- -- Enabling the RebindableSyntax extension will allow you to use -- the standard if-then-else syntax instead. cond :: Elt t => Exp Bool -> Exp t -> Exp t -> Exp t -- | While construct. Continue to apply the given function, starting with -- the initial value, until the test function evaluates to False. while :: forall e. Elt e => (Exp e -> Exp Bool) -> (Exp e -> Exp e) -> Exp e -> Exp e -- | Repeatedly apply a function a fixed number of times iterate :: Elt a => Exp Int -> (Exp a -> Exp a) -> Exp a -> Exp a -- | Reduce along an innermost slice of an array sequentially, by -- applying a binary operator to a starting value and the array from left -- to right. sfoldl :: (Shape sh, Elt a, Elt b) => (Exp a -> Exp b -> Exp a) -> Exp a -> Exp sh -> Acc (Array (sh :. Int) b) -> Exp a -- | Conjunction: True if both arguments are true. This is a short-circuit -- operator, so the second argument will be evaluated only if the first -- is true. (&&) :: Exp Bool -> Exp Bool -> Exp Bool infixr 3 && -- | Disjunction: True if either argument is true. This is a short-circuit -- operator, so the second argument will be evaluated only if the first -- is false. (||) :: Exp Bool -> Exp Bool -> Exp Bool infixr 2 || -- | Logical negation not :: Exp Bool -> Exp Bool -- | subtract is the same as flip (-). subtract :: Num a => Exp a -> Exp a -> Exp a -- | Determine if a number is even even :: Integral a => Exp a -> Exp Bool -- | Determine if a number is odd odd :: Integral a => Exp a -> Exp Bool -- | gcd x y is the non-negative factor of both x -- and y of which every common factor of both x and -- y is also a factor; for example: -- -- 
--   gcd 4 2 = 2
--   gcd (-4) 6 = 2
--   gcd 0 4 = 4
--   gcd 0 0 = 0
--
-- -- That is, the common divisor that is "greatest" in the divisibility -- preordering. gcd :: Integral a => Exp a -> Exp a -> Exp a -- | lcm x y is the smallest positive integer that both -- x and y divide. lcm :: Integral a => Exp a -> Exp a -> Exp a -- | Raise a number to a non-negative integral power (^) :: forall a b. (Num a, Integral b) => Exp a -> Exp b -> Exp a infixr 8 ^ -- | Raise a number to an integral power (^^) :: (Fractional a, Integral b) => Exp a -> Exp b -> Exp a infixr 8 ^^ -- | The one index for a rank-0 array. index0 :: Exp Z -- | Turn an Int expression into a rank-1 indexing expression. index1 :: Elt i => Exp i -> Exp (Z :. i) -- | Turn a rank-1 indexing expression into an Int expression. unindex1 :: Elt i => Exp (Z :. i) -> Exp i -- | Creates a rank-2 index from two Exp Int`s index2 :: Elt i => Exp i -> Exp i -> Exp ((Z :. i) :. i) -- | Destructs a rank-2 index to an Exp tuple of two Int`s. unindex2 :: Elt i => Exp ((Z :. i) :. i) -> Exp (i, i) -- | Create a rank-3 index from three Exp Int`s index3 :: Elt i => Exp i -> Exp i -> Exp i -> Exp (((Z :. i) :. i) :. i) -- | Destruct a rank-3 index into an Exp tuple of Int`s unindex3 :: Elt i => Exp (((Z :. i) :. i) :. i) -> Exp (i, i, i) -- | Get the innermost dimension of a shape. -- -- The innermost dimension (right-most component of the shape) is the -- index of the array which varies most rapidly, and corresponds to -- elements of the array which are adjacent in memory. -- -- Another way to think of this is, for example when writing nested loops -- over an array in C, this index corresponds to the index iterated over -- by the innermost nested loop. indexHead :: (Elt sh, Elt a) => Exp (sh :. a) -> Exp a -- | Get all but the innermost element of a shape indexTail :: (Elt sh, Elt a) => Exp (sh :. a) -> Exp sh -- | Map a multi-dimensional index into a linear, row-major representation -- of an array. toIndex :: forall sh. Shape sh => Exp sh -> Exp sh -> Exp Int -- | Inverse of toIndex fromIndex :: forall sh. Shape sh => Exp sh -> Exp Int -> Exp sh -- | Intersection of two shapes intersect :: forall sh. Shape sh => Exp sh -> Exp sh -> Exp sh -- | Convert a character to an Int. ord :: Exp Char -> Exp Int -- | Convert an Int into a character. chr :: Exp Int -> Exp Char -- | Convert a Boolean value to an Int, where False turns -- into '0' and True into '1'. boolToInt :: Exp Bool -> Exp Int -- | Reinterpret a value as another type. The two representations must have -- the same bit size. bitcast :: (Elt a, Elt b, IsScalar (EltR a), IsScalar (EltR b), BitSizeEq (EltR a) (EltR b)) => Exp a -> Exp b -- | Call a foreign array function. -- -- The form the first argument takes is dependent on the backend being -- targeted. Note that the foreign function only has access to the input -- array(s) passed in as its argument. -- -- In case the operation is being executed on a backend which does not -- support this foreign implementation, the fallback implementation is -- used instead, which itself could be a foreign implementation for a -- (presumably) different backend, or an implementation in pure -- Accelerate. In this way, multiple foreign implementations can be -- supplied, and will be tested for suitability against the target -- backend in sequence. -- -- For an example see the accelerate-fft package. foreignAcc :: forall as bs asm. (Arrays as, Arrays bs, Foreign asm) => asm (ArraysR as -> ArraysR bs) -> (Acc as -> Acc bs) -> Acc as -> Acc bs -- | Call a foreign scalar expression. -- -- The form of the first argument is dependent on the backend being -- targeted. Note that the foreign function only has access to the input -- element(s) passed in as its first argument. -- -- As with foreignAcc, the fallback implementation itself may be a -- (sequence of) foreign implementation(s) for a different backend(s), or -- implemented purely in Accelerate. foreignExp :: forall x y asm. (Elt x, Elt y, Foreign asm) => asm (EltR x -> EltR y) -> (Exp x -> Exp y) -> Exp x -> Exp y -- | Rank of an array (as a plain Haskell value) arrayRank :: forall sh e. Shape sh => Array sh e -> Int -- | Shape of an array (as a plain Haskell value) arrayShape :: Shape sh => Array sh e -> sh -- | Total number of elements in an array (as a plain Haskell value) arraySize :: Shape sh => Array sh e -> Int -- | Change the shape of an array without altering its contents. The -- arraySize of the source and result arrays must be identical. arrayReshape :: (Shape sh, Shape sh') => sh -> Array sh' e -> Array sh e -- | Array indexing in plain Haskell code. indexArray :: (Shape sh, Elt e) => Array sh e -> sh -> e -- | Linear array indexing in plain Haskell code. linearIndexArray :: Elt e => Array sh e -> Int -> e -- | Create an array from its representation function, applied at each -- index of the array fromFunction :: (Shape sh, Elt e) => sh -> (sh -> e) -> Array sh e -- | Create an array using a monadic function applied at each index fromFunctionM :: forall sh e. (Shape sh, Elt e) => sh -> (sh -> IO e) -> IO (Array sh e) -- | Convert elements of a list into an Accelerate Array -- -- This will generate a new multidimensional Array of the -- specified shape and extent by consuming elements from the list and -- adding them to the array in row-major order. -- -- 
--   >>> fromList (Z:.10) [0..] :: Vector Int
--   Vector (Z :. 10) [0,1,2,3,4,5,6,7,8,9]
--
-- -- Note that we pull elements off the list lazily, so infinite lists are -- accepted: -- -- 
--   >>> fromList (Z:.5:.10) (repeat 0) :: Matrix Float
--   Matrix (Z :. 5 :. 10)
--     [ 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0,
--       0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0,
--       0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0,
--       0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0,
--       0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0]
--
-- -- You can also make use of the OverloadedLists extension to -- produce one-dimensional vectors from a finite list. -- -- 
--   >>> [0..9] :: Vector Int
--   Vector (Z :. 10) [0,1,2,3,4,5,6,7,8,9]
--
-- -- Note that this requires first traversing the list to determine its -- length, and then traversing it a second time to collect the elements -- into the array, thus forcing the spine of the list to be manifest on -- the heap. fromList :: forall sh e. (Shape sh, Elt e) => sh -> [e] -> Array sh e -- | Convert an accelerated Array to a list in row-major order toList :: forall sh e. (Shape sh, Elt e) => Array sh e -> [e] -- | Function composition. (.) :: (b -> c) -> (a -> b) -> a -> c infixr 9 . -- | Application operator. This operator is redundant, since ordinary -- application (f x) means the same as (f $ x). -- However, $ has low, right-associative binding precedence, so it -- sometimes allows parentheses to be omitted; for example: -- -- 
--   f $ g $ h x  =  f (g (h x))
--
-- -- It is also useful in higher-order situations, such as map -- ($ 0) xs, or zipWith ($) fs xs. -- -- Note that ($) is levity-polymorphic in its result -- type, so that foo $ True where foo :: Bool -> -- Int# is well-typed. ($) :: forall (r :: RuntimeRep) a (b :: TYPE r). (a -> b) -> a -> b infixr 0 $ -- | & is a reverse application operator. This provides -- notational convenience. Its precedence is one higher than that of the -- forward application operator $, which allows & to be -- nested in $. -- -- 
--   >>> 5 & (+1) & show
--   "6"
--
(&) :: a -> (a -> b) -> b infixl 1 & -- | error stops execution and displays an error message. error :: forall (r :: RuntimeRep) (a :: TYPE r). HasCallStack => [Char] -> a -- | A special case of error. It is expected that compilers will -- recognize this and insert error messages which are more appropriate to -- the context in which undefined appears. undefined :: forall (r :: RuntimeRep) (a :: TYPE r). HasCallStack => a -- | const x is a unary function which evaluates to x for -- all inputs. -- -- 
--   >>> const 42 "hello"
--   42
--
-- -- 
--   >>> map (const 42) [0..3]
--   [42,42,42,42]
--
const :: a -> b -> a -- | otherwise is defined as the value True. It helps to make -- guards more readable. eg. -- -- 
--   f x | x < 0     = ...
--       | otherwise = ...
--
otherwise :: Bool -- | Conversion of values to readable Strings. -- -- Derived instances of Show have the following properties, which -- are compatible with derived instances of Read: -- -- -- -- For example, given the declarations -- -- 
--   infixr 5 :^:
--   data Tree a =  Leaf a  |  Tree a :^: Tree a
--
-- -- the derived instance of Show is equivalent to -- -- 
--   instance (Show a) => Show (Tree a) where
--   
--          showsPrec d (Leaf m) = showParen (d > app_prec) $
--               showString "Leaf " . showsPrec (app_prec+1) m
--            where app_prec = 10
--   
--          showsPrec d (u :^: v) = showParen (d > up_prec) $
--               showsPrec (up_prec+1) u .
--               showString " :^: "      .
--               showsPrec (up_prec+1) v
--            where up_prec = 5
--
-- -- Note that right-associativity of :^: is ignored. For example, -- -- class Show a -- | Representable types of kind *. This class is derivable in GHC -- with the DeriveGeneric flag on. -- -- A Generic instance must satisfy the following laws: -- -- 
--   from . to ≡ id
--   to . from ≡ id
--
class Generic a -- | Request a CallStack. -- -- NOTE: The implicit parameter ?callStack :: CallStack is an -- implementation detail and should not be considered part of the -- CallStack API, we may decide to change the implementation in -- the future. type HasCallStack = ?callStack :: CallStack -- | A fixed-precision integer type with at least the range [-2^29 .. -- 2^29-1]. The exact range for a given implementation can be -- determined by using minBound and maxBound from the -- Bounded class. data Int -- | 8-bit signed integer type data Int8 -- | 16-bit signed integer type data Int16 -- | 32-bit signed integer type data Int32 -- | 64-bit signed integer type data Int64 -- | A Word is an unsigned integral type, with the same size as -- Int. data Word -- | 8-bit unsigned integer type data Word8 -- | 16-bit unsigned integer type data Word16 -- | 32-bit unsigned integer type data Word32 -- | 64-bit unsigned integer type data Word64 newtype Half Half :: CUShort -> Half [getHalf] :: Half -> CUShort -- | Single-precision floating point numbers. It is desirable that this -- type be at least equal in range and precision to the IEEE -- single-precision type. data Float -- | Double-precision floating point numbers. It is desirable that this -- type be at least equal in range and precision to the IEEE -- double-precision type. data Double data Bool False :: Bool True :: Bool pattern True_ :: HasCallStack => Exp Bool pattern False_ :: HasCallStack => Exp Bool -- | The Maybe type encapsulates an optional value. A value of type -- Maybe a either contains a value of type a -- (represented as Just a), or it is empty (represented -- as Nothing). Using Maybe is a good way to deal with -- errors or exceptional cases without resorting to drastic measures such -- as error. -- -- The Maybe type is also a monad. It is a simple kind of error -- monad, where all errors are represented by Nothing. A richer -- error monad can be built using the Either type. data Maybe a Nothing :: Maybe a Just :: a -> Maybe a pattern Nothing_ :: forall a_11. (HasCallStack, Elt a_11) => Exp (Maybe a_11) pattern Just_ :: forall a_11. (HasCallStack, Elt a_11) => Exp a_11 -> Exp (Maybe a_11) -- | The character type Char is an enumeration whose values -- represent Unicode (or equivalently ISO/IEC 10646) code points (i.e. -- characters, see http://www.unicode.org/ for details). This set -- extends the ISO 8859-1 (Latin-1) character set (the first 256 -- characters), which is itself an extension of the ASCII character set -- (the first 128 characters). A character literal in Haskell has type -- Char. -- -- To convert a Char to or from the corresponding Int value -- defined by Unicode, use toEnum and fromEnum from the -- Enum class respectively (or equivalently ord and -- chr). data Char -- | Haskell type representing the C float type. (The concrete -- types of Foreign.C.Types#platform are platform-specific.) data CFloat -- | Haskell type representing the C double type. (The concrete -- types of Foreign.C.Types#platform are platform-specific.) data CDouble -- | Haskell type representing the C short type. (The concrete -- types of Foreign.C.Types#platform are platform-specific.) data CShort -- | Haskell type representing the C unsigned short type. (The -- concrete types of Foreign.C.Types#platform are -- platform-specific.) data CUShort -- | Haskell type representing the C int type. (The concrete -- types of Foreign.C.Types#platform are platform-specific.) data CInt -- | Haskell type representing the C unsigned int type. (The -- concrete types of Foreign.C.Types#platform are -- platform-specific.) data CUInt -- | Haskell type representing the C long type. (The concrete -- types of Foreign.C.Types#platform are platform-specific.) data CLong -- | Haskell type representing the C unsigned long type. (The -- concrete types of Foreign.C.Types#platform are -- platform-specific.) data CULong -- | Haskell type representing the C long long type. (The -- concrete types of Foreign.C.Types#platform are -- platform-specific.) data CLLong -- | Haskell type representing the C unsigned long long type. -- (The concrete types of Foreign.C.Types#platform are -- platform-specific.) data CULLong -- | Haskell type representing the C char type. (The concrete -- types of Foreign.C.Types#platform are platform-specific.) data CChar -- | Haskell type representing the C signed char type. (The -- concrete types of Foreign.C.Types#platform are -- platform-specific.) data CSChar -- | Haskell type representing the C unsigned char type. (The -- concrete types of Foreign.C.Types#platform are -- platform-specific.) data CUChar