Data/Array/Base.hs

   1 -----------------------------------------------------------------------------
   2 -- |
   3 -- Module      :  Data.Array.Base
   4 -- Copyright   :  (c) The University of Glasgow 2001
   5 -- License     :  BSD-style (see the file libraries/base/LICENSE)
   6 --
   7 -- Maintainer  :  libraries@haskell.org
   8 -- Stability   :  experimental
   9 -- Portability :  non-portable
  10 --
  11 -- Basis for IArray and MArray.  Not intended for external consumption;
  12 -- use IArray or MArray instead.
  13 --
  14 -----------------------------------------------------------------------------
  15
  16 -- #hide
  17 module Data.Array.Base where
  18
  19 import Prelude
  20
  21 import Data.Ix          ( Ix, range, index, rangeSize )
  22
  23 #ifdef __GLASGOW_HASKELL__
  24 import GHC.Arr          ( STArray, unsafeIndex )
  25 import qualified GHC.Arr as Arr
  26 import qualified GHC.Arr as ArrST
  27 import GHC.ST           ( ST(..), runST )
  28 import GHC.Base
  29 import GHC.Word         ( Word(..) )
  30 import GHC.Ptr          ( Ptr(..), FunPtr(..), nullPtr, nullFunPtr )
  31 import GHC.Float        ( Float(..), Double(..) )
  32 import GHC.Stable       ( StablePtr(..) )
  33 import GHC.Int          ( Int8(..),  Int16(..),  Int32(..),  Int64(..) )
  34 import GHC.Word         ( Word8(..), Word16(..), Word32(..), Word64(..) )
  35 #endif
  36
  37 #ifdef __HUGS__
  38 import qualified Hugs.Array as Arr
  39 import qualified Hugs.ST as ArrST
  40 import Hugs.Array ( unsafeIndex )
  41 import Hugs.ST ( STArray, ST(..), runST )
  42 #endif
  43
  44 import Data.Dynamic
  45 #include "Dynamic.h"
  46
  47 #include "MachDeps.h"
  48
  49 -----------------------------------------------------------------------------
  50 -- Class of immutable arrays
  51
  52 -- | Class of array types with bounds
  53 class HasBounds a where
  54     -- | Extracts the bounds of an array
  55     bounds :: Ix i => a i e -> (i,i)
  56
  57 {- | Class of immutable array types.
  58
  59 An array type has the form @(a i e)@ where @a@ is the array type
  60 constructor (kind @* -> * -> *@), @i@ is the index type (a member of
  61 the class 'Ix'), and @e@ is the element type.  The @IArray@ class is
  62 parameterised over both @a@ and @e@, so that instances specialised to
  63 certain element types can be defined.
  64 -}
  65 class HasBounds a => IArray a e where
  66     unsafeArray      :: Ix i => (i,i) -> [(Int, e)] -> a i e
  67     unsafeAt         :: Ix i => a i e -> Int -> e
  68     unsafeReplace    :: Ix i => a i e -> [(Int, e)] -> a i e
  69     unsafeAccum      :: Ix i => (e -> e' -> e) -> a i e -> [(Int, e')] -> a i e
  70     unsafeAccumArray :: Ix i => (e -> e' -> e) -> e -> (i,i) -> [(Int, e')] -> a i e
  71
  72     unsafeReplace arr ies = runST (unsafeReplaceST arr ies >>= unsafeFreeze)
  73     unsafeAccum f arr ies = runST (unsafeAccumST f arr ies >>= unsafeFreeze)
  74     unsafeAccumArray f e lu ies = runST (unsafeAccumArrayST f e lu ies >>= unsafeFreeze)
  75
  76 {-# INLINE unsafeReplaceST #-}
  77 unsafeReplaceST :: (IArray a e, Ix i) => a i e -> [(Int, e)] -> ST s (STArray s i e)
  78 unsafeReplaceST arr ies = do
  79     marr <- thaw arr
  80     sequence_ [unsafeWrite marr i e | (i, e) <- ies]
  81     return marr
  82
  83 {-# INLINE unsafeAccumST #-}
  84 unsafeAccumST :: (IArray a e, Ix i) => (e -> e' -> e) -> a i e -> [(Int, e')] -> ST s (STArray s i e)
  85 unsafeAccumST f arr ies = do
  86     marr <- thaw arr
  87     sequence_ [do
  88         old <- unsafeRead marr i
  89         unsafeWrite marr i (f old new)
  90         | (i, new) <- ies]
  91     return marr
  92
  93 {-# INLINE unsafeAccumArrayST #-}
  94 unsafeAccumArrayST :: Ix i => (e -> e' -> e) -> e -> (i,i) -> [(Int, e')] -> ST s (STArray s i e)
  95 unsafeAccumArrayST f e (l,u) ies = do
  96     marr <- newArray (l,u) e
  97     sequence_ [do
  98         old <- unsafeRead marr i
  99         unsafeWrite marr i (f old new)
 100         | (i, new) <- ies]
 101     return marr
 102
 103
 104 {-# INLINE array #-}
 105
 106 {-| Constructs an immutable array from a pair of bounds and a list of
 107 initial associations.
 108
 109 The bounds are specified as a pair of the lowest and highest bounds in
 110 the array respectively.  For example, a one-origin vector of length 10
 111 has bounds (1,10), and a one-origin 10 by 10 matrix has bounds
 112 ((1,1),(10,10)).
 113
 114 An association is a pair of the form @(i,x)@, which defines the value
 115 of the array at index @i@ to be @x@.  The array is undefined if any
 116 index in the list is out of bounds.  If any two associations in the
 117 list have the same index, the value at that index is undefined.
 118
 119 Because the indices must be checked for these errors, 'array' is
 120 strict in the bounds argument and in the indices of the association
 121 list.  Whether @array@ is strict or non-strict in the elements depends
 122 on the array type: 'Data.Array.Array' is a non-strict array type, but
 123 all of the 'Data.Array.Unboxed.UArray' arrays are strict.  Thus in a
 124 non-strict array, recurrences such as the following are possible:
 125
 126 > a = array (1,100) ((1,1) : [(i, i * a!(i-1)) | i \<- [2..100]])
 127
 128 Not every index within the bounds of the array need appear in the
 129 association list, but the values associated with indices that do not
 130 appear will be undefined.
 131
 132 If, in any dimension, the lower bound is greater than the upper bound,
 133 then the array is legal, but empty. Indexing an empty array always
 134 gives an array-bounds error, but 'bounds' still yields the bounds with
 135 which the array was constructed.
 136 -}
 137 array   :: (IArray a e, Ix i)
 138         => (i,i)        -- ^ bounds of the array: (lowest,highest)
 139         -> [(i, e)]     -- ^ list of associations
 140         -> a i e
 141 array (l,u) ies = unsafeArray (l,u) [(index (l,u) i, e) | (i, e) <- ies]
 142
 143 -- Since unsafeFreeze is not guaranteed to be only a cast, we will
 144 -- use unsafeArray and zip instead of a specialized loop to implement
 145 -- listArray, unlike Array.listArray, even though it generates some
 146 -- unnecessary heap allocation. Will use the loop only when we have
 147 -- fast unsafeFreeze, namely for Array and UArray (well, they cover
 148 -- almost all cases).
 149
 150 {-# INLINE listArray #-}
 151
 152 -- | Constructs an immutable array from a list of initial elements.
 153 -- The list gives the elements of the array in ascending order
 154 -- beginning with the lowest index.
 155 listArray :: (IArray a e, Ix i) => (i,i) -> [e] -> a i e
 156 listArray (l,u) es = unsafeArray (l,u) (zip [0 .. rangeSize (l,u) - 1] es)
 157
 158 {-# INLINE listArrayST #-}
 159 listArrayST :: Ix i => (i,i) -> [e] -> ST s (STArray s i e)
 160 listArrayST (l,u) es = do
 161     marr <- newArray_ (l,u)
 162     let n = rangeSize (l,u)
 163     let fillFromList i xs | i == n    = return ()
 164                           | otherwise = case xs of
 165             []   -> return ()
 166             y:ys -> unsafeWrite marr i y >> fillFromList (i+1) ys
 167     fillFromList 0 es
 168     return marr
 169
 170 {-# RULES
 171 "listArray/Array" listArray =
 172     \lu es -> runST (listArrayST lu es >>= ArrST.unsafeFreezeSTArray)
 173     #-}
 174
 175 #ifdef __GLASGOW_HASKELL__
 176 {-# INLINE listUArrayST #-}
 177 listUArrayST :: (MArray (STUArray s) e (ST s), Ix i)
 178              => (i,i) -> [e] -> ST s (STUArray s i e)
 179 listUArrayST (l,u) es = do
 180     marr <- newArray_ (l,u)
 181     let n = rangeSize (l,u)
 182     let fillFromList i xs | i == n    = return ()
 183                           | otherwise = case xs of
 184             []   -> return ()
 185             y:ys -> unsafeWrite marr i y >> fillFromList (i+1) ys
 186     fillFromList 0 es
 187     return marr
 188
 189 -- I don't know how to write a single rule for listUArrayST, because
 190 -- the type looks like constrained over 's', which runST doesn't
 191 -- like. In fact all MArray (STUArray s) instances are polymorphic
 192 -- wrt. 's', but runST can't know that.
 193
 194 -- I would like to write a rule for listUArrayST (or listArray or
 195 -- whatever) applied to unpackCString#. Unfortunately unpackCString#
 196 -- calls seem to be floated out, then floated back into the middle
 197 -- of listUArrayST, so I was not able to do this.
 198
 199 {-# RULES
 200 "listArray/UArray/Bool"      listArray = \lu (es :: [Bool])        ->
 201     runST (listUArrayST lu es >>= unsafeFreezeSTUArray)
 202 "listArray/UArray/Char"      listArray = \lu (es :: [Char])        ->
 203     runST (listUArrayST lu es >>= unsafeFreezeSTUArray)
 204 "listArray/UArray/Int"       listArray = \lu (es :: [Int])         ->
 205     runST (listUArrayST lu es >>= unsafeFreezeSTUArray)
 206 "listArray/UArray/Word"      listArray = \lu (es :: [Word])        ->
 207     runST (listUArrayST lu es >>= unsafeFreezeSTUArray)
 208 "listArray/UArray/Ptr"       listArray = \lu (es :: [Ptr a])       ->
 209     runST (listUArrayST lu es >>= unsafeFreezeSTUArray)
 210 "listArray/UArray/FunPtr"    listArray = \lu (es :: [FunPtr a])    ->
 211     runST (listUArrayST lu es >>= unsafeFreezeSTUArray)
 212 "listArray/UArray/Float"     listArray = \lu (es :: [Float])       ->
 213     runST (listUArrayST lu es >>= unsafeFreezeSTUArray)
 214 "listArray/UArray/Double"    listArray = \lu (es :: [Double])      ->
 215     runST (listUArrayST lu es >>= unsafeFreezeSTUArray)
 216 "listArray/UArray/StablePtr" listArray = \lu (es :: [StablePtr a]) ->
 217     runST (listUArrayST lu es >>= unsafeFreezeSTUArray)
 218 "listArray/UArray/Int8"      listArray = \lu (es :: [Int8])        ->
 219     runST (listUArrayST lu es >>= unsafeFreezeSTUArray)
 220 "listArray/UArray/Int16"     listArray = \lu (es :: [Int16])       ->
 221     runST (listUArrayST lu es >>= unsafeFreezeSTUArray)
 222 "listArray/UArray/Int32"     listArray = \lu (es :: [Int32])       ->
 223     runST (listUArrayST lu es >>= unsafeFreezeSTUArray)
 224 "listArray/UArray/Int64"     listArray = \lu (es :: [Int64])       ->
 225     runST (listUArrayST lu es >>= unsafeFreezeSTUArray)
 226 "listArray/UArray/Word8"     listArray = \lu (es :: [Word8])       ->
 227     runST (listUArrayST lu es >>= unsafeFreezeSTUArray)
 228 "listArray/UArray/Word16"    listArray = \lu (es :: [Word16])      ->
 229     runST (listUArrayST lu es >>= unsafeFreezeSTUArray)
 230 "listArray/UArray/Word32"    listArray = \lu (es :: [Word32])      ->
 231     runST (listUArrayST lu es >>= unsafeFreezeSTUArray)
 232 "listArray/UArray/Word64"    listArray = \lu (es :: [Word64])      ->
 233     runST (listUArrayST lu es >>= unsafeFreezeSTUArray)
 234     #-}
 235 #endif /* __GLASGOW_HASKELL__ */
 236
 237 {-# INLINE (!) #-}
 238 -- | Returns the element of an immutable array at the specified index.
 239 (!) :: (IArray a e, Ix i) => a i e -> i -> e
 240 arr ! i = case bounds arr of (l,u) -> unsafeAt arr (index (l,u) i)
 241
 242 {-# INLINE indices #-}
 243 -- | Returns a list of all the valid indices in an array.
 244 indices :: (HasBounds a, Ix i) => a i e -> [i]
 245 indices arr = case bounds arr of (l,u) -> range (l,u)
 246
 247 {-# INLINE elems #-}
 248 -- | Returns a list of all the elements of an array, in the same order
 249 -- as their indices.
 250 elems :: (IArray a e, Ix i) => a i e -> [e]
 251 elems arr = case bounds arr of
 252     (l,u) -> [unsafeAt arr i | i <- [0 .. rangeSize (l,u) - 1]]
 253
 254 {-# INLINE assocs #-}
 255 -- | Returns the contents of an array as a list of associations.
 256 assocs :: (IArray a e, Ix i) => a i e -> [(i, e)]
 257 assocs arr = case bounds arr of
 258     (l,u) -> [(i, unsafeAt arr (unsafeIndex (l,u) i)) | i <- range (l,u)]
 259
 260 {-# INLINE accumArray #-}
 261
 262 {-|
 263 Constructs an immutable array from a list of associations.  Unlike
 264 'array', the same index is allowed to occur multiple times in the list
 265 of associations; an /accumulating function/ is used to combine the
 266 values of elements with the same index.
 267
 268 For example, given a list of values of some index type, hist produces
 269 a histogram of the number of occurrences of each index within a
 270 specified range:
 271
 272 > hist :: (Ix a, Num b) => (a,a) -> [a] -> Array a b
 273 > hist bnds is = accumArray (+) 0 bnds [(i, 1) | i\<-is, inRange bnds i]
 274 -}
 275 accumArray :: (IArray a e, Ix i)
 276         => (e -> e' -> e)       -- ^ An accumulating function
 277         -> e                    -- ^ A default element
 278         -> (i,i)                -- ^ The bounds of the array
 279         -> [(i, e')]            -- ^ List of associations
 280         -> a i e                -- ^ Returns: the array
 281 accumArray f init (l,u) ies =
 282     unsafeAccumArray f init (l,u) [(index (l,u) i, e) | (i, e) <- ies]
 283
 284 {-# INLINE (//) #-}
 285 {-|
 286 Takes an array and a list of pairs and returns an array identical to
 287 the left argument except that it has been updated by the associations
 288 in the right argument. (As with the array function, the indices in the
 289 association list must be unique for the updated elements to be
 290 defined.) For example, if m is a 1-origin, n by n matrix, then
 291 @m\/\/[((i,i), 0) | i \<- [1..n]]@ is the same matrix, except with the
 292 diagonal zeroed.
 293
 294 For most array types, this operation is O(/n/) where /n/ is the size
 295 of the array.  However, the 'Data.Array.Diff.DiffArray' type provides
 296 this operation with complexity linear in the number of updates.
 297 -}
 298 (//) :: (IArray a e, Ix i) => a i e -> [(i, e)] -> a i e
 299 arr // ies = case bounds arr of
 300     (l,u) -> unsafeReplace arr [(index (l,u) i, e) | (i, e) <- ies]
 301
 302 {-# INLINE accum #-}
 303 {-|
 304 @accum f@ takes an array and an association list and accumulates pairs
 305 from the list into the array with the accumulating function @f@. Thus
 306 'accumArray' can be defined using 'accum':
 307
 308 > accumArray f z b = accum f (array b [(i, z) | i \<- range b])
 309 -}
 310 accum :: (IArray a e, Ix i) => (e -> e' -> e) -> a i e -> [(i, e')] -> a i e
 311 accum f arr ies = case bounds arr of
 312     (l,u) -> unsafeAccum f arr [(index (l,u) i, e) | (i, e) <- ies]
 313
 314 {-# INLINE amap #-}
 315 -- | Returns a new array derived from the original array by applying a
 316 -- function to each of the elements.
 317 amap :: (IArray a e', IArray a e, Ix i) => (e' -> e) -> a i e' -> a i e
 318 amap f arr = case bounds arr of
 319     (l,u) -> unsafeArray (l,u) [(i, f (unsafeAt arr i)) |
 320                                 i <- [0 .. rangeSize (l,u) - 1]]
 321 {-# INLINE ixmap #-}
 322 -- | Returns a new array derived from the original array by applying a
 323 -- function to each of the indices.
 324 ixmap :: (IArray a e, Ix i, Ix j) => (i,i) -> (i -> j) -> a j e -> a i e
 325 ixmap (l,u) f arr =
 326     unsafeArray (l,u) [(unsafeIndex (l,u) i, arr ! f i) | i <- range (l,u)]
 327
 328 -----------------------------------------------------------------------------
 329 -- Normal polymorphic arrays
 330
 331 instance HasBounds Arr.Array where
 332     {-# INLINE bounds #-}
 333     bounds = Arr.bounds
 334
 335 instance IArray Arr.Array e where
 336     {-# INLINE unsafeArray #-}
 337     unsafeArray      = Arr.unsafeArray
 338     {-# INLINE unsafeAt #-}
 339     unsafeAt         = Arr.unsafeAt
 340     {-# INLINE unsafeReplace #-}
 341     unsafeReplace    = Arr.unsafeReplace
 342     {-# INLINE unsafeAccum #-}
 343     unsafeAccum      = Arr.unsafeAccum
 344     {-# INLINE unsafeAccumArray #-}
 345     unsafeAccumArray = Arr.unsafeAccumArray
 346
 347 #ifdef __GLASGOW_HASKELL__
 348 -----------------------------------------------------------------------------
 349 -- Flat unboxed arrays
 350
 351 -- | Arrays with unboxed elements.  Instances of 'IArray' are provided
 352 -- for 'UArray' with certain element types ('Int', 'Float', 'Char',
 353 -- etc.; see the 'UArray' class for a full list).
 354 --
 355 -- A 'UArray' will generally be more efficient (in terms of both time
 356 -- and space) than the equivalent 'Data.Array.Array' with the same
 357 -- element type.  However, 'UArray' is strict in its elements - so
 358 -- don\'t use 'UArray' if you require the non-strictness that
 359 -- 'Data.Array.Array' provides.
 360 --
 361 -- Because the @IArray@ interface provides operations overloaded on
 362 -- the type of the array, it should be possible to just change the
 363 -- array type being used by a program from say @Array@ to @UArray@ to
 364 -- get the benefits of unboxed arrays (don\'t forget to import
 365 -- "Data.Array.Unboxed" instead of "Data.Array").
 366 --
 367 data UArray i e = UArray !i !i ByteArray#
 368
 369 INSTANCE_TYPEABLE2(UArray,uArrayTc,"UArray")
 370
 371 instance HasBounds UArray where
 372     {-# INLINE bounds #-}
 373     bounds (UArray l u _) = (l,u)
 374
 375 {-# INLINE unsafeArrayUArray #-}
 376 unsafeArrayUArray :: (MArray (STUArray s) e (ST s), Ix i)
 377                   => (i,i) -> [(Int, e)] -> e -> ST s (UArray i e)
 378 unsafeArrayUArray (l,u) ies default_elem = do
 379     marr <- newArray (l,u) default_elem
 380     sequence_ [unsafeWrite marr i e | (i, e) <- ies]
 381     unsafeFreezeSTUArray marr
 382
 383 {-# INLINE unsafeFreezeSTUArray #-}
 384 unsafeFreezeSTUArray :: STUArray s i e -> ST s (UArray i e)
 385 unsafeFreezeSTUArray (STUArray l u marr#) = ST $ \s1# ->
 386     case unsafeFreezeByteArray# marr# s1# of { (# s2#, arr# #) ->
 387     (# s2#, UArray l u arr# #) }
 388
 389 {-# INLINE unsafeReplaceUArray #-}
 390 unsafeReplaceUArray :: (MArray (STUArray s) e (ST s), Ix i)
 391                     => UArray i e -> [(Int, e)] -> ST s (UArray i e)
 392 unsafeReplaceUArray arr ies = do
 393     marr <- thawSTUArray arr
 394     sequence_ [unsafeWrite marr i e | (i, e) <- ies]
 395     unsafeFreezeSTUArray marr
 396
 397 {-# INLINE unsafeAccumUArray #-}
 398 unsafeAccumUArray :: (MArray (STUArray s) e (ST s), Ix i)
 399                   => (e -> e' -> e) -> UArray i e -> [(Int, e')] -> ST s (UArray i e)
 400 unsafeAccumUArray f arr ies = do
 401     marr <- thawSTUArray arr
 402     sequence_ [do
 403         old <- unsafeRead marr i
 404         unsafeWrite marr i (f old new)
 405         | (i, new) <- ies]
 406     unsafeFreezeSTUArray marr
 407
 408 {-# INLINE unsafeAccumArrayUArray #-}
 409 unsafeAccumArrayUArray :: (MArray (STUArray s) e (ST s), Ix i)
 410                        => (e -> e' -> e) -> e -> (i,i) -> [(Int, e')] -> ST s (UArray i e)
 411 unsafeAccumArrayUArray f init (l,u) ies = do
 412     marr <- newArray (l,u) init
 413     sequence_ [do
 414         old <- unsafeRead marr i
 415         unsafeWrite marr i (f old new)
 416         | (i, new) <- ies]
 417     unsafeFreezeSTUArray marr
 418
 419 {-# INLINE eqUArray #-}
 420 eqUArray :: (IArray UArray e, Ix i, Eq e) => UArray i e -> UArray i e -> Bool
 421 eqUArray arr1@(UArray l1 u1 _) arr2@(UArray l2 u2 _) =
 422     if rangeSize (l1,u1) == 0 then rangeSize (l2,u2) == 0 else
 423     l1 == l2 && u1 == u2 &&
 424     and [unsafeAt arr1 i == unsafeAt arr2 i | i <- [0 .. rangeSize (l1,u1) - 1]]
 425
 426 {-# INLINE cmpUArray #-}
 427 cmpUArray :: (IArray UArray e, Ix i, Ord e) => UArray i e -> UArray i e -> Ordering
 428 cmpUArray arr1 arr2 = compare (assocs arr1) (assocs arr2)
 429
 430 {-# INLINE cmpIntUArray #-}
 431 cmpIntUArray :: (IArray UArray e, Ord e) => UArray Int e -> UArray Int e -> Ordering
 432 cmpIntUArray arr1@(UArray l1 u1 _) arr2@(UArray l2 u2 _) =
 433     if rangeSize (l1,u1) == 0 then if rangeSize (l2,u2) == 0 then EQ else LT else
 434     if rangeSize (l2,u2) == 0 then GT else
 435     case compare l1 l2 of
 436         EQ    -> foldr cmp (compare u1 u2) [0 .. rangeSize (l1, min u1 u2) - 1]
 437         other -> other
 438     where
 439     cmp i rest = case compare (unsafeAt arr1 i) (unsafeAt arr2 i) of
 440         EQ    -> rest
 441         other -> other
 442
 443 {-# RULES "cmpUArray/Int" cmpUArray = cmpIntUArray #-}
 444 #endif /* __GLASGOW_HASKELL__ */
 445
 446 -----------------------------------------------------------------------------
 447 -- Showing IArrays
 448
 449 {-# SPECIALISE
 450     showsIArray :: (IArray UArray e, Ix i, Show i, Show e) =>
 451                    Int -> UArray i e -> ShowS
 452   #-}
 453
 454 showsIArray :: (IArray a e, Ix i, Show i, Show e) => Int -> a i e -> ShowS
 455 showsIArray p a =
 456     showParen (p > 9) $
 457     showString "array " .
 458     shows (bounds a) .
 459     showChar ' ' .
 460     shows (assocs a)
 461
 462 #ifdef __GLASGOW_HASKELL__
 463 -----------------------------------------------------------------------------
 464 -- Flat unboxed arrays: instances
 465
 466 instance IArray UArray Bool where
 467     {-# INLINE unsafeArray #-}
 468     unsafeArray lu ies = runST (unsafeArrayUArray lu ies False)
 469     {-# INLINE unsafeAt #-}
 470     unsafeAt (UArray _ _ arr#) (I# i#) =
 471         (indexWordArray# arr# (bOOL_INDEX i#) `and#` bOOL_BIT i#)
 472         `neWord#` int2Word# 0#
 473     {-# INLINE unsafeReplace #-}
 474     unsafeReplace arr ies = runST (unsafeReplaceUArray arr ies)
 475     {-# INLINE unsafeAccum #-}
 476     unsafeAccum f arr ies = runST (unsafeAccumUArray f arr ies)
 477     {-# INLINE unsafeAccumArray #-}
 478     unsafeAccumArray f init lu ies = runST (unsafeAccumArrayUArray f init lu ies)
 479
 480 instance IArray UArray Char where
 481     {-# INLINE unsafeArray #-}
 482     unsafeArray lu ies = runST (unsafeArrayUArray lu ies '\0')
 483     {-# INLINE unsafeAt #-}
 484     unsafeAt (UArray _ _ arr#) (I# i#) = C# (indexWideCharArray# arr# i#)
 485     {-# INLINE unsafeReplace #-}
 486     unsafeReplace arr ies = runST (unsafeReplaceUArray arr ies)
 487     {-# INLINE unsafeAccum #-}
 488     unsafeAccum f arr ies = runST (unsafeAccumUArray f arr ies)
 489     {-# INLINE unsafeAccumArray #-}
 490     unsafeAccumArray f init lu ies = runST (unsafeAccumArrayUArray f init lu ies)
 491
 492 instance IArray UArray Int where
 493     {-# INLINE unsafeArray #-}
 494     unsafeArray lu ies = runST (unsafeArrayUArray lu ies 0)
 495     {-# INLINE unsafeAt #-}
 496     unsafeAt (UArray _ _ arr#) (I# i#) = I# (indexIntArray# arr# i#)
 497     {-# INLINE unsafeReplace #-}
 498     unsafeReplace arr ies = runST (unsafeReplaceUArray arr ies)
 499     {-# INLINE unsafeAccum #-}
 500     unsafeAccum f arr ies = runST (unsafeAccumUArray f arr ies)
 501     {-# INLINE unsafeAccumArray #-}
 502     unsafeAccumArray f init lu ies = runST (unsafeAccumArrayUArray f init lu ies)
 503
 504 instance IArray UArray Word where
 505     {-# INLINE unsafeArray #-}
 506     unsafeArray lu ies = runST (unsafeArrayUArray lu ies 0)
 507     {-# INLINE unsafeAt #-}
 508     unsafeAt (UArray _ _ arr#) (I# i#) = W# (indexWordArray# arr# i#)
 509     {-# INLINE unsafeReplace #-}
 510     unsafeReplace arr ies = runST (unsafeReplaceUArray arr ies)
 511     {-# INLINE unsafeAccum #-}
 512     unsafeAccum f arr ies = runST (unsafeAccumUArray f arr ies)
 513     {-# INLINE unsafeAccumArray #-}
 514     unsafeAccumArray f init lu ies = runST (unsafeAccumArrayUArray f init lu ies)
 515
 516 instance IArray UArray (Ptr a) where
 517     {-# INLINE unsafeArray #-}
 518     unsafeArray lu ies = runST (unsafeArrayUArray lu ies nullPtr)
 519     {-# INLINE unsafeAt #-}
 520     unsafeAt (UArray _ _ arr#) (I# i#) = Ptr (indexAddrArray# arr# i#)
 521     {-# INLINE unsafeReplace #-}
 522     unsafeReplace arr ies = runST (unsafeReplaceUArray arr ies)
 523     {-# INLINE unsafeAccum #-}
 524     unsafeAccum f arr ies = runST (unsafeAccumUArray f arr ies)
 525     {-# INLINE unsafeAccumArray #-}
 526     unsafeAccumArray f init lu ies = runST (unsafeAccumArrayUArray f init lu ies)
 527
 528 instance IArray UArray (FunPtr a) where
 529     {-# INLINE unsafeArray #-}
 530     unsafeArray lu ies = runST (unsafeArrayUArray lu ies nullFunPtr)
 531     {-# INLINE unsafeAt #-}
 532     unsafeAt (UArray _ _ arr#) (I# i#) = FunPtr (indexAddrArray# arr# i#)
 533     {-# INLINE unsafeReplace #-}
 534     unsafeReplace arr ies = runST (unsafeReplaceUArray arr ies)
 535     {-# INLINE unsafeAccum #-}
 536     unsafeAccum f arr ies = runST (unsafeAccumUArray f arr ies)
 537     {-# INLINE unsafeAccumArray #-}
 538     unsafeAccumArray f init lu ies = runST (unsafeAccumArrayUArray f init lu ies)
 539
 540 instance IArray UArray Float where
 541     {-# INLINE unsafeArray #-}
 542     unsafeArray lu ies = runST (unsafeArrayUArray lu ies 0)
 543     {-# INLINE unsafeAt #-}
 544     unsafeAt (UArray _ _ arr#) (I# i#) = F# (indexFloatArray# arr# i#)
 545     {-# INLINE unsafeReplace #-}
 546     unsafeReplace arr ies = runST (unsafeReplaceUArray arr ies)
 547     {-# INLINE unsafeAccum #-}
 548     unsafeAccum f arr ies = runST (unsafeAccumUArray f arr ies)
 549     {-# INLINE unsafeAccumArray #-}
 550     unsafeAccumArray f init lu ies = runST (unsafeAccumArrayUArray f init lu ies)
 551
 552 instance IArray UArray Double where
 553     {-# INLINE unsafeArray #-}
 554     unsafeArray lu ies = runST (unsafeArrayUArray lu ies 0)
 555     {-# INLINE unsafeAt #-}
 556     unsafeAt (UArray _ _ arr#) (I# i#) = D# (indexDoubleArray# arr# i#)
 557     {-# INLINE unsafeReplace #-}
 558     unsafeReplace arr ies = runST (unsafeReplaceUArray arr ies)
 559     {-# INLINE unsafeAccum #-}
 560     unsafeAccum f arr ies = runST (unsafeAccumUArray f arr ies)
 561     {-# INLINE unsafeAccumArray #-}
 562     unsafeAccumArray f init lu ies = runST (unsafeAccumArrayUArray f init lu ies)
 563
 564 instance IArray UArray (StablePtr a) where
 565     {-# INLINE unsafeArray #-}
 566     unsafeArray lu ies = runST (unsafeArrayUArray lu ies nullStablePtr)
 567     {-# INLINE unsafeAt #-}
 568     unsafeAt (UArray _ _ arr#) (I# i#) = StablePtr (indexStablePtrArray# arr# i#)
 569     {-# INLINE unsafeReplace #-}
 570     unsafeReplace arr ies = runST (unsafeReplaceUArray arr ies)
 571     {-# INLINE unsafeAccum #-}
 572     unsafeAccum f arr ies = runST (unsafeAccumUArray f arr ies)
 573     {-# INLINE unsafeAccumArray #-}
 574     unsafeAccumArray f init lu ies = runST (unsafeAccumArrayUArray f init lu ies)
 575
 576 -- bogus StablePtr value for initialising a UArray of StablePtr.
 577 nullStablePtr = StablePtr (unsafeCoerce# 0#)
 578
 579 instance IArray UArray Int8 where
 580     {-# INLINE unsafeArray #-}
 581     unsafeArray lu ies = runST (unsafeArrayUArray lu ies 0)
 582     {-# INLINE unsafeAt #-}
 583     unsafeAt (UArray _ _ arr#) (I# i#) = I8# (indexInt8Array# arr# i#)
 584     {-# INLINE unsafeReplace #-}
 585     unsafeReplace arr ies = runST (unsafeReplaceUArray arr ies)
 586     {-# INLINE unsafeAccum #-}
 587     unsafeAccum f arr ies = runST (unsafeAccumUArray f arr ies)
 588     {-# INLINE unsafeAccumArray #-}
 589     unsafeAccumArray f init lu ies = runST (unsafeAccumArrayUArray f init lu ies)
 590
 591 instance IArray UArray Int16 where
 592     {-# INLINE unsafeArray #-}
 593     unsafeArray lu ies = runST (unsafeArrayUArray lu ies 0)
 594     {-# INLINE unsafeAt #-}
 595     unsafeAt (UArray _ _ arr#) (I# i#) = I16# (indexInt16Array# arr# i#)
 596     {-# INLINE unsafeReplace #-}
 597     unsafeReplace arr ies = runST (unsafeReplaceUArray arr ies)
 598     {-# INLINE unsafeAccum #-}
 599     unsafeAccum f arr ies = runST (unsafeAccumUArray f arr ies)
 600     {-# INLINE unsafeAccumArray #-}
 601     unsafeAccumArray f init lu ies = runST (unsafeAccumArrayUArray f init lu ies)
 602
 603 instance IArray UArray Int32 where
 604     {-# INLINE unsafeArray #-}
 605     unsafeArray lu ies = runST (unsafeArrayUArray lu ies 0)
 606     {-# INLINE unsafeAt #-}
 607     unsafeAt (UArray _ _ arr#) (I# i#) = I32# (indexInt32Array# arr# i#)
 608     {-# INLINE unsafeReplace #-}
 609     unsafeReplace arr ies = runST (unsafeReplaceUArray arr ies)
 610     {-# INLINE unsafeAccum #-}
 611     unsafeAccum f arr ies = runST (unsafeAccumUArray f arr ies)
 612     {-# INLINE unsafeAccumArray #-}
 613     unsafeAccumArray f init lu ies = runST (unsafeAccumArrayUArray f init lu ies)
 614
 615 instance IArray UArray Int64 where
 616     {-# INLINE unsafeArray #-}
 617     unsafeArray lu ies = runST (unsafeArrayUArray lu ies 0)
 618     {-# INLINE unsafeAt #-}
 619     unsafeAt (UArray _ _ arr#) (I# i#) = I64# (indexInt64Array# arr# i#)
 620     {-# INLINE unsafeReplace #-}
 621     unsafeReplace arr ies = runST (unsafeReplaceUArray arr ies)
 622     {-# INLINE unsafeAccum #-}
 623     unsafeAccum f arr ies = runST (unsafeAccumUArray f arr ies)
 624     {-# INLINE unsafeAccumArray #-}
 625     unsafeAccumArray f init lu ies = runST (unsafeAccumArrayUArray f init lu ies)
 626
 627 instance IArray UArray Word8 where
 628     {-# INLINE unsafeArray #-}
 629     unsafeArray lu ies = runST (unsafeArrayUArray lu ies 0)
 630     {-# INLINE unsafeAt #-}
 631     unsafeAt (UArray _ _ arr#) (I# i#) = W8# (indexWord8Array# arr# i#)
 632     {-# INLINE unsafeReplace #-}
 633     unsafeReplace arr ies = runST (unsafeReplaceUArray arr ies)
 634     {-# INLINE unsafeAccum #-}
 635     unsafeAccum f arr ies = runST (unsafeAccumUArray f arr ies)
 636     {-# INLINE unsafeAccumArray #-}
 637     unsafeAccumArray f init lu ies = runST (unsafeAccumArrayUArray f init lu ies)
 638
 639 instance IArray UArray Word16 where
 640     {-# INLINE unsafeArray #-}
 641     unsafeArray lu ies = runST (unsafeArrayUArray lu ies 0)
 642     {-# INLINE unsafeAt #-}
 643     unsafeAt (UArray _ _ arr#) (I# i#) = W16# (indexWord16Array# arr# i#)
 644     {-# INLINE unsafeReplace #-}
 645     unsafeReplace arr ies = runST (unsafeReplaceUArray arr ies)
 646     {-# INLINE unsafeAccum #-}
 647     unsafeAccum f arr ies = runST (unsafeAccumUArray f arr ies)
 648     {-# INLINE unsafeAccumArray #-}
 649     unsafeAccumArray f init lu ies = runST (unsafeAccumArrayUArray f init lu ies)
 650
 651 instance IArray UArray Word32 where
 652     {-# INLINE unsafeArray #-}
 653     unsafeArray lu ies = runST (unsafeArrayUArray lu ies 0)
 654     {-# INLINE unsafeAt #-}
 655     unsafeAt (UArray _ _ arr#) (I# i#) = W32# (indexWord32Array# arr# i#)
 656     {-# INLINE unsafeReplace #-}
 657     unsafeReplace arr ies = runST (unsafeReplaceUArray arr ies)
 658     {-# INLINE unsafeAccum #-}
 659     unsafeAccum f arr ies = runST (unsafeAccumUArray f arr ies)
 660     {-# INLINE unsafeAccumArray #-}
 661     unsafeAccumArray f init lu ies = runST (unsafeAccumArrayUArray f init lu ies)
 662
 663 instance IArray UArray Word64 where
 664     {-# INLINE unsafeArray #-}
 665     unsafeArray lu ies = runST (unsafeArrayUArray lu ies 0)
 666     {-# INLINE unsafeAt #-}
 667     unsafeAt (UArray _ _ arr#) (I# i#) = W64# (indexWord64Array# arr# i#)
 668     {-# INLINE unsafeReplace #-}
 669     unsafeReplace arr ies = runST (unsafeReplaceUArray arr ies)
 670     {-# INLINE unsafeAccum #-}
 671     unsafeAccum f arr ies = runST (unsafeAccumUArray f arr ies)
 672     {-# INLINE unsafeAccumArray #-}
 673     unsafeAccumArray f init lu ies = runST (unsafeAccumArrayUArray f init lu ies)
 674
 675 instance Ix ix => Eq (UArray ix Bool) where
 676     (==) = eqUArray
 677
 678 instance Ix ix => Eq (UArray ix Char) where
 679     (==) = eqUArray
 680
 681 instance Ix ix => Eq (UArray ix Int) where
 682     (==) = eqUArray
 683
 684 instance Ix ix => Eq (UArray ix Word) where
 685     (==) = eqUArray
 686
 687 instance Ix ix => Eq (UArray ix (Ptr a)) where
 688     (==) = eqUArray
 689
 690 instance Ix ix => Eq (UArray ix (FunPtr a)) where
 691     (==) = eqUArray
 692
 693 instance Ix ix => Eq (UArray ix Float) where
 694     (==) = eqUArray
 695
 696 instance Ix ix => Eq (UArray ix Double) where
 697     (==) = eqUArray
 698
 699 instance Ix ix => Eq (UArray ix (StablePtr a)) where
 700     (==) = eqUArray
 701
 702 instance Ix ix => Eq (UArray ix Int8) where
 703     (==) = eqUArray
 704
 705 instance Ix ix => Eq (UArray ix Int16) where
 706     (==) = eqUArray
 707
 708 instance Ix ix => Eq (UArray ix Int32) where
 709     (==) = eqUArray
 710
 711 instance Ix ix => Eq (UArray ix Int64) where
 712     (==) = eqUArray
 713
 714 instance Ix ix => Eq (UArray ix Word8) where
 715     (==) = eqUArray
 716
 717 instance Ix ix => Eq (UArray ix Word16) where
 718     (==) = eqUArray
 719
 720 instance Ix ix => Eq (UArray ix Word32) where
 721     (==) = eqUArray
 722
 723 instance Ix ix => Eq (UArray ix Word64) where
 724     (==) = eqUArray
 725
 726 instance Ix ix => Ord (UArray ix Bool) where
 727     compare = cmpUArray
 728
 729 instance Ix ix => Ord (UArray ix Char) where
 730     compare = cmpUArray
 731
 732 instance Ix ix => Ord (UArray ix Int) where
 733     compare = cmpUArray
 734
 735 instance Ix ix => Ord (UArray ix Word) where
 736     compare = cmpUArray
 737
 738 instance Ix ix => Ord (UArray ix (Ptr a)) where
 739     compare = cmpUArray
 740
 741 instance Ix ix => Ord (UArray ix (FunPtr a)) where
 742     compare = cmpUArray
 743
 744 instance Ix ix => Ord (UArray ix Float) where
 745     compare = cmpUArray
 746
 747 instance Ix ix => Ord (UArray ix Double) where
 748     compare = cmpUArray
 749
 750 instance Ix ix => Ord (UArray ix Int8) where
 751     compare = cmpUArray
 752
 753 instance Ix ix => Ord (UArray ix Int16) where
 754     compare = cmpUArray
 755
 756 instance Ix ix => Ord (UArray ix Int32) where
 757     compare = cmpUArray
 758
 759 instance Ix ix => Ord (UArray ix Int64) where
 760     compare = cmpUArray
 761
 762 instance Ix ix => Ord (UArray ix Word8) where
 763     compare = cmpUArray
 764
 765 instance Ix ix => Ord (UArray ix Word16) where
 766     compare = cmpUArray
 767
 768 instance Ix ix => Ord (UArray ix Word32) where
 769     compare = cmpUArray
 770
 771 instance Ix ix => Ord (UArray ix Word64) where
 772     compare = cmpUArray
 773
 774 instance (Ix ix, Show ix) => Show (UArray ix Bool) where
 775     showsPrec = showsIArray
 776
 777 instance (Ix ix, Show ix) => Show (UArray ix Char) where
 778     showsPrec = showsIArray
 779
 780 instance (Ix ix, Show ix) => Show (UArray ix Int) where
 781     showsPrec = showsIArray
 782
 783 instance (Ix ix, Show ix) => Show (UArray ix Word) where
 784     showsPrec = showsIArray
 785
 786 instance (Ix ix, Show ix) => Show (UArray ix Float) where
 787     showsPrec = showsIArray
 788
 789 instance (Ix ix, Show ix) => Show (UArray ix Double) where
 790     showsPrec = showsIArray
 791
 792 instance (Ix ix, Show ix) => Show (UArray ix Int8) where
 793     showsPrec = showsIArray
 794
 795 instance (Ix ix, Show ix) => Show (UArray ix Int16) where
 796     showsPrec = showsIArray
 797
 798 instance (Ix ix, Show ix) => Show (UArray ix Int32) where
 799     showsPrec = showsIArray
 800
 801 instance (Ix ix, Show ix) => Show (UArray ix Int64) where
 802     showsPrec = showsIArray
 803
 804 instance (Ix ix, Show ix) => Show (UArray ix Word8) where
 805     showsPrec = showsIArray
 806
 807 instance (Ix ix, Show ix) => Show (UArray ix Word16) where
 808     showsPrec = showsIArray
 809
 810 instance (Ix ix, Show ix) => Show (UArray ix Word32) where
 811     showsPrec = showsIArray
 812
 813 instance (Ix ix, Show ix) => Show (UArray ix Word64) where
 814     showsPrec = showsIArray
 815 #endif /* __GLASGOW_HASKELL__ */
 816
 817 -----------------------------------------------------------------------------
 818 -- Mutable arrays
 819
 820 {-# NOINLINE arrEleBottom #-}
 821 arrEleBottom :: a
 822 arrEleBottom = error "MArray: undefined array element"
 823
 824 {-| Class of mutable array types.
 825
 826 An array type has the form @(a i e)@ where @a@ is the array type
 827 constructor (kind @* -> * -> *@), @i@ is the index type (a member of
 828 the class 'Ix'), and @e@ is the element type.
 829
 830 The @MArray@ class is parameterised over both @a@ and @e@ (so that
 831 instances specialised to certain element types can be defined, in the
 832 same way as for 'IArray'), and also over the type of the monad, @m@,
 833 in which the mutable array will be manipulated.
 834 -}
 835 class (HasBounds a, Monad m) => MArray a e m where
 836
 837     -- | Builds a new array, with every element initialised to the supplied
 838     -- value.
 839     newArray    :: Ix i => (i,i) -> e -> m (a i e)
 840
 841     -- | Builds a new array, with every element initialised to undefined.
 842     newArray_   :: Ix i => (i,i) -> m (a i e)
 843
 844     unsafeRead  :: Ix i => a i e -> Int -> m e
 845     unsafeWrite :: Ix i => a i e -> Int -> e -> m ()
 846
 847     newArray (l,u) init = do
 848         marr <- newArray_ (l,u)
 849         sequence_ [unsafeWrite marr i init | i <- [0 .. rangeSize (l,u) - 1]]
 850         return marr
 851
 852     newArray_ (l,u) = newArray (l,u) arrEleBottom
 853
 854     -- newArray takes an initialiser which all elements of
 855     -- the newly created array are initialised to.  newArray_ takes
 856     -- no initialiser, it is assumed that the array is initialised with
 857     -- "undefined" values.
 858
 859     -- why not omit newArray_?  Because in the unboxed array case we would
 860     -- like to omit the initialisation altogether if possible.  We can't do
 861     -- this for boxed arrays, because the elements must all have valid values
 862     -- at all times in case of garbage collection.
 863
 864     -- why not omit newArray?  Because in the boxed case, we can omit the
 865     -- default initialisation with undefined values if we *do* know the
 866     -- initial value and it is constant for all elements.
 867
 868 {-# INLINE newListArray #-}
 869 -- | Constructs a mutable array from a list of initial elements.
 870 -- The list gives the elements of the array in ascending order
 871 -- beginning with the lowest index.
 872 newListArray :: (MArray a e m, Ix i) => (i,i) -> [e] -> m (a i e)
 873 newListArray (l,u) es = do
 874     marr <- newArray_ (l,u)
 875     let n = rangeSize (l,u)
 876     let fillFromList i xs | i == n    = return ()
 877                           | otherwise = case xs of
 878             []   -> return ()
 879             y:ys -> unsafeWrite marr i y >> fillFromList (i+1) ys
 880     fillFromList 0 es
 881     return marr
 882
 883 {-# INLINE readArray #-}
 884 -- | Read an element from a mutable array
 885 readArray :: (MArray a e m, Ix i) => a i e -> i -> m e
 886 readArray marr i = case bounds marr of
 887     (l,u) -> unsafeRead marr (index (l,u) i)
 888
 889 {-# INLINE writeArray #-}
 890 -- | Write an element in a mutable array
 891 writeArray :: (MArray a e m, Ix i) => a i e -> i -> e -> m ()
 892 writeArray marr i e = case bounds marr of
 893     (l,u) -> unsafeWrite marr (index (l,u) i) e
 894
 895 {-# INLINE getElems #-}
 896 -- | Return a list of all the elements of a mutable array
 897 getElems :: (MArray a e m, Ix i) => a i e -> m [e]
 898 getElems marr = case bounds marr of
 899     (l,u) -> sequence [unsafeRead marr i | i <- [0 .. rangeSize (l,u) - 1]]
 900
 901 {-# INLINE getAssocs #-}
 902 -- | Return a list of all the associations of a mutable array, in
 903 -- index order.
 904 getAssocs :: (MArray a e m, Ix i) => a i e -> m [(i, e)]
 905 getAssocs marr = case bounds marr of
 906     (l,u) -> sequence [do e <- unsafeRead marr (index (l,u) i); return (i,e)
 907               | i <- range (l,u)]
 908
 909 {-# INLINE mapArray #-}
 910 -- | Constructs a new array derived from the original array by applying a
 911 -- function to each of the elements.
 912 mapArray :: (MArray a e' m, MArray a e m, Ix i) => (e' -> e) -> a i e' -> m (a i e)
 913 mapArray f marr = case bounds marr of
 914   (l,u) -> do
 915     marr' <- newArray_ (l,u)
 916     sequence_ [do
 917         e <- unsafeRead marr i
 918         unsafeWrite marr' i (f e)
 919         | i <- [0 .. rangeSize (l,u) - 1]]
 920     return marr'
 921
 922 {-# INLINE mapIndices #-}
 923 -- | Constructs a new array derived from the original array by applying a
 924 -- function to each of the indices.
 925 mapIndices :: (MArray a e m, Ix i, Ix j) => (i,i) -> (i -> j) -> a j e -> m (a i e)
 926 mapIndices (l,u) f marr = do
 927     marr' <- newArray_ (l,u)
 928     sequence_ [do
 929         e <- readArray marr (f i)
 930         unsafeWrite marr' (unsafeIndex (l,u) i) e
 931         | i <- range (l,u)]
 932     return marr'
 933
 934 -----------------------------------------------------------------------------
 935 -- Polymorphic non-strict mutable arrays (ST monad)
 936
 937 instance HasBounds (STArray s) where
 938     {-# INLINE bounds #-}
 939     bounds = ArrST.boundsSTArray
 940
 941 instance MArray (STArray s) e (ST s) where
 942     {-# INLINE newArray #-}
 943     newArray    = ArrST.newSTArray
 944     {-# INLINE unsafeRead #-}
 945     unsafeRead  = ArrST.unsafeReadSTArray
 946     {-# INLINE unsafeWrite #-}
 947     unsafeWrite = ArrST.unsafeWriteSTArray
 948
 949 -----------------------------------------------------------------------------
 950 -- Typeable instance for STArray
 951
 952 sTArrayTc :: TyCon
 953 sTArrayTc = mkTyCon "STArray"
 954
 955 instance (Typeable a, Typeable b, Typeable c) => Typeable (STArray a b c) where
 956   typeOf a = mkAppTy sTArrayTc [typeOf ((undefined :: STArray a b c -> a) a),
 957                                 typeOf ((undefined :: STArray a b c -> b) a),
 958                                 typeOf ((undefined :: STArray a b c -> c) a)]
 959
 960 #ifdef __GLASGOW_HASKELL__
 961 -----------------------------------------------------------------------------
 962 -- Flat unboxed mutable arrays (ST monad)
 963
 964 -- | A mutable array with unboxed elements, that can be manipulated in
 965 -- the 'ST' monad.  The type arguments are as follows:
 966 --
 967 --  * @s@: the state variable argument for the 'ST' type
 968 --
 969 --  * @i@: the index type of the array (should be an instance of @Ix@)
 970 --
 971 --  * @e@: the element type of the array.  Only certain element types
 972 --    are supported.
 973 --
 974 -- An 'STUArray' will generally be more efficient (in terms of both time
 975 -- and space) than the equivalent boxed version ('STArray') with the same
 976 -- element type.  However, 'STUArray' is strict in its elements - so
 977 -- don\'t use 'STUArray' if you require the non-strictness that
 978 -- 'STArray' provides.
 979 data STUArray s i a = STUArray !i !i (MutableByteArray# s)
 980
 981 INSTANCE_TYPEABLE3(STUArray,stUArrayTc,"STUArray")
 982
 983 instance HasBounds (STUArray s) where
 984     {-# INLINE bounds #-}
 985     bounds (STUArray l u _) = (l,u)
 986
 987 instance MArray (STUArray s) Bool (ST s) where
 988     {-# INLINE newArray #-}
 989     newArray (l,u) init = ST $ \s1# ->
 990         case rangeSize (l,u)            of { I# n# ->
 991         case newByteArray# (bOOL_SCALE n#) s1# of { (# s2#, marr# #) ->
 992         case bOOL_WORD_SCALE n#         of { n'# ->
 993         let loop i# s3# | i# ==# n'# = s3#
 994                         | otherwise  =
 995                 case writeWordArray# marr# i# e# s3# of { s4# ->
 996                 loop (i# +# 1#) s4# } in
 997         case loop 0# s2#                of { s3# ->
 998         (# s3#, STUArray l u marr# #) }}}}
 999       where
1000         W# e# = if init then maxBound else 0
1001     {-# INLINE newArray_ #-}
1002     newArray_ (l,u) = ST $ \s1# ->
1003         case rangeSize (l,u)            of { I# n# ->
1004         case newByteArray# (bOOL_SCALE n#) s1# of { (# s2#, marr# #) ->
1005         (# s2#, STUArray l u marr# #) }}
1006     {-# INLINE unsafeRead #-}
1007     unsafeRead (STUArray _ _ marr#) (I# i#) = ST $ \s1# ->
1008         case readWordArray# marr# (bOOL_INDEX i#) s1# of { (# s2#, e# #) ->
1009         (# s2#, (e# `and#` bOOL_BIT i#) `neWord#` int2Word# 0# #) }
1010     {-# INLINE unsafeWrite #-}
1011     unsafeWrite (STUArray _ _ marr#) (I# i#) e = ST $ \s1# ->
1012         case bOOL_INDEX i#              of { j# ->
1013         case readWordArray# marr# j# s1# of { (# s2#, old# #) ->
1014         case if e then old# `or#` bOOL_BIT i#
1015              else old# `and#` bOOL_NOT_BIT i# of { e# ->
1016         case writeWordArray# marr# j# e# s2# of { s3# ->
1017         (# s3#, () #) }}}}
1018
1019 instance MArray (STUArray s) Char (ST s) where
1020     {-# INLINE newArray_ #-}
1021     newArray_ (l,u) = ST $ \s1# ->
1022         case rangeSize (l,u)            of { I# n# ->
1023         case newByteArray# (n# *# 4#) s1# of { (# s2#, marr# #) ->
1024         (# s2#, STUArray l u marr# #) }}
1025     {-# INLINE unsafeRead #-}
1026     unsafeRead (STUArray _ _ marr#) (I# i#) = ST $ \s1# ->
1027         case readWideCharArray# marr# i# s1# of { (# s2#, e# #) ->
1028         (# s2#, C# e# #) }
1029     {-# INLINE unsafeWrite #-}
1030     unsafeWrite (STUArray _ _ marr#) (I# i#) (C# e#) = ST $ \s1# ->
1031         case writeWideCharArray# marr# i# e# s1# of { s2# ->
1032         (# s2#, () #) }
1033
1034 instance MArray (STUArray s) Int (ST s) where
1035     {-# INLINE newArray_ #-}
1036     newArray_ (l,u) = ST $ \s1# ->
1037         case rangeSize (l,u)            of { I# n# ->
1038         case newByteArray# (wORD_SCALE n#) s1# of { (# s2#, marr# #) ->
1039         (# s2#, STUArray l u marr# #) }}
1040     {-# INLINE unsafeRead #-}
1041     unsafeRead (STUArray _ _ marr#) (I# i#) = ST $ \s1# ->
1042         case readIntArray# marr# i# s1# of { (# s2#, e# #) ->
1043         (# s2#, I# e# #) }
1044     {-# INLINE unsafeWrite #-}
1045     unsafeWrite (STUArray _ _ marr#) (I# i#) (I# e#) = ST $ \s1# ->
1046         case writeIntArray# marr# i# e# s1# of { s2# ->
1047         (# s2#, () #) }
1048
1049 instance MArray (STUArray s) Word (ST s) where
1050     {-# INLINE newArray_ #-}
1051     newArray_ (l,u) = ST $ \s1# ->
1052         case rangeSize (l,u)            of { I# n# ->
1053         case newByteArray# (wORD_SCALE n#) s1# of { (# s2#, marr# #) ->
1054         (# s2#, STUArray l u marr# #) }}
1055     {-# INLINE unsafeRead #-}
1056     unsafeRead (STUArray _ _ marr#) (I# i#) = ST $ \s1# ->
1057         case readWordArray# marr# i# s1# of { (# s2#, e# #) ->
1058         (# s2#, W# e# #) }
1059     {-# INLINE unsafeWrite #-}
1060     unsafeWrite (STUArray _ _ marr#) (I# i#) (W# e#) = ST $ \s1# ->
1061         case writeWordArray# marr# i# e# s1# of { s2# ->
1062         (# s2#, () #) }
1063
1064 instance MArray (STUArray s) (Ptr a) (ST s) where
1065     {-# INLINE newArray_ #-}
1066     newArray_ (l,u) = ST $ \s1# ->
1067         case rangeSize (l,u)            of { I# n# ->
1068         case newByteArray# (wORD_SCALE n#) s1# of { (# s2#, marr# #) ->
1069         (# s2#, STUArray l u marr# #) }}
1070     {-# INLINE unsafeRead #-}
1071     unsafeRead (STUArray _ _ marr#) (I# i#) = ST $ \s1# ->
1072         case readAddrArray# marr# i# s1# of { (# s2#, e# #) ->
1073         (# s2#, Ptr e# #) }
1074     {-# INLINE unsafeWrite #-}
1075     unsafeWrite (STUArray _ _ marr#) (I# i#) (Ptr e#) = ST $ \s1# ->
1076         case writeAddrArray# marr# i# e# s1# of { s2# ->
1077         (# s2#, () #) }
1078
1079 instance MArray (STUArray s) (FunPtr a) (ST s) where
1080     {-# INLINE newArray_ #-}
1081     newArray_ (l,u) = ST $ \s1# ->
1082         case rangeSize (l,u)            of { I# n# ->
1083         case newByteArray# (wORD_SCALE n#) s1# of { (# s2#, marr# #) ->
1084         (# s2#, STUArray l u marr# #) }}
1085     {-# INLINE unsafeRead #-}
1086     unsafeRead (STUArray _ _ marr#) (I# i#) = ST $ \s1# ->
1087         case readAddrArray# marr# i# s1# of { (# s2#, e# #) ->
1088         (# s2#, FunPtr e# #) }
1089     {-# INLINE unsafeWrite #-}
1090     unsafeWrite (STUArray _ _ marr#) (I# i#) (FunPtr e#) = ST $ \s1# ->
1091         case writeAddrArray# marr# i# e# s1# of { s2# ->
1092         (# s2#, () #) }
1093
1094 instance MArray (STUArray s) Float (ST s) where
1095     {-# INLINE newArray_ #-}
1096     newArray_ (l,u) = ST $ \s1# ->
1097         case rangeSize (l,u)            of { I# n# ->
1098         case newByteArray# (fLOAT_SCALE n#) s1# of { (# s2#, marr# #) ->
1099         (# s2#, STUArray l u marr# #) }}
1100     {-# INLINE unsafeRead #-}
1101     unsafeRead (STUArray _ _ marr#) (I# i#) = ST $ \s1# ->
1102         case readFloatArray# marr# i# s1# of { (# s2#, e# #) ->
1103         (# s2#, F# e# #) }
1104     {-# INLINE unsafeWrite #-}
1105     unsafeWrite (STUArray _ _ marr#) (I# i#) (F# e#) = ST $ \s1# ->
1106         case writeFloatArray# marr# i# e# s1# of { s2# ->
1107         (# s2#, () #) }
1108
1109 instance MArray (STUArray s) Double (ST s) where
1110     {-# INLINE newArray_ #-}
1111     newArray_ (l,u) = ST $ \s1# ->
1112         case rangeSize (l,u)            of { I# n# ->
1113         case newByteArray# (dOUBLE_SCALE n#) s1# of { (# s2#, marr# #) ->
1114         (# s2#, STUArray l u marr# #) }}
1115     {-# INLINE unsafeRead #-}
1116     unsafeRead (STUArray _ _ marr#) (I# i#) = ST $ \s1# ->
1117         case readDoubleArray# marr# i# s1# of { (# s2#, e# #) ->
1118         (# s2#, D# e# #) }
1119     {-# INLINE unsafeWrite #-}
1120     unsafeWrite (STUArray _ _ marr#) (I# i#) (D# e#) = ST $ \s1# ->
1121         case writeDoubleArray# marr# i# e# s1# of { s2# ->
1122         (# s2#, () #) }
1123
1124 instance MArray (STUArray s) (StablePtr a) (ST s) where
1125     {-# INLINE newArray_ #-}
1126     newArray_ (l,u) = ST $ \s1# ->
1127         case rangeSize (l,u)            of { I# n# ->
1128         case newByteArray# (wORD_SCALE n#) s1# of { (# s2#, marr# #) ->
1129         (# s2#, STUArray l u marr# #) }}
1130     {-# INLINE unsafeRead #-}
1131     unsafeRead (STUArray _ _ marr#) (I# i#) = ST $ \s1# ->
1132         case readStablePtrArray# marr# i# s1# of { (# s2#, e# #) ->
1133         (# s2# , StablePtr e# #) }
1134     {-# INLINE unsafeWrite #-}
1135     unsafeWrite (STUArray _ _ marr#) (I# i#) (StablePtr e#) = ST $ \s1# ->
1136         case writeStablePtrArray# marr# i# e# s1# of { s2# ->
1137         (# s2#, () #) }
1138
1139 instance MArray (STUArray s) Int8 (ST s) where
1140     {-# INLINE newArray_ #-}
1141     newArray_ (l,u) = ST $ \s1# ->
1142         case rangeSize (l,u)            of { I# n# ->
1143         case newByteArray# n# s1#       of { (# s2#, marr# #) ->
1144         (# s2#, STUArray l u marr# #) }}
1145     {-# INLINE unsafeRead #-}
1146     unsafeRead (STUArray _ _ marr#) (I# i#) = ST $ \s1# ->
1147         case readInt8Array# marr# i# s1# of { (# s2#, e# #) ->
1148         (# s2#, I8# e# #) }
1149     {-# INLINE unsafeWrite #-}
1150     unsafeWrite (STUArray _ _ marr#) (I# i#) (I8# e#) = ST $ \s1# ->
1151         case writeInt8Array# marr# i# e# s1# of { s2# ->
1152         (# s2#, () #) }
1153
1154 instance MArray (STUArray s) Int16 (ST s) where
1155     {-# INLINE newArray_ #-}
1156     newArray_ (l,u) = ST $ \s1# ->
1157         case rangeSize (l,u)            of { I# n# ->
1158         case newByteArray# (n# *# 2#) s1# of { (# s2#, marr# #) ->
1159         (# s2#, STUArray l u marr# #) }}
1160     {-# INLINE unsafeRead #-}
1161     unsafeRead (STUArray _ _ marr#) (I# i#) = ST $ \s1# ->
1162         case readInt16Array# marr# i# s1# of { (# s2#, e# #) ->
1163         (# s2#, I16# e# #) }
1164     {-# INLINE unsafeWrite #-}
1165     unsafeWrite (STUArray _ _ marr#) (I# i#) (I16# e#) = ST $ \s1# ->
1166         case writeInt16Array# marr# i# e# s1# of { s2# ->
1167         (# s2#, () #) }
1168
1169 instance MArray (STUArray s) Int32 (ST s) where
1170     {-# INLINE newArray_ #-}
1171     newArray_ (l,u) = ST $ \s1# ->
1172         case rangeSize (l,u)            of { I# n# ->
1173         case newByteArray# (n# *# 4#) s1# of { (# s2#, marr# #) ->
1174         (# s2#, STUArray l u marr# #) }}
1175     {-# INLINE unsafeRead #-}
1176     unsafeRead (STUArray _ _ marr#) (I# i#) = ST $ \s1# ->
1177         case readInt32Array# marr# i# s1# of { (# s2#, e# #) ->
1178         (# s2#, I32# e# #) }
1179     {-# INLINE unsafeWrite #-}
1180     unsafeWrite (STUArray _ _ marr#) (I# i#) (I32# e#) = ST $ \s1# ->
1181         case writeInt32Array# marr# i# e# s1# of { s2# ->
1182         (# s2#, () #) }
1183
1184 instance MArray (STUArray s) Int64 (ST s) where
1185     {-# INLINE newArray_ #-}
1186     newArray_ (l,u) = ST $ \s1# ->
1187         case rangeSize (l,u)            of { I# n# ->
1188         case newByteArray# (n# *# 8#) s1# of { (# s2#, marr# #) ->
1189         (# s2#, STUArray l u marr# #) }}
1190     {-# INLINE unsafeRead #-}
1191     unsafeRead (STUArray _ _ marr#) (I# i#) = ST $ \s1# ->
1192         case readInt64Array# marr# i# s1# of { (# s2#, e# #) ->
1193         (# s2#, I64# e# #) }
1194     {-# INLINE unsafeWrite #-}
1195     unsafeWrite (STUArray _ _ marr#) (I# i#) (I64# e#) = ST $ \s1# ->
1196         case writeInt64Array# marr# i# e# s1# of { s2# ->
1197         (# s2#, () #) }
1198
1199 instance MArray (STUArray s) Word8 (ST s) where
1200     {-# INLINE newArray_ #-}
1201     newArray_ (l,u) = ST $ \s1# ->
1202         case rangeSize (l,u)            of { I# n# ->
1203         case newByteArray# n# s1#       of { (# s2#, marr# #) ->
1204         (# s2#, STUArray l u marr# #) }}
1205     {-# INLINE unsafeRead #-}
1206     unsafeRead (STUArray _ _ marr#) (I# i#) = ST $ \s1# ->
1207         case readWord8Array# marr# i# s1# of { (# s2#, e# #) ->
1208         (# s2#, W8# e# #) }
1209     {-# INLINE unsafeWrite #-}
1210     unsafeWrite (STUArray _ _ marr#) (I# i#) (W8# e#) = ST $ \s1# ->
1211         case writeWord8Array# marr# i# e# s1# of { s2# ->
1212         (# s2#, () #) }
1213
1214 instance MArray (STUArray s) Word16 (ST s) where
1215     {-# INLINE newArray_ #-}
1216     newArray_ (l,u) = ST $ \s1# ->
1217         case rangeSize (l,u)            of { I# n# ->
1218         case newByteArray# (n# *# 2#) s1# of { (# s2#, marr# #) ->
1219         (# s2#, STUArray l u marr# #) }}
1220     {-# INLINE unsafeRead #-}
1221     unsafeRead (STUArray _ _ marr#) (I# i#) = ST $ \s1# ->
1222         case readWord16Array# marr# i# s1# of { (# s2#, e# #) ->
1223         (# s2#, W16# e# #) }
1224     {-# INLINE unsafeWrite #-}
1225     unsafeWrite (STUArray _ _ marr#) (I# i#) (W16# e#) = ST $ \s1# ->
1226         case writeWord16Array# marr# i# e# s1# of { s2# ->
1227         (# s2#, () #) }
1228
1229 instance MArray (STUArray s) Word32 (ST s) where
1230     {-# INLINE newArray_ #-}
1231     newArray_ (l,u) = ST $ \s1# ->
1232         case rangeSize (l,u)            of { I# n# ->
1233         case newByteArray# (n# *# 4#) s1# of { (# s2#, marr# #) ->
1234         (# s2#, STUArray l u marr# #) }}
1235     {-# INLINE unsafeRead #-}
1236     unsafeRead (STUArray _ _ marr#) (I# i#) = ST $ \s1# ->
1237         case readWord32Array# marr# i# s1# of { (# s2#, e# #) ->
1238         (# s2#, W32# e# #) }
1239     {-# INLINE unsafeWrite #-}
1240     unsafeWrite (STUArray _ _ marr#) (I# i#) (W32# e#) = ST $ \s1# ->
1241         case writeWord32Array# marr# i# e# s1# of { s2# ->
1242         (# s2#, () #) }
1243
1244 instance MArray (STUArray s) Word64 (ST s) where
1245     {-# INLINE newArray_ #-}
1246     newArray_ (l,u) = ST $ \s1# ->
1247         case rangeSize (l,u)            of { I# n# ->
1248         case newByteArray# (n# *# 8#) s1# of { (# s2#, marr# #) ->
1249         (# s2#, STUArray l u marr# #) }}
1250     {-# INLINE unsafeRead #-}
1251     unsafeRead (STUArray _ _ marr#) (I# i#) = ST $ \s1# ->
1252         case readWord64Array# marr# i# s1# of { (# s2#, e# #) ->
1253         (# s2#, W64# e# #) }
1254     {-# INLINE unsafeWrite #-}
1255     unsafeWrite (STUArray _ _ marr#) (I# i#) (W64# e#) = ST $ \s1# ->
1256         case writeWord64Array# marr# i# e# s1# of { s2# ->
1257         (# s2#, () #) }
1258
1259 -----------------------------------------------------------------------------
1260 -- Translation between elements and bytes
1261
1262 bOOL_SCALE, bOOL_WORD_SCALE,
1263   wORD_SCALE, dOUBLE_SCALE, fLOAT_SCALE :: Int# -> Int#
1264 bOOL_SCALE n# = (n# +# last#) `uncheckedIShiftRA#` 3#
1265   where I# last# = SIZEOF_HSWORD * 8 - 1
1266 bOOL_WORD_SCALE n# = bOOL_INDEX (n# +# last#)
1267   where I# last# = SIZEOF_HSWORD * 8 - 1
1268 wORD_SCALE   n# = scale# *# n# where I# scale# = SIZEOF_HSWORD
1269 dOUBLE_SCALE n# = scale# *# n# where I# scale# = SIZEOF_HSDOUBLE
1270 fLOAT_SCALE  n# = scale# *# n# where I# scale# = SIZEOF_HSFLOAT
1271
1272 bOOL_INDEX :: Int# -> Int#
1273 #if SIZEOF_HSWORD == 4
1274 bOOL_INDEX i# = i# `uncheckedIShiftRA#` 5#
1275 #elif SIZEOF_HSWORD == 8
1276 bOOL_INDEX i# = i# `uncheckedIShiftRA#` 6#
1277 #endif
1278
1279 bOOL_BIT, bOOL_NOT_BIT :: Int# -> Word#
1280 bOOL_BIT     n# = int2Word# 1# `uncheckedShiftL#` (word2Int# (int2Word# n# `and#` mask#))
1281   where W# mask# = SIZEOF_HSWORD * 8 - 1
1282 bOOL_NOT_BIT n# = bOOL_BIT n# `xor#` mb# where W# mb# = maxBound
1283 #endif /* __GLASGOW_HASKELL__ */
1284
1285 -----------------------------------------------------------------------------
1286 -- Freezing
1287
1288 -- | Converts a mutable array (any instance of 'MArray') to an
1289 -- immutable array (any instance of 'IArray') by taking a complete
1290 -- copy of it.
1291 freeze :: (Ix i, MArray a e m, IArray b e) => a i e -> m (b i e)
1292 freeze marr = case bounds marr of
1293   (l,u) -> do
1294     ies <- sequence [do e <- unsafeRead marr i; return (i,e)
1295                      | i <- [0 .. rangeSize (l,u) - 1]]
1296     return (unsafeArray (l,u) ies)
1297
1298 #ifdef __GLASGOW_HASKELL__
1299 freezeSTUArray :: Ix i => STUArray s i e -> ST s (UArray i e)
1300 freezeSTUArray (STUArray l u marr#) = ST $ \s1# ->
1301     case sizeofMutableByteArray# marr#  of { n# ->
1302     case newByteArray# n# s1#           of { (# s2#, marr'# #) ->
1303     case unsafeCoerce# memcpy marr'# marr# n# s2# of { (# s3#, () #) ->
1304     case unsafeFreezeByteArray# marr'# s3# of { (# s4#, arr# #) ->
1305     (# s4#, UArray l u arr# #) }}}}
1306
1307 {-# RULES
1308 "freeze/STArray"  freeze = ArrST.freezeSTArray
1309 "freeze/STUArray" freeze = freezeSTUArray
1310     #-}
1311 #endif /* __GLASGOW_HASKELL__ */
1312
1313 -- In-place conversion of mutable arrays to immutable ones places
1314 -- a proof obligation on the user: no other parts of your code can
1315 -- have a reference to the array at the point where you unsafely
1316 -- freeze it (and, subsequently mutate it, I suspect).
1317
1318 {-# INLINE unsafeFreeze #-}
1319
1320 -- | Converts a mutable array to an immutable array /without taking a
1321 -- copy/.  This function is \"unsafe\" because if any further
1322 -- modifications are made to the original mutable array then they will
1323 -- be shared with the immutable version.  It is safe to use,
1324 -- therefore, if the mutable version is never modified after the
1325 -- freeze operation.
1326 unsafeFreeze :: (Ix i, MArray a e m, IArray b e) => a i e -> m (b i e)
1327 unsafeFreeze = freeze
1328
1329 {-# RULES
1330 "unsafeFreeze/STArray"  unsafeFreeze = ArrST.unsafeFreezeSTArray
1331 "unsafeFreeze/STUArray" unsafeFreeze = unsafeFreezeSTUArray
1332     #-}
1333
1334 -----------------------------------------------------------------------------
1335 -- Thawing
1336
1337 -- | Converts an immutable array (any instance of 'IArray') into a
1338 -- mutable array (any instance of 'MArray') by taking a complete copy
1339 -- of it.
1340 thaw :: (Ix i, IArray a e, MArray b e m) => a i e -> m (b i e)
1341 thaw arr = case bounds arr of
1342   (l,u) -> do
1343     marr <- newArray_ (l,u)
1344     sequence_ [unsafeWrite marr i (unsafeAt arr i)
1345                | i <- [0 .. rangeSize (l,u) - 1]]
1346     return marr
1347
1348 #ifdef __GLASGOW_HASKELL__
1349 thawSTUArray :: Ix i => UArray i e -> ST s (STUArray s i e)
1350 thawSTUArray (UArray l u arr#) = ST $ \s1# ->
1351     case sizeofByteArray# arr#          of { n# ->
1352     case newByteArray# n# s1#           of { (# s2#, marr# #) ->
1353     case unsafeCoerce# memcpy marr# arr# n# s2# of { (# s3#, () #) ->
1354     (# s3#, STUArray l u marr# #) }}}
1355
1356 foreign import ccall unsafe "memcpy"
1357     memcpy :: MutableByteArray# RealWorld -> ByteArray# -> Int# -> IO ()
1358
1359 {-# RULES
1360 "thaw/STArray"  thaw = ArrST.thawSTArray
1361 "thaw/STUArray" thaw = thawSTUArray
1362     #-}
1363 #endif /* __GLASGOW_HASKELL__ */
1364
1365 -- In-place conversion of immutable arrays to mutable ones places
1366 -- a proof obligation on the user: no other parts of your code can
1367 -- have a reference to the array at the point where you unsafely
1368 -- thaw it (and, subsequently mutate it, I suspect).
1369
1370 {-# INLINE unsafeThaw #-}
1371
1372 -- | Converts an immutable array into a mutable array /without taking
1373 -- a copy/.  This function is \"unsafe\" because any subsequent
1374 -- modifications made to the mutable version of the array will be
1375 -- shared with the immutable version.  It is safe to use, therefore, if
1376 -- the immutable version is never referenced again.
1377 unsafeThaw :: (Ix i, IArray a e, MArray b e m) => a i e -> m (b i e)
1378 unsafeThaw = thaw
1379
1380 #ifdef __GLASGOW_HASKELL__
1381 {-# INLINE unsafeThawSTUArray #-}
1382 unsafeThawSTUArray :: Ix i => UArray i e -> ST s (STUArray s i e)
1383 unsafeThawSTUArray (UArray l u marr#) =
1384     return (STUArray l u (unsafeCoerce# marr#))
1385
1386 {-# RULES
1387 "unsafeThaw/STArray"    unsafeThaw = ArrST.unsafeThawSTArray
1388 "unsafeThaw/STUArray"   unsafeThaw = unsafeThawSTUArray
1389     #-}
1390 #endif /* __GLASGOW_HASKELL__ */