Safe Haskell | Safe-Infered |
---|
Repa arrays are wrappers around a linear structure that holds the element data. The representation tag determines what structure holds the data.
Delayed Representations (functions that compute elements)
Manifest Representations (real data)
-
U
-- Adaptive unboxed vectors. -
V
-- Boxed vectors. -
B
-- Strict ByteStrings. -
F
-- Foreign memory buffers.
Meta Representations
-
P
-- Arrays that are partitioned into several representations. -
X
-- Arrays whose elements are all undefined.
Array fusion is achieved via the delayed (D
) and cursored (C
)
representations. At compile time, the GHC simplifier combines the functions
contained within D
and C
arrays without needing to create manifest
intermediate arrays.
Converting between the parallel manifest representations (eg U
and B
)
is either constant time or parallel copy, depending on the compatability
of the physical representation.
Writing fast code:
- Repa does not support nested parallellism.
This means that you cannot
map
a parallel worker function across an array and then callcomputeP
to evaluate it, or pass a parallel worker to parallel reductions such asfoldP
. If you do then you will get a run-time warning and the code will run very slowly. - Arrays of type
(Array D sh a)
or(Array C sh a)
are not real arrays. They are represented as functions that compute each element on demand. You need to use a function likecomputeS
,computeP
,computeUnboxedP
and so on to actually evaluate the elements. - You should add
INLINE
pragmas to all leaf-functions in your code, expecially ones that compute numberic results. This ensures they are specialised at the appropriate element types. - Scheduling a parallel computation takes about 200us on an OSX machine. You should sequential computation for small arrays in inner loops, or a the bottom of a divide-and-conquer algorithm.
- data family Array r sh e
- module Data.Array.Repa.Shape
- module Data.Array.Repa.Index
- class Repr r e where
- extent :: Shape sh => Array r sh e -> sh
- index, unsafeIndex :: Shape sh => Array r sh e -> sh -> e
- linearIndex, unsafeLinearIndex :: Shape sh => Array r sh e -> Int -> e
- deepSeqArray :: Shape sh => Array r sh e -> b -> b
- (!) :: (Repr r e, Shape sh) => Array r sh e -> sh -> e
- toList :: (Shape sh, Repr r e) => Array r sh e -> [e]
- deepSeqArrays :: (Shape sh, Repr r e) => [Array r sh e] -> b -> b
- computeP :: Fill r1 r2 sh e => Array r1 sh e -> Array r2 sh e
- computeS :: Fill r1 r2 sh e => Array r1 sh e -> Array r2 sh e
- copyP :: (Repr r1 e, Fill D r2 sh e) => Array r1 sh e -> Array r2 sh e
- copyS :: (Repr r1 e, Fill D r2 sh e) => Array r1 sh e -> Array r2 sh e
- now :: (Shape sh, Repr r e, Monad m) => Array r sh e -> m (Array r sh e)
- data D
- fromFunction :: sh -> (sh -> a) -> Array D sh a
- toFunction :: (Shape sh, Repr r1 a) => Array r1 sh a -> (sh, sh -> a)
- delay :: (Shape sh, Repr r e) => Array r sh e -> Array D sh e
- data U
- computeUnboxedP :: Fill r1 U sh e => Array r1 sh e -> Array U sh e
- computeUnboxedS :: Fill r1 U sh e => Array r1 sh e -> Array U sh e
- fromListUnboxed :: (Shape sh, Unbox a) => sh -> [a] -> Array U sh a
- fromUnboxed :: (Shape sh, Unbox e) => sh -> Vector e -> Array U sh e
- toUnboxed :: Unbox e => Array U sh e -> Vector e
- reshape :: (Shape sh2, Shape sh1, Repr r1 e) => sh2 -> Array r1 sh1 e -> Array D sh2 e
- append, (++) :: (Shape sh, Repr r1 e, Repr r2 e) => Array r1 (sh :. Int) e -> Array r2 (sh :. Int) e -> Array D (sh :. Int) e
- transpose :: (Shape sh, Repr r e) => Array r ((sh :. Int) :. Int) e -> Array D ((sh :. Int) :. Int) e
- extend :: (Slice sl, Shape (FullShape sl), Shape (SliceShape sl), Repr r e) => sl -> Array r (SliceShape sl) e -> Array D (FullShape sl) e
- backpermute, unsafeBackpermute :: forall r sh1 sh2 e. (Shape sh1, Shape sh2, Repr r e) => sh2 -> (sh2 -> sh1) -> Array r sh1 e -> Array D sh2 e
- backpermuteDft :: forall r0 r1 sh1 sh2 e. (Shape sh1, Shape sh2, Repr r0 e, Repr r1 e) => Array r0 sh2 e -> (sh2 -> Maybe sh1) -> Array r1 sh1 e -> Array D sh2 e
- module Data.Array.Repa.Slice
- slice :: (Slice sl, Shape (FullShape sl), Shape (SliceShape sl), Repr r e) => Array r (FullShape sl) e -> sl -> Array D (SliceShape sl) e
- map :: (Shape sh, Repr r a) => (a -> b) -> Array r sh a -> Array D sh b
- zipWith :: (Shape sh, Repr r1 a, Repr r2 b) => (a -> b -> c) -> Array r1 sh a -> Array r2 sh b -> Array D sh c
- (+^) :: (Num c, Shape sh, Repr r2 c, Repr r1 c) => Array r1 sh c -> Array r2 sh c -> Array D sh c
- (-^) :: (Num c, Shape sh, Repr r2 c, Repr r1 c) => Array r1 sh c -> Array r2 sh c -> Array D sh c
- (*^) :: (Num c, Shape sh, Repr r2 c, Repr r1 c) => Array r1 sh c -> Array r2 sh c -> Array D sh c
- (/^) :: (Fractional c, Shape sh, Repr r2 c, Repr r1 c) => Array r1 sh c -> Array r2 sh c -> Array D sh c
- class Combine r1 a r2 b | r1 -> r2 where
- traverse, unsafeTraverse :: forall r sh sh' a b. (Shape sh, Shape sh', Repr r a) => Array r sh a -> (sh -> sh') -> ((sh -> a) -> sh' -> b) -> Array D sh' b
- traverse2, unsafeTraverse2 :: forall r1 r2 sh sh' sh'' a b c. (Shape sh, Shape sh', Shape sh'', Repr r1 a, Repr r2 b) => Array r1 sh a -> Array r2 sh' b -> (sh -> sh' -> sh'') -> ((sh -> a) -> (sh' -> b) -> sh'' -> c) -> Array D sh'' c
- traverse3, unsafeTraverse3 :: forall r1 r2 r3 sh1 sh2 sh3 sh4 a b c d. (Shape sh1, Shape sh2, Shape sh3, Shape sh4, Repr r1 a, Repr r2 b, Repr r3 c) => Array r1 sh1 a -> Array r2 sh2 b -> Array r3 sh3 c -> (sh1 -> sh2 -> sh3 -> sh4) -> ((sh1 -> a) -> (sh2 -> b) -> (sh3 -> c) -> sh4 -> d) -> Array D sh4 d
- traverse4, unsafeTraverse4 :: forall r1 r2 r3 r4 sh1 sh2 sh3 sh4 sh5 a b c d e. (Shape sh1, Shape sh2, Shape sh3, Shape sh4, Shape sh5, Repr r1 a, Repr r2 b, Repr r3 c, Repr r4 d) => Array r1 sh1 a -> Array r2 sh2 b -> Array r3 sh3 c -> Array r4 sh4 d -> (sh1 -> sh2 -> sh3 -> sh4 -> sh5) -> ((sh1 -> a) -> (sh2 -> b) -> (sh3 -> c) -> (sh4 -> d) -> sh5 -> e) -> Array D sh5 e
- interleave2 :: (Shape sh, Repr r1 a, Repr r2 a) => Array r1 (sh :. Int) a -> Array r2 (sh :. Int) a -> Array D (sh :. Int) a
- interleave3 :: (Shape sh, Repr r1 a, Repr r2 a, Repr r3 a) => Array r1 (sh :. Int) a -> Array r2 (sh :. Int) a -> Array r3 (sh :. Int) a -> Array D (sh :. Int) a
- interleave4 :: (Shape sh, Repr r1 a, Repr r2 a, Repr r3 a, Repr r4 a) => Array r1 (sh :. Int) a -> Array r2 (sh :. Int) a -> Array r3 (sh :. Int) a -> Array r4 (sh :. Int) a -> Array D (sh :. Int) a
- foldP :: (Shape sh, Elt a, Unbox a, Repr r a) => (a -> a -> a) -> a -> Array r (sh :. Int) a -> Array U sh a
- foldS :: (Shape sh, Elt a, Unbox a, Repr r a) => (a -> a -> a) -> a -> Array r (sh :. Int) a -> Array U sh a
- foldAllP :: (Shape sh, Elt a, Unbox a, Repr r a) => (a -> a -> a) -> a -> Array r sh a -> a
- foldAllS :: (Shape sh, Elt a, Unbox a, Repr r a) => (a -> a -> a) -> a -> Array r sh a -> a
- sumP :: (Shape sh, Num a, Elt a, Unbox a, Repr r a) => Array r (sh :. Int) a -> Array U sh a
- sumS :: (Shape sh, Num a, Elt a, Unbox a, Repr r a) => Array r (sh :. Int) a -> Array U sh a
- sumAllP :: (Shape sh, Elt a, Unbox a, Num a, Repr r a) => Array r sh a -> a
- sumAllS :: (Shape sh, Elt a, Unbox a, Num a, Repr r a) => Array r sh a -> a
- select :: Unbox a => (Int -> Bool) -> (Int -> a) -> Int -> Array U DIM1 a
Abstract array representation
data family Array r sh e Source
Arrays with a representation tag, shape, and element type.
Use one of the type tags like D
, U
and so on for r
,
one of DIM1
, DIM2
... for sh
.
module Data.Array.Repa.Shape
module Data.Array.Repa.Index
Class of array representations that we can read elements from.
extent :: Shape sh => Array r sh e -> shSource
O(1). Take the extent of an array.
index, unsafeIndex :: Shape sh => Array r sh e -> sh -> eSource
O(1). Shape polymorphic indexing.
linearIndex, unsafeLinearIndex :: Shape sh => Array r sh e -> Int -> eSource
O(1). Linear indexing into underlying, row-major, array representation.
deepSeqArray :: Shape sh => Array r sh e -> b -> bSource
Ensure an array's data structure is fully evaluated.
Repr X e | Undefined array elements. Inspecting them yields |
Repr D a | Compute elements of a delayed array. |
Repr B Word8 | Read elements from a |
Repr C a | Compute elements of a cursored array. |
Storable a => Repr F a | Read elements from a foreign buffer. |
Unbox a => Repr U a | Read elements from an unboxed vector array. |
Repr V a | Read elements from a boxed vector array. |
(Repr r1 e, Repr r2 e) => Repr (P r1 r2) e | Read elements from a partitioned array. |
deepSeqArrays :: (Shape sh, Repr r e) => [Array r sh e] -> b -> bSource
Apply deepSeqArray
to up to four arrays.
The implementation of this function has been hand-unwound to work for up to
four arrays. Putting more in the list yields error
.
Converting between array representations
computeP :: Fill r1 r2 sh e => Array r1 sh e -> Array r2 sh eSource
Parallel computation of array elements.
computeS :: Fill r1 r2 sh e => Array r1 sh e -> Array r2 sh eSource
Sequential computation of array elements.
copyP :: (Repr r1 e, Fill D r2 sh e) => Array r1 sh e -> Array r2 sh eSource
Parallel copying of arrays.
- This is a wrapper that delays an array before calling
computeP
. - You can use it to copy manifest arrays between representations.
- You can also use it to compute elements, but doing this may not be as efficient. This is because delaying it the second time can hide information about the structure of the original computation.
copyS :: (Repr r1 e, Fill D r2 sh e) => Array r1 sh e -> Array r2 sh eSource
Sequential copying of arrays.
now :: (Shape sh, Repr r e, Monad m) => Array r sh e -> m (Array r sh e)Source
Apply deepSeqArray
to an array so the result is actually constructed
at this point in a monadic computation.
- Haskell's laziness means that applications of
computeP
andcopyP
are automatically suspended. - Laziness can be problematic for data parallel programs, because we want each array to be constructed in parallel before moving onto the next one.
For example:
do arr2 <- now $ computeP $ map f arr1 arr3 <- now $ computeP $ zipWith arr2 arr1 return arr3
Concrete array representations
Delayed representation
Delayed arrays are represented as functions from the index to element value.
Repr D a | Compute elements of a delayed array. |
(Fillable r2 e, Elt e) => FillRange D r2 DIM2 e | Compute a range of elements in a rank-2 array. |
(Fillable r2 e, Shape sh) => Fill D r2 sh e | Compute all elements in an array. |
Combine X a D b | |
Combine D a D b | |
Combine B Word8 D b | |
Storable a => Combine F a D b | |
Unbox a => Combine U a D b |
fromFunction :: sh -> (sh -> a) -> Array D sh aSource
O(1). Wrap a function as a delayed array.
toFunction :: (Shape sh, Repr r1 a) => Array r1 sh a -> (sh, sh -> a)Source
O(1). Produce the extent of an array and a function to retrieve an arbitrary element.
delay :: (Shape sh, Repr r e) => Array r sh e -> Array D sh eSource
O(1). Delay an array. This wraps the internal representation to be a function from indices to elements, so consumers don't need to worry about what the previous representation was.
Unboxed vector representation
Unboxed arrays are represented as unboxed vectors.
The implementation of Unboxed
is based on type families and
picks an efficient, specialised representation for every element type. In
particular, unboxed vectors of pairs are represented as pairs of unboxed
vectors. This is the most efficient representation for numerical data.
computeUnboxedP :: Fill r1 U sh e => Array r1 sh e -> Array U sh eSource
Parallel computation of array elements.
- This is an alias for
computeP
with a more specific type.
computeUnboxedS :: Fill r1 U sh e => Array r1 sh e -> Array U sh eSource
Sequential computation of array elements..
- This is an alias for
computeS
with a more specific type.
fromListUnboxed :: (Shape sh, Unbox a) => sh -> [a] -> Array U sh aSource
O(n). Convert a list to an unboxed vector array.
- This is an alias for
fromList
with a more specific type.
fromUnboxed :: (Shape sh, Unbox e) => sh -> Vector e -> Array U sh eSource
O(1). Wrap an unboxed vector as an array.
Operators
Index space transformations
reshape :: (Shape sh2, Shape sh1, Repr r1 e) => sh2 -> Array r1 sh1 e -> Array D sh2 eSource
Impose a new shape on the elements of an array.
The new extent must be the same size as the original, else error
.
append, (++) :: (Shape sh, Repr r1 e, Repr r2 e) => Array r1 (sh :. Int) e -> Array r2 (sh :. Int) e -> Array D (sh :. Int) eSource
Append two arrays.
transpose :: (Shape sh, Repr r e) => Array r ((sh :. Int) :. Int) e -> Array D ((sh :. Int) :. Int) eSource
Transpose the lowest two dimensions of an array. Transposing an array twice yields the original.
extend :: (Slice sl, Shape (FullShape sl), Shape (SliceShape sl), Repr r e) => sl -> Array r (SliceShape sl) e -> Array D (FullShape sl) eSource
Extend an array, according to a given slice specification.
backpermute,unsafeBackpermuteSource
:: forall r sh1 sh2 e . (Shape sh1, Shape sh2, Repr r e) | |
=> sh2 | Extent of result array. |
-> (sh2 -> sh1) | Function mapping each index in the result array to an index of the source array. |
-> Array r sh1 e | Source array. |
-> Array D sh2 e |
Backwards permutation of an array's elements. The result array has the same extent as the original.
:: forall r0 r1 sh1 sh2 e . (Shape sh1, Shape sh2, Repr r0 e, Repr r1 e) | |
=> Array r0 sh2 e | Default values ( |
-> (sh2 -> Maybe sh1) | Function mapping each index in the result array to an index in the source array. |
-> Array r1 sh1 e | Source array. |
-> Array D sh2 e |
Default backwards permutation of an array's elements.
If the function returns Nothing
then the value at that index is taken
from the default array (arrDft
)
module Data.Array.Repa.Slice
slice :: (Slice sl, Shape (FullShape sl), Shape (SliceShape sl), Repr r e) => Array r (FullShape sl) e -> sl -> Array D (SliceShape sl) eSource
Take a slice from an array, according to a given specification.
Structure preserving operations
map :: (Shape sh, Repr r a) => (a -> b) -> Array r sh a -> Array D sh bSource
Apply a worker function to each element of an array, yielding a new array with the same extent.
zipWith :: (Shape sh, Repr r1 a, Repr r2 b) => (a -> b -> c) -> Array r1 sh a -> Array r2 sh b -> Array D sh cSource
Combine two arrays, element-wise, with a binary operator. If the extent of the two array arguments differ, then the resulting array's extent is their intersection.
(+^) :: (Num c, Shape sh, Repr r2 c, Repr r1 c) => Array r1 sh c -> Array r2 sh c -> Array D sh cSource
(-^) :: (Num c, Shape sh, Repr r2 c, Repr r1 c) => Array r1 sh c -> Array r2 sh c -> Array D sh cSource
(*^) :: (Num c, Shape sh, Repr r2 c, Repr r1 c) => Array r1 sh c -> Array r2 sh c -> Array D sh cSource
(/^) :: (Fractional c, Shape sh, Repr r2 c, Repr r1 c) => Array r1 sh c -> Array r2 sh c -> Array D sh cSource
class Combine r1 a r2 b | r1 -> r2 whereSource
Combining versions of map
and zipWith
that preserve the representation
of cursored and partitioned arrays.
For cursored (C
) arrays, the cursoring of the source array is preserved.
For partitioned (P
) arrays, the worker function is fused with each array
partition separately, instead of treating the whole array as a single
bulk object.
Preserving the cursored and/or paritioned representation of an array
is will make follow-on computation more efficient than if the array was
converted to a vanilla Delayed (D
) array as with plain map
and zipWith
.
If the source array is not cursored or partitioned then cmap
and
czipWith
are identical to the plain functions.
cmap :: Shape sh => (a -> b) -> Array r1 sh a -> Array r2 sh bSource
Combining map
.
czipWith :: (Shape sh, Repr r c) => (c -> a -> b) -> Array r sh c -> Array r1 sh a -> Array r2 sh bSource
Combining zipWith
.
If you have a cursored or partitioned source array then use that as
the third argument (corresponding to r1
here)
Generic traversal
:: forall r sh sh' a b . (Shape sh, Shape sh', Repr r a) | |
=> Array r sh a | Source array. |
-> (sh -> sh') | Function to produce the extent of the result. |
-> ((sh -> a) -> sh' -> b) | Function to produce elements of the result. It is passed a lookup function to get elements of the source. |
-> Array D sh' b |
Unstructured traversal.
traverse2,unsafeTraverse2Source
:: forall r1 r2 sh sh' sh'' a b c . (Shape sh, Shape sh', Shape sh'', Repr r1 a, Repr r2 b) | |
=> Array r1 sh a | First source array. |
-> Array r2 sh' b | Second source array. |
-> (sh -> sh' -> sh'') | Function to produce the extent of the result. |
-> ((sh -> a) -> (sh' -> b) -> sh'' -> c) | Function to produce elements of the result. It is passed lookup functions to get elements of the source arrays. |
-> Array D sh'' c |
Unstructured traversal over two arrays at once.
traverse3, unsafeTraverse3 :: forall r1 r2 r3 sh1 sh2 sh3 sh4 a b c d. (Shape sh1, Shape sh2, Shape sh3, Shape sh4, Repr r1 a, Repr r2 b, Repr r3 c) => Array r1 sh1 a -> Array r2 sh2 b -> Array r3 sh3 c -> (sh1 -> sh2 -> sh3 -> sh4) -> ((sh1 -> a) -> (sh2 -> b) -> (sh3 -> c) -> sh4 -> d) -> Array D sh4 dSource
Unstructured traversal over three arrays at once.
traverse4, unsafeTraverse4 :: forall r1 r2 r3 r4 sh1 sh2 sh3 sh4 sh5 a b c d e. (Shape sh1, Shape sh2, Shape sh3, Shape sh4, Shape sh5, Repr r1 a, Repr r2 b, Repr r3 c, Repr r4 d) => Array r1 sh1 a -> Array r2 sh2 b -> Array r3 sh3 c -> Array r4 sh4 d -> (sh1 -> sh2 -> sh3 -> sh4 -> sh5) -> ((sh1 -> a) -> (sh2 -> b) -> (sh3 -> c) -> (sh4 -> d) -> sh5 -> e) -> Array D sh5 eSource
Unstructured traversal over four arrays at once.
Interleaving
interleave2 :: (Shape sh, Repr r1 a, Repr r2 a) => Array r1 (sh :. Int) a -> Array r2 (sh :. Int) a -> Array D (sh :. Int) aSource
Interleave the elements of two arrays.
All the input arrays must have the same extent, else error
.
The lowest dimension of the result array is twice the size of the inputs.
interleave2 a1 a2 b1 b2 => a1 b1 a2 b2 a3 a4 b3 b4 a3 b3 a4 b4
interleave3 :: (Shape sh, Repr r1 a, Repr r2 a, Repr r3 a) => Array r1 (sh :. Int) a -> Array r2 (sh :. Int) a -> Array r3 (sh :. Int) a -> Array D (sh :. Int) aSource
Interleave the elements of three arrays.
interleave4 :: (Shape sh, Repr r1 a, Repr r2 a, Repr r3 a, Repr r4 a) => Array r1 (sh :. Int) a -> Array r2 (sh :. Int) a -> Array r3 (sh :. Int) a -> Array r4 (sh :. Int) a -> Array D (sh :. Int) aSource
Interleave the elements of four arrays.
Reduction
foldP :: (Shape sh, Elt a, Unbox a, Repr r a) => (a -> a -> a) -> a -> Array r (sh :. Int) a -> Array U sh aSource
Parallel reduction of the innermost dimension of an arbitray rank array.
The first argument needs to be an associative sequential operator.
The starting element must be neutral with respect to the operator, for
example 0
is neutral with respect to (+)
as 0 + a = a
.
These restrictions are required to support parallel evaluation, as the
starting element may be used multiple times depending on the number of threads.
foldS :: (Shape sh, Elt a, Unbox a, Repr r a) => (a -> a -> a) -> a -> Array r (sh :. Int) a -> Array U sh aSource
Sequential reduction of the innermost dimension of an arbitrary rank array.
Combine this with transpose
to fold any other dimension.
foldAllP :: (Shape sh, Elt a, Unbox a, Repr r a) => (a -> a -> a) -> a -> Array r sh a -> aSource
Parallel reduction of an array of arbitrary rank to a single scalar value.
The first argument needs to be an associative sequential operator.
The starting element must be neutral with respect to the operator,
for example 0
is neutral with respect to (+)
as 0 + a = a
.
These restrictions are required to support parallel evaluation, as the
starting element may be used multiple times depending on the number of threads.
foldAllS :: (Shape sh, Elt a, Unbox a, Repr r a) => (a -> a -> a) -> a -> Array r sh a -> aSource
Sequential reduction of an array of arbitrary rank to a single scalar value.
sumP :: (Shape sh, Num a, Elt a, Unbox a, Repr r a) => Array r (sh :. Int) a -> Array U sh aSource
Sequential sum the innermost dimension of an array.
sumS :: (Shape sh, Num a, Elt a, Unbox a, Repr r a) => Array r (sh :. Int) a -> Array U sh aSource
Sequential sum the innermost dimension of an array.
sumAllP :: (Shape sh, Elt a, Unbox a, Num a, Repr r a) => Array r sh a -> aSource
Parallel sum all the elements of an array.
sumAllS :: (Shape sh, Elt a, Unbox a, Num a, Repr r a) => Array r sh a -> aSource
Sequential sum of all the elements of an array.
:: Unbox a | |
=> (Int -> Bool) | If the Int matches this predicate, |
-> (Int -> a) | ... then pass it to this fn to produce a value |
-> Int | Range between 0 and this maximum. |
-> Array U DIM1 a | Array containing produced values. |
Produce an array by applying a predicate to a range of integers. If the predicate matches, then use the second function to generate the element.
- This is a low-level function helpful for writing filtering operations on arrays.
- Use the integer as the index into the array you're filtering.