2 {-# LANGUAGE NoImplicitPrelude, NoBangPatterns, MagicHash, UnboxedTuples #-}
3 {-# OPTIONS_GHC -funbox-strict-fields #-}
4 {-# OPTIONS_HADDOCK hide #-}
6 -----------------------------------------------------------------------------
9 -- Copyright : (c) The University of Glasgow, 1994-2000
10 -- License : see libraries/base/LICENSE
12 -- Maintainer : cvs-ghc@haskell.org
13 -- Stability : internal
14 -- Portability : non-portable (GHC extensions)
16 -- GHC\'s array implementation.
18 -----------------------------------------------------------------------------
36 %*********************************************************
38 \subsection{The @Ix@ class}
40 %*********************************************************
43 -- | The 'Ix' class is used to map a contiguous subrange of values in
44 -- a type onto integers. It is used primarily for array indexing
45 -- (see the array package).
47 -- The first argument @(l,u)@ of each of these operations is a pair
48 -- specifying the lower and upper bounds of a contiguous subrange of values.
50 -- An implementation is entitled to assume the following laws about these
53 -- * @'inRange' (l,u) i == 'elem' i ('range' (l,u))@ @ @
55 -- * @'range' (l,u) '!!' 'index' (l,u) i == i@, when @'inRange' (l,u) i@
57 -- * @'map' ('index' (l,u)) ('range' (l,u))) == [0..'rangeSize' (l,u)-1]@ @ @
59 -- * @'rangeSize' (l,u) == 'length' ('range' (l,u))@ @ @
61 -- Minimal complete instance: 'range', 'index' and 'inRange'.
63 class (Ord a) => Ix a where
64 -- | The list of values in the subrange defined by a bounding pair.
66 -- | The position of a subscript in the subrange.
67 index :: (a,a) -> a -> Int
68 -- | Like 'index', but without checking that the value is in range.
69 unsafeIndex :: (a,a) -> a -> Int
70 -- | Returns 'True' the given subscript lies in the range defined
72 inRange :: (a,a) -> a -> Bool
73 -- | The size of the subrange defined by a bounding pair.
74 rangeSize :: (a,a) -> Int
75 -- | like 'rangeSize', but without checking that the upper bound is
77 unsafeRangeSize :: (a,a) -> Int
79 -- Must specify one of index, unsafeIndex
81 -- 'index' is typically over-ridden in instances, with essentially
82 -- the same code, but using indexError instead of hopelessIndexError
83 -- Reason: we have 'Show' at the instances
84 {-# INLINE index #-} -- See Note [Inlining index]
85 index b i | inRange b i = unsafeIndex b i
86 | otherwise = hopelessIndexError
88 unsafeIndex b i = index b i
90 rangeSize b@(_l,h) | inRange b h = unsafeIndex b h + 1
91 | otherwise = 0 -- This case is only here to
92 -- check for an empty range
93 -- NB: replacing (inRange b h) by (l <= h) fails for
94 -- tuples. E.g. (1,2) <= (2,1) but the range is empty
96 unsafeRangeSize b@(_l,h) = unsafeIndex b h + 1
99 Note that the following is NOT right
100 rangeSize (l,h) | l <= h = index b h + 1
103 Because it might be the case that l<h, but the range
104 is nevertheless empty. Consider
106 Here l<h, but the second index ranges from 2..1 and
109 %*********************************************************
111 \subsection{Instances of @Ix@}
113 %*********************************************************
115 Note [Inlining index]
116 ~~~~~~~~~~~~~~~~~~~~~
117 We inline the 'index' operation,
119 * Partly because it generates much faster code
120 (although bigger); see Trac #1216
122 * Partly because it exposes the bounds checks to the simplifier which
125 If you make a per-instance index method, you may consider inlining it.
127 Note [Double bounds-checking of index values]
128 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
129 When you index an array, a!x, there are two possible bounds checks we might make:
131 (A) Check that (inRange (bounds a) x) holds.
133 (A) is checked in the method for 'index'
135 (B) Check that (index (bounds a) x) lies in the range 0..n,
136 where n is the size of the underlying array
138 (B) is checked in the top-level function (!), in safeIndex.
140 Of course it *should* be the case that (A) holds iff (B) holds, but that
141 is a property of the particular instances of index, bounds, and inRange,
142 so GHC cannot guarantee it.
144 * If you do (A) and not (B), then you might get a seg-fault,
145 by indexing at some bizarre location. Trac #1610
147 * If you do (B) but not (A), you may get no complaint when you index
148 an array out of its semantic bounds. Trac #2120
150 At various times we have had (A) and not (B), or (B) and not (A); both
151 led to complaints. So now we implement *both* checks (Trac #2669).
153 For 1-d, 2-d, and 3-d arrays of Int we have specialised instances to avoid this.
155 Note [Out-of-bounds error messages]
156 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
157 The default method for 'index' generates hoplelessIndexError, because
158 Ix doesn't have Show as a superclass. For particular base types we
159 can do better, so we override the default method for index.
162 -- Abstract these errors from the relevant index functions so that
163 -- the guts of the function will be small enough to inline.
165 {-# NOINLINE indexError #-}
166 indexError :: Show a => (a,a) -> a -> String -> b
168 = error (showString "Ix{" . showString tp . showString "}.index: Index " .
169 showParen True (showsPrec 0 i) .
170 showString " out of range " $
171 showParen True (showsPrec 0 rng) "")
173 hopelessIndexError :: Int -- Try to use 'indexError' instead!
174 hopelessIndexError = error "Error in array index"
176 ----------------------------------------------------------------------
177 instance Ix Char where
181 {-# INLINE unsafeIndex #-}
182 unsafeIndex (m,_n) i = fromEnum i - fromEnum m
184 {-# INLINE index #-} -- See Note [Out-of-bounds error messages]
185 -- and Note [Inlining index]
186 index b i | inRange b i = unsafeIndex b i
187 | otherwise = indexError b i "Char"
189 inRange (m,n) i = m <= i && i <= n
191 ----------------------------------------------------------------------
192 instance Ix Int where
194 -- The INLINE stops the build in the RHS from getting inlined,
195 -- so that callers can fuse with the result of range
198 {-# INLINE unsafeIndex #-}
199 unsafeIndex (m,_n) i = i - m
201 {-# INLINE index #-} -- See Note [Out-of-bounds error messages]
202 -- and Note [Inlining index]
203 index b i | inRange b i = unsafeIndex b i
204 | otherwise = indexError b i "Int"
206 {-# INLINE inRange #-}
207 inRange (I# m,I# n) (I# i) = m <=# i && i <=# n
209 ----------------------------------------------------------------------
210 instance Ix Integer where
214 {-# INLINE unsafeIndex #-}
215 unsafeIndex (m,_n) i = fromInteger (i - m)
217 {-# INLINE index #-} -- See Note [Out-of-bounds error messages]
218 -- and Note [Inlining index]
219 index b i | inRange b i = unsafeIndex b i
220 | otherwise = indexError b i "Integer"
222 inRange (m,n) i = m <= i && i <= n
224 ----------------------------------------------------------------------
225 instance Ix Bool where -- as derived
229 {-# INLINE unsafeIndex #-}
230 unsafeIndex (l,_) i = fromEnum i - fromEnum l
232 {-# INLINE index #-} -- See Note [Out-of-bounds error messages]
233 -- and Note [Inlining index]
234 index b i | inRange b i = unsafeIndex b i
235 | otherwise = indexError b i "Bool"
237 inRange (l,u) i = fromEnum i >= fromEnum l && fromEnum i <= fromEnum u
239 ----------------------------------------------------------------------
240 instance Ix Ordering where -- as derived
244 {-# INLINE unsafeIndex #-}
245 unsafeIndex (l,_) i = fromEnum i - fromEnum l
247 {-# INLINE index #-} -- See Note [Out-of-bounds error messages]
248 -- and Note [Inlining index]
249 index b i | inRange b i = unsafeIndex b i
250 | otherwise = indexError b i "Ordering"
252 inRange (l,u) i = fromEnum i >= fromEnum l && fromEnum i <= fromEnum u
254 ----------------------------------------------------------------------
257 range ((), ()) = [()]
258 {-# INLINE unsafeIndex #-}
259 unsafeIndex ((), ()) () = 0
260 {-# INLINE inRange #-}
261 inRange ((), ()) () = True
263 {-# INLINE index #-} -- See Note [Inlining index]
264 index b i = unsafeIndex b i
266 ----------------------------------------------------------------------
267 instance (Ix a, Ix b) => Ix (a, b) where -- as derived
268 {-# SPECIALISE instance Ix (Int,Int) #-}
271 range ((l1,l2),(u1,u2)) =
272 [ (i1,i2) | i1 <- range (l1,u1), i2 <- range (l2,u2) ]
274 {-# INLINE unsafeIndex #-}
275 unsafeIndex ((l1,l2),(u1,u2)) (i1,i2) =
276 unsafeIndex (l1,u1) i1 * unsafeRangeSize (l2,u2) + unsafeIndex (l2,u2) i2
278 {-# INLINE inRange #-}
279 inRange ((l1,l2),(u1,u2)) (i1,i2) =
280 inRange (l1,u1) i1 && inRange (l2,u2) i2
282 -- Default method for index
284 ----------------------------------------------------------------------
285 instance (Ix a1, Ix a2, Ix a3) => Ix (a1,a2,a3) where
286 {-# SPECIALISE instance Ix (Int,Int,Int) #-}
288 range ((l1,l2,l3),(u1,u2,u3)) =
289 [(i1,i2,i3) | i1 <- range (l1,u1),
293 unsafeIndex ((l1,l2,l3),(u1,u2,u3)) (i1,i2,i3) =
294 unsafeIndex (l3,u3) i3 + unsafeRangeSize (l3,u3) * (
295 unsafeIndex (l2,u2) i2 + unsafeRangeSize (l2,u2) * (
296 unsafeIndex (l1,u1) i1))
298 inRange ((l1,l2,l3),(u1,u2,u3)) (i1,i2,i3) =
299 inRange (l1,u1) i1 && inRange (l2,u2) i2 &&
302 -- Default method for index
304 ----------------------------------------------------------------------
305 instance (Ix a1, Ix a2, Ix a3, Ix a4) => Ix (a1,a2,a3,a4) where
306 range ((l1,l2,l3,l4),(u1,u2,u3,u4)) =
307 [(i1,i2,i3,i4) | i1 <- range (l1,u1),
312 unsafeIndex ((l1,l2,l3,l4),(u1,u2,u3,u4)) (i1,i2,i3,i4) =
313 unsafeIndex (l4,u4) i4 + unsafeRangeSize (l4,u4) * (
314 unsafeIndex (l3,u3) i3 + unsafeRangeSize (l3,u3) * (
315 unsafeIndex (l2,u2) i2 + unsafeRangeSize (l2,u2) * (
316 unsafeIndex (l1,u1) i1)))
318 inRange ((l1,l2,l3,l4),(u1,u2,u3,u4)) (i1,i2,i3,i4) =
319 inRange (l1,u1) i1 && inRange (l2,u2) i2 &&
320 inRange (l3,u3) i3 && inRange (l4,u4) i4
322 -- Default method for index
324 instance (Ix a1, Ix a2, Ix a3, Ix a4, Ix a5) => Ix (a1,a2,a3,a4,a5) where
325 range ((l1,l2,l3,l4,l5),(u1,u2,u3,u4,u5)) =
326 [(i1,i2,i3,i4,i5) | i1 <- range (l1,u1),
332 unsafeIndex ((l1,l2,l3,l4,l5),(u1,u2,u3,u4,u5)) (i1,i2,i3,i4,i5) =
333 unsafeIndex (l5,u5) i5 + unsafeRangeSize (l5,u5) * (
334 unsafeIndex (l4,u4) i4 + unsafeRangeSize (l4,u4) * (
335 unsafeIndex (l3,u3) i3 + unsafeRangeSize (l3,u3) * (
336 unsafeIndex (l2,u2) i2 + unsafeRangeSize (l2,u2) * (
337 unsafeIndex (l1,u1) i1))))
339 inRange ((l1,l2,l3,l4,l5),(u1,u2,u3,u4,u5)) (i1,i2,i3,i4,i5) =
340 inRange (l1,u1) i1 && inRange (l2,u2) i2 &&
341 inRange (l3,u3) i3 && inRange (l4,u4) i4 &&
344 -- Default method for index
347 %*********************************************************
349 \subsection{The @Array@ types}
351 %*********************************************************
354 type IPr = (Int, Int)
356 -- | The type of immutable non-strict (boxed) arrays
357 -- with indices in @i@ and elements in @e@.
358 data Ix i => Array i e
359 = Array !i -- the lower bound, l
360 !i -- the upper bound, u
361 !Int -- a cache of (rangeSize (l,u))
362 -- used to make sure an index is
364 (Array# e) -- The actual elements
366 -- | Mutable, boxed, non-strict arrays in the 'ST' monad. The type
367 -- arguments are as follows:
369 -- * @s@: the state variable argument for the 'ST' type
371 -- * @i@: the index type of the array (should be an instance of 'Ix')
373 -- * @e@: the element type of the array.
376 = STArray !i -- the lower bound, l
377 !i -- the upper bound, u
378 !Int -- a cache of (rangeSize (l,u))
379 -- used to make sure an index is
381 (MutableArray# s e) -- The actual elements
382 -- No Ix context for STArray. They are stupid,
383 -- and force an Ix context on the equality instance.
385 -- Just pointer equality on mutable arrays:
386 instance Eq (STArray s i e) where
387 STArray _ _ _ arr1# == STArray _ _ _ arr2# =
388 sameMutableArray# arr1# arr2#
392 %*********************************************************
394 \subsection{Operations on immutable arrays}
396 %*********************************************************
399 {-# NOINLINE arrEleBottom #-}
401 arrEleBottom = error "(Array.!): undefined array element"
403 -- | Construct an array with the specified bounds and containing values
404 -- for given indices within these bounds.
406 -- The array is undefined (i.e. bottom) if any index in the list is
407 -- out of bounds. The Haskell 98 Report further specifies that if any
408 -- two associations in the list have the same index, the value at that
409 -- index is undefined (i.e. bottom). However in GHC's implementation,
410 -- the value at such an index is the value part of the last association
411 -- with that index in the list.
413 -- Because the indices must be checked for these errors, 'array' is
414 -- strict in the bounds argument and in the indices of the association
415 -- list, but non-strict in the values. Thus, recurrences such as the
416 -- following are possible:
418 -- > a = array (1,100) ((1,1) : [(i, i * a!(i-1)) | i <- [2..100]])
420 -- Not every index within the bounds of the array need appear in the
421 -- association list, but the values associated with indices that do not
422 -- appear will be undefined (i.e. bottom).
424 -- If, in any dimension, the lower bound is greater than the upper bound,
425 -- then the array is legal, but empty. Indexing an empty array always
426 -- gives an array-bounds error, but 'bounds' still yields the bounds
427 -- with which the array was constructed.
430 => (i,i) -- ^ a pair of /bounds/, each of the index type
431 -- of the array. These bounds are the lowest and
432 -- highest indices in the array, in that order.
433 -- For example, a one-origin vector of length
434 -- '10' has bounds '(1,10)', and a one-origin '10'
435 -- by '10' matrix has bounds '((1,1),(10,10))'.
436 -> [(i, e)] -- ^ a list of /associations/ of the form
437 -- (/index/, /value/). Typically, this list will
438 -- be expressed as a comprehension. An
439 -- association '(i, x)' defines the value of
440 -- the array at index 'i' to be 'x'.
443 = let n = safeRangeSize (l,u)
444 in unsafeArray' (l,u) n
445 [(safeIndex (l,u) n i, e) | (i, e) <- ies]
447 {-# INLINE unsafeArray #-}
448 unsafeArray :: Ix i => (i,i) -> [(Int, e)] -> Array i e
449 unsafeArray b ies = unsafeArray' b (rangeSize b) ies
451 {-# INLINE unsafeArray' #-}
452 unsafeArray' :: Ix i => (i,i) -> Int -> [(Int, e)] -> Array i e
453 unsafeArray' (l,u) n@(I# n#) ies = runST (ST $ \s1# ->
454 case newArray# n# arrEleBottom s1# of
456 foldr (fill marr#) (done l u n marr#) ies s2#)
459 fill :: MutableArray# s e -> (Int, e) -> STRep s a -> STRep s a
460 -- NB: put the \s after the "=" so that 'fill'
461 -- inlines when applied to three args
462 fill marr# (I# i#, e) next
463 = \s1# -> case writeArray# marr# i# e s1# of
467 done :: Ix i => i -> i -> Int -> MutableArray# s e -> STRep s (Array i e)
470 = \s1# -> case unsafeFreezeArray# marr# s1# of
471 (# s2#, arr# #) -> (# s2#, Array l u n arr# #)
473 -- This is inefficient and I'm not sure why:
474 -- listArray (l,u) es = unsafeArray (l,u) (zip [0 .. rangeSize (l,u) - 1] es)
475 -- The code below is better. It still doesn't enable foldr/build
476 -- transformation on the list of elements; I guess it's impossible
477 -- using mechanisms currently available.
479 -- | Construct an array from a pair of bounds and a list of values in
481 {-# INLINE listArray #-}
482 listArray :: Ix i => (i,i) -> [e] -> Array i e
483 listArray (l,u) es = runST (ST $ \s1# ->
484 case safeRangeSize (l,u) of { n@(I# n#) ->
485 case newArray# n# arrEleBottom s1# of { (# s2#, marr# #) ->
486 let fillFromList i# xs s3# | i# ==# n# = s3#
487 | otherwise = case xs of
489 y:ys -> case writeArray# marr# i# y s3# of { s4# ->
490 fillFromList (i# +# 1#) ys s4# } in
491 case fillFromList 0# es s2# of { s3# ->
492 done l u n marr# s3# }}})
494 -- | The value at the given index in an array.
496 (!) :: Ix i => Array i e -> i -> e
497 arr@(Array l u n _) ! i = unsafeAt arr $ safeIndex (l,u) n i
499 {-# INLINE safeRangeSize #-}
500 safeRangeSize :: Ix i => (i, i) -> Int
501 safeRangeSize (l,u) = let r = rangeSize (l, u)
502 in if r < 0 then negRange
505 -- Don't inline this error message everywhere!!
506 negRange :: Int -- Uninformative, but Ix does not provide Show
507 negRange = error "Negative range size"
509 {-# INLINE[1] safeIndex #-}
510 -- See Note [Double bounds-checking of index values]
511 -- Inline *after* (!) so the rules can fire
512 safeIndex :: Ix i => (i, i) -> Int -> i -> Int
513 safeIndex (l,u) n i = let i' = index (l,u) i
514 in if (0 <= i') && (i' < n)
516 else badSafeIndex i' n
518 -- See Note [Double bounds-checking of index values]
520 "safeIndex/I" safeIndex = lessSafeIndex :: (Int,Int) -> Int -> Int -> Int
521 "safeIndex/(I,I)" safeIndex = lessSafeIndex :: ((Int,Int),(Int,Int)) -> Int -> (Int,Int) -> Int
522 "safeIndex/(I,I,I)" safeIndex = lessSafeIndex :: ((Int,Int,Int),(Int,Int,Int)) -> Int -> (Int,Int,Int) -> Int
525 lessSafeIndex :: Ix i => (i, i) -> Int -> i -> Int
526 -- See Note [Double bounds-checking of index values]
527 -- Do only (A), the semantic check
528 lessSafeIndex (l,u) _ i = index (l,u) i
530 -- Don't inline this long error message everywhere!!
531 badSafeIndex :: Int -> Int -> Int
532 badSafeIndex i' n = error ("Error in array index; " ++ show i' ++
533 " not in range [0.." ++ show n ++ ")")
535 {-# INLINE unsafeAt #-}
536 unsafeAt :: Ix i => Array i e -> Int -> e
537 unsafeAt (Array _ _ _ arr#) (I# i#) =
538 case indexArray# arr# i# of (# e #) -> e
540 -- | The bounds with which an array was constructed.
541 {-# INLINE bounds #-}
542 bounds :: Ix i => Array i e -> (i,i)
543 bounds (Array l u _ _) = (l,u)
545 -- | The number of elements in the array.
546 {-# INLINE numElements #-}
547 numElements :: Ix i => Array i e -> Int
548 numElements (Array _ _ n _) = n
550 -- | The list of indices of an array in ascending order.
551 {-# INLINE indices #-}
552 indices :: Ix i => Array i e -> [i]
553 indices (Array l u _ _) = range (l,u)
555 -- | The list of elements of an array in index order.
557 elems :: Ix i => Array i e -> [e]
558 elems arr@(Array _ _ n _) =
559 [unsafeAt arr i | i <- [0 .. n - 1]]
561 -- | The list of associations of an array in index order.
562 {-# INLINE assocs #-}
563 assocs :: Ix i => Array i e -> [(i, e)]
564 assocs arr@(Array l u _ _) =
565 [(i, arr ! i) | i <- range (l,u)]
567 -- | The 'accumArray' function deals with repeated indices in the association
568 -- list using an /accumulating function/ which combines the values of
569 -- associations with the same index.
570 -- For example, given a list of values of some index type, @hist@
571 -- produces a histogram of the number of occurrences of each index within
572 -- a specified range:
574 -- > hist :: (Ix a, Num b) => (a,a) -> [a] -> Array a b
575 -- > hist bnds is = accumArray (+) 0 bnds [(i, 1) | i<-is, inRange bnds i]
577 -- If the accumulating function is strict, then 'accumArray' is strict in
578 -- the values, as well as the indices, in the association list. Thus,
579 -- unlike ordinary arrays built with 'array', accumulated arrays should
580 -- not in general be recursive.
581 {-# INLINE accumArray #-}
583 => (e -> a -> e) -- ^ accumulating function
584 -> e -- ^ initial value
585 -> (i,i) -- ^ bounds of the array
586 -> [(i, a)] -- ^ association list
588 accumArray f initial (l,u) ies =
589 let n = safeRangeSize (l,u)
590 in unsafeAccumArray' f initial (l,u) n
591 [(safeIndex (l,u) n i, e) | (i, e) <- ies]
593 {-# INLINE unsafeAccumArray #-}
594 unsafeAccumArray :: Ix i => (e -> a -> e) -> e -> (i,i) -> [(Int, a)] -> Array i e
595 unsafeAccumArray f initial b ies = unsafeAccumArray' f initial b (rangeSize b) ies
597 {-# INLINE unsafeAccumArray' #-}
598 unsafeAccumArray' :: Ix i => (e -> a -> e) -> e -> (i,i) -> Int -> [(Int, a)] -> Array i e
599 unsafeAccumArray' f initial (l,u) n@(I# n#) ies = runST (ST $ \s1# ->
600 case newArray# n# initial s1# of { (# s2#, marr# #) ->
601 foldr (adjust f marr#) (done l u n marr#) ies s2# })
603 {-# INLINE adjust #-}
604 adjust :: (e -> a -> e) -> MutableArray# s e -> (Int, a) -> STRep s b -> STRep s b
606 adjust f marr# (I# i#, new) next
607 = \s1# -> case readArray# marr# i# s1# of
609 case writeArray# marr# i# (f old new) s2# of
612 -- | Constructs an array identical to the first argument except that it has
613 -- been updated by the associations in the right argument.
614 -- For example, if @m@ is a 1-origin, @n@ by @n@ matrix, then
616 -- > m//[((i,i), 0) | i <- [1..n]]
618 -- is the same matrix, except with the diagonal zeroed.
620 -- Repeated indices in the association list are handled as for 'array':
621 -- Haskell 98 specifies that the resulting array is undefined (i.e. bottom),
622 -- but GHC's implementation uses the last association for each index.
624 (//) :: Ix i => Array i e -> [(i, e)] -> Array i e
625 arr@(Array l u n _) // ies =
626 unsafeReplace arr [(safeIndex (l,u) n i, e) | (i, e) <- ies]
628 {-# INLINE unsafeReplace #-}
629 unsafeReplace :: Ix i => Array i e -> [(Int, e)] -> Array i e
630 unsafeReplace arr ies = runST (do
631 STArray l u n marr# <- thawSTArray arr
632 ST (foldr (fill marr#) (done l u n marr#) ies))
634 -- | @'accum' f@ takes an array and an association list and accumulates
635 -- pairs from the list into the array with the accumulating function @f@.
636 -- Thus 'accumArray' can be defined using 'accum':
638 -- > accumArray f z b = accum f (array b [(i, z) | i <- range b])
641 accum :: Ix i => (e -> a -> e) -> Array i e -> [(i, a)] -> Array i e
642 accum f arr@(Array l u n _) ies =
643 unsafeAccum f arr [(safeIndex (l,u) n i, e) | (i, e) <- ies]
645 {-# INLINE unsafeAccum #-}
646 unsafeAccum :: Ix i => (e -> a -> e) -> Array i e -> [(Int, a)] -> Array i e
647 unsafeAccum f arr ies = runST (do
648 STArray l u n marr# <- thawSTArray arr
649 ST (foldr (adjust f marr#) (done l u n marr#) ies))
652 amap :: Ix i => (a -> b) -> Array i a -> Array i b
653 amap f arr@(Array l u n _) =
654 unsafeArray' (l,u) n [(i, f (unsafeAt arr i)) | i <- [0 .. n - 1]]
656 -- | 'ixmap' allows for transformations on array indices.
657 -- It may be thought of as providing function composition on the right
658 -- with the mapping that the original array embodies.
660 -- A similar transformation of array values may be achieved using 'fmap'
661 -- from the 'Array' instance of the 'Functor' class.
663 ixmap :: (Ix i, Ix j) => (i,i) -> (i -> j) -> Array j e -> Array i e
665 array (l,u) [(i, arr ! f i) | i <- range (l,u)]
667 {-# INLINE eqArray #-}
668 eqArray :: (Ix i, Eq e) => Array i e -> Array i e -> Bool
669 eqArray arr1@(Array l1 u1 n1 _) arr2@(Array l2 u2 n2 _) =
670 if n1 == 0 then n2 == 0 else
671 l1 == l2 && u1 == u2 &&
672 and [unsafeAt arr1 i == unsafeAt arr2 i | i <- [0 .. n1 - 1]]
674 {-# INLINE cmpArray #-}
675 cmpArray :: (Ix i, Ord e) => Array i e -> Array i e -> Ordering
676 cmpArray arr1 arr2 = compare (assocs arr1) (assocs arr2)
678 {-# INLINE cmpIntArray #-}
679 cmpIntArray :: Ord e => Array Int e -> Array Int e -> Ordering
680 cmpIntArray arr1@(Array l1 u1 n1 _) arr2@(Array l2 u2 n2 _) =
682 if n2 == 0 then EQ else LT
683 else if n2 == 0 then GT
684 else case compare l1 l2 of
685 EQ -> foldr cmp (compare u1 u2) [0 .. (n1 `min` n2) - 1]
688 cmp i rest = case compare (unsafeAt arr1 i) (unsafeAt arr2 i) of
692 {-# RULES "cmpArray/Int" cmpArray = cmpIntArray #-}
696 %*********************************************************
698 \subsection{Array instances}
700 %*********************************************************
703 instance Ix i => Functor (Array i) where
706 instance (Ix i, Eq e) => Eq (Array i e) where
709 instance (Ix i, Ord e) => Ord (Array i e) where
712 instance (Ix a, Show a, Show b) => Show (Array a b) where
714 showParen (p > appPrec) $
715 showString "array " .
716 showsPrec appPrec1 (bounds a) .
718 showsPrec appPrec1 (assocs a)
719 -- Precedence of 'array' is the precedence of application
721 -- The Read instance is in GHC.Read
725 %*********************************************************
727 \subsection{Operations on mutable arrays}
729 %*********************************************************
731 Idle ADR question: What's the tradeoff here between flattening these
732 datatypes into @STArray ix ix (MutableArray# s elt)@ and using
733 it as is? As I see it, the former uses slightly less heap and
734 provides faster access to the individual parts of the bounds while the
735 code used has the benefit of providing a ready-made @(lo, hi)@ pair as
736 required by many array-related functions. Which wins? Is the
737 difference significant (probably not).
739 Idle AJG answer: When I looked at the outputted code (though it was 2
740 years ago) it seems like you often needed the tuple, and we build
741 it frequently. Now we've got the overloading specialiser things
742 might be different, though.
745 {-# INLINE newSTArray #-}
746 newSTArray :: Ix i => (i,i) -> e -> ST s (STArray s i e)
747 newSTArray (l,u) initial = ST $ \s1# ->
748 case safeRangeSize (l,u) of { n@(I# n#) ->
749 case newArray# n# initial s1# of { (# s2#, marr# #) ->
750 (# s2#, STArray l u n marr# #) }}
752 {-# INLINE boundsSTArray #-}
753 boundsSTArray :: STArray s i e -> (i,i)
754 boundsSTArray (STArray l u _ _) = (l,u)
756 {-# INLINE numElementsSTArray #-}
757 numElementsSTArray :: STArray s i e -> Int
758 numElementsSTArray (STArray _ _ n _) = n
760 {-# INLINE readSTArray #-}
761 readSTArray :: Ix i => STArray s i e -> i -> ST s e
762 readSTArray marr@(STArray l u n _) i =
763 unsafeReadSTArray marr (safeIndex (l,u) n i)
765 {-# INLINE unsafeReadSTArray #-}
766 unsafeReadSTArray :: Ix i => STArray s i e -> Int -> ST s e
767 unsafeReadSTArray (STArray _ _ _ marr#) (I# i#)
768 = ST $ \s1# -> readArray# marr# i# s1#
770 {-# INLINE writeSTArray #-}
771 writeSTArray :: Ix i => STArray s i e -> i -> e -> ST s ()
772 writeSTArray marr@(STArray l u n _) i e =
773 unsafeWriteSTArray marr (safeIndex (l,u) n i) e
775 {-# INLINE unsafeWriteSTArray #-}
776 unsafeWriteSTArray :: Ix i => STArray s i e -> Int -> e -> ST s ()
777 unsafeWriteSTArray (STArray _ _ _ marr#) (I# i#) e = ST $ \s1# ->
778 case writeArray# marr# i# e s1# of
783 %*********************************************************
785 \subsection{Moving between mutable and immutable}
787 %*********************************************************
790 freezeSTArray :: Ix i => STArray s i e -> ST s (Array i e)
791 freezeSTArray (STArray l u n@(I# n#) marr#) = ST $ \s1# ->
792 case newArray# n# arrEleBottom s1# of { (# s2#, marr'# #) ->
793 let copy i# s3# | i# ==# n# = s3#
795 case readArray# marr# i# s3# of { (# s4#, e #) ->
796 case writeArray# marr'# i# e s4# of { s5# ->
797 copy (i# +# 1#) s5# }} in
798 case copy 0# s2# of { s3# ->
799 case unsafeFreezeArray# marr'# s3# of { (# s4#, arr# #) ->
800 (# s4#, Array l u n arr# #) }}}
802 {-# INLINE unsafeFreezeSTArray #-}
803 unsafeFreezeSTArray :: Ix i => STArray s i e -> ST s (Array i e)
804 unsafeFreezeSTArray (STArray l u n marr#) = ST $ \s1# ->
805 case unsafeFreezeArray# marr# s1# of { (# s2#, arr# #) ->
806 (# s2#, Array l u n arr# #) }
808 thawSTArray :: Ix i => Array i e -> ST s (STArray s i e)
809 thawSTArray (Array l u n@(I# n#) arr#) = ST $ \s1# ->
810 case newArray# n# arrEleBottom s1# of { (# s2#, marr# #) ->
811 let copy i# s3# | i# ==# n# = s3#
813 case indexArray# arr# i# of { (# e #) ->
814 case writeArray# marr# i# e s3# of { s4# ->
815 copy (i# +# 1#) s4# }} in
816 case copy 0# s2# of { s3# ->
817 (# s3#, STArray l u n marr# #) }}
819 {-# INLINE unsafeThawSTArray #-}
820 unsafeThawSTArray :: Ix i => Array i e -> ST s (STArray s i e)
821 unsafeThawSTArray (Array l u n arr#) = ST $ \s1# ->
822 case unsafeThawArray# arr# s1# of { (# s2#, marr# #) ->
823 (# s2#, STArray l u n marr# #) }