\begin{code}
-{-# OPTIONS -fno-implicit-prelude #-}
+{-# OPTIONS_GHC -fno-implicit-prelude -fno-bang-patterns #-}
-----------------------------------------------------------------------------
-- |
-- Module : GHC.Arr
--
-----------------------------------------------------------------------------
+-- #hide
module GHC.Arr where
import {-# SOURCE #-} GHC.Err ( error )
%*********************************************************
\begin{code}
+-- | The 'Ix' class is used to map a contiguous subrange of values in
+-- a type onto integers. It is used primarily for array indexing
+-- (see "Data.Array", "Data.Array.IArray" and "Data.Array.MArray").
+--
+-- The first argument @(l,u)@ of each of these operations is a pair
+-- specifying the lower and upper bounds of a contiguous subrange of values.
+--
+-- An implementation is entitled to assume the following laws about these
+-- operations:
+--
+-- * @'inRange' (l,u) i == 'elem' i ('range' (l,u))@
+--
+-- * @'range' (l,u) '!!' 'index' (l,u) i == i@, when @'inRange' (l,u) i@
+--
+-- * @'map' ('index' (l,u)) ('range' (l,u))) == [0..'rangeSize' (l,u)-1]@
+--
+-- * @'rangeSize' (l,u) == 'length' ('range' (l,u))@
+--
+-- Minimal complete instance: 'range', 'index' and 'inRange'.
+--
class (Ord a) => Ix a where
+ -- | The list of values in the subrange defined by a bounding pair.
range :: (a,a) -> [a]
- index, unsafeIndex :: (a,a) -> a -> Int
+ -- | The position of a subscript in the subrange.
+ index :: (a,a) -> a -> Int
+ -- | Like 'index', but without checking that the value is in range.
+ unsafeIndex :: (a,a) -> a -> Int
+ -- | Returns 'True' the given subscript lies in the range defined
+ -- the bounding pair.
inRange :: (a,a) -> a -> Bool
+ -- | The size of the subrange defined by a bounding pair.
rangeSize :: (a,a) -> Int
+ -- | like 'rangeSize', but without checking that the upper bound is
+ -- in range.
unsafeRangeSize :: (a,a) -> Int
-- Must specify one of index, unsafeIndex
- index b i | inRange b i = unsafeIndex b i
+ index b i | inRange b i = unsafeIndex b i
| otherwise = error "Error in array index"
unsafeIndex b i = index b i
- -- As long as you don't override the default rangeSize,
- -- you can specify unsafeRangeSize as follows, to speed up
- -- some operations:
- --
- -- unsafeRangeSize b@(_l,h) = unsafeIndex b h + 1
- --
rangeSize b@(_l,h) | inRange b h = unsafeIndex b h + 1
- | otherwise = 0
- unsafeRangeSize b = rangeSize b
+ | otherwise = 0 -- This case is only here to
+ -- check for an empty range
+ -- NB: replacing (inRange b h) by (l <= h) fails for
+ -- tuples. E.g. (1,2) <= (2,1) but the range is empty
+
+ unsafeRangeSize b@(_l,h) = unsafeIndex b h + 1
\end{code}
Note that the following is NOT right
inRange (m,n) i = m <= i && i <= n
- unsafeRangeSize b@(_l,h) = unsafeIndex b h + 1
-
----------------------------------------------------------------------
instance Ix Int where
{-# INLINE range #-}
{-# INLINE inRange #-}
inRange (I# m,I# n) (I# i) = m <=# i && i <=# n
- unsafeRangeSize b@(_l,h) = unsafeIndex b h + 1
-
----------------------------------------------------------------------
instance Ix Integer where
{-# INLINE range #-}
inRange (m,n) i = m <= i && i <= n
- unsafeRangeSize b@(_l,h) = unsafeIndex b h + 1
-
----------------------------------------------------------------------
instance Ix Bool where -- as derived
{-# INLINE range #-}
inRange (l,u) i = fromEnum i >= fromEnum l && fromEnum i <= fromEnum u
- unsafeRangeSize b@(_l,h) = unsafeIndex b h + 1
-
----------------------------------------------------------------------
instance Ix Ordering where -- as derived
{-# INLINE range #-}
inRange (l,u) i = fromEnum i >= fromEnum l && fromEnum i <= fromEnum u
- unsafeRangeSize b@(_l,h) = unsafeIndex b h + 1
-
----------------------------------------------------------------------
instance Ix () where
{-# INLINE range #-}
{-# INLINE index #-}
index b i = unsafeIndex b i
- unsafeRangeSize b@(_l,h) = unsafeIndex b h + 1
-
----------------------------------------------------------------------
instance (Ix a, Ix b) => Ix (a, b) where -- as derived
{-# SPECIALISE instance Ix (Int,Int) #-}
inRange ((l1,l2),(u1,u2)) (i1,i2) =
inRange (l1,u1) i1 && inRange (l2,u2) i2
- unsafeRangeSize b@(_l,h) = unsafeIndex b h + 1
-
-- Default method for index
----------------------------------------------------------------------
inRange (l1,u1) i1 && inRange (l2,u2) i2 &&
inRange (l3,u3) i3
- unsafeRangeSize b@(_l,h) = unsafeIndex b h + 1
-
-- Default method for index
----------------------------------------------------------------------
inRange (l1,u1) i1 && inRange (l2,u2) i2 &&
inRange (l3,u3) i3 && inRange (l4,u4) i4
- unsafeRangeSize b@(_l,h) = unsafeIndex b h + 1
-
-- Default method for index
instance (Ix a1, Ix a2, Ix a3, Ix a4, Ix a5) => Ix (a1,a2,a3,a4,a5) where
inRange (l3,u3) i3 && inRange (l4,u4) i4 &&
inRange (l5,u5) i5
- unsafeRangeSize b@(_l,h) = unsafeIndex b h + 1
-
-- Default method for index
\end{code}
\begin{code}
type IPr = (Int, Int)
+-- | The type of immutable non-strict (boxed) arrays
+-- with indices in @i@ and elements in @e@.
data Ix i => Array i e = Array !i !i (Array# e)
-- | Mutable, boxed, non-strict arrays in the 'ST' monad. The type
arrEleBottom :: a
arrEleBottom = error "(Array.!): undefined array element"
--- | Note: GHC's implementation of @array@ differs slightly from the Haskell 98
--- report. If the same index appears twice, GHC's implementation takes the
--- value from last (index,value) pair in the list, rather than yielding bottom
--- for that array slot.
+-- | 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, 'array' is
+-- strict in the bounds argument and in the indices of the association
+-- list, but nonstrict in the values. Thus, 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 (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 'bounds' still yields the bounds
+-- with which the array was constructed.
{-# INLINE array #-}
-array :: Ix i => (i,i) -> [(i, e)] -> Array i e
+array :: Ix i
+ => (i,i) -- ^ a pair of /bounds/, each of the index type
+ -- of the array. These bounds are the lowest and
+ -- highest indices in the array, in that order.
+ -- 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))'.
+ -> [(i, e)] -- ^ a list of /associations/ of the form
+ -- (/index/, /value/). Typically, this list will
+ -- be expressed as a comprehension. An
+ -- association '(i, x)' defines the value of
+ -- the array at index 'i' to be 'x'.
+ -> Array i e
array (l,u) ies = unsafeArray (l,u) [(index (l,u) i, e) | (i, e) <- ies]
{-# INLINE unsafeArray #-}
-- transformation on the list of elements; I guess it's impossible
-- using mechanisms currently available.
+-- | Construct an array from a pair of bounds and a list of values in
+-- index order.
{-# INLINE listArray #-}
listArray :: Ix i => (i,i) -> [e] -> Array i e
listArray (l,u) es = runST (ST $ \s1# ->
case fillFromList 0# es s2# of { s3# ->
done l u marr# s3# }}})
+-- | The value at the given index in an array.
{-# INLINE (!) #-}
(!) :: Ix i => Array i e -> i -> e
arr@(Array l u _) ! i = unsafeAt arr (index (l,u) i)
unsafeAt (Array _ _ arr#) (I# i#) =
case indexArray# arr# i# of (# e #) -> e
+-- | The bounds with which an array was constructed.
{-# INLINE bounds #-}
bounds :: Ix i => Array i e -> (i,i)
bounds (Array l u _) = (l,u)
+-- | The list of indices of an array in ascending order.
{-# INLINE indices #-}
indices :: Ix i => Array i e -> [i]
indices (Array l u _) = range (l,u)
+-- | The list of elements of an array in index order.
{-# INLINE elems #-}
elems :: Ix i => Array i e -> [e]
elems arr@(Array l u _) =
[unsafeAt arr i | i <- [0 .. rangeSize (l,u) - 1]]
+-- | The list of associations of an array in index order.
{-# INLINE assocs #-}
assocs :: Ix i => Array i e -> [(i, e)]
assocs arr@(Array l u _) =
[(i, unsafeAt arr (unsafeIndex (l,u) i)) | i <- range (l,u)]
+-- | The 'accumArray' deals with repeated indices in the association
+-- list using an /accumulating function/ which combines the values of
+-- associations 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]
+--
+-- If the accumulating function is strict, then 'accumArray' is strict in
+-- the values, as well as the indices, in the association list. Thus,
+-- unlike ordinary arrays built with 'array', accumulated arrays should
+-- not in general be recursive.
{-# INLINE accumArray #-}
-accumArray :: Ix i => (e -> a -> e) -> e -> (i,i) -> [(i, a)] -> Array i e
+accumArray :: Ix i
+ => (e -> a -> e) -- ^ accumulating function
+ -> e -- ^ initial value
+ -> (i,i) -- ^ bounds of the array
+ -> [(i, a)] -- ^ association list
+ -> Array i e
accumArray f init (l,u) ies =
unsafeAccumArray f init (l,u) [(index (l,u) i, e) | (i, e) <- ies]
case writeArray# marr# i# (f old new) s2# of { s3# ->
next s3# }}
+-- | Constructs an array identical to the first 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.
+--
+-- Repeated indices in the association list are handled as for 'array':
+-- Haskell 98 specifies that the resulting array is undefined (i.e. bottom),
+-- but GHC's implementation uses the last association for each index.
{-# INLINE (//) #-}
(//) :: Ix i => Array i e -> [(i, e)] -> Array i e
arr@(Array l u _) // ies =
STArray _ _ marr# <- thawSTArray arr
ST (foldr (fill marr#) (done l u marr#) ies))
+-- | @'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])
+--
{-# INLINE accum #-}
accum :: Ix i => (e -> a -> e) -> Array i e -> [(i, a)] -> Array i e
accum f arr@(Array l u _) ies =
amap f arr@(Array l u _) =
unsafeArray (l,u) [(i, f (unsafeAt arr i)) | i <- [0 .. rangeSize (l,u) - 1]]
+-- | 'ixmap' 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 'fmap'
+-- from the 'Array' instance of the 'Functor' class.
{-# INLINE ixmap #-}
ixmap :: (Ix i, Ix j) => (i,i) -> (i -> j) -> Array j e -> Array i e
ixmap (l,u) f arr =
projects / haskell-directory.git / blobdiff