X-Git-Url: http://git.megacz.com/?a=blobdiff_plain;f=GHC%2FArr.lhs;h=87ce3b2bc8dff3d62e30af6b0c821aff2d545ea0;hb=c1a7d1856f1af6450ae3e04072b9d36960bc2257;hp=c0c7009e82c124045e4adeefb133f35a9385d99d;hpb=2ceb6e9c72b7af137f54adfe6a4d2e0085193f80;p=haskell-directory.git diff --git a/GHC/Arr.lhs b/GHC/Arr.lhs index c0c7009..87ce3b2 100644 --- a/GHC/Arr.lhs +++ b/GHC/Arr.lhs @@ -1,5 +1,5 @@ \begin{code} -{-# OPTIONS -fno-implicit-prelude #-} +{-# OPTIONS_GHC -fno-implicit-prelude -fno-bang-patterns #-} ----------------------------------------------------------------------------- -- | -- Module : GHC.Arr @@ -14,6 +14,7 @@ -- ----------------------------------------------------------------------------- +-- #hide module GHC.Arr where import {-# SOURCE #-} GHC.Err ( error ) @@ -37,27 +38,54 @@ default () %********************************************************* \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 @@ -101,8 +129,6 @@ instance Ix Char where inRange (m,n) i = m <= i && i <= n - unsafeRangeSize b@(_l,h) = unsafeIndex b h + 1 - ---------------------------------------------------------------------- instance Ix Int where {-# INLINE range #-} @@ -119,8 +145,6 @@ instance Ix Int where {-# 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 #-} @@ -134,8 +158,6 @@ instance Ix Integer where inRange (m,n) i = m <= i && i <= n - unsafeRangeSize b@(_l,h) = unsafeIndex b h + 1 - ---------------------------------------------------------------------- instance Ix Bool where -- as derived {-# INLINE range #-} @@ -149,8 +171,6 @@ instance Ix Bool 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 Ordering where -- as derived {-# INLINE range #-} @@ -164,8 +184,6 @@ 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 #-} @@ -177,8 +195,6 @@ 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 {-# SPECIALISE instance Ix (Int,Int) #-} @@ -195,8 +211,6 @@ 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 ---------------------------------------------------------------------- @@ -217,8 +231,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 +251,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,8 +273,6 @@ 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} @@ -277,6 +285,8 @@ instance (Ix a1, Ix a2, Ix a3, Ix a4, Ix a5) => Ix (a1,a2,a3,a4,a5) where \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 @@ -310,12 +320,45 @@ instance Eq (STArray s i e) where 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 #-} @@ -343,6 +386,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# -> @@ -356,6 +401,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) @@ -365,26 +411,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] @@ -402,6 +471,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 = @@ -413,6 +493,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 = @@ -429,6 +515,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 =