2 % (c) The AQUA Project, Glasgow University, 1994-1999
5 \section[Array]{Module @Array@}
8 {-# OPTIONS -fno-implicit-prelude #-}
13 module Ix -- export all of Ix
14 , Array -- Array type is abstract
16 , array -- :: (Ix a) => (a,a) -> [(a,b)] -> Array a b
17 , listArray -- :: (Ix a) => (a,a) -> [b] -> Array a b
18 , (!) -- :: (Ix a) => Array a b -> a -> b
19 , bounds -- :: (Ix a) => Array a b -> (a,a)
20 , indices -- :: (Ix a) => Array a b -> [a]
21 , elems -- :: (Ix a) => Array a b -> [b]
22 , assocs -- :: (Ix a) => Array a b -> [(a,b)]
23 , accumArray -- :: (Ix a) => (b -> c -> b) -> b -> (a,a) -> [(a,c)] -> Array a b
24 , (//) -- :: (Ix a) => Array a b -> [(a,b)] -> Array a b
25 , accum -- :: (Ix a) => (b -> c -> b) -> Array a b -> [(a,c)] -> Array a b
26 , ixmap -- :: (Ix a, Ix b) => (a,a) -> (a -> b) -> Array b c -> Array a b
30 -- Ix a => Functor (Array a)
31 -- (Ix a, Eq b) => Eq (Array a b)
32 -- (Ix a, Ord b) => Ord (Array a b)
33 -- (Ix a, Show a, Show b) => Show (Array a b)
34 -- (Ix a, Read a, Read b) => Read (Array a b)
37 -- Implementation checked wrt. Haskell 98 lib report, 1/99.
45 import PrelArr -- Most of the hard work is done here
58 %*********************************************************
60 \subsection{Definitions of array, !, bounds}
62 %*********************************************************
66 #ifdef USE_FOLDR_BUILD
67 {-# INLINE indices #-}
72 {-# SPECIALISE listArray :: (Int,Int) -> [b] -> Array Int b #-}
73 listArray :: (Ix a) => (a,a) -> [b] -> Array a b
74 listArray b vs = array b (zip (range b) vs)
76 {-# SPECIALISE indices :: Array Int b -> [Int] #-}
77 indices :: (Ix a) => Array a b -> [a]
78 indices = range . bounds
80 {-# SPECIALISE elems :: Array Int b -> [b] #-}
81 elems :: (Ix a) => Array a b -> [b]
82 elems a = [a!i | i <- indices a]
84 {-# SPECIALISE assocs :: Array Int b -> [(Int,b)] #-}
85 assocs :: (Ix a) => Array a b -> [(a,b)]
86 assocs a = [(i, a!i) | i <- indices a]
88 {-# SPECIALISE amap :: (b -> c) -> Array Int b -> Array Int c #-}
89 amap :: (Ix a) => (b -> c) -> Array a b -> Array a c
90 amap f a = array b [(i, f (a!i)) | i <- range b]
93 ixmap :: (Ix a, Ix b) => (a,a) -> (a -> b) -> Array b c -> Array a c
94 ixmap b f a = array b [(i, a ! f i) | i <- range b]
98 %*********************************************************
100 \subsection{Instance declarations for Array type}
102 %*********************************************************
105 instance Ix a => Functor (Array a) where
108 instance (Ix a, Eq b) => Eq (Array a b) where
109 a == a' = assocs a == assocs a'
110 a /= a' = assocs a /= assocs a'
112 instance (Ix a, Ord b) => Ord (Array a b) where
113 compare a b = compare (assocs a) (assocs b)
115 instance (Ix a, Show a, Show b) => Show (Array a b) where
116 showsPrec p a = showParen (p > 9) (
117 showString "array " .
118 shows (bounds a) . showChar ' ' .
120 showList = showList__ (showsPrec 0)
123 instance (Ix a, Read a, Read b) => Read (Array a b) where
124 readsPrec p = readParen (p > 9)
125 (\r -> [(array b as, u) | ("array",s) <- lex r,
128 readList = readList__ (readsPrec 0)
135 data Array ix elt = Array (ix,ix) (PrimArray elt)
137 array :: Ix a => (a,a) -> [(a,b)] -> Array a b
138 array ixs@(ix_start, ix_end) ivs = primRunST (do
139 { mut_arr <- primNewArray (rangeSize ixs) arrEleBottom
140 ; mapM_ (\ (i,v) -> primWriteArray mut_arr (index ixs i) v) ivs
141 ; arr <- primUnsafeFreezeArray mut_arr
142 ; return (Array ixs arr)
146 arrEleBottom = error "(Array.!): undefined array element"
148 listArray :: Ix a => (a,a) -> [b] -> Array a b
149 listArray b vs = array b (zipWith (\ a b -> (a,b)) (range b) vs)
151 (!) :: Ix a => Array a b -> a -> b
152 (Array bounds arr) ! i = primIndexArray arr (index bounds i)
154 bounds :: Ix a => Array a b -> (a,a)
155 bounds (Array b _) = b
157 indices :: Ix a => Array a b -> [a]
158 indices = range . bounds
160 elems :: Ix a => Array a b -> [b]
161 elems a = [a!i | i <- indices a]
163 assocs :: Ix a => Array a b -> [(a,b)]
164 assocs a = [(i, a!i) | i <- indices a]
166 (//) :: Ix a => Array a b -> [(a,b)] -> Array a b
167 a // us = array (bounds a)
168 ([(i,a!i) | i <- indices a \\ [i | (i,_) <- us]]
171 accum :: Ix a => (b -> c -> b) -> Array a b -> [(a,c)] -> Array a b
172 accum f = foldl (\a (i,v) -> a // [(i,f (a!i) v)])
174 accumArray :: Ix a => (b -> c -> b) -> b -> (a,a) -> [(a,c)] -> Array a b
175 accumArray f z b = accum f (array b [(i,z) | i <- range b])
177 ixmap :: (Ix a, Ix b) => (a,a) -> (a -> b) -> Array b c -> Array a c
178 ixmap b f a = array b [(i, a ! f i) | i <- range b]
181 instance (Ix a) => Functor (Array a) where
182 fmap f a = array (bounds a) [(i, f(a!i)) | i <- indices a]
184 instance (Ix a, Eq b) => Eq (Array a b) where
185 a == a' = assocs a == assocs a'
187 instance (Ix a, Ord b) => Ord (Array a b) where
188 a <= a' = assocs a <= assocs a'
191 instance (Ix a, Show a, Show b) => Show (Array a b) where
192 showsPrec p a = showParen (p > 9) (
193 showString "array " .
194 shows (bounds a) . showChar ' ' .
197 instance (Ix a, Read a, Read b) => Read (Array a b) where
198 readsPrec p = readParen (p > 9)
199 (\r -> [(array b as, u) | ("array",s) <- lex r,