repa-array-4.0.0.1: Data/Repa/Array.hs
--
-- | 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.
--
-- A Repa array is a wrapper around an underlying container structure that
-- holds the array elements.
--
-- In the type (`Array` @l@ @a@), the @l@ specifies the `Layout` of data,
-- which includes the type of the underlying container, as well as how
-- the elements should be arranged in that container. The @a@ specifies
-- the element type.
--
-- === Material layouts
--
-- Material layouts hold real data and are defined in "Data.Repa.Array.Material".
--
-- For performance reasons, random access indexing into these layouts
-- is not bounds checked. However, all bulk operators like @map@ and @concat@
-- are guaranteed to be safe.
--
-- * `B` -- Boxed vectors.
--
-- * `U` -- Adaptive unboxed vectors.
--
-- * `F` -- Foreign memory buffers.
--
-- * `N` -- Nested arrays.
--
--
-- === 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.
--
-- === Meta layouts
--
-- Meta 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).
--
-- === 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.
--
-- 2. 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.
--
-- 3. Compile your program with @ghc -O2 -fllvm -optlo-O3@. The LLVM compiler
-- produces better object code that GHC's internal native code generator.
--
module Data.Repa.Array
( module Data.Repa.Array.Index
, Name (..)
, Bulk (..), BulkI
, (!)
, length
-- * Index arrays
-- | Index arrays define an index space but do not contain concrete
-- element values. Indexing into any point in the array produces
-- the index at that point. Index arrays are typically used to
-- provide an array shape to other array operators.
-- ** Linear spaces
, L(..)
, linear
-- ** RowWise spaces
, RW(..)
, rowWise
-- * Meta arrays
-- ** Delayed arrays
, D(..)
, fromFunction
, toFunction
, delay
, D2(..)
, delay2
-- ** Windowed arrays
, W(..)
, Windowable (..)
, windowed
, entire
-- ** Tupled arrays
, T2(..)
, tup2
, untup2
-- * Material arrays
-- | Material arrays are represented as concrete data in memory
-- and are defined in "Data.Repa.Array.Material". Indexing into these
-- arrays is not bounds checked, so you may want to use them in
-- conjunction with a @C@hecked layout.
, Material
-- ** Dense arrays
, E (..)
, vector
, matrix
, cube
-- * Conversion
, fromList, fromListInto
, toList
-- * Computation
, Load
, Target
, computeS, computeIntoS
-- * Operators
-- ** Index space
-- | Index space transforms view the elements of an array in a different
-- order, but do not compute new elements. They are all constant time
-- operations as the location of the required element in the source
-- array is computed on demand.
, reverse
-- ** Mapping
, map, map2
, mapS, map2S
-- ** Filtering
, filter
-- ** Searching
, findIndex
-- ** Sloshing
-- | Sloshing operators copy array elements into a different arrangement,
-- but do not create new element values.
, concat
, concatWith, unlines
, intercalate
, ConcatDict
, partition
, partitionBy
, partitionByIx
-- ** Grouping
, groups
, groupsWith
, GroupsDict
-- ** Folding
, foldl
, folds
, foldsWith
, Folds(..)
, FoldsDict)
where
import Data.Repa.Array.Index
import Data.Repa.Array.Linear as A
import Data.Repa.Array.Dense as A
import Data.Repa.Array.RowWise as A
import Data.Repa.Array.Delayed as A
import Data.Repa.Array.Delayed2 as A
import Data.Repa.Array.Window as A
import Data.Repa.Array.Tuple as A
import Data.Repa.Eval.Array as A
import Data.Repa.Array.Internals.Target as A
import Data.Repa.Array.Internals.Bulk as A
import Data.Repa.Array.Internals.Operator.Concat as A
import Data.Repa.Array.Internals.Operator.Group as A
import Data.Repa.Array.Internals.Operator.Fold as A
import Data.Repa.Array.Internals.Operator.Partition as A
import Data.Repa.Array.Internals.Operator.Reduce as A
import Data.Repa.Array.Internals.Operator.Filter as A
import qualified Data.Vector.Fusion.Stream.Monadic as V
import Control.Monad
import Prelude
hiding (reverse, length, map, zipWith, concat, unlines, foldl, filter)
#include "repa-array.h"
-- | Classes supported by all material representations.
--
-- We can index them in a random-access manner,
-- window them in constant time,
-- and use them as targets for a computation.
--
-- In particular, delayed arrays are not material as we cannot use them
-- as targets for a computation.
--
type Material l a
= (Bulk l a, Windowable l a, Target l a)
-- | O(1). View the elements of a vector in reverse order.
--
-- @
-- > toList $ reverse $ fromList U [0..10 :: Int]
-- [10,9,8,7,6,5,4,3,2,1,0]
-- @
reverse :: BulkI l a
=> Array l a -> Array (D l) a
reverse !arr
= let !len = size (extent $ layout arr)
get ix = arr `index` (len - ix - 1)
in fromFunction (layout arr) get
{-# INLINE_ARRAY reverse #-}
-- | O(len src) Yield `Just` the index of the first element matching the predicate
-- or `Nothing` if no such element exists.
findIndex :: BulkI l a
=> (a -> Bool) -> Array l a -> Maybe Int
findIndex p !arr
= loop_findIndex V.SPEC 0
where
!len = size (extent $ layout arr)
loop_findIndex !sPEC !ix
| ix >= len = Nothing
| otherwise
= let !x = arr `index` ix
in if p x then Just ix
else loop_findIndex sPEC (ix + 1)
{-# INLINE_INNER loop_findIndex #-}
{-# INLINE_ARRAY findIndex #-}
-- | Like `A.map`, but immediately `computeS` the result.
mapS :: (Bulk lSrc a, Target lDst b, Index lSrc ~ Index lDst)
=> Name lDst -- ^ Name of destination layout.
-> (a -> b) -- ^ Worker function.
-> Array lSrc a -- ^ Source array.
-> Array lDst b
mapS l f !xs = computeS l $! A.map f xs
{-# INLINE mapS #-}
-- | Like `A.map2`, but immediately `computeS` the result.
map2S :: (Bulk lSrc1 a, Bulk lSrc2 b, Target lDst c
, Index lSrc1 ~ Index lDst
, Index lSrc2 ~ Index lDst)
=> Name lDst -- ^ Name of destination layout.
-> (a -> b -> c ) -- ^ Worker function.
-> Array lSrc1 a -- ^ Source array.
-> Array lSrc2 b -- ^ Source array
-> Maybe (Array lDst c)
map2S l f xs ys
= liftM (computeS l) $! A.map2 f xs ys
{-# INLINE map2S #-}