Trailing whitespaces
[ghc.git] / libraries / base / GHC / Arr.lhs
1 \begin{code}
2 {-# LANGUAGE Unsafe #-}
3 {-# LANGUAGE NoImplicitPrelude, NoBangPatterns, MagicHash, UnboxedTuples #-}
4 {-# OPTIONS_GHC -funbox-strict-fields #-}
5 {-# OPTIONS_HADDOCK hide #-}
6
7 -----------------------------------------------------------------------------
8 -- |
9 -- Module      :  GHC.Arr
10 -- Copyright   :  (c) The University of Glasgow, 1994-2000
11 -- License     :  see libraries/base/LICENSE
12 --
13 -- Maintainer  :  cvs-ghc@haskell.org
14 -- Stability   :  internal
15 -- Portability :  non-portable (GHC extensions)
16 --
17 -- GHC\'s array implementation.
18 --
19 -----------------------------------------------------------------------------
20
21 -- #hide
22 module GHC.Arr (
23         Ix(..), Array(..), STArray(..),
24
25         indexError, hopelessIndexError,
26         arrEleBottom, array, listArray,
27         (!), safeRangeSize, negRange, safeIndex, badSafeIndex,
28         bounds, numElements, numElementsSTArray, indices, elems,
29         assocs, accumArray, adjust, (//), accum,
30         amap, ixmap,
31         eqArray, cmpArray, cmpIntArray,
32         newSTArray, boundsSTArray,
33         readSTArray, writeSTArray,
34         freezeSTArray, thawSTArray,
35
36         -- * Unsafe operations
37         fill, done,
38         unsafeArray, unsafeArray',
39         lessSafeIndex, unsafeAt, unsafeReplace,
40         unsafeAccumArray, unsafeAccumArray', unsafeAccum,
41         unsafeReadSTArray, unsafeWriteSTArray,
42         unsafeFreezeSTArray, unsafeThawSTArray,
43     ) where
44
45 import GHC.Enum
46 import GHC.Num
47 import GHC.ST
48 import GHC.Base
49 import GHC.List
50 import GHC.Real( fromIntegral )
51 import GHC.Show
52
53 infixl 9  !, //
54
55 default ()
56 \end{code}
57
58
59 %*********************************************************
60 %*                                                      *
61 \subsection{The @Ix@ class}
62 %*                                                      *
63 %*********************************************************
64
65 \begin{code}
66 -- | The 'Ix' class is used to map a contiguous subrange of values in
67 -- a type onto integers.  It is used primarily for array indexing
68 -- (see the array package).
69 --
70 -- The first argument @(l,u)@ of each of these operations is a pair
71 -- specifying the lower and upper bounds of a contiguous subrange of values.
72 --
73 -- An implementation is entitled to assume the following laws about these
74 -- operations:
75 --
76 -- * @'inRange' (l,u) i == 'elem' i ('range' (l,u))@ @ @
77 --
78 -- * @'range' (l,u) '!!' 'index' (l,u) i == i@, when @'inRange' (l,u) i@
79 --
80 -- * @'map' ('index' (l,u)) ('range' (l,u))) == [0..'rangeSize' (l,u)-1]@ @ @
81 --
82 -- * @'rangeSize' (l,u) == 'length' ('range' (l,u))@ @ @
83 --
84 -- Minimal complete instance: 'range', 'index' and 'inRange'.
85 --
86 class (Ord a) => Ix a where
87     -- | The list of values in the subrange defined by a bounding pair.
88     range               :: (a,a) -> [a]
89     -- | The position of a subscript in the subrange.
90     index               :: (a,a) -> a -> Int
91     -- | Like 'index', but without checking that the value is in range.
92     unsafeIndex         :: (a,a) -> a -> Int
93     -- | Returns 'True' the given subscript lies in the range defined
94     -- the bounding pair.
95     inRange             :: (a,a) -> a -> Bool
96     -- | The size of the subrange defined by a bounding pair.
97     rangeSize           :: (a,a) -> Int
98     -- | like 'rangeSize', but without checking that the upper bound is
99     -- in range.
100     unsafeRangeSize     :: (a,a) -> Int
101
102         -- Must specify one of index, unsafeIndex
103
104         -- 'index' is typically over-ridden in instances, with essentially
105         -- the same code, but using indexError instead of hopelessIndexError
106         -- Reason: we have 'Show' at the instances
107     {-# INLINE index #-}  -- See Note [Inlining index]
108     index b i | inRange b i = unsafeIndex b i
109               | otherwise   = hopelessIndexError
110
111     unsafeIndex b i = index b i
112
113     rangeSize b@(_l,h) | inRange b h = unsafeIndex b h + 1
114                        | otherwise   = 0        -- This case is only here to
115                                                 -- check for an empty range
116         -- NB: replacing (inRange b h) by (l <= h) fails for
117         --     tuples.  E.g.  (1,2) <= (2,1) but the range is empty
118
119     unsafeRangeSize b@(_l,h) = unsafeIndex b h + 1
120 \end{code}
121
122 Note that the following is NOT right
123         rangeSize (l,h) | l <= h    = index b h + 1
124                         | otherwise = 0
125
126 Because it might be the case that l<h, but the range
127 is nevertheless empty.  Consider
128         ((1,2),(2,1))
129 Here l<h, but the second index ranges from 2..1 and
130 hence is empty
131
132 %*********************************************************
133 %*                                                      *
134 \subsection{Instances of @Ix@}
135 %*                                                      *
136 %*********************************************************
137
138 Note [Inlining index]
139 ~~~~~~~~~~~~~~~~~~~~~
140 We inline the 'index' operation,
141
142  * Partly because it generates much faster code
143    (although bigger); see Trac #1216
144
145  * Partly because it exposes the bounds checks to the simplifier which
146    might help a big.
147
148 If you make a per-instance index method, you may consider inlining it.
149
150 Note [Double bounds-checking of index values]
151 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
152 When you index an array, a!x, there are two possible bounds checks we might make:
153
154   (A) Check that (inRange (bounds a) x) holds.
155
156       (A) is checked in the method for 'index'
157
158   (B) Check that (index (bounds a) x) lies in the range 0..n,
159       where n is the size of the underlying array
160
161       (B) is checked in the top-level function (!), in safeIndex.
162
163 Of course it *should* be the case that (A) holds iff (B) holds, but that
164 is a property of the particular instances of index, bounds, and inRange,
165 so GHC cannot guarantee it.
166
167  * If you do (A) and not (B), then you might get a seg-fault,
168    by indexing at some bizarre location.  Trac #1610
169
170  * If you do (B) but not (A), you may get no complaint when you index
171    an array out of its semantic bounds.  Trac #2120
172
173 At various times we have had (A) and not (B), or (B) and not (A); both
174 led to complaints.  So now we implement *both* checks (Trac #2669).
175
176 For 1-d, 2-d, and 3-d arrays of Int we have specialised instances to avoid this.
177
178 Note [Out-of-bounds error messages]
179 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
180 The default method for 'index' generates hoplelessIndexError, because
181 Ix doesn't have Show as a superclass.  For particular base types we
182 can do better, so we override the default method for index.
183
184 \begin{code}
185 -- Abstract these errors from the relevant index functions so that
186 -- the guts of the function will be small enough to inline.
187
188 {-# NOINLINE indexError #-}
189 indexError :: Show a => (a,a) -> a -> String -> b
190 indexError rng i tp
191   = error (showString "Ix{" . showString tp . showString "}.index: Index " .
192            showParen True (showsPrec 0 i) .
193            showString " out of range " $
194            showParen True (showsPrec 0 rng) "")
195
196 hopelessIndexError :: Int -- Try to use 'indexError' instead!
197 hopelessIndexError = error "Error in array index"
198
199 ----------------------------------------------------------------------
200 instance  Ix Char  where
201     {-# INLINE range #-}
202     range (m,n) = [m..n]
203
204     {-# INLINE unsafeIndex #-}
205     unsafeIndex (m,_n) i = fromEnum i - fromEnum m
206
207     {-# INLINE index #-}  -- See Note [Out-of-bounds error messages]
208                           -- and Note [Inlining index]
209     index b i | inRange b i =  unsafeIndex b i
210               | otherwise   =  indexError b i "Char"
211
212     inRange (m,n) i     =  m <= i && i <= n
213
214 ----------------------------------------------------------------------
215 instance  Ix Int  where
216     {-# INLINE range #-}
217         -- The INLINE stops the build in the RHS from getting inlined,
218         -- so that callers can fuse with the result of range
219     range (m,n) = [m..n]
220
221     {-# INLINE unsafeIndex #-}
222     unsafeIndex (m,_n) i = i - m
223
224     {-# INLINE index #-}  -- See Note [Out-of-bounds error messages]
225                           -- and Note [Inlining index]
226     index b i | inRange b i =  unsafeIndex b i
227               | otherwise   =  indexError b i "Int"
228
229     {-# INLINE inRange #-}
230     inRange (I# m,I# n) (I# i) =  m <=# i && i <=# n
231
232 instance Ix Word where
233     range (m,n)         = [m..n]
234     unsafeIndex (m,_) i = fromIntegral (i - m)
235     inRange (m,n) i     = m <= i && i <= n
236
237 ----------------------------------------------------------------------
238 instance  Ix Integer  where
239     {-# INLINE range #-}
240     range (m,n) = [m..n]
241
242     {-# INLINE unsafeIndex #-}
243     unsafeIndex (m,_n) i   = fromInteger (i - m)
244
245     {-# INLINE index #-}  -- See Note [Out-of-bounds error messages]
246                           -- and Note [Inlining index]
247     index b i | inRange b i =  unsafeIndex b i
248               | otherwise   =  indexError b i "Integer"
249
250     inRange (m,n) i     =  m <= i && i <= n
251
252 ----------------------------------------------------------------------
253 instance Ix Bool where -- as derived
254     {-# INLINE range #-}
255     range (m,n) = [m..n]
256
257     {-# INLINE unsafeIndex #-}
258     unsafeIndex (l,_) i = fromEnum i - fromEnum l
259
260     {-# INLINE index #-}  -- See Note [Out-of-bounds error messages]
261                           -- and Note [Inlining index]
262     index b i | inRange b i =  unsafeIndex b i
263               | otherwise   =  indexError b i "Bool"
264
265     inRange (l,u) i = fromEnum i >= fromEnum l && fromEnum i <= fromEnum u
266
267 ----------------------------------------------------------------------
268 instance Ix Ordering where -- as derived
269     {-# INLINE range #-}
270     range (m,n) = [m..n]
271
272     {-# INLINE unsafeIndex #-}
273     unsafeIndex (l,_) i = fromEnum i - fromEnum l
274
275     {-# INLINE index #-}  -- See Note [Out-of-bounds error messages]
276                           -- and Note [Inlining index]
277     index b i | inRange b i =  unsafeIndex b i
278               | otherwise   =  indexError b i "Ordering"
279
280     inRange (l,u) i = fromEnum i >= fromEnum l && fromEnum i <= fromEnum u
281
282 ----------------------------------------------------------------------
283 instance Ix () where
284     {-# INLINE range #-}
285     range   ((), ())    = [()]
286     {-# INLINE unsafeIndex #-}
287     unsafeIndex   ((), ()) () = 0
288     {-# INLINE inRange #-}
289     inRange ((), ()) () = True
290
291     {-# INLINE index #-}  -- See Note [Inlining index]
292     index b i = unsafeIndex b i
293
294 ----------------------------------------------------------------------
295 instance (Ix a, Ix b) => Ix (a, b) where -- as derived
296     {-# SPECIALISE instance Ix (Int,Int) #-}
297
298     {-# INLINE range #-}
299     range ((l1,l2),(u1,u2)) =
300       [ (i1,i2) | i1 <- range (l1,u1), i2 <- range (l2,u2) ]
301
302     {-# INLINE unsafeIndex #-}
303     unsafeIndex ((l1,l2),(u1,u2)) (i1,i2) =
304       unsafeIndex (l1,u1) i1 * unsafeRangeSize (l2,u2) + unsafeIndex (l2,u2) i2
305
306     {-# INLINE inRange #-}
307     inRange ((l1,l2),(u1,u2)) (i1,i2) =
308       inRange (l1,u1) i1 && inRange (l2,u2) i2
309
310     -- Default method for index
311
312 ----------------------------------------------------------------------
313 instance  (Ix a1, Ix a2, Ix a3) => Ix (a1,a2,a3)  where
314     {-# SPECIALISE instance Ix (Int,Int,Int) #-}
315
316     range ((l1,l2,l3),(u1,u2,u3)) =
317         [(i1,i2,i3) | i1 <- range (l1,u1),
318                       i2 <- range (l2,u2),
319                       i3 <- range (l3,u3)]
320
321     unsafeIndex ((l1,l2,l3),(u1,u2,u3)) (i1,i2,i3) =
322       unsafeIndex (l3,u3) i3 + unsafeRangeSize (l3,u3) * (
323       unsafeIndex (l2,u2) i2 + unsafeRangeSize (l2,u2) * (
324       unsafeIndex (l1,u1) i1))
325
326     inRange ((l1,l2,l3),(u1,u2,u3)) (i1,i2,i3) =
327       inRange (l1,u1) i1 && inRange (l2,u2) i2 &&
328       inRange (l3,u3) i3
329
330     -- Default method for index
331
332 ----------------------------------------------------------------------
333 instance  (Ix a1, Ix a2, Ix a3, Ix a4) => Ix (a1,a2,a3,a4)  where
334     range ((l1,l2,l3,l4),(u1,u2,u3,u4)) =
335       [(i1,i2,i3,i4) | i1 <- range (l1,u1),
336                        i2 <- range (l2,u2),
337                        i3 <- range (l3,u3),
338                        i4 <- range (l4,u4)]
339
340     unsafeIndex ((l1,l2,l3,l4),(u1,u2,u3,u4)) (i1,i2,i3,i4) =
341       unsafeIndex (l4,u4) i4 + unsafeRangeSize (l4,u4) * (
342       unsafeIndex (l3,u3) i3 + unsafeRangeSize (l3,u3) * (
343       unsafeIndex (l2,u2) i2 + unsafeRangeSize (l2,u2) * (
344       unsafeIndex (l1,u1) i1)))
345
346     inRange ((l1,l2,l3,l4),(u1,u2,u3,u4)) (i1,i2,i3,i4) =
347       inRange (l1,u1) i1 && inRange (l2,u2) i2 &&
348       inRange (l3,u3) i3 && inRange (l4,u4) i4
349
350     -- Default method for index
351
352 instance  (Ix a1, Ix a2, Ix a3, Ix a4, Ix a5) => Ix (a1,a2,a3,a4,a5)  where
353     range ((l1,l2,l3,l4,l5),(u1,u2,u3,u4,u5)) =
354       [(i1,i2,i3,i4,i5) | i1 <- range (l1,u1),
355                           i2 <- range (l2,u2),
356                           i3 <- range (l3,u3),
357                           i4 <- range (l4,u4),
358                           i5 <- range (l5,u5)]
359
360     unsafeIndex ((l1,l2,l3,l4,l5),(u1,u2,u3,u4,u5)) (i1,i2,i3,i4,i5) =
361       unsafeIndex (l5,u5) i5 + unsafeRangeSize (l5,u5) * (
362       unsafeIndex (l4,u4) i4 + unsafeRangeSize (l4,u4) * (
363       unsafeIndex (l3,u3) i3 + unsafeRangeSize (l3,u3) * (
364       unsafeIndex (l2,u2) i2 + unsafeRangeSize (l2,u2) * (
365       unsafeIndex (l1,u1) i1))))
366
367     inRange ((l1,l2,l3,l4,l5),(u1,u2,u3,u4,u5)) (i1,i2,i3,i4,i5) =
368       inRange (l1,u1) i1 && inRange (l2,u2) i2 &&
369       inRange (l3,u3) i3 && inRange (l4,u4) i4 &&
370       inRange (l5,u5) i5
371
372     -- Default method for index
373 \end{code}
374
375 %*********************************************************
376 %*                                                      *
377 \subsection{The @Array@ types}
378 %*                                                      *
379 %*********************************************************
380
381 \begin{code}
382 -- | The type of immutable non-strict (boxed) arrays
383 -- with indices in @i@ and elements in @e@.
384 data Array i e
385          = Array !i         -- the lower bound, l
386                  !i         -- the upper bound, u
387                  !Int       -- a cache of (rangeSize (l,u))
388                             -- used to make sure an index is
389                             -- really in range
390                  (Array# e) -- The actual elements
391
392 -- | Mutable, boxed, non-strict arrays in the 'ST' monad.  The type
393 -- arguments are as follows:
394 --
395 --  * @s@: the state variable argument for the 'ST' type
396 --
397 --  * @i@: the index type of the array (should be an instance of 'Ix')
398 --
399 --  * @e@: the element type of the array.
400 --
401 data STArray s i e
402          = STArray !i                  -- the lower bound, l
403                    !i                  -- the upper bound, u
404                    !Int                -- a cache of (rangeSize (l,u))
405                                        -- used to make sure an index is
406                                        -- really in range
407                    (MutableArray# s e) -- The actual elements
408         -- No Ix context for STArray.  They are stupid,
409         -- and force an Ix context on the equality instance.
410
411 -- Just pointer equality on mutable arrays:
412 instance Eq (STArray s i e) where
413     STArray _ _ _ arr1# == STArray _ _ _ arr2# =
414         sameMutableArray arr1# arr2#
415 \end{code}
416
417
418 %*********************************************************
419 %*                                                      *
420 \subsection{Operations on immutable arrays}
421 %*                                                      *
422 %*********************************************************
423
424 \begin{code}
425 {-# NOINLINE arrEleBottom #-}
426 arrEleBottom :: a
427 arrEleBottom = error "(Array.!): undefined array element"
428
429 -- | Construct an array with the specified bounds and containing values
430 -- for given indices within these bounds.
431 --
432 -- The array is undefined (i.e. bottom) if any index in the list is
433 -- out of bounds.  The Haskell 2010 Report further specifies that if any
434 -- two associations in the list have the same index, the value at that
435 -- index is undefined (i.e. bottom).  However in GHC's implementation,
436 -- the value at such an index is the value part of the last association
437 -- with that index in the list.
438 --
439 -- Because the indices must be checked for these errors, 'array' is
440 -- strict in the bounds argument and in the indices of the association
441 -- list, but non-strict in the values.  Thus, recurrences such as the
442 -- following are possible:
443 --
444 -- > a = array (1,100) ((1,1) : [(i, i * a!(i-1)) | i <- [2..100]])
445 --
446 -- Not every index within the bounds of the array need appear in the
447 -- association list, but the values associated with indices that do not
448 -- appear will be undefined (i.e. bottom).
449 --
450 -- If, in any dimension, the lower bound is greater than the upper bound,
451 -- then the array is legal, but empty.  Indexing an empty array always
452 -- gives an array-bounds error, but 'bounds' still yields the bounds
453 -- with which the array was constructed.
454 {-# INLINE array #-}
455 array :: Ix i
456         => (i,i)        -- ^ a pair of /bounds/, each of the index type
457                         -- of the array.  These bounds are the lowest and
458                         -- highest indices in the array, in that order.
459                         -- For example, a one-origin vector of length
460                         -- '10' has bounds '(1,10)', and a one-origin '10'
461                         -- by '10' matrix has bounds '((1,1),(10,10))'.
462         -> [(i, e)]     -- ^ a list of /associations/ of the form
463                         -- (/index/, /value/).  Typically, this list will
464                         -- be expressed as a comprehension.  An
465                         -- association '(i, x)' defines the value of
466                         -- the array at index 'i' to be 'x'.
467         -> Array i e
468 array (l,u) ies
469     = let n = safeRangeSize (l,u)
470       in unsafeArray' (l,u) n
471                       [(safeIndex (l,u) n i, e) | (i, e) <- ies]
472
473 {-# INLINE unsafeArray #-}
474 unsafeArray :: Ix i => (i,i) -> [(Int, e)] -> Array i e
475 unsafeArray b ies = unsafeArray' b (rangeSize b) ies
476
477 {-# INLINE unsafeArray' #-}
478 unsafeArray' :: Ix i => (i,i) -> Int -> [(Int, e)] -> Array i e
479 unsafeArray' (l,u) n@(I# n#) ies = runST (ST $ \s1# ->
480     case newArray# n# arrEleBottom s1# of
481         (# s2#, marr# #) ->
482             foldr (fill marr#) (done l u n marr#) ies s2#)
483
484 {-# INLINE fill #-}
485 fill :: MutableArray# s e -> (Int, e) -> STRep s a -> STRep s a
486 -- NB: put the \s after the "=" so that 'fill'
487 --     inlines when applied to three args
488 fill marr# (I# i#, e) next
489  = \s1# -> case writeArray# marr# i# e s1# of
490              s2# -> next s2#
491
492 {-# INLINE done #-}
493 done :: Ix i => i -> i -> Int -> MutableArray# s e -> STRep s (Array i e)
494 -- See NB on 'fill'
495 done l u n marr#
496   = \s1# -> case unsafeFreezeArray# marr# s1# of
497               (# s2#, arr# #) -> (# s2#, Array l u n arr# #)
498
499 -- This is inefficient and I'm not sure why:
500 -- listArray (l,u) es = unsafeArray (l,u) (zip [0 .. rangeSize (l,u) - 1] es)
501 -- The code below is better. It still doesn't enable foldr/build
502 -- transformation on the list of elements; I guess it's impossible
503 -- using mechanisms currently available.
504
505 -- | Construct an array from a pair of bounds and a list of values in
506 -- index order.
507 {-# INLINE listArray #-}
508 listArray :: Ix i => (i,i) -> [e] -> Array i e
509 listArray (l,u) es = runST (ST $ \s1# ->
510     case safeRangeSize (l,u)            of { n@(I# n#) ->
511     case newArray# n# arrEleBottom s1#  of { (# s2#, marr# #) ->
512     let fillFromList i# xs s3# | i# ==# n# = s3#
513                                | otherwise = case xs of
514             []   -> s3#
515             y:ys -> case writeArray# marr# i# y s3# of { s4# ->
516                     fillFromList (i# +# 1#) ys s4# } in
517     case fillFromList 0# es s2#         of { s3# ->
518     done l u n marr# s3# }}})
519
520 -- | The value at the given index in an array.
521 {-# INLINE (!) #-}
522 (!) :: Ix i => Array i e -> i -> e
523 arr@(Array l u n _) ! i = unsafeAt arr $ safeIndex (l,u) n i
524
525 {-# INLINE safeRangeSize #-}
526 safeRangeSize :: Ix i => (i, i) -> Int
527 safeRangeSize (l,u) = let r = rangeSize (l, u)
528                       in if r < 0 then negRange
529                                   else r
530
531 -- Don't inline this error message everywhere!!
532 negRange :: Int   -- Uninformative, but Ix does not provide Show
533 negRange = error "Negative range size"
534
535 {-# INLINE[1] safeIndex #-}
536 -- See Note [Double bounds-checking of index values]
537 -- Inline *after* (!) so the rules can fire
538 safeIndex :: Ix i => (i, i) -> Int -> i -> Int
539 safeIndex (l,u) n i = let i' = index (l,u) i
540                       in if (0 <= i') && (i' < n)
541                          then i'
542                          else badSafeIndex i' n
543
544 -- See Note [Double bounds-checking of index values]
545 {-# RULES
546 "safeIndex/I"       safeIndex = lessSafeIndex :: (Int,Int) -> Int -> Int -> Int
547 "safeIndex/(I,I)"   safeIndex = lessSafeIndex :: ((Int,Int),(Int,Int)) -> Int -> (Int,Int) -> Int
548 "safeIndex/(I,I,I)" safeIndex = lessSafeIndex :: ((Int,Int,Int),(Int,Int,Int)) -> Int -> (Int,Int,Int) -> Int
549   #-}
550
551 lessSafeIndex :: Ix i => (i, i) -> Int -> i -> Int
552 -- See Note [Double bounds-checking of index values]
553 -- Do only (A), the semantic check
554 lessSafeIndex (l,u) _ i = index (l,u) i
555
556 -- Don't inline this long error message everywhere!!
557 badSafeIndex :: Int -> Int -> Int
558 badSafeIndex i' n = error ("Error in array index; " ++ show i' ++
559                         " not in range [0.." ++ show n ++ ")")
560
561 {-# INLINE unsafeAt #-}
562 unsafeAt :: Ix i => Array i e -> Int -> e
563 unsafeAt (Array _ _ _ arr#) (I# i#) =
564     case indexArray# arr# i# of (# e #) -> e
565
566 -- | The bounds with which an array was constructed.
567 {-# INLINE bounds #-}
568 bounds :: Ix i => Array i e -> (i,i)
569 bounds (Array l u _ _) = (l,u)
570
571 -- | The number of elements in the array.
572 {-# INLINE numElements #-}
573 numElements :: Ix i => Array i e -> Int
574 numElements (Array _ _ n _) = n
575
576 -- | The list of indices of an array in ascending order.
577 {-# INLINE indices #-}
578 indices :: Ix i => Array i e -> [i]
579 indices (Array l u _ _) = range (l,u)
580
581 -- | The list of elements of an array in index order.
582 {-# INLINE elems #-}
583 elems :: Ix i => Array i e -> [e]
584 elems arr@(Array _ _ n _) =
585     [unsafeAt arr i | i <- [0 .. n - 1]]
586
587 -- | The list of associations of an array in index order.
588 {-# INLINE assocs #-}
589 assocs :: Ix i => Array i e -> [(i, e)]
590 assocs arr@(Array l u _ _) =
591     [(i, arr ! i) | i <- range (l,u)]
592
593 -- | The 'accumArray' function deals with repeated indices in the association
594 -- list using an /accumulating function/ which combines the values of
595 -- associations with the same index.
596 -- For example, given a list of values of some index type, @hist@
597 -- produces a histogram of the number of occurrences of each index within
598 -- a specified range:
599 --
600 -- > hist :: (Ix a, Num b) => (a,a) -> [a] -> Array a b
601 -- > hist bnds is = accumArray (+) 0 bnds [(i, 1) | i<-is, inRange bnds i]
602 --
603 -- If the accumulating function is strict, then 'accumArray' is strict in
604 -- the values, as well as the indices, in the association list.  Thus,
605 -- unlike ordinary arrays built with 'array', accumulated arrays should
606 -- not in general be recursive.
607 {-# INLINE accumArray #-}
608 accumArray :: Ix i
609         => (e -> a -> e)        -- ^ accumulating function
610         -> e                    -- ^ initial value
611         -> (i,i)                -- ^ bounds of the array
612         -> [(i, a)]             -- ^ association list
613         -> Array i e
614 accumArray f initial (l,u) ies =
615     let n = safeRangeSize (l,u)
616     in unsafeAccumArray' f initial (l,u) n
617                          [(safeIndex (l,u) n i, e) | (i, e) <- ies]
618
619 {-# INLINE unsafeAccumArray #-}
620 unsafeAccumArray :: Ix i => (e -> a -> e) -> e -> (i,i) -> [(Int, a)] -> Array i e
621 unsafeAccumArray f initial b ies = unsafeAccumArray' f initial b (rangeSize b) ies
622
623 {-# INLINE unsafeAccumArray' #-}
624 unsafeAccumArray' :: Ix i => (e -> a -> e) -> e -> (i,i) -> Int -> [(Int, a)] -> Array i e
625 unsafeAccumArray' f initial (l,u) n@(I# n#) ies = runST (ST $ \s1# ->
626     case newArray# n# initial s1#          of { (# s2#, marr# #) ->
627     foldr (adjust f marr#) (done l u n marr#) ies s2# })
628
629 {-# INLINE adjust #-}
630 adjust :: (e -> a -> e) -> MutableArray# s e -> (Int, a) -> STRep s b -> STRep s b
631 -- See NB on 'fill'
632 adjust f marr# (I# i#, new) next
633   = \s1# -> case readArray# marr# i# s1# of
634                 (# s2#, old #) ->
635                     case writeArray# marr# i# (f old new) s2# of
636                         s3# -> next s3#
637
638 -- | Constructs an array identical to the first argument except that it has
639 -- been updated by the associations in the right argument.
640 -- For example, if @m@ is a 1-origin, @n@ by @n@ matrix, then
641 --
642 -- > m//[((i,i), 0) | i <- [1..n]]
643 --
644 -- is the same matrix, except with the diagonal zeroed.
645 --
646 -- Repeated indices in the association list are handled as for 'array':
647 -- Haskell 2010 specifies that the resulting array is undefined (i.e. bottom),
648 -- but GHC's implementation uses the last association for each index.
649 {-# INLINE (//) #-}
650 (//) :: Ix i => Array i e -> [(i, e)] -> Array i e
651 arr@(Array l u n _) // ies =
652     unsafeReplace arr [(safeIndex (l,u) n i, e) | (i, e) <- ies]
653
654 {-# INLINE unsafeReplace #-}
655 unsafeReplace :: Ix i => Array i e -> [(Int, e)] -> Array i e
656 unsafeReplace arr ies = runST (do
657     STArray l u n marr# <- thawSTArray arr
658     ST (foldr (fill marr#) (done l u n marr#) ies))
659
660 -- | @'accum' f@ takes an array and an association list and accumulates
661 -- pairs from the list into the array with the accumulating function @f@.
662 -- Thus 'accumArray' can be defined using 'accum':
663 --
664 -- > accumArray f z b = accum f (array b [(i, z) | i <- range b])
665 --
666 {-# INLINE accum #-}
667 accum :: Ix i => (e -> a -> e) -> Array i e -> [(i, a)] -> Array i e
668 accum f arr@(Array l u n _) ies =
669     unsafeAccum f arr [(safeIndex (l,u) n i, e) | (i, e) <- ies]
670
671 {-# INLINE unsafeAccum #-}
672 unsafeAccum :: Ix i => (e -> a -> e) -> Array i e -> [(Int, a)] -> Array i e
673 unsafeAccum f arr ies = runST (do
674     STArray l u n marr# <- thawSTArray arr
675     ST (foldr (adjust f marr#) (done l u n marr#) ies))
676
677 {-# INLINE amap #-}
678 amap :: Ix i => (a -> b) -> Array i a -> Array i b
679 amap f arr@(Array l u n _) =
680     unsafeArray' (l,u) n [(i, f (unsafeAt arr i)) | i <- [0 .. n - 1]]
681
682 -- | 'ixmap' allows for transformations on array indices.
683 -- It may be thought of as providing function composition on the right
684 -- with the mapping that the original array embodies.
685 --
686 -- A similar transformation of array values may be achieved using 'fmap'
687 -- from the 'Array' instance of the 'Functor' class.
688 {-# INLINE ixmap #-}
689 ixmap :: (Ix i, Ix j) => (i,i) -> (i -> j) -> Array j e -> Array i e
690 ixmap (l,u) f arr =
691     array (l,u) [(i, arr ! f i) | i <- range (l,u)]
692
693 {-# INLINE eqArray #-}
694 eqArray :: (Ix i, Eq e) => Array i e -> Array i e -> Bool
695 eqArray arr1@(Array l1 u1 n1 _) arr2@(Array l2 u2 n2 _) =
696     if n1 == 0 then n2 == 0 else
697     l1 == l2 && u1 == u2 &&
698     and [unsafeAt arr1 i == unsafeAt arr2 i | i <- [0 .. n1 - 1]]
699
700 {-# INLINE [1] cmpArray #-}
701 cmpArray :: (Ix i, Ord e) => Array i e -> Array i e -> Ordering
702 cmpArray arr1 arr2 = compare (assocs arr1) (assocs arr2)
703
704 {-# INLINE cmpIntArray #-}
705 cmpIntArray :: Ord e => Array Int e -> Array Int e -> Ordering
706 cmpIntArray arr1@(Array l1 u1 n1 _) arr2@(Array l2 u2 n2 _) =
707     if n1 == 0 then
708         if n2 == 0 then EQ else LT
709     else if n2 == 0 then GT
710     else case compare l1 l2 of
711              EQ    -> foldr cmp (compare u1 u2) [0 .. (n1 `min` n2) - 1]
712              other -> other
713   where
714     cmp i rest = case compare (unsafeAt arr1 i) (unsafeAt arr2 i) of
715         EQ    -> rest
716         other -> other
717
718 {-# RULES "cmpArray/Int" cmpArray = cmpIntArray #-}
719 \end{code}
720
721
722 %*********************************************************
723 %*                                                      *
724 \subsection{Array instances}
725 %*                                                      *
726 %*********************************************************
727
728 \begin{code}
729 instance Ix i => Functor (Array i) where
730     fmap = amap
731
732 instance (Ix i, Eq e) => Eq (Array i e) where
733     (==) = eqArray
734
735 instance (Ix i, Ord e) => Ord (Array i e) where
736     compare = cmpArray
737
738 instance (Ix a, Show a, Show b) => Show (Array a b) where
739     showsPrec p a =
740         showParen (p > appPrec) $
741         showString "array " .
742         showsPrec appPrec1 (bounds a) .
743         showChar ' ' .
744         showsPrec appPrec1 (assocs a)
745         -- Precedence of 'array' is the precedence of application
746
747 -- The Read instance is in GHC.Read
748 \end{code}
749
750
751 %*********************************************************
752 %*                                                      *
753 \subsection{Operations on mutable arrays}
754 %*                                                      *
755 %*********************************************************
756
757 Idle ADR question: What's the tradeoff here between flattening these
758 datatypes into @STArray ix ix (MutableArray# s elt)@ and using
759 it as is?  As I see it, the former uses slightly less heap and
760 provides faster access to the individual parts of the bounds while the
761 code used has the benefit of providing a ready-made @(lo, hi)@ pair as
762 required by many array-related functions.  Which wins? Is the
763 difference significant (probably not).
764
765 Idle AJG answer: When I looked at the outputted code (though it was 2
766 years ago) it seems like you often needed the tuple, and we build
767 it frequently. Now we've got the overloading specialiser things
768 might be different, though.
769
770 \begin{code}
771 {-# INLINE newSTArray #-}
772 newSTArray :: Ix i => (i,i) -> e -> ST s (STArray s i e)
773 newSTArray (l,u) initial = ST $ \s1# ->
774     case safeRangeSize (l,u)            of { n@(I# n#) ->
775     case newArray# n# initial s1#       of { (# s2#, marr# #) ->
776     (# s2#, STArray l u n marr# #) }}
777
778 {-# INLINE boundsSTArray #-}
779 boundsSTArray :: STArray s i e -> (i,i)
780 boundsSTArray (STArray l u _ _) = (l,u)
781
782 {-# INLINE numElementsSTArray #-}
783 numElementsSTArray :: STArray s i e -> Int
784 numElementsSTArray (STArray _ _ n _) = n
785
786 {-# INLINE readSTArray #-}
787 readSTArray :: Ix i => STArray s i e -> i -> ST s e
788 readSTArray marr@(STArray l u n _) i =
789     unsafeReadSTArray marr (safeIndex (l,u) n i)
790
791 {-# INLINE unsafeReadSTArray #-}
792 unsafeReadSTArray :: Ix i => STArray s i e -> Int -> ST s e
793 unsafeReadSTArray (STArray _ _ _ marr#) (I# i#)
794     = ST $ \s1# -> readArray# marr# i# s1#
795
796 {-# INLINE writeSTArray #-}
797 writeSTArray :: Ix i => STArray s i e -> i -> e -> ST s ()
798 writeSTArray marr@(STArray l u n _) i e =
799     unsafeWriteSTArray marr (safeIndex (l,u) n i) e
800
801 {-# INLINE unsafeWriteSTArray #-}
802 unsafeWriteSTArray :: Ix i => STArray s i e -> Int -> e -> ST s ()
803 unsafeWriteSTArray (STArray _ _ _ marr#) (I# i#) e = ST $ \s1# ->
804     case writeArray# marr# i# e s1# of
805         s2# -> (# s2#, () #)
806 \end{code}
807
808
809 %*********************************************************
810 %*                                                      *
811 \subsection{Moving between mutable and immutable}
812 %*                                                      *
813 %*********************************************************
814
815 \begin{code}
816 freezeSTArray :: Ix i => STArray s i e -> ST s (Array i e)
817 freezeSTArray (STArray l u n@(I# n#) marr#) = ST $ \s1# ->
818     case newArray# n# arrEleBottom s1#  of { (# s2#, marr'# #) ->
819     let copy i# s3# | i# ==# n# = s3#
820                     | otherwise =
821             case readArray# marr# i# s3# of { (# s4#, e #) ->
822             case writeArray# marr'# i# e s4# of { s5# ->
823             copy (i# +# 1#) s5# }} in
824     case copy 0# s2#                    of { s3# ->
825     case unsafeFreezeArray# marr'# s3#  of { (# s4#, arr# #) ->
826     (# s4#, Array l u n arr# #) }}}
827
828 {-# INLINE unsafeFreezeSTArray #-}
829 unsafeFreezeSTArray :: Ix i => STArray s i e -> ST s (Array i e)
830 unsafeFreezeSTArray (STArray l u n marr#) = ST $ \s1# ->
831     case unsafeFreezeArray# marr# s1#   of { (# s2#, arr# #) ->
832     (# s2#, Array l u n arr# #) }
833
834 thawSTArray :: Ix i => Array i e -> ST s (STArray s i e)
835 thawSTArray (Array l u n@(I# n#) arr#) = ST $ \s1# ->
836     case newArray# n# arrEleBottom s1#  of { (# s2#, marr# #) ->
837     let copy i# s3# | i# ==# n# = s3#
838                     | otherwise =
839             case indexArray# arr# i#    of { (# e #) ->
840             case writeArray# marr# i# e s3# of { s4# ->
841             copy (i# +# 1#) s4# }} in
842     case copy 0# s2#                    of { s3# ->
843     (# s3#, STArray l u n marr# #) }}
844
845 {-# INLINE unsafeThawSTArray #-}
846 unsafeThawSTArray :: Ix i => Array i e -> ST s (STArray s i e)
847 unsafeThawSTArray (Array l u n arr#) = ST $ \s1# ->
848     case unsafeThawArray# arr# s1#      of { (# s2#, marr# #) ->
849     (# s2#, STArray l u n marr# #) }
850 \end{code}