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 {-# INLINE array #-}
 314 array :: Ix i => (i,i) -> [(i, e)] -> Array i e
 315 array (l,u) ies = unsafeArray (l,u) [(index (l,u) i, e) | (i, e) <- ies]
 316
 317 {-# INLINE unsafeArray #-}
 318 unsafeArray :: Ix i => (i,i) -> [(Int, e)] -> Array i e
 319 unsafeArray (l,u) ies = runST (ST $ \s1# ->
 320     case rangeSize (l,u)                of { I# n# ->
 321     case newArray# n# arrEleBottom s1#  of { (# s2#, marr# #) ->
 322     foldr (fill marr#) (done l u marr#) ies s2# }})
 323
 324 {-# INLINE fill #-}
 325 fill :: MutableArray# s e -> (Int, e) -> STRep s a -> STRep s a
 326 fill marr# (I# i#, e) next s1# =
 327     case writeArray# marr# i# e s1#     of { s2# ->
 328     next s2# }
 329
 330 {-# INLINE done #-}
 331 done :: Ix i => i -> i -> MutableArray# s e -> STRep s (Array i e)
 332 done l u marr# s1# =
 333     case unsafeFreezeArray# marr# s1#   of { (# s2#, arr# #) ->
 334     (# s2#, Array l u arr# #) }
 335
 336 -- This is inefficient and I'm not sure why:
 337 -- listArray (l,u) es = unsafeArray (l,u) (zip [0 .. rangeSize (l,u) - 1] es)
 338 -- The code below is better. It still doesn't enable foldr/build
 339 -- transformation on the list of elements; I guess it's impossible
 340 -- using mechanisms currently available.
 341
 342 {-# INLINE listArray #-}
 343 listArray :: Ix i => (i,i) -> [e] -> Array i e
 344 listArray (l,u) es = runST (ST $ \s1# ->
 345     case rangeSize (l,u)                of { I# n# ->
 346     case newArray# n# arrEleBottom s1#  of { (# s2#, marr# #) ->
 347     let fillFromList i# xs s3# | i# ==# n# = s3#
 348                                | otherwise = case xs of
 349             []   -> s3#
 350             y:ys -> case writeArray# marr# i# y s3# of { s4# ->
 351                     fillFromList (i# +# 1#) ys s4# } in
 352     case fillFromList 0# es s2#         of { s3# ->
 353     done l u marr# s3# }}})
 354
 355 {-# INLINE (!) #-}
 356 (!) :: Ix i => Array i e -> i -> e
 357 arr@(Array l u _) ! i = unsafeAt arr (index (l,u) i)
 358
 359 {-# INLINE unsafeAt #-}
 360 unsafeAt :: Ix i => Array i e -> Int -> e
 361 unsafeAt (Array _ _ arr#) (I# i#) =
 362     case indexArray# arr# i# of (# e #) -> e
 363
 364 {-# INLINE bounds #-}
 365 bounds :: Ix i => Array i e -> (i,i)
 366 bounds (Array l u _) = (l,u)
 367
 368 {-# INLINE indices #-}
 369 indices :: Ix i => Array i e -> [i]
 370 indices (Array l u _) = range (l,u)
 371
 372 {-# INLINE elems #-}
 373 elems :: Ix i => Array i e -> [e]
 374 elems arr@(Array l u _) =
 375     [unsafeAt arr i | i <- [0 .. rangeSize (l,u) - 1]]
 376
 377 {-# INLINE assocs #-}
 378 assocs :: Ix i => Array i e -> [(i, e)]
 379 assocs arr@(Array l u _) =
 380     [(i, unsafeAt arr (unsafeIndex (l,u) i)) | i <- range (l,u)]
 381
 382 {-# INLINE accumArray #-}
 383 accumArray :: Ix i => (e -> a -> e) -> e -> (i,i) -> [(i, a)] -> Array i e
 384 accumArray f init (l,u) ies =
 385     unsafeAccumArray f init (l,u) [(index (l,u) i, e) | (i, e) <- ies]
 386
 387 {-# INLINE unsafeAccumArray #-}
 388 unsafeAccumArray :: Ix i => (e -> a -> e) -> e -> (i,i) -> [(Int, a)] -> Array i e
 389 unsafeAccumArray f init (l,u) ies = runST (ST $ \s1# ->
 390     case rangeSize (l,u)                of { I# n# ->
 391     case newArray# n# init s1#          of { (# s2#, marr# #) ->
 392     foldr (adjust f marr#) (done l u marr#) ies s2# }})
 393
 394 {-# INLINE adjust #-}
 395 adjust :: (e -> a -> e) -> MutableArray# s e -> (Int, a) -> STRep s b -> STRep s b
 396 adjust f marr# (I# i#, new) next s1# =
 397     case readArray# marr# i# s1#        of { (# s2#, old #) ->
 398     case writeArray# marr# i# (f old new) s2# of { s3# ->
 399     next s3# }}
 400
 401 {-# INLINE (//) #-}
 402 (//) :: Ix i => Array i e -> [(i, e)] -> Array i e
 403 arr@(Array l u _) // ies =
 404     unsafeReplace arr [(index (l,u) i, e) | (i, e) <- ies]
 405
 406 {-# INLINE unsafeReplace #-}
 407 unsafeReplace :: Ix i => Array i e -> [(Int, e)] -> Array i e
 408 unsafeReplace arr@(Array l u _) ies = runST (do
 409     STArray _ _ marr# <- thawSTArray arr
 410     ST (foldr (fill marr#) (done l u marr#) ies))
 411
 412 {-# INLINE accum #-}
 413 accum :: Ix i => (e -> a -> e) -> Array i e -> [(i, a)] -> Array i e
 414 accum f arr@(Array l u _) ies =
 415     unsafeAccum f arr [(index (l,u) i, e) | (i, e) <- ies]
 416
 417 {-# INLINE unsafeAccum #-}
 418 unsafeAccum :: Ix i => (e -> a -> e) -> Array i e -> [(Int, a)] -> Array i e
 419 unsafeAccum f arr@(Array l u _) ies = runST (do
 420     STArray _ _ marr# <- thawSTArray arr
 421     ST (foldr (adjust f marr#) (done l u marr#) ies))
 422
 423 {-# INLINE amap #-}
 424 amap :: Ix i => (a -> b) -> Array i a -> Array i b
 425 amap f arr@(Array l u _) =
 426     unsafeArray (l,u) [(i, f (unsafeAt arr i)) | i <- [0 .. rangeSize (l,u) - 1]]
 427
 428 {-# INLINE ixmap #-}
 429 ixmap :: (Ix i, Ix j) => (i,i) -> (i -> j) -> Array j e -> Array i e
 430 ixmap (l,u) f arr =
 431     unsafeArray (l,u) [(unsafeIndex (l,u) i, arr ! f i) | i <- range (l,u)]
 432
 433 {-# INLINE eqArray #-}
 434 eqArray :: (Ix i, Eq e) => Array i e -> Array i e -> Bool
 435 eqArray arr1@(Array l1 u1 _) arr2@(Array l2 u2 _) =
 436     if rangeSize (l1,u1) == 0 then rangeSize (l2,u2) == 0 else
 437     l1 == l2 && u1 == u2 &&
 438     and [unsafeAt arr1 i == unsafeAt arr2 i | i <- [0 .. rangeSize (l1,u1) - 1]]
 439
 440 {-# INLINE cmpArray #-}
 441 cmpArray :: (Ix i, Ord e) => Array i e -> Array i e -> Ordering
 442 cmpArray arr1 arr2 = compare (assocs arr1) (assocs arr2)
 443
 444 {-# INLINE cmpIntArray #-}
 445 cmpIntArray :: Ord e => Array Int e -> Array Int e -> Ordering
 446 cmpIntArray arr1@(Array l1 u1 _) arr2@(Array l2 u2 _) =
 447     if rangeSize (l1,u1) == 0 then if rangeSize (l2,u2) == 0 then EQ else LT else
 448     if rangeSize (l2,u2) == 0 then GT else
 449     case compare l1 l2 of
 450         EQ    -> foldr cmp (compare u1 u2) [0 .. rangeSize (l1, min u1 u2) - 1]
 451         other -> other
 452     where
 453     cmp i rest = case compare (unsafeAt arr1 i) (unsafeAt arr2 i) of
 454         EQ    -> rest
 455         other -> other
 456
 457 {-# RULES "cmpArray/Int" cmpArray = cmpIntArray #-}
 458 \end{code}
 459
 460
 461 %*********************************************************
 462 %*                                                      *
 463 \subsection{Array instances}
 464 %*                                                      *
 465 %*********************************************************
 466
 467 \begin{code}
 468 instance Ix i => Functor (Array i) where
 469     fmap = amap
 470
 471 instance (Ix i, Eq e) => Eq (Array i e) where
 472     (==) = eqArray
 473
 474 instance (Ix i, Ord e) => Ord (Array i e) where
 475     compare = cmpArray
 476
 477 instance (Ix a, Show a, Show b) => Show (Array a b) where
 478     showsPrec p a =
 479         showParen (p > appPrec) $
 480         showString "array " .
 481         showsPrec appPrec1 (bounds a) .
 482         showChar ' ' .
 483         showsPrec appPrec1 (assocs a)
 484         -- Precedence of 'array' is the precedence of application
 485
 486 -- The Read instance is in GHC.Read
 487 \end{code}
 488
 489
 490 %*********************************************************
 491 %*                                                      *
 492 \subsection{Operations on mutable arrays}
 493 %*                                                      *
 494 %*********************************************************
 495
 496 Idle ADR question: What's the tradeoff here between flattening these
 497 datatypes into @STArray ix ix (MutableArray# s elt)@ and using
 498 it as is?  As I see it, the former uses slightly less heap and
 499 provides faster access to the individual parts of the bounds while the
 500 code used has the benefit of providing a ready-made @(lo, hi)@ pair as
 501 required by many array-related functions.  Which wins? Is the
 502 difference significant (probably not).
 503
 504 Idle AJG answer: When I looked at the outputted code (though it was 2
 505 years ago) it seems like you often needed the tuple, and we build
 506 it frequently. Now we've got the overloading specialiser things
 507 might be different, though.
 508
 509 \begin{code}
 510 {-# INLINE newSTArray #-}
 511 newSTArray :: Ix i => (i,i) -> e -> ST s (STArray s i e)
 512 newSTArray (l,u) init = ST $ \s1# ->
 513     case rangeSize (l,u)                of { I# n# ->
 514     case newArray# n# init s1#          of { (# s2#, marr# #) ->
 515     (# s2#, STArray l u marr# #) }}
 516
 517 {-# INLINE boundsSTArray #-}
 518 boundsSTArray :: STArray s i e -> (i,i)
 519 boundsSTArray (STArray l u _) = (l,u)
 520
 521 {-# INLINE readSTArray #-}
 522 readSTArray :: Ix i => STArray s i e -> i -> ST s e
 523 readSTArray marr@(STArray l u _) i =
 524     unsafeReadSTArray marr (index (l,u) i)
 525
 526 {-# INLINE unsafeReadSTArray #-}
 527 unsafeReadSTArray :: Ix i => STArray s i e -> Int -> ST s e
 528 unsafeReadSTArray (STArray _ _ marr#) (I# i#) = ST $ \s1# ->
 529     readArray# marr# i# s1#
 530
 531 {-# INLINE writeSTArray #-}
 532 writeSTArray :: Ix i => STArray s i e -> i -> e -> ST s ()
 533 writeSTArray marr@(STArray l u _) i e =
 534     unsafeWriteSTArray marr (index (l,u) i) e
 535
 536 {-# INLINE unsafeWriteSTArray #-}
 537 unsafeWriteSTArray :: Ix i => STArray s i e -> Int -> e -> ST s ()
 538 unsafeWriteSTArray (STArray _ _ marr#) (I# i#) e = ST $ \s1# ->
 539     case writeArray# marr# i# e s1#     of { s2# ->
 540     (# s2#, () #) }
 541 \end{code}
 542
 543
 544 %*********************************************************
 545 %*                                                      *
 546 \subsection{Moving between mutable and immutable}
 547 %*                                                      *
 548 %*********************************************************
 549
 550 \begin{code}
 551 freezeSTArray :: Ix i => STArray s i e -> ST s (Array i e)
 552 freezeSTArray (STArray l u marr#) = ST $ \s1# ->
 553     case rangeSize (l,u)                of { I# n# ->
 554     case newArray# n# arrEleBottom s1#  of { (# s2#, marr'# #) ->
 555     let copy i# s3# | i# ==# n# = s3#
 556                     | otherwise =
 557             case readArray# marr# i# s3# of { (# s4#, e #) ->
 558             case writeArray# marr'# i# e s4# of { s5# ->
 559             copy (i# +# 1#) s5# }} in
 560     case copy 0# s2#                    of { s3# ->
 561     case unsafeFreezeArray# marr'# s3#  of { (# s4#, arr# #) ->
 562     (# s4#, Array l u arr# #) }}}}
 563
 564 {-# INLINE unsafeFreezeSTArray #-}
 565 unsafeFreezeSTArray :: Ix i => STArray s i e -> ST s (Array i e)
 566 unsafeFreezeSTArray (STArray l u marr#) = ST $ \s1# ->
 567     case unsafeFreezeArray# marr# s1#   of { (# s2#, arr# #) ->
 568     (# s2#, Array l u arr# #) }
 569
 570 thawSTArray :: Ix i => Array i e -> ST s (STArray s i e)
 571 thawSTArray (Array l u arr#) = ST $ \s1# ->
 572     case rangeSize (l,u)                of { I# n# ->
 573     case newArray# n# arrEleBottom s1#  of { (# s2#, marr# #) ->
 574     let copy i# s3# | i# ==# n# = s3#
 575                     | otherwise =
 576             case indexArray# arr# i#    of { (# e #) ->
 577             case writeArray# marr# i# e s3# of { s4# ->
 578             copy (i# +# 1#) s4# }} in
 579     case copy 0# s2#                    of { s3# ->
 580     (# s3#, STArray l u marr# #) }}}
 581
 582 {-# INLINE unsafeThawSTArray #-}
 583 unsafeThawSTArray :: Ix i => Array i e -> ST s (STArray s i e)
 584 unsafeThawSTArray (Array l u arr#) = ST $ \s1# ->
 585     case unsafeThawArray# arr# s1#      of { (# s2#, marr# #) ->
 586     (# s2#, STArray l u marr# #) }
 587 \end{code}