GHC/Arr.lhs

   1 \begin{code}
   2 {-# OPTIONS -fno-implicit-prelude #-}
   3 -----------------------------------------------------------------------------
   4 -- |
   5 -- Module      :  GHC.Arr
   6 -- Copyright   :  (c) The University of Glasgow, 1994-2000
   7 -- License     :  see libraries/base/LICENSE
   8 --
   9 -- Maintainer  :  cvs-ghc@haskell.org
  10 -- Stability   :  internal
  11 -- Portability :  non-portable (GHC extensions)
  12 --
  13 -- GHC\'s array implementation.
  14 --
  15 -----------------------------------------------------------------------------
  16
  17 module GHC.Arr where
  18
  19 import {-# SOURCE #-} GHC.Err ( error )
  20 import GHC.Enum
  21 import GHC.Num
  22 import GHC.ST
  23 import GHC.Base
  24 import GHC.List
  25 import GHC.Show
  26
  27 infixl 9  !, //
  28
  29 default ()
  30 \end{code}
  31
  32
  33 %*********************************************************
  34 %*                                                      *
  35 \subsection{The @Ix@ class}
  36 %*                                                      *
  37 %*********************************************************
  38
  39 \begin{code}
  40 class (Ord a) => Ix a where
  41     range               :: (a,a) -> [a]
  42     index, unsafeIndex  :: (a,a) -> a -> Int
  43     inRange             :: (a,a) -> a -> Bool
  44     rangeSize           :: (a,a) -> Int
  45     unsafeRangeSize     :: (a,a) -> Int
  46
  47         -- Must specify one of index, unsafeIndex
  48     index b i | inRange b i = unsafeIndex b i
  49               | otherwise   = error "Error in array index"
  50     unsafeIndex b i = index b i
  51
  52         -- As long as you don't override the default rangeSize,
  53         -- you can specify unsafeRangeSize as follows, to speed up
  54         -- some operations:
  55         --
  56         --    unsafeRangeSize b@(_l,h) = unsafeIndex b h + 1
  57         --
  58     rangeSize b@(_l,h) | inRange b h = unsafeIndex b h + 1
  59                        | otherwise   = 0
  60     unsafeRangeSize b = rangeSize b
  61 \end{code}
  62
  63 Note that the following is NOT right
  64         rangeSize (l,h) | l <= h    = index b h + 1
  65                         | otherwise = 0
  66
  67 Because it might be the case that l<h, but the range
  68 is nevertheless empty.  Consider
  69         ((1,2),(2,1))
  70 Here l<h, but the second index ranges from 2..1 and
  71 hence is empty
  72
  73 %*********************************************************
  74 %*                                                      *
  75 \subsection{Instances of @Ix@}
  76 %*                                                      *
  77 %*********************************************************
  78
  79 \begin{code}
  80 -- abstract these errors from the relevant index functions so that
  81 -- the guts of the function will be small enough to inline.
  82
  83 {-# NOINLINE indexError #-}
  84 indexError :: Show a => (a,a) -> a -> String -> b
  85 indexError rng i tp
  86   = error (showString "Ix{" . showString tp . showString "}.index: Index " .
  87            showParen True (showsPrec 0 i) .
  88            showString " out of range " $
  89            showParen True (showsPrec 0 rng) "")
  90
  91 ----------------------------------------------------------------------
  92 instance  Ix Char  where
  93     {-# INLINE range #-}
  94     range (m,n) = [m..n]
  95
  96     {-# INLINE unsafeIndex #-}
  97     unsafeIndex (m,_n) i = fromEnum i - fromEnum m
  98
  99     index b i | inRange b i =  unsafeIndex b i
 100               | otherwise   =  indexError b i "Char"
 101
 102     inRange (m,n) i     =  m <= i && i <= n
 103
 104     unsafeRangeSize b@(_l,h) = unsafeIndex b h + 1
 105
 106 ----------------------------------------------------------------------
 107 instance  Ix Int  where
 108     {-# INLINE range #-}
 109         -- The INLINE stops the build in the RHS from getting inlined,
 110         -- so that callers can fuse with the result of range
 111     range (m,n) = [m..n]
 112
 113     {-# INLINE unsafeIndex #-}
 114     unsafeIndex (m,_n) i = i - m
 115
 116     index b i | inRange b i =  unsafeIndex b i
 117               | otherwise   =  indexError b i "Int"
 118
 119     {-# INLINE inRange #-}
 120     inRange (I# m,I# n) (I# i) =  m <=# i && i <=# n
 121
 122     unsafeRangeSize b@(_l,h) = unsafeIndex b h + 1
 123
 124 ----------------------------------------------------------------------
 125 instance  Ix Integer  where
 126     {-# INLINE range #-}
 127     range (m,n) = [m..n]
 128
 129     {-# INLINE unsafeIndex #-}
 130     unsafeIndex (m,_n) i   = fromInteger (i - m)
 131
 132     index b i | inRange b i =  unsafeIndex b i
 133               | otherwise   =  indexError b i "Integer"
 134
 135     inRange (m,n) i     =  m <= i && i <= n
 136
 137     unsafeRangeSize b@(_l,h) = unsafeIndex b h + 1
 138
 139 ----------------------------------------------------------------------
 140 instance Ix Bool where -- as derived
 141     {-# INLINE range #-}
 142     range (m,n) = [m..n]
 143
 144     {-# INLINE unsafeIndex #-}
 145     unsafeIndex (l,_) i = fromEnum i - fromEnum l
 146
 147     index b i | inRange b i =  unsafeIndex b i
 148               | otherwise   =  indexError b i "Bool"
 149
 150     inRange (l,u) i = fromEnum i >= fromEnum l && fromEnum i <= fromEnum u
 151
 152     unsafeRangeSize b@(_l,h) = unsafeIndex b h + 1
 153
 154 ----------------------------------------------------------------------
 155 instance Ix Ordering where -- as derived
 156     {-# INLINE range #-}
 157     range (m,n) = [m..n]
 158
 159     {-# INLINE unsafeIndex #-}
 160     unsafeIndex (l,_) i = fromEnum i - fromEnum l
 161
 162     index b i | inRange b i =  unsafeIndex b i
 163               | otherwise   =  indexError b i "Ordering"
 164
 165     inRange (l,u) i = fromEnum i >= fromEnum l && fromEnum i <= fromEnum u
 166
 167     unsafeRangeSize b@(_l,h) = unsafeIndex b h + 1
 168
 169 ----------------------------------------------------------------------
 170 instance Ix () where
 171     {-# INLINE range #-}
 172     range   ((), ())    = [()]
 173     {-# INLINE unsafeIndex #-}
 174     unsafeIndex   ((), ()) () = 0
 175     {-# INLINE inRange #-}
 176     inRange ((), ()) () = True
 177     {-# INLINE index #-}
 178     index b i = unsafeIndex b i
 179
 180     unsafeRangeSize b@(_l,h) = unsafeIndex b h + 1
 181
 182 ----------------------------------------------------------------------
 183 instance (Ix a, Ix b) => Ix (a, b) where -- as derived
 184     {-# SPECIALISE instance Ix (Int,Int) #-}
 185
 186     {- INLINE range #-}
 187     range ((l1,l2),(u1,u2)) =
 188       [ (i1,i2) | i1 <- range (l1,u1), i2 <- range (l2,u2) ]
 189
 190     {- INLINE unsafeIndex #-}
 191     unsafeIndex ((l1,l2),(u1,u2)) (i1,i2) =
 192       unsafeIndex (l1,u1) i1 * unsafeRangeSize (l2,u2) + unsafeIndex (l2,u2) i2
 193
 194     {- INLINE inRange #-}
 195     inRange ((l1,l2),(u1,u2)) (i1,i2) =
 196       inRange (l1,u1) i1 && inRange (l2,u2) i2
 197
 198     unsafeRangeSize b@(_l,h) = unsafeIndex b h + 1
 199
 200     -- Default method for index
 201
 202 ----------------------------------------------------------------------
 203 instance  (Ix a1, Ix a2, Ix a3) => Ix (a1,a2,a3)  where
 204     {-# SPECIALISE instance Ix (Int,Int,Int) #-}
 205
 206     range ((l1,l2,l3),(u1,u2,u3)) =
 207         [(i1,i2,i3) | i1 <- range (l1,u1),
 208                       i2 <- range (l2,u2),
 209                       i3 <- range (l3,u3)]
 210
 211     unsafeIndex ((l1,l2,l3),(u1,u2,u3)) (i1,i2,i3) =
 212       unsafeIndex (l3,u3) i3 + unsafeRangeSize (l3,u3) * (
 213       unsafeIndex (l2,u2) i2 + unsafeRangeSize (l2,u2) * (
 214       unsafeIndex (l1,u1) i1))
 215
 216     inRange ((l1,l2,l3),(u1,u2,u3)) (i1,i2,i3) =
 217       inRange (l1,u1) i1 && inRange (l2,u2) i2 &&
 218       inRange (l3,u3) i3
 219
 220     unsafeRangeSize b@(_l,h) = unsafeIndex b h + 1
 221
 222     -- Default method for index
 223
 224 ----------------------------------------------------------------------
 225 instance  (Ix a1, Ix a2, Ix a3, Ix a4) => Ix (a1,a2,a3,a4)  where
 226     range ((l1,l2,l3,l4),(u1,u2,u3,u4)) =
 227       [(i1,i2,i3,i4) | i1 <- range (l1,u1),
 228                        i2 <- range (l2,u2),
 229                        i3 <- range (l3,u3),
 230                        i4 <- range (l4,u4)]
 231
 232     unsafeIndex ((l1,l2,l3,l4),(u1,u2,u3,u4)) (i1,i2,i3,i4) =
 233       unsafeIndex (l4,u4) i4 + unsafeRangeSize (l4,u4) * (
 234       unsafeIndex (l3,u3) i3 + unsafeRangeSize (l3,u3) * (
 235       unsafeIndex (l2,u2) i2 + unsafeRangeSize (l2,u2) * (
 236       unsafeIndex (l1,u1) i1)))
 237
 238     inRange ((l1,l2,l3,l4),(u1,u2,u3,u4)) (i1,i2,i3,i4) =
 239       inRange (l1,u1) i1 && inRange (l2,u2) i2 &&
 240       inRange (l3,u3) i3 && inRange (l4,u4) i4
 241
 242     unsafeRangeSize b@(_l,h) = unsafeIndex b h + 1
 243
 244     -- Default method for index
 245
 246 instance  (Ix a1, Ix a2, Ix a3, Ix a4, Ix a5) => Ix (a1,a2,a3,a4,a5)  where
 247     range ((l1,l2,l3,l4,l5),(u1,u2,u3,u4,u5)) =
 248       [(i1,i2,i3,i4,i5) | i1 <- range (l1,u1),
 249                           i2 <- range (l2,u2),
 250                           i3 <- range (l3,u3),
 251                           i4 <- range (l4,u4),
 252                           i5 <- range (l5,u5)]
 253
 254     unsafeIndex ((l1,l2,l3,l4,l5),(u1,u2,u3,u4,u5)) (i1,i2,i3,i4,i5) =
 255       unsafeIndex (l5,u5) i5 + unsafeRangeSize (l5,u5) * (
 256       unsafeIndex (l4,u4) i4 + unsafeRangeSize (l4,u4) * (
 257       unsafeIndex (l3,u3) i3 + unsafeRangeSize (l3,u3) * (
 258       unsafeIndex (l2,u2) i2 + unsafeRangeSize (l2,u2) * (
 259       unsafeIndex (l1,u1) i1))))
 260
 261     inRange ((l1,l2,l3,l4,l5),(u1,u2,u3,u4,u5)) (i1,i2,i3,i4,i5) =
 262       inRange (l1,u1) i1 && inRange (l2,u2) i2 &&
 263       inRange (l3,u3) i3 && inRange (l4,u4) i4 &&
 264       inRange (l5,u5) i5
 265
 266     unsafeRangeSize b@(_l,h) = unsafeIndex b h + 1
 267
 268     -- Default method for index
 269 \end{code}
 270
 271 %*********************************************************
 272 %*                                                      *
 273 \subsection{The @Array@ types}
 274 %*                                                      *
 275 %*********************************************************
 276
 277 \begin{code}
 278 type IPr = (Int, Int)
 279
 280 data Ix i => Array     i e = Array   !i !i (Array# e)
 281
 282 -- | Mutable, boxed, non-strict arrays in the 'ST' monad.  The type
 283 -- arguments are as follows:
 284 --
 285 --  * @s@: the state variable argument for the 'ST' type
 286 --
 287 --  * @i@: the index type of the array (should be an instance of 'Ix')
 288 --
 289 --  * @e@: the element type of the array.
 290 --
 291 data         STArray s i e = STArray !i !i (MutableArray# s e)
 292         -- No Ix context for STArray.  They are stupid,
 293         -- and force an Ix context on the equality instance.
 294
 295 -- Just pointer equality on mutable arrays:
 296 instance Eq (STArray s i e) where
 297     STArray _ _ arr1# == STArray _ _ arr2# =
 298         sameMutableArray# arr1# arr2#
 299 \end{code}
 300
 301
 302 %*********************************************************
 303 %*                                                      *
 304 \subsection{Operations on immutable arrays}
 305 %*                                                      *
 306 %*********************************************************
 307
 308 \begin{code}
 309 {-# NOINLINE arrEleBottom #-}
 310 arrEleBottom :: a
 311 arrEleBottom = error "(Array.!): undefined array element"
 312
 313 -- | Note: GHC's implementation of @array@ differs slightly from the Haskell 98
 314 -- report.  If the same index appears twice, GHC's implementation takes the
 315 -- value from last (index,value) pair in the list, rather than yielding bottom
 316 -- for that array slot.
 317 {-# INLINE array #-}
 318 array :: Ix i => (i,i) -> [(i, e)] -> Array i e
 319 array (l,u) ies = unsafeArray (l,u) [(index (l,u) i, e) | (i, e) <- ies]
 320
 321 {-# INLINE unsafeArray #-}
 322 unsafeArray :: Ix i => (i,i) -> [(Int, e)] -> Array i e
 323 unsafeArray (l,u) ies = runST (ST $ \s1# ->
 324     case rangeSize (l,u)                of { I# n# ->
 325     case newArray# n# arrEleBottom s1#  of { (# s2#, marr# #) ->
 326     foldr (fill marr#) (done l u marr#) ies s2# }})
 327
 328 {-# INLINE fill #-}
 329 fill :: MutableArray# s e -> (Int, e) -> STRep s a -> STRep s a
 330 fill marr# (I# i#, e) next s1# =
 331     case writeArray# marr# i# e s1#     of { s2# ->
 332     next s2# }
 333
 334 {-# INLINE done #-}
 335 done :: Ix i => i -> i -> MutableArray# s e -> STRep s (Array i e)
 336 done l u marr# s1# =
 337     case unsafeFreezeArray# marr# s1#   of { (# s2#, arr# #) ->
 338     (# s2#, Array l u arr# #) }
 339
 340 -- This is inefficient and I'm not sure why:
 341 -- listArray (l,u) es = unsafeArray (l,u) (zip [0 .. rangeSize (l,u) - 1] es)
 342 -- The code below is better. It still doesn't enable foldr/build
 343 -- transformation on the list of elements; I guess it's impossible
 344 -- using mechanisms currently available.
 345
 346 {-# INLINE listArray #-}
 347 listArray :: Ix i => (i,i) -> [e] -> Array i e
 348 listArray (l,u) es = runST (ST $ \s1# ->
 349     case rangeSize (l,u)                of { I# n# ->
 350     case newArray# n# arrEleBottom s1#  of { (# s2#, marr# #) ->
 351     let fillFromList i# xs s3# | i# ==# n# = s3#
 352                                | otherwise = case xs of
 353             []   -> s3#
 354             y:ys -> case writeArray# marr# i# y s3# of { s4# ->
 355                     fillFromList (i# +# 1#) ys s4# } in
 356     case fillFromList 0# es s2#         of { s3# ->
 357     done l u marr# s3# }}})
 358
 359 {-# INLINE (!) #-}
 360 (!) :: Ix i => Array i e -> i -> e
 361 arr@(Array l u _) ! i = unsafeAt arr (index (l,u) i)
 362
 363 {-# INLINE unsafeAt #-}
 364 unsafeAt :: Ix i => Array i e -> Int -> e
 365 unsafeAt (Array _ _ arr#) (I# i#) =
 366     case indexArray# arr# i# of (# e #) -> e
 367
 368 {-# INLINE bounds #-}
 369 bounds :: Ix i => Array i e -> (i,i)
 370 bounds (Array l u _) = (l,u)
 371
 372 {-# INLINE indices #-}
 373 indices :: Ix i => Array i e -> [i]
 374 indices (Array l u _) = range (l,u)
 375
 376 {-# INLINE elems #-}
 377 elems :: Ix i => Array i e -> [e]
 378 elems arr@(Array l u _) =
 379     [unsafeAt arr i | i <- [0 .. rangeSize (l,u) - 1]]
 380
 381 {-# INLINE assocs #-}
 382 assocs :: Ix i => Array i e -> [(i, e)]
 383 assocs arr@(Array l u _) =
 384     [(i, unsafeAt arr (unsafeIndex (l,u) i)) | i <- range (l,u)]
 385
 386 {-# INLINE accumArray #-}
 387 accumArray :: Ix i => (e -> a -> e) -> e -> (i,i) -> [(i, a)] -> Array i e
 388 accumArray f init (l,u) ies =
 389     unsafeAccumArray f init (l,u) [(index (l,u) i, e) | (i, e) <- ies]
 390
 391 {-# INLINE unsafeAccumArray #-}
 392 unsafeAccumArray :: Ix i => (e -> a -> e) -> e -> (i,i) -> [(Int, a)] -> Array i e
 393 unsafeAccumArray f init (l,u) ies = runST (ST $ \s1# ->
 394     case rangeSize (l,u)                of { I# n# ->
 395     case newArray# n# init s1#          of { (# s2#, marr# #) ->
 396     foldr (adjust f marr#) (done l u marr#) ies s2# }})
 397
 398 {-# INLINE adjust #-}
 399 adjust :: (e -> a -> e) -> MutableArray# s e -> (Int, a) -> STRep s b -> STRep s b
 400 adjust f marr# (I# i#, new) next s1# =
 401     case readArray# marr# i# s1#        of { (# s2#, old #) ->
 402     case writeArray# marr# i# (f old new) s2# of { s3# ->
 403     next s3# }}
 404
 405 {-# INLINE (//) #-}
 406 (//) :: Ix i => Array i e -> [(i, e)] -> Array i e
 407 arr@(Array l u _) // ies =
 408     unsafeReplace arr [(index (l,u) i, e) | (i, e) <- ies]
 409
 410 {-# INLINE unsafeReplace #-}
 411 unsafeReplace :: Ix i => Array i e -> [(Int, e)] -> Array i e
 412 unsafeReplace arr@(Array l u _) ies = runST (do
 413     STArray _ _ marr# <- thawSTArray arr
 414     ST (foldr (fill marr#) (done l u marr#) ies))
 415
 416 {-# INLINE accum #-}
 417 accum :: Ix i => (e -> a -> e) -> Array i e -> [(i, a)] -> Array i e
 418 accum f arr@(Array l u _) ies =
 419     unsafeAccum f arr [(index (l,u) i, e) | (i, e) <- ies]
 420
 421 {-# INLINE unsafeAccum #-}
 422 unsafeAccum :: Ix i => (e -> a -> e) -> Array i e -> [(Int, a)] -> Array i e
 423 unsafeAccum f arr@(Array l u _) ies = runST (do
 424     STArray _ _ marr# <- thawSTArray arr
 425     ST (foldr (adjust f marr#) (done l u marr#) ies))
 426
 427 {-# INLINE amap #-}
 428 amap :: Ix i => (a -> b) -> Array i a -> Array i b
 429 amap f arr@(Array l u _) =
 430     unsafeArray (l,u) [(i, f (unsafeAt arr i)) | i <- [0 .. rangeSize (l,u) - 1]]
 431
 432 {-# INLINE ixmap #-}
 433 ixmap :: (Ix i, Ix j) => (i,i) -> (i -> j) -> Array j e -> Array i e
 434 ixmap (l,u) f arr =
 435     unsafeArray (l,u) [(unsafeIndex (l,u) i, arr ! f i) | i <- range (l,u)]
 436
 437 {-# INLINE eqArray #-}
 438 eqArray :: (Ix i, Eq e) => Array i e -> Array i e -> Bool
 439 eqArray arr1@(Array l1 u1 _) arr2@(Array l2 u2 _) =
 440     if rangeSize (l1,u1) == 0 then rangeSize (l2,u2) == 0 else
 441     l1 == l2 && u1 == u2 &&
 442     and [unsafeAt arr1 i == unsafeAt arr2 i | i <- [0 .. rangeSize (l1,u1) - 1]]
 443
 444 {-# INLINE cmpArray #-}
 445 cmpArray :: (Ix i, Ord e) => Array i e -> Array i e -> Ordering
 446 cmpArray arr1 arr2 = compare (assocs arr1) (assocs arr2)
 447
 448 {-# INLINE cmpIntArray #-}
 449 cmpIntArray :: Ord e => Array Int e -> Array Int e -> Ordering
 450 cmpIntArray arr1@(Array l1 u1 _) arr2@(Array l2 u2 _) =
 451     if rangeSize (l1,u1) == 0 then if rangeSize (l2,u2) == 0 then EQ else LT else
 452     if rangeSize (l2,u2) == 0 then GT else
 453     case compare l1 l2 of
 454         EQ    -> foldr cmp (compare u1 u2) [0 .. rangeSize (l1, min u1 u2) - 1]
 455         other -> other
 456     where
 457     cmp i rest = case compare (unsafeAt arr1 i) (unsafeAt arr2 i) of
 458         EQ    -> rest
 459         other -> other
 460
 461 {-# RULES "cmpArray/Int" cmpArray = cmpIntArray #-}
 462 \end{code}
 463
 464
 465 %*********************************************************
 466 %*                                                      *
 467 \subsection{Array instances}
 468 %*                                                      *
 469 %*********************************************************
 470
 471 \begin{code}
 472 instance Ix i => Functor (Array i) where
 473     fmap = amap
 474
 475 instance (Ix i, Eq e) => Eq (Array i e) where
 476     (==) = eqArray
 477
 478 instance (Ix i, Ord e) => Ord (Array i e) where
 479     compare = cmpArray
 480
 481 instance (Ix a, Show a, Show b) => Show (Array a b) where
 482     showsPrec p a =
 483         showParen (p > appPrec) $
 484         showString "array " .
 485         showsPrec appPrec1 (bounds a) .
 486         showChar ' ' .
 487         showsPrec appPrec1 (assocs a)
 488         -- Precedence of 'array' is the precedence of application
 489
 490 -- The Read instance is in GHC.Read
 491 \end{code}
 492
 493
 494 %*********************************************************
 495 %*                                                      *
 496 \subsection{Operations on mutable arrays}
 497 %*                                                      *
 498 %*********************************************************
 499
 500 Idle ADR question: What's the tradeoff here between flattening these
 501 datatypes into @STArray ix ix (MutableArray# s elt)@ and using
 502 it as is?  As I see it, the former uses slightly less heap and
 503 provides faster access to the individual parts of the bounds while the
 504 code used has the benefit of providing a ready-made @(lo, hi)@ pair as
 505 required by many array-related functions.  Which wins? Is the
 506 difference significant (probably not).
 507
 508 Idle AJG answer: When I looked at the outputted code (though it was 2
 509 years ago) it seems like you often needed the tuple, and we build
 510 it frequently. Now we've got the overloading specialiser things
 511 might be different, though.
 512
 513 \begin{code}
 514 {-# INLINE newSTArray #-}
 515 newSTArray :: Ix i => (i,i) -> e -> ST s (STArray s i e)
 516 newSTArray (l,u) init = ST $ \s1# ->
 517     case rangeSize (l,u)                of { I# n# ->
 518     case newArray# n# init s1#          of { (# s2#, marr# #) ->
 519     (# s2#, STArray l u marr# #) }}
 520
 521 {-# INLINE boundsSTArray #-}
 522 boundsSTArray :: STArray s i e -> (i,i)
 523 boundsSTArray (STArray l u _) = (l,u)
 524
 525 {-# INLINE readSTArray #-}
 526 readSTArray :: Ix i => STArray s i e -> i -> ST s e
 527 readSTArray marr@(STArray l u _) i =
 528     unsafeReadSTArray marr (index (l,u) i)
 529
 530 {-# INLINE unsafeReadSTArray #-}
 531 unsafeReadSTArray :: Ix i => STArray s i e -> Int -> ST s e
 532 unsafeReadSTArray (STArray _ _ marr#) (I# i#) = ST $ \s1# ->
 533     readArray# marr# i# s1#
 534
 535 {-# INLINE writeSTArray #-}
 536 writeSTArray :: Ix i => STArray s i e -> i -> e -> ST s ()
 537 writeSTArray marr@(STArray l u _) i e =
 538     unsafeWriteSTArray marr (index (l,u) i) e
 539
 540 {-# INLINE unsafeWriteSTArray #-}
 541 unsafeWriteSTArray :: Ix i => STArray s i e -> Int -> e -> ST s ()
 542 unsafeWriteSTArray (STArray _ _ marr#) (I# i#) e = ST $ \s1# ->
 543     case writeArray# marr# i# e s1#     of { s2# ->
 544     (# s2#, () #) }
 545 \end{code}
 546
 547
 548 %*********************************************************
 549 %*                                                      *
 550 \subsection{Moving between mutable and immutable}
 551 %*                                                      *
 552 %*********************************************************
 553
 554 \begin{code}
 555 freezeSTArray :: Ix i => STArray s i e -> ST s (Array i e)
 556 freezeSTArray (STArray l u marr#) = ST $ \s1# ->
 557     case rangeSize (l,u)                of { I# n# ->
 558     case newArray# n# arrEleBottom s1#  of { (# s2#, marr'# #) ->
 559     let copy i# s3# | i# ==# n# = s3#
 560                     | otherwise =
 561             case readArray# marr# i# s3# of { (# s4#, e #) ->
 562             case writeArray# marr'# i# e s4# of { s5# ->
 563             copy (i# +# 1#) s5# }} in
 564     case copy 0# s2#                    of { s3# ->
 565     case unsafeFreezeArray# marr'# s3#  of { (# s4#, arr# #) ->
 566     (# s4#, Array l u arr# #) }}}}
 567
 568 {-# INLINE unsafeFreezeSTArray #-}
 569 unsafeFreezeSTArray :: Ix i => STArray s i e -> ST s (Array i e)
 570 unsafeFreezeSTArray (STArray l u marr#) = ST $ \s1# ->
 571     case unsafeFreezeArray# marr# s1#   of { (# s2#, arr# #) ->
 572     (# s2#, Array l u arr# #) }
 573
 574 thawSTArray :: Ix i => Array i e -> ST s (STArray s i e)
 575 thawSTArray (Array l u arr#) = ST $ \s1# ->
 576     case rangeSize (l,u)                of { I# n# ->
 577     case newArray# n# arrEleBottom s1#  of { (# s2#, marr# #) ->
 578     let copy i# s3# | i# ==# n# = s3#
 579                     | otherwise =
 580             case indexArray# arr# i#    of { (# e #) ->
 581             case writeArray# marr# i# e s3# of { s4# ->
 582             copy (i# +# 1#) s4# }} in
 583     case copy 0# s2#                    of { s3# ->
 584     (# s3#, STArray l u marr# #) }}}
 585
 586 {-# INLINE unsafeThawSTArray #-}
 587 unsafeThawSTArray :: Ix i => Array i e -> ST s (STArray s i e)
 588 unsafeThawSTArray (Array l u arr#) = ST $ \s1# ->
 589     case unsafeThawArray# arr# s1#      of { (# s2#, marr# #) ->
 590     (# s2#, STArray l u marr# #) }
 591 \end{code}