1 % -----------------------------------------------------------------------------
2 % $Id: PrelArr.lhs,v 1.30 2001/09/13 15:54:43 simonmar Exp $
4 % (c) The University of Glasgow, 1994-2000
7 \section[PrelArr]{Module @PrelArr@}
9 Array implementation, @PrelArr@ exports the basic array
12 For byte-arrays see @PrelByteArr@.
15 {-# OPTIONS -fno-implicit-prelude #-}
19 import {-# SOURCE #-} PrelErr ( error )
33 %*********************************************************
35 \subsection{The @Ix@ class}
37 %*********************************************************
40 class (Ord a) => Ix a where
42 index, unsafeIndex :: (a,a) -> a -> Int
43 inRange :: (a,a) -> a -> Bool
44 rangeSize :: (a,a) -> Int
45 unsafeRangeSize :: (a,a) -> Int
47 -- Must specify one of index, unsafeIndex
48 index b i | inRange b i = unsafeIndex b i
49 | otherwise = error "Error in array index"
50 unsafeIndex b i = index b i
52 -- As long as you don't override the default rangeSize,
53 -- you can specify unsafeRangeSize as follows, to speed up
56 -- unsafeRangeSize b@(_l,h) = unsafeIndex b h + 1
58 rangeSize b@(_l,h) | inRange b h = unsafeIndex b h + 1
60 unsafeRangeSize b = rangeSize b
63 Note that the following is NOT right
64 rangeSize (l,h) | l <= h = index b h + 1
67 Because it might be the case that l<h, but the range
68 is nevertheless empty. Consider
70 Here l<h, but the second index ranges from 2..1 and
73 %*********************************************************
75 \subsection{Instances of @Ix@}
77 %*********************************************************
80 -- abstract these errors from the relevant index functions so that
81 -- the guts of the function will be small enough to inline.
83 {-# NOINLINE indexError #-}
84 indexError :: Show a => (a,a) -> a -> String -> b
86 = error (showString "Ix{" . showString tp . showString "}.index: Index " .
87 showParen True (showsPrec 0 i) .
88 showString " out of range " $
89 showParen True (showsPrec 0 rng) "")
91 ----------------------------------------------------------------------
92 instance Ix Char where
96 {-# INLINE unsafeIndex #-}
97 unsafeIndex (m,_n) i = fromEnum i - fromEnum m
99 index b i | inRange b i = unsafeIndex b i
100 | otherwise = indexError b i "Char"
102 inRange (m,n) i = m <= i && i <= n
104 unsafeRangeSize b@(_l,h) = unsafeIndex b h + 1
106 ----------------------------------------------------------------------
107 instance Ix Int where
109 -- The INLINE stops the build in the RHS from getting inlined,
110 -- so that callers can fuse with the result of range
113 {-# INLINE unsafeIndex #-}
114 unsafeIndex (m,_n) i = i - m
116 index b i | inRange b i = unsafeIndex b i
117 | otherwise = indexError b i "Int"
119 {-# INLINE inRange #-}
120 inRange (I# m,I# n) (I# i) = m <=# i && i <=# n
122 unsafeRangeSize b@(_l,h) = unsafeIndex b h + 1
124 ----------------------------------------------------------------------
125 instance Ix Integer where
129 {-# INLINE unsafeIndex #-}
130 unsafeIndex (m,_n) i = fromInteger (i - m)
132 index b i | inRange b i = unsafeIndex b i
133 | otherwise = indexError b i "Integer"
135 inRange (m,n) i = m <= i && i <= n
137 unsafeRangeSize b@(_l,h) = unsafeIndex b h + 1
139 ----------------------------------------------------------------------
140 instance Ix Bool where -- as derived
144 {-# INLINE unsafeIndex #-}
145 unsafeIndex (l,_) i = fromEnum i - fromEnum l
147 index b i | inRange b i = unsafeIndex b i
148 | otherwise = indexError b i "Bool"
150 inRange (l,u) i = fromEnum i >= fromEnum l && fromEnum i <= fromEnum u
152 unsafeRangeSize b@(_l,h) = unsafeIndex b h + 1
154 ----------------------------------------------------------------------
155 instance Ix Ordering where -- as derived
159 {-# INLINE unsafeIndex #-}
160 unsafeIndex (l,_) i = fromEnum i - fromEnum l
162 index b i | inRange b i = unsafeIndex b i
163 | otherwise = indexError b i "Ordering"
165 inRange (l,u) i = fromEnum i >= fromEnum l && fromEnum i <= fromEnum u
167 unsafeRangeSize b@(_l,h) = unsafeIndex b h + 1
169 ----------------------------------------------------------------------
172 range ((), ()) = [()]
173 {-# INLINE unsafeIndex #-}
174 unsafeIndex ((), ()) () = 0
175 {-# INLINE inRange #-}
176 inRange ((), ()) () = True
178 index b i = unsafeIndex b i
180 unsafeRangeSize b@(_l,h) = unsafeIndex b h + 1
182 ----------------------------------------------------------------------
183 instance (Ix a, Ix b) => Ix (a, b) where -- as derived
184 {-# SPECIALISE instance Ix (Int,Int) #-}
187 range ((l1,l2),(u1,u2)) =
188 [ (i1,i2) | i1 <- range (l1,u1), i2 <- range (l2,u2) ]
190 {- INLINE unsafeIndex #-}
191 unsafeIndex ((l1,l2),(u1,u2)) (i1,i2) =
192 unsafeIndex (l1,u1) i1 * unsafeRangeSize (l2,u2) + unsafeIndex (l2,u2) i2
194 {- INLINE inRange #-}
195 inRange ((l1,l2),(u1,u2)) (i1,i2) =
196 inRange (l1,u1) i1 && inRange (l2,u2) i2
198 unsafeRangeSize b@(_l,h) = unsafeIndex b h + 1
200 -- Default method for index
202 ----------------------------------------------------------------------
203 instance (Ix a1, Ix a2, Ix a3) => Ix (a1,a2,a3) where
204 {-# SPECIALISE instance Ix (Int,Int,Int) #-}
206 range ((l1,l2,l3),(u1,u2,u3)) =
207 [(i1,i2,i3) | i1 <- range (l1,u1),
211 unsafeIndex ((l1,l2,l3),(u1,u2,u3)) (i1,i2,i3) =
212 unsafeIndex (l3,u3) i3 + unsafeRangeSize (l3,u3) * (
213 unsafeIndex (l2,u2) i2 + unsafeRangeSize (l2,u2) * (
214 unsafeIndex (l1,u1) i1))
216 inRange ((l1,l2,l3),(u1,u2,u3)) (i1,i2,i3) =
217 inRange (l1,u1) i1 && inRange (l2,u2) i2 &&
220 unsafeRangeSize b@(_l,h) = unsafeIndex b h + 1
222 -- Default method for index
224 ----------------------------------------------------------------------
225 instance (Ix a1, Ix a2, Ix a3, Ix a4) => Ix (a1,a2,a3,a4) where
226 range ((l1,l2,l3,l4),(u1,u2,u3,u4)) =
227 [(i1,i2,i3,i4) | i1 <- range (l1,u1),
232 unsafeIndex ((l1,l2,l3,l4),(u1,u2,u3,u4)) (i1,i2,i3,i4) =
233 unsafeIndex (l4,u4) i4 + unsafeRangeSize (l4,u4) * (
234 unsafeIndex (l3,u3) i3 + unsafeRangeSize (l3,u3) * (
235 unsafeIndex (l2,u2) i2 + unsafeRangeSize (l2,u2) * (
236 unsafeIndex (l1,u1) i1)))
238 inRange ((l1,l2,l3,l4),(u1,u2,u3,u4)) (i1,i2,i3,i4) =
239 inRange (l1,u1) i1 && inRange (l2,u2) i2 &&
240 inRange (l3,u3) i3 && inRange (l4,u4) i4
242 unsafeRangeSize b@(_l,h) = unsafeIndex b h + 1
244 -- Default method for index
246 instance (Ix a1, Ix a2, Ix a3, Ix a4, Ix a5) => Ix (a1,a2,a3,a4,a5) where
247 range ((l1,l2,l3,l4,l5),(u1,u2,u3,u4,u5)) =
248 [(i1,i2,i3,i4,i5) | i1 <- range (l1,u1),
254 unsafeIndex ((l1,l2,l3,l4,l5),(u1,u2,u3,u4,u5)) (i1,i2,i3,i4,i5) =
255 unsafeIndex (l5,u5) i5 + unsafeRangeSize (l5,u5) * (
256 unsafeIndex (l4,u4) i4 + unsafeRangeSize (l4,u4) * (
257 unsafeIndex (l3,u3) i3 + unsafeRangeSize (l3,u3) * (
258 unsafeIndex (l2,u2) i2 + unsafeRangeSize (l2,u2) * (
259 unsafeIndex (l1,u1) i1))))
261 inRange ((l1,l2,l3,l4,l5),(u1,u2,u3,u4,u5)) (i1,i2,i3,i4,i5) =
262 inRange (l1,u1) i1 && inRange (l2,u2) i2 &&
263 inRange (l3,u3) i3 && inRange (l4,u4) i4 &&
266 unsafeRangeSize b@(_l,h) = unsafeIndex b h + 1
268 -- Default method for index
272 %*********************************************************
274 \subsection{Mutable references}
276 %*********************************************************
279 data STRef s a = STRef (MutVar# s a)
281 newSTRef :: a -> ST s (STRef s a)
282 newSTRef init = ST $ \s1# ->
283 case newMutVar# init s1# of { (# s2#, var# #) ->
284 (# s2#, STRef var# #) }
286 readSTRef :: STRef s a -> ST s a
287 readSTRef (STRef var#) = ST $ \s1# -> readMutVar# var# s1#
289 writeSTRef :: STRef s a -> a -> ST s ()
290 writeSTRef (STRef var#) val = ST $ \s1# ->
291 case writeMutVar# var# val s1# of { s2# ->
294 -- Just pointer equality on mutable references:
295 instance Eq (STRef s a) where
296 STRef v1# == STRef v2# = sameMutVar# v1# v2#
300 %*********************************************************
302 \subsection{The @Array@ types}
304 %*********************************************************
307 type IPr = (Int, Int)
309 data Ix i => Array i e = Array !i !i (Array# e)
310 data Ix i => STArray s i e = STArray !i !i (MutableArray# s e)
312 -- Just pointer equality on mutable arrays:
313 instance Eq (STArray s i e) where
314 STArray _ _ arr1# == STArray _ _ arr2# =
315 sameMutableArray# arr1# arr2#
319 %*********************************************************
321 \subsection{Operations on immutable arrays}
323 %*********************************************************
326 {-# NOINLINE arrEleBottom #-}
328 arrEleBottom = error "(Array.!): undefined array element"
331 array :: Ix i => (i,i) -> [(i, e)] -> Array i e
332 array (l,u) ies = unsafeArray (l,u) [(index (l,u) i, e) | (i, e) <- ies]
334 {-# INLINE unsafeArray #-}
335 unsafeArray :: Ix i => (i,i) -> [(Int, e)] -> Array i e
336 unsafeArray (l,u) ies = runST (ST $ \s1# ->
337 case rangeSize (l,u) of { I# n# ->
338 case newArray# n# arrEleBottom s1# of { (# s2#, marr# #) ->
339 foldr (fill marr#) (done l u marr#) ies s2# }})
342 fill :: MutableArray# s e -> (Int, e) -> STRep s a -> STRep s a
343 fill marr# (I# i#, e) next s1# =
344 case writeArray# marr# i# e s1# of { s2# ->
348 done :: Ix i => i -> i -> MutableArray# s e -> STRep s (Array i e)
350 case unsafeFreezeArray# marr# s1# of { (# s2#, arr# #) ->
351 (# s2#, Array l u arr# #) }
353 -- This is inefficient and I'm not sure why:
354 -- listArray (l,u) es = unsafeArray (l,u) (zip [0 .. rangeSize (l,u) - 1] es)
355 -- The code below is better. It still doesn't enable foldr/build
356 -- transformation on the list of elements; I guess it's impossible
357 -- using mechanisms currently available.
359 {-# INLINE listArray #-}
360 listArray :: Ix i => (i,i) -> [e] -> Array i e
361 listArray (l,u) es = runST (ST $ \s1# ->
362 case rangeSize (l,u) of { I# n# ->
363 case newArray# n# arrEleBottom s1# of { (# s2#, marr# #) ->
364 let fillFromList i# xs s3# | i# ==# n# = s3#
365 | otherwise = case xs of
367 y:ys -> case writeArray# marr# i# y s3# of { s4# ->
368 fillFromList (i# +# 1#) ys s4# } in
369 case fillFromList 0# es s2# of { s3# ->
370 done l u marr# s3# }}})
373 (!) :: Ix i => Array i e -> i -> e
374 arr@(Array l u _) ! i = unsafeAt arr (index (l,u) i)
376 {-# INLINE unsafeAt #-}
377 unsafeAt :: Ix i => Array i e -> Int -> e
378 unsafeAt (Array _ _ arr#) (I# i#) =
379 case indexArray# arr# i# of (# e #) -> e
381 {-# INLINE bounds #-}
382 bounds :: Ix i => Array i e -> (i,i)
383 bounds (Array l u _) = (l,u)
385 {-# INLINE indices #-}
386 indices :: Ix i => Array i e -> [i]
387 indices (Array l u _) = range (l,u)
390 elems :: Ix i => Array i e -> [e]
391 elems arr@(Array l u _) =
392 [unsafeAt arr i | i <- [0 .. rangeSize (l,u) - 1]]
394 {-# INLINE assocs #-}
395 assocs :: Ix i => Array i e -> [(i, e)]
396 assocs arr@(Array l u _) =
397 [(i, unsafeAt arr (unsafeIndex (l,u) i)) | i <- range (l,u)]
399 {-# INLINE accumArray #-}
400 accumArray :: Ix i => (e -> a -> e) -> e -> (i,i) -> [(i, a)] -> Array i e
401 accumArray f init (l,u) ies =
402 unsafeAccumArray f init (l,u) [(index (l,u) i, e) | (i, e) <- ies]
404 {-# INLINE unsafeAccumArray #-}
405 unsafeAccumArray :: Ix i => (e -> a -> e) -> e -> (i,i) -> [(Int, a)] -> Array i e
406 unsafeAccumArray f init (l,u) ies = runST (ST $ \s1# ->
407 case rangeSize (l,u) of { I# n# ->
408 case newArray# n# init s1# of { (# s2#, marr# #) ->
409 foldr (adjust f marr#) (done l u marr#) ies s2# }})
411 {-# INLINE adjust #-}
412 adjust :: (e -> a -> e) -> MutableArray# s e -> (Int, a) -> STRep s b -> STRep s b
413 adjust f marr# (I# i#, new) next s1# =
414 case readArray# marr# i# s1# of { (# s2#, old #) ->
415 case writeArray# marr# i# (f old new) s2# of { s3# ->
419 (//) :: Ix i => Array i e -> [(i, e)] -> Array i e
420 arr@(Array l u _) // ies =
421 unsafeReplace arr [(index (l,u) i, e) | (i, e) <- ies]
423 {-# INLINE unsafeReplace #-}
424 unsafeReplace :: Ix i => Array i e -> [(Int, e)] -> Array i e
425 unsafeReplace arr@(Array l u _) ies = runST (do
426 STArray _ _ marr# <- thawSTArray arr
427 ST (foldr (fill marr#) (done l u marr#) ies))
430 accum :: Ix i => (e -> a -> e) -> Array i e -> [(i, a)] -> Array i e
431 accum f arr@(Array l u _) ies =
432 unsafeAccum f arr [(index (l,u) i, e) | (i, e) <- ies]
434 {-# INLINE unsafeAccum #-}
435 unsafeAccum :: Ix i => (e -> a -> e) -> Array i e -> [(Int, a)] -> Array i e
436 unsafeAccum f arr@(Array l u _) ies = runST (do
437 STArray _ _ marr# <- thawSTArray arr
438 ST (foldr (adjust f marr#) (done l u marr#) ies))
441 amap :: Ix i => (a -> b) -> Array i a -> Array i b
442 amap f arr@(Array l u _) =
443 unsafeArray (l,u) [(i, f (unsafeAt arr i)) | i <- [0 .. rangeSize (l,u) - 1]]
446 ixmap :: (Ix i, Ix j) => (i,i) -> (i -> j) -> Array j e -> Array i e
448 unsafeArray (l,u) [(unsafeIndex (l,u) i, arr ! f i) | i <- range (l,u)]
450 {-# INLINE eqArray #-}
451 eqArray :: (Ix i, Eq e) => Array i e -> Array i e -> Bool
452 eqArray arr1@(Array l1 u1 _) arr2@(Array l2 u2 _) =
453 if rangeSize (l1,u1) == 0 then rangeSize (l2,u2) == 0 else
454 l1 == l2 && u1 == u2 &&
455 and [unsafeAt arr1 i == unsafeAt arr2 i | i <- [0 .. rangeSize (l1,u1) - 1]]
457 {-# INLINE cmpArray #-}
458 cmpArray :: (Ix i, Ord e) => Array i e -> Array i e -> Ordering
459 cmpArray arr1 arr2 = compare (assocs arr1) (assocs arr2)
461 {-# INLINE cmpIntArray #-}
462 cmpIntArray :: Ord e => Array Int e -> Array Int e -> Ordering
463 cmpIntArray arr1@(Array l1 u1 _) arr2@(Array l2 u2 _) =
464 if rangeSize (l1,u1) == 0 then if rangeSize (l2,u2) == 0 then EQ else LT else
465 if rangeSize (l2,u2) == 0 then GT else
466 case compare l1 l2 of
467 EQ -> foldr cmp (compare u1 u2) [0 .. rangeSize (l1, min u1 u2) - 1]
470 cmp i rest = case compare (unsafeAt arr1 i) (unsafeAt arr2 i) of
474 {-# RULES "cmpArray/Int" cmpArray = cmpIntArray #-}
478 %*********************************************************
480 \subsection{Array instances}
482 %*********************************************************
485 instance Ix i => Functor (Array i) where
488 instance (Ix i, Eq e) => Eq (Array i e) where
491 instance (Ix i, Ord e) => Ord (Array i e) where
494 instance (Ix a, Show a, Show b) => Show (Array a b) where
497 showString "array " .
503 instance (Ix a, Read a, Read b) => Read (Array a b) where
504 readsPrec p = readParen (p > 9)
505 (\r -> [(array b as, u) | ("array",s) <- lex r,
512 %*********************************************************
514 \subsection{Operations on mutable arrays}
516 %*********************************************************
518 Idle ADR question: What's the tradeoff here between flattening these
519 datatypes into @STArray ix ix (MutableArray# s elt)@ and using
520 it as is? As I see it, the former uses slightly less heap and
521 provides faster access to the individual parts of the bounds while the
522 code used has the benefit of providing a ready-made @(lo, hi)@ pair as
523 required by many array-related functions. Which wins? Is the
524 difference significant (probably not).
526 Idle AJG answer: When I looked at the outputted code (though it was 2
527 years ago) it seems like you often needed the tuple, and we build
528 it frequently. Now we've got the overloading specialiser things
529 might be different, though.
532 {-# INLINE newSTArray #-}
533 newSTArray :: Ix i => (i,i) -> e -> ST s (STArray s i e)
534 newSTArray (l,u) init = ST $ \s1# ->
535 case rangeSize (l,u) of { I# n# ->
536 case newArray# n# init s1# of { (# s2#, marr# #) ->
537 (# s2#, STArray l u marr# #) }}
539 {-# INLINE boundsSTArray #-}
540 boundsSTArray :: STArray s i e -> (i,i)
541 boundsSTArray (STArray l u _) = (l,u)
543 {-# INLINE readSTArray #-}
544 readSTArray :: Ix i => STArray s i e -> i -> ST s e
545 readSTArray marr@(STArray l u _) i =
546 unsafeReadSTArray marr (index (l,u) i)
548 {-# INLINE unsafeReadSTArray #-}
549 unsafeReadSTArray :: Ix i => STArray s i e -> Int -> ST s e
550 unsafeReadSTArray (STArray _ _ marr#) (I# i#) = ST $ \s1# ->
551 readArray# marr# i# s1#
553 {-# INLINE writeSTArray #-}
554 writeSTArray :: Ix i => STArray s i e -> i -> e -> ST s ()
555 writeSTArray marr@(STArray l u _) i e =
556 unsafeWriteSTArray marr (index (l,u) i) e
558 {-# INLINE unsafeWriteSTArray #-}
559 unsafeWriteSTArray :: Ix i => STArray s i e -> Int -> e -> ST s ()
560 unsafeWriteSTArray (STArray _ _ marr#) (I# i#) e = ST $ \s1# ->
561 case writeArray# marr# i# e s1# of { s2# ->
566 %*********************************************************
568 \subsection{Moving between mutable and immutable}
570 %*********************************************************
573 freezeSTArray :: Ix i => STArray s i e -> ST s (Array i e)
574 freezeSTArray (STArray l u marr#) = ST $ \s1# ->
575 case rangeSize (l,u) of { I# n# ->
576 case newArray# n# arrEleBottom s1# of { (# s2#, marr'# #) ->
577 let copy i# s3# | i# ==# n# = s3#
579 case readArray# marr# i# s3# of { (# s4#, e #) ->
580 case writeArray# marr'# i# e s4# of { s5# ->
581 copy (i# +# 1#) s5# }} in
582 case copy 0# s2# of { s3# ->
583 case unsafeFreezeArray# marr'# s3# of { (# s4#, arr# #) ->
584 (# s4#, Array l u arr# #) }}}}
586 {-# INLINE unsafeFreezeSTArray #-}
587 unsafeFreezeSTArray :: Ix i => STArray s i e -> ST s (Array i e)
588 unsafeFreezeSTArray (STArray l u marr#) = ST $ \s1# ->
589 case unsafeFreezeArray# marr# s1# of { (# s2#, arr# #) ->
590 (# s2#, Array l u arr# #) }
592 thawSTArray :: Ix i => Array i e -> ST s (STArray s i e)
593 thawSTArray (Array l u arr#) = ST $ \s1# ->
594 case rangeSize (l,u) of { I# n# ->
595 case newArray# n# arrEleBottom s1# of { (# s2#, marr# #) ->
596 let copy i# s3# | i# ==# n# = s3#
598 case indexArray# arr# i# of { (# e #) ->
599 case writeArray# marr# i# e s3# of { s4# ->
600 copy (i# +# 1#) s4# }} in
601 case copy 0# s2# of { s3# ->
602 (# s3#, STArray l u marr# #) }}}
604 {-# INLINE unsafeThawSTArray #-}
605 unsafeThawSTArray :: Ix i => Array i e -> ST s (STArray s i e)
606 unsafeThawSTArray (Array l u arr#) = ST $ \s1# ->
607 case unsafeThawArray# arr# s1# of { (# s2#, marr# #) ->
608 (# s2#, STArray l u marr# #) }