ghc/lib/std/PrelArr.lhs

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