X-Git-Url: http://git.megacz.com/?a=blobdiff_plain;f=GHC%2FArr.lhs;h=ade0b984d9d79efdfc0c4ad338f96c5ff627910f;hb=8073392a94dc5ab198e4758d6738a0c7f5ed68cf;hp=cb962ddddb3d55f11c132c2daa95276a7cced39a;hpb=c4f3ff1e8892824d25da4d314619e7895d5d0480;p=ghc-base.git diff --git a/GHC/Arr.lhs b/GHC/Arr.lhs index cb962dd..ade0b98 100644 --- a/GHC/Arr.lhs +++ b/GHC/Arr.lhs @@ -1,5 +1,8 @@ \begin{code} -{-# OPTIONS -fno-implicit-prelude #-} +{-# LANGUAGE NoImplicitPrelude, NoBangPatterns, MagicHash, UnboxedTuples #-} +{-# OPTIONS_GHC -funbox-strict-fields #-} +{-# OPTIONS_HADDOCK hide #-} + ----------------------------------------------------------------------------- -- | -- Module : GHC.Arr @@ -14,9 +17,9 @@ -- ----------------------------------------------------------------------------- +-- #hide module GHC.Arr where -import {-# SOURCE #-} GHC.Err ( error ) import GHC.Enum import GHC.Num import GHC.ST @@ -31,53 +34,132 @@ default () %********************************************************* -%* * +%* * \subsection{The @Ix@ class} -%* * +%* * %********************************************************* \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 the array package). +-- +-- 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 - range :: (a,a) -> [a] - index, unsafeIndex :: (a,a) -> a -> Int - inRange :: (a,a) -> a -> Bool - rangeSize :: (a,a) -> Int + -- | The list of values in the subrange defined by a bounding pair. + range :: (a,a) -> [a] + -- | 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 - | otherwise = error "Error in array index" + -- Must specify one of index, unsafeIndex + + -- 'index' is typically over-ridden in instances, with essentially + -- the same code, but using indexError instead of hopelessIndexError + -- Reason: we have 'Show' at the instances + {-# INLINE index #-} -- See Note [Inlining index] + index b i | inRange b i = unsafeIndex b i + | otherwise = hopelessIndexError + 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 - rangeSize (l,h) | l <= h = index b h + 1 - | otherwise = 0 + rangeSize (l,h) | l <= h = index b h + 1 + | otherwise = 0 Because it might be the case that l (a,a) -> a -> String -> b indexError rng i tp = error (showString "Ix{" . showString tp . showString "}.index: Index " . showParen True (showsPrec 0 i) . - showString " out of range " $ - showParen True (showsPrec 0 rng) "") + showString " out of range " $ + showParen True (showsPrec 0 rng) "") + +hopelessIndexError :: Int -- Try to use 'indexError' instead! +hopelessIndexError = error "Error in array index" ---------------------------------------------------------------------- instance Ix Char where @@ -96,31 +181,31 @@ instance Ix Char where {-# INLINE unsafeIndex #-} unsafeIndex (m,_n) i = fromEnum i - fromEnum m + {-# INLINE index #-} -- See Note [Out-of-bounds error messages] + -- and Note [Inlining index] index b i | inRange b i = unsafeIndex b i - | otherwise = indexError b i "Char" - - inRange (m,n) i = m <= i && i <= n + | otherwise = indexError b i "Char" - unsafeRangeSize b@(_l,h) = unsafeIndex b h + 1 + inRange (m,n) i = m <= i && i <= n ---------------------------------------------------------------------- instance Ix Int where {-# INLINE range #-} - -- The INLINE stops the build in the RHS from getting inlined, - -- so that callers can fuse with the result of range + -- The INLINE stops the build in the RHS from getting inlined, + -- so that callers can fuse with the result of range range (m,n) = [m..n] {-# INLINE unsafeIndex #-} unsafeIndex (m,_n) i = i - m + {-# INLINE index #-} -- See Note [Out-of-bounds error messages] + -- and Note [Inlining index] index b i | inRange b i = unsafeIndex b i - | otherwise = indexError b i "Int" + | otherwise = indexError b i "Int" {-# 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 #-} @@ -129,12 +214,12 @@ instance Ix Integer where {-# INLINE unsafeIndex #-} unsafeIndex (m,_n) i = fromInteger (i - m) + {-# INLINE index #-} -- See Note [Out-of-bounds error messages] + -- and Note [Inlining index] index b i | inRange b i = unsafeIndex b i - | otherwise = indexError b i "Integer" + | otherwise = indexError b i "Integer" - inRange (m,n) i = m <= i && i <= n - - unsafeRangeSize b@(_l,h) = unsafeIndex b h + 1 + inRange (m,n) i = m <= i && i <= n ---------------------------------------------------------------------- instance Ix Bool where -- as derived @@ -144,13 +229,13 @@ instance Ix Bool where -- as derived {-# INLINE unsafeIndex #-} unsafeIndex (l,_) i = fromEnum i - fromEnum l + {-# INLINE index #-} -- See Note [Out-of-bounds error messages] + -- and Note [Inlining index] index b i | inRange b i = unsafeIndex b i - | otherwise = indexError b i "Bool" + | otherwise = indexError b i "Bool" 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 #-} @@ -159,13 +244,13 @@ instance Ix Ordering where -- as derived {-# INLINE unsafeIndex #-} unsafeIndex (l,_) i = fromEnum i - fromEnum l + {-# INLINE index #-} -- See Note [Out-of-bounds error messages] + -- and Note [Inlining index] index b i | inRange b i = unsafeIndex b i - | otherwise = indexError b i "Ordering" + | otherwise = indexError b i "Ordering" 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 #-} @@ -174,29 +259,26 @@ instance Ix () where unsafeIndex ((), ()) () = 0 {-# INLINE inRange #-} inRange ((), ()) () = True - {-# INLINE index #-} - index b i = unsafeIndex b i - unsafeRangeSize b@(_l,h) = unsafeIndex b h + 1 + {-# INLINE index #-} -- See Note [Inlining index] + index b i = unsafeIndex b i ---------------------------------------------------------------------- instance (Ix a, Ix b) => Ix (a, b) where -- as derived {-# SPECIALISE instance Ix (Int,Int) #-} - {- INLINE range #-} + {-# INLINE range #-} range ((l1,l2),(u1,u2)) = [ (i1,i2) | i1 <- range (l1,u1), i2 <- range (l2,u2) ] - {- INLINE unsafeIndex #-} + {-# INLINE unsafeIndex #-} unsafeIndex ((l1,l2),(u1,u2)) (i1,i2) = unsafeIndex (l1,u1) i1 * unsafeRangeSize (l2,u2) + unsafeIndex (l2,u2) i2 - {- INLINE inRange #-} + {-# INLINE inRange #-} 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 ---------------------------------------------------------------------- @@ -217,8 +299,6 @@ 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 ---------------------------------------------------------------------- @@ -239,8 +319,6 @@ 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 @@ -263,36 +341,58 @@ 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} %********************************************************* -%* * +%* * \subsection{The @Array@ types} -%* * +%* * %********************************************************* \begin{code} type IPr = (Int, Int) -data Ix i => Array i e = Array !i !i (Array# e) -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. +-- | The type of immutable non-strict (boxed) arrays +-- with indices in @i@ and elements in @e@. +data Array i e + = Array !i -- the lower bound, l + !i -- the upper bound, u + !Int -- a cache of (rangeSize (l,u)) + -- used to make sure an index is + -- really in range + (Array# e) -- The actual elements + +-- | 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 -- the lower bound, l + !i -- the upper bound, u + !Int -- a cache of (rangeSize (l,u)) + -- used to make sure an index is + -- really in range + (MutableArray# s e) -- The actual elements + -- 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 - STArray _ _ arr1# == STArray _ _ arr2# = + STArray _ _ _ arr1# == STArray _ _ _ arr2# = sameMutableArray# arr1# arr2# \end{code} %********************************************************* -%* * +%* * \subsection{Operations on immutable arrays} -%* * +%* * %********************************************************* \begin{code} @@ -300,28 +400,75 @@ 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 non-strict 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 (l,u) ies = unsafeArray (l,u) [(index (l,u) i, e) | (i, e) <- ies] +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 + = let n = safeRangeSize (l,u) + in unsafeArray' (l,u) n + [(safeIndex (l,u) n i, e) | (i, e) <- ies] {-# INLINE unsafeArray #-} unsafeArray :: Ix i => (i,i) -> [(Int, e)] -> Array i e -unsafeArray (l,u) ies = runST (ST $ \s1# -> - case rangeSize (l,u) of { I# n# -> - case newArray# n# arrEleBottom s1# of { (# s2#, marr# #) -> - foldr (fill marr#) (done l u marr#) ies s2# }}) +unsafeArray b ies = unsafeArray' b (rangeSize b) ies + +{-# INLINE unsafeArray' #-} +unsafeArray' :: Ix i => (i,i) -> Int -> [(Int, e)] -> Array i e +unsafeArray' (l,u) n@(I# n#) ies = runST (ST $ \s1# -> + case newArray# n# arrEleBottom s1# of + (# s2#, marr# #) -> + foldr (fill marr#) (done l u n marr#) ies s2#) {-# INLINE fill #-} fill :: MutableArray# s e -> (Int, e) -> STRep s a -> STRep s a -fill marr# (I# i#, e) next s1# = - case writeArray# marr# i# e s1# of { s2# -> - next s2# } +-- NB: put the \s after the "=" so that 'fill' +-- inlines when applied to three args +fill marr# (I# i#, e) next + = \s1# -> case writeArray# marr# i# e s1# of + s2# -> next s2# {-# INLINE done #-} -done :: Ix i => i -> i -> MutableArray# s e -> STRep s (Array i e) -done l u marr# s1# = - case unsafeFreezeArray# marr# s1# of { (# s2#, arr# #) -> - (# s2#, Array l u arr# #) } +done :: Ix i => i -> i -> Int -> MutableArray# s e -> STRep s (Array i e) +-- See NB on 'fill' +done l u n marr# + = \s1# -> case unsafeFreezeArray# marr# s1# of + (# s2#, arr# #) -> (# s2#, Array l u n arr# #) -- This is inefficient and I'm not sure why: -- listArray (l,u) es = unsafeArray (l,u) (zip [0 .. rangeSize (l,u) - 1] es) @@ -329,10 +476,12 @@ 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# -> - case rangeSize (l,u) of { I# n# -> + case safeRangeSize (l,u) of { n@(I# n#) -> case newArray# n# arrEleBottom s1# of { (# s2#, marr# #) -> let fillFromList i# xs s3# | i# ==# n# = s3# | otherwise = case xs of @@ -340,92 +489,187 @@ listArray (l,u) es = runST (ST $ \s1# -> y:ys -> case writeArray# marr# i# y s3# of { s4# -> fillFromList (i# +# 1#) ys s4# } in case fillFromList 0# es s2# of { s3# -> - done l u marr# s3# }}}) + done l u n 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) +arr@(Array l u n _) ! i = unsafeAt arr $ safeIndex (l,u) n i + +{-# INLINE safeRangeSize #-} +safeRangeSize :: Ix i => (i, i) -> Int +safeRangeSize (l,u) = let r = rangeSize (l, u) + in if r < 0 then negRange + else r + +-- Don't inline this error message everywhere!! +negRange :: Int -- Uninformative, but Ix does not provide Show +negRange = error "Negative range size" + +{-# INLINE[1] safeIndex #-} +-- See Note [Double bounds-checking of index values] +-- Inline *after* (!) so the rules can fire +safeIndex :: Ix i => (i, i) -> Int -> i -> Int +safeIndex (l,u) n i = let i' = index (l,u) i + in if (0 <= i') && (i' < n) + then i' + else badSafeIndex i' n + +-- See Note [Double bounds-checking of index values] +{-# RULES +"safeIndex/I" safeIndex = lessSafeIndex :: (Int,Int) -> Int -> Int -> Int +"safeIndex/(I,I)" safeIndex = lessSafeIndex :: ((Int,Int),(Int,Int)) -> Int -> (Int,Int) -> Int +"safeIndex/(I,I,I)" safeIndex = lessSafeIndex :: ((Int,Int,Int),(Int,Int,Int)) -> Int -> (Int,Int,Int) -> Int + #-} + +lessSafeIndex :: Ix i => (i, i) -> Int -> i -> Int +-- See Note [Double bounds-checking of index values] +-- Do only (A), the semantic check +lessSafeIndex (l,u) _ i = index (l,u) i + +-- Don't inline this long error message everywhere!! +badSafeIndex :: Int -> Int -> Int +badSafeIndex i' n = error ("Error in array index; " ++ show i' ++ + " not in range [0.." ++ show n ++ ")") {-# INLINE unsafeAt #-} unsafeAt :: Ix i => Array i e -> Int -> e -unsafeAt (Array _ _ arr#) (I# 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) +bounds (Array l u _ _) = (l,u) +-- | The number of elements in the array. +{-# INLINE numElements #-} +numElements :: Ix i => Array i e -> Int +numElements (Array _ _ n _) = n + +-- | 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) +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]] +elems arr@(Array _ _ n _) = + [unsafeAt arr i | i <- [0 .. n - 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)] - +assocs arr@(Array l u _ _) = + [(i, arr ! i) | i <- range (l,u)] + +-- | The 'accumArray' function 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 f init (l,u) ies = - unsafeAccumArray f init (l,u) [(index (l,u) i, e) | (i, e) <- ies] +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 initial (l,u) ies = + let n = safeRangeSize (l,u) + in unsafeAccumArray' f initial (l,u) n + [(safeIndex (l,u) n i, e) | (i, e) <- ies] {-# INLINE unsafeAccumArray #-} unsafeAccumArray :: Ix i => (e -> a -> e) -> e -> (i,i) -> [(Int, a)] -> Array i e -unsafeAccumArray f init (l,u) ies = runST (ST $ \s1# -> - case rangeSize (l,u) of { I# n# -> - case newArray# n# init s1# of { (# s2#, marr# #) -> - foldr (adjust f marr#) (done l u marr#) ies s2# }}) +unsafeAccumArray f initial b ies = unsafeAccumArray' f initial b (rangeSize b) ies + +{-# INLINE unsafeAccumArray' #-} +unsafeAccumArray' :: Ix i => (e -> a -> e) -> e -> (i,i) -> Int -> [(Int, a)] -> Array i e +unsafeAccumArray' f initial (l,u) n@(I# n#) ies = runST (ST $ \s1# -> + case newArray# n# initial s1# of { (# s2#, marr# #) -> + foldr (adjust f marr#) (done l u n marr#) ies s2# }) {-# INLINE adjust #-} adjust :: (e -> a -> e) -> MutableArray# s e -> (Int, a) -> STRep s b -> STRep s b -adjust f marr# (I# i#, new) next s1# = - case readArray# marr# i# s1# of { (# s2#, old #) -> - case writeArray# marr# i# (f old new) s2# of { s3# -> - next s3# }} - +-- See NB on 'fill' +adjust f marr# (I# i#, new) next + = \s1# -> case readArray# marr# i# s1# of + (# s2#, old #) -> + 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 = - unsafeReplace arr [(index (l,u) i, e) | (i, e) <- ies] +arr@(Array l u n _) // ies = + unsafeReplace arr [(safeIndex (l,u) n i, e) | (i, e) <- ies] {-# INLINE unsafeReplace #-} unsafeReplace :: Ix i => Array i e -> [(Int, e)] -> Array i e -unsafeReplace arr@(Array l u _) ies = runST (do - STArray _ _ marr# <- thawSTArray arr - ST (foldr (fill marr#) (done l u marr#) ies)) +unsafeReplace arr ies = runST (do + STArray l u n marr# <- thawSTArray arr + ST (foldr (fill marr#) (done l u n 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 = - unsafeAccum f arr [(index (l,u) i, e) | (i, e) <- ies] +accum f arr@(Array l u n _) ies = + unsafeAccum f arr [(safeIndex (l,u) n i, e) | (i, e) <- ies] {-# INLINE unsafeAccum #-} unsafeAccum :: Ix i => (e -> a -> e) -> Array i e -> [(Int, a)] -> Array i e -unsafeAccum f arr@(Array l u _) ies = runST (do - STArray _ _ marr# <- thawSTArray arr - ST (foldr (adjust f marr#) (done l u marr#) ies)) +unsafeAccum f arr ies = runST (do + STArray l u n marr# <- thawSTArray arr + ST (foldr (adjust f marr#) (done l u n marr#) ies)) {-# INLINE amap #-} 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]] +amap f arr@(Array l u n _) = + unsafeArray' (l,u) n [(i, f (unsafeAt arr i)) | i <- [0 .. n - 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 = - unsafeArray (l,u) [(unsafeIndex (l,u) i, arr ! f i) | i <- range (l,u)] + array (l,u) [(i, arr ! f i) | i <- range (l,u)] {-# INLINE eqArray #-} eqArray :: (Ix i, Eq e) => Array i e -> Array i e -> Bool -eqArray arr1@(Array l1 u1 _) arr2@(Array l2 u2 _) = - if rangeSize (l1,u1) == 0 then rangeSize (l2,u2) == 0 else +eqArray arr1@(Array l1 u1 n1 _) arr2@(Array l2 u2 n2 _) = + if n1 == 0 then n2 == 0 else l1 == l2 && u1 == u2 && - and [unsafeAt arr1 i == unsafeAt arr2 i | i <- [0 .. rangeSize (l1,u1) - 1]] + and [unsafeAt arr1 i == unsafeAt arr2 i | i <- [0 .. n1 - 1]] {-# INLINE cmpArray #-} cmpArray :: (Ix i, Ord e) => Array i e -> Array i e -> Ordering @@ -433,13 +677,14 @@ cmpArray arr1 arr2 = compare (assocs arr1) (assocs arr2) {-# INLINE cmpIntArray #-} cmpIntArray :: Ord e => Array Int e -> Array Int e -> Ordering -cmpIntArray arr1@(Array l1 u1 _) arr2@(Array l2 u2 _) = - if rangeSize (l1,u1) == 0 then if rangeSize (l2,u2) == 0 then EQ else LT else - if rangeSize (l2,u2) == 0 then GT else - case compare l1 l2 of - EQ -> foldr cmp (compare u1 u2) [0 .. rangeSize (l1, min u1 u2) - 1] - other -> other - where +cmpIntArray arr1@(Array l1 u1 n1 _) arr2@(Array l2 u2 n2 _) = + if n1 == 0 then + if n2 == 0 then EQ else LT + else if n2 == 0 then GT + else case compare l1 l2 of + EQ -> foldr cmp (compare u1 u2) [0 .. (n1 `min` n2) - 1] + other -> other + where cmp i rest = case compare (unsafeAt arr1 i) (unsafeAt arr2 i) of EQ -> rest other -> other @@ -449,9 +694,9 @@ cmpIntArray arr1@(Array l1 u1 _) arr2@(Array l2 u2 _) = %********************************************************* -%* * +%* * \subsection{Array instances} -%* * +%* * %********************************************************* \begin{code} @@ -466,26 +711,21 @@ 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} %********************************************************* -%* * +%* * \subsection{Operations on mutable arrays} -%* * +%* * %********************************************************* Idle ADR question: What's the tradeoff here between flattening these @@ -504,48 +744,51 @@ might be different, though. \begin{code} {-# INLINE newSTArray #-} newSTArray :: Ix i => (i,i) -> e -> ST s (STArray s i e) -newSTArray (l,u) init = ST $ \s1# -> - case rangeSize (l,u) of { I# n# -> - case newArray# n# init s1# of { (# s2#, marr# #) -> - (# s2#, STArray l u marr# #) }} +newSTArray (l,u) initial = ST $ \s1# -> + case safeRangeSize (l,u) of { n@(I# n#) -> + case newArray# n# initial s1# of { (# s2#, marr# #) -> + (# s2#, STArray l u n marr# #) }} {-# INLINE boundsSTArray #-} boundsSTArray :: STArray s i e -> (i,i) -boundsSTArray (STArray l u _) = (l,u) +boundsSTArray (STArray l u _ _) = (l,u) + +{-# INLINE numElementsSTArray #-} +numElementsSTArray :: STArray s i e -> Int +numElementsSTArray (STArray _ _ n _) = n {-# INLINE readSTArray #-} readSTArray :: Ix i => STArray s i e -> i -> ST s e -readSTArray marr@(STArray l u _) i = - unsafeReadSTArray marr (index (l,u) i) +readSTArray marr@(STArray l u n _) i = + unsafeReadSTArray marr (safeIndex (l,u) n i) {-# INLINE unsafeReadSTArray #-} unsafeReadSTArray :: Ix i => STArray s i e -> Int -> ST s e -unsafeReadSTArray (STArray _ _ marr#) (I# i#) = ST $ \s1# -> - readArray# marr# i# s1# +unsafeReadSTArray (STArray _ _ _ marr#) (I# i#) + = ST $ \s1# -> readArray# marr# i# s1# {-# INLINE writeSTArray #-} writeSTArray :: Ix i => STArray s i e -> i -> e -> ST s () -writeSTArray marr@(STArray l u _) i e = - unsafeWriteSTArray marr (index (l,u) i) e +writeSTArray marr@(STArray l u n _) i e = + unsafeWriteSTArray marr (safeIndex (l,u) n i) e {-# INLINE unsafeWriteSTArray #-} unsafeWriteSTArray :: Ix i => STArray s i e -> Int -> e -> ST s () -unsafeWriteSTArray (STArray _ _ marr#) (I# i#) e = ST $ \s1# -> - case writeArray# marr# i# e s1# of { s2# -> - (# s2#, () #) } +unsafeWriteSTArray (STArray _ _ _ marr#) (I# i#) e = ST $ \s1# -> + case writeArray# marr# i# e s1# of + s2# -> (# s2#, () #) \end{code} %********************************************************* -%* * +%* * \subsection{Moving between mutable and immutable} -%* * +%* * %********************************************************* \begin{code} freezeSTArray :: Ix i => STArray s i e -> ST s (Array i e) -freezeSTArray (STArray l u marr#) = ST $ \s1# -> - case rangeSize (l,u) of { I# n# -> +freezeSTArray (STArray l u n@(I# n#) marr#) = ST $ \s1# -> case newArray# n# arrEleBottom s1# of { (# s2#, marr'# #) -> let copy i# s3# | i# ==# n# = s3# | otherwise = @@ -554,17 +797,16 @@ freezeSTArray (STArray l u marr#) = ST $ \s1# -> copy (i# +# 1#) s5# }} in case copy 0# s2# of { s3# -> case unsafeFreezeArray# marr'# s3# of { (# s4#, arr# #) -> - (# s4#, Array l u arr# #) }}}} + (# s4#, Array l u n arr# #) }}} {-# INLINE unsafeFreezeSTArray #-} unsafeFreezeSTArray :: Ix i => STArray s i e -> ST s (Array i e) -unsafeFreezeSTArray (STArray l u marr#) = ST $ \s1# -> +unsafeFreezeSTArray (STArray l u n marr#) = ST $ \s1# -> case unsafeFreezeArray# marr# s1# of { (# s2#, arr# #) -> - (# s2#, Array l u arr# #) } + (# s2#, Array l u n arr# #) } thawSTArray :: Ix i => Array i e -> ST s (STArray s i e) -thawSTArray (Array l u arr#) = ST $ \s1# -> - case rangeSize (l,u) of { I# n# -> +thawSTArray (Array l u n@(I# n#) arr#) = ST $ \s1# -> case newArray# n# arrEleBottom s1# of { (# s2#, marr# #) -> let copy i# s3# | i# ==# n# = s3# | otherwise = @@ -572,11 +814,11 @@ thawSTArray (Array l u arr#) = ST $ \s1# -> case writeArray# marr# i# e s3# of { s4# -> copy (i# +# 1#) s4# }} in case copy 0# s2# of { s3# -> - (# s3#, STArray l u marr# #) }}} + (# s3#, STArray l u n marr# #) }} {-# INLINE unsafeThawSTArray #-} unsafeThawSTArray :: Ix i => Array i e -> ST s (STArray s i e) -unsafeThawSTArray (Array l u arr#) = ST $ \s1# -> +unsafeThawSTArray (Array l u n arr#) = ST $ \s1# -> case unsafeThawArray# arr# s1# of { (# s2#, marr# #) -> - (# s2#, STArray l u marr# #) } + (# s2#, STArray l u n marr# #) } \end{code}