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