1 -----------------------------------------------------------------------------
3 -- Module : Data.Array.Base
4 -- Copyright : (c) The University of Glasgow 2001
5 -- License : BSD-style (see the file libraries/base/LICENSE)
7 -- Maintainer : libraries@haskell.org
8 -- Stability : experimental
9 -- Portability : non-portable
11 -- Basis for IArray and MArray. Not intended for external consumption;
12 -- use IArray or MArray instead.
14 -----------------------------------------------------------------------------
17 module Data.Array.Base where
21 import Data.Ix ( Ix, range, index, rangeSize )
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 )
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(..) )
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 )
49 -----------------------------------------------------------------------------
50 -- Class of immutable arrays
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)
57 {- | Class of immutable array types.
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.
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
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)
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
80 sequence_ [unsafeWrite marr i e | (i, e) <- ies]
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
88 old <- unsafeRead marr i
89 unsafeWrite marr i (f old new)
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
98 old <- unsafeRead marr i
99 unsafeWrite marr i (f old new)
106 {-| Constructs an immutable array from a pair of bounds and a list of
107 initial associations.
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
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.
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:
126 > a = array (1,100) ((1,1) : [(i, i * a!(i-1)) | i \<- [2..100]])
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.
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.
137 array :: (IArray a e, Ix i)
138 => (i,i) -- ^ bounds of the array: (lowest,highest)
139 -> [(i, e)] -- ^ list of associations
141 array (l,u) ies = unsafeArray (l,u) [(index (l,u) i, e) | (i, e) <- ies]
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).
150 {-# INLINE listArray #-}
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)
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
166 y:ys -> unsafeWrite marr i y >> fillFromList (i+1) ys
171 "listArray/Array" listArray =
172 \lu es -> runST (listArrayST lu es >>= ArrST.unsafeFreezeSTArray)
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
185 y:ys -> unsafeWrite marr i y >> fillFromList (i+1) ys
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.
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.
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)
235 #endif /* __GLASGOW_HASKELL__ */
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)
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)
248 -- | Returns a list of all the elements of an array, in the same order
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]]
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)]
260 {-# INLINE accumArray #-}
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.
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
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]
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]
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
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.
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]
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':
308 > accumArray f z b = accum f (array b [(i, z) | i \<- range b])
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]
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]]
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
326 unsafeArray (l,u) [(unsafeIndex (l,u) i, arr ! f i) | i <- range (l,u)]
328 -----------------------------------------------------------------------------
329 -- Normal polymorphic arrays
331 instance HasBounds Arr.Array where
332 {-# INLINE bounds #-}
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
347 #ifdef __GLASGOW_HASKELL__
348 -----------------------------------------------------------------------------
349 -- Flat unboxed arrays
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).
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.
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").
367 data UArray i e = UArray !i !i ByteArray#
369 INSTANCE_TYPEABLE2(UArray,uArrayTc,"UArray")
371 instance HasBounds UArray where
372 {-# INLINE bounds #-}
373 bounds (UArray l u _) = (l,u)
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
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# #) }
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
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
403 old <- unsafeRead marr i
404 unsafeWrite marr i (f old new)
406 unsafeFreezeSTUArray marr
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
414 old <- unsafeRead marr i
415 unsafeWrite marr i (f old new)
417 unsafeFreezeSTUArray marr
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]]
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)
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]
439 cmp i rest = case compare (unsafeAt arr1 i) (unsafeAt arr2 i) of
443 {-# RULES "cmpUArray/Int" cmpUArray = cmpIntUArray #-}
444 #endif /* __GLASGOW_HASKELL__ */
446 -----------------------------------------------------------------------------
450 showsIArray :: (IArray UArray e, Ix i, Show i, Show e) =>
451 Int -> UArray i e -> ShowS
454 showsIArray :: (IArray a e, Ix i, Show i, Show e) => Int -> a i e -> ShowS
457 showString "array " .
462 #ifdef __GLASGOW_HASKELL__
463 -----------------------------------------------------------------------------
464 -- Flat unboxed arrays: instances
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)
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)
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)
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)
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)
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)
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)
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)
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)
576 -- bogus StablePtr value for initialising a UArray of StablePtr.
577 nullStablePtr = StablePtr (unsafeCoerce# 0#)
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)
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)
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)
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)
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)
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)
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)
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)
675 instance Ix ix => Eq (UArray ix Bool) where
678 instance Ix ix => Eq (UArray ix Char) where
681 instance Ix ix => Eq (UArray ix Int) where
684 instance Ix ix => Eq (UArray ix Word) where
687 instance Ix ix => Eq (UArray ix (Ptr a)) where
690 instance Ix ix => Eq (UArray ix (FunPtr a)) where
693 instance Ix ix => Eq (UArray ix Float) where
696 instance Ix ix => Eq (UArray ix Double) where
699 instance Ix ix => Eq (UArray ix (StablePtr a)) where
702 instance Ix ix => Eq (UArray ix Int8) where
705 instance Ix ix => Eq (UArray ix Int16) where
708 instance Ix ix => Eq (UArray ix Int32) where
711 instance Ix ix => Eq (UArray ix Int64) where
714 instance Ix ix => Eq (UArray ix Word8) where
717 instance Ix ix => Eq (UArray ix Word16) where
720 instance Ix ix => Eq (UArray ix Word32) where
723 instance Ix ix => Eq (UArray ix Word64) where
726 instance Ix ix => Ord (UArray ix Bool) where
729 instance Ix ix => Ord (UArray ix Char) where
732 instance Ix ix => Ord (UArray ix Int) where
735 instance Ix ix => Ord (UArray ix Word) where
738 instance Ix ix => Ord (UArray ix (Ptr a)) where
741 instance Ix ix => Ord (UArray ix (FunPtr a)) where
744 instance Ix ix => Ord (UArray ix Float) where
747 instance Ix ix => Ord (UArray ix Double) where
750 instance Ix ix => Ord (UArray ix Int8) where
753 instance Ix ix => Ord (UArray ix Int16) where
756 instance Ix ix => Ord (UArray ix Int32) where
759 instance Ix ix => Ord (UArray ix Int64) where
762 instance Ix ix => Ord (UArray ix Word8) where
765 instance Ix ix => Ord (UArray ix Word16) where
768 instance Ix ix => Ord (UArray ix Word32) where
771 instance Ix ix => Ord (UArray ix Word64) where
774 instance (Ix ix, Show ix) => Show (UArray ix Bool) where
775 showsPrec = showsIArray
777 instance (Ix ix, Show ix) => Show (UArray ix Char) where
778 showsPrec = showsIArray
780 instance (Ix ix, Show ix) => Show (UArray ix Int) where
781 showsPrec = showsIArray
783 instance (Ix ix, Show ix) => Show (UArray ix Word) where
784 showsPrec = showsIArray
786 instance (Ix ix, Show ix) => Show (UArray ix Float) where
787 showsPrec = showsIArray
789 instance (Ix ix, Show ix) => Show (UArray ix Double) where
790 showsPrec = showsIArray
792 instance (Ix ix, Show ix) => Show (UArray ix Int8) where
793 showsPrec = showsIArray
795 instance (Ix ix, Show ix) => Show (UArray ix Int16) where
796 showsPrec = showsIArray
798 instance (Ix ix, Show ix) => Show (UArray ix Int32) where
799 showsPrec = showsIArray
801 instance (Ix ix, Show ix) => Show (UArray ix Int64) where
802 showsPrec = showsIArray
804 instance (Ix ix, Show ix) => Show (UArray ix Word8) where
805 showsPrec = showsIArray
807 instance (Ix ix, Show ix) => Show (UArray ix Word16) where
808 showsPrec = showsIArray
810 instance (Ix ix, Show ix) => Show (UArray ix Word32) where
811 showsPrec = showsIArray
813 instance (Ix ix, Show ix) => Show (UArray ix Word64) where
814 showsPrec = showsIArray
815 #endif /* __GLASGOW_HASKELL__ */
817 -----------------------------------------------------------------------------
820 {-# NOINLINE arrEleBottom #-}
822 arrEleBottom = error "MArray: undefined array element"
824 {-| Class of mutable array types.
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.
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.
835 class (HasBounds a, Monad m) => MArray a e m where
837 -- | Builds a new array, with every element initialised to the supplied
839 newArray :: Ix i => (i,i) -> e -> m (a i e)
841 -- | Builds a new array, with every element initialised to undefined.
842 newArray_ :: Ix i => (i,i) -> m (a i e)
844 unsafeRead :: Ix i => a i e -> Int -> m e
845 unsafeWrite :: Ix i => a i e -> Int -> e -> m ()
847 newArray (l,u) init = do
848 marr <- newArray_ (l,u)
849 sequence_ [unsafeWrite marr i init | i <- [0 .. rangeSize (l,u) - 1]]
852 newArray_ (l,u) = newArray (l,u) arrEleBottom
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.
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.
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.
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
879 y:ys -> unsafeWrite marr i y >> fillFromList (i+1) ys
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)
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
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]]
901 {-# INLINE getAssocs #-}
902 -- | Return a list of all the associations of a mutable array, in
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)
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
915 marr' <- newArray_ (l,u)
917 e <- unsafeRead marr i
918 unsafeWrite marr' i (f e)
919 | i <- [0 .. rangeSize (l,u) - 1]]
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)
929 e <- readArray marr (f i)
930 unsafeWrite marr' (unsafeIndex (l,u) i) e
934 -----------------------------------------------------------------------------
935 -- Polymorphic non-strict mutable arrays (ST monad)
937 instance HasBounds (STArray s) where
938 {-# INLINE bounds #-}
939 bounds = ArrST.boundsSTArray
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
949 -----------------------------------------------------------------------------
950 -- Typeable instance for STArray
953 sTArrayTc = mkTyCon "STArray"
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)]
960 #ifdef __GLASGOW_HASKELL__
961 -----------------------------------------------------------------------------
962 -- Flat unboxed mutable arrays (ST monad)
964 -- | A mutable array with unboxed elements, that can be manipulated in
965 -- the 'ST' monad. The type arguments are as follows:
967 -- * @s@: the state variable argument for the 'ST' type
969 -- * @i@: the index type of the array (should be an instance of @Ix@)
971 -- * @e@: the element type of the array. Only certain element types
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)
981 INSTANCE_TYPEABLE3(STUArray,stUArrayTc,"STUArray")
983 instance HasBounds (STUArray s) where
984 {-# INLINE bounds #-}
985 bounds (STUArray l u _) = (l,u)
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#
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# #) }}}}
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# ->
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# #) ->
1029 {-# INLINE unsafeWrite #-}
1030 unsafeWrite (STUArray _ _ marr#) (I# i#) (C# e#) = ST $ \s1# ->
1031 case writeWideCharArray# marr# i# e# s1# of { s2# ->
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# #) ->
1044 {-# INLINE unsafeWrite #-}
1045 unsafeWrite (STUArray _ _ marr#) (I# i#) (I# e#) = ST $ \s1# ->
1046 case writeIntArray# marr# i# e# s1# of { s2# ->
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# #) ->
1059 {-# INLINE unsafeWrite #-}
1060 unsafeWrite (STUArray _ _ marr#) (I# i#) (W# e#) = ST $ \s1# ->
1061 case writeWordArray# marr# i# e# s1# of { s2# ->
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# #) ->
1074 {-# INLINE unsafeWrite #-}
1075 unsafeWrite (STUArray _ _ marr#) (I# i#) (Ptr e#) = ST $ \s1# ->
1076 case writeAddrArray# marr# i# e# s1# of { s2# ->
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# ->
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# #) ->
1104 {-# INLINE unsafeWrite #-}
1105 unsafeWrite (STUArray _ _ marr#) (I# i#) (F# e#) = ST $ \s1# ->
1106 case writeFloatArray# marr# i# e# s1# of { s2# ->
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# #) ->
1119 {-# INLINE unsafeWrite #-}
1120 unsafeWrite (STUArray _ _ marr#) (I# i#) (D# e#) = ST $ \s1# ->
1121 case writeDoubleArray# marr# i# e# s1# of { s2# ->
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# ->
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# #) ->
1149 {-# INLINE unsafeWrite #-}
1150 unsafeWrite (STUArray _ _ marr#) (I# i#) (I8# e#) = ST $ \s1# ->
1151 case writeInt8Array# marr# i# e# s1# of { s2# ->
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# ->
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# ->
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# ->
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# #) ->
1209 {-# INLINE unsafeWrite #-}
1210 unsafeWrite (STUArray _ _ marr#) (I# i#) (W8# e#) = ST $ \s1# ->
1211 case writeWord8Array# marr# i# e# s1# of { s2# ->
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# ->
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# ->
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# ->
1259 -----------------------------------------------------------------------------
1260 -- Translation between elements and bytes
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
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#
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__ */
1285 -----------------------------------------------------------------------------
1288 -- | Converts a mutable array (any instance of 'MArray') to an
1289 -- immutable array (any instance of 'IArray') by taking a complete
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
1294 ies <- sequence [do e <- unsafeRead marr i; return (i,e)
1295 | i <- [0 .. rangeSize (l,u) - 1]]
1296 return (unsafeArray (l,u) ies)
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# #) }}}}
1308 "freeze/STArray" freeze = ArrST.freezeSTArray
1309 "freeze/STUArray" freeze = freezeSTUArray
1311 #endif /* __GLASGOW_HASKELL__ */
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).
1318 {-# INLINE unsafeFreeze #-}
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
1330 "unsafeFreeze/STArray" unsafeFreeze = ArrST.unsafeFreezeSTArray
1331 "unsafeFreeze/STUArray" unsafeFreeze = unsafeFreezeSTUArray
1334 -----------------------------------------------------------------------------
1337 -- | Converts an immutable array (any instance of 'IArray') into a
1338 -- mutable array (any instance of 'MArray') by taking a complete copy
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
1343 marr <- newArray_ (l,u)
1344 sequence_ [unsafeWrite marr i (unsafeAt arr i)
1345 | i <- [0 .. rangeSize (l,u) - 1]]
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# #) }}}
1356 foreign import ccall unsafe "memcpy"
1357 memcpy :: MutableByteArray# RealWorld -> ByteArray# -> Int# -> IO ()
1360 "thaw/STArray" thaw = ArrST.thawSTArray
1361 "thaw/STUArray" thaw = thawSTUArray
1363 #endif /* __GLASGOW_HASKELL__ */
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).
1370 {-# INLINE unsafeThaw #-}
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)
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#))
1387 "unsafeThaw/STArray" unsafeThaw = ArrST.unsafeThawSTArray
1388 "unsafeThaw/STUArray" unsafeThaw = unsafeThawSTUArray
1390 #endif /* __GLASGOW_HASKELL__ */