Data.Repa.Array

NOTE: This is an ALPHA version of Repa 4. The API is not yet complete with respect to Repa 3. Some important functions are still missing, and the docs may not be up-to-date.

How to write fast code

1. Add INLINE pragmas to all leaf-functions in your code, expecially ones that compute numeric results. Non-inlined lazy function calls can cost upwards of 50 cycles each, while each numeric operator only costs one (or less). Inlining leaf functions also ensures they are specialised at the appropriate numeric types.

1. Add bang patterns to all function arguments, and all fields of your data types. In a high-performance Haskell program, the cost of lazy evaluation can easily dominate the run time if not handled correctly. You don't want to rely on the strictness analyser in numeric code because if it does not return a perfect result then the performance of your program will be awful. This is less of a problem for general Haskell code, and in a different context relying on strictness analysis is fine.
2. Compile your program with ghc -O2 -fllvm -optlo-O3. The LLVM compiler produces better object code that GHC's internal native code generator.

Documentation

type Array a = Array A a

Arrays of elements that are automatically layed out into some efficient runtime representation.

The implementation uses type families to chose unboxed representations for all elements that can be unboxed. In particular: arrays of unboxed tuples are represented as tuples of unboxed arrays, and nested arrays are represented using a segment descriptor and a single single flat vector containing all the elements.

type Elem a = (Bulk A a, Windowable A a)

Class of elements that can be automatically organised into arrays.

type Build a = (Bulk A a, Target A a)

Class of elements where arrays of those elements can be constructed in arbitrary order.

Basics

index :: Elem a => Array a -> Int -> a

O(1). Get an element from an array.

If the provided index is outside the extent of the array then the result depends on the layout.

(!) :: Elem a => Array a -> Int -> a

O(1). Alias for index

length :: Elem a => Array a -> Int

O(1). Get the number of elements in an array.

first :: Elem a => Array a -> Maybe a

O(1). Take the first element of an array, or Nothing if it's empty.

last :: Elem a => Array a -> Maybe a

O(1). Take the last element of an array, or Nothing if it's empty.

head :: Elem a => Array a -> Maybe a

O(1). alias for first.

tail :: Elem a => Array a -> Maybe (Array a)

O(1). Take the tail of an array, or Nothing if it's empty.

init :: Elem a => Array a -> Maybe (Array a)

O(1). Take the initial elements of an array, or Nothing if it's empty.

Construction

empty :: Build a => Array a

O(1). An empty array of the given layout.

singleton :: Build a => a -> Array a

O(1). Create a new empty array containing a single element.

generateMaybeS :: Build a => Int -> (Int -> Maybe a) -> Maybe (Array a)

Like generateS but use a function that produces Maybe an element. If any element returns Nothing, then Nothing for the whole array.

generateEitherS :: Build a => Int -> (Int -> Either err a) -> Either err (Array a)

Like generateS but use a function that produces Either some error or an element. If any element returns Nothing, then Nothing for the whole array.

Conversion

fromList :: Build a => [a] -> Array a

Convert a list to an array.

fromLists :: Build a => [[a]] -> Array (Array a)

Convert a nested list to an array.

fromListss :: Build a => [[[a]]] -> Array (Array (Array a))

Convert a triply nested list to a triply nested array.

toList :: Elem a => Array a -> [a]

Convert an array to a list.

toLists :: (Elem a, Elem (Array a)) => Array (Array a) -> [[a]]

Convert a nested array to some lists.

toListss :: (Elem a, Elem (Array a), Elem (Array (Array a))) => Array (Array (Array a)) -> [[[a]]]

Convert a triply nested array to a triply nested list.

Operators

Replicating

replicates :: (Elem a, Build a) => Array (Int, a) -> Array a

Segmented replicate.

Mapping

map :: (Elem a, Build b) => (a -> b) -> Array a -> Array b

Apply a function to all the elements of a list.

map2 :: (Elem a, Elem b, Build c) => (a -> b -> c) -> Array a -> Array b -> Maybe (Array c)

