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