Data.Array.Base
| Copyright | (c) The University of Glasgow 2001 |
|---|---|
| License | BSD-style (see the file libraries/base/LICENSE) |
| Maintainer | libraries@haskell.org |
| Stability | experimental |
| Portability | non-portable (MPTCs, uses Control.Monad.ST) |
| Safe Haskell | None |
| Language | Haskell2010 |
Description
Basis for IArray and MArray. Not intended for external consumption; use IArray or MArray instead.
WARNING
This module is considered internal.
The Package Versioning Policy does not apply.
The contents of this module may change in any way whatsoever and without any warning between minor versions of this package.
Authors importing this module are expected to track development closely.
class IArray (a :: Type -> Type -> Type) e where Source
Class of immutable array types.
An array type has the form (a i e) where a is the array type constructor (kind * -> * -> *), i is the index type (a member of the class Ix), and e is the element type. The IArray class is parameterised over both a and e, so that instances specialised to certain element types can be defined.
Minimal complete definition
Methods
bounds :: Ix i => a i e -> (i, i) Source
Extracts the bounds of an immutable array
numElements :: Ix i => a i e -> Int Source
unsafeArray :: Ix i => (i, i) -> [(Int, e)] -> a i e Source
unsafeAt :: Ix i => a i e -> Int -> e Source
unsafeReplace :: Ix i => a i e -> [(Int, e)] -> a i e Source
unsafeAccum :: Ix i => (e -> e' -> e) -> a i e -> [(Int, e')] -> a i e Source
unsafeAccumArray :: Ix i => (e -> e' -> e) -> e -> (i, i) -> [(Int, e')] -> a i e Source
Instances
safeRangeSize :: Ix i => (i, i) -> Int Source
safeIndex :: Ix i => (i, i) -> Int -> i -> Int Source
unsafeReplaceST :: (IArray a e, Ix i) => a i e -> [(Int, e)] -> ST s (STArray s i e) Source
unsafeAccumST :: (IArray a e, Ix i) => (e -> e' -> e) -> a i e -> [(Int, e')] -> ST s (STArray s i e) Source
unsafeAccumArrayST :: Ix i => (e -> e' -> e) -> e -> (i, i) -> [(Int, e')] -> ST s (STArray s i e) Source
Arguments
| :: (IArray a e, Ix i) | |
| => (i, i) | bounds of the array: (lowest,highest) |
| -> [(i, e)] | list of associations |
| -> a i e |
Constructs an immutable array from a pair of bounds and a list of initial associations.
The bounds are specified as a pair of the lowest and highest bounds in the array respectively. For example, a one-origin vector of length 10 has bounds (1,10), and a one-origin 10 by 10 matrix has bounds ((1,1),(10,10)).
An association is a pair of the form (i,x), which defines the value of the array at index i to be x. The array is undefined if any index in the list is out of bounds. If any two associations in the list have the same index, the value at that index is implementation-dependent. (In GHC, the last value specified for that index is used. Other implementations will also do this for unboxed arrays, but Haskell 98 requires that for Array the value at such indices is bottom.)
Because the indices must be checked for these errors, array is strict in the bounds argument and in the indices of the association list. Whether array is strict or non-strict in the elements depends on the array type: Array is a non-strict array type, but all of the UArray arrays are strict. Thus in a non-strict array, recurrences such as the following are possible:
a = array (1,100) ((1,1) : [(i, i * a!(i-1)) | i \<- [2..100]])
Not every index within the bounds of the array need appear in the association list, but the values associated with indices that do not appear will be undefined.
If, in any dimension, the lower bound is greater than the upper bound, then the array is legal, but empty. Indexing an empty array always gives an array-bounds error, but bounds still yields the bounds with which the array was constructed.
listArray :: (IArray a e, Ix i) => (i, i) -> [e] -> a i e Source
Constructs an immutable array from a list of initial elements. The list gives the elements of the array in ascending order beginning with the lowest index.
genArray :: (IArray a e, Ix i) => (i, i) -> (i -> e) -> a i e Source
Constructs an immutable array using a generator function.
Since: array-0.5.6.0
listArrayST :: Ix i => (i, i) -> [e] -> ST s (STArray s i e) Source
listUArrayST :: (MArray (STUArray s) e (ST s), Ix i) => (i, i) -> [e] -> ST s (STUArray s i e) Source
type ListUArray e = forall i. Ix i => (i, i) -> [e] -> UArray i e Source
(!) :: (IArray a e, Ix i) => a i e -> i -> e Source
Returns the element of an immutable array at the specified index, or throws an exception if the index is out of bounds.
(!?) :: (IArray a e, Ix i) => a i e -> i -> Maybe e Source
Returns Just the element of an immutable array at the specified index, or Nothing if the index is out of bounds.
Since: array-0.5.6.0
indices :: (IArray a e, Ix i) => a i e -> [i] Source
Returns a list of all the valid indices in an array.
elems :: (IArray a e, Ix i) => a i e -> [e] Source
Returns a list of all the elements of an array, in the same order as their indices.
assocs :: (IArray a e, Ix i) => a i e -> [(i, e)] Source
Returns the contents of an array as a list of associations.
Arguments
| :: (IArray a e, Ix i) | |
| => (e -> e' -> e) | An accumulating function |
| -> e | A default element |
| -> (i, i) | The bounds of the array |
| -> [(i, e')] | List of associations |
| -> a i e | Returns: the array |
Constructs an immutable array from a list of associations. Unlike array, the same index is allowed to occur multiple times in the list of associations; an accumulating function is used to combine the values of elements with the same index.
For example, given a list of values of some index type, hist produces a histogram of the number of occurrences of each index within a specified range:
hist :: (Ix a, Num b) => (a,a) -> [a] -> Array a b hist bnds is = accumArray (+) 0 bnds [(i, 1) | i\<-is, inRange bnds i]
(//) :: (IArray a e, Ix i) => a i e -> [(i, e)] -> a i e Source
Takes an array and a list of pairs and returns an array identical to the left argument except that it has been updated by the associations in the right argument. For example, if m is a 1-origin, n by n matrix, then m//[((i,i), 0) | i <- [1..n]] is the same matrix, except with the diagonal zeroed.
As with the array function, if any two associations in the list have the same index, the value at that index is implementation-dependent. (In GHC, the last value specified for that index is used. Other implementations will also do this for unboxed arrays, but Haskell 98 requires that for Array the value at such indices is bottom.)
For most array types, this operation is O(n) where n is the size of the array. However, the diffarray package provides an array type for which this operation has complexity linear in the number of updates.
accum :: (IArray a e, Ix i) => (e -> e' -> e) -> a i e -> [(i, e')] -> a i e Source
accum f takes an array and an association list and accumulates pairs from the list into the array with the accumulating function f. Thus accumArray can be defined using accum:
accumArray f z b = accum f (array b [(i, z) | i \<- range b])
amap :: (IArray a e', IArray a e, Ix i) => (e' -> e) -> a i e' -> a i e Source
Returns a new array derived from the original array by applying a function to each of the elements.
ixmap :: (IArray a e, Ix i, Ix j) => (i, i) -> (i -> j) -> a j e -> a i e Source
Returns a new array derived from the original array by applying a function to each of the indices.
foldrArray :: (IArray a e, Ix i) => (e -> b -> b) -> b -> a i e -> b Source
Lazy right-associative fold.
Since: array-0.5.8.0
foldlArray' :: (IArray a e, Ix i) => (b -> e -> b) -> b -> a i e -> b Source
Strict accumulating left-associative fold.
Since: array-0.5.8.0
foldlArray :: (IArray a e, Ix i) => (b -> e -> b) -> b -> a i e -> b Source
Lazy left-associative fold.
Since: array-0.5.8.0
foldrArray' :: (IArray a e, Ix i) => (e -> b -> b) -> b -> a i e -> b Source
Strict accumulating right-associative fold.
Since: array-0.5.8.0
traverseArray_ :: (IArray a e, Ix i, Applicative f) => (e -> f b) -> a i e -> f () Source
Map elements to applicative actions, sequence them left-to-right, and discard the results.
Since: array-0.5.8.0
forArray_ :: (IArray a e, Ix i, Applicative f) => a i e -> (e -> f b) -> f () Source
forArray_ is traverseArray_ with its arguments flipped.
Since: array-0.5.8.0
foldlArrayM' :: (IArray a e, Ix i, Monad m) => (b -> e -> m b) -> b -> a i e -> m b Source
Strict accumulating left-associative monadic fold.
Since: array-0.5.8.0
foldrArrayM' :: (IArray a e, Ix i, Monad m) => (e -> b -> m b) -> b -> a i e -> m b Source
Strict accumulating right-associative monadic fold.
Since: array-0.5.8.0
Arrays with unboxed elements. Instances of IArray are provided for UArray with certain element types (Int, Float, Char, etc.; see the UArray class for a full list).
A UArray will generally be more efficient (in terms of both time and space) than the equivalent Array with the same element type. However, UArray is strict in its elements - so don't use UArray if you require the non-strictness that Array provides.
Because the IArray interface provides operations overloaded on the type of the array, it should be possible to just change the array type being used by a program from say Array to UArray to get the benefits of unboxed arrays (don't forget to import Data.Array.Unboxed instead of Data.Array).
Constructors
| UArray !i !i !Int ByteArray# |
Instances
unsafeArrayUArray :: (MArray (STUArray s) e (ST s), Ix i) => (i, i) -> [(Int, e)] -> e -> ST s (UArray i e) Source
unsafeFreezeSTUArray :: STUArray s i e -> ST s (UArray i e) Source
unsafeReplaceUArray :: (MArray (STUArray s) e (ST s), Ix i) => UArray i e -> [(Int, e)] -> ST s (UArray i e) Source
unsafeAccumUArray :: (MArray (STUArray s) e (ST s), Ix i) => (e -> e' -> e) -> UArray i e -> [(Int, e')] -> ST s (UArray i e) Source
unsafeAccumArrayUArray :: (MArray (STUArray s) e (ST s), Ix i) => (e -> e' -> e) -> e -> (i, i) -> [(Int, e')] -> ST s (UArray i e) Source
eqUArray :: (IArray UArray e, Ix i, Eq e) => UArray i e -> UArray i e -> Bool Source
cmpUArray :: (IArray UArray e, Ix i, Ord e) => UArray i e -> UArray i e -> Ordering Source
cmpIntUArray :: (IArray UArray e, Ord e) => UArray Int e -> UArray Int e -> Ordering Source
showsIArray :: (IArray a e, Ix i, Show i, Show e) => Int -> a i e -> ShowS Source
readIArray :: (IArray a e, Ix i, Read i, Read e) => ReadPrec (a i e) Source
nullStablePtr :: StablePtr a Source
arrEleBottom :: a Source
class Monad m => MArray (a :: Type -> Type -> Type) e (m :: Type -> Type) where Source
Class of mutable array types.
An array type has the form (a i e) where a is the array type constructor (kind * -> * -> *), i is the index type (a member of the class Ix), and e is the element type.
The MArray class is parameterised over both a and e (so that instances specialised to certain element types can be defined, in the same way as for IArray), and also over the type of the monad, m, in which the mutable array will be manipulated.
Minimal complete definition
getBounds, getNumElements, (newArray | unsafeNewArray_), unsafeRead, unsafeWrite
Methods
getBounds :: Ix i => a i e -> m (i, i) Source
Returns the bounds of the array (lowest,highest).
getNumElements :: Ix i => a i e -> m Int Source
Returns the number of elements in the array.
newArray :: Ix i => (i, i) -> e -> m (a i e) Source
Builds a new array, with every element initialised to the supplied value. The first and second element of the tuple specifies the lowest and highest index, respectively.
newArray_ :: Ix i => (i, i) -> m (a i e) Source
Builds a new array, with every element initialised to an undefined value. In a monadic context in which operations must be deterministic (e.g. the ST monad), the array elements are initialised to a fixed but undefined value, such as zero. The first and second element of the tuple specifies the lowest and highest index, respectively.
unsafeNewArray_ :: Ix i => (i, i) -> m (a i e) Source
Builds a new array, with every element initialised to an undefined value. The first and second element of the tuple specifies the lowest and highest index, respectively.
unsafeRead :: Ix i => a i e -> Int -> m e Source
unsafeWrite :: Ix i => a i e -> Int -> e -> m () Source
Instances
newListArray :: (MArray a e m, Ix i) => (i, i) -> [e] -> m (a i e) Source
Constructs a mutable array from a list of initial elements. The list gives the elements of the array in ascending order beginning with the lowest index. The first and second element of the tuple specifies the lowest and highest index, respectively.
newGenArray :: (MArray a e m, Ix i) => (i, i) -> (i -> m e) -> m (a i e) Source
Constructs a mutable array using a generator function. It invokes the generator function in ascending order of the indices.
Since: array-0.5.6.0
readArray :: (MArray a e m, Ix i) => a i e -> i -> m e Source
Read an element from a mutable array
writeArray :: (MArray a e m, Ix i) => a i e -> i -> e -> m () Source
Write an element in a mutable array
modifyArray :: (MArray a e m, Ix i) => a i e -> i -> (e -> e) -> m () Source
Modify an element in a mutable array
Since: array-0.5.6.0
modifyArray' :: (MArray a e m, Ix i) => a i e -> i -> (e -> e) -> m () Source
Modify an element in a mutable array. Strict in the written element.
Since: array-0.5.6.0
getElems :: (MArray a e m, Ix i) => a i e -> m [e] Source
Return a list of all the elements of a mutable array
getAssocs :: (MArray a e m, Ix i) => a i e -> m [(i, e)] Source
Return a list of all the associations of a mutable array, in index order.
mapArray :: (MArray a e' m, MArray a e m, Ix i) => (e' -> e) -> a i e' -> m (a i e) Source
Constructs a new array derived from the original array by applying a function to each of the elements.
mapIndices :: (MArray a e m, Ix i, Ix j) => (i, i) -> (i -> j) -> a j e -> m (a i e) Source
Constructs a new array derived from the original array by applying a function to each of the indices.
foldlMArray' :: (MArray a e m, Ix i) => (b -> e -> b) -> b -> a i e -> m b Source
Strict accumulating left-associative fold.
Since: array-0.5.8.0
foldrMArray' :: (MArray a e m, Ix i) => (e -> b -> b) -> b -> a i e -> m b Source
Strict accumulating right-associative fold.
Since: array-0.5.8.0
foldlMArrayM' :: (MArray a e m, Ix i) => (b -> e -> m b) -> b -> a i e -> m b Source
Strict accumulating left-associative monadic fold.
Since: array-0.5.8.0
foldrMArrayM' :: (MArray a e m, Ix i) => (e -> b -> m b) -> b -> a i e -> m b Source
Strict accumulating right-associative monadic fold.
Since: array-0.5.8.0
mapMArrayM_ :: (MArray a e m, Ix i) => (e -> m b) -> a i e -> m () Source
Map elements to monadic actions, sequence them left-to-right, and discard the results.
Since: array-0.5.8.0
forMArrayM_ :: (MArray a e m, Ix i) => a i e -> (e -> m b) -> m () Source
forMArrayM_ is mapMArrayM_ with its arguments flipped.
Since: array-0.5.8.0
A mutable array with unboxed elements, that can be manipulated in the ST monad. The type arguments are as follows:
-
s: the state variable argument for theSTtype -
i: the index type of the array (should be an instance ofIx) -
e: the element type of the array. Only certain element types are supported.
An STUArray will generally be more efficient (in terms of both time and space) than the equivalent boxed version (STArray) with the same element type. However, STUArray is strict in its elements - so don't use STUArray if you require the non-strictness that STArray provides.
Constructors
| STUArray !i !i !Int (MutableByteArray# s) |
Instances
unsafeNewArraySTUArray_ :: Ix i => (i, i) -> (Int# -> Int#) -> ST s (STUArray s i e) Source
bOOL_SCALE :: Int# -> Int# Source
wORD_SCALE :: Int# -> Int# Source
dOUBLE_SCALE :: Int# -> Int# Source
fLOAT_SCALE :: Int# -> Int# Source
safe_scale :: Int# -> Int# -> Int# Source
bOOL_INDEX :: Int# -> Int# Source
The index of the word which the given Bool array elements falls within.
bOOL_BIT :: Int# -> Word# Source
bOOL_NOT_BIT :: Int# -> Word# Source
freeze :: (Ix i, MArray a e m, IArray b e) => a i e -> m (b i e) Source
Converts a mutable array (any instance of MArray) to an immutable array (any instance of IArray) by taking a complete copy of it.
freezeSTUArray :: STUArray s i e -> ST s (UArray i e) Source
memcpy_freeze :: MutableByteArray# s -> MutableByteArray# s -> CSize -> IO (Ptr a) Source
unsafeFreeze :: (Ix i, MArray a e m, IArray b e) => a i e -> m (b i e) Source
Converts an mutable array into an immutable array. The implementation may either simply cast the array from one type to the other without copying the array, or it may take a full copy of the array.
Note that because the array is possibly not copied, any subsequent modifications made to the mutable version of the array may be shared with the immutable version. It is safe to use, therefore, if the mutable version is never modified after the freeze operation.
The non-copying implementation is supported between certain pairs of array types only; one constraint is that the array types must have identical representations. In GHC, The following pairs of array types have a non-copying O(1) implementation of unsafeFreeze. Because the optimised versions are enabled by specialisations, you will need to compile with optimisation (-O) to get them.
thaw :: (Ix i, IArray a e, MArray b e m) => a i e -> m (b i e) Source
Converts an immutable array (any instance of IArray) into a mutable array (any instance of MArray) by taking a complete copy of it.
thawSTUArray :: UArray i e -> ST s (STUArray s i e) Source
memcpy_thaw :: MutableByteArray# s -> ByteArray# -> CSize -> IO (Ptr a) Source
unsafeThaw :: (Ix i, IArray a e, MArray b e m) => a i e -> m (b i e) Source
Converts an immutable array into a mutable array. The implementation may either simply cast the array from one type to the other without copying the array, or it may take a full copy of the array.
Note that because the array is possibly not copied, any subsequent modifications made to the mutable version of the array may be shared with the immutable version. It is only safe to use, therefore, if the immutable array is never referenced again in this thread, and there is no possibility that it can be also referenced in another thread. If you use an unsafeThawwriteunsafeFreeze sequence in a multi-threaded setting, then you must ensure that this sequence is atomic with respect to other threads, or a garbage collector crash may result (because the write may be writing to a frozen array).
The non-copying implementation is supported between certain pairs of array types only; one constraint is that the array types must have identical representations. In GHC, The following pairs of array types have a non-copying O(1) implementation of unsafeThaw. Because the optimised versions are enabled by specialisations, you will need to compile with optimisation (-O) to get them.
unsafeThawSTUArray :: UArray i e -> ST s (STUArray s i e) Source
unsafeThawIOArray :: Array ix e -> IO (IOArray ix e) Source
thawIOArray :: Array ix e -> IO (IOArray ix e) Source
freezeIOArray :: IOArray ix e -> IO (Array ix e) Source
unsafeFreezeIOArray :: IOArray ix e -> IO (Array ix e) Source
castSTUArray :: STUArray s ix a -> ST s (STUArray s ix b) Source
Casts an STUArray with one element type into one with a different element type. All the elements of the resulting array are undefined (unless you know what you're doing...).
© The University of Glasgow and others
Licensed under a BSD-style license (see top of the page).
https://downloads.haskell.org/~ghc/9.12.1/docs/libraries/array-0.5.8.0-8d84/Data-Array-Base.html