ghc/lib/std/PrelArr.lhs

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