-- Hoogle documentation, generated by Haddock -- See Hoogle, http://www.haskell.org/hoogle/ -- | An embedded language for accelerated array processing -- -- Data.Array.Accelerate defines an embedded array language for -- computations for high-performance computing in Haskell. Computations -- on multi-dimensional, regular arrays are expressed in the form of -- parameterised collective operations, such as maps, reductions, and -- permutations. These computations may then be online compiled and -- executed on a range of architectures. -- -- -- -- As a simple example, consider the computation of a dot product of two -- vectors of floating point numbers: -- -- 
--   dotp :: Acc (Vector Float) -> Acc (Vector Float) -> Acc (Scalar Float)
--   dotp xs ys = fold (+) 0 (zipWith (*) xs ys)
--
-- -- Except for the type, this code is almost the same as the corresponding -- Haskell code on lists of floats. The types indicate that the -- computation may be online-compiled for performance – for example, -- using Data.Array.Accelerate.CUDA it may be on-the-fly -- off-loaded to the GPU. -- -- -- -- Currently, there are two backends: -- --
    --
  1. An interpreter that serves as a reference implementation of the -- intended semantics of the language, which is included in this -- package.
    2. --
  2. A CUDA backend generating code for CUDA-capable NVIDIA GPUs: -- http://hackage.haskell.org/package/accelerate-cuda
    3. --
-- -- Several experimental and/or incomplete backends also exist. If you are -- interested in helping finish these, please contact us. -- --
    --
  1. Cilk/ICC and OpenCL: -- https://github.com/AccelerateHS/accelerate-backend-kit
    2. --
  2. Another OpenCL backend: -- https://github.com/HIPERFIT/accelerate-opencl
    3. --
  3. A backend to the Repa array library: -- https://github.com/blambo/accelerate-repa
    4. --
-- -- -- -- The following support packages are available: -- --
    --
  1. accelerate-cuda: A high-performance parallel backend -- targeting CUDA-enabled NVIDIA GPUs. Requires the NVIDIA CUDA SDK and, -- for full functionality, hardware with compute capability 1.2 or -- greater. See the table on Wikipedia for supported GPUs: -- http://en.wikipedia.org/wiki/CUDA#Supported_GPUs
    2. --
  2. accelerate-examples: Computational kernels and -- applications showcasing Accelerate, as well as performance and -- regression tests.
    3. --
  3. accelerate-io: Fast conversion between Accelerate -- arrays and other formats, including Repa arrays.
    4. --
  4. accelerate-fft: Computation of Discrete Fourier -- Transforms.
    5. --
