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


-- | An embedded language for accelerated array processing
--   
--   <tt>Data.Array.Accelerate</tt> 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.
--   
--   <ul>
--   <li><i><i>A simple example</i></i></li>
--   </ul>
--   
--   As a simple example, consider the computation of a dot product of two
--   vectors of floating point numbers:
--   
--   <pre>
--   dotp :: Acc (Vector Float) -&gt; Acc (Vector Float) -&gt; Acc (Scalar Float)
--   dotp xs ys = fold (+) 0 (zipWith (*) xs ys)
--   </pre>
--   
--   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 <tt>Data.Array.Accelerate.LLVM.PTX</tt> it may be on-the-fly
--   off-loaded to the GPU.
--   
--   <ul>
--   <li><i><i>Additional components</i></i></li>
--   </ul>
--   
--   The following supported add-ons are available as separate packages.
--   Install them from Hackage with <tt>cabal install &lt;package&gt;</tt>
--   
--   <ul>
--   <li><tt>accelerate-llvm-native</tt>: Backend supporting parallel
--   execution on multicore CPUs.</li>
--   <li><tt>accelerate-llvm-ptx</tt>: Backend supporting parallel
--   execution on CUDA-capable NVIDIA GPUs. Requires a GPU with compute
--   capability 2.0 or greater. See the following table for supported GPUs:
--   <a>http://en.wikipedia.org/wiki/CUDA#Supported_GPUs</a></li>
--   <li><tt>accelerate-cuda</tt>: Backend targeting CUDA-enabled NVIDIA
--   GPUs. Requires a GPU with compute compatibility 1.2 or greater. /NOTE:
--   This backend is being deprecated in favour of
--   <tt>accelerate-llvm-ptx</tt>./</li>
--   <li><tt>accelerate-examples</tt>: Computational kernels and
--   applications showcasing the use of Accelerate as well as a regression
--   test suite, supporting function and performance testing.</li>
--   <li><tt>accelerate-io</tt>: Fast conversions between Accelerate arrays
--   and other array formats (including vector and repa).</li>
--   <li><tt>accelerate-fft</tt>: Discrete Fourier transforms, with FFI
--   bindings to optimised implementations.</li>
--   <li><tt>accelerate-bignum</tt>: Fixed-width large integer
--   arithmetic.</li>
--   <li><tt>colour-accelerate</tt>: Colour representations in Accelerate
--   (RGB, sRGB, HSV, and HSL).</li>
--   <li><tt>gloss-accelerate</tt>: Generate gloss pictures from
--   Accelerate.</li>
--   <li><tt>gloss-raster-accelerate</tt>: Parallel rendering of raster
--   images and animations.</li>
--   <li><tt>lens-accelerate</tt>: Lens operators for Accelerate
--   types.</li>
--   <li><tt>linear-accelerate</tt>: Linear vector spaces in
--   Accelerate.</li>
--   <li><tt>mwc-random-accelerate</tt>: Generate Accelerate arrays filled
--   with high quality pseudorandom numbers.</li>
--   </ul>
--   
--   <ul>
--   <li><i><i>Examples and documentation</i></i></li>
--   </ul>
--   
--   Haddock documentation is included in the package
--   
--   The <tt>accelerate-examples</tt> package demonstrates a range of
--   computational kernels and several complete applications, including:
--   
--   <ul>
--   <li>An implementation of the Canny edge detection algorithm</li>
--   <li>An interactive Mandelbrot set generator</li>
--   <li>A particle-based simulation of stable fluid flows</li>
--   <li>An <i>n</i>-body simulation of gravitational attraction between
--   solid particles</li>
--   <li>An implementation of the PageRank algorithm</li>
--   <li>A simple interactive ray tracer</li>
--   <li>A particle based simulation of stable fluid flows</li>
--   <li>A cellular automata simulation</li>
--   <li>A "password recovery" tool, for dictionary lookup of MD5
--   hashes</li>
--   </ul>
--   
--   <tt>lulesh-accelerate</tt> 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.
--   
--   <ul>
--   <li><i><i>Mailing list and contacts</i></i></li>
--   </ul>
--   
--   <ul>
--   <li>Mailing list: <a>accelerate-haskell@googlegroups.com</a>
--   (discussion of both use and development welcome).</li>
--   <li>Sign up for the mailing list here:
--   <a>http://groups.google.com/group/accelerate-haskell</a></li>
--   <li>Bug reports and issue tracking:
--   <a>https://github.com/AccelerateHS/accelerate/issues</a></li>
--   </ul>
@package accelerate
@version 1.0.0.0


-- | Bitwise operations for signed and unsigned integer expressions.
module Data.Array.Accelerate.Data.Bits

-- | The <a>Bits</a> 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 where shift x i = cond (i < 0) (x `shiftR` (- i)) $ cond (i > 0) (x `shiftL` i) $ x rotate x i = cond (i < 0) (x `rotateR` (- i)) $ cond (i > 0) (x `rotateL` i) $ x zeroBits = clearBit (bit 0) 0 setBit x i = x .|. bit i clearBit x i = x .&. complement (bit i) complementBit x i = x `xor` bit i shiftL x i = x `shift` i unsafeShiftL = shiftL shiftR x i = x `shift` (- i) unsafeShiftR = shiftR rotateL x i = x `rotate` i rotateR x i = x `rotate` (- i)

-- | 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

-- | <tt><a>shift</a> x i</tt> shifts <tt>x</tt> left by <tt>i</tt> bits if
--   <tt>i</tt> is positive, or right by <tt>-i</tt> bits otherwise. Right
--   shifts perform sign extension on signed number types; i.e. they fill
--   the top bits with 1 if the <tt>x</tt> is negative and with 0
--   otherwise.
shift :: Bits a => Exp a -> Exp Int -> Exp a

-- | <tt><a>rotate</a> x i</tt> rotates <tt>x</tt> left by <tt>i</tt> bits
--   if <tt>i</tt> is positive, or right by <tt>-i</tt> bits otherwise.
rotate :: Bits a => Exp a -> Exp Int -> Exp a

-- | The value with all bits unset
zeroBits :: Bits a => Exp a

-- | <tt>bit <i>i</i></tt> is a value with the <tt><i>i</i></tt>th bit set
--   and all other bits clear.
bit :: Bits a => Exp Int -> Exp a

-- | <tt>x `setBit` i</tt> is the same as <tt>x .|. bit i</tt>
setBit :: Bits a => Exp a -> Exp Int -> Exp a

-- | <tt>x `clearBit` i</tt> is the same as <tt>x .&amp;. complement (bit
--   i)</tt>
clearBit :: Bits a => Exp a -> Exp Int -> Exp a

-- | <tt>x `complementBit` i</tt> is the same as <tt>x `xor` bit i</tt>
complementBit :: Bits a => Exp a -> Exp Int -> Exp a

-- | Return <a>True</a> if the <tt>n</tt>th bit of the argument is 1
testBit :: Bits a => Exp a -> Exp Int -> Exp Bool

-- | Return <a>True</a> 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 <a>finiteBitSize</a>.
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 <tt>x</tt> 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 <a>finiteBitSize</a>.
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
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:
--   
--   <pre>
--   logBase2 x = finiteBitSize x - 1 - countLeadingZeros x
--   </pre>
countLeadingZeros :: FiniteBits b => Exp b -> Exp Int

-- | Count the number of zero bits following the least significant set bit.
--   The related <a>find-first-set operation</a> can be expressed in terms
--   of this as:
--   
--   <pre>
--   findFirstSet x = 1 + countTrailingZeros x
--   </pre>
countTrailingZeros :: FiniteBits b => Exp b -> Exp Int
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.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


-- | Complex numbers
module Data.Array.Accelerate.Data.Complex

-- | Complex numbers are an algebraic type.
--   
--   For a complex number <tt>z</tt>, <tt><a>abs</a> z</tt> is a number
--   with the magnitude of <tt>z</tt>, but oriented in the positive real
--   direction, whereas <tt><a>signum</a> z</tt> has the phase of
--   <tt>z</tt>, but unit magnitude.
--   
--   The <a>Foldable</a> and <a>Traversable</a> instances traverse the real
--   part first.
data Complex a :: * -> *

-- | forms a complex number from its real and imaginary rectangular
--   components.
(:+) :: ~a -> ~a -> Complex a

-- | 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)

-- | <tt><a>cis</a> t</tt> is a complex value with magnitude <tt>1</tt> and
--   phase <tt>t</tt> (modulo <tt>2*<a>pi</a></tt>).
cis :: forall a. Floating a => Exp a -> Exp (Complex a)

-- | The function <a>polar</a> takes a complex number and returns a
--   (magnitude, phase) pair in canonical form: the magnitude is
--   non-negative, and the phase in the range <tt>(-<a>pi</a>,
--   <a>pi</a>]</tt>; 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