Combine two arrays of the same length element-wise.

If the arrays don't have the same length then Nothing.

mapElems :: (Array a -> Array b) -> Array (Array a) -> Array (Array b)

Apply a function to all the elements of a doubly nested array, preserving the nesting structure.

• This function has a non-standard time complexity. As nested arrays use a segment descriptor based representation, detatching and reattaching the nesting structure is a constant time operation. However, the array passed to the worker function will also contain any elements in the array representation that are not reachable from the segment descriptor. This matters if the source array was produced by a function that filters the segments directly, like slices.

Folding

foldl :: Elem b => (a -> b -> a) -> a -> Array b -> a

Left fold of all elements in an array.

folds

Arguments

:: (Elem a, Build n, Build b)

=> (a -> b -> b)

Worker function.

-> b

Initial state when folding segments.

-> Array (n, Int)

Segment names and lengths.

-> Array a

Elements.

-> (Array (n, b), Folds Int Int n a b)

Segmented fold over vectors of segment lengths and input values.

• The total lengths of all segments need not match the length of the input elements vector. The returned Folds state can be inspected to determine whether all segments were completely folded, or the vector of segment lengths or elements was too short relative to the other.

foldsWith

Arguments

:: (Elem a, Build n, Build b)

=> (a -> b -> b)

Worker function.

-> b

Initial state when folding segments.

-> Maybe (n, Int, b)

Name, length and initial state for first segment.

-> Array (n, Int)

Segment names and lengths.

-> Array a

Elements.

-> (Array (n, b), Folds Int Int n a b)

Like folds, but take an initial state for the first segment.

Special Folds

sum :: (Elem a, Num a) => Array a -> a

Yield the sum of the elements of an array.

product :: (Elem a, Num a) => Array a -> a

Yield the product of the elements of an array.

mean :: (Elem a, Fractional a) => Array a -> a

Yield the mean value of the elements of an array.

std :: (Elem a, Floating a) => Array a -> a

Yield the standard deviation of the elements of an array

correlate :: (Elem a, Floating a) => Array a -> Array a -> a

Compute the Pearson correlation of two arrays.

If the arrays differ in length then only the common prefix is correlated.

Filtering

filter :: Build a => (a -> Bool) -> Array a -> Array a

O(len src) Keep the elements of an array that match the given predicate.

slices

Arguments

:: Array Int

Segment starting positions.

-> Array Int

Segment lengths.

-> Array a

Array elements.

-> Array (Array a)

O(1). Produce a nested array by taking slices from some array of elements.

• This is a constant time operation, as the representation for nested vectors just wraps the starts, lengths and elements vectors.

trims :: Elem a => (a -> Bool) -> Array (Array a) -> Array (Array a)

For each segment of a nested vector, trim elements off the start and end of the segment that match the given predicate.

trimEnds :: Elem a => (a -> Bool) -> Array (Array a) -> Array (Array a)

For each segment of a nested array, trim elements off the end of the segment that match the given predicate.

trimStarts :: Elem a => (a -> Bool) -> Array (Array a) -> Array (Array a)

For each segment of a nested array, trim elements off the start of the segment that match the given predicate.

Zipping

zip :: (Elem a, Elem b) => Array a -> Array b -> Array (a, b)

O(1). Pack a pair of arrays to an array of pairs.

unzip :: (Elem a, Elem b) => Array (a, b) -> (Array a, Array b)

O(1). Unpack an array of pairs to a pair of arrays.

Sloshing

reverse :: Build a => Array a -> Array a

O(n). Reverse the elements of a list.

> toList $ reverse $ fromList [0 .. 10 :: Int]
[10,9,8,7,6,5,4,3,2,1,0]

concat

Arguments

:: (Elem a, Build a)

=> Array (Array a)

Arrays to concatenate.

-> Array a

Concatenate nested arrays.

concats :: Array (Array (Array a)) -> Array (Array a)

