GHC/Arr.lhs

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