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