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