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