2 % (c) The AQUA Project, Glasgow University, 1994-1996
4 \section[PrelArr]{Module @PrelArr@}
6 Array implementation, @PrelArr@ exports the basic array
9 For byte-arrays see @PrelByteArr@.
12 {-# OPTIONS -fno-implicit-prelude #-}
16 import {-# SOURCE #-} PrelErr ( error )
18 import PrelList (foldl)
31 {-# SPECIALISE array :: (Int,Int) -> [(Int,b)] -> Array Int b #-}
32 array :: (Ix a) => (a,a) -> [(a,b)] -> Array a b
34 {-# SPECIALISE (!) :: Array Int b -> Int -> b #-}
35 (!) :: (Ix a) => Array a b -> a -> b
37 {-# SPECIALISE (//) :: Array Int b -> [(Int,b)] -> Array Int b #-}
38 (//) :: (Ix a) => Array a b -> [(a,b)] -> Array a b
40 {-# SPECIALISE accum :: (b -> c -> b) -> Array Int b -> [(Int,c)] -> Array Int b #-}
41 accum :: (Ix a) => (b -> c -> b) -> Array a b -> [(a,c)] -> Array a b
43 {-# SPECIALISE accumArray :: (b -> c -> b) -> b -> (Int,Int) -> [(Int,c)] -> Array Int b #-}
44 accumArray :: (Ix a) => (b -> c -> b) -> b -> (a,a) -> [(a,c)] -> Array a b
46 bounds :: (Ix a) => Array a b -> (a,a)
47 assocs :: (Ix a) => Array a b -> [(a,b)]
48 indices :: (Ix a) => Array a b -> [a]
52 %*********************************************************
54 \subsection{The @Array@ types}
56 %*********************************************************
61 data Ix ix => Array ix elt = Array ix ix (Array# elt)
62 data Ix ix => MutableArray s ix elt = MutableArray ix ix (MutableArray# s elt)
65 data MutableVar s a = MutableVar (MutVar# s a)
67 instance Eq (MutableVar s a) where
68 MutableVar v1# == MutableVar v2#
71 -- just pointer equality on arrays:
72 instance Eq (MutableArray s ix elt) where
73 MutableArray _ _ arr1# == MutableArray _ _ arr2#
74 = sameMutableArray# arr1# arr2#
77 %*********************************************************
79 \subsection{Operations on mutable variables}
81 %*********************************************************
84 newVar :: a -> ST s (MutableVar s a)
85 readVar :: MutableVar s a -> ST s a
86 writeVar :: MutableVar s a -> a -> ST s ()
88 newVar init = ST $ \ s# ->
89 case (newMutVar# init s#) of { (# s2#, var# #) ->
90 (# s2#, MutableVar var# #) }
92 readVar (MutableVar var#) = ST $ \ s# -> readMutVar# var# s#
94 writeVar (MutableVar var#) val = ST $ \ s# ->
95 case writeMutVar# var# val s# of { s2# ->
99 %*********************************************************
101 \subsection{Operations on immutable arrays}
103 %*********************************************************
105 "array", "!" and "bounds" are basic; the rest can be defined in terms of them
108 {-# INLINE bounds #-}
109 bounds (Array l u _) = (l,u)
111 {-# INLINE assocs #-} -- Want to fuse the list comprehension
112 assocs a = [(i, a!i) | i <- indices a]
114 {-# INLINE indices #-}
115 indices = range . bounds
117 {-# SPECIALISE amap :: (b -> c) -> Array Int b -> Array Int c #-}
118 amap :: (Ix a) => (b -> c) -> Array a b -> Array a c
119 amap f a = array b [(i, f (a!i)) | i <- range b]
123 = let n# = case (index (l,u) i) of { I# x -> x } -- index fails if out of range
125 case (indexArray# arr# n#) of
130 = case rangeSize ixs of { I# n ->
132 case newArray# n arrEleBottom s1 of { (# s2, marr #) ->
133 foldr (fill ixs marr) (done ixs marr) ivs s2
136 fill :: Ix ix => (ix,ix) -> MutableArray# s elt
137 -> (ix,elt) -> STRep s a -> STRep s a
139 fill ixs marr (i,v) next = \s1 -> case index ixs i of { I# n ->
140 case writeArray# marr n v s1 of { s2 ->
143 done :: Ix ix => (ix,ix) -> MutableArray# s elt
144 -> STRep s (Array ix elt)
146 done (l,u) marr = \s1 ->
147 case unsafeFreezeArray# marr s1 of { (# s2, arr #) ->
148 (# s2, Array l u arr #) }
151 arrEleBottom = error "(Array.!): undefined array element"
154 -----------------------------------------------------------------------
155 -- These also go better with magic: (//), accum, accumArray
156 -- *** NB *** We INLINE them all so that their foldr's get to the call site
161 -- copy the old array:
162 arr <- thawArray old_array
163 -- now write the new elements into the new array:
168 fill_it_in :: Ix ix => MutableArray s ix elt -> [(ix, elt)] -> ST s ()
169 {-# INLINE fill_it_in #-}
170 fill_it_in arr lst = foldr (fill_one_in arr) (return ()) lst
171 -- **** STRICT **** (but that's OK...)
173 fill_one_in arr (i, v) rst = writeArray arr i v >> rst
175 zap_with_f :: Ix ix => (elt -> elt2 -> elt) -> MutableArray s ix elt -> [(ix,elt2)] -> ST s ()
176 -- zap_with_f: reads an elem out first, then uses "f" on that and the new value
177 {-# INLINE zap_with_f #-}
180 = foldr (zap_one f arr) (return ()) lst
182 zap_one f arr (i, new_v) rst = do
183 old_v <- readArray arr i
184 writeArray arr i (f old_v new_v)
188 accum f old_array ivs
190 -- copy the old array:
191 arr <- thawArray old_array
192 -- now zap the elements in question with "f":
197 {-# INLINE accumArray #-}
198 accumArray f zero ixs ivs
200 arr <- newArray ixs zero
207 %*********************************************************
209 \subsection{Array instances}
211 %*********************************************************
215 instance Ix a => Functor (Array a) where
218 instance (Ix a, Eq b) => Eq (Array a b) where
219 a == a' = assocs a == assocs a'
220 a /= a' = assocs a /= assocs a'
222 instance (Ix a, Ord b) => Ord (Array a b) where
223 compare a b = compare (assocs a) (assocs b)
225 instance (Ix a, Show a, Show b) => Show (Array a b) where
226 showsPrec p a = showParen (p > 9) (
227 showString "array " .
228 shows (bounds a) . showChar ' ' .
230 showList = showList__ (showsPrec 0)
233 instance (Ix a, Read a, Read b) => Read (Array a b) where
234 readsPrec p = readParen (p > 9)
235 (\r -> [(array b as, u) | ("array",s) <- lex r,
238 readList = readList__ (readsPrec 0)
243 %*********************************************************
245 \subsection{Operations on mutable arrays}
247 %*********************************************************
249 Idle ADR question: What's the tradeoff here between flattening these
250 datatypes into @MutableArray ix ix (MutableArray# s elt)@ and using
251 it as is? As I see it, the former uses slightly less heap and
252 provides faster access to the individual parts of the bounds while the
253 code used has the benefit of providing a ready-made @(lo, hi)@ pair as
254 required by many array-related functions. Which wins? Is the
255 difference significant (probably not).
257 Idle AJG answer: When I looked at the outputted code (though it was 2
258 years ago) it seems like you often needed the tuple, and we build
259 it frequently. Now we've got the overloading specialiser things
260 might be different, though.
263 newArray :: Ix ix => (ix,ix) -> elt -> ST s (MutableArray s ix elt)
265 {-# SPECIALIZE newArray :: IPr -> elt -> ST s (MutableArray s Int elt),
266 (IPr,IPr) -> elt -> ST s (MutableArray s IPr elt)
268 newArray (l,u) init = ST $ \ s# ->
269 case rangeSize (l,u) of { I# n# ->
270 case (newArray# n# init s#) of { (# s2#, arr# #) ->
271 (# s2#, MutableArray l u arr# #) }}
275 boundsOfArray :: Ix ix => MutableArray s ix elt -> (ix, ix)
276 {-# SPECIALIZE boundsOfArray :: MutableArray s Int elt -> IPr #-}
277 boundsOfArray (MutableArray l u _) = (l,u)
279 readArray :: Ix ix => MutableArray s ix elt -> ix -> ST s elt
280 {-# SPECIALIZE readArray :: MutableArray s Int elt -> Int -> ST s elt,
281 MutableArray s IPr elt -> IPr -> ST s elt
284 readArray (MutableArray l u arr#) n = ST $ \ s# ->
285 case (index (l,u) n) of { I# n# ->
286 case readArray# arr# n# s# of { (# s2#, r #) ->
289 writeArray :: Ix ix => MutableArray s ix elt -> ix -> elt -> ST s ()
290 {-# SPECIALIZE writeArray :: MutableArray s Int elt -> Int -> elt -> ST s (),
291 MutableArray s IPr elt -> IPr -> elt -> ST s ()
294 writeArray (MutableArray l u arr#) n ele = ST $ \ s# ->
295 case index (l,u) n of { I# n# ->
296 case writeArray# arr# n# ele s# of { s2# ->
301 %*********************************************************
303 \subsection{Moving between mutable and immutable}
305 %*********************************************************
308 freezeArray :: Ix ix => MutableArray s ix elt -> ST s (Array ix elt)
309 {-# SPECIALISE freezeArray :: MutableArray s Int elt -> ST s (Array Int elt),
310 MutableArray s IPr elt -> ST s (Array IPr elt)
313 freezeArray (MutableArray l u arr#) = ST $ \ s# ->
314 case rangeSize (l,u) of { I# n# ->
315 case freeze arr# n# s# of { (# s2#, frozen# #) ->
316 (# s2#, Array l u frozen# #) }}
318 freeze :: MutableArray# s ele -- the thing
319 -> Int# -- size of thing to be frozen
320 -> State# s -- the Universe and everything
321 -> (# State# s, Array# ele #)
323 = case newArray# n# init s# of { (# s2#, newarr1# #) ->
324 case copy 0# n# m_arr# newarr1# s2# of { (# s3#, newarr2# #) ->
325 unsafeFreezeArray# newarr2# s3#
328 init = error "freezeArray: element not copied"
331 -> MutableArray# s ele
332 -> MutableArray# s ele
334 -> (# State# s, MutableArray# s ele #)
336 copy cur# end# from# to# st#
340 = case readArray# from# cur# st# of { (# s1#, ele #) ->
341 case writeArray# to# cur# ele s1# of { s2# ->
342 copy (cur# +# 1#) end# from# to# s2#
345 unsafeFreezeArray :: Ix ix => MutableArray s ix elt -> ST s (Array ix elt)
346 unsafeFreezeArray (MutableArray l u arr#) = ST $ \ s# ->
347 case unsafeFreezeArray# arr# s# of { (# s2#, frozen# #) ->
348 (# s2#, Array l u frozen# #) }
350 --This takes a immutable array, and copies it into a mutable array, in a
353 thawArray :: Ix ix => Array ix elt -> ST s (MutableArray s ix elt)
354 {-# SPECIALISE thawArray :: Array Int elt -> ST s (MutableArray s Int elt),
355 Array IPr elt -> ST s (MutableArray s IPr elt)
358 thawArray (Array l u arr#) = ST $ \ s# ->
359 case rangeSize (l,u) of { I# n# ->
360 case thaw arr# n# s# of { (# s2#, thawed# #) ->
361 (# s2#, MutableArray l u thawed# #)}}
363 thaw :: Array# ele -- the thing
364 -> Int# -- size of thing to be thawed
365 -> State# s -- the Universe and everything
366 -> (# State# s, MutableArray# s ele #)
369 = case newArray# n# init s# of { (# s2#, newarr1# #) ->
370 copy 0# n# arr1# newarr1# s2# }
372 init = error "thawArray: element not copied"
376 -> MutableArray# s ele
378 -> (# State# s, MutableArray# s ele #)
380 copy cur# end# from# to# st#
384 = case indexArray# from# cur# of { (# ele #) ->
385 case writeArray# to# cur# ele st# of { s1# ->
386 copy (cur# +# 1#) end# from# to# s1#
389 -- this is a quicker version of the above, just flipping the type
390 -- (& representation) of an immutable array. And placing a
391 -- proof obligation on the programmer.
392 unsafeThawArray :: Ix ix => Array ix elt -> ST s (MutableArray s ix elt)
393 unsafeThawArray (Array l u arr#) = ST $ \ s# ->
394 case unsafeThawArray# arr# s# of
395 (# s2#, marr# #) -> (# s2#, MutableArray l u marr# #)