X-Git-Url: http://git.megacz.com/?a=blobdiff_plain;f=GHC%2FArr.lhs;h=b376c2fc1db0aaf415e3e62edd39e6127f75ba54;hb=696a935b0818ab9cf1a4fbd93faf9add88ead1cd;hp=940b60334f090f5124218d69823a6c2517870ad9;hpb=7f1f4e7a695c402ddd3a1dc2cc7114e649a78ebc;p=ghc-base.git diff --git a/GHC/Arr.lhs b/GHC/Arr.lhs index 940b603..b376c2f 100644 --- a/GHC/Arr.lhs +++ b/GHC/Arr.lhs @@ -1,18 +1,18 @@ -% ----------------------------------------------------------------------------- -% $Id: Arr.lhs,v 1.1 2001/06/28 14:15:03 simonmar Exp $ -% -% (c) The University of Glasgow, 1994-2000 -% - -\section[GHC.Arr]{Module @GHC.Arr@} - -Array implementation, @GHC.Arr@ exports the basic array -types and operations. - -For byte-arrays see @GHC.ByteArr@. - \begin{code} -{-# OPTIONS -fno-implicit-prelude #-} +{-# OPTIONS_GHC -fno-implicit-prelude #-} +----------------------------------------------------------------------------- +-- | +-- Module : GHC.Arr +-- Copyright : (c) The University of Glasgow, 1994-2000 +-- License : see libraries/base/LICENSE +-- +-- Maintainer : cvs-ghc@haskell.org +-- Stability : internal +-- Portability : non-portable (GHC extensions) +-- +-- GHC\'s array implementation. +-- +----------------------------------------------------------------------------- module GHC.Arr where @@ -37,17 +37,67 @@ default () %********************************************************* \begin{code} -class (Ord a) => Ix a where +-- | 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. + -- + -- 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 + -- + unsafeRangeSize :: (a,a) -> Int -- Must specify one of index, unsafeIndex index b i | inRange b i = unsafeIndex b i | otherwise = error "Error in array index" unsafeIndex b i = index b i + + rangeSize b@(_l,h) | inRange b h = unsafeIndex b h + 1 + | otherwise = 0 + unsafeRangeSize b = rangeSize b \end{code} +Note that the following is NOT right + rangeSize (l,h) | l <= h = index b h + 1 + | otherwise = 0 + +Because it might be the case that l= fromEnum l && fromEnum i <= fromEnum u + unsafeRangeSize b@(_l,h) = unsafeIndex b h + 1 + ---------------------------------------------------------------------- instance Ix Ordering where -- as derived {-# INLINE range #-} @@ -136,6 +193,8 @@ instance Ix Ordering where -- as derived 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 #-} @@ -147,6 +206,7 @@ instance Ix () where {-# 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 @@ -164,6 +224,8 @@ instance (Ix a, Ix b) => Ix (a, b) where -- as derived 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 ---------------------------------------------------------------------- @@ -184,6 +246,8 @@ instance (Ix a1, Ix a2, Ix a3) => Ix (a1,a2,a3) where inRange (l1,u1) i1 && inRange (l2,u2) i2 && inRange (l3,u3) i3 + unsafeRangeSize b@(_l,h) = unsafeIndex b h + 1 + -- Default method for index ---------------------------------------------------------------------- @@ -204,6 +268,8 @@ instance (Ix a1, Ix a2, Ix a3, Ix a4) => Ix (a1,a2,a3,a4) where 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 @@ -226,40 +292,9 @@ 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 - -- Default method for index -\end{code} - + unsafeRangeSize b@(_l,h) = unsafeIndex b h + 1 -%******************************************************** -%* * -\subsection{Size of @Ix@ interval} -%* * -%******************************************************** - -The @rangeSize@ operator returns the number of elements -in the range for an @Ix@ pair. - -\begin{code} -{-# SPECIALISE unsafeRangeSize :: (Int,Int) -> Int #-} -{-# SPECIALISE unsafeRangeSize :: ((Int,Int),(Int,Int)) -> Int #-} -unsafeRangeSize :: (Ix a) => (a,a) -> Int -unsafeRangeSize b@(_l,h) = unsafeIndex b h + 1 - -{-# SPECIALISE rangeSize :: (Int,Int) -> Int #-} -{-# SPECIALISE rangeSize :: ((Int,Int),(Int,Int)) -> Int #-} -rangeSize :: (Ix a) => (a,a) -> Int -rangeSize b@(_l,h) | inRange b h = unsafeIndex b h + 1 - | otherwise = 0 - --- Note that the following is NOT right --- rangeSize (l,h) | l <= h = index b h + 1 --- | otherwise = 0 --- --- Because it might be the case that l Array i e = Array !i !i (Array# e) -data Ix i => STArray s i e = STArray !i !i (MutableArray# s e) + +-- | Mutable, boxed, non-strict arrays in the 'ST' monad. The type +-- arguments are as follows: +-- +-- * @s@: the state variable argument for the 'ST' type +-- +-- * @i@: the index type of the array (should be an instance of 'Ix') +-- +-- * @e@: the element type of the array. +-- +data STArray s i e = STArray !i !i (MutableArray# s e) + -- No Ix context for STArray. They are stupid, + -- and force an Ix context on the equality instance. -- Just pointer equality on mutable arrays: instance Eq (STArray s i e) where @@ -292,8 +341,45 @@ instance Eq (STArray s i e) where arrEleBottom :: a arrEleBottom = error "(Array.!): undefined array element" +-- | 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 #-} @@ -321,6 +407,8 @@ done l u marr# s1# = -- 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# -> @@ -334,6 +422,7 @@ 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) @@ -343,26 +432,49 @@ unsafeAt :: Ix i => Array i e -> Int -> e 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] @@ -380,6 +492,17 @@ adjust f marr# (I# i#, new) next s1# = 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 = @@ -391,6 +514,12 @@ unsafeReplace arr@(Array l u _) ies = runST (do 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 = @@ -407,6 +536,12 @@ amap :: Ix i => (a -> b) -> Array i a -> Array i b 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 = @@ -458,19 +593,14 @@ instance (Ix i, Ord e) => Ord (Array i e) where instance (Ix a, Show a, Show b) => Show (Array a b) where showsPrec p a = - showParen (p > 9) $ + showParen (p > appPrec) $ showString "array " . - shows (bounds a) . + showsPrec appPrec1 (bounds a) . showChar ' ' . - shows (assocs a) - -{- -instance (Ix a, Read a, Read b) => Read (Array a b) where - readsPrec p = readParen (p > 9) - (\r -> [(array b as, u) | ("array",s) <- lex r, - (b,t) <- reads s, - (as,u) <- reads t ]) --} + showsPrec appPrec1 (assocs a) + -- Precedence of 'array' is the precedence of application + +-- The Read instance is in GHC.Read \end{code}