repa-array-4.1.0.1: Bulk array representations and operators.

Safe HaskellNone
LanguageHaskell98

Data.Repa.Array.Meta

Contents

Description

Meta arrays either generate elements on the fly, or wrap an inner array to provide an extra features.

Delayed layouts

Delayed layouts represent the elements of an array by a function that computes those elements on demand.

  • D -- Functions from indices to elements.

Index-space layouts

Index-space produce the corresponding index for each element of the array, rather than real data. They can be used to define an array shape without needing to provide element data.

  • L -- Linear spaces.
  • RW -- RowWise spaces.

Combining layouts

Combining layouts combine existing layouts into new ones.

  • W -- Windowed arrays.
  • E -- Dense arrays.
  • T2 -- Tupled arrays.

Array fusion

Array fusion is achieved via the delayed (D) layout and the computeS function. For example:

> import Data.Repa.Array
> computeS U $ A.map (+ 1) $ A.map (* 2) $ fromList U [1 .. 100 :: Int]

Lets look at the result of the first map:

> :type A.map (* 2) $ fromList U [1 .. 100 :: Int]
A.map (* 2) $ fromList U [1 .. 100 :: Int] 
    :: Array (D U) Int

In the type Array (D U) Int, the outer D indicates that the array is represented as a function that computes each element on demand.

Applying a second map layers another element-producing function on top:

> :type A.map (+ 1) $ A.map (* 2) $ fromList U [1 .. 100 :: Int]
A.map (+ 1) $ A.map (* 2) $ fromList U [1 .. 100 :: Int]
    :: Array (D (D U)) Int

At runtime, indexing into an array of the above type involves calling the outer D-elayed function, which calls the inner D-elayed function, which retrieves source data from the inner U-nboxed array. Although this works, indexing into a deep stack of delayed arrays can be quite expensive.

To fully evaluate a delayed array, use the computeS function, which computes each element of the array sequentially. We pass computeS the name of the desired result layout, in this case we use U to indicate an unboxed array of values:

> :type computeS U $ A.map (+ 1) $ A.map (* 2) $ fromList U [1 .. 100 :: Int]
computeS U $ A.map (+ 1) $ A.map (* 2) $ fromList U [1 .. 100 :: Int]
     :: Array U Int

At runtime, each element of the result will be computed by first reading the source element, applying (*2) to it, then applying (+1) to it, then writing to the result array. Array "fusion" is achieved by the fact that result of applying (*2) to an element is used directly, without writing it to an intermediate buffer.

An added bonus is that during compilation, the GHC simplifier will inline the definitions of map and computeS, then eliminate the intermediate function calls. In the compiled code all intermediate values will be stored unboxed in registers, without any overhead due to boxing or laziness.

When used correctly, array fusion allows Repa programs to run as fast as equivalents in C or Fortran. However, without fusion the programs typically run 10-20x slower (so remember apply computeS to delayed arrays).

Synopsis

Delayed arrays

data D l Source

Delayed arrays wrap functions from an index to element value. The index space is specified by an inner layout, l.

Every time you index into a delayed array the element at that position is recomputed.

Constructors

Delayed 

Fields

delayedLayout :: l
 

Instances

Eq (Name l) => Eq (Name (D l)) 
Eq l => Eq (D l) 
Show (Name l) => Show (Name (D l)) 
Show l => Show (D l) 
Layout l => Layout (D l)

Delayed arrays.

Layout l => Bulk (D l) a

Delayed arrays.

(Layout l1, Target l2 a) => Load (D l1) l2 a 
data Name (D l) = D (Name l) 
type Index (D l) = Index l 
data Array (D l) = ADelayed !l (Index l -> a) 

fromFunction :: l -> (Index l -> a) -> Array (D l) a Source

Wrap a function as a delayed array.

> toList $ fromFunction (Linear 10) (* 2)
    = [0, 2, 4, 6, 8, 10, 12, 14, 16, 18]