-- | The phase of a complex number, in the range <tt>(-<a>pi</a>,
--   <a>pi</a>]</tt>. 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
--   
--   <pre>
--   conjugate(Z) = X - iY
--   </pre>
conjugate :: Num a => Exp (Complex a) -> Exp (Complex a)
instance Data.Array.Accelerate.Array.Sugar.Elt a => Data.Array.Accelerate.Array.Sugar.Elt (Data.Complex.Complex a)
instance cst a => Data.Array.Accelerate.Product.IsProduct cst (Data.Complex.Complex a)
instance (Data.Array.Accelerate.Lift.Lift Data.Array.Accelerate.Smart.Exp a, Data.Array.Accelerate.Array.Sugar.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.Array.Sugar.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.Classes.FromIntegral.FromIntegral a (Data.Complex.Complex b)


-- | 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

-- | <a>Arrays</a> consists of nested tuples of individual <a>Array</a>s,
--   currently up to 15-elements wide. Accelerate computations can thereby
--   return multiple results.
class (Typeable a, Typeable (ArrRepr a)) => Arrays a

-- | Run a complete embedded array program using the reference interpreter.
run :: Arrays a => Acc a -> a

-- | Prepare and run an embedded array program of one argument
run1 :: (Arrays a, Arrays b) => (Acc a -> Acc b) -> a -> b


-- | <tt>Data.Array.Accelerate</tt> 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.
--   
--   <ul>
--   <li><i><i>Abstract interface:</i></i></li>
--   </ul>
--   
--   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.
--   
--   <ul>
--   <li><i><i>Stratified language:</i></i></li>
--   </ul>
--   
--   Accelerate distinguishes the types of collective operations <a>Acc</a>
--   from the type of scalar operations <a>Exp</a> to achieve a stratified
--   language. Collective operations comprise many scalar computations that
--   are executed in parallel, but scalar computations <i>can not</i>
--   contain collective operations. This separation excludes <i>nested,
--   irregular</i> data-parallelism statically; instead, Accelerate is
--   limited to <i>flat data-parallelism</i> involving only regular,
--   multi-dimensional arrays.
--   
--   <ul>
--   <li><i><i>Optimisations:</i></i></li>
--   </ul>
--   
--   Accelerate uses a number of scalar and array optimisations, including
--   <i>array fusion</i>, 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.
--   
--   <ul>
--   <li><i><i>Code execution:</i></i></li>
--   </ul>
--   
--   Several backends are available which can be used to evaluate
--   accelerate programs:
--   
--   <ul>
--   <li><a>Data.Array.Accelerate.Interpreter</a>: simple interpreter in
--   Haskell as a reference implementation defining the semantics of the
--   Accelerate language</li>
--   <li><a>accelerate-llvm-native</a>: implementation supporting parallel
--   execution on multicore CPUs (e.g. x86).</li>
--   <li><a>accelerate-llvm-ptx</a>: implementation supporting parallel
--   execution on CUDA-capable NVIDIA GPUs.</li>
--   <li><a>accelerate-cuda</a>: an older implementation supporting
--   parallel execution on CUDA-capable NVIDIA GPUs. <i><b>NOTE:</b> This
--   backend is being deprecated in favour of
--   <tt>accelerate-llvm-ptx</tt>.</i></li>
--   </ul>
--   
--   <ul>
--   <li><i><i>Examples:</i></i></li>
--   </ul>
--   
--   <ul>
--   <li>The <a>accelerate-examples</a> package demonstrates a range of
--   computational kernels and several complete
--   applications:<ul><li>Implementation of the <a>canny edge
--   detector</a></li><li>Interactive <a>Mandelbrot set</a>
--   generator</li><li><a>N-body simulation</a> of gravitational attraction
--   between large bodies</li><li>Implementation of the <a>PageRank</a>
--   algorithm</li><li>A simple, real-time, interactive <a>ray
--   tracer</a>.</li><li>A particle based simulation of stable fluid
--   flows</li><li>A cellular automaton simulation</li><li>A "password
--   recovery" tool, for dictionary attacks on MD5 hashes.</li></ul></li>
--   <li><a>lulesh-accelerate</a> is an implementation of the Livermore
--   Unstructured Lagrangian Explicit Shock Hydrodynamics (LULESH)
--   application. LULESH is representative of typical hydrodynamics codes,
--   although simplified and hard-coded to solve the Sedov blast problem on
--   an unstructured hexahedron mesh.<ul><li>For more information on
--   LULESH: <a>https://codesign.llnl.gov/lulesh.php</a>.</li></ul></li>
--   </ul>
--   
--   <ul>
--   <li><i><i>Additional components:</i></i></li>
--   </ul>
--   
--   <ul>
--   <li><a>accelerate-io</a>: Fast conversion between Accelerate arrays
--   and other formats (e.g. Repa, Vector).</li>
--   <li><a>accelerate-fft</a>: Fast Fourier transform, with FFI bindings
--   to optimised implementations.</li>
--   <li><a>accelerate-bignum</a>: Fixed-width large integer
--   arithmetic.</li>
--   <li><a>colour-accelerate</a>: Colour representations in Accelerate
--   (RGB, sRGB, HSV, and HSL).</li>
--   <li><a>gloss-accelerate</a>: Generate <a>gloss</a> pictures from
--   Accelerate.</li>
--   <li><a>gloss-raster-accelerate</a>: Parallel rendering of raster
--   images and animations.</li>
--   <li><a>lens-accelerate</a>: <a>Lens</a> operators for Accelerate
--   types.</li>
--   <li><a>linear-accelerate</a>: <a>Linear</a> vector space types for
--   Accelerate.</li>
--   <li><a>mwc-random-accelerate</a>: Generate Accelerate arrays filled
--   with high-quality pseudorandom numbers.</li>
--   </ul>
--   
--   <ul>
--   <li><i><i>Contact:</i></i></li>
--   </ul>
--   
--   <ul>
--   <li>Mailing list for both use and development
--   discussion:<ul><li><a>mailto:accelerate-haskell@googlegroups.com</a></li><li><a>http://groups.google.com/group/accelerate-haskell</a></li></ul></li>
--   <li>Bug reports:
--   <a>https://github.com/AccelerateHS/accelerate/issues</a></li>
--   <li>Maintainers:<ul><li>Trevor L. McDonell:
--   <a>mailto:tmcdonell@cse.unsw.edu.au</a></li><li>Manuel M T
--   Chakravarty: <a>mailto:chak@cse.unsw.edu.au</a></li></ul></li>
--   </ul>
--   
--   <ul>
--   <li><i><i>Tip:</i></i></li>
--   </ul>
--   
--   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:
--   
--   <pre>
--   ./foo +RTS -A64M -n2M -RTS
--   </pre>
--   
--   You can make these settings the default by adding the following
--   <tt>ghc-options</tt> to your <tt>.cabal</tt> file or similar:
--   
--   <pre>
--   ghc-options: -with-rtsopts=-n2M -with-rtsopts=-A64M
--   </pre>
--   
--   To specify RTS options you will also need to compile your program with
--   <tt>-rtsopts</tt>.
module Data.Array.Accelerate

-- | Accelerate is an <i>embedded language</i> 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 <i>runtime compiler</i> which generates
--   and executes parallel SIMD code of the target language at application
--   <i>runtime</i>.
--   
--   The type constructor <a>Acc</a> represents embedded collective array
--   operations. A term of type <tt>Acc a</tt> is an Accelerate program
--   which, once executed, will produce a value of type <tt>a</tt> (an
--   <a>Array</a> or a tuple of <a>Arrays</a>). Collective operations of
--   type <tt>Acc a</tt> comprise many <i>scalar expressions</i>, wrapped
--   in type constructor <a>Exp</a>, which will be executed in parallel.
--   Although collective operations comprise many scalar operations
--   executed in parallel, scalar operations <i>cannot</i> initiate new
--   collective operations: this stratification between scalar operations
--   in <a>Exp</a> and array operations in <a>Acc</a> helps statically
--   exclude <i>nested data parallelism</i>, which is difficult to execute
--   efficiently on constrained hardware such as GPUs.
--   
--   For example, to compute a vector dot product we could write:
--   
--   <pre>
--   dotp :: Num a =&gt; Vector a -&gt; Vector a -&gt; Acc (Scalar a)
--   dotp xs ys =
--     let
--         xs' = use xs
--         ys' = use ys
--     in
--     fold (+) 0 ( zipWith (*) xs' ys' )
--   </pre>
--   
--   The function <tt>dotp</tt> consumes two one-dimensional arrays
--   (<a>Vector</a>s) of values, and produces a single (<a>Scalar</a>)
--   result as output. As the return type is wrapped in the type
--   <a>Acc</a>, we see that it is an embedded Accelerate computation - it
--   will be evaluated in the <i>object</i> language of dynamically
--   generated parallel code, rather than the <i>meta</i> language of
--   vanilla Haskell.
--   
--   As the arguments to <tt>dotp</tt> are plain Haskell arrays, to make
--   these available to Accelerate computations they must be embedded with
--   the <a>use</a> function.
--   
--   An Accelerate backend is used to evaluate the embedded computation and
--   return the result back to vanilla Haskell. Calling the <tt>run</tt>
--   function of a backend will generate code for the target architecture,
--   compile, and execute it. For example, the following backends are
--   available:
--   
--   <ul>
--   <li><a>accelerate-llvm-native</a>: for execution on multicore
--   CPUs</li>
--   <li><a>accelerate-llvm-ptx</a>: for execution on NVIDIA CUDA-capable
--   GPUs</li>
--   </ul>
--   
--   See also <a>Exp</a>, which encapsulates embedded <i>scalar</i>
--   computations.
--   
--   <ul>
--   <li><i><i>Fusion:</i></i></li>
--   </ul>
--   
--   Array computations of type <a>Acc</a> will be subject to <i>array
--   fusion</i>; Accelerate will combine individual <a>Acc</a> 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:
--   
--   <ol>
--   <li>Element-wise operations, such as <a>map</a>, <a>generate</a>, and
--   <a>backpermute</a>. Each element of these operations can be computed
--   independently of all others.</li>
--   <li>Collective operations such as <a>fold</a>, <a>scanl</a>, and
--   <a>stencil</a>. To compute each output element of these operations
--   requires reading multiple elements from the input array(s).</li>
--   </ol>
--   
--   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:
--   
--   <pre>
--   map -&gt; reverse -&gt; reshape -&gt; map -&gt; map
--   </pre>
--   
--   <pre>
--   map -&gt; backpermute -&gt;
--                         zipWith -&gt; map
--             generate -&gt;
--   </pre>
--   
--   If the consumer operation uses more than one element of the input
--   array (typically, via <a>generate</a> 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:
--   
--   <pre>
--        use -&gt;
--               zipWith -&gt; fold |-&gt; map
--   generate -&gt;
--   </pre>
--   
--   Here the element-wise sequence (<a>use</a> + <a>generate</a> +
--   <a>zipWith</a>) will fuse into a single operation, which then fuses
--   into the collective <a>fold</a> operation. At this point in the
--   program the <a>fold</a> must now be evaluated. In the final step the
--   <a>map</a> reads in the array produced by <a>fold</a>. As there is no
--   fusion between the <a>fold</a> and <a>map</a> steps, this program
--   consists of two "loops"; one for the <a>use</a> + <a>generate</a> +
--   <a>zipWith</a> + <a>fold</a> step, and one for the final <a>map</a>
--   step.
--   
--   You can see how many operations will be executed in the fused program
--   by <a>Show</a>-ing the <a>Acc</a> program, or by using the debugging
--   option <tt>-ddump-dot</tt> to save the program as a graphviz DOT file.
--   
--   As a special note, the operations <a>unzip</a> and <a>reshape</a>,
--   when applied to a real array, are executed in constant time, so in
--   this situation these operations will not be fused.
--   
--   <ul>
--   <li><i><i>Tips:</i></i></li>
--   </ul>
--   
--   <ul>
--   <li>Since <a>Acc</a> represents embedded computations that will only
--   be executed when evaluated by a backend, we can programatically
--   generate these computations using the meta language Haskell; for
--   example, unrolling loops or embedding input values into the generated
--   code.</li>
--   <li>It is usually best to keep all intermediate computations in
--   <a>Acc</a>, and only <tt>run</tt> the computation at the very end to
--   produce the final result. This enables optimisations between
--   intermediate results (e.g. array fusion) and, if the target
--   architecture has a separate memory space as is the case of GPUs, to
--   prevent excessive data transfers.</li>
--   </ul>
data Acc a

-- | Dense, regular, multi-dimensional arrays.
--   
--   The <a>Array</a> 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 <a>Array</a> type has two type
--   parameters:
--   
--   <ul>
--   <li><i>sh</i>: is the shape of the array, tracking the dimensionality
--   and extent of each dimension of the array; for example, <a>DIM1</a>
--   for one-dimensional <a>Vector</a>s, <a>DIM2</a> for two-dimensional
--   matrices, and so on.</li>
--   <li><i>e</i>: represents the type of each element of the array; for
--   example, <a>Int</a>, <a>Float</a>, et cetera.</li>
--   </ul>
--   
--   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 <a>Shape</a> is the fastest varying). The
--   allowable array element types are members of the <a>Elt</a> class,
--   which roughly consists of:
--   
--   <ul>
--   <li>Signed and unsigned integers (8, 16, 32, and 64-bits wide).</li>
--   <li>Floating point numbers (single and double precision)</li>
--   <li><a>Char</a></li>
--   <li><a>Bool</a></li>
--   <li>()</li>
--   <li>Shapes formed from <a>Z</a> and (<a>:.</a>)</li>
--   <li>Nested tuples of all of these, currently up to 15-elements
--   wide.</li>
--   </ul>
--   
--   Note that <a>Array</a> 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 <a>use</a>.
--   
--   Section "Getting data in" lists functions for getting data into and
--   out of the <a>Array</a> type.
data Array sh e

-- | <a>Arrays</a> consists of nested tuples of individual <a>Array</a>s,
--   currently up to 15-elements wide. Accelerate computations can thereby
--   return multiple results.
class (Typeable a, Typeable (ArrRepr a)) => Arrays a

-- | Scalars arrays hold a single element
type Scalar e = Array DIM0 e

-- | Vectors are one-dimensional arrays
type Vector e = Array DIM1 e

-- | Segment descriptor (vector of segment lengths).
--   
--   To represent nested one-dimensional arrays, we use a flat array of
--   data values in conjunction with a <i>segment descriptor</i>, which
--   stores the lengths of the subarrays.
type Segments i = Vector i

-- | The <a>Elt</a> class characterises the allowable array element types,
--   and hence the types which can appear in scalar Accelerate expressions.
--   
--   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:
--   
--   <ul>
--   <li>Signed and unsigned integers (8, 16, 32, and 64-bits wide)</li>
--   <li>Floating point numbers (single and double precision)</li>
--   <li><a>Char</a></li>
--   <li><a>Bool</a></li>
--   <li>()</li>
--   <li>Shapes formed from <a>Z</a> and (<a>:.</a>)</li>
--   <li>Nested tuples of all of these, currently up to 15-elements
--   wide</li>
--   </ul>
--   
--   Adding new instances for <a>Elt</a> consists of explaining to
--   Accelerate how to map between your data type and a (tuple of)
--   primitive values. For examples see:
--   
--   <ul>
--   <li><a>Data.Array.Accelerate.Data.Complex</a></li>
--   <li><a>Data.Array.Accelerate.Data.Monoid</a></li>
--   <li><a>linear-accelerate</a></li>
--   <li><a>colour-accelerate</a></li>
--   </ul>
class (Show a, Typeable a, Typeable (EltRepr a), ArrayElt (EltRepr a)) => Elt a

-- | Rank-0 index
data Z
Z :: Z

-- | Increase an index rank by one dimension. The <a>:.</a> operator is
--   used to construct both values and types.
data (:.) tail head
(:.) :: tail -> head -> (:.) tail head
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), Shape (EltRepr sh), FullShape sh ~ sh, CoSliceShape sh ~ sh, SliceShape sh ~ Z) => Shape sh where rank = rank . fromElt size = size . fromElt empty = toElt empty ignore = toElt ignore intersect sh1 sh2 = toElt (intersect (fromElt sh1) (fromElt sh2)) union sh1 sh2 = toElt (union (fromElt sh1) (fromElt sh2)) fromIndex sh ix = toElt (fromIndex (fromElt sh) ix) toIndex sh ix = toIndex (fromElt sh) (fromElt ix) bound sh ix bndy = case bound (fromElt sh) (fromElt ix) bndy of { Left v -> Left v Right ix' -> Right $ toElt ix' } iter sh f c r = iter (fromElt sh) (f . toElt) c r iter1 sh f r = iter1 (fromElt sh) (f . toElt) r rangeToShape (low, high) = toElt (rangeToShape (fromElt low, fromElt high)) shapeToRange ix = let (low, high) = shapeToRange (fromElt ix) in (toElt low, toElt high) shapeToList = shapeToList . fromElt listToShape = toElt . listToShape

