GHC/Arr.lhs

   1 \begin{code}
   2 {-# OPTIONS_GHC -funbox-strict-fields #-}
   3 {-# LANGUAGE NoImplicitPrelude, NoBangPatterns #-}
   4 {-# OPTIONS_HADDOCK hide #-}
   5 -----------------------------------------------------------------------------
   6 -- |
   7 -- Module      :  GHC.Arr
   8 -- Copyright   :  (c) The University of Glasgow, 1994-2000
   9 -- License     :  see libraries/base/LICENSE
  10 --
  11 -- Maintainer  :  cvs-ghc@haskell.org
  12 -- Stability   :  internal
  13 -- Portability :  non-portable (GHC extensions)
  14 --
  15 -- GHC\'s array implementation.
  16 --
  17 -----------------------------------------------------------------------------
  18
  19 -- #hide
  20 module GHC.Arr where
  21
  22 import GHC.Enum
  23 import GHC.Num
  24 import GHC.ST
  25 import GHC.Base
  26 import GHC.List
  27 import GHC.Show
  28
  29 infixl 9  !, //
  30
  31 default ()
  32 \end{code}
  33
  34
  35 %*********************************************************
  36 %*                                                      *
  37 \subsection{The @Ix@ class}
  38 %*                                                      *
  39 %*********************************************************
  40
  41 \begin{code}
  42 -- | The 'Ix' class is used to map a contiguous subrange of values in
  43 -- a type onto integers.  It is used primarily for array indexing
  44 -- (see the array package).
  45 --
  46 -- The first argument @(l,u)@ of each of these operations is a pair
  47 -- specifying the lower and upper bounds of a contiguous subrange of values.
  48 --
  49 -- An implementation is entitled to assume the following laws about these
  50 -- operations:
  51 --
  52 -- * @'inRange' (l,u) i == 'elem' i ('range' (l,u))@
  53 --
  54 -- * @'range' (l,u) '!!' 'index' (l,u) i == i@, when @'inRange' (l,u) i@
  55 --
  56 -- * @'map' ('index' (l,u)) ('range' (l,u))) == [0..'rangeSize' (l,u)-1]@
  57 --
  58 -- * @'rangeSize' (l,u) == 'length' ('range' (l,u))@
  59 --
  60 -- Minimal complete instance: 'range', 'index' and 'inRange'.
  61 --
  62 class (Ord a) => Ix a where
  63     -- | The list of values in the subrange defined by a bounding pair.
  64     range               :: (a,a) -> [a]
  65     -- | The position of a subscript in the subrange.
  66     index               :: (a,a) -> a -> Int
  67     -- | Like 'index', but without checking that the value is in range.
  68     unsafeIndex         :: (a,a) -> a -> Int
  69     -- | Returns 'True' the given subscript lies in the range defined
  70     -- the bounding pair.
  71     inRange             :: (a,a) -> a -> Bool
  72     -- | The size of the subrange defined by a bounding pair.
  73     rangeSize           :: (a,a) -> Int
  74     -- | like 'rangeSize', but without checking that the upper bound is
  75     -- in range.
  76     unsafeRangeSize     :: (a,a) -> Int
  77
  78         -- Must specify one of index, unsafeIndex
  79     index b i | inRange b i = unsafeIndex b i
  80               | otherwise   = error "Error in array index"
  81     unsafeIndex b i = index b i
  82
  83     rangeSize b@(_l,h) | inRange b h = unsafeIndex b h + 1
  84                        | otherwise   = 0        -- This case is only here to
  85                                                 -- check for an empty range
  86         -- NB: replacing (inRange b h) by (l <= h) fails for
  87         --     tuples.  E.g.  (1,2) <= (2,1) but the range is empty
  88
  89     unsafeRangeSize b@(_l,h) = unsafeIndex b h + 1
  90 \end{code}
  91
  92 Note that the following is NOT right
  93         rangeSize (l,h) | l <= h    = index b h + 1
  94                         | otherwise = 0
  95
  96 Because it might be the case that l<h, but the range
  97 is nevertheless empty.  Consider
  98         ((1,2),(2,1))
  99 Here l<h, but the second index ranges from 2..1 and
 100 hence is empty
 101
 102 %*********************************************************
 103 %*                                                      *
 104 \subsection{Instances of @Ix@}
 105 %*                                                      *
 106 %*********************************************************
 107
 108 \begin{code}
 109 -- abstract these errors from the relevant index functions so that
 110 -- the guts of the function will be small enough to inline.
 111
 112 {-# NOINLINE indexError #-}
 113 indexError :: Show a => (a,a) -> a -> String -> b
 114 indexError rng i tp
 115   = error (showString "Ix{" . showString tp . showString "}.index: Index " .
 116            showParen True (showsPrec 0 i) .
 117            showString " out of range " $
 118            showParen True (showsPrec 0 rng) "")
 119
 120 ----------------------------------------------------------------------
 121 instance  Ix Char  where
 122     {-# INLINE range #-}
 123     range (m,n) = [m..n]
 124
 125     {-# INLINE unsafeIndex #-}
 126     unsafeIndex (m,_n) i = fromEnum i - fromEnum m
 127
 128     index b i | inRange b i =  unsafeIndex b i
 129               | otherwise   =  indexError b i "Char"
 130
 131     inRange (m,n) i     =  m <= i && i <= n
 132
 133 ----------------------------------------------------------------------
 134 instance  Ix Int  where
 135     {-# INLINE range #-}
 136         -- The INLINE stops the build in the RHS from getting inlined,
 137         -- so that callers can fuse with the result of range
 138     range (m,n) = [m..n]
 139
 140     {-# INLINE unsafeIndex #-}
 141     unsafeIndex (m,_n) i = i - m
 142
 143     index b i | inRange b i =  unsafeIndex b i
 144               | otherwise   =  indexError b i "Int"
 145
 146     {-# INLINE inRange #-}
 147     inRange (I# m,I# n) (I# i) =  m <=# i && i <=# n
 148
 149 ----------------------------------------------------------------------
 150 instance  Ix Integer  where
 151     {-# INLINE range #-}
 152     range (m,n) = [m..n]
 153
 154     {-# INLINE unsafeIndex #-}
 155     unsafeIndex (m,_n) i   = fromInteger (i - m)
 156
 157     index b i | inRange b i =  unsafeIndex b i
 158               | otherwise   =  indexError b i "Integer"
 159
 160     inRange (m,n) i     =  m <= i && i <= n
 161
 162 ----------------------------------------------------------------------
 163 instance Ix Bool where -- as derived
 164     {-# INLINE range #-}
 165     range (m,n) = [m..n]
 166
 167     {-# INLINE unsafeIndex #-}
 168     unsafeIndex (l,_) i = fromEnum i - fromEnum l
 169
 170     index b i | inRange b i =  unsafeIndex b i
 171               | otherwise   =  indexError b i "Bool"
 172
 173     inRange (l,u) i = fromEnum i >= fromEnum l && fromEnum i <= fromEnum u
 174
 175 ----------------------------------------------------------------------
 176 instance Ix Ordering where -- as derived
 177     {-# INLINE range #-}
 178     range (m,n) = [m..n]
 179
 180     {-# INLINE unsafeIndex #-}
 181     unsafeIndex (l,_) i = fromEnum i - fromEnum l
 182
 183     index b i | inRange b i =  unsafeIndex b i
 184               | otherwise   =  indexError b i "Ordering"
 185
 186     inRange (l,u) i = fromEnum i >= fromEnum l && fromEnum i <= fromEnum u
 187
 188 ----------------------------------------------------------------------
 189 instance Ix () where
 190     {-# INLINE range #-}
 191     range   ((), ())    = [()]
 192     {-# INLINE unsafeIndex #-}
 193     unsafeIndex   ((), ()) () = 0
 194     {-# INLINE inRange #-}
 195     inRange ((), ()) () = True
 196     {-# INLINE index #-}
 197     index b i = unsafeIndex b i
 198
 199 ----------------------------------------------------------------------
 200 instance (Ix a, Ix b) => Ix (a, b) where -- as derived
 201     {-# SPECIALISE instance Ix (Int,Int) #-}
 202
 203     {-# INLINE range #-}
 204     range ((l1,l2),(u1,u2)) =
 205       [ (i1,i2) | i1 <- range (l1,u1), i2 <- range (l2,u2) ]
 206
 207     {-# INLINE unsafeIndex #-}
 208     unsafeIndex ((l1,l2),(u1,u2)) (i1,i2) =
 209       unsafeIndex (l1,u1) i1 * unsafeRangeSize (l2,u2) + unsafeIndex (l2,u2) i2
 210
 211     {-# INLINE inRange #-}
 212     inRange ((l1,l2),(u1,u2)) (i1,i2) =
 213       inRange (l1,u1) i1 && inRange (l2,u2) i2
 214
 215     -- Default method for index
 216
 217 ----------------------------------------------------------------------
 218 instance  (Ix a1, Ix a2, Ix a3) => Ix (a1,a2,a3)  where
 219     {-# SPECIALISE instance Ix (Int,Int,Int) #-}
 220
 221     range ((l1,l2,l3),(u1,u2,u3)) =
 222         [(i1,i2,i3) | i1 <- range (l1,u1),
 223                       i2 <- range (l2,u2),
 224                       i3 <- range (l3,u3)]
 225
 226     unsafeIndex ((l1,l2,l3),(u1,u2,u3)) (i1,i2,i3) =
 227       unsafeIndex (l3,u3) i3 + unsafeRangeSize (l3,u3) * (
 228       unsafeIndex (l2,u2) i2 + unsafeRangeSize (l2,u2) * (
 229       unsafeIndex (l1,u1) i1))
 230
 231     inRange ((l1,l2,l3),(u1,u2,u3)) (i1,i2,i3) =
 232       inRange (l1,u1) i1 && inRange (l2,u2) i2 &&
 233       inRange (l3,u3) i3
 234
 235     -- Default method for index
 236
 237 ----------------------------------------------------------------------
 238 instance  (Ix a1, Ix a2, Ix a3, Ix a4) => Ix (a1,a2,a3,a4)  where
 239     range ((l1,l2,l3,l4),(u1,u2,u3,u4)) =
 240       [(i1,i2,i3,i4) | i1 <- range (l1,u1),
 241                        i2 <- range (l2,u2),
 242                        i3 <- range (l3,u3),
 243                        i4 <- range (l4,u4)]
 244
 245     unsafeIndex ((l1,l2,l3,l4),(u1,u2,u3,u4)) (i1,i2,i3,i4) =
 246       unsafeIndex (l4,u4) i4 + unsafeRangeSize (l4,u4) * (
 247       unsafeIndex (l3,u3) i3 + unsafeRangeSize (l3,u3) * (
 248       unsafeIndex (l2,u2) i2 + unsafeRangeSize (l2,u2) * (
 249       unsafeIndex (l1,u1) i1)))
 250
 251     inRange ((l1,l2,l3,l4),(u1,u2,u3,u4)) (i1,i2,i3,i4) =
 252       inRange (l1,u1) i1 && inRange (l2,u2) i2 &&
 253       inRange (l3,u3) i3 && inRange (l4,u4) i4
 254
 255     -- Default method for index
 256
 257 instance  (Ix a1, Ix a2, Ix a3, Ix a4, Ix a5) => Ix (a1,a2,a3,a4,a5)  where
 258     range ((l1,l2,l3,l4,l5),(u1,u2,u3,u4,u5)) =
 259       [(i1,i2,i3,i4,i5) | i1 <- range (l1,u1),
 260                           i2 <- range (l2,u2),
 261                           i3 <- range (l3,u3),
 262                           i4 <- range (l4,u4),
 263                           i5 <- range (l5,u5)]
 264
 265     unsafeIndex ((l1,l2,l3,l4,l5),(u1,u2,u3,u4,u5)) (i1,i2,i3,i4,i5) =
 266       unsafeIndex (l5,u5) i5 + unsafeRangeSize (l5,u5) * (
 267       unsafeIndex (l4,u4) i4 + unsafeRangeSize (l4,u4) * (
 268       unsafeIndex (l3,u3) i3 + unsafeRangeSize (l3,u3) * (
 269       unsafeIndex (l2,u2) i2 + unsafeRangeSize (l2,u2) * (
 270       unsafeIndex (l1,u1) i1))))
 271
 272     inRange ((l1,l2,l3,l4,l5),(u1,u2,u3,u4,u5)) (i1,i2,i3,i4,i5) =
 273       inRange (l1,u1) i1 && inRange (l2,u2) i2 &&
 274       inRange (l3,u3) i3 && inRange (l4,u4) i4 &&
 275       inRange (l5,u5) i5
 276
 277     -- Default method for index
 278 \end{code}
 279
 280 %*********************************************************
 281 %*                                                      *
 282 \subsection{The @Array@ types}
 283 %*                                                      *
 284 %*********************************************************
 285
 286 \begin{code}
 287 type IPr = (Int, Int)
 288
 289 -- | The type of immutable non-strict (boxed) arrays
 290 -- with indices in @i@ and elements in @e@.
 291 -- The Int is the number of elements in the Array.
 292 data Ix i => Array i e
 293                  = Array !i         -- the lower bound, l
 294                          !i         -- the upper bound, u
 295                          !Int       -- a cache of (rangeSize (l,u))
 296                                     -- used to make sure an index is
 297                                     -- really in range
 298                          (Array# e) -- The actual elements
 299
 300 -- | Mutable, boxed, non-strict arrays in the 'ST' monad.  The type
 301 -- arguments are as follows:
 302 --
 303 --  * @s@: the state variable argument for the 'ST' type
 304 --
 305 --  * @i@: the index type of the array (should be an instance of 'Ix')
 306 --
 307 --  * @e@: the element type of the array.
 308 --
 309 data STArray s i e
 310          = STArray !i                  -- the lower bound, l
 311                    !i                  -- the upper bound, u
 312                    !Int                -- a cache of (rangeSize (l,u))
 313                                        -- used to make sure an index is
 314                                        -- really in range
 315                    (MutableArray# s e) -- The actual elements
 316         -- No Ix context for STArray.  They are stupid,
 317         -- and force an Ix context on the equality instance.
 318
 319 -- Just pointer equality on mutable arrays:
 320 instance Eq (STArray s i e) where
 321     STArray _ _ _ arr1# == STArray _ _ _ arr2# =
 322         sameMutableArray# arr1# arr2#
 323 \end{code}
 324
 325
 326 %*********************************************************
 327 %*                                                      *
 328 \subsection{Operations on immutable arrays}
 329 %*                                                      *
 330 %*********************************************************
 331
 332 \begin{code}
 333 {-# NOINLINE arrEleBottom #-}
 334 arrEleBottom :: a
 335 arrEleBottom = error "(Array.!): undefined array element"
 336
 337 -- | Construct an array with the specified bounds and containing values
 338 -- for given indices within these bounds.
 339 --
 340 -- The array is undefined (i.e. bottom) if any index in the list is
 341 -- out of bounds.  The Haskell 98 Report further specifies that if any
 342 -- two associations in the list have the same index, the value at that
 343 -- index is undefined (i.e. bottom).  However in GHC's implementation,
 344 -- the value at such an index is the value part of the last association
 345 -- with that index in the list.
 346 --
 347 -- Because the indices must be checked for these errors, 'array' is
 348 -- strict in the bounds argument and in the indices of the association
 349 -- list, but nonstrict in the values.  Thus, recurrences such as the
 350 -- following are possible:
 351 --
 352 -- > a = array (1,100) ((1,1) : [(i, i * a!(i-1)) | i <- [2..100]])
 353 --
 354 -- Not every index within the bounds of the array need appear in the
 355 -- association list, but the values associated with indices that do not
 356 -- appear will be undefined (i.e. bottom).
 357 --
 358 -- If, in any dimension, the lower bound is greater than the upper bound,
 359 -- then the array is legal, but empty.  Indexing an empty array always
 360 -- gives an array-bounds error, but 'bounds' still yields the bounds
 361 -- with which the array was constructed.
 362 {-# INLINE array #-}
 363 array :: Ix i
 364         => (i,i)        -- ^ a pair of /bounds/, each of the index type
 365                         -- of the array.  These bounds are the lowest and
 366                         -- highest indices in the array, in that order.
 367                         -- For example, a one-origin vector of length
 368                         -- '10' has bounds '(1,10)', and a one-origin '10'
 369                         -- by '10' matrix has bounds '((1,1),(10,10))'.
 370         -> [(i, e)]     -- ^ a list of /associations/ of the form
 371                         -- (/index/, /value/).  Typically, this list will
 372                         -- be expressed as a comprehension.  An
 373                         -- association '(i, x)' defines the value of
 374                         -- the array at index 'i' to be 'x'.
 375         -> Array i e
 376 array (l,u) ies
 377     = let n = safeRangeSize (l,u)
 378       in unsafeArray' (l,u) n
 379                       [(safeIndex (l,u) n i, e) | (i, e) <- ies]
 380
 381 {-# INLINE unsafeArray #-}
 382 unsafeArray :: Ix i => (i,i) -> [(Int, e)] -> Array i e
 383 unsafeArray b ies = unsafeArray' b (rangeSize b) ies
 384
 385 {-# INLINE unsafeArray' #-}
 386 unsafeArray' :: Ix i => (i,i) -> Int -> [(Int, e)] -> Array i e
 387 unsafeArray' (l,u) n@(I# n#) ies = runST (ST $ \s1# ->
 388     case newArray# n# arrEleBottom s1# of
 389         (# s2#, marr# #) ->
 390             foldr (fill marr#) (done l u n marr#) ies s2#)
 391
 392 {-# INLINE fill #-}
 393 fill :: MutableArray# s e -> (Int, e) -> STRep s a -> STRep s a
 394 fill marr# (I# i#, e) next s1# =
 395     case writeArray# marr# i# e s1#     of { s2# ->
 396     next s2# }
 397
 398 {-# INLINE done #-}
 399 done :: Ix i => i -> i -> Int -> MutableArray# s e -> STRep s (Array i e)
 400 done l u n marr# s1# =
 401     case unsafeFreezeArray# marr# s1# of
 402         (# s2#, arr# #) -> (# s2#, Array l u n arr# #)
 403
 404 -- This is inefficient and I'm not sure why:
 405 -- listArray (l,u) es = unsafeArray (l,u) (zip [0 .. rangeSize (l,u) - 1] es)
 406 -- The code below is better. It still doesn't enable foldr/build
 407 -- transformation on the list of elements; I guess it's impossible
 408 -- using mechanisms currently available.
 409
 410 -- | Construct an array from a pair of bounds and a list of values in
 411 -- index order.
 412 {-# INLINE listArray #-}
 413 listArray :: Ix i => (i,i) -> [e] -> Array i e
 414 listArray (l,u) es = runST (ST $ \s1# ->
 415     case safeRangeSize (l,u)            of { n@(I# n#) ->
 416     case newArray# n# arrEleBottom s1#  of { (# s2#, marr# #) ->
 417     let fillFromList i# xs s3# | i# ==# n# = s3#
 418                                | otherwise = case xs of
 419             []   -> s3#
 420             y:ys -> case writeArray# marr# i# y s3# of { s4# ->
 421                     fillFromList (i# +# 1#) ys s4# } in
 422     case fillFromList 0# es s2#         of { s3# ->
 423     done l u n marr# s3# }}})
 424
 425 -- | The value at the given index in an array.
 426 {-# INLINE (!) #-}
 427 (!) :: Ix i => Array i e -> i -> e
 428 arr@(Array l u n _) ! i = unsafeAt arr $ safeIndex (l,u) n i
 429
 430 {-# INLINE safeRangeSize #-}
 431 safeRangeSize :: Ix i => (i, i) -> Int
 432 safeRangeSize (l,u) = let r = rangeSize (l, u)
 433                       in if r < 0 then error "Negative range size"
 434                                   else r
 435
 436 {-# INLINE safeIndex #-}
 437 safeIndex :: Ix i => (i, i) -> Int -> i -> Int
 438 safeIndex (l,u) n i = let i' = unsafeIndex (l,u) i
 439                       in if (0 <= i') && (i' < n)
 440                          then i'
 441                          else error "Error in array index"
 442
 443 {-# INLINE unsafeAt #-}
 444 unsafeAt :: Ix i => Array i e -> Int -> e
 445 unsafeAt (Array _ _ _ arr#) (I# i#) =
 446     case indexArray# arr# i# of (# e #) -> e
 447
 448 -- | The bounds with which an array was constructed.
 449 {-# INLINE bounds #-}
 450 bounds :: Ix i => Array i e -> (i,i)
 451 bounds (Array l u _ _) = (l,u)
 452
 453 -- | The number of elements in the array.
 454 {-# INLINE numElements #-}
 455 numElements :: Ix i => Array i e -> Int
 456 numElements (Array _ _ n _) = n
 457
 458 -- | The list of indices of an array in ascending order.
 459 {-# INLINE indices #-}
 460 indices :: Ix i => Array i e -> [i]
 461 indices (Array l u _ _) = range (l,u)
 462
 463 -- | The list of elements of an array in index order.
 464 {-# INLINE elems #-}
 465 elems :: Ix i => Array i e -> [e]
 466 elems arr@(Array l u n _) =
 467     [unsafeAt arr i | i <- [0 .. n - 1]]
 468
 469 -- | The list of associations of an array in index order.
 470 {-# INLINE assocs #-}
 471 assocs :: Ix i => Array i e -> [(i, e)]
 472 assocs arr@(Array l u _ _) =
 473     [(i, arr ! i) | i <- range (l,u)]
 474
 475 -- | The 'accumArray' deals with repeated indices in the association
 476 -- list using an /accumulating function/ which combines the values of
 477 -- associations with the same index.
 478 -- For example, given a list of values of some index type, @hist@
 479 -- produces a histogram of the number of occurrences of each index within
 480 -- a specified range:
 481 --
 482 -- > hist :: (Ix a, Num b) => (a,a) -> [a] -> Array a b
 483 -- > hist bnds is = accumArray (+) 0 bnds [(i, 1) | i<-is, inRange bnds i]
 484 --
 485 -- If the accumulating function is strict, then 'accumArray' is strict in
 486 -- the values, as well as the indices, in the association list.  Thus,
 487 -- unlike ordinary arrays built with 'array', accumulated arrays should
 488 -- not in general be recursive.
 489 {-# INLINE accumArray #-}
 490 accumArray :: Ix i
 491         => (e -> a -> e)        -- ^ accumulating function
 492         -> e                    -- ^ initial value
 493         -> (i,i)                -- ^ bounds of the array
 494         -> [(i, a)]             -- ^ association list
 495         -> Array i e
 496 accumArray f init (l,u) ies =
 497     let n = safeRangeSize (l,u)
 498     in unsafeAccumArray' f init (l,u) n
 499                          [(safeIndex (l,u) n i, e) | (i, e) <- ies]
 500
 501 {-# INLINE unsafeAccumArray #-}
 502 unsafeAccumArray :: Ix i => (e -> a -> e) -> e -> (i,i) -> [(Int, a)] -> Array i e
 503 unsafeAccumArray f init b ies = unsafeAccumArray' f init b (rangeSize b) ies
 504
 505 {-# INLINE unsafeAccumArray' #-}
 506 unsafeAccumArray' :: Ix i => (e -> a -> e) -> e -> (i,i) -> Int -> [(Int, a)] -> Array i e
 507 unsafeAccumArray' f init (l,u) n@(I# n#) ies = runST (ST $ \s1# ->
 508     case newArray# n# init s1#          of { (# s2#, marr# #) ->
 509     foldr (adjust f marr#) (done l u n marr#) ies s2# })
 510
 511 {-# INLINE adjust #-}
 512 adjust :: (e -> a -> e) -> MutableArray# s e -> (Int, a) -> STRep s b -> STRep s b
 513 adjust f marr# (I# i#, new) next s1# =
 514     case readArray# marr# i# s1# of
 515         (# s2#, old #) ->
 516             case writeArray# marr# i# (f old new) s2# of
 517                 s3# -> next s3#
 518
 519 -- | Constructs an array identical to the first argument except that it has
 520 -- been updated by the associations in the right argument.
 521 -- For example, if @m@ is a 1-origin, @n@ by @n@ matrix, then
 522 --
 523 -- > m//[((i,i), 0) | i <- [1..n]]
 524 --
 525 -- is the same matrix, except with the diagonal zeroed.
 526 --
 527 -- Repeated indices in the association list are handled as for 'array':
 528 -- Haskell 98 specifies that the resulting array is undefined (i.e. bottom),
 529 -- but GHC's implementation uses the last association for each index.
 530 {-# INLINE (//) #-}
 531 (//) :: Ix i => Array i e -> [(i, e)] -> Array i e
 532 arr@(Array l u n _) // ies =
 533     unsafeReplace arr [(safeIndex (l,u) n i, e) | (i, e) <- ies]
 534
 535 {-# INLINE unsafeReplace #-}
 536 unsafeReplace :: Ix i => Array i e -> [(Int, e)] -> Array i e
 537 unsafeReplace arr ies = runST (do
 538     STArray l u n marr# <- thawSTArray arr
 539     ST (foldr (fill marr#) (done l u n marr#) ies))
 540
 541 -- | @'accum' f@ takes an array and an association list and accumulates
 542 -- pairs from the list into the array with the accumulating function @f@.
 543 -- Thus 'accumArray' can be defined using 'accum':
 544 --
 545 -- > accumArray f z b = accum f (array b [(i, z) | i <- range b])
 546 --
 547 {-# INLINE accum #-}
 548 accum :: Ix i => (e -> a -> e) -> Array i e -> [(i, a)] -> Array i e
 549 accum f arr@(Array l u n _) ies =
 550     unsafeAccum f arr [(safeIndex (l,u) n i, e) | (i, e) <- ies]
 551
 552 {-# INLINE unsafeAccum #-}
 553 unsafeAccum :: Ix i => (e -> a -> e) -> Array i e -> [(Int, a)] -> Array i e
 554 unsafeAccum f arr ies = runST (do
 555     STArray l u n marr# <- thawSTArray arr
 556     ST (foldr (adjust f marr#) (done l u n marr#) ies))
 557
 558 {-# INLINE amap #-}
 559 amap :: Ix i => (a -> b) -> Array i a -> Array i b
 560 amap f arr@(Array l u n _) =
 561     unsafeArray' (l,u) n [(i, f (unsafeAt arr i)) | i <- [0 .. n - 1]]
 562
 563 -- | 'ixmap' allows for transformations on array indices.
 564 -- It may be thought of as providing function composition on the right
 565 -- with the mapping that the original array embodies.
 566 --
 567 -- A similar transformation of array values may be achieved using 'fmap'
 568 -- from the 'Array' instance of the 'Functor' class.
 569 {-# INLINE ixmap #-}
 570 ixmap :: (Ix i, Ix j) => (i,i) -> (i -> j) -> Array j e -> Array i e
 571 ixmap (l,u) f arr =
 572     array (l,u) [(i, arr ! f i) | i <- range (l,u)]
 573
 574 {-# INLINE eqArray #-}
 575 eqArray :: (Ix i, Eq e) => Array i e -> Array i e -> Bool
 576 eqArray arr1@(Array l1 u1 n1 _) arr2@(Array l2 u2 n2 _) =
 577     if n1 == 0 then n2 == 0 else
 578     l1 == l2 && u1 == u2 &&
 579     and [unsafeAt arr1 i == unsafeAt arr2 i | i <- [0 .. n1 - 1]]
 580
 581 {-# INLINE cmpArray #-}
 582 cmpArray :: (Ix i, Ord e) => Array i e -> Array i e -> Ordering
 583 cmpArray arr1 arr2 = compare (assocs arr1) (assocs arr2)
 584
 585 {-# INLINE cmpIntArray #-}
 586 cmpIntArray :: Ord e => Array Int e -> Array Int e -> Ordering
 587 cmpIntArray arr1@(Array l1 u1 n1 _) arr2@(Array l2 u2 n2 _) =
 588     if n1 == 0 then
 589         if n2 == 0 then EQ else LT
 590     else if n2 == 0 then GT
 591     else case compare l1 l2 of
 592              EQ    -> foldr cmp (compare u1 u2) [0 .. (n1 `min` n2) - 1]
 593              other -> other
 594   where
 595     cmp i rest = case compare (unsafeAt arr1 i) (unsafeAt arr2 i) of
 596         EQ    -> rest
 597         other -> other
 598
 599 {-# RULES "cmpArray/Int" cmpArray = cmpIntArray #-}
 600 \end{code}
 601
 602
 603 %*********************************************************
 604 %*                                                      *
 605 \subsection{Array instances}
 606 %*                                                      *
 607 %*********************************************************
 608
 609 \begin{code}
 610 instance Ix i => Functor (Array i) where
 611     fmap = amap
 612
 613 instance (Ix i, Eq e) => Eq (Array i e) where
 614     (==) = eqArray
 615
 616 instance (Ix i, Ord e) => Ord (Array i e) where
 617     compare = cmpArray
 618
 619 instance (Ix a, Show a, Show b) => Show (Array a b) where
 620     showsPrec p a =
 621         showParen (p > appPrec) $
 622         showString "array " .
 623         showsPrec appPrec1 (bounds a) .
 624         showChar ' ' .
 625         showsPrec appPrec1 (assocs a)
 626         -- Precedence of 'array' is the precedence of application
 627
 628 -- The Read instance is in GHC.Read
 629 \end{code}
 630
 631
 632 %*********************************************************
 633 %*                                                      *
 634 \subsection{Operations on mutable arrays}
 635 %*                                                      *
 636 %*********************************************************
 637
 638 Idle ADR question: What's the tradeoff here between flattening these
 639 datatypes into @STArray ix ix (MutableArray# s elt)@ and using
 640 it as is?  As I see it, the former uses slightly less heap and
 641 provides faster access to the individual parts of the bounds while the
 642 code used has the benefit of providing a ready-made @(lo, hi)@ pair as
 643 required by many array-related functions.  Which wins? Is the
 644 difference significant (probably not).
 645
 646 Idle AJG answer: When I looked at the outputted code (though it was 2
 647 years ago) it seems like you often needed the tuple, and we build
 648 it frequently. Now we've got the overloading specialiser things
 649 might be different, though.
 650
 651 \begin{code}
 652 {-# INLINE newSTArray #-}
 653 newSTArray :: Ix i => (i,i) -> e -> ST s (STArray s i e)
 654 newSTArray (l,u) init = ST $ \s1# ->
 655     case safeRangeSize (l,u)            of { n@(I# n#) ->
 656     case newArray# n# init s1#          of { (# s2#, marr# #) ->
 657     (# s2#, STArray l u n marr# #) }}
 658
 659 {-# INLINE boundsSTArray #-}
 660 boundsSTArray :: STArray s i e -> (i,i)
 661 boundsSTArray (STArray l u _ _) = (l,u)
 662
 663 {-# INLINE numElementsSTArray #-}
 664 numElementsSTArray :: STArray s i e -> Int
 665 numElementsSTArray (STArray _ _ n _) = n
 666
 667 {-# INLINE readSTArray #-}
 668 readSTArray :: Ix i => STArray s i e -> i -> ST s e
 669 readSTArray marr@(STArray l u n _) i =
 670     unsafeReadSTArray marr (safeIndex (l,u) n i)
 671
 672 {-# INLINE unsafeReadSTArray #-}
 673 unsafeReadSTArray :: Ix i => STArray s i e -> Int -> ST s e
 674 unsafeReadSTArray (STArray _ _ _ marr#) (I# i#)
 675     = ST $ \s1# -> readArray# marr# i# s1#
 676
 677 {-# INLINE writeSTArray #-}
 678 writeSTArray :: Ix i => STArray s i e -> i -> e -> ST s ()
 679 writeSTArray marr@(STArray l u n _) i e =
 680     unsafeWriteSTArray marr (safeIndex (l,u) n i) e
 681
 682 {-# INLINE unsafeWriteSTArray #-}
 683 unsafeWriteSTArray :: Ix i => STArray s i e -> Int -> e -> ST s ()
 684 unsafeWriteSTArray (STArray _ _ _ marr#) (I# i#) e = ST $ \s1# ->
 685     case writeArray# marr# i# e s1# of
 686         s2# -> (# s2#, () #)
 687 \end{code}
 688
 689
 690 %*********************************************************
 691 %*                                                      *
 692 \subsection{Moving between mutable and immutable}
 693 %*                                                      *
 694 %*********************************************************
 695
 696 \begin{code}
 697 freezeSTArray :: Ix i => STArray s i e -> ST s (Array i e)
 698 freezeSTArray (STArray l u n@(I# n#) marr#) = ST $ \s1# ->
 699     case newArray# n# arrEleBottom s1#  of { (# s2#, marr'# #) ->
 700     let copy i# s3# | i# ==# n# = s3#
 701                     | otherwise =
 702             case readArray# marr# i# s3# of { (# s4#, e #) ->
 703             case writeArray# marr'# i# e s4# of { s5# ->
 704             copy (i# +# 1#) s5# }} in
 705     case copy 0# s2#                    of { s3# ->
 706     case unsafeFreezeArray# marr'# s3#  of { (# s4#, arr# #) ->
 707     (# s4#, Array l u n arr# #) }}}
 708
 709 {-# INLINE unsafeFreezeSTArray #-}
 710 unsafeFreezeSTArray :: Ix i => STArray s i e -> ST s (Array i e)
 711 unsafeFreezeSTArray (STArray l u n marr#) = ST $ \s1# ->
 712     case unsafeFreezeArray# marr# s1#   of { (# s2#, arr# #) ->
 713     (# s2#, Array l u n arr# #) }
 714
 715 thawSTArray :: Ix i => Array i e -> ST s (STArray s i e)
 716 thawSTArray (Array l u n@(I# n#) arr#) = ST $ \s1# ->
 717     case newArray# n# arrEleBottom s1#  of { (# s2#, marr# #) ->
 718     let copy i# s3# | i# ==# n# = s3#
 719                     | otherwise =
 720             case indexArray# arr# i#    of { (# e #) ->
 721             case writeArray# marr# i# e s3# of { s4# ->
 722             copy (i# +# 1#) s4# }} in
 723     case copy 0# s2#                    of { s3# ->
 724     (# s3#, STArray l u n marr# #) }}
 725
 726 {-# INLINE unsafeThawSTArray #-}
 727 unsafeThawSTArray :: Ix i => Array i e -> ST s (STArray s i e)
 728 unsafeThawSTArray (Array l u n arr#) = ST $ \s1# ->
 729     case unsafeThawArray# arr# s1#      of { (# s2#, marr# #) ->
 730     (# s2#, STArray l u n marr# #) }
 731 \end{code}