toFunction :: Bulk l a => Array (D l) a -> (l, Index l -> a) Source

Produce the extent of an array, and a function to retrieve an arbitrary element.

delay :: Bulk l a => Array l a -> Array (D l) a Source

Wrap an existing array in a delayed one.

map :: Bulk l a => (a -> b) -> Array l a -> Array (D l) b Source

Apply a worker function to each element of an array, yielding a new array with the same extent.

The resulting array is delayed, meaning every time you index into it the element at that index is recomputed.

data D2 l1 l2 Source

A delayed array formed from two source arrays. The source arrays can have different layouts but must have the same extent.

Constructors

Delayed2 

Fields

delayed2Layout1 :: l1
 
delayed2Layout2 :: l2
 

Instances

(Eq (Name l1), Eq (Name l2)) => Eq (Name (D2 l1 l2)) 
(Show (Name l1), Show (Name l2)) => Show (Name (D2 l1 l2)) 
(Eq l1, Eq l2) => Eq (D2 l1 l2) 
(Show l1, Show l2) => Show (D2 l1 l2) 
(Layout l1, Layout l2, (~) * (Index l1) (Index l2)) => Layout (D2 l1 l2)

Delayed arrays.

(Layout l1, Layout l2, (~) * (Index l1) (Index l2)) => Bulk (D2 l1 l2) a

Delayed arrays.

(Layout lSrc1, Layout lSrc2, Target lDst a, (~) * (Index lSrc1) (Index lSrc2)) => Load (D2 lSrc1 lSrc2) lDst a 
data Name (D2 l1 l2) = D2 (Name l1) (Name l2) 
type Index (D2 l1 l2) = Index l1 
data Array (D2 l1 l2) = ADelayed2 !l1 !l2 (Index l1 -> a) 

delay2 :: (Bulk l1 a, Bulk l2 b, Index l1 ~ Index l2) => Array l1 a -> Array l2 b -> Maybe (Array (D2 l1 l2) (a, b)) Source

Wrap two existing arrays in a delayed array.

map2 :: (Bulk l1 a, Bulk l2 b, Index l1 ~ Index l2) => (a -> b -> c) -> Array l1 a -> Array l2 b -> Maybe (Array (D2 l1 l2) c) Source

Combine two arrays element-wise using the given worker function.

The two source arrays must have the same extent, else Nothing.

Linear spaces

data L Source

A linear layout with the elements indexed by integers.

  • Indexing is not bounds checked. Indexing outside the extent yields the corresponding index.

Constructors

Linear 

Fields

linearLength :: Int
 

Instances

Eq L 
Show L 
Layout L

Linear layout.

Bulk L Int

Linear arrays.

Eq (Name L) 
Show (Name L) 
data Name L = L 
type Index L = Int 
data Array L Int = LArray Int 

linear :: Int -> Array L Int Source

Construct a linear array that produces the corresponding index for every element.