-- | Slices, aka generalised indices, as <i>n</i>-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 SliceShape sl :: * type CoSliceShape sl :: * type FullShape sl :: * where {
    type family SliceShape sl :: *;
    type family CoSliceShape sl :: *;
    type family FullShape sl :: *;
}
sliceIndex :: Slice sl => sl -> SliceIndex (EltRepr sl) (EltRepr (SliceShape sl)) (EltRepr (CoSliceShape sl)) (EltRepr (FullShape sl))

-- | Marker for entire dimensions in <a>slice</a> and <a>replicate</a>
--   descriptors.
--   
--   Occurrences of <a>All</a> indicate the dimensions into which the
--   array's existing extent will be placed unchanged.
--   
--   See <a>slice</a> and <a>replicate</a> for examples.
data All
All :: All

-- | Marker for arbitrary dimensions in <a>slice</a> and <a>replicate</a>
--   descriptors.
--   
--   <a>Any</a> can be used in the leftmost position of a slice instead of
--   <a>Z</a>, indicating that any dimensionality is admissible in that
--   position.
--   
--   See <a>slice</a> and <a>replicate</a> for examples.
data Any sh
Any :: Any sh

-- | Multidimensional array indexing. Extract the value from an array at
--   the specified zero-based index.
--   
--   <pre>
--   &gt;&gt;&gt; let mat = fromList (Z:.5:.10) [0..]
--   
--   &gt;&gt;&gt; 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]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; mat ! Z:.1:.2
--   12
--   </pre>
(!) :: (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.
--   
--   <pre>
--   &gt;&gt;&gt; let mat = fromList (Z:.5:.10) [0..]
--   
--   &gt;&gt;&gt; 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]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; mat !! 12
--   12
--   </pre>
(!!) :: (Shape sh, Elt e) => Acc (Array sh e) -> Exp Int -> Exp e
infixl 9 !!

-- | Extract the element of a singleton array.
--   
--   <pre>
--   the xs  ==  xs ! Z
--   </pre>
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 :: (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 :: 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, <a>use</a> may entail data transfer (e.g. to a GPU).
--   
--   <a>use</a> is overloaded so that it can accept tuples of
--   <a>Arrays</a>:
--   
--   <pre>
--   &gt;&gt;&gt; let vec = fromList (Z:.10) [0..]  :: Array DIM1 Int
--   Vector (Z :. 10) [0,1,2,3,4,5,6,7,8,9]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; let mat = fromList (Z:.5:.10) [0..]  :: Array DIM2 Int
--   
--   &gt;&gt;&gt; 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]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; let vec' = use vec         :: Acc (Array DIM1 Int)
--   
--   &gt;&gt;&gt; let mat' = use mat         :: Acc (Array DIM2 Int)
--   
--   &gt;&gt;&gt; let tup  = use (vec, mat)  :: Acc (Array DIM1 Int, Array DIM2 Int)
--   </pre>
use :: Arrays arrays => arrays -> Acc arrays

-- | Construct a singleton (one element) array from a scalar value (or
--   tuple of scalar values).
unit :: 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
--   (<a>Vector</a>) of three floating point numbers:
--   
--   <pre>
--   &gt;&gt;&gt; generate (index1 3) (\_ -&gt; 1.2)
--   Vector (Z :. 3) [1.2,1.2,1.2]
--   </pre>
--   
--   Or equivalently:
--   
--   <pre>
--   &gt;&gt;&gt; fill (constant (Z :. 3)) 1.2
--   Vector (Z :. 3) [1.2,1.2,1.2]
--   </pre>
--   
--   The following will create a vector with the elements <tt>[1..10]</tt>:
--   
--   <pre>
--   &gt;&gt;&gt; generate (index1 10) (\ix -&gt; unindex1 ix + 1)
--   Vector (Z :. 10) [1,2,3,4,5,6,7,8,9,10]
--   </pre>
--   
--   <ul>
--   <li><i><i>NOTE:</i></i></li>
--   </ul>
--   
--   Using <a>generate</a>, 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 <a>Exp</a> terms
--   by array indexing operations such as (<a>!</a>) or <a>the</a>, the
--   program will fail with the error:
--   './Data/Array/Accelerate/Trafo/Sharing.hs:447 (convertSharingExp):
--   inconsistent valuation @ shared 'Exp' tree ...'.
generate :: (Shape sh, Elt a) => Exp sh -> (Exp sh -> Exp a) -> Acc (Array sh a)

-- | Create an array where all elements are the same value.
fill :: (Shape sh, Elt e) => Exp sh -> Exp e -> Acc (Array sh e)

-- | Create an array of the given shape containing the values <tt>x</tt>,
--   <tt>x+1</tt>, etc. (in row-major order).
--   
--   <pre>
--   &gt;&gt;&gt; enumFromN (constant (Z:.5:.10)) 0 :: Array DIM2 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]
--   </pre>
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 <tt>x</tt>,
--   <tt>x+y</tt>, <tt>x+y+y</tt> etc. (in row-major order).
--   
--   <pre>
--   &gt;&gt;&gt; enumFromStepN (constant (Z:.5:.10)) 0 0.5 :: Array DIM2 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]
--   </pre>
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.
--   
--   <pre>
--   &gt;&gt;&gt; let m1 = fromList (Z:.5:.10) [0..]
--   
--   &gt;&gt;&gt; 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]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; let m2 = fromList (Z:.10:.3) [0..]
--   
--   &gt;&gt;&gt; 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]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; 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]
--   </pre>
(++) :: forall sh e. (Slice sh, Shape sh, Elt e) => Acc (Array (sh :. Int) e) -> Acc (Array (sh :. Int) e) -> Acc (Array (sh :. Int) e)
infixr 5 ++

-- | Infix version of <a>acond</a>. If the predicate evaluates to
--   <a>True</a>, the first component of the tuple is returned, else the
--   second.
--   
--   See also: <a>ifThenElse</a>.
(?|) :: Arrays a => Exp Bool -> (Acc a, Acc a) -> Acc a
infix 0 ?|

-- | An array-level if-then-else construct.
acond :: Arrays a => Exp Bool -> Acc a -> Acc a -> Acc a

-- | An array-level <a>while</a> construct. Continue to apply the given
--   function, starting with the initial value, until the test function
--   evaluates to <a>False</a>.
awhile :: Arrays a => (Acc a -> Acc (Scalar Bool)) -> (Acc a -> Acc a) -> Acc a -> Acc a

-- | For use with <tt>-XRebindableSyntax</tt>, this class provides
--   <a>ifThenElse</a> lifted to both scalar and array types.
class IfThenElse t where type EltT t a :: Constraint 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
--   
--   <pre>
--   (acc1 &gt;-&gt; acc2) arrs = let tmp = acc1 arrs
--                          in  tmp `seq` acc2 tmp
--   </pre>
(>->) :: (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 <a>transpose</a>
--   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:
--   
--   <pre>
--   loop :: Exp Int -&gt; Exp Int
--   loop ticks =
--     let clockRate = 900000   -- kHz
--     in  while (\i -&gt; i &lt; 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]))
--   </pre>
--   
--   Without the use of <a>compute</a>, 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
indexed :: (Shape sh, Elt a) => Acc (Array sh a) -> Acc (Array sh (sh, a))

