Show instances for boxed and unboxed immutable vectors
[darcs-mirrors/vector.git] / Data / Vector.hs
1 {-# LANGUAGE MagicHash, UnboxedTuples, FlexibleInstances, MultiParamTypeClasses #-}
2
3 -- |
4 -- Module : Data.Vector
5 -- Copyright : (c) Roman Leshchinskiy 2008
6 -- License : BSD-style
7 --
8 -- Maintainer : Roman Leshchinskiy <rl@cse.unsw.edu.au>
9 -- Stability : experimental
10 -- Portability : non-portable
11 --
12 -- Boxed vectors
13 --
14
15 module Data.Vector (
16 Vector,
17
18 -- * Length information
19 length, null,
20
21 -- * Construction
22 empty, singleton, cons, snoc, replicate, (++), copy,
23
24 -- * Accessing individual elements
25 (!), head, last,
26
27 -- * Subvectors
28 slice, init, tail, take, drop,
29
30 -- * Permutations
31 accum, (//), update, backpermute,
32
33 -- * Mapping and zipping
34 map, zipWith, zip,
35
36 -- * Filtering
37 filter, takeWhile, dropWhile,
38
39 -- * Searching
40 elem, notElem, find, findIndex,
41
42 -- * Folding
43 foldl, foldl1, foldl', foldl1', foldr, foldr1,
44
45 -- * Scans
46 prescanl, prescanl',
47
48 -- * Conversion to/from lists
49 toList, fromList
50 ) where
51
52 import Data.Vector.IVector ( IVector(..) )
53 import qualified Data.Vector.IVector as IV
54 import qualified Data.Vector.Mutable as Mut
55
56 import Control.Monad.ST ( runST )
57
58 import GHC.ST ( ST(..) )
59 import GHC.Prim ( Array#, unsafeFreezeArray#, indexArray#, (+#) )
60 import GHC.Base ( Int(..) )
61
62 import Prelude hiding ( length, null,
63 replicate, (++),
64 head, last,
65 init, tail, take, drop,
66 map, zipWith, zip,
67 filter, takeWhile, dropWhile,
68 elem, notElem,
69 foldl, foldl1, foldr, foldr1 )
70
71 data Vector a = Vector {-# UNPACK #-} !Int
72 {-# UNPACK #-} !Int
73 (Array# a)
74
75 instance Show a => Show (Vector a) where
76 show = (Prelude.++ " :: Data.Vector.Vector") . ("fromList " Prelude.++) . show . toList
77
78 instance IVector Vector a where
79 {-# INLINE vnew #-}
80 vnew init = runST (do
81 Mut.Vector i n marr# <- init
82 ST (\s# -> case unsafeFreezeArray# marr# s# of
83 (# s2#, arr# #) -> (# s2#, Vector i n arr# #)))
84
85 {-# INLINE vlength #-}
86 vlength (Vector _ n _) = n
87
88 {-# INLINE unsafeSlice #-}
89 unsafeSlice (Vector i _ arr#) j n = Vector (i+j) n arr#
90
91 {-# INLINE unsafeIndex #-}
92 unsafeIndex (Vector (I# i#) _ arr#) (I# j#) f
93 = case indexArray# arr# (i# +# j#) of (# x #) -> f x
94
95 instance Eq a => Eq (Vector a) where
96 {-# INLINE (==) #-}
97 (==) = IV.eq
98
99 instance Ord a => Ord (Vector a) where
100 {-# INLINE compare #-}
101 compare = IV.cmp
102
103 -- Length
104 -- ------
105
106 length :: Vector a -> Int
107 {-# INLINE length #-}
108 length = IV.length
109
110 null :: Vector a -> Bool
111 {-# INLINE null #-}
112 null = IV.null
113
114 -- Construction
115 -- ------------
116
117 -- | Empty vector
118 empty :: Vector a
119 {-# INLINE empty #-}
120 empty = IV.empty
121
122 -- | Vector with exaclty one element
123 singleton :: a -> Vector a
124 {-# INLINE singleton #-}
125 singleton = IV.singleton
126
127 -- | Vector of the given length with the given value in each position
128 replicate :: Int -> a -> Vector a
129 {-# INLINE replicate #-}
130 replicate = IV.replicate
131
132 -- | Prepend an element
133 cons :: a -> Vector a -> Vector a
134 {-# INLINE cons #-}
135 cons = IV.cons
136
137 -- | Append an element
138 snoc :: Vector a -> a -> Vector a
139 {-# INLINE snoc #-}
140 snoc = IV.snoc
141
142 infixr 5 ++
143 -- | Concatenate two vectors
144 (++) :: Vector a -> Vector a -> Vector a
145 {-# INLINE (++) #-}
146 (++) = (IV.++)
147
148 -- | Create a copy of a vector. Useful when dealing with slices.
149 copy :: Vector a -> Vector a
150 {-# INLINE copy #-}
151 copy = IV.copy
152
153 -- Accessing individual elements
154 -- -----------------------------
155
156 -- | Indexing
157 (!) :: Vector a -> Int -> a
158 {-# INLINE (!) #-}
159 (!) = (IV.!)
160
161 -- | First element
162 head :: Vector a -> a
163 {-# INLINE head #-}
164 head = IV.head
165
166 -- | Last element
167 last :: Vector a -> a
168 {-# INLINE last #-}
169 last = IV.last
170
171 -- Subarrays
172 -- ---------
173
174 -- | Yield a part of the vector without copying it. Safer version of
175 -- 'unsafeSlice'.
176 slice :: Vector a -> Int -- ^ starting index
177 -> Int -- ^ length
178 -> Vector a
179 {-# INLINE slice #-}
180 slice = IV.slice
181
182 -- | Yield all but the last element without copying.
183 init :: Vector a -> Vector a
184 {-# INLINE init #-}
185 init = IV.init
186
187 -- | All but the first element (without copying).
188 tail :: Vector a -> Vector a
189 {-# INLINE tail #-}
190 tail = IV.tail
191
192 -- | Yield the first @n@ elements without copying.
193 take :: Int -> Vector a -> Vector a
194 {-# INLINE take #-}
195 take = IV.take
196
197 -- | Yield all but the first @n@ elements without copying.
198 drop :: Int -> Vector a -> Vector a
199 {-# INLINE drop #-}
200 drop = IV.drop
201
202 -- Permutations
203 -- ------------
204
205 accum :: (a -> b -> a) -> Vector a -> [(Int,b)] -> Vector a
206 {-# INLINE accum #-}
207 accum = IV.accum
208
209 (//) :: Vector a -> [(Int, a)] -> Vector a
210 {-# INLINE (//) #-}
211 (//) = (IV.//)
212
213 update :: Vector a -> Vector (Int, a) -> Vector a
214 {-# INLINE update #-}
215 update = IV.update
216
217 backpermute :: Vector a -> Vector Int -> Vector a
218 {-# INLINE backpermute #-}
219 backpermute = IV.backpermute
220
221 -- Mapping/zipping
222 -- ---------------
223
224 -- | Map a function over a vector
225 map :: (a -> b) -> Vector a -> Vector b
226 {-# INLINE map #-}
227 map = IV.map
228
229 -- | Zip two vectors with the given function.
230 zipWith :: (a -> b -> c) -> Vector a -> Vector b -> Vector c
231 {-# INLINE zipWith #-}
232 zipWith = IV.zipWith
233
234 zip :: Vector a -> Vector b -> Vector (a, b)
235 {-# INLINE zip #-}
236 zip = IV.zip
237
238 -- Filtering
239 -- ---------
240
241 -- | Drop elements which do not satisfy the predicate
242 filter :: (a -> Bool) -> Vector a -> Vector a
243 {-# INLINE filter #-}
244 filter = IV.filter
245
246 -- | Yield the longest prefix of elements satisfying the predicate.
247 takeWhile :: (a -> Bool) -> Vector a -> Vector a
248 {-# INLINE takeWhile #-}
249 takeWhile = IV.takeWhile
250
251 -- | Drop the longest prefix of elements that satisfy the predicate.
252 dropWhile :: (a -> Bool) -> Vector a -> Vector a
253 {-# INLINE dropWhile #-}
254 dropWhile = IV.dropWhile
255
256 -- Searching
257 -- ---------
258
259 infix 4 `elem`
260 -- | Check whether the vector contains an element
261 elem :: Eq a => a -> Vector a -> Bool
262 {-# INLINE elem #-}
263 elem = IV.elem
264
265 infix 4 `notElem`
266 -- | Inverse of `elem`
267 notElem :: Eq a => a -> Vector a -> Bool
268 {-# INLINE notElem #-}
269 notElem = IV.notElem
270
271 -- | Yield 'Just' the first element matching the predicate or 'Nothing' if no
272 -- such element exists.
273 find :: (a -> Bool) -> Vector a -> Maybe a
274 {-# INLINE find #-}
275 find = IV.find
276
277 -- | Yield 'Just' the index of the first element matching the predicate or
278 -- 'Nothing' if no such element exists.
279 findIndex :: (a -> Bool) -> Vector a -> Maybe Int
280 {-# INLINE findIndex #-}
281 findIndex = IV.findIndex
282
283 -- Folding
284 -- -------
285
286 -- | Left fold
287 foldl :: (a -> b -> a) -> a -> Vector b -> a
288 {-# INLINE foldl #-}
289 foldl = IV.foldl
290
291 -- | Lefgt fold on non-empty vectors
292 foldl1 :: (a -> a -> a) -> Vector a -> a
293 {-# INLINE foldl1 #-}
294 foldl1 = IV.foldl1
295
296 -- | Left fold with strict accumulator
297 foldl' :: (a -> b -> a) -> a -> Vector b -> a
298 {-# INLINE foldl' #-}
299 foldl' = IV.foldl'
300
301 -- | Left fold on non-empty vectors with strict accumulator
302 foldl1' :: (a -> a -> a) -> Vector a -> a
303 {-# INLINE foldl1' #-}
304 foldl1' = IV.foldl1'
305
306 -- | Right fold
307 foldr :: (a -> b -> b) -> b -> Vector a -> b
308 {-# INLINE foldr #-}
309 foldr = IV.foldr
310
311 -- | Right fold on non-empty vectors
312 foldr1 :: (a -> a -> a) -> Vector a -> a
313 {-# INLINE foldr1 #-}
314 foldr1 = IV.foldr1
315
316 -- Scans
317 -- -----
318
319 -- | Prefix scan
320 prescanl :: (a -> b -> a) -> a -> Vector b -> Vector a
321 {-# INLINE prescanl #-}
322 prescanl = IV.prescanl
323
324 -- | Prefix scan with strict accumulator
325 prescanl' :: (a -> b -> a) -> a -> Vector b -> Vector a
326 {-# INLINE prescanl' #-}
327 prescanl' = IV.prescanl'
328
329 -- | Convert a vector to a list
330 toList :: Vector a -> [a]
331 {-# INLINE toList #-}
332 toList = IV.toList
333
334 -- | Convert a list to a vector
335 fromList :: [a] -> Vector a
336 {-# INLINE fromList #-}
337 fromList = IV.fromList
338