> toList $ linear 10
   [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

RowWise spaces

data RW sh Source

A row-wise layout that maps higher rank indices to linear ones in a row-major order.

Indices are ordered so the inner-most coordinate varies most frequently:

> Prelude.map (fromIndex (RowWise (ish2 2 3))) [0..5]
   [(Z :. 0) :. 0, (Z :. 0) :. 1, (Z :. 0) :. 2, 
    (Z :. 1) :. 0, (Z :. 1) :. 1, (Z :. 1) :. 2]
  • Indexing is not bounds checked. Indexing outside the extent yields the corresponding index.

Constructors

RowWise 

Fields

rowWiseShape :: !sh
 

Instances

Eq (Name (RW sh)) => Eq (Name (RW ((:.) sh Int))) 
Eq (Name (RW Z)) 
Eq sh => Eq (RW sh) 
Show (Name (RW sh)) => Show (Name (RW ((:.) sh Int))) 
Show (Name (RW Z)) 
Show sh => Show (RW sh) 
Shape sh => Shape (RW sh) 
(Layout (RW sh), (~) * (Index (RW sh)) sh) => Layout (RW ((:.) sh Int)) 
Layout (RW Z) 
(Layout (RW sh), (~) * (Index (RW sh)) sh) => Bulk (RW sh) sh

Row-wise arrays.

data Name (RW ((:.) sh Int)) = RC (Name (RW sh)) 
data Name (RW Z) = RZ 
type Index (RW ((:.) sh Int)) = (:.) sh Int 
type Index (RW Z) = Z 
data Array (RW sh) sh = RArray sh 

rowWise :: sh -> Array (RW sh) sh Source

Construct a rowWise array that produces the corresponding index for every element.

> toList $ rowWise (ish2 3 2) 
   [(Z :. 0) :. 0, (Z :. 0) :. 1,
    (Z :. 1) :. 0, (Z :. 1) :. 1,
    (Z :. 2) :. 0, (Z :. 2) :. 1]

Windowed arrays

data W l Source

Constructors

Window 

Fields

windowStart :: Index l
 
windowSize :: Index l
 
windowInner :: l
 

Instances

Eq (Name l) => Eq (Name (W l)) 
(Eq l, Eq (Index l)) => Eq (W l) 
Show (Name l) => Show (Name (W l)) 
(Show l, Show (Index l)) => Show (W l) 
Layout l => Layout (W l)

Windowed arrays.

Bulk l a => Bulk (W l) a

Windowed arrays.

Bulk l a => Windowable (W l) a

Windows are windowable.

data Name (W l) = W (Name l) 
type Index (W l) = Index l 
data Array (W l) = WArray !(Index l) !(Index l) !(Array l a) 

class Bulk l a => Windowable l a where Source

Class of array representations that can be windowed directly.

The underlying representation can encode the window, without needing to add a wrapper to the existing layout.

Methods

window :: Index l -> Index l -> Array l a -> Array l a Source

Instances

Storable a => Windowable S a 
Windowable B a

Boxed windows.

Storable a => Windowable F a

Windowing Foreign arrays.

Unbox a => Windowable U a

Windowing Unboxed arrays.

Windowable A Char 
Windowable A Double 
Windowable A Float 
Windowable A Int 
Windowable A Int8 
Windowable A Int16 
Windowable A Int32 
Windowable A Int64 
Windowable A Word8 
Windowable A Date32 
Bulk A a => Windowable A [a] 
(BulkI l a, Windowable l a) => Windowable N (Array l a)

Windowing Nested arrays.

(Windowable A a, Windowable A b) => Windowable A (a, b) 
(Windowable A a, Windowable A b) => Windowable A ((:*:) a b) 
(Bulk A a, Windowable l a, (~) * (Index l) Int) => Windowable A (Array l a) 
Bulk l a => Windowable (W l) a

Windows are windowable.

(Windowable l1 a, Windowable l2 b, (~) * (Index l1) (Index l2)) => Windowable (T2 l1 l2) (a, b)

Tupled windows.

windowed :: Index l -> Index l -> Array l a -> Array (W l) a Source

Wrap a window around an exiting array.

entire :: Bulk l a => Array l a -> Array (W l) a Source

Wrap a window around an existing array that encompases the entire array.

tail :: (Windowable l a, Index l ~ Int) => Array l a -> Maybe (Array l a) Source

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

init :: (Windowable l a, Index l ~ Int) => Array l a -> Maybe (Array l a) Source

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

Dense arrays

data E r l Source

The Dense layout maps a higher-ranked index space to some underlying linear index space.

For example, we can create a dense 2D row-wise array where the elements are stored in a flat unboxed vector:

> import Data.Repa.Array.Material
> let Just arr  = fromListInto (matrix U 10 10) [1000..1099 :: Float]

> :type arr
arr :: Array (E U (RW DIM2) Float

> arr ! (Z :. 5 :. 4)
> 1054.0

Constructors

Dense r l 

Instances

(Eq (Name r), Eq (Name l)) => Eq (Name (E r l)) 
(Show (Name r), Show (Name l)) => Show (Name (E r l)) 
(Eq r, Eq l) => Eq (E r l) 
(Show r, Show l) => Show (E r l) 
((~) * (Index r) Int, Layout r, Layout l) => Layout (E r l)

Dense arrays.

((~) * (Index r) Int, Layout l, Bulk r a) => Bulk (E r l) a

Dense arrays.

(Layout l, (~) * (Index r) Int, Target r a) => Target (E r l) a

Dense buffers.

Unpack (Buffer r a) tBuf => Unpack (Buffer (E r l) a) (l, tBuf) 
data Name (E r l) = E (Name r) (Name l) 
type Index (E r l) = Index l 
data Array (E r l) = Array l (Array r a) 
data Buffer (E r l) = EBuffer !l !(Buffer r a) 

vector :: LayoutI l => Name l -> Int -> E l DIM1 Source

Yield a layout for a dense vector of the given length.

The first argument is the name of the underlying linear layout which stores the elements.

matrix :: LayoutI l => Name l -> Int -> Int -> E l DIM2 Source

Yield a layout for a matrix with the given number of rows and columns.

cube :: LayoutI l => Name l -> Int -> Int -> Int -> E l DIM3 Source

Yield a layout for a cube with the given number of planes, rows, and columns.

Tupled arrays

data T2 l1 l2 Source

Tupled arrays where the components are unpacked and can have separate representations.

Constructors

Tup2 !l1 !l2 

Instances

(Convert A a1 A a2, Convert A b1 A b2) => Convert A (a1, b1) (T2 A A) (a2, b2) 
(Eq (Name l1), Eq (Name l2)) => Eq (Name (T2 l1 l2)) 
(Show (Name l1), Show (Name l2)) => Show (Name (T2 l1 l2)) 
(Eq l1, Eq l2) => Eq (T2 l1 l2) 
(Show (Array l1 a), Show (Array l2 b)) => Show (Array (T2 l1 l2) (a, b)) 
(Show l1, Show l2) => Show (T2 l1 l2) 
((~) * (Index l1) (Index l2), Layout l1, Layout l2) => Layout (T2 l1 l2) 
(Unpack (Buffer r1 a) t1, Unpack (Buffer r2 b) t2) => Unpack (Buffer (T2 r1 r2) (a, b)) (t1, t2) 
(Bulk l1 a, Bulk l2 b, (~) * (Index l1) (Index l2)) => Bulk (T2 l1 l2) (a, b)

Tupled arrays.

(Windowable l1 a, Windowable l2 b, (~) * (Index l1) (Index l2)) => Windowable (T2 l1 l2) (a, b)

Tupled windows.

(Target l1 a, Target l2 b, (~) * (Index l1) (Index l2)) => Target (T2 l1 l2) (a, b)

Tupled buffers.

(Convert A a1 A a2, Convert A b1 A b2) => Convert (T2 A A) (a1, b1) A (a2, b2) 
data Name (T2 l1 l2) = T2 !(Name l1) !(Name l2) 
type Index (T2 l1 l2) = Index l1 
data Array (T2 l1 l2) (a, b) = T2Array !(Array l1 a) !(Array l2 b) 
data Buffer (T2 l1 l2) (a, b) = T2Buffer !(Buffer l1 a) !(Buffer l2 b) 

tup2 :: (Bulk l1 a, Bulk l2 b, Index l1 ~ Index l2) => Array l1 a -> Array l2 b -> Array (T2 l1 l2) (a, b) Source

Tuple two arrays into an array of pairs.

The two argument arrays must have the same index type, but can have different extents. The extent of the result is the intersection of the extents of the two argument arrays.

untup2 :: Array (T2 l1 l2) (a, b) -> (Array l1 a, Array l2 b) Source

Untuple an array of tuples in to a tuple of arrays.

  • The two returned components may have different extents, though they are guaranteed to be at least as big as the argument array. This is the key property that makes untup2 different from unzip.