1e823f3eac68a79476fc63961352f433b47412a5
[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, indexM, headM, lastM,
26
27 -- * Subvectors
28 slice, init, tail, take, drop,
29
30 -- * Permutations
31 accum, (//), update, backpermute, reverse,
32
33 -- * Mapping
34 map, concatMap,
35
36 -- * Zipping and unzipping
37 zipWith, zipWith3, zip, zip3, unzip, unzip3,
38
39 -- * Filtering
40 filter, takeWhile, dropWhile,
41
42 -- * Searching
43 elem, notElem, find, findIndex,
44
45 -- * Folding
46 foldl, foldl1, foldl', foldl1', foldr, foldr1,
47
48 -- * Specialised folds
49 and, or, sum, product, maximum, minimum,
50
51 -- * Unfolding
52 unfoldr,
53
54 -- * Scans
55 prescanl, prescanl',
56 postscanl, postscanl',
57 scanl, scanl', scanl1, scanl1',
58
59 -- * Enumeration
60 enumFromTo, enumFromThenTo,
61
62 -- * Conversion to/from lists
63 toList, fromList
64 ) where
65
66 import Data.Vector.IVector ( IVector(..) )
67 import qualified Data.Vector.IVector as IV
68 import qualified Data.Vector.Mutable as Mut
69 import Data.Primitive.Array
70
71 import Control.Monad.ST ( runST )
72
73 import Prelude hiding ( length, null,
74 replicate, (++),
75 head, last,
76 init, tail, take, drop, reverse,
77 map, concatMap,
78 zipWith, zipWith3, zip, zip3, unzip, unzip3,
79 filter, takeWhile, dropWhile,
80 elem, notElem,
81 foldl, foldl1, foldr, foldr1,
82 and, or, sum, product, minimum, maximum,
83 scanl, scanl1,
84 enumFromTo, enumFromThenTo )
85
86 import qualified Prelude
87
88 data Vector a = Vector {-# UNPACK #-} !Int
89 {-# UNPACK #-} !Int
90 {-# UNPACK #-} !(Array a)
91
92 instance Show a => Show (Vector a) where
93 show = (Prelude.++ " :: Data.Vector.Vector") . ("fromList " Prelude.++) . show . toList
94
95 instance IVector Vector a where
96 {-# INLINE vnew #-}
97 vnew init = runST (do
98 Mut.Vector i n marr <- init
99 arr <- unsafeFreezeArray marr
100 return (Vector i n arr))
101
102 {-# INLINE vlength #-}
103 vlength (Vector _ n _) = n
104
105 {-# INLINE unsafeSlice #-}
106 unsafeSlice (Vector i _ arr) j n = Vector (i+j) n arr
107
108 {-# INLINE unsafeIndexM #-}
109 unsafeIndexM (Vector i _ arr) j = indexArrayM arr (i+j)
110
111 instance Eq a => Eq (Vector a) where
112 {-# INLINE (==) #-}
113 (==) = IV.eq
114
115 instance Ord a => Ord (Vector a) where
116 {-# INLINE compare #-}
117 compare = IV.cmp
118
119 -- Length
120 -- ------
121
122 length :: Vector a -> Int
123 {-# INLINE length #-}
124 length = IV.length
125
126 null :: Vector a -> Bool
127 {-# INLINE null #-}
128 null = IV.null
129
130 -- Construction
131 -- ------------
132
133 -- | Empty vector
134 empty :: Vector a
135 {-# INLINE empty #-}
136 empty = IV.empty
137
138 -- | Vector with exaclty one element
139 singleton :: a -> Vector a
140 {-# INLINE singleton #-}
141 singleton = IV.singleton
142
143 -- | Vector of the given length with the given value in each position
144 replicate :: Int -> a -> Vector a
145 {-# INLINE replicate #-}
146 replicate = IV.replicate
147
148 -- | Prepend an element
149 cons :: a -> Vector a -> Vector a
150 {-# INLINE cons #-}
151 cons = IV.cons
152
153 -- | Append an element
154 snoc :: Vector a -> a -> Vector a
155 {-# INLINE snoc #-}
156 snoc = IV.snoc
157
158 infixr 5 ++
159 -- | Concatenate two vectors
160 (++) :: Vector a -> Vector a -> Vector a
161 {-# INLINE (++) #-}
162 (++) = (IV.++)
163
164 -- | Create a copy of a vector. Useful when dealing with slices.
165 copy :: Vector a -> Vector a
166 {-# INLINE copy #-}
167 copy = IV.copy
168
169 -- Accessing individual elements
170 -- -----------------------------
171
172 -- | Indexing
173 (!) :: Vector a -> Int -> a
174 {-# INLINE (!) #-}
175 (!) = (IV.!)
176
177 -- | First element
178 head :: Vector a -> a
179 {-# INLINE head #-}
180 head = IV.head
181
182 -- | Last element
183 last :: Vector a -> a
184 {-# INLINE last #-}
185 last = IV.last
186
187 -- | Monadic indexing which can be strict in the vector while remaining lazy in
188 -- the element
189 indexM :: Monad m => Vector a -> Int -> m a
190 {-# INLINE indexM #-}
191 indexM = IV.indexM
192
193 headM :: Monad m => Vector a -> m a
194 {-# INLINE headM #-}
195 headM = IV.headM
196
197 lastM :: Monad m => Vector a -> m a
198 {-# INLINE lastM #-}
199 lastM = IV.lastM
200
201 -- Subarrays
202 -- ---------
203
204 -- | Yield a part of the vector without copying it. Safer version of
205 -- 'unsafeSlice'.
206 slice :: Vector a -> Int -- ^ starting index
207 -> Int -- ^ length
208 -> Vector a
209 {-# INLINE slice #-}
210 slice = IV.slice
211
212 -- | Yield all but the last element without copying.
213 init :: Vector a -> Vector a
214 {-# INLINE init #-}
215 init = IV.init
216
217 -- | All but the first element (without copying).
218 tail :: Vector a -> Vector a
219 {-# INLINE tail #-}
220 tail = IV.tail
221
222 -- | Yield the first @n@ elements without copying.
223 take :: Int -> Vector a -> Vector a
224 {-# INLINE take #-}
225 take = IV.take
226
227 -- | Yield all but the first @n@ elements without copying.
228 drop :: Int -> Vector a -> Vector a
229 {-# INLINE drop #-}
230 drop = IV.drop
231
232 -- Permutations
233 -- ------------
234
235 accum :: (a -> b -> a) -> Vector a -> [(Int,b)] -> Vector a
236 {-# INLINE accum #-}
237 accum = IV.accum
238
239 (//) :: Vector a -> [(Int, a)] -> Vector a
240 {-# INLINE (//) #-}
241 (//) = (IV.//)
242
243 update :: Vector a -> Vector (Int, a) -> Vector a
244 {-# INLINE update #-}
245 update = IV.update
246
247 backpermute :: Vector a -> Vector Int -> Vector a
248 {-# INLINE backpermute #-}
249 backpermute = IV.backpermute
250
251 reverse :: Vector a -> Vector a
252 {-# INLINE reverse #-}
253 reverse = IV.reverse
254
255 -- Mapping
256 -- -------
257
258 -- | Map a function over a vector
259 map :: (a -> b) -> Vector a -> Vector b
260 {-# INLINE map #-}
261 map = IV.map
262
263 concatMap :: (a -> Vector b) -> Vector a -> Vector b
264 {-# INLINE concatMap #-}
265 concatMap = IV.concatMap
266
267 -- Zipping/unzipping
268 -- -----------------
269
270 -- | Zip two vectors with the given function.
271 zipWith :: (a -> b -> c) -> Vector a -> Vector b -> Vector c
272 {-# INLINE zipWith #-}
273 zipWith = IV.zipWith
274
275 -- | Zip three vectors with the given function.
276 zipWith3 :: (a -> b -> c -> d) -> Vector a -> Vector b -> Vector c -> Vector d
277 {-# INLINE zipWith3 #-}
278 zipWith3 = IV.zipWith3
279
280 zip :: Vector a -> Vector b -> Vector (a, b)
281 {-# INLINE zip #-}
282 zip = IV.zip
283
284 zip3 :: Vector a -> Vector b -> Vector c -> Vector (a, b, c)
285 {-# INLINE zip3 #-}
286 zip3 = IV.zip3
287
288 unzip :: Vector (a, b) -> (Vector a, Vector b)
289 {-# INLINE unzip #-}
290 unzip = IV.unzip
291
292 unzip3 :: Vector (a, b, c) -> (Vector a, Vector b, Vector c)
293 {-# INLINE unzip3 #-}
294 unzip3 = IV.unzip3
295
296 -- Filtering
297 -- ---------
298
299 -- | Drop elements which do not satisfy the predicate
300 filter :: (a -> Bool) -> Vector a -> Vector a
301 {-# INLINE filter #-}
302 filter = IV.filter
303
304 -- | Yield the longest prefix of elements satisfying the predicate.
305 takeWhile :: (a -> Bool) -> Vector a -> Vector a
306 {-# INLINE takeWhile #-}
307 takeWhile = IV.takeWhile
308
309 -- | Drop the longest prefix of elements that satisfy the predicate.
310 dropWhile :: (a -> Bool) -> Vector a -> Vector a
311 {-# INLINE dropWhile #-}
312 dropWhile = IV.dropWhile
313
314 -- Searching
315 -- ---------
316
317 infix 4 `elem`
318 -- | Check whether the vector contains an element
319 elem :: Eq a => a -> Vector a -> Bool
320 {-# INLINE elem #-}
321 elem = IV.elem
322
323 infix 4 `notElem`
324 -- | Inverse of `elem`
325 notElem :: Eq a => a -> Vector a -> Bool
326 {-# INLINE notElem #-}
327 notElem = IV.notElem
328
329 -- | Yield 'Just' the first element matching the predicate or 'Nothing' if no
330 -- such element exists.
331 find :: (a -> Bool) -> Vector a -> Maybe a
332 {-# INLINE find #-}
333 find = IV.find
334
335 -- | Yield 'Just' the index of the first element matching the predicate or
336 -- 'Nothing' if no such element exists.
337 findIndex :: (a -> Bool) -> Vector a -> Maybe Int
338 {-# INLINE findIndex #-}
339 findIndex = IV.findIndex
340
341 -- Folding
342 -- -------
343
344 -- | Left fold
345 foldl :: (a -> b -> a) -> a -> Vector b -> a
346 {-# INLINE foldl #-}
347 foldl = IV.foldl
348
349 -- | Lefgt fold on non-empty vectors
350 foldl1 :: (a -> a -> a) -> Vector a -> a
351 {-# INLINE foldl1 #-}
352 foldl1 = IV.foldl1
353
354 -- | Left fold with strict accumulator
355 foldl' :: (a -> b -> a) -> a -> Vector b -> a
356 {-# INLINE foldl' #-}
357 foldl' = IV.foldl'
358
359 -- | Left fold on non-empty vectors with strict accumulator
360 foldl1' :: (a -> a -> a) -> Vector a -> a
361 {-# INLINE foldl1' #-}
362 foldl1' = IV.foldl1'
363
364 -- | Right fold
365 foldr :: (a -> b -> b) -> b -> Vector a -> b
366 {-# INLINE foldr #-}
367 foldr = IV.foldr
368
369 -- | Right fold on non-empty vectors
370 foldr1 :: (a -> a -> a) -> Vector a -> a
371 {-# INLINE foldr1 #-}
372 foldr1 = IV.foldr1
373
374 -- Specialised folds
375 -- -----------------
376
377 and :: Vector Bool -> Bool
378 {-# INLINE and #-}
379 and = IV.and
380
381 or :: Vector Bool -> Bool
382 {-# INLINE or #-}
383 or = IV.or
384
385 sum :: Num a => Vector a -> a
386 {-# INLINE sum #-}
387 sum = IV.sum
388
389 product :: Num a => Vector a -> a
390 {-# INLINE product #-}
391 product = IV.product
392
393 maximum :: Ord a => Vector a -> a
394 {-# INLINE maximum #-}
395 maximum = IV.maximum
396
397 minimum :: Ord a => Vector a -> a
398 {-# INLINE minimum #-}
399 minimum = IV.minimum
400
401 -- Unfolding
402 -- ---------
403
404 unfoldr :: (b -> Maybe (a, b)) -> b -> Vector a
405 {-# INLINE unfoldr #-}
406 unfoldr = IV.unfoldr
407
408 -- Scans
409 -- -----
410
411 -- | Prefix scan
412 prescanl :: (a -> b -> a) -> a -> Vector b -> Vector a
413 {-# INLINE prescanl #-}
414 prescanl = IV.prescanl
415
416 -- | Prefix scan with strict accumulator
417 prescanl' :: (a -> b -> a) -> a -> Vector b -> Vector a
418 {-# INLINE prescanl' #-}
419 prescanl' = IV.prescanl'
420
421 -- | Suffix scan
422 postscanl :: (a -> b -> a) -> a -> Vector b -> Vector a
423 {-# INLINE postscanl #-}
424 postscanl = IV.postscanl
425
426 -- | Suffix scan with strict accumulator
427 postscanl' :: (a -> b -> a) -> a -> Vector b -> Vector a
428 {-# INLINE postscanl' #-}
429 postscanl' = IV.postscanl'
430
431 -- | Haskell-style scan
432 scanl :: (a -> b -> a) -> a -> Vector b -> Vector a
433 {-# INLINE scanl #-}
434 scanl = IV.scanl
435
436 -- | Haskell-style scan with strict accumulator
437 scanl' :: (a -> b -> a) -> a -> Vector b -> Vector a
438 {-# INLINE scanl' #-}
439 scanl' = IV.scanl'
440
441 -- | Scan over a non-empty 'Vector'
442 scanl1 :: (a -> a -> a) -> Vector a -> Vector a
443 {-# INLINE scanl1 #-}
444 scanl1 = IV.scanl1
445
446 -- | Scan over a non-empty 'Vector' with a strict accumulator
447 scanl1' :: (a -> a -> a) -> Vector a -> Vector a
448 {-# INLINE scanl1' #-}
449 scanl1' = IV.scanl1'
450
451 -- Enumeration
452 -- -----------
453
454 enumFromTo :: Enum a => a -> a -> Vector a
455 {-# INLINE enumFromTo #-}
456 enumFromTo = IV.enumFromTo
457
458 enumFromThenTo :: Enum a => a -> a -> a -> Vector a
459 {-# INLINE enumFromThenTo #-}
460 enumFromThenTo = IV.enumFromThenTo
461
462 -- Conversion to/from lists
463 -- ------------------------
464
465 -- | Convert a vector to a list
466 toList :: Vector a -> [a]
467 {-# INLINE toList #-}
468 toList = IV.toList
469
470 -- | Convert a list to a vector
471 fromList :: [a] -> Vector a
472 {-# INLINE fromList #-}
473 fromList = IV.fromList
474