X-Git-Url: http://git.megacz.com/?a=blobdiff_plain;f=GHC%2FArr.lhs;h=dbd7975218b9714ef2d3c1c56f0e66670ad9822b;hb=ee7be4593b1b17d4ef45c37963b8b19d53865ab6;hp=4586fec9d40250e8c6fbeb7445e3901ae0a63b78;hpb=9998ccb135e022aee442d32bf1f9e723a2256887;p=ghc-base.git diff --git a/GHC/Arr.lhs b/GHC/Arr.lhs index 4586fec..dbd7975 100644 --- a/GHC/Arr.lhs +++ b/GHC/Arr.lhs @@ -1,5 +1,7 @@ \begin{code} -{-# OPTIONS_GHC -fno-implicit-prelude -fno-bang-patterns -funbox-strict-fields #-} +{-# OPTIONS_GHC -funbox-strict-fields #-} +{-# LANGUAGE NoImplicitPrelude, NoBangPatterns #-} +{-# OPTIONS_HADDOCK hide #-} ----------------------------------------------------------------------------- -- | -- Module : GHC.Arr @@ -17,7 +19,6 @@ -- #hide module GHC.Arr where -import {-# SOURCE #-} GHC.Err ( error ) import GHC.Enum import GHC.Num import GHC.ST @@ -32,9 +33,9 @@ default () %********************************************************* -%* * +%* * \subsection{The @Ix@ class} -%* * +%* * %********************************************************* \begin{code} @@ -60,48 +61,48 @@ default () -- class (Ord a) => Ix a where -- | The list of values in the subrange defined by a bounding pair. - range :: (a,a) -> [a] + range :: (a,a) -> [a] -- | The position of a subscript in the subrange. - index :: (a,a) -> a -> Int + index :: (a,a) -> a -> Int -- | Like 'index', but without checking that the value is in range. - unsafeIndex :: (a,a) -> a -> Int + unsafeIndex :: (a,a) -> a -> Int -- | Returns 'True' the given subscript lies in the range defined -- the bounding pair. - inRange :: (a,a) -> a -> Bool + inRange :: (a,a) -> a -> Bool -- | The size of the subrange defined by a bounding pair. - rangeSize :: (a,a) -> Int + 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 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 -- 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 + | 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) "") ---------------------------------------------------------------------- instance Ix Char where @@ -125,22 +126,22 @@ instance Ix Char where unsafeIndex (m,_n) i = fromEnum i - fromEnum m index b i | inRange b i = unsafeIndex b i - | otherwise = indexError b i "Char" + | otherwise = indexError b i "Char" - inRange (m,n) i = m <= i && i <= n + 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 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 @@ -154,9 +155,9 @@ instance Ix Integer where unsafeIndex (m,_n) i = fromInteger (i - m) 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 + inRange (m,n) i = m <= i && i <= n ---------------------------------------------------------------------- instance Ix Bool where -- as derived @@ -167,7 +168,7 @@ instance Ix Bool where -- as derived unsafeIndex (l,_) i = fromEnum i - fromEnum l 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 @@ -180,7 +181,7 @@ instance Ix Ordering where -- as derived unsafeIndex (l,_) i = fromEnum i - fromEnum l 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 @@ -277,9 +278,9 @@ instance (Ix a1, Ix a2, Ix a3, Ix a4, Ix a5) => Ix (a1,a2,a3,a4,a5) where \end{code} %********************************************************* -%* * +%* * \subsection{The @Array@ types} -%* * +%* * %********************************************************* \begin{code} @@ -312,8 +313,8 @@ data STArray s i e -- 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. + -- 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 @@ -323,9 +324,9 @@ instance Eq (STArray s i e) where %********************************************************* -%* * +%* * \subsection{Operations on immutable arrays} -%* * +%* * %********************************************************* \begin{code} @@ -360,18 +361,18 @@ arrEleBottom = error "(Array.!): undefined array element" -- with which the array was constructed. {-# INLINE array #-} 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 + => (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 @@ -462,7 +463,7 @@ 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 n _) = +elems arr@(Array _ _ n _) = [unsafeAt arr i | i <- [0 .. n - 1]] -- | The list of associations of an array in index order. @@ -487,24 +488,24 @@ assocs arr@(Array l u _ _) = -- not in general be recursive. {-# INLINE accumArray #-} 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 = + => (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 init (l,u) n + 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 b ies = unsafeAccumArray' f init b (rangeSize b) ies +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 init (l,u) n@(I# n#) ies = runST (ST $ \s1# -> - case newArray# n# init s1# of { (# s2#, marr# #) -> +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 #-} @@ -600,9 +601,9 @@ cmpIntArray arr1@(Array l1 u1 n1 _) arr2@(Array l2 u2 n2 _) = %********************************************************* -%* * +%* * \subsection{Array instances} -%* * +%* * %********************************************************* \begin{code} @@ -622,16 +623,16 @@ instance (Ix a, Show a, Show b) => Show (Array a b) where showsPrec appPrec1 (bounds a) . showChar ' ' . showsPrec appPrec1 (assocs a) - -- Precedence of 'array' is the precedence of application + -- 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 @@ -650,9 +651,9 @@ 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# -> +newSTArray (l,u) initial = ST $ \s1# -> case safeRangeSize (l,u) of { n@(I# n#) -> - case newArray# n# init s1# of { (# s2#, marr# #) -> + case newArray# n# initial s1# of { (# s2#, marr# #) -> (# s2#, STArray l u n marr# #) }} {-# INLINE boundsSTArray #-} @@ -687,9 +688,9 @@ unsafeWriteSTArray (STArray _ _ _ marr#) (I# i#) e = ST $ \s1# -> %********************************************************* -%* * +%* * \subsection{Moving between mutable and immutable} -%* * +%* * %********************************************************* \begin{code}