O(len result) Concatenate the outer two layers of a triply nested array. (Segmented concatenation).

• The operation is performed entirely on the segment descriptors of the array, and does not require the inner array elements to be copied.
• This version is faster than plain concat on triply nested arrays.

concatWith

Arguments

:: (Elem a, Build a)

=> Array a

Separator array.

-> Array (Array a)

Arrays to concatenate.

-> Array a

O(len result) Concatenate the elements of some nested vector, inserting a copy of the provided separator array between each element.

unlines :: Array (Array Char) -> Array Char

O(len result) Perform a concatWith, adding a newline character to the end of each inner array.

intercalate

Arguments

:: (Elem a, Build a)

=> Array a

Separator array.

-> Array (Array a)

Arrays to concatenate.

-> Array a

O(len result) Insert a copy of the separator array between the elements of the second and concatenate the result.

ragspose3 :: Array (Array (Array a)) -> Array (Array (Array a))

Ragged transpose of a triply nested array.

• This operation is performed entirely on the segment descriptors of the nested arrays, and does not require the inner array elements to be copied.

Slicing

slice :: Elem a => Int -> Int -> Array a -> Maybe (Array a)

Take a slice out of an array, given a starting position and length.

Inserting

insert :: Build a => (Int -> Maybe a) -> Array a -> Array a

Insert elements produced by the given function in to an array.

Searching

findIndex :: Elem a => (a -> Bool) -> Array a -> Maybe Int

O(len src) Yield Just the index of the first element matching the predicate or Nothing if no such element exists.

Merging

merge

Arguments

:: (Ord k, Elem (k, a), Elem (k, b), Build (k, c))

=> (k -> a -> b -> c)

Combine two values with the same key.

-> (k -> a -> c)

Handle a left value without a right value.

-> (k -> b -> c)

Handle a right value without a left value.

-> Array (k, a)

Array of keys and left values.

-> Array (k, b)

Array of keys and right values.

-> Array (k, c)

Array of keys and results.

Merge two sorted key-value streams.

mergeMaybe

Arguments

:: (Ord k, Elem (k, a), Elem (k, b), Build (k, c))

=> (k -> a -> b -> Maybe c)

Combine two values with the same key.

-> (k -> a -> Maybe c)

Handle a left value without a right value.

-> (k -> b -> Maybe c)

Handle a right value without a left value.

-> Array (k, a)

Array of keys and left values.

-> Array (k, b)

Array of keys and right values.

-> Array (k, c)

Array of keys and results.

Like merge, but only produce the elements where the worker functions return Just.

Compacting

compact :: (Elem a, Build b) => (s -> a -> (s, Maybe b)) -> s -> Array a -> Array b

Combination of fold and filter.

We walk over the stream front to back, maintaining an accumulator. At each point we can chose to emit an element (or not)

compactIn :: Build a => (a -> a -> (a, Maybe a)) -> Array a -> Array a

Like compact but use the first value of the stream as the initial state, and add the final state to the end of the output.

Grouping

groups

Arguments

:: (Eq a, Build a)

=> Array a

Input elements.

-> (Array (a, Int), Maybe (a, Int))

Completed and final segment lengths.

From a stream of values which has consecutive runs of idential values, produce a stream of the lengths of these runs.

groupsWith

Arguments

:: Build a

=> (a -> a -> Bool)

Comparison function.

-> Maybe (a, Int)

Starting element and count.

-> Array a

Input elements.

-> (Array (a, Int), Maybe (a, Int))

Completed and final segment lengths.

Like groups, but use the given function to determine whether two consecutive elements should be in the same group. Also take an initial starting group and count.

Splitting

segment

Arguments

:: (Elem a, Unbox a)

=> (a -> Bool)

Detect the start of a segment.

-> (a -> Bool)

Detect the end of a segment.

-> Array a

Array to segment.

-> Array (Array a)

O(len src). Given predicates which detect the start and end of a segment, split an vector into the indicated segments.