-- -- Install them from Hackage with cabal install PACKAGE -- -- -- -- Haddock documentation is included in the package, and a tutorial is -- available on the GitHub wiki: -- https://github.com/AccelerateHS/accelerate/wiki -- -- The accelerate-examples package demonstrates a range of -- computational kernels and several complete applications, including: -- -- -- -- -- -- -- -- -- -- @package accelerate @version 0.13.0.2 -- | 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. -- -- Surface types versus representation types -- -- As a general rule, we perform all computations on representation types -- and we store all data as values of representation types. To guarantee -- the type safety of the interpreter, this currently implies a lot of -- conversions between surface and representation types. Optimising the -- code by eliminating back and forth conversions is fine, but only where -- it doesn't negatively affects clarity — after all, the main purpose of -- the interpreter is to serve as an executable specification. module Data.Array.Accelerate.Interpreter -- | 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 -- | Stream a lazily read list of input arrays through the given program, -- collecting results as we go stream :: (Arrays a, Arrays b) => (Acc a -> Acc b) -> [a] -> [b] -- | This module defines an embedded language of array computations for -- high-performance computing. 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 executed on a range of -- architectures. -- -- -- -- The types representing array computations are only exported abstractly -- — i.e., 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. -- -- -- -- Access to the various backends is via a run function in -- backend-specific top level modules. Currently, we have the following: -- -- -- -- -- -- module Data.Array.Accelerate -- | Array-valued collective computations data Acc a class (Typeable (ArrRepr a), Typeable (ArrRepr' a), Typeable a) => Arrays a -- | Multi-dimensional arrays for array processing. -- -- If device and host memory are separate, arrays will be transferred to -- the device when necessary (if possible asynchronously and in parallel -- with other tasks) and cached on the device if sufficient memory is -- available. data Array sh e -- | 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 segment descriptor, which -- stores the lengths of the subarrays. type Segments i = Vector i -- | Accelerate supports as array elements only simple atomic types, and -- tuples thereof. These element types are stored efficiently in memory, -- unpacked as consecutive elements without pointers. -- -- This class characterises the types of values that can be array -- elements, and hence, appear in scalar Accelerate expressions. class (Show a, Typeable a, Typeable (EltRepr a), Typeable (EltRepr' a), ArrayElt (EltRepr a), ArrayElt (EltRepr' a)) => Elt a -- | Rank-0 index data Z Z :: Z -- | Increase an index rank by one dimension. The :. operator is -- used to construct both values and types. data (:.) tail head (:.) :: tail -> head -> :. tail head -- | Shapes and indices of multi-dimensional arrays class (Elt sh, Elt (Any sh), Shape (EltRepr sh)) => Shape sh where dim = dim . fromElt size = size . fromElt ignore = toElt ignore intersect sh1 sh2 = toElt (intersect (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 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 -- | Marker for entire dimensions in slice descriptors. -- -- For example, when used in slices passed to replicate, the -- occurrences of All indicate the dimensions into which the -- array's existing extent will be placed, rather than the new dimensions -- introduced by replication. data All All :: All -- | Marker for arbitrary shapes in slice descriptors. Such arbitrary -- shapes may include an unknown number of dimensions. -- -- Any can be used in the leftmost position of a slice instead of -- Z, for example (Any :. _ :. _). In the following -- definition Any is used to match against whatever shape the type -- variable sh takes: -- -- 
--   repN :: (Shape sh, Elt e) => Int -> Acc (Array sh e) -> Acc (Array (sh:.Int) e)
--   repN n a = replicate (constant $ Any :. n) a
--
data Any sh Any :: Any sh -- | Slices, aka generalised indices, as n-tuples and mappings of -- slice indices to slices, co-slices, and slice dimensions class (Elt sl, Shape (SliceShape sl), Shape (CoSliceShape sl), Shape (FullShape sl)) => Slice sl where type family SliceShape sl :: * type family CoSliceShape sl :: * type family FullShape sl :: * sliceIndex :: Slice sl => sl -> SliceIndex (EltRepr sl) (EltRepr (SliceShape sl)) (EltRepr (CoSliceShape sl)) (EltRepr (FullShape sl)) 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 -- | Expression form that extracts a scalar from an array (!) :: (Shape ix, Elt e) => Acc (Array ix e) -> Exp ix -> Exp e -- | Expression form that extracts a scalar from an array at a linear index (!!) :: (Shape ix, Elt e) => Acc (Array ix e) -> Exp Int -> Exp e -- | Extraction of the element in a singleton array the :: Elt e => Acc (Scalar e) -> Exp e -- | Test whether an array is empty null :: (Shape ix, Elt e) => Acc (Array ix e) -> Exp Bool -- | Expression form that yields the shape of an array shape :: (Shape ix, Elt e) => Acc (Array ix e) -> Exp ix -- | Expression form that yields the size of an array size :: (Shape ix, Elt e) => Acc (Array ix e) -> Exp Int -- | The total number of elements in an array of the given Shape shapeSize :: Shape ix => Exp ix -> Exp Int -- | Index an array with a generalised array index, supplied as the -- second argument. The result is a new array (possibly a singleton) -- containing the selected dimensions (Alls) in their entirety. -- -- This can be used to cut out entire dimensions. The opposite of -- replicate. For example, if mat is a two dimensional -- array, the following will select a specific row and yield a one -- dimensional result: -- -- 
--   slice mat (constant (Z :. (2::Int) :. All))
--
-- -- A fully specified index (with no Alls) would return a single -- element (zero dimensional array). slice :: (Slice slix, Elt e) => Acc (Array (FullShape slix) e) -> Exp slix -> Acc (Array (SliceShape slix) e) -- | Yield all but the last element of the input vector. The vector must -- not be empty. init :: Elt e => Acc (Vector e) -> Acc (Vector e) -- | Yield all but the first element of the input vector. The vector must -- not be empty. tail :: Elt e => Acc (Vector e) -> Acc (Vector e) -- | Yield the first n elements of the input vector. The vector -- must contain no more than n elements. take :: Elt e => Exp Int -> Acc (Vector e) -> Acc (Vector e) -- | Yield all but the first n elements of the input vector. The -- vector must contain no fewer than n elements. drop :: Elt e => Exp Int -> Acc (Vector e) -> Acc (Vector e) -- | Yield a slit (slice) from the vector. The vector must contain at least -- i + n elements. Denotationally, we have: -- -- 
--   slit i n = take n . drop i
--
slit :: Elt e => Exp Int -> Exp Int -> Acc (Vector e) -> Acc (Vector e) -- | Array inlet: makes an array available for processing using the -- Accelerate language. -- -- Depending upon the backend used to execute array computations, this -- may trigger (asynchronous) data transfer. use :: Arrays arrays => arrays -> Acc arrays -- | Scalar inlet: injects a scalar (or a tuple of scalars) into a -- singleton array for use in the Accelerate language. 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 -- (Vector) of three floating point numbers: -- -- 
--   generate (index1 3) (\_ -> 1.2)
--
-- -- Or, equivalently: -- -- 
--   generate (constant (Z :. (3::Int))) (\_ -> 1.2)
--
-- -- Finally, the following will create an array equivalent to '[1..10]': -- -- 
--   generate (index1 10) $ \ ix ->
--            let (Z :. i) = unlift ix
--            in fromIntegral i
--
generate :: (Shape ix, Elt a) => Exp ix -> (Exp ix -> Exp a) -> Acc (Array ix a) -- | Replicate an array across one or more dimensions as specified by the -- generalised array index provided as the first argument. -- -- For example, assuming arr is a vector (one-dimensional -- array), -- -- 
--   replicate (Z :.2 :.All :.3) arr
--
-- -- yields a three dimensional array, where arr is replicated -- twice across the first and three times across the third dimension. replicate :: (Slice slix, Elt e) => Exp slix -> Acc (Array (SliceShape slix) e) -> Acc (Array (FullShape slix) e) -- | 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 x, x+1, etc -- (in row-major order). enumFromN :: (Shape sh, Elt e, IsNum e) => Exp sh -> Exp e -> Acc (Array sh e) -- | Create an array of the given shape containing the values x, -- x+y, x+y+y etc. (in row-major order). enumFromStepN :: (Shape sh, Elt e, IsNum e) => Exp sh -> Exp e -> Exp e -> Acc (Array sh e) -- | Infix version of cond. (?|) :: Arrays a => Exp Bool -> (Acc a, Acc a) -> Acc a -- | An array-level if-then-else construct. cond :: Arrays a => Exp Bool -> Acc a -> Acc a -> Acc a -- | Pipelining of two array computations. -- -- Denotationally, we have -- -- 
--   (acc1 >-> acc2) arrs = let tmp = acc1 arrs in acc2 tmp
--
-- -- Operationally, the array computations acc1 and acc2 -- will not share any sub-computations, neither between each other nor -- with the environment. This makes them truly independent stages that -- only communicate by way of the result of acc1 which is being -- fed as an argument to acc2. (>->) :: (Arrays a, Arrays b, Arrays c) => (Acc a -> Acc b) -> (Acc b -> Acc c) -> (Acc a -> Acc c) -- | Change the shape of an array without altering its contents. The -- size of the source and result arrays must be identical. -- -- 
--   precondition: size ix == size ix'
--
reshape :: (Shape ix, Shape ix', Elt e) => Exp ix -> Acc (Array ix' e) -> Acc (Array ix e) -- | Flattens a given array of arbitrary dimension. flatten :: (Shape ix, Elt a) => Acc (Array ix a) -> Acc (Vector a) -- | Forward permutation specified by an index mapping. The result array is -- initialised with the given defaults and any further values that are -- permuted into the result array are added to the current value using -- the given combination function. -- -- The combination function must be associative. Elements that are -- mapped to the magic value ignore by the permutation function -- are dropped. permute :: (Shape ix, Shape ix', Elt a) => (Exp a -> Exp a -> Exp a) -> Acc (Array ix' a) -> (Exp ix -> Exp ix') -> Acc (Array ix a) -> Acc (Array ix' a) -- | Backward permutation specified by an index mapping from the -- destination array specifying which element of the source array to -- read. backpermute :: (Shape ix, Shape ix', Elt a) => Exp ix' -> (Exp ix' -> Exp ix) -> Acc (Array ix a) -> Acc (Array ix' a) -- | Magic value identifying elements that are ignored in a forward -- permutation. Note that this currently does not work for singleton -- arrays. ignore :: Shape ix => Exp ix -- | 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) -- | Apply the given function element-wise to the given array. map :: (Shape ix, Elt a, Elt b) => (Exp a -> Exp b) -> Acc (Array ix a) -> Acc (Array ix 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 ix, Elt a, Elt b, Elt c) => (Exp a -> Exp b -> Exp c) -> Acc (Array ix a) -> Acc (Array ix b) -> Acc (Array ix c) -- | Zip three arrays with the given function 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 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) -- | 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)) -- | The converse of zip, but the shape of the two results is -- identical to the shape of the argument. 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)) -- | Drop elements that do not satisfy the predicate filter :: Elt a => (Exp a -> Exp Bool) -> Acc (Vector a) -> Acc (Vector a) -- | Copy elements from source array to destination array according to a -- map. This is a forward-permute operation where a map vector -- encodes an input to output index mapping. Output elements for indices -- that are not mapped assume the default vector's value. -- -- For example: -- -- 
--   default = [0, 0, 0, 0, 0, 0, 0, 0, 0]
--   map     = [1, 3, 7, 2, 5, 8]
--   input   = [1, 9, 6, 4, 4, 2, 5]
--   
--   output  = [0, 1, 4, 9, 0, 4, 0, 6, 2]
--
-- -- Note if the same index appears in the map more than once, the result -- is undefined. The map vector cannot be larger than the input vector. scatter :: Elt e => Acc (Vector Int) -> Acc (Vector e) -> Acc (Vector e) -> Acc (Vector e) -- | Conditionally copy elements from source array to destination array -- according to a map. This is a forward-permute operation where a -- map vector encodes an input to output index mapping. In -- addition, there is a mask vector, and an associated predicate -- function, that specifies whether an elements will be copied. If not -- copied, the output array assumes the default vector's value. -- -- For example: -- -- 
--   default = [0, 0, 0, 0, 0, 0, 0, 0, 0]
--   map     = [1, 3, 7, 2, 5, 8]
--   mask    = [3, 4, 9, 2, 7, 5]
--   pred    = (> 4)
--   input   = [1, 9, 6, 4, 4, 2]
--   
--   output  = [0, 0, 0, 0, 0, 4, 0, 6, 2]
--
-- -- Note if the same index appears in the map more than once, the result -- is undefined. The map and input vector must be of the same length. scatterIf :: (Elt e, Elt e') => Acc (Vector Int) -> Acc (Vector e) -> (Exp e -> Exp Bool) -> Acc (Vector e') -> Acc (Vector e') -> Acc (Vector e') -- | Copy elements from source array to destination array according to a -- map. This is a backpermute operation where a map vector encodes -- the output to input index mapping. -- -- For example: -- -- 
--   input  = [1, 9, 6, 4, 4, 2, 0, 1, 2]
--   map    = [1, 3, 7, 2, 5, 3]
--   
--   output = [9, 4, 1, 6, 2, 4]
--
gather :: Elt e => Acc (Vector Int) -> Acc (Vector e) -> Acc (Vector e) -- | Conditionally copy elements from source array to destination array -- according to a map. This is a backpermute operation where a map -- vector encodes the output to input index mapping. In addition, there -- is a mask vector, and an associated predication function, -- that specifies whether an element will be copied. If not copied, the -- output array assumes the default vector's value. -- -- For example: -- -- 
--   default = [6, 6, 6, 6, 6, 6]
--   map     = [1, 3, 7, 2, 5, 3]
--   mask    = [3, 4, 9, 2, 7, 5]
--   pred    = (> 4)
--   input   = [1, 9, 6, 4, 4, 2, 0, 1, 2]
--   
--   output  = [6, 6, 1, 6, 2, 4]
--
gatherIf :: (Elt e, Elt e') => Acc (Vector Int) -> Acc (Vector e) -> (Exp e -> Exp Bool) -> Acc (Vector e') -> Acc (Vector e') -> Acc (Vector e') -- | Reduction of the innermost dimension of an array of arbitrary rank. -- The first argument needs to be an associative function to -- enable an efficient parallel implementation. fold :: (Shape ix, Elt a) => (Exp a -> Exp a -> Exp a) -> Exp a -> Acc (Array (ix :. Int) a) -> Acc (Array ix a) -- | Variant of fold that requires the reduced array to be non-empty -- and doesn't need an default value. The first argument needs to be an -- associative function to enable an efficient parallel -- implementation. fold1 :: (Shape ix, Elt a) => (Exp a -> Exp a -> Exp a) -> Acc (Array (ix :. Int) a) -> Acc (Array ix a) -- | Reduction of an array of arbitrary rank to a single scalar value. foldAll :: (Shape sh, Elt a) => (Exp a -> Exp a -> Exp a) -> Exp a -> Acc (Array sh a) -> Acc (Scalar a) -- | Variant of foldAll that requires the reduced array to be -- non-empty and doesn't need an default value. fold1All :: (Shape sh, Elt a) => (Exp a -> Exp a -> Exp a) -> Acc (Array sh a) -> Acc (Scalar a) -- | Segmented reduction along the innermost dimension. Performs one -- individual reduction per segment of the source array. These reductions -- proceed in parallel. -- -- The source array must have at least rank 1. The Segments array -- determines the lengths of the logical sub-arrays, each of which is -- folded separately. foldSeg :: (Shape ix, Elt a, Elt i, IsIntegral i) => (Exp a -> Exp a -> Exp a) -> Exp a -> Acc (Array (ix :. Int) a) -> Acc (Segments i) -> Acc (Array (ix :. Int) a) -- | Variant of foldSeg that requires all segments of the -- reduced array to be non-empty and doesn't need a default value. -- -- The source array must have at least rank 1. The Segments array -- determines the lengths of the logical sub-arrays, each of which is -- folded separately. fold1Seg :: (Shape ix, Elt a, Elt i, IsIntegral i) => (Exp a -> Exp a -> Exp a) -> Acc (Array (ix :. Int) a) -> Acc (Segments i) -> Acc (Array (ix :. 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 True and :: Shape sh => Acc (Array sh Bool) -> Acc (Scalar Bool) -- | Check if any element is True or :: Shape sh => Acc (Array sh Bool) -> Acc (Scalar Bool) -- | Compute the sum of elements sum :: (Shape sh, Elt e, IsNum e) => Acc (Array sh e) -> Acc (Scalar e) -- | Compute the product of the elements product :: (Shape sh, Elt e, IsNum e) => Acc (Array sh e) -> Acc (Scalar e) -- | Yield the minimum element of an array. The array must not be empty. minimum :: (Shape sh, Elt e, IsScalar e) => Acc (Array sh e) -> Acc (Scalar e) -- | Yield the maximum element of an array. The array must not be empty. maximum :: (Shape sh, Elt e, IsScalar e) => Acc (Array sh e) -> Acc (Scalar e) -- | Data.List style left-to-right scan, but with the additional -- restriction that the first argument needs to be an associative -- function to enable an efficient parallel implementation. The initial -- value (second argument) may be arbitrary. scanl :: Elt a => (Exp a -> Exp a -> Exp a) -> Exp a -> Acc (Vector a) -> Acc (Vector a) -- | Data.List style left-to-right scan without an initial value (aka -- inclusive scan). Again, the first argument needs to be an -- associative function. Denotationally, we have -- -- 
--   scanl1 f e arr = tail (scanl f e arr)
--
scanl1 :: Elt a => (Exp a -> Exp a -> Exp a) -> Acc (Vector a) -> Acc (Vector a) -- | Variant of scanl, where the final result of the reduction is -- returned separately. Denotationally, we have -- -- 
--   scanl' f e arr = (init res, unit (res!len))
--     where
--       len = shape arr
--       res = scanl f e arr
--
scanl' :: Elt a => (Exp a -> Exp a -> Exp a) -> Exp a -> Acc (Vector a) -> (Acc (Vector a), Acc (Scalar a)) -- | Right-to-left variant of scanl. scanr :: Elt a => (Exp a -> Exp a -> Exp a) -> Exp a -> Acc (Vector a) -> Acc (Vector a) -- | Right-to-left variant of scanl1. scanr1 :: Elt a => (Exp a -> Exp a -> Exp a) -> Acc (Vector a) -> Acc (Vector a) -- | Right-to-left variant of scanl'. scanr' :: Elt a => (Exp a -> Exp a -> Exp a) -> Exp a -> Acc (Vector a) -> (Acc (Vector a), Acc (Scalar a)) -- | Left-to-right prescan (aka exclusive scan). As for scan, the -- first argument must be an associative function. Denotationally, -- we have -- -- 
--   prescanl f e = Prelude.fst . scanl' f e
--
prescanl :: Elt a => (Exp a -> Exp a -> Exp a) -> Exp a -> Acc (Vector a) -> Acc (Vector a) -- | Left-to-right postscan, a variant of scanl1 with an initial -- value. Denotationally, we have -- -- 
--   postscanl f e = map (e `f`) . scanl1 f
--
postscanl :: Elt a => (Exp a -> Exp a -> Exp a) -> Exp a -> Acc (Vector a) -> Acc (Vector a) -- | Right-to-left prescan (aka exclusive scan). As for scan, the -- first argument must be an associative function. Denotationally, -- we have -- -- 
--   prescanr f e = Prelude.fst . scanr' f e
--
prescanr :: Elt a => (Exp a -> Exp a -> Exp a) -> Exp a -> Acc (Vector a) -> Acc (Vector a) -- | Right-to-left postscan, a variant of scanr1 with an initial -- value. Denotationally, we have -- -- 
--   postscanr f e = map (e `f`) . scanr1 f
--
postscanr :: Elt a => (Exp a -> Exp a -> Exp a) -> Exp a -> Acc (Vector a) -> Acc (Vector a) -- | Segmented version of scanl scanlSeg :: (Elt a, Elt i, IsIntegral i) => (Exp a -> Exp a -> Exp a) -> Exp a -> Acc (Vector a) -> Acc (Segments i) -> Acc (Vector a) -- | Segmented version of scanl1. scanl1Seg :: (Elt a, Elt i, IsIntegral i) => (Exp a -> Exp a -> Exp a) -> Acc (Vector a) -> Acc (Segments i) -> Acc (Vector a) -- | Segmented version of scanl' -- -- 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. scanl'Seg :: (Elt a, Elt i, IsIntegral i) => (Exp a -> Exp a -> Exp a) -> Exp a -> Acc (Vector a) -> Acc (Segments i) -> Acc (Vector a, Vector a) -- | Segmented version of prescanl. prescanlSeg :: (Elt a, Elt i, IsIntegral i) => (Exp a -> Exp a -> Exp a) -> Exp a -> Acc (Vector a) -> Acc (Segments i) -> Acc (Vector a) -- | Segmented version of postscanl. postscanlSeg :: (Elt a, Elt i, IsIntegral i) => (Exp a -> Exp a -> Exp a) -> Exp a -> Acc (Vector a) -> Acc (Segments i) -> Acc (Vector a) -- | Segmented version of scanr. scanrSeg :: (Elt a, Elt i, IsIntegral i) => (Exp a -> Exp a -> Exp a) -> Exp a -> Acc (Vector a) -> Acc (Segments i) -> Acc (Vector a) -- | Segmented version of scanr1. scanr1Seg :: (Elt a, Elt i, IsIntegral i) => (Exp a -> Exp a -> Exp a) -> Acc (Vector a) -> Acc (Segments i) -> Acc (Vector a) -- | Segmented version of scanr'. scanr'Seg :: (Elt a, Elt i, IsIntegral i) => (Exp a -> Exp a -> Exp a) -> Exp a -> Acc (Vector a) -> Acc (Segments i) -> Acc (Vector a, Vector a) -- | Segmented version of prescanr. prescanrSeg :: (Elt a, Elt i, IsIntegral i) => (Exp a -> Exp a -> Exp a) -> Exp a -> Acc (Vector a) -> Acc (Segments i) -> Acc (Vector a) -- | Segmented version of postscanr. postscanrSeg :: (Elt a, Elt i, IsIntegral i) => (Exp a -> Exp a -> Exp a) -> Exp a -> Acc (Vector a) -> Acc (Segments i) -> Acc (Vector a) -- | Map a stencil over an array. In contrast to map, the domain of -- a stencil function is an entire neighbourhood of each array -- element. Neighbourhoods are sub-arrays centred around a focal point. -- They are not necessarily rectangular, but they are symmetric in each -- dimension and have an extent of at least three in each dimensions — -- 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 :: (Shape ix, Elt a, Elt b, Stencil ix a stencil) => (stencil -> Exp b) -> Boundary a -> Acc (Array ix a) -> Acc (Array ix 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. stencil2 :: (Shape ix, Elt a, Elt b, Elt c, Stencil ix a stencil1, Stencil ix b stencil2) => (stencil1 -> stencil2 -> Exp c) -> Boundary a -> Acc (Array ix a) -> Boundary b -> Acc (Array ix b) -> Acc (Array ix 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) -- | Call a foreign function. The form the function takes is dependent on -- the backend being used. The arguments are passed as either a single -- array or as a tuple of arrays. In addition a pure Accelerate version -- of the function needs to be provided to support backends other than -- the one being targeted. foreignAcc :: (Arrays acc, Arrays res, Foreign ff) => ff acc res -> (Acc acc -> Acc res) -> Acc acc -> Acc res -- | Call a foreign function with foreign implementations for two different -- backends. foreignAcc2 :: (Arrays acc, Arrays res, Foreign ff1, Foreign ff2) => ff1 acc res -> ff2 acc res -> (Acc acc -> Acc res) -> Acc acc -> Acc res -- | Call a foreign function with foreign implementations for three -- different backends. foreignAcc3 :: (Arrays acc, Arrays res, Foreign ff1, Foreign ff2, Foreign ff3) => ff1 acc res -> ff2 acc res -> ff3 acc res -> (Acc acc -> Acc res) -> Acc acc -> Acc res -- | Call a foreign expression function. The form the function takes is -- dependent on the backend being used. The arguments are passed as -- either a single scalar element or as a tuple of elements. In addition -- a pure Accelerate version of the function needs to be provided to -- support backends other than the one being targeted. foreignExp :: (Elt e, Elt res, Foreign ff) => ff e res -> (Exp e -> Exp res) -> Exp e -> Exp res -- | Call a foreign function with foreign implementations for two different -- backends. foreignExp2 :: (Elt e, Elt res, Foreign ff1, Foreign ff2) => ff1 e res -> ff2 e res -> (Exp e -> Exp res) -> Exp e -> Exp res -- | Call a foreign function with foreign implementations for three -- different backends. foreignExp3 :: (Elt e, Elt res, Foreign ff1, Foreign ff2, Foreign ff3) => ff1 e res -> ff2 e res -> ff3 e res -> (Exp e -> Exp res) -> Exp e -> Exp res -- | Scalar expressions for plain array computations. data Exp t -- | All scalar type 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 -- | A fixed-precision integer type with at least the range [-2^29 .. -- 2^29-1]. The exact range for a given implementation can be -- determined by using minBound and maxBound from the -- Bounded class. data Int :: * -- | 8-bit signed integer type data Int8 :: * -- | 16-bit signed integer type data Int16 :: * -- | 32-bit signed integer type data Int32 :: * -- | 64-bit signed integer type data Int64 :: * -- | A Word is an unsigned integral type, with the same size as -- Int. data Word :: * -- | 8-bit unsigned integer type data Word8 :: * -- | 16-bit unsigned integer type data Word16 :: * -- | 32-bit unsigned integer type data Word32 :: * -- | 64-bit unsigned integer type data Word64 :: * -- | Haskell type representing the C short type. data CShort :: * -- | Haskell type representing the C unsigned short type. data CUShort :: * -- | Haskell type representing the C int type. data CInt :: * -- | Haskell type representing the C unsigned int type. data CUInt :: * -- | Haskell type representing the C long type. data CLong :: * -- | Haskell type representing the C unsigned long type. data CULong :: * -- | Haskell type representing the C long long type. data CLLong :: * -- | Haskell type representing the C unsigned long long type. data CULLong :: * -- | 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 :: * -- | Haskell type representing the C float type. data CFloat :: * -- | Haskell type representing the C double type. data CDouble :: * data Bool :: * -- | The character type Char is an enumeration whose values -- represent Unicode (or equivalently ISO/IEC 10646) characters (see -- http://www.unicode.org/ for details). This set extends the ISO -- 8859-1 (Latin-1) character set (the first 256 characters), which is -- itself an extension of the ASCII character set (the first 128 -- characters). A character literal in Haskell has type Char. -- -- To convert a Char to or from the corresponding Int value -- defined by Unicode, use toEnum and fromEnum from the -- Enum class respectively (or equivalently ord and -- chr). data Char :: * -- | Haskell type representing the C char type. data CChar :: * -- | Haskell type representing the C signed char type. data CSChar :: * -- | Haskell type representing the C unsigned char type. data CUChar :: * -- | The class of types e which can be lifted into c. class Lift c e where type family Plain e 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 :: Unlift c e => c (Plain e) -> e -- | Lift a unary function into Exp. lift1 :: (Unlift Exp e1, Lift Exp e2) => (e1 -> e2) -> Exp (Plain e1) -> Exp (Plain e2) -- | Lift a binary function into Exp. lift2 :: (Unlift Exp e1, Unlift Exp e2, Lift Exp e3) => (e1 -> e2 -> e3) -> Exp (Plain e1) -> Exp (Plain e2) -> Exp (Plain e3) -- | 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 -- | 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 pair. fst :: Unlift f (f a, f b) => f (Plain (f a), Plain (f b)) -> f a -- | Extract the second component of a pair. snd :: Unlift f (f a, f b) => f (Plain (f a), Plain (f b)) -> f 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 -- | Conditional expression. If the predicate evaluates to True, the -- first component of the tuple is returned, else the second. (?) :: Elt t => Exp Bool -> (Exp t, Exp t) -> Exp t -- | Conjunction (&&*) :: Exp Bool -> Exp Bool -> Exp Bool -- | Disjunction (||*) :: Exp Bool -> Exp Bool -> Exp Bool -- | Negation not :: Exp Bool -> Exp Bool -- | Equality lifted into Accelerate expressions. (==*) :: (Elt t, IsScalar t) => Exp t -> Exp t -> Exp Bool -- | Inequality lifted into Accelerate expressions. (/=*) :: (Elt t, IsScalar t) => Exp t -> Exp t -> Exp Bool -- | Smaller-than lifted into Accelerate expressions. (<*) :: (Elt t, IsScalar t) => Exp t -> Exp t -> Exp Bool -- | Smaller-or-equal lifted into Accelerate expressions. (<=*) :: (Elt t, IsScalar t) => Exp t -> Exp t -> Exp Bool -- | Greater-than lifted into Accelerate expressions. (>*) :: (Elt t, IsScalar t) => Exp t -> Exp t -> Exp Bool -- | Greater-or-equal lifted into Accelerate expressions. (>=*) :: (Elt t, IsScalar t) => Exp t -> Exp t -> Exp Bool -- | Determine the maximum of two scalars. max :: (Elt t, IsScalar t) => Exp t -> Exp t -> Exp t -- | Determine the minimum of two scalars. min :: (Elt t, IsScalar t) => Exp t -> Exp t -> Exp t -- | truncate x returns the integer nearest x between -- zero and x. truncate :: (Elt a, Elt b, IsFloating a, IsIntegral b) => Exp a -> Exp b -- | round x returns the nearest integer to x, or the -- even integer if x is equidistant between two integers. round :: (Elt a, Elt b, IsFloating a, IsIntegral b) => Exp a -> Exp b -- | floor x returns the greatest integer not greater than -- x. floor :: (Elt a, Elt b, IsFloating a, IsIntegral b) => Exp a -> Exp b -- | ceiling x returns the least integer not less than x. ceiling :: (Elt a, Elt b, IsFloating a, IsIntegral b) => Exp a -> Exp b -- | bit i is a value with the ith bit set and all other -- bits clear bit :: (Elt t, IsIntegral t) => Exp Int -> Exp t -- | x `setBit` i is the same as x .|. bit i setBit :: (Elt t, IsIntegral t) => Exp t -> Exp Int -> Exp t -- | x `clearBit` i is the same as x .&. complement (bit -- i) clearBit :: (Elt t, IsIntegral t) => Exp t -> Exp Int -> Exp t -- | x `complementBit` i is the same as x `xor` bit i complementBit :: (Elt t, IsIntegral t) => Exp t -> Exp Int -> Exp t -- | Return True if the nth bit of the argument is 1 testBit :: (Elt t, IsIntegral t) => Exp t -> Exp Int -> Exp Bool -- | shift x i shifts x left by i bits if -- i is positive, or right by -i bits otherwise. Right -- shifts perform sign extension on signed number types; i.e. they fill -- the top bits with 1 if the x is negative and with 0 -- otherwise. shift :: (Elt t, IsIntegral t) => Exp t -> Exp Int -> Exp t -- | Shift the argument left by the specified number of bits (which must be -- non-negative). shiftL :: (Elt t, IsIntegral t) => Exp t -> Exp Int -> Exp t -- | 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 bitSize. -- -- Right shifts perform sign extension on signed number types; i.e. they -- fill the top bits with 1 if the x is negative and with 0 -- otherwise. shiftR :: (Elt t, IsIntegral t) => Exp t -> Exp Int -> Exp t -- | rotate x i rotates x left by i bits -- if i is positive, or right by -i bits otherwise. rotate :: (Elt t, IsIntegral t) => Exp t -> Exp Int -> Exp t -- | Rotate the argument left by the specified number of bits (which must -- be non-negative). rotateL :: (Elt t, IsIntegral t) => Exp t -> Exp Int -> Exp t -- | Rotate the argument right by the specified number of bits (which must -- be non-negative). rotateR :: (Elt t, IsIntegral t) => Exp t -> Exp Int -> Exp t -- | The one index for a rank-0 array. index0 :: Exp Z -- | Turn an Int expression into a rank-1 indexing expression. index1 :: Elt i => Exp i -> Exp (Z :. i) -- | Turn a rank-1 indexing expression into an Int expression. unindex1 :: Elt i => Exp (Z :. i) -> Exp i -- | Creates a rank-2 index from two Exp Int`s index2 :: (Elt i, 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 :: (Elt i, Slice (Z :. i)) => Exp ((Z :. i) :. i) -> Exp (i, i) -- | Get the outermost dimension of a shape indexHead :: Slice sh => Exp (sh :. Int) -> Exp Int -- | Get all but the outermost element of a shape indexTail :: Slice sh => Exp (sh :. Int) -> Exp sh -- | Map a multi-dimensional index into a linear, row-major representation -- of an array. The first argument is the array shape, the second is the -- index. toIndex :: Shape sh => Exp sh -> Exp sh -> Exp Int -- | Inverse of fromIndex fromIndex :: Shape sh => Exp sh -> Exp Int -> Exp sh -- | Convert a Boolean value to an Int, where False turns -- into '0' and True into '1'. boolToInt :: Exp Bool -> Exp Int -- | General coercion from integral types fromIntegral :: (Elt a, Elt b, IsIntegral a, IsNum b) => Exp a -> Exp b -- | Rank of an array arrayDim :: 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 Shape arraySize :: Shape sh => sh -> Int -- | Array indexing in plain Haskell code indexArray :: Array sh e -> sh -> e -- | Convert a list, with elements in row-major order, into an accelerated -- array. fromList :: (Shape sh, Elt e) => sh -> [e] -> Array sh e -- | Convert an accelerated array to a list in row-major order. toList :: Array sh e -> [e] -- | Convert an IArray to an accelerated array. -- -- While the type signature mentions Accelerate internals that are not -- exported, in practice satisfying the type equality is straight -- forward. The index type ix must be the unit type () -- for singleton arrays, or an Int or tuple of Int's -- for multidimensional arrays. fromIArray :: (EltRepr ix ~ EltRepr sh, IArray a e, Ix ix, Shape sh, Elt ix, Elt e) => a ix e -> Array sh e -- | Convert an accelerated array to an IArray. toIArray :: (EltRepr ix ~ EltRepr sh, IArray a e, Ix ix, Shape sh, Elt ix, Elt e) => Array sh e -> a ix e