-- | Apply the given function element-wise to an array.
--   
--   <pre>
--   map f [x1, x2, ... xn] = [f x1, f x2, ... f xn]
--   </pre>
map :: (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.
zipWith :: (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 <a>zipWith</a>.
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 <a>zipWith</a>.
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 <a>zipWith</a>.
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 <a>zipWith</a>.
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 <a>zipWith</a>.
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 <a>zipWith</a>.
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 <a>zipWith</a>.
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 <a>izipWith</a>.
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 <a>zipWith</a>.
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 <a>zipWith</a>.
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 <a>zipWith</a>.
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 <a>zipWith</a>.
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 <a>zipWith</a>.
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 <a>zipWith</a>.
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.
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 <a>zip</a>, but the shape of the two results is
--   identical to the shape of the argument.
--   
--   If the argument array is manifest in memory, <a>unzip</a> is a NOP.
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 8-tuples and return eight 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
--   <a>size</a> of the source and result arrays must be identical.
--   
--   <pre>
--   precondition: shapeSize sh == shapeSize sh'
--   </pre>
--   
--   If the argument array is manifest in memory, <a>reshape</a> is a NOP.
--   If the argument is to be fused into a subsequent operation,
--   <a>reshape</a> corresponds to an index transformation in the fused
--   code.
reshape :: (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 <a>reshape</a>, 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
--   <i>generalised</i> array index provided as the first argument.
--   
--   For example, given the following vector:
--   
--   <pre>
--   &gt;&gt;&gt; let vec = fromList (Z:.10) [0..]
--   Vector (Z :. 10) [0,1,2,3,4,5,6,7,8,9]
--   </pre>
--   
--   ...we can replicate these elements to form a two-dimensional array
--   either by replicating those elements as new rows:
--   
--   <pre>
--   &gt;&gt;&gt; replicate (lift (Z :. 4 :. 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]
--   </pre>
--   
--   ...or as columns:
--   
--   <pre>
--   &gt;&gt;&gt; replicate (lift (Z :. All :. 4)) (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]
--   </pre>
--   
--   Replication along more than one dimension is also possible. Here we
--   replicate twice across the first dimension and three times across the
--   third dimension:
--   
--   <pre>
--   &gt;&gt;&gt; replicate (lift (Z :. 2 :. All :. 3)) (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]
--   </pre>
--   
--   The marker <a>Any</a> can be used in the slice specification to match
--   against some arbitrary dimension. For example, here <a>Any</a> matches
--   against whatever shape type variable <tt>sh</tt> takes.
--   
--   <pre>
--   rep0 :: (Shape sh, Elt e) =&gt; Exp Int -&gt; Acc (Array sh e) -&gt; Acc (Array (sh :. Int) e)
--   rep0 n a = replicate (lift (Any :. n)) a
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; let x = unit 42  :: Acc (Scalar Int)
--   
--   &gt;&gt;&gt; rep0 10 x
--   Vector (Z :. 10) [42,42,42,42,42,42,42,42,42,42]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; 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]
--   </pre>
--   
--   Of course, <a>Any</a> and <a>All</a> can be used together.
--   
--   <pre>
--   rep1 :: (Shape sh, Elt e) =&gt; Exp Int -&gt; Acc (Array (sh :. Int) e) -&gt; Acc (Array (sh :. Int :. Int) e)
--   rep1 n a = A.replicate (lift (Any :. n :. All)) a
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; 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]
--   </pre>
replicate :: (Slice slix, Elt e) => Exp slix -> Acc (Array (SliceShape slix) e) -> Acc (Array (FullShape slix) e)

-- | Index an array with a <i>generalised</i> array index, supplied as the
--   second argument. The result is a new array (possibly a singleton)
--   containing the selected dimensions (<a>All</a>s) in their entirety.
--   
--   <a>slice</a> is the opposite of <a>replicate</a>, and can be used to
--   <i>cut out</i> entire dimensions. For example, for the two dimensional
--   array <tt>mat</tt>:
--   
--   <pre>
--   &gt;&gt;&gt; let mat = fromList (Z:.5:.10) [0..]
--   
--   &gt;&gt;&gt; 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]
--   </pre>
--   
--   ...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
--   <a>All</a>):
--   
--   <pre>
--   &gt;&gt;&gt; slice (use mat) (lift (Z :. 2 :. All))
--   Vector (Z :. 10) [20,21,22,23,24,25,26,27,28,29]
--   </pre>
--   
--   A fully specified index (with no <a>All</a>s) returns a single element
--   (zero dimensional array).
--   
--   <pre>
--   &gt;&gt;&gt; slice (use mat) (lift (Z :. 4 :. 2))
--   Scalar Z [42]
--   </pre>
--   
--   The marker <a>Any</a> can be used in the slice specification to match
--   against some arbitrary (lower) dimension. Here <a>Any</a> matches
--   whatever shape type variable <tt>sh</tt> takes:
--   
--   <pre>
--   sl0 :: (Shape sh, Elt e) =&gt; Acc (Array (sh:.Int) e) -&gt; Exp Int -&gt; Acc (Array sh e)
--   sl0 a n = A.slice a (lift (Any :. n))
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; let vec = fromList (Z:.10) [0..]
--   
--   &gt;&gt;&gt; sl0 (use vec) 4
--   Scalar Z [4]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; sl0 (use mat) 4
--   Vector (Z :. 5) [4,14,24,34,44]
--   </pre>
--   
--   Of course, <a>Any</a> and <a>All</a> can be used together.
--   
--   <pre>
--   sl1 :: (Shape sh, Elt e) =&gt; Acc (Array (sh:.Int:.Int) e) -&gt; Exp Int -&gt; Acc (Array (sh:.Int) e)
--   sl1 a n = A.slice a (lift (Any :. n :. All))
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; sl1 (use mat) 4
--   Vector (Z :. 10) [40,41,42,43,44,45,46,47,48,49]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; let cube = fromList (Z:.3:.4:.5) [0..]
--   
--   &gt;&gt;&gt; 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]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; sl1 (use cube) 2
--   Matrix (Z :. 3 :. 5)
--     [ 10, 11, 12, 13, 14,
--       30, 31, 32, 33, 34,
--       50, 51, 52, 53, 54]
--   </pre>
slice :: (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.
--   
--   <pre>
--   &gt;&gt;&gt; let mat = fromList (Z:.5:.10) [0..]
--   
--   &gt;&gt;&gt; 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]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; 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]
--   </pre>
init :: forall sh e. (Slice sh, 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.
--   
--   <pre>
--   &gt;&gt;&gt; let mat = fromList (Z:.5:.10) [0..]
--   
--   &gt;&gt;&gt; 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]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; 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]
--   </pre>
tail :: forall sh e. (Slice sh, Shape sh, Elt e) => Acc (Array (sh :. Int) e) -> Acc (Array (sh :. Int) e)

-- | Yield the first <tt>n</tt> elements in the innermost dimension of the
--   array (plus all lower dimensional elements).
--   
--   <pre>
--   &gt;&gt;&gt; let mat = fromList (Z:.5:.10) [0..]
--   
--   &gt;&gt;&gt; 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]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; 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]
--   </pre>
take :: forall sh e. (Slice sh, Shape sh, Elt e) => Exp Int -> Acc (Array (sh :. Int) e) -> Acc (Array (sh :. Int) e)

-- | Yield all but the first <tt>n</tt> elements along the innermost
--   dimension of the array (plus all lower dimensional elements).
--   
--   <pre>
--   &gt;&gt;&gt; let mat = fromList (Z:.5:.10) [0..]
--   
--   &gt;&gt;&gt; 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]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; drop 7 (use mat)
--   Matrix (Z :. 5 :. 3)
--     [  7,  8,  9,
--       17, 18, 19,
--       27, 28, 29,
--       37, 38, 39,
--       47, 48, 49]
--   </pre>
drop :: forall sh e. (Slice sh, 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:
--   
--   <pre>
--   slit i n = take n . drop i
--   </pre>
slit :: forall sh e. (Slice sh, Shape sh, Elt e) => Exp Int -> Exp Int -> Acc (Array (sh :. Int) e) -> Acc (Array (sh :. Int) 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 <i>associative</i> and
--   <i>commutative</i>. Elements that are mapped to the magic value
--   <a>ignore</a> by the permutation function are dropped.
--   
--   For example, we can use <a>permute</a> to compute the occurrence count
--   (histogram) for an array of values in the range <tt>[0,10)</tt>:
--   
--   <pre>
--   histogram :: Acc (Vector Int) -&gt; Acc (Vector Int)
--   histogram xs =
--     let zeros = fill (constant (Z:.10)) 0
--         ones  = fill (shape xs)         1
--     in
--     permute (+) zeros (\ix -&gt; index1 (xs!ix)) ones
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; 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]
--   
--   &gt;&gt;&gt; histogram (use xs)
--   Vector (Z :. 10) [2,4,4,3,2,2,0,0,2,1]
--   </pre>
--   
--   <ul>
--   <li><i><i>Note:</i></i></li>
--   </ul>
--   
--   Regarding array fusion:
--   
--   <ol>
--   <li>The <a>permute</a> operation will always be evaluated; it can not
--   be fused into a later step.</li>
--   <li>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.</li>
--   <li>The array of source values can fuse into the permutation
--   operation.</li>
--   </ol>
permute :: (Shape sh, Shape sh', Elt a) => (Exp a -> Exp a -> Exp a) -> Acc (Array sh' a) -> (Exp sh -> Exp sh') -> Acc (Array sh a) -> Acc (Array sh' a)

-- | Magic value identifying elements that are ignored in a forward
--   permutation.
ignore :: Shape sh => Exp sh

-- | 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.
--   
--   <pre>
--   &gt;&gt;&gt; let to    = fromList (Z :. 6) [1,3,7,2,5,8]
--   
--   &gt;&gt;&gt; let input = fromList (Z :. 7) [1,9,6,4,4,2,5]
--   
--   &gt;&gt;&gt; scatter (use to) (fill (constant (Z:.10)) 0) (use input)
--   Vector (Z :. 10) [0,1,4,9,0,4,0,6,2,0]
--   </pre>
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 <a>transpose</a> a matrix; at
--   every index <tt>Z:.y:.x</tt> in the result array, we get the value at
--   that index by reading from the source array at index <tt>Z:.x:.y</tt>:
--   
--   <pre>
--   swap :: Exp DIM2 -&gt; Exp DIM2
--   swap = lift1 $ \(Z:.y:.x) -&gt; Z:.x:.y
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; let mat = fromList (Z:.5:.10) [0..]
--   
--   &gt;&gt;&gt; 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]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; let mat' = use mat
--   
--   &gt;&gt;&gt; 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]
--   </pre>
backpermute :: (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.
--   
--   <pre>
--   &gt;&gt;&gt; let input = fromList (Z:.9) [1,9,6,4,4,2,0,1,2]
--   
--   &gt;&gt;&gt; let from  = fromList (Z:.6) [1,3,7,2,5,3]
--   
--   &gt;&gt;&gt; gather (use from) (use input)
--   Vector (Z :. 6) [9,4,1,6,2,4]
--   </pre>
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)

-- | 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.
--   
--   <pre>
--   &gt;&gt;&gt; let vec = fromList (Z :. 10) [1..10] :: Vector Int
--   
--   &gt;&gt;&gt; vec
--   Vector (Z :. 10) [1,2,3,4,5,6,7,8,9,10]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; filter even (use vec)
--   (Vector (Z :. 5) [2,4,6,8,10], Scalar Z [5])
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; 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] :: Array DIM2 Int
--   
--   &gt;&gt;&gt; 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]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; 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])
--   </pre>
filter :: forall sh e. (Shape sh, Slice sh, Elt e) => (Exp e -> Exp Bool) -> Acc (Array (sh :. Int) e) -> Acc (Vector e, Array sh Int)