segmentOn

Arguments

:: (Elem a, Unbox a)

=> (a -> Bool)

Detect the end of a segment.

-> Array a

Array to segment.

-> Array (Array a)

O(len src). Given a terminating value, split an vector into segments.

The result segments do not include the terminator.

dice

Arguments

:: (Elem a, Unbox a)

=> (a -> Bool)

Detect the start of an inner segment.

-> (a -> Bool)

Detect the end of an inner segment.

-> (a -> Bool)

Detect the start of an outer segment.

-> (a -> Bool)

Detect the end of an outer segment.

-> Array a

Array to dice.

-> Array (Array (Array a))

O(len src). Like segment, but cut the source array twice.

diceSep

Arguments

:: (Elem a, Eq a)

=> a

Terminating element for inner segments.

-> a

Terminating element for outer segments.

-> Array a

Vector to dice.

-> Array (Array (Array a))

O(len src). Given field and row terminating values, split an array into rows and fields.

Products

Generic

prod :: Array A a -> Array A b -> Array A (a :*: b)

Form the product of two arrays, in constant time.

unprod :: Array A (a :*: b) -> (Array A a, Array A b)

Unpack a product of two arrays, in constant time.

Pattern synonyms

These patterns patterns work on arrays of arbitrary element type.

(Haddock 2.16.0 has a bug where the type signatures come out monomorphic)

pattern Prod2 :: forall a a1. Int -> Array A a -> Array A a1 -> Array A ((:*:) a ((:*:) a1 ()))

pattern Prod3 :: forall a a1 a2. Int -> Array A a -> Array A a1 -> Array A a2 -> Array A ((:*:) a ((:*:) a1 ((:*:) a2 ())))

pattern Prod4 :: forall a a1 a2 a3. Int -> Array A a -> Array A a1 -> Array A a2 -> Array A a3 -> Array A ((:*:) a ((:*:) a1 ((:*:) a2 ((:*:) a3 ()))))

pattern Prod5 :: forall a a1 a2 a3 a4. Int -> Array A a -> Array A a1 -> Array A a2 -> Array A a3 -> Array A a4 -> Array A ((:*:) a ((:*:) a1 ((:*:) a2 ((:*:) a3 ((:*:) a4 ())))))

pattern Prod6 :: forall a a1 a2 a3 a4 a5. Int -> Array A a -> Array A a1 -> Array A a2 -> Array A a3 -> Array A a4 -> Array A a5 -> Array A ((:*:) a ((:*:) a1 ((:*:) a2 ((:*:) a3 ((:*:) a4 ((:*:) a5 ()))))))

pattern Prod7 :: forall a a1 a2 a3 a4 a5 a6. Int -> Array A a -> Array A a1 -> Array A a2 -> Array A a3 -> Array A a4 -> Array A a5 -> Array A a6 -> Array A ((:*:) a ((:*:) a1 ((:*:) a2 ((:*:) a3 ((:*:) a4 ((:*:) a5 ((:*:) a6 ())))))))

pattern Prod8 :: forall a a1 a2 a3 a4 a5 a6 a7. Int -> Array A a -> Array A a1 -> Array A a2 -> Array A a3 -> Array A a4 -> Array A a5 -> Array A a6 -> Array A a7 -> Array A ((:*:) a ((:*:) a1 ((:*:) a2 ((:*:) a3 ((:*:) a4 ((:*:) a5 ((:*:) a6 ((:*:) a7 ()))))))))

pattern Prod9 :: forall a a1 a2 a3 a4 a5 a6 a7 a8. Int -> Array A a -> Array A a1 -> Array A a2 -> Array A a3 -> Array A a4 -> Array A a5 -> Array A a6 -> Array A a7 -> Array A a8 -> Array A ((:*:) a ((:*:) a1 ((:*:) a2 ((:*:) a3 ((:*:) a4 ((:*:) a5 ((:*:) a6 ((:*:) a7 ((:*:) a8 ())))))))))