-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/
-- | Mutable and immutable arrays
--
-- This package defines the classes <tt>IArray</tt> of immutable arrays
-- and <tt>MArray</tt> of arrays mutable within appropriate monads, as
-- well as some instances of these classes.
@package array
@version 0.4.0.0
-- | An overloaded interface to mutable arrays. For array types which can
-- be used with this interface, see <a>Data.Array.IO</a>,
-- <a>Data.Array.ST</a>, and <a>Data.Array.Storable</a>.
module Data.Array.MArray
-- | Class of mutable array types.
--
-- An array type has the form <tt>(a i e)</tt> where <tt>a</tt> is the
-- array type constructor (kind <tt>* -> * -> *</tt>), <tt>i</tt>
-- is the index type (a member of the class <a>Ix</a>), and <tt>e</tt> is
-- the element type.
--
-- The <tt>MArray</tt> class is parameterised over both <tt>a</tt> and
-- <tt>e</tt> (so that instances specialised to certain element types can
-- be defined, in the same way as for <a>IArray</a>), and also over the
-- type of the monad, <tt>m</tt>, in which the mutable array will be
-- manipulated.
class Monad m => MArray a e m where newArray (l, u) initialValue = do { let n = safeRangeSize (l, u); marr <- unsafeNewArray_ (l, u); sequence_ [unsafeWrite marr i initialValue | i <- [0 .. n - 1]]; return marr } unsafeNewArray_ (l, u) = newArray (l, u) arrEleBottom newArray_ (l, u) = newArray (l, u) arrEleBottom
getBounds :: (MArray a e m, Ix i) => a i e -> m (i, i)
newArray :: (MArray a e m, Ix i) => (i, i) -> e -> m (a i e)
newArray_ :: (MArray a e m, Ix i) => (i, i) -> m (a i e)
-- | 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.
newListArray :: (MArray a e m, Ix i) => (i, i) -> [e] -> m (a i e)
-- | Read an element from a mutable array
readArray :: (MArray a e m, Ix i) => a i e -> i -> m e
-- | Write an element in a mutable array
writeArray :: (MArray a e m, Ix i) => a i e -> i -> e -> m ()
-- | Constructs a new array derived from the original array by applying a
-- function to each of the elements.
mapArray :: (MArray a e' m, MArray a e m, Ix i) => (e' -> e) -> a i e' -> m (a i e)
-- | Constructs a new array derived from the original array by applying a
-- function to each of the indices.
mapIndices :: (MArray a e m, Ix i, Ix j) => (i, i) -> (i -> j) -> a j e -> m (a i e)
-- | Return a list of all the elements of a mutable array
getElems :: (MArray a e m, Ix i) => a i e -> m [e]
-- | Return a list of all the associations of a mutable array, in index
-- order.
getAssocs :: (MArray a e m, Ix i) => a i e -> m [(i, e)]
-- | Converts a mutable array (any instance of <a>MArray</a>) to an
-- immutable array (any instance of <a>IArray</a>) by taking a complete
-- copy of it.
freeze :: (Ix i, MArray a e m, IArray b e) => a i e -> m (b i e)
-- | 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 <a>unsafeFreeze</a>. Because
-- the optimised versions are enabled by specialisations, you will need
-- to compile with optimisation (-O) to get them.
--
-- <ul>
-- <li><a>IOUArray</a> -> <a>UArray</a></li>
-- <li><a>STUArray</a> -> <a>UArray</a></li>
-- <li><a>IOArray</a> -> <a>Array</a></li>
-- <li><a>STArray</a> -> <a>Array</a></li>
-- </ul>
-- | <i>Deprecated: Please import from Data.Array.Unsafe instead; This will
-- be removed in the next release</i>
unsafeFreeze :: (Ix i, MArray a e m, IArray b e) => a i e -> m (b i e)
-- | Converts an immutable array (any instance of <a>IArray</a>) into a
-- mutable array (any instance of <a>MArray</a>) by taking a complete
-- copy of it.
thaw :: (Ix i, IArray a e, MArray b e m) => a i e -> m (b i e)
-- | 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 unsafeThaw<i>write</i>unsafeFreeze 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 <a>unsafeThaw</a>. Because
-- the optimised versions are enabled by specialisations, you will need
-- to compile with optimisation (-O) to get them.
--
-- <ul>
-- <li><a>UArray</a> -> <a>IOUArray</a></li>
-- <li><a>UArray</a> -> <a>STUArray</a></li>
-- <li><a>Array</a> -> <a>IOArray</a></li>
-- <li><a>Array</a> -> <a>STArray</a></li>
-- </ul>
-- | <i>Deprecated: Please import from Data.Array.Unsafe instead; This will
-- be removed in the next release</i>
unsafeThaw :: (Ix i, IArray a e, MArray b e m) => a i e -> m (b i e)
-- | An overloaded interface to mutable arrays. For array types which can
-- be used with this interface, see <a>Data.Array.IO</a>,
-- <a>Data.Array.ST</a>, and <a>Data.Array.Storable</a>. . Safe API only
-- of <a>Data.Array.MArray</a>.
module Data.Array.MArray.Safe
-- | Class of mutable array types.
--
-- An array type has the form <tt>(a i e)</tt> where <tt>a</tt> is the
-- array type constructor (kind <tt>* -> * -> *</tt>), <tt>i</tt>
-- is the index type (a member of the class <a>Ix</a>), and <tt>e</tt> is
-- the element type.
--
-- The <tt>MArray</tt> class is parameterised over both <tt>a</tt> and
-- <tt>e</tt> (so that instances specialised to certain element types can
-- be defined, in the same way as for <a>IArray</a>), and also over the
-- type of the monad, <tt>m</tt>, in which the mutable array will be
-- manipulated.
class Monad m => MArray a e m where newArray (l, u) initialValue = do { let n = safeRangeSize (l, u); marr <- unsafeNewArray_ (l, u); sequence_ [unsafeWrite marr i initialValue | i <- [0 .. n - 1]]; return marr } unsafeNewArray_ (l, u) = newArray (l, u) arrEleBottom newArray_ (l, u) = newArray (l, u) arrEleBottom
getBounds :: (MArray a e m, Ix i) => a i e -> m (i, i)
newArray :: (MArray a e m, Ix i) => (i, i) -> e -> m (a i e)
newArray_ :: (MArray a e m, Ix i) => (i, i) -> m (a i e)
-- | 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.
newListArray :: (MArray a e m, Ix i) => (i, i) -> [e] -> m (a i e)
-- | Read an element from a mutable array
readArray :: (MArray a e m, Ix i) => a i e -> i -> m e
-- | Write an element in a mutable array
writeArray :: (MArray a e m, Ix i) => a i e -> i -> e -> m ()
-- | Constructs a new array derived from the original array by applying a
-- function to each of the elements.
mapArray :: (MArray a e' m, MArray a e m, Ix i) => (e' -> e) -> a i e' -> m (a i e)
-- | Constructs a new array derived from the original array by applying a
-- function to each of the indices.
mapIndices :: (MArray a e m, Ix i, Ix j) => (i, i) -> (i -> j) -> a j e -> m (a i e)
-- | Return a list of all the elements of a mutable array
getElems :: (MArray a e m, Ix i) => a i e -> m [e]
-- | Return a list of all the associations of a mutable array, in index
-- order.
getAssocs :: (MArray a e m, Ix i) => a i e -> m [(i, e)]
-- | Converts a mutable array (any instance of <a>MArray</a>) to an
-- immutable array (any instance of <a>IArray</a>) by taking a complete
-- copy of it.
freeze :: (Ix i, MArray a e m, IArray b e) => a i e -> m (b i e)
-- | Converts an immutable array (any instance of <a>IArray</a>) into a
-- mutable array (any instance of <a>MArray</a>) by taking a complete
-- copy of it.
thaw :: (Ix i, IArray a e, MArray b e m) => a i e -> m (b i e)
-- | Contains the various unsafe operations that can be performed on
-- arrays.
module Data.Array.Unsafe
-- | Casts an <a>STUArray</a> 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...).
castSTUArray :: STUArray s ix a -> ST s (STUArray s ix b)
-- | Casts an <a>IOUArray</a> 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...).
castIOUArray :: IOUArray ix a -> IO (IOUArray ix b)
-- | 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 <a>unsafeFreeze</a>. Because
-- the optimised versions are enabled by specialisations, you will need
-- to compile with optimisation (-O) to get them.
--
-- <ul>
-- <li><a>IOUArray</a> -> <a>UArray</a></li>
-- <li><a>STUArray</a> -> <a>UArray</a></li>
-- <li><a>IOArray</a> -> <a>Array</a></li>
-- <li><a>STArray</a> -> <a>Array</a></li>
-- </ul>
unsafeFreeze :: (Ix i, MArray a e m, IArray b e) => a i e -> m (b i e)
-- | 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 unsafeThaw<i>write</i>unsafeFreeze 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 <a>unsafeThaw</a>. Because
-- the optimised versions are enabled by specialisations, you will need
-- to compile with optimisation (-O) to get them.
--
-- <ul>
-- <li><a>UArray</a> -> <a>IOUArray</a></li>
-- <li><a>UArray</a> -> <a>STUArray</a></li>
-- <li><a>Array</a> -> <a>IOArray</a></li>
-- <li><a>Array</a> -> <a>STArray</a></li>
-- </ul>
unsafeThaw :: (Ix i, IArray a e, MArray b e m) => a i e -> m (b i e)
-- | Construct a <a>StorableArray</a> from an arbitrary <a>ForeignPtr</a>.
-- It is the caller's responsibility to ensure that the <a>ForeignPtr</a>
-- points to an area of memory sufficient for the specified bounds.
unsafeForeignPtrToStorableArray :: Ix i => ForeignPtr e -> (i, i) -> IO (StorableArray i e)
-- | Mutable boxed and unboxed arrays in the IO monad.
module Data.Array.IO
-- | An <a>IOArray</a> is a mutable, boxed, non-strict array in the
-- <a>IO</a> monad. The type arguments are as follows:
--
-- <ul>
-- <li><tt>i</tt>: the index type of the array (should be an instance of
-- <a>Ix</a>)</li>
-- <li><tt>e</tt>: the element type of the array.</li>
-- </ul>
data IOArray i e :: * -> * -> *
-- | Mutable, unboxed, strict arrays in the <a>IO</a> monad. The type
-- arguments are as follows:
--
-- <ul>
-- <li><tt>i</tt>: the index type of the array (should be an instance of
-- <a>Ix</a>)</li>
-- <li><tt>e</tt>: the element type of the array. Only certain element
-- types are supported: see <a>Data.Array.MArray</a> for a list of
-- instances.</li>
-- </ul>
data IOUArray i e
-- | Casts an <a>IOUArray</a> 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...).
-- | <i>Deprecated: Please import from Data.Array.Unsafe instead; This will
-- be removed in the next release</i>
castIOUArray :: IOUArray i a -> IO (IOUArray i b)
-- | Reads a number of <a>Word8</a>s from the specified <a>Handle</a>
-- directly into an array.
hGetArray :: Handle -> IOUArray Int Word8 -> Int -> IO Int
-- | Writes an array of <a>Word8</a> to the specified <a>Handle</a>.
hPutArray :: Handle -> IOUArray Int Word8 -> Int -> IO ()
-- | Mutable boxed and unboxed arrays in the IO monad. . Safe API only of
-- <a>Data.Array.IO</a>.
module Data.Array.IO.Safe
-- | An <a>IOArray</a> is a mutable, boxed, non-strict array in the
-- <a>IO</a> monad. The type arguments are as follows:
--
-- <ul>
-- <li><tt>i</tt>: the index type of the array (should be an instance of
-- <a>Ix</a>)</li>
-- <li><tt>e</tt>: the element type of the array.</li>
-- </ul>
data IOArray i e :: * -> * -> *
-- | Mutable, unboxed, strict arrays in the <a>IO</a> monad. The type
-- arguments are as follows:
--
-- <ul>
-- <li><tt>i</tt>: the index type of the array (should be an instance of
-- <a>Ix</a>)</li>
-- <li><tt>e</tt>: the element type of the array. Only certain element
-- types are supported: see <a>Data.Array.MArray</a> for a list of
-- instances.</li>
-- </ul>
data IOUArray i e
-- | Reads a number of <a>Word8</a>s from the specified <a>Handle</a>
-- directly into an array.
hGetArray :: Handle -> IOUArray Int Word8 -> Int -> IO Int
-- | Writes an array of <a>Word8</a> to the specified <a>Handle</a>.
hPutArray :: Handle -> IOUArray Int Word8 -> Int -> IO ()
-- | Mutable boxed and unboxed arrays in the <a>ST</a> monad.
module Data.Array.ST
-- | Mutable, boxed, non-strict arrays in the <a>ST</a> monad. The type
-- arguments are as follows:
--
-- <ul>
-- <li><tt>s</tt>: the state variable argument for the <a>ST</a>
-- type</li>
-- <li><tt>i</tt>: the index type of the array (should be an instance of
-- <a>Ix</a>)</li>
-- <li><tt>e</tt>: the element type of the array.</li>
-- </ul>
data STArray s i e :: * -> * -> * -> *
-- | A safe way to create and work with a mutable array before returning an
-- immutable array for later perusal. This function avoids copying the
-- array before returning it - it uses <a>unsafeFreeze</a> internally,
-- but this wrapper is a safe interface to that function.
runSTArray :: Ix i => (forall s. ST s (STArray s i e)) -> Array i e
-- | A mutable array with unboxed elements, that can be manipulated in the
-- <a>ST</a> monad. The type arguments are as follows:
--
-- <ul>
-- <li><tt>s</tt>: the state variable argument for the <a>ST</a>
-- type</li>
-- <li><tt>i</tt>: the index type of the array (should be an instance of
-- <tt>Ix</tt>)</li>
-- <li><tt>e</tt>: the element type of the array. Only certain element
-- types are supported.</li>
-- </ul>
--
-- An <a>STUArray</a> will generally be more efficient (in terms of both
-- time and space) than the equivalent boxed version (<a>STArray</a>)
-- with the same element type. However, <a>STUArray</a> is strict in its
-- elements - so don't use <a>STUArray</a> if you require the
-- non-strictness that <a>STArray</a> provides.
data STUArray s i e
-- | A safe way to create and work with an unboxed mutable array before
-- returning an immutable array for later perusal. This function avoids
-- copying the array before returning it - it uses <a>unsafeFreeze</a>
-- internally, but this wrapper is a safe interface to that function.
runSTUArray :: Ix i => (forall s. ST s (STUArray s i e)) -> UArray i e
-- | Casts an <a>STUArray</a> 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...).
-- | <i>Deprecated: Please import from Data.Array.Unsafe instead; This will
-- be removed in the next release</i>
castSTUArray :: STUArray s ix a -> ST s (STUArray s ix b)
-- | Mutable boxed and unboxed arrays in the <a>ST</a> monad.
--
-- Safe API only of <a>Data.Array.ST</a>.
module Data.Array.ST.Safe
-- | Mutable, boxed, non-strict arrays in the <a>ST</a> monad. The type
-- arguments are as follows:
--
-- <ul>
-- <li><tt>s</tt>: the state variable argument for the <a>ST</a>
-- type</li>
-- <li><tt>i</tt>: the index type of the array (should be an instance of
-- <a>Ix</a>)</li>
-- <li><tt>e</tt>: the element type of the array.</li>
-- </ul>
data STArray s i e :: * -> * -> * -> *
-- | A safe way to create and work with a mutable array before returning an
-- immutable array for later perusal. This function avoids copying the
-- array before returning it - it uses <a>unsafeFreeze</a> internally,
-- but this wrapper is a safe interface to that function.
runSTArray :: Ix i => (forall s. ST s (STArray s i e)) -> Array i e
-- | A mutable array with unboxed elements, that can be manipulated in the
-- <a>ST</a> monad. The type arguments are as follows:
--
-- <ul>
-- <li><tt>s</tt>: the state variable argument for the <a>ST</a>
-- type</li>
-- <li><tt>i</tt>: the index type of the array (should be an instance of
-- <tt>Ix</tt>)</li>
-- <li><tt>e</tt>: the element type of the array. Only certain element
-- types are supported.</li>
-- </ul>
--
-- An <a>STUArray</a> will generally be more efficient (in terms of both
-- time and space) than the equivalent boxed version (<a>STArray</a>)
-- with the same element type. However, <a>STUArray</a> is strict in its
-- elements - so don't use <a>STUArray</a> if you require the
-- non-strictness that <a>STArray</a> provides.
data STUArray s i e
-- | A safe way to create and work with an unboxed mutable array before
-- returning an immutable array for later perusal. This function avoids
-- copying the array before returning it - it uses <a>unsafeFreeze</a>
-- internally, but this wrapper is a safe interface to that function.
runSTUArray :: Ix i => (forall s. ST s (STUArray s i e)) -> UArray i e
-- | A storable array is an IO-mutable array which stores its contents in a
-- contiguous memory block living in the C heap. Elements are stored
-- according to the class <a>Storable</a>. You can obtain the pointer to
-- the array contents to manipulate elements from languages like C.
--
-- It is similar to <a>IOUArray</a> but slower. Its advantage is that
-- it's compatible with C.
module Data.Array.Storable
-- | The array type
data StorableArray i e
-- | The pointer to the array contents is obtained by
-- <a>withStorableArray</a>. The idea is similar to <a>ForeignPtr</a>
-- (used internally here). The pointer should be used only during
-- execution of the <a>IO</a> action retured by the function passed as
-- argument to <a>withStorableArray</a>.
withStorableArray :: StorableArray i e -> (Ptr e -> IO a) -> IO a
-- | If you want to use it afterwards, ensure that you
-- <a>touchStorableArray</a> after the last use of the pointer, so the
-- array is not freed too early.
touchStorableArray :: StorableArray i e -> IO ()
-- | Construct a <a>StorableArray</a> from an arbitrary <a>ForeignPtr</a>.
-- It is the caller's responsibility to ensure that the <a>ForeignPtr</a>
-- points to an area of memory sufficient for the specified bounds.
-- | <i>Deprecated: Please import from Data.Array.Unsafe instead; This will
-- be removed in the next release</i>
unsafeForeignPtrToStorableArray :: Ix i => ForeignPtr e -> (i, i) -> IO (StorableArray i e)
-- | A storable array is an IO-mutable array which stores its contents in a
-- contiguous memory block living in the C heap. Elements are stored
-- according to the class <tt>Storable</tt>. You can obtain the pointer
-- to the array contents to manipulate elements from languages like C.
--
-- It is similar to <a>IOUArray</a> but slower. Its advantage is that
-- it's compatible with C.
--
-- Safe API only of <a>Data.Array.Storable</a>.
module Data.Array.Storable.Safe
-- | The array type
data StorableArray i e
-- | The pointer to the array contents is obtained by
-- <a>withStorableArray</a>. The idea is similar to <a>ForeignPtr</a>
-- (used internally here). The pointer should be used only during
-- execution of the <a>IO</a> action retured by the function passed as
-- argument to <a>withStorableArray</a>.
withStorableArray :: StorableArray i e -> (Ptr e -> IO a) -> IO a
-- | If you want to use it afterwards, ensure that you
-- <a>touchStorableArray</a> after the last use of the pointer, so the
-- array is not freed too early.
touchStorableArray :: StorableArray i e -> IO ()
-- | Basic non-strict arrays.
--
-- <i>Note:</i> The <a>Data.Array.IArray</a> module provides a more
-- general interface to immutable arrays: it defines operations with the
-- same names as those defined below, but with more general types, and
-- also defines <a>Array</a> instances of the relevant classes. To use
-- that more general interface, import <a>Data.Array.IArray</a> but not
-- <a>Data.Array</a>.
module Data.Array
-- | The type of immutable non-strict (boxed) arrays with indices in
-- <tt>i</tt> and elements in <tt>e</tt>.
data Array i e :: * -> * -> *
-- | Construct an array with the specified bounds and containing values for
-- given indices within these bounds.
--
-- The array is undefined (i.e. bottom) if any index in the list is out
-- of bounds. The Haskell 98 Report further specifies that if any two
-- associations in the list have the same index, the value at that index
-- is undefined (i.e. bottom). However in GHC's implementation, the value
-- at such an index is the value part of the last association with that
-- index in the list.
--
-- Because the indices must be checked for these errors, <a>array</a> is
-- strict in the bounds argument and in the indices of the association
-- list, but non-strict in the values. Thus, recurrences such as the
-- following are possible:
--
-- <pre>
-- a = array (1,100) ((1,1) : [(i, i * a!(i-1)) | i <- [2..100]])
-- </pre>
--
-- 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 (i.e. bottom).
--
-- 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 <a>bounds</a> still yields the bounds
-- with which the array was constructed.
array :: Ix i => (i, i) -> [(i, e)] -> Array i e
-- | Construct an array from a pair of bounds and a list of values in index
-- order.
listArray :: Ix i => (i, i) -> [e] -> Array i e
-- | The <a>accumArray</a> function deals with repeated indices in the
-- association list using an <i>accumulating function</i> which combines
-- the values of associations with the same index. For example, given a
-- list of values of some index type, <tt>hist</tt> produces a histogram
-- of the number of occurrences of each index within a specified range:
--
-- <pre>
-- hist :: (Ix a, Num b) => (a,a) -> [a] -> Array a b
-- hist bnds is = accumArray (+) 0 bnds [(i, 1) | i<-is, inRange bnds i]
-- </pre>
--
-- If the accumulating function is strict, then <a>accumArray</a> is
-- strict in the values, as well as the indices, in the association list.
-- Thus, unlike ordinary arrays built with <a>array</a>, accumulated
-- arrays should not in general be recursive.
accumArray :: Ix i => (e -> a -> e) -> e -> (i, i) -> [(i, a)] -> Array i e
-- | The value at the given index in an array.
(!) :: Ix i => Array i e -> i -> e
-- | The bounds with which an array was constructed.
bounds :: Ix i => Array i e -> (i, i)
-- | The list of indices of an array in ascending order.
indices :: Ix i => Array i e -> [i]
-- | The list of elements of an array in index order.
elems :: Ix i => Array i e -> [e]
-- | The list of associations of an array in index order.
assocs :: Ix i => Array i e -> [(i, e)]
-- | Constructs an array identical to the first argument except that it has
-- been updated by the associations in the right argument. For example,
-- if <tt>m</tt> is a 1-origin, <tt>n</tt> by <tt>n</tt> matrix, then
--
-- <pre>
-- m//[((i,i), 0) | i <- [1..n]]
-- </pre>
--
-- is the same matrix, except with the diagonal zeroed.
--
-- Repeated indices in the association list are handled as for
-- <a>array</a>: Haskell 98 specifies that the resulting array is
-- undefined (i.e. bottom), but GHC's implementation uses the last
-- association for each index.
(//) :: Ix i => Array i e -> [(i, e)] -> Array i e
-- | <tt><a>accum</a> f</tt> takes an array and an association list and
-- accumulates pairs from the list into the array with the accumulating
-- function <tt>f</tt>. Thus <a>accumArray</a> can be defined using
-- <a>accum</a>:
--
-- <pre>
-- accumArray f z b = accum f (array b [(i, z) | i <- range b])
-- </pre>
accum :: Ix i => (e -> a -> e) -> Array i e -> [(i, a)] -> Array i e
-- | <a>ixmap</a> allows for transformations on array indices. It may be
-- thought of as providing function composition on the right with the
-- mapping that the original array embodies.
--
-- A similar transformation of array values may be achieved using
-- <a>fmap</a> from the <a>Array</a> instance of the <a>Functor</a>
-- class.
ixmap :: (Ix i, Ix j) => (i, i) -> (i -> j) -> Array j e -> Array i e
-- | Immutable arrays, with an overloaded interface. For array types which
-- can be used with this interface, see the <a>Array</a> type exported by
-- this module and the <a>Data.Array.Unboxed</a> module. Other packages,
-- such as diffarray, also provide arrays using this interface.
module Data.Array.IArray
-- | Class of immutable array types.
--
-- An array type has the form <tt>(a i e)</tt> where <tt>a</tt> is the
-- array type constructor (kind <tt>* -> * -> *</tt>), <tt>i</tt>
-- is the index type (a member of the class <a>Ix</a>), and <tt>e</tt> is
-- the element type. The <tt>IArray</tt> class is parameterised over both
-- <tt>a</tt> and <tt>e</tt>, so that instances specialised to certain
-- element types can be defined.
class IArray a e where unsafeReplace arr ies = runST (unsafeReplaceST arr ies >>= unsafeFreeze) unsafeAccum f arr ies = runST (unsafeAccumST f arr ies >>= unsafeFreeze) unsafeAccumArray f e lu ies = runST (unsafeAccumArrayST f e lu ies >>= unsafeFreeze)
bounds :: (IArray a e, Ix i) => a i e -> (i, i)
-- | The type of immutable non-strict (boxed) arrays with indices in
-- <tt>i</tt> and elements in <tt>e</tt>.
data Array 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 <tt>(i,x)</tt>, which defines the
-- value of the array at index <tt>i</tt> to be <tt>x</tt>. 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 <tt>Array</tt> the
-- value at such indices is bottom.)
--
-- Because the indices must be checked for these errors, <a>array</a> is
-- strict in the bounds argument and in the indices of the association
-- list. Whether <tt>array</tt> is strict or non-strict in the elements
-- depends on the array type: <a>Array</a> is a non-strict array type,
-- but all of the <a>UArray</a> arrays are strict. Thus in a non-strict
-- array, recurrences such as the following are possible:
--
-- <pre>
-- a = array (1,100) ((1,1) : [(i, i * a!(i-1)) | i \<- [2..100]])
-- </pre>
--
-- 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 <a>bounds</a> still yields the bounds
-- with which the array was constructed.
array :: (IArray a e, Ix i) => (i, i) -> [(i, e)] -> a i e
-- | 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.
listArray :: (IArray a e, Ix i) => (i, i) -> [e] -> a i e
-- | Constructs an immutable array from a list of associations. Unlike
-- <a>array</a>, the same index is allowed to occur multiple times in the
-- list of associations; an <i>accumulating function</i> 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:
--
-- <pre>
-- hist :: (Ix a, Num b) => (a,a) -> [a] -> Array a b
-- hist bnds is = accumArray (+) 0 bnds [(i, 1) | i\<-is, inRange bnds i]
-- </pre>
accumArray :: (IArray a e, Ix i) => (e -> e' -> e) -> e -> (i, i) -> [(i, e')] -> a i e
-- | Returns the element of an immutable array at the specified index.
(!) :: (IArray a e, Ix i) => a i e -> i -> e
-- | Returns a list of all the valid indices in an array.
indices :: (IArray a e, Ix i) => a i e -> [i]
-- | Returns a list of all the elements of an array, in the same order as
-- their indices.
elems :: (IArray a e, Ix i) => a i e -> [e]
-- | Returns the contents of an array as a list of associations.
assocs :: (IArray a e, Ix i) => a i e -> [(i, e)]
-- | 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 <tt>m//[((i,i), 0) | i <- [1..n]]</tt> is the same matrix,
-- except with the diagonal zeroed.
--
-- As with the <a>array</a> 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 <tt>Array</tt> the value at
-- such indices is bottom.)
--
-- For most array types, this operation is O(<i>n</i>) where <i>n</i> 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.
(//) :: (IArray a e, Ix i) => a i e -> [(i, e)] -> a i e
-- | <tt>accum f</tt> takes an array and an association list and
-- accumulates pairs from the list into the array with the accumulating
-- function <tt>f</tt>. Thus <a>accumArray</a> can be defined using
-- <a>accum</a>:
--
-- <pre>
-- accumArray f z b = accum f (array b [(i, z) | i \<- range b])
-- </pre>
accum :: (IArray a e, Ix i) => (e -> e' -> e) -> a i e -> [(i, e')] -> a i e
-- | Returns a new array derived from the original array by applying a
-- function to each of the elements.
amap :: (IArray a e', IArray a e, Ix i) => (e' -> e) -> a i e' -> a i e
-- | Returns a new array derived from the original array by applying a
-- function to each of the indices.
ixmap :: (IArray a e, Ix i, Ix j) => (i, i) -> (i -> j) -> a j e -> a i e
-- | Unboxed immutable arrays.
module Data.Array.Unboxed
-- | Arrays with unboxed elements. Instances of <a>IArray</a> are provided
-- for <a>UArray</a> with certain element types (<a>Int</a>,
-- <a>Float</a>, <a>Char</a>, etc.; see the <a>UArray</a> class for a
-- full list).
--
-- A <a>UArray</a> will generally be more efficient (in terms of both
-- time and space) than the equivalent <a>Array</a> with the same element
-- type. However, <a>UArray</a> is strict in its elements - so don't use
-- <a>UArray</a> if you require the non-strictness that <a>Array</a>
-- provides.
--
-- Because the <tt>IArray</tt> 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 <tt>Array</tt> to
-- <tt>UArray</tt> to get the benefits of unboxed arrays (don't forget to
-- import <a>Data.Array.Unboxed</a> instead of <a>Data.Array</a>).
data UArray i e
distrib
>
Mageia
>
5
>
i586
>
media
>
core-release
>
by-pkgid
>
6e204a966e8c42d976f99a1700ce5f20
>
files
>
2188