-- | Reduction of the innermost dimension of an array of arbitrary rank.
--   The first argument needs to be an <i>associative</i> function to
--   enable an efficient parallel implementation. The initial element does
--   not need to be an identity element of the combination function.
--   
--   <pre>
--   &gt;&gt;&gt; let mat = fromList (Z:.5:.10) [0..]
--   
--   &gt;&gt;&gt; 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]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; fold (+) 42 (use mat)
--   Vector (Z :. 5) [87,187,287,387,487]
--   </pre>
--   
--   Reductions with non-commutative operators are supported. For example,
--   the following computes the maximum segment sum problem along each
--   innermost dimension of the array.
--   
--   <a>https://en.wikipedia.org/wiki/Maximum_subarray_problem</a>
--   
--   <pre>
--   maximumSegmentSum
--       :: forall sh e. (Shape sh, Num e, Ord e)
--       =&gt; Acc (Array (sh :. Int) e)
--       -&gt; Acc (Array sh e)
--   maximumSegmentSum
--     = map (\v -&gt; let (x,_,_,_) = unlift v :: (Exp e, Exp e, Exp e, Exp e) in x)
--     . fold1 f
--     . map g
--     where
--       f :: (Num a, Ord a) =&gt; Exp (a,a,a,a) -&gt; Exp (a,a,a,a) -&gt; Exp (a,a,a,a)
--       f x y =
--         let (mssx, misx, mcsx, tsx) = unlift x
--             (mssy, misy, mcsy, tsy) = unlift y
--         in
--         lift ( mssx `max` (mssy `max` (mcsx+misy))
--              , misx `max` (tsx+misy)
--              , mcsy `max` (mcsx+tsy)
--              , tsx+tsy
--              )
--   
--       g :: (Num a, Ord a) =&gt; Exp a -&gt; Exp (a,a,a,a)
--       g x = let y = max x 0
--             in  lift (y,y,y,x)
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; let vec = fromList (Z:.10) [-2,1,-3,4,-1,2,1,-5,4,0]
--   
--   &gt;&gt;&gt; maximumSegmentSum (use vec)
--   Scalar Z [6]
--   </pre>
--   
--   See also <a>Fold</a>, which can be a useful way to compute multiple
--   results from a single reduction.
fold :: (Shape sh, Elt a) => (Exp a -> Exp a -> Exp a) -> Exp a -> Acc (Array (sh :. Int) a) -> Acc (Array sh a)

-- | Variant of <a>fold</a> that requires the reduced array to be non-empty
--   and doesn't need an default value. The first argument needs to be an
--   <i>associative</i> function to enable an efficient parallel
--   implementation. The initial element does not need to be an identity
--   element.
fold1 :: (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 <i>associative</i> function to enable
--   efficient parallel implementation. The initial element does not need
--   to be an identity element.
--   
--   <pre>
--   &gt;&gt;&gt; let vec = fromList (Z:.10) [0..]
--   
--   &gt;&gt;&gt; foldAll (+) 42 (use vec)
--   Scalar Z [87]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; let mat = fromList (Z:.5:.10) [0..]
--   
--   &gt;&gt;&gt; foldAll (+) 0 (use mat)
--   Scalar Z [1225]
--   </pre>
foldAll :: (Shape sh, Elt a) => (Exp a -> Exp a -> Exp a) -> Exp a -> Acc (Array sh a) -> Acc (Scalar a)

-- | Variant of <a>foldAll</a> that requires the reduced array to be
--   non-empty and doesn't need an default value. The first argument must
--   be an <i>associative</i> 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).
--   
--   <pre>
--   &gt;&gt;&gt; let seg = fromList (Z:.4) [1,4,0,3]
--   
--   &gt;&gt;&gt; seg
--   Vector (Z :. 4) [1,4,0,3]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; let mat = fromList (Z:.5:.10) [0..]
--   
--   &gt;&gt;&gt; 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]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; 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]
--   </pre>
foldSeg :: (Shape sh, Elt a, Elt i, IsIntegral i) => (Exp a -> Exp a -> Exp a) -> Exp a -> Acc (Array (sh :. Int) a) -> Acc (Segments i) -> Acc (Array (sh :. Int) a)

-- | Variant of <a>foldSeg</a> that requires <i>all</i> segments of the
--   reduced array to be non-empty and doesn't need a default value. The
--   segment descriptor specifies the length of each of the logical
--   sub-arrays.
fold1Seg :: (Shape sh, Elt a, Elt i, IsIntegral i) => (Exp a -> Exp a -> Exp a) -> Acc (Array (sh :. Int) a) -> Acc (Segments i) -> Acc (Array (sh :. Int) a)

-- | Check if all elements satisfy a predicate
all :: (Shape sh, Elt e) => (Exp e -> Exp Bool) -> Acc (Array sh e) -> Acc (Scalar Bool)

-- | Check if any element satisfies the predicate
any :: (Shape sh, Elt e) => (Exp e -> Exp Bool) -> Acc (Array sh e) -> Acc (Scalar Bool)

-- | Check if all elements are <a>True</a>
and :: Shape sh => Acc (Array sh Bool) -> Acc (Scalar Bool)

-- | Check if any element is <a>True</a>
or :: Shape sh => Acc (Array sh Bool) -> Acc (Scalar Bool)

-- | Compute the sum of elements
sum :: (Shape sh, Num e) => Acc (Array sh e) -> Acc (Scalar e)

-- | Compute the product of the elements
product :: (Shape sh, Num e) => Acc (Array sh e) -> Acc (Scalar e)

-- | Yield the minimum element of an array. The array must not be empty.
minimum :: (Shape sh, Ord e) => Acc (Array sh e) -> Acc (Scalar e)

-- | Yield the maximum element of an array. The array must not be empty.
maximum :: (Shape sh, Ord e) => Acc (Array sh e) -> Acc (Scalar e)

-- | Data.List style left-to-right scan along the innermost dimension of an
--   arbitrary rank array. The first argument needs to be an
--   <i>associative</i> function to enable efficient parallel
--   implementation. The initial value (second argument) may be arbitrary.
--   
--   <pre>
--   &gt;&gt;&gt; scanl (+) 10 (use $ fromList (Z :. 10) [0..])
--   Array (Z :. 11) [10,10,11,13,16,20,25,31,38,46,55]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; scanl (+) 0 (use $ fromList (Z :. 4 :. 10) [0..])
--   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]
--   </pre>
scanl :: (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 array must not be
--   empty. The first argument needs to be an <i>associative</i> function.
--   Denotationally, we have:
--   
--   <pre>
--   scanl1 f e arr = tail (scanl f e arr)
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; scanl (+) (use $ fromList (Z:.4:.10) [0..])
--   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]
--   </pre>
scanl1 :: (Shape sh, Elt a) => (Exp a -> Exp a -> Exp a) -> Acc (Array (sh :. Int) a) -> Acc (Array (sh :. Int) a)

-- | Variant of <a>scanl</a>, where the last element (final reduction
--   result) along each dimension is returned separately. Denotationally we
--   have:
--   
--   <pre>
--   scanl' f e arr = (init res, unit (res!len))
--     where
--       len = shape arr
--       res = scanl f e arr
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; let (res,sum) = scanl' (+) 0 (use $ fromList (Z:.10) [0..])
--   
--   &gt;&gt;&gt; res
--   Vector (Z :. 10) [0,0,1,3,6,10,15,21,28,36]
--   
--   &gt;&gt;&gt; sum
--   Scalar Z [45]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; let (res,sums) = scanl' (+) 0 (use $ fromList (Z:.4:.10) [0..])
--   
--   &gt;&gt;&gt; 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]
--   
--   &gt;&gt;&gt; sums
--   Vector (Z :. 4) [45,145,245,345]
--   </pre>
scanl' :: (Shape sh, Elt a) => (Exp a -> Exp a -> Exp a) -> Exp a -> Acc (Array (sh :. Int) a) -> (Acc (Array (sh :. Int) a), Acc (Array sh a))

-- | Right-to-left variant of <a>scanl</a>.
scanr :: (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 <a>scanl1</a>.
scanr1 :: (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 <a>scanl'</a>.
scanr' :: (Shape sh, Elt a) => (Exp a -> Exp a -> Exp a) -> Exp a -> Acc (Array (sh :. Int) a) -> (Acc (Array (sh :. Int) a), Acc (Array sh a))

-- | Left-to-right prescan (aka exclusive scan). As for <tt>scan</tt>, the
--   first argument must be an <i>associative</i> function. Denotationally,
--   we have
--   
--   <pre>
--   prescanl f e = Prelude.fst . scanl' f e
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; let vec = fromList (Z:.10) [1..10]
--   
--   &gt;&gt;&gt; prescanl (+) 0 (use vec)
--   Vector (Z :. 10) [0,0,1,3,6,10,15,21,28,36]
--   </pre>
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 postscan, a variant of <a>scanl1</a> with an initial
--   value. As with <a>scanl1</a>, the array must not be empty.
--   Denotationally, we have:
--   
--   <pre>
--   postscanl f e = map (e `f`) . scanl1 f
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; let vec = fromList (Z:.10) [1..10]
--   
--   &gt;&gt;&gt; postscanl (+) 42 (use vec)
--   Vector (Z :. 10) [42,43,45,48,52,57,63,70,78,87]
--   </pre>
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 prescan (aka exclusive scan). As for <tt>scan</tt>, the
--   first argument must be an <i>associative</i> function. Denotationally,
--   we have
--   
--   <pre>
--   prescanr f e = Prelude.fst . scanr' f e
--   </pre>
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 <a>scanr1</a> with an initial
--   value. Denotationally, we have
--   
--   <pre>
--   postscanr f e = map (e `f`) . scanr1 f
--   </pre>
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 <a>scanl</a> along the innermost dimension of an
--   array. The innermost dimension must have at least as many elements as
--   the sum of the segment descriptor.
--   
--   <pre>
--   &gt;&gt;&gt; let seg = fromList (Z:.4) [1,4,0,3]
--   
--   &gt;&gt;&gt; seg
--   Vector (Z :. 4) [1,4,0,3]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; let mat = fromList (Z:.5:.10) [0..]
--   
--   &gt;&gt;&gt; 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]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; 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]
--   </pre>
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 <a>scanl1</a> along the innermost dimension.
--   
--   As with <a>scanl1</a>, the total number of elements considered, in
--   this case given by the <a>sum</a> 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:
--   
--   <pre>
--   scanl1Seg f xs [n,0,0] == scanl1Seg f xs [n]   where n /= 0
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; let seg = fromList (Z:.4) [1,4,0,3]
--   
--   &gt;&gt;&gt; seg
--   Vector (Z :. 4) [1,4,0,3]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; let mat = fromList (Z:.5:.10) [0..]
--   
--   &gt;&gt;&gt; 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]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; 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]
--   </pre>
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 <a>scanl'</a> 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.
--   
--   <pre>
--   &gt;&gt;&gt; let seg = fromList (Z:.4) [1,4,0,3]
--   
--   &gt;&gt;&gt; seg
--   Vector (Z :. 4) [1,4,0,3]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; let mat = fromList (Z:.5:.10) [0..]
--   
--   &gt;&gt;&gt; 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]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; let (res,sums) = scanl'Seg (+) 0 (use mat) (use seg)
--   
--   &gt;&gt;&gt; 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]
--   
--   &gt;&gt;&gt; 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]
--   </pre>
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 <a>prescanl</a>.
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 <a>postscanl</a>.
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 <a>scanr</a> along the innermost dimension of an
--   array. The innermost dimension must have at least as many elements as
--   the sum of the segment descriptor.
--   
--   <pre>
--   &gt;&gt;&gt; let seg = fromList (Z:.4) [1,4,0,3]
--   
--   &gt;&gt;&gt; seg
--   Vector (Z :. 4) [1,4,0,3]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; let mat = fromList (Z:.5:.10) [0..]
--   
--   &gt;&gt;&gt; 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]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; 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]
--   </pre>
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 <a>scanr1</a>.
--   
--   <pre>
--   &gt;&gt;&gt; let seg = fromList (Z:.4) [1,4,0,3]
--   
--   &gt;&gt;&gt; seg
--   Vector (Z :. 4) [1,4,0,3]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; let mat = fromList (Z:.5:.10) [0..]
--   
--   &gt;&gt;&gt; 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]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; 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]
--   </pre>
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 <a>scanr'</a>.
--   
--   <pre>
--   &gt;&gt;&gt; let seg = fromList (Z:.4) [1,4,0,3]
--   
--   &gt;&gt;&gt; seg
--   Vector (Z :. 4) [1,4,0,3]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; let mat = fromList (Z:.5:.10) [0..]
--   
--   &gt;&gt;&gt; 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]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; let (res,sums) = scanr'Seg (+) 0 (use mat) (use seg)
--   
--   &gt;&gt;&gt; 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]
--   
--   &gt;&gt;&gt; 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]
--   </pre>
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 <a>prescanr</a>.
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 <a>postscanr</a>.
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 <a>map</a>, the domain of
--   a stencil function is an entire <i>neighbourhood</i> 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:
--   
--   <pre>
--   s31 :: Stencil3 a -&gt; Exp a
--   s31 (l,c,r) = ...
--   </pre>
--   
--   ...where <tt>c</tt> is the focal point of the stencil, and <tt>l</tt>
--   and <tt>r</tt> represent the elements to the left and right of the
--   focal point, respectively. Similarly, a 3x3 stencil for a
--   two-dimensional array:
--   
--   <pre>
--   s33 :: Stencil3x3 a -&gt; Exp a
--   s33 ((_,t,_)
--   </pre>
--   
--   ,(l,c,r) ,(_,b,_)) = ...
--   
--   ...where <tt>c</tt> is again the focal point and <tt>t</tt>,
--   <tt>b</tt>, <tt>l</tt> and <tt>r</tt> 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 <a>Gaussian blur</a> as a
--   separable 2-pass operation.
--   
--   <pre>
--   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 =&gt; [Exp a] -&gt; Stencil5x1 a -&gt; Exp a
--   convolve5x1 kernel (_, (a,b,c,d,e), _)
--     = Prelude.sum $ Prelude.zipWith (*) kernel [a,b,c,d,e]
--   
--   convolve1x5 :: Num a =&gt; [Exp a] -&gt; Stencil1x5 a -&gt; 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 =&gt; Acc (Array DIM2 a) -&gt; Acc (Array DIM2 a)
--   blur = stencil (convolve5x1 gaussian) Clamp
--        . stencil (convolve1x5 gaussian) Clamp
--   </pre>
stencil :: (Stencil sh a stencil, Elt b) => (stencil -> Exp b) -> Boundary 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 <a>zipWith</a>.
stencil2 :: (Stencil sh a stencil1, Stencil sh b stencil2, Elt c) => (stencil1 -> stencil2 -> Exp c) -> Boundary a -> Acc (Array sh a) -> Boundary b -> Acc (Array sh b) -> Acc (Array sh c)
class (Elt (StencilRepr sh stencil), Stencil sh a (StencilRepr sh stencil)) => Stencil sh a stencil

-- | Boundary condition specification for stencil operations.
data Boundary a

-- | clamp coordinates to the extent of the array
Clamp :: Boundary a

-- | mirror coordinates beyond the array extent
Mirror :: Boundary a

-- | wrap coordinates around on each dimension
Wrap :: Boundary a

-- | use a constant value for outlying coordinates
Constant :: a -> Boundary a
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 <a>Exp</a> represents embedded scalar expressions. The
--   collective operations of Accelerate <a>Acc</a> consist of many scalar
--   expressions executed in data-parallel.
--   
--   Note that scalar expressions can not initiate new collective
--   operations: doing so introduces <i>nested data parallelism</i>, which
--   is difficult to execute efficiently on constrained hardware such as
--   GPUs, and is thus currently unsupported.
data Exp t

-- | The <a>Eq</a> class defines equality <a>==</a> and inequality
--   <a>/=</a> for scalar Accelerate expressions.
--   
--   For convenience, we include <a>Elt</a> as a superclass.
class Elt a => Eq a where x == y = mkLNot (x /= y) x /= y = mkLNot (x == y)
(==) :: Eq a => Exp a -> Exp a -> Exp Bool
(/=) :: Eq a => Exp a -> Exp a -> Exp Bool

-- | The <a>Ord</a> class for totally ordered datatypes
class Eq a => Ord a where x < y = x /= y && x <= y x > y = not (x <= y) x <= y = not (x > y) x >= y = x == y || not (x <= y) min x y = Exp $ Cond (x <= y) x y max x y = Exp $ Cond (x <= y) y x
(<) :: 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

-- | 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

-- | Basic numeric class
type Num a = (Elt a, Num (Exp a))
(+) :: Num a => a -> a -> a
(-) :: Num a => a -> a -> a
(*) :: Num a => a -> a -> a

-- | Unary negation.
negate :: Num a => a -> a

-- | Absolute value.
abs :: Num a => a -> a

-- | Sign of a number. The functions <a>abs</a> and <a>signum</a> should
--   satisfy the law:
--   
--   <pre>
--   abs x * signum x == x
--   </pre>
--   
--   For real numbers, the <a>signum</a> is either <tt>-1</tt> (negative),
--   <tt>0</tt> (zero) or <tt>1</tt> (positive).
signum :: Num a => a -> a

-- | Conversion from an <a>Integer</a>. An integer literal represents the
--   application of the function <a>fromInteger</a> to the appropriate
--   value of type <a>Integer</a>, so such literals have type
--   <tt>(<a>Num</a> a) =&gt; a</tt>.
fromInteger :: Num a => Integer -> a

-- | Integral numbers, supporting integral division
type Integral a = (Enum a, Real a, Integral (Exp a))

-- | integer division truncated toward zero
quot :: Integral a => a -> a -> a

-- | integer remainder, satisfying
--   
--   <pre>
--   (x `quot` y)*y + (x `rem` y) == x
--   </pre>
rem :: Integral a => a -> a -> a

-- | integer division truncated toward negative infinity
div :: Integral a => a -> a -> a

-- | integer modulus, satisfying
--   
--   <pre>
--   (x `div` y)*y + (x `mod` y) == x
--   </pre>
mod :: Integral a => a -> a -> a

-- | simultaneous <a>quot</a> and <a>rem</a>
quotRem :: Integral a => a -> a -> (a, a)

-- | simultaneous <a>div</a> and <a>mod</a>
divMod :: Integral a => a -> a -> (a, a)

-- | Fractional numbers, supporting real division
type Fractional a = (Num a, Fractional (Exp a))

-- | fractional division
(/) :: Fractional a => a -> a -> a

-- | reciprocal fraction
recip :: Fractional a => a -> a

-- | Conversion from a <a>Rational</a> (that is <tt><a>Ratio</a>
--   <a>Integer</a></tt>). A floating literal stands for an application of
--   <a>fromRational</a> to a value of type <a>Rational</a>, so such
--   literals have type <tt>(<a>Fractional</a> a) =&gt; a</tt>.
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
logBase :: Floating a => a -> a -> a

-- | Extracting components of fractions.
class (Real a, Fractional a) => RealFrac a
properFraction :: (RealFrac a, Num b, ToFloating b a, IsIntegral b) => Exp a -> (Exp b, Exp a)

-- | <tt>truncate x</tt> returns the integer nearest <tt>x</tt> between
--   zero and <tt>x</tt>
truncate :: (RealFrac a, Elt b, IsIntegral b) => Exp a -> Exp b

-- | <tt><a>round</a> x</tt> returns the nearest integer to <tt>x</tt>; the
--   even integer if <tt>x</tt> is equidistant between two integers
round :: (RealFrac a, Elt b, IsIntegral b) => Exp a -> Exp b

-- | <tt><a>ceiling</a> x</tt> returns the least integer not less than
--   <tt>x</tt>
ceiling :: (RealFrac a, Elt b, IsIntegral b) => Exp a -> Exp b

-- | <tt><a>floor</a> x</tt> returns the greatest integer not greater than
--   <tt>x</tt>
floor :: (RealFrac a, Elt b, IsIntegral b) => Exp a -> Exp b

-- | Generalisation of <a>div</a> to any instance of <a>RealFrac</a>
div' :: (RealFrac a, Elt b, IsIntegral b) => Exp a -> Exp a -> Exp b

-- | Generalisation of <a>mod</a> to any instance of <a>RealFrac</a>
mod' :: (Floating a, RealFrac a, ToFloating Int a) => Exp a -> Exp a -> Exp a

-- | Generalisation of <a>divMod</a> to any instance of <a>RealFrac</a>
divMod' :: (Floating a, RealFrac a, Num b, IsIntegral 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 where floatRadix _ = fromInteger (floatRadix (undefined :: a)) floatDigits _ = constant (floatDigits (undefined :: a)) floatRange _ = let (m, n) = floatRange (undefined :: a) in (constant m, constant n) isIEEE _ = constant (isIEEE (undefined :: Float)) decodeFloat = ((\ format_a7UjZ kind_a7Uk0 fn_a7Uk1 msg_a7Uk2 -> error (format_a7UjZ kind_a7Uk0 (call fn_a7Uk1 msg_a7Uk2))) (\ kind_a7Uk3 msg_a7Uk4 -> message kind_a7Uk3 ("Data/Array/Accelerate/Classes/RealFloat.hs:99:21: " ++ msg_a7Uk4)) Internal) "RealFloat.decodeFloat" "Not implemented yet" encodeFloat = ((\ format_a7Uk8 kind_a7Uk9 fn_a7Uka msg_a7Ukb -> error (format_a7Uk8 kind_a7Uk9 (call fn_a7Uka msg_a7Ukb))) (\ kind_a7Ukc msg_a7Ukd -> message kind_a7Ukc ("Data/Array/Accelerate/Classes/RealFloat.hs:100:21: " ++ msg_a7Ukd)) Internal) "RealFloat.encodeFloat" "Not implemented yet" exponent = ((\ format_a7Ukh kind_a7Uki fn_a7Ukj msg_a7Ukk -> error (format_a7Ukh kind_a7Uki (call fn_a7Ukj msg_a7Ukk))) (\ kind_a7Ukl msg_a7Ukm -> message kind_a7Ukl ("Data/Array/Accelerate/Classes/RealFloat.hs:101:21: " ++ msg_a7Ukm)) Internal) "RealFloat.exponent" "Not implemented yet" significand = ((\ format_a7Ukq kind_a7Ukr fn_a7Uks msg_a7Ukt -> error (format_a7Ukq kind_a7Ukr (call fn_a7Uks msg_a7Ukt))) (\ kind_a7Uku msg_a7Ukv -> message kind_a7Uku ("Data/Array/Accelerate/Classes/RealFloat.hs:102:21: " ++ msg_a7Ukv)) Internal) "RealFloat.significand" "Not implemented yet" scaleFloat = ((\ format_a7Ukz kind_a7UkA fn_a7UkB msg_a7UkC -> error (format_a7Ukz kind_a7UkA (call fn_a7UkB msg_a7UkC))) (\ kind_a7UkD msg_a7UkE -> message kind_a7UkD ("Data/Array/Accelerate/Classes/RealFloat.hs:103:21: " ++ msg_a7UkE)) Internal) "RealFloat.scaleFloat" "Not implemented yet" isInfinite = ((\ format_a7UkI kind_a7UkJ fn_a7UkK msg_a7UkL -> error (format_a7UkI kind_a7UkJ (call fn_a7UkK msg_a7UkL))) (\ kind_a7UkM msg_a7UkN -> message kind_a7UkM ("Data/Array/Accelerate/Classes/RealFloat.hs:104:21: " ++ msg_a7UkN)) Internal) "RealFloat.isInfinite" "Not implemented yet" isDenormalized = ((\ format_a7UkR kind_a7UkS fn_a7UkT msg_a7UkU -> error (format_a7UkR kind_a7UkS (call fn_a7UkT msg_a7UkU))) (\ kind_a7UkV msg_a7UkW -> message kind_a7UkV ("Data/Array/Accelerate/Classes/RealFloat.hs:105:21: " ++ msg_a7UkW)) Internal) "RealFloat.isDenormalized" "Not implemented yet" isNegativeZero = ((\ format_a7Ul0 kind_a7Ul1 fn_a7Ul2 msg_a7Ul3 -> error (format_a7Ul0 kind_a7Ul1 (call fn_a7Ul2 msg_a7Ul3))) (\ kind_a7Ul4 msg_a7Ul5 -> message kind_a7Ul4 ("Data/Array/Accelerate/Classes/RealFloat.hs:106:21: " ++ msg_a7Ul5)) Internal) "RealFloat.isNegativeZero" "Not implemented yet"

-- | 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 <a>floatRadix</a> in the significand
--   (constant)
floatDigits :: RealFloat a => Exp a -> Exp Int

-- | The number of digits of <a>floatRadix</a> 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
--   <tt>(m,n) = <a>decodeFloat</a> x</tt> then <tt>x = m*b^^n</tt>, where
--   <tt>b</tt> is the floating-point radix (<a>floatRadix</a>).
--   Furthermore, either <tt>m</tt> and <tt>n</tt> are both zero, or
--   <tt>b^(d-1) &lt;= <tt>abs</tt> m &lt; b^d</tt>, where <tt>d =
--   <a>floatDigits</a> x</tt>.
decodeFloat :: RealFloat a => Exp a -> (Exp Int64, Exp Int)

-- | Inverse of <a>decodeFloat</a>
encodeFloat :: RealFloat a => Exp Int64 -> Exp Int -> Exp a

-- | Corresponds to the second component of <a>decodeFloat</a>
exponent :: RealFloat a => Exp a -> Exp Int

-- | Corresponds to the first component of <a>decodeFloat</a>
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

-- | <a>True</a> if the argument is an IEEE "not-a-number" (NaN) value
isNaN :: RealFloat a => Exp a -> Exp Bool

-- | <a>True</a> if the argument is an IEEE infinity or negative-infinity
isInfinite :: RealFloat a => Exp a -> Exp Bool

-- | <a>True</a> if the argument is too small to be represented in
--   normalized format
isDenormalized :: RealFloat a => Exp a -> Exp Bool

-- | <a>True</a> if the argument is an IEEE negative zero
isNegativeZero :: RealFloat a => Exp a -> Exp Bool

-- | <a>True</a> if the argument is an IEEE floating point number
isIEEE :: RealFloat a => Exp a -> Exp Bool

-- | <a>True</a> 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 <tt>x</tt> and <tt>y</tt>, <tt><a>atan2</a> y x</tt>
--   computes the angle (from the positive x-axis) of the vector from the
--   origin to the point <tt>(x,y)</tt>. <tt><a>atan2</a> y x</tt> returns
--   a value in the range [<tt>-pi</tt>, <tt>pi</tt>].
atan2 :: RealFloat a => Exp a -> Exp a -> Exp a

-- | Accelerate lacks a most-general lossless <a>Integer</a> type, which
--   the standard <a>fromIntegral</a> 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 <a>Rational</a> type, which
--   the standard <a>realToFrac</a> uses as an intermediate value when
--   coercing to floating-point types. Instead, we use this class to
--   capture a direct coercion between to 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 <tt>e</tt> which can be lifted into <tt>c</tt>.
class Lift c e where type Plain e where {
    type family Plain e;
}

-- | Lift the given value into a surface type <tt>c</tt> --- either
--   <a>Exp</a> for scalar expressions or <a>Acc</a> for array
--   computations. The value may already contain subexpressions in
--   <tt>c</tt>.
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 <a>Exp</a>.
lift1 :: (Unlift Exp a, Lift Exp b) => (a -> b) -> Exp (Plain a) -> Exp (Plain b)

-- | Lift a binary function into <a>Exp</a>.
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 <a>Exp</a>.
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

-- | 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 :: Elt t => t -> Exp t

-- | Extract the first component of a scalar pair.
fst :: forall a b. (Elt a, Elt b) => Exp (a, b) -> Exp a

-- | Extract the first component of an array pair.
afst :: forall a b. (Arrays a, Arrays b) => Acc (a, b) -> Acc a

-- | Extract the second component of a scalar pair.
snd :: forall a b. (Elt a, Elt b) => Exp (a, b) -> Exp b

-- | Extract the second component of an array pair
asnd :: forall a b. (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 <a>cond</a>. If the predicate evaluates to
--   <a>True</a>, the first component of the tuple is returned, else the
--   second.
--   
--   See also: <a>ifThenElse</a>.
(?) :: Elt t => Exp Bool -> (Exp t, Exp t) -> Exp t
infix 0 ?

-- | A case-like control structure
caseof :: (Elt a, Elt b) => Exp a -> [(Exp a -> Exp Bool, Exp b)] -> Exp b -> Exp b

-- | A scalar-level if-then-else construct.
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 <a>False</a>.
while :: Elt e => (Exp e -> Exp Bool) -> (Exp e -> Exp e) -> Exp e -> Exp e

-- | Repeatedly apply a function a fixed number of times
iterate :: forall a. Elt a => Exp Int -> (Exp a -> Exp a) -> Exp a -> Exp a

-- | Reduce along an innermost slice of an array <i>sequentially</i>, by
--   applying a binary operator to a starting value and the array from left
--   to right.
sfoldl :: forall sh a b. (Shape sh, Slice 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

-- | <a>subtract</a> is the same as <tt><tt>flip</tt> (<a>-</a>)</tt>.
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

-- | <tt><a>gcd</a> x y</tt> is the non-negative factor of both <tt>x</tt>
--   and <tt>y</tt> of which every common factor of both <tt>x</tt> and
--   <tt>y</tt> is also a factor; for example:
--   
--   <pre>
--   &gt;&gt;&gt; gcd 4 2 = 2
--   
--   &gt;&gt;&gt; gcd (-4) 6 = 2
--   
--   &gt;&gt;&gt; gcd 0 4 = 4
--   
--   &gt;&gt;&gt; gcd 0 0 = 0
--   </pre>
--   
--   That is, the common divisor that is "greatest" in the divisibility
--   preordering.
gcd :: Integral a => Exp a -> Exp a -> Exp a

-- | <tt><a>lcm</a> x y</tt> is the smallest positive integer that both
--   <tt>x</tt> and <tt>y</tt> 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 <a>Int</a> expression into a rank-1 indexing expression.
index1 :: Elt i => Exp i -> Exp (Z :. i)

-- | Turn a rank-1 indexing expression into an <a>Int</a> expression.
unindex1 :: Elt i => Exp (Z :. i) -> Exp i

-- | Creates a rank-2 index from two Exp Int`s
index2 :: (Elt i, Slice (Z :. i)) => Exp i -> Exp i -> Exp ((Z :. i) :. i)

-- | Destructs a rank-2 index to an Exp tuple of two Int`s.
unindex2 :: forall i. (Elt i, Slice (Z :. i)) => Exp ((Z :. i) :. i) -> Exp (i, i)

-- | Create a rank-3 index from three Exp Int`s
index3 :: (Elt i, Slice (Z :. i), Slice ((Z :. i) :. 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 :: forall i. (Elt i, Slice (Z :. i), Slice ((Z :. i) :. i)) => Exp (((Z :. i) :. i) :. i) -> Exp (i, i, i)

-- | Get the innermost dimension of a shape
indexHead :: (Slice sh, Elt a) => Exp (sh :. a) -> Exp a

-- | Get all but the innermost element of a shape
indexTail :: (Slice sh, Elt a) => Exp (sh :. a) -> Exp sh

-- | Map a multi-dimensional index into a linear, row-major representation
--   of an array.
toIndex :: Shape sh => Exp sh -> Exp sh -> Exp Int

-- | Inverse of <a>toIndex</a>
fromIndex :: Shape sh => Exp sh -> Exp Int -> Exp sh

-- | Intersection of two shapes
intersect :: Shape sh => Exp sh -> Exp sh -> Exp sh

-- | Convert a character to an <a>Int</a>.
ord :: Exp Char -> Exp Int

-- | Convert an <a>Int</a> into a character.
chr :: Exp Int -> Exp Char

-- | Convert a Boolean value to an <a>Int</a>, where <a>False</a> turns
--   into '0' and <a>True</a> 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 a, IsScalar b, BitSizeEq a 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 of 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 <a>accelerate-fft</a> package.
foreignAcc :: (Arrays as, Arrays bs, Foreign asm) => asm (as -> 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 <a>foreignAcc</a>, the fallback implementation itself may be a
--   (sequence of) foreign implementation(s) for a different backend(s), or
--   implemented purely in Accelerate.
foreignExp :: (Elt x, Elt y, Foreign asm) => asm (x -> y) -> (Exp x -> Exp y) -> Exp x -> Exp y

-- | Rank of an array.
arrayRank :: Shape sh => sh -> Int

-- | Array shape in plain Haskell code.
arrayShape :: Shape sh => Array sh e -> sh

-- | Total number of elements in an array of the given <a>Shape</a>.
arraySize :: Shape sh => sh -> Int

-- | Array indexing in plain Haskell code.
indexArray :: Array sh e -> sh -> 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

-- | Convert elements of a list into an Accelerate <a>Array</a>.
--   
--   This will generate a new multidimensional <a>Array</a> of the
--   specified shape and extent by consuming elements from the list and
--   adding them to the array in row-major order.
--   
--   <pre>
--   &gt;&gt;&gt; fromList (Z:.10) [0..] :: Vector Int
--   Vector (Z :. 10) [0,1,2,3,4,5,6,7,8,9]
--   </pre>
--   
--   Note that we pull elements off the list lazily, so infinite lists are
--   accepted:
--   
--   <pre>
--   &gt;&gt;&gt; fromList (Z:.5:.10) (repeat 0) :: Array DIM2 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]
--   </pre>
--   
--   You can also make use of the <tt>OverloadedLists</tt> extension to
--   produce one-dimensional vectors from a <i>finite</i> list.
--   
--   <pre>
--   &gt;&gt;&gt; [0..9] :: Vector Int
--   Vector (Z :. 10) [0,1,2,3,4,5,6,7,8,9]
--   </pre>
--   
--   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 :: (Shape sh, Elt e) => sh -> [e] -> Array sh e

-- | Convert an accelerated <a>Array</a> to a list in row-major order.
toList :: forall sh e. Array sh e -> [e]

-- | Function composition.
(.) :: (b -> c) -> (a -> b) -> a -> c
infixr 9 .

-- | Application operator. This operator is redundant, since ordinary
--   application <tt>(f x)</tt> means the same as <tt>(f <a>$</a> x)</tt>.
--   However, <a>$</a> has low, right-associative binding precedence, so it
--   sometimes allows parentheses to be omitted; for example:
--   
--   <pre>
--   f $ g $ h x  =  f (g (h x))
--   </pre>
--   
--   It is also useful in higher-order situations, such as <tt><a>map</a>
--   (<a>$</a> 0) xs</tt>, or <tt><a>zipWith</a> (<a>$</a>) fs xs</tt>.
($) :: (a -> b) -> a -> b
infixr 0 $

-- | <a>error</a> stops execution and displays an error message.
error :: HasCallStack => [Char] -> a

-- | A special case of <a>error</a>. It is expected that compilers will
--   recognize this and insert error messages which are more appropriate to
--   the context in which <a>undefined</a> appears.
undefined :: HasCallStack => a

-- | <tt>const x</tt> is a unary function which evaluates to <tt>x</tt> for
--   all inputs.
--   
--   For instance,
--   
--   <pre>
--   &gt;&gt;&gt; map (const 42) [0..3]
--   [42,42,42,42]
--   </pre>
const :: a -> b -> a

-- | A fixed-precision integer type with at least the range <tt>[-2^29 ..
--   2^29-1]</tt>. The exact range for a given implementation can be
--   determined by using <a>minBound</a> and <a>maxBound</a> from the
--   <a>Bounded</a> 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 <a>Word</a> is an unsigned integral type, with the same size as
--   <a>Int</a>.
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 :: *

-- | 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

-- | The character type <a>Char</a> is an enumeration whose values
--   represent Unicode (or equivalently ISO/IEC 10646) characters (see
--   <a>http://www.unicode.org/</a> 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 <a>Char</a>.
--   
--   To convert a <a>Char</a> to or from the corresponding <a>Int</a> value
--   defined by Unicode, use <a>toEnum</a> and <a>fromEnum</a> from the
--   <a>Enum</a> class respectively (or equivalently <tt>ord</tt> and
--   <tt>chr</tt>).
data Char :: *

-- | Haskell type representing the C <tt>float</tt> type.
data CFloat :: *

-- | Haskell type representing the C <tt>double</tt> type.
data CDouble :: *

-- | Haskell type representing the C <tt>short</tt> type.
data CShort :: *

-- | Haskell type representing the C <tt>unsigned short</tt> type.
data CUShort :: *

-- | Haskell type representing the C <tt>int</tt> type.
data CInt :: *

-- | Haskell type representing the C <tt>unsigned int</tt> type.
data CUInt :: *

-- | Haskell type representing the C <tt>long</tt> type.
data CLong :: *

-- | Haskell type representing the C <tt>unsigned long</tt> type.
data CULong :: *

-- | Haskell type representing the C <tt>long long</tt> type.
data CLLong :: *

-- | Haskell type representing the C <tt>unsigned long long</tt> type.
data CULLong :: *

-- | Haskell type representing the C <tt>char</tt> type.
data CChar :: *

-- | Haskell type representing the C <tt>signed char</tt> type.
data CSChar :: *

-- | Haskell type representing the C <tt>unsigned char</tt> type.
data CUChar :: *

-- | All scalar types
class Typeable a => IsScalar a

-- | Numeric types
class (Num a, IsScalar a) => IsNum a

-- | Bounded types
class IsBounded a

-- | Integral types
class (IsScalar a, IsNum a, IsBounded a) => IsIntegral a

-- | Floating types
class (Floating a, IsScalar a, IsNum a) => IsFloating a

-- | Non-numeric types
class IsNonNum a


-- | 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 laws:
--   
--   <ul>
--   <li><pre>mappend mempty x = x</pre></li>
--   <li><pre>mappend x mempty = x</pre></li>
--   <li><pre>mappend x (mappend y z) = mappend (mappend x y) z</pre></li>
--   <li><pre>mconcat = <a>foldr</a> mappend mempty</pre></li>
--   </ul>
--   
--   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
--   <tt>newtype</tt>s and make those instances of <a>Monoid</a>, e.g.
--   <tt>Sum</tt> and <tt>Product</tt>.
class Monoid a

-- | Identity of <a>mappend</a>
mempty :: Monoid a => a

-- | An associative operation
mappend :: Monoid a => a -> a -> a

-- | Fold a list using the monoid. For most types, the default definition
--   for <a>mconcat</a> will be used, but the function is included in the
--   class definition so that an optimized version can be provided for
--   specific types.
mconcat :: Monoid a => [a] -> a

-- | An infix synonym for <a>mappend</a>.
(<>) :: Monoid m => m -> m -> m
infixr 6 <>

-- | Monoid under addition.
newtype Sum a :: * -> *
Sum :: a -> Sum a
[getSum] :: Sum a -> a

-- | Monoid under multiplication.
newtype Product a :: * -> *
Product :: a -> Product a
[getProduct] :: Product a -> a
instance Data.Array.Accelerate.Array.Sugar.Elt a => Data.Array.Accelerate.Array.Sugar.Elt (Data.Monoid.Sum a)
instance Data.Array.Accelerate.Array.Sugar.Elt a => Data.Array.Accelerate.Product.IsProduct Data.Array.Accelerate.Array.Sugar.Elt (Data.Monoid.Sum a)
instance (Data.Array.Accelerate.Lift.Lift Data.Array.Accelerate.Smart.Exp a, Data.Array.Accelerate.Array.Sugar.Elt (Data.Array.Accelerate.Lift.Plain a)) => Data.Array.Accelerate.Lift.Lift Data.Array.Accelerate.Smart.Exp (Data.Monoid.Sum a)
instance Data.Array.Accelerate.Array.Sugar.Elt a => Data.Array.Accelerate.Lift.Unlift Data.Array.Accelerate.Smart.Exp (Data.Monoid.Sum (Data.Array.Accelerate.Smart.Exp a))
instance Data.Array.Accelerate.Classes.Num.Num a => GHC.Base.Monoid (Data.Array.Accelerate.Smart.Exp (Data.Monoid.Sum a))
instance Data.Array.Accelerate.Classes.Num.Num a => GHC.Num.Num (Data.Array.Accelerate.Smart.Exp (Data.Monoid.Sum a))
instance Data.Array.Accelerate.Classes.Eq.Eq a => Data.Array.Accelerate.Classes.Eq.Eq (Data.Monoid.Sum a)
instance Data.Array.Accelerate.Classes.Ord.Ord a => Data.Array.Accelerate.Classes.Ord.Ord (Data.Monoid.Sum a)
instance Data.Array.Accelerate.Array.Sugar.Elt a => Data.Array.Accelerate.Array.Sugar.Elt (Data.Monoid.Product a)
instance Data.Array.Accelerate.Array.Sugar.Elt a => Data.Array.Accelerate.Product.IsProduct Data.Array.Accelerate.Array.Sugar.Elt (Data.Monoid.Product a)
instance (Data.Array.Accelerate.Lift.Lift Data.Array.Accelerate.Smart.Exp a, Data.Array.Accelerate.Array.Sugar.Elt (Data.Array.Accelerate.Lift.Plain a)) => Data.Array.Accelerate.Lift.Lift Data.Array.Accelerate.Smart.Exp (Data.Monoid.Product a)
instance Data.Array.Accelerate.Array.Sugar.Elt a => Data.Array.Accelerate.Lift.Unlift Data.Array.Accelerate.Smart.Exp (Data.Monoid.Product (Data.Array.Accelerate.Smart.Exp a))
instance Data.Array.Accelerate.Classes.Num.Num a => GHC.Base.Monoid (Data.Array.Accelerate.Smart.Exp (Data.Monoid.Product a))
instance Data.Array.Accelerate.Classes.Num.Num a => GHC.Num.Num (Data.Array.Accelerate.Smart.Exp (Data.Monoid.Product a))
instance Data.Array.Accelerate.Classes.Eq.Eq a => Data.Array.Accelerate.Classes.Eq.Eq (Data.Monoid.Product a)
instance Data.Array.Accelerate.Classes.Ord.Ord a => Data.Array.Accelerate.Classes.Ord.Ord (Data.Monoid.Product a)
instance GHC.Base.Monoid (Data.Array.Accelerate.Smart.Exp ())
instance (Data.Array.Accelerate.Array.Sugar.Elt a, Data.Array.Accelerate.Array.Sugar.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.Array.Sugar.Elt a, Data.Array.Accelerate.Array.Sugar.Elt b, Data.Array.Accelerate.Array.Sugar.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.Array.Sugar.Elt a, Data.Array.Accelerate.Array.Sugar.Elt b, Data.Array.Accelerate.Array.Sugar.Elt c, Data.Array.Accelerate.Array.Sugar.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.Array.Sugar.Elt a, Data.Array.Accelerate.Array.Sugar.Elt b, Data.Array.Accelerate.Array.Sugar.Elt c, Data.Array.Accelerate.Array.Sugar.Elt d, Data.Array.Accelerate.Array.Sugar.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))


-- | Combine folds in <a>Applicative</a> 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].
--   
--   <ol>
--   
--   <li><a>http://squing.blogspot.com/2008/11/beautiful-folding.html</a></li>
--   <li><a>https://www.youtube.com/watch?v=6a5Ti0r8Q2s</a></li>
--   </ol>
module Data.Array.Accelerate.Data.Fold

-- | <a>Fold</a> describes how to process data of some <tt>i</tt>nput type
--   into some <tt>o</tt>utput type, via a reduction using some
--   intermediate Monoid <tt>w</tt>. For example, both <tt>sum</tt> and
--   <tt>length</tt> below use the <a>Sum</a> monoid:
--   
--   <pre>
--   &gt;&gt;&gt; let sum = Fold (lift . Sum) (getSum . unlift)
--   
--   &gt;&gt;&gt; let length = Fold (\_ -&gt; 1) (getSum . unlift)
--   </pre>
--   
--   The key is that <a>Fold</a>s can be combined using <a>Applicative</a>
--   in order to produce multiple outputs from a <i>single</i> reduction of
--   the array. For example:
--   
--   <pre>
--   &gt;&gt;&gt; let average = (/) &lt;$&gt; sum &lt;*&gt; length
--   </pre>
--   
--   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 <a>Fold</a> has some numeric instances, this can also be
--   defined more succinctly as:
--   
--   <pre>
--   &gt;&gt;&gt; let average = sum / length
--   </pre>
--   
--   A more complex example:
--   
--   <pre>
--   &gt;&gt;&gt; let sumOfSquares = Fold (lift . Sum . (^2)) (getSum . unlift)
--   
--   &gt;&gt;&gt; let standardDeviation = sqrt ((sumOfSquares / length) - (sum / length) ^ 2)
--   </pre>
--   
--   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 <a>Fold</a> 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))
