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' = index (l,u) i
 439                       in if (0 <= i') && (i' < n)
 440                          then i'
 441                          else error ("Error in array index; " ++ show i' ++
 442                                      " not in range [0.." ++ show n ++ ")")
 443
 444 {-# INLINE unsafeAt #-}
 445 unsafeAt :: Ix i => Array i e -> Int -> e
 446 unsafeAt (Array _ _ _ arr#) (I# i#) =
 447     case indexArray# arr# i# of (# e #) -> e
 448
 449 -- | The bounds with which an array was constructed.
 450 {-# INLINE bounds #-}
 451 bounds :: Ix i => Array i e -> (i,i)
 452 bounds (Array l u _ _) = (l,u)
 453
 454 -- | The number of elements in the array.
 455 {-# INLINE numElements #-}
 456 numElements :: Ix i => Array i e -> Int
 457 numElements (Array _ _ n _) = n
 458
 459 -- | The list of indices of an array in ascending order.
 460 {-# INLINE indices #-}
 461 indices :: Ix i => Array i e -> [i]
 462 indices (Array l u _ _) = range (l,u)
 463
 464 -- | The list of elements of an array in index order.
 465 {-# INLINE elems #-}
 466 elems :: Ix i => Array i e -> [e]
 467 elems arr@(Array _ _ n _) =
 468     [unsafeAt arr i | i <- [0 .. n - 1]]
 469
 470 -- | The list of associations of an array in index order.
 471 {-# INLINE assocs #-}
 472 assocs :: Ix i => Array i e -> [(i, e)]
 473 assocs arr@(Array l u _ _) =
 474     [(i, arr ! i) | i <- range (l,u)]
 475
 476 -- | The 'accumArray' deals with repeated indices in the association
 477 -- list using an /accumulating function/ which combines the values of
 478 -- associations with the same index.
 479 -- For example, given a list of values of some index type, @hist@
 480 -- produces a histogram of the number of occurrences of each index within
 481 -- a specified range:
 482 --
 483 -- > hist :: (Ix a, Num b) => (a,a) -> [a] -> Array a b
 484 -- > hist bnds is = accumArray (+) 0 bnds [(i, 1) | i<-is, inRange bnds i]
 485 --
 486 -- If the accumulating function is strict, then 'accumArray' is strict in
 487 -- the values, as well as the indices, in the association list.  Thus,
 488 -- unlike ordinary arrays built with 'array', accumulated arrays should
 489 -- not in general be recursive.
 490 {-# INLINE accumArray #-}
 491 accumArray :: Ix i
 492         => (e -> a -> e)        -- ^ accumulating function
 493         -> e                    -- ^ initial value
 494         -> (i,i)                -- ^ bounds of the array
 495         -> [(i, a)]             -- ^ association list
 496         -> Array i e
 497 accumArray f initial (l,u) ies =
 498     let n = safeRangeSize (l,u)
 499     in unsafeAccumArray' f initial (l,u) n
 500                          [(safeIndex (l,u) n i, e) | (i, e) <- ies]
 501
 502 {-# INLINE unsafeAccumArray #-}
 503 unsafeAccumArray :: Ix i => (e -> a -> e) -> e -> (i,i) -> [(Int, a)] -> Array i e
 504 unsafeAccumArray f initial b ies = unsafeAccumArray' f initial b (rangeSize b) ies
 505
 506 {-# INLINE unsafeAccumArray' #-}
 507 unsafeAccumArray' :: Ix i => (e -> a -> e) -> e -> (i,i) -> Int -> [(Int, a)] -> Array i e
 508 unsafeAccumArray' f initial (l,u) n@(I# n#) ies = runST (ST $ \s1# ->
 509     case newArray# n# initial s1#          of { (# s2#, marr# #) ->
 510     foldr (adjust f marr#) (done l u n marr#) ies s2# })
 511
 512 {-# INLINE adjust #-}
 513 adjust :: (e -> a -> e) -> MutableArray# s e -> (Int, a) -> STRep s b -> STRep s b
 514 adjust f marr# (I# i#, new) next s1# =
 515     case readArray# marr# i# s1# of
 516         (# s2#, old #) ->
 517             case writeArray# marr# i# (f old new) s2# of
 518                 s3# -> next s3#
 519
 520 -- | Constructs an array identical to the first argument except that it has
 521 -- been updated by the associations in the right argument.
 522 -- For example, if @m@ is a 1-origin, @n@ by @n@ matrix, then
 523 --
 524 -- > m//[((i,i), 0) | i <- [1..n]]
 525 --
 526 -- is the same matrix, except with the diagonal zeroed.
 527 --
 528 -- Repeated indices in the association list are handled as for 'array':
 529 -- Haskell 98 specifies that the resulting array is undefined (i.e. bottom),
 530 -- but GHC's implementation uses the last association for each index.
 531 {-# INLINE (//) #-}
 532 (//) :: Ix i => Array i e -> [(i, e)] -> Array i e
 533 arr@(Array l u n _) // ies =
 534     unsafeReplace arr [(safeIndex (l,u) n i, e) | (i, e) <- ies]
 535
 536 {-# INLINE unsafeReplace #-}
 537 unsafeReplace :: Ix i => Array i e -> [(Int, e)] -> Array i e
 538 unsafeReplace arr ies = runST (do
 539     STArray l u n marr# <- thawSTArray arr
 540     ST (foldr (fill marr#) (done l u n marr#) ies))
 541
 542 -- | @'accum' f@ takes an array and an association list and accumulates
 543 -- pairs from the list into the array with the accumulating function @f@.
 544 -- Thus 'accumArray' can be defined using 'accum':
 545 --
 546 -- > accumArray f z b = accum f (array b [(i, z) | i <- range b])
 547 --
 548 {-# INLINE accum #-}
 549 accum :: Ix i => (e -> a -> e) -> Array i e -> [(i, a)] -> Array i e
 550 accum f arr@(Array l u n _) ies =
 551     unsafeAccum f arr [(safeIndex (l,u) n i, e) | (i, e) <- ies]
 552
 553 {-# INLINE unsafeAccum #-}
 554 unsafeAccum :: Ix i => (e -> a -> e) -> Array i e -> [(Int, a)] -> Array i e
 555 unsafeAccum f arr ies = runST (do
 556     STArray l u n marr# <- thawSTArray arr
 557     ST (foldr (adjust f marr#) (done l u n marr#) ies))
 558
 559 {-# INLINE amap #-}
 560 amap :: Ix i => (a -> b) -> Array i a -> Array i b
 561 amap f arr@(Array l u n _) =
 562     unsafeArray' (l,u) n [(i, f (unsafeAt arr i)) | i <- [0 .. n - 1]]
 563
 564 -- | 'ixmap' allows for transformations on array indices.
 565 -- It may be thought of as providing function composition on the right
 566 -- with the mapping that the original array embodies.
 567 --
 568 -- A similar transformation of array values may be achieved using 'fmap'
 569 -- from the 'Array' instance of the 'Functor' class.
 570 {-# INLINE ixmap #-}
 571 ixmap :: (Ix i, Ix j) => (i,i) -> (i -> j) -> Array j e -> Array i e
 572 ixmap (l,u) f arr =
 573     array (l,u) [(i, arr ! f i) | i <- range (l,u)]
 574
 575 {-# INLINE eqArray #-}
 576 eqArray :: (Ix i, Eq e) => Array i e -> Array i e -> Bool
 577 eqArray arr1@(Array l1 u1 n1 _) arr2@(Array l2 u2 n2 _) =
 578     if n1 == 0 then n2 == 0 else
 579     l1 == l2 && u1 == u2 &&
 580     and [unsafeAt arr1 i == unsafeAt arr2 i | i <- [0 .. n1 - 1]]
 581
 582 {-# INLINE cmpArray #-}
 583 cmpArray :: (Ix i, Ord e) => Array i e -> Array i e -> Ordering
 584 cmpArray arr1 arr2 = compare (assocs arr1) (assocs arr2)
 585
 586 {-# INLINE cmpIntArray #-}
 587 cmpIntArray :: Ord e => Array Int e -> Array Int e -> Ordering
 588 cmpIntArray arr1@(Array l1 u1 n1 _) arr2@(Array l2 u2 n2 _) =
 589     if n1 == 0 then
 590         if n2 == 0 then EQ else LT
 591     else if n2 == 0 then GT
 592     else case compare l1 l2 of
 593              EQ    -> foldr cmp (compare u1 u2) [0 .. (n1 `min` n2) - 1]
 594              other -> other
 595   where
 596     cmp i rest = case compare (unsafeAt arr1 i) (unsafeAt arr2 i) of
 597         EQ    -> rest
 598         other -> other
 599
 600 {-# RULES "cmpArray/Int" cmpArray = cmpIntArray #-}
 601 \end{code}
 602
 603
 604 %*********************************************************
 605 %*                                                      *
 606 \subsection{Array instances}
 607 %*                                                      *
 608 %*********************************************************
 609
 610 \begin{code}
 611 instance Ix i => Functor (Array i) where
 612     fmap = amap
 613
 614 instance (Ix i, Eq e) => Eq (Array i e) where
 615     (==) = eqArray
 616
 617 instance (Ix i, Ord e) => Ord (Array i e) where
 618     compare = cmpArray
 619
 620 instance (Ix a, Show a, Show b) => Show (Array a b) where
 621     showsPrec p a =
 622         showParen (p > appPrec) $
 623         showString "array " .
 624         showsPrec appPrec1 (bounds a) .
 625         showChar ' ' .
 626         showsPrec appPrec1 (assocs a)
 627         -- Precedence of 'array' is the precedence of application
 628
 629 -- The Read instance is in GHC.Read
 630 \end{code}
 631
 632
 633 %*********************************************************
 634 %*                                                      *
 635 \subsection{Operations on mutable arrays}
 636 %*                                                      *
 637 %*********************************************************
 638
 639 Idle ADR question: What's the tradeoff here between flattening these
 640 datatypes into @STArray ix ix (MutableArray# s elt)@ and using
 641 it as is?  As I see it, the former uses slightly less heap and
 642 provides faster access to the individual parts of the bounds while the
 643 code used has the benefit of providing a ready-made @(lo, hi)@ pair as
 644 required by many array-related functions.  Which wins? Is the
 645 difference significant (probably not).
 646
 647 Idle AJG answer: When I looked at the outputted code (though it was 2
 648 years ago) it seems like you often needed the tuple, and we build
 649 it frequently. Now we've got the overloading specialiser things
 650 might be different, though.
 651
 652 \begin{code}
 653 {-# INLINE newSTArray #-}
 654 newSTArray :: Ix i => (i,i) -> e -> ST s (STArray s i e)
 655 newSTArray (l,u) initial = ST $ \s1# ->
 656     case safeRangeSize (l,u)            of { n@(I# n#) ->
 657     case newArray# n# initial s1#       of { (# s2#, marr# #) ->
 658     (# s2#, STArray l u n marr# #) }}
 659
 660 {-# INLINE boundsSTArray #-}
 661 boundsSTArray :: STArray s i e -> (i,i)
 662 boundsSTArray (STArray l u _ _) = (l,u)
 663
 664 {-# INLINE numElementsSTArray #-}
 665 numElementsSTArray :: STArray s i e -> Int
 666 numElementsSTArray (STArray _ _ n _) = n
 667
 668 {-# INLINE readSTArray #-}
 669 readSTArray :: Ix i => STArray s i e -> i -> ST s e
 670 readSTArray marr@(STArray l u n _) i =
 671     unsafeReadSTArray marr (safeIndex (l,u) n i)
 672
 673 {-# INLINE unsafeReadSTArray #-}
 674 unsafeReadSTArray :: Ix i => STArray s i e -> Int -> ST s e
 675 unsafeReadSTArray (STArray _ _ _ marr#) (I# i#)
 676     = ST $ \s1# -> readArray# marr# i# s1#
 677
 678 {-# INLINE writeSTArray #-}
 679 writeSTArray :: Ix i => STArray s i e -> i -> e -> ST s ()
 680 writeSTArray marr@(STArray l u n _) i e =
 681     unsafeWriteSTArray marr (safeIndex (l,u) n i) e
 682
 683 {-# INLINE unsafeWriteSTArray #-}
 684 unsafeWriteSTArray :: Ix i => STArray s i e -> Int -> e -> ST s ()
 685 unsafeWriteSTArray (STArray _ _ _ marr#) (I# i#) e = ST $ \s1# ->
 686     case writeArray# marr# i# e s1# of
 687         s2# -> (# s2#, () #)
 688 \end{code}
 689
 690
 691 %*********************************************************
 692 %*                                                      *
 693 \subsection{Moving between mutable and immutable}
 694 %*                                                      *
 695 %*********************************************************
 696
 697 \begin{code}
 698 freezeSTArray :: Ix i => STArray s i e -> ST s (Array i e)
 699 freezeSTArray (STArray l u n@(I# n#) marr#) = ST $ \s1# ->
 700     case newArray# n# arrEleBottom s1#  of { (# s2#, marr'# #) ->
 701     let copy i# s3# | i# ==# n# = s3#
 702                     | otherwise =
 703             case readArray# marr# i# s3# of { (# s4#, e #) ->
 704             case writeArray# marr'# i# e s4# of { s5# ->
 705             copy (i# +# 1#) s5# }} in
 706     case copy 0# s2#                    of { s3# ->
 707     case unsafeFreezeArray# marr'# s3#  of { (# s4#, arr# #) ->
 708     (# s4#, Array l u n arr# #) }}}
 709
 710 {-# INLINE unsafeFreezeSTArray #-}
 711 unsafeFreezeSTArray :: Ix i => STArray s i e -> ST s (Array i e)
 712 unsafeFreezeSTArray (STArray l u n marr#) = ST $ \s1# ->
 713     case unsafeFreezeArray# marr# s1#   of { (# s2#, arr# #) ->
 714     (# s2#, Array l u n arr# #) }
 715
 716 thawSTArray :: Ix i => Array i e -> ST s (STArray s i e)
 717 thawSTArray (Array l u n@(I# n#) arr#) = ST $ \s1# ->
 718     case newArray# n# arrEleBottom s1#  of { (# s2#, marr# #) ->
 719     let copy i# s3# | i# ==# n# = s3#
 720                     | otherwise =
 721             case indexArray# arr# i#    of { (# e #) ->
 722             case writeArray# marr# i# e s3# of { s4# ->
 723             copy (i# +# 1#) s4# }} in
 724     case copy 0# s2#                    of { s3# ->
 725     (# s3#, STArray l u n marr# #) }}
 726
 727 {-# INLINE unsafeThawSTArray #-}
 728 unsafeThawSTArray :: Ix i => Array i e -> ST s (STArray s i e)
 729 unsafeThawSTArray (Array l u n arr#) = ST $ \s1# ->
 730     case unsafeThawArray# arr# s1#      of { (# s2#, marr# #) ->
 731     (# s2#, STArray l u n marr# #) }
 732 \end{code}