Add monadic vector combinators
[darcs-mirrors/vector.git] / Data / Vector.hs
1 {-# LANGUAGE FlexibleInstances, MultiParamTypeClasses, TypeFamilies, Rank2Types #-}
2
3 -- |
4 -- Module : Data.Vector
5 -- Copyright : (c) Roman Leshchinskiy 2008-2010
6 -- License : BSD-style
7 --
8 -- Maintainer : Roman Leshchinskiy <rl@cse.unsw.edu.au>
9 -- Stability : experimental
10 -- Portability : non-portable
11 --
12 -- A library for boxed vectors (that is, polymorphic arrays capable of
13 -- holding any Haskell value). The vectors come in two flavors:
14 --
15 -- * mutable
16 --
17 -- * immutable
18 --
19 -- and support a rich interface of both list-like operations, and bulk
20 -- array operations.
21 --
22 -- For unboxed arrays, use the 'Data.Vector.Unboxed' interface.
23 --
24
25 module Data.Vector (
26
27 -- * The pure and mutable array types
28 Vector, MVector,
29
30 -- * Constructing vectors
31 empty,
32 singleton,
33 cons,
34 snoc,
35 (++),
36 replicate,
37 generate,
38 force,
39
40 -- * Operations based on length information
41 length,
42 null,
43
44 -- * Accessing individual elements
45 (!),
46 head,
47 last,
48
49 -- ** Accessors in a monad
50 indexM,
51 headM,
52 lastM,
53
54 -- ** Accessor functions with no bounds checking
55 unsafeIndex, unsafeHead, unsafeLast,
56 unsafeIndexM, unsafeHeadM, unsafeLastM,
57
58 -- * Subvectors
59 init,
60 tail,
61 take,
62 drop,
63 slice,
64
65 -- * Subvector construction without bounds checks
66 unsafeSlice, unsafeInit, unsafeTail, unsafeTake, unsafeDrop,
67
68 -- * Permutations
69 accum, accumulate, accumulate_,
70 (//), update, update_,
71 backpermute, reverse,
72 unsafeAccum, unsafeAccumulate, unsafeAccumulate_,
73 unsafeUpd, unsafeUpdate, unsafeUpdate_,
74 unsafeBackpermute,
75
76 -- * Mapping
77 map, imap, concatMap,
78
79 -- * Zipping and unzipping
80 zipWith, zipWith3, zipWith4, zipWith5, zipWith6,
81 izipWith, izipWith3, izipWith4, izipWith5, izipWith6,
82 zip, zip3, zip4, zip5, zip6,
83 unzip, unzip3, unzip4, unzip5, unzip6,
84
85 -- * Filtering
86 filter, ifilter, takeWhile, dropWhile,
87 partition, unstablePartition, span, break,
88
89 -- * Searching
90 elem, notElem, find, findIndex, findIndices, elemIndex, elemIndices,
91
92 -- * Folding
93 foldl, foldl1, foldl', foldl1', foldr, foldr1, foldr', foldr1',
94 ifoldl, ifoldl', ifoldr, ifoldr',
95
96 -- * Specialised folds
97 all, any, and, or,
98 sum, product,
99 maximum, maximumBy, minimum, minimumBy,
100 minIndex, minIndexBy, maxIndex, maxIndexBy,
101
102 -- * Unfolding
103 unfoldr, unfoldrN,
104
105 -- * Scans
106 prescanl, prescanl',
107 postscanl, postscanl',
108 scanl, scanl', scanl1, scanl1',
109 prescanr, prescanr',
110 postscanr, postscanr',
111 scanr, scanr', scanr1, scanr1',
112
113 -- * Enumeration
114 enumFromN, enumFromStepN, enumFromTo, enumFromThenTo,
115
116 -- * Conversion to/from lists
117 toList, fromList, fromListN,
118
119 -- * Monadic operations
120 replicateM, mapM, mapM_, forM, forM_, zipWithM, zipWithM_, filterM,
121 foldM, foldM', fold1M, fold1M',
122
123 -- * Destructive operations
124 create, modify, copy, unsafeCopy
125 ) where
126
127 import qualified Data.Vector.Generic as G
128 import Data.Vector.Mutable ( MVector(..) )
129 import Data.Primitive.Array
130 import qualified Data.Vector.Fusion.Stream as Stream
131
132 import Control.Monad ( liftM )
133 import Control.Monad.ST ( ST )
134 import Control.Monad.Primitive
135
136 import Prelude hiding ( length, null,
137 replicate, (++),
138 head, last,
139 init, tail, take, drop, reverse,
140 map, concatMap,
141 zipWith, zipWith3, zip, zip3, unzip, unzip3,
142 filter, takeWhile, dropWhile, span, break,
143 elem, notElem,
144 foldl, foldl1, foldr, foldr1,
145 all, any, and, or, sum, product, minimum, maximum,
146 scanl, scanl1, scanr, scanr1,
147 enumFromTo, enumFromThenTo,
148 mapM, mapM_ )
149
150 import qualified Prelude
151
152 import Data.Typeable ( Typeable )
153 import Data.Data ( Data(..) )
154
155 -- | Boxed vectors, supporting efficient slicing.
156 data Vector a = Vector {-# UNPACK #-} !Int
157 {-# UNPACK #-} !Int
158 {-# UNPACK #-} !(Array a)
159 deriving ( Typeable )
160
161 instance Show a => Show (Vector a) where
162 show = (Prelude.++ " :: Data.Vector.Vector") . ("fromList " Prelude.++) . show . toList
163
164 instance Data a => Data (Vector a) where
165 gfoldl = G.gfoldl
166 toConstr _ = error "toConstr"
167 gunfold _ _ = error "gunfold"
168 dataTypeOf _ = G.mkType "Data.Vector.Vector"
169 dataCast1 = G.dataCast
170
171 type instance G.Mutable Vector = MVector
172
173 instance G.Vector Vector a where
174 {-# INLINE unsafeFreeze #-}
175 unsafeFreeze (MVector i n marr)
176 = Vector i n `liftM` unsafeFreezeArray marr
177
178 {-# INLINE basicLength #-}
179 basicLength (Vector _ n _) = n
180
181 {-# INLINE basicUnsafeSlice #-}
182 basicUnsafeSlice j n (Vector i _ arr) = Vector (i+j) n arr
183
184 {-# INLINE basicUnsafeIndexM #-}
185 basicUnsafeIndexM (Vector i _ arr) j = indexArrayM arr (i+j)
186
187 -- See [HACKS:Eq and Ord instances]
188 instance Eq a => Eq (Vector a) where
189 {-# INLINE (==) #-}
190 xs == ys = Stream.eq (G.stream xs) (G.stream ys)
191
192 {-# INLINE (/=) #-}
193 xs /= ys = not (Stream.eq (G.stream xs) (G.stream ys))
194
195 -- See [HACKS:Eq and Ord instances]
196 instance Ord a => Ord (Vector a) where
197 {-# INLINE compare #-}
198 compare xs ys = Stream.cmp (G.stream xs) (G.stream ys)
199
200 {-# INLINE (<) #-}
201 xs < ys = Stream.cmp (G.stream xs) (G.stream ys) == LT
202
203 {-# INLINE (<=) #-}
204 xs <= ys = Stream.cmp (G.stream xs) (G.stream ys) /= GT
205
206 {-# INLINE (>) #-}
207 xs > ys = Stream.cmp (G.stream xs) (G.stream ys) == GT
208
209 {-# INLINE (>=) #-}
210 xs >= ys = Stream.cmp (G.stream xs) (G.stream ys) /= LT
211
212 -- Length
213 -- ------
214
215 -- |/O(1)/. Yield the length of a vector as an 'Int'
216 length :: Vector a -> Int
217 {-# INLINE length #-}
218 length = G.length
219
220 -- |/O(1)/. 'null' tests whether the given array is empty.
221 null :: Vector a -> Bool
222 {-# INLINE null #-}
223 null = G.null
224
225 -- Construction
226 -- ------------
227
228 -- |/O(1)/. 'empty' builds a vector of size zero.
229 empty :: Vector a
230 {-# INLINE empty #-}
231 empty = G.empty
232
233 -- |/O(1)/, Vector with exactly one element
234 singleton :: a -> Vector a
235 {-# INLINE singleton #-}
236 singleton = G.singleton
237
238 -- |/O(n)/. @'replicate' n e@ yields a vector of length @n@ storing @e@ at each position
239 replicate :: Int -> a -> Vector a
240 {-# INLINE replicate #-}
241 replicate = G.replicate
242
243 -- |/O(n)/, Generate a vector of the given length by applying a (pure)
244 -- generator function to each index
245 generate :: Int -> (Int -> a) -> Vector a
246 {-# INLINE generate #-}
247 generate = G.generate
248
249 -- |/O(n)/, Prepend an element to an array.
250 cons :: a -> Vector a -> Vector a
251 {-# INLINE cons #-}
252 cons = G.cons
253
254 -- |/O(n)/, Append an element to an array.
255 snoc :: Vector a -> a -> Vector a
256 {-# INLINE snoc #-}
257 snoc = G.snoc
258
259 infixr 5 ++
260
261 -- |/O(n)/, Concatenate two vectors
262 (++) :: Vector a -> Vector a -> Vector a
263 {-# INLINE (++) #-}
264 (++) = (G.++)
265
266 -- |/O(n)/, Create a copy of a vector.
267 -- @force@ is useful when dealing with slices, as the garbage collector
268 -- may be able to free the original vector if no further references are held.
269 --
270 force :: Vector a -> Vector a
271 {-# INLINE force #-}
272 force = G.force
273
274 -- Accessing individual elements
275 -- -----------------------------
276
277 -- |/O(1)/. Read the element in the vector at the given index.
278 (!) :: Vector a -> Int -> a
279 {-# INLINE (!) #-}
280 (!) = (G.!)
281
282 -- |/O(1)/. 'head' returns the first element of the vector
283 head :: Vector a -> a
284 {-# INLINE head #-}
285 head = G.head
286
287 -- |/O(n)/. 'last' yields the last element of an array.
288 last :: Vector a -> a
289 {-# INLINE last #-}
290 last = G.last
291
292 -- |/O(1)/, Unsafe indexing without bounds checking
293 --
294 -- By not performing bounds checks, this function may be faster when
295 -- this function is used in an inner loop)
296 --
297 unsafeIndex :: Vector a -> Int -> a
298 {-# INLINE unsafeIndex #-}
299 unsafeIndex = G.unsafeIndex
300
301 -- |/O(1)/, Yield the first element of a vector without checking if the vector is empty
302 --
303 -- By not performing bounds checks, this function may be faster when
304 -- this function is used in an inner loop)
305 unsafeHead :: Vector a -> a
306 {-# INLINE unsafeHead #-}
307 unsafeHead = G.unsafeHead
308
309 -- | Yield the last element of a vector without checking if the vector is empty
310 --
311 -- By not performing bounds checks, this function may be faster when
312 -- this function is used in an inner loop)
313 unsafeLast :: Vector a -> a
314 {-# INLINE unsafeLast #-}
315 unsafeLast = G.unsafeLast
316
317 -- | Monadic indexing which can be strict in the vector while remaining lazy in the element
318 indexM :: Monad m => Vector a -> Int -> m a
319 {-# INLINE indexM #-}
320 indexM = G.indexM
321
322 -- | Monadic head which can be strict in the vector while remaining lazy in the element
323 headM :: Monad m => Vector a -> m a
324 {-# INLINE headM #-}
325 headM = G.headM
326
327 -- | Monadic last which can be strict in the vector while remaining lazy in the element
328 lastM :: Monad m => Vector a -> m a
329 {-# INLINE lastM #-}
330 lastM = G.lastM
331
332 -- | Unsafe monadic indexing without bounds checks
333 unsafeIndexM :: Monad m => Vector a -> Int -> m a
334 {-# INLINE unsafeIndexM #-}
335 unsafeIndexM = G.unsafeIndexM
336
337 -- | Unsafe monadic head (access the first element) without bounds checks
338 unsafeHeadM :: Monad m => Vector a -> m a
339 {-# INLINE unsafeHeadM #-}
340 unsafeHeadM = G.unsafeHeadM
341
342 -- | Unsafe monadic last (access the last element) without bounds checks
343 unsafeLastM :: Monad m => Vector a -> m a
344 {-# INLINE unsafeLastM #-}
345 unsafeLastM = G.unsafeLastM
346
347 -- Subarrays
348 -- ---------
349
350 -- | /O(1)/, Yield a part of the vector without copying it.
351 --
352 slice :: Int -- ^ starting index
353 -> Int -- ^ length
354 -> Vector a
355 -> Vector a
356 {-# INLINE slice #-}
357 slice = G.slice
358
359 -- |/O(1)/, Yield all but the last element without copying.
360 init :: Vector a -> Vector a
361 {-# INLINE init #-}
362 init = G.init
363
364 -- |/O(1), Yield all but the first element (without copying).
365 tail :: Vector a -> Vector a
366 {-# INLINE tail #-}
367 tail = G.tail
368
369 -- |/O(1)/, Yield the first @n@ elements without copying.
370 take :: Int -> Vector a -> Vector a
371 {-# INLINE take #-}
372 take = G.take
373
374 -- |/O(1)/, Yield all but the first @n@ elements without copying.
375 drop :: Int -> Vector a -> Vector a
376 {-# INLINE drop #-}
377 drop = G.drop
378
379 -- |/O(1)/, Unsafely yield a part of the vector without copying it and without
380 -- performing bounds checks.
381 unsafeSlice :: Int -- ^ starting index
382 -> Int -- ^ length
383 -> Vector a
384 -> Vector a
385 {-# INLINE unsafeSlice #-}
386 unsafeSlice = G.unsafeSlice
387
388 -- |/O(1)/, Zero-copying 'init' without bounds checks.
389 unsafeInit :: Vector a -> Vector a
390 {-# INLINE unsafeInit #-}
391 unsafeInit = G.unsafeInit
392
393 -- |/O(1)/, Zero-copying 'tail' without bounds checks.
394 unsafeTail :: Vector a -> Vector a
395 {-# INLINE unsafeTail #-}
396 unsafeTail = G.unsafeTail
397
398 -- |/O(1)/, Zero-copying 'take' without bounds checks.
399 unsafeTake :: Int -> Vector a -> Vector a
400 {-# INLINE unsafeTake #-}
401 unsafeTake = G.unsafeTake
402
403 -- |/O(1)/, Zero-copying 'drop' without bounds checks.
404 unsafeDrop :: Int -> Vector a -> Vector a
405 {-# INLINE unsafeDrop #-}
406 unsafeDrop = G.unsafeDrop
407
408 -- Permutations
409 -- ------------
410
411 -- TODO there is no documentation for the accum* family of functions
412
413 -- | TODO unsafeAccum.
414 unsafeAccum :: (a -> b -> a) -> Vector a -> [(Int,b)] -> Vector a
415 {-# INLINE unsafeAccum #-}
416 unsafeAccum = G.unsafeAccum
417
418 -- | TODO unsafeAccumulate
419 unsafeAccumulate :: (a -> b -> a) -> Vector a -> Vector (Int,b) -> Vector a
420 {-# INLINE unsafeAccumulate #-}
421 unsafeAccumulate = G.unsafeAccumulate
422
423 -- | TODO unsafeAccumulate_
424 unsafeAccumulate_
425 :: (a -> b -> a) -> Vector a -> Vector Int -> Vector b -> Vector a
426 {-# INLINE unsafeAccumulate_ #-}
427 unsafeAccumulate_ = G.unsafeAccumulate_
428
429 -- | TODO accum
430 accum :: (a -> b -> a) -> Vector a -> [(Int,b)] -> Vector a
431 {-# INLINE accum #-}
432 accum = G.accum
433
434 -- | TODO accumulate
435 accumulate :: (a -> b -> a) -> Vector a -> Vector (Int,b) -> Vector a
436 {-# INLINE accumulate #-}
437 accumulate = G.accumulate
438
439 -- | TODO accumulate_
440 accumulate_ :: (a -> b -> a) -> Vector a -> Vector Int -> Vector b -> Vector a
441 {-# INLINE accumulate_ #-}
442 accumulate_ = G.accumulate_
443
444 -- | TODO unsafeUpd
445 unsafeUpd :: Vector a -> [(Int, a)] -> Vector a
446 {-# INLINE unsafeUpd #-}
447 unsafeUpd = G.unsafeUpd
448
449 -- | TODO unsafeUpdate
450 unsafeUpdate :: Vector a -> Vector (Int, a) -> Vector a
451 {-# INLINE unsafeUpdate #-}
452 unsafeUpdate = G.unsafeUpdate
453
454 -- | TODO unsafeUpdate_
455 unsafeUpdate_ :: Vector a -> Vector Int -> Vector a -> Vector a
456 {-# INLINE unsafeUpdate_ #-}
457 unsafeUpdate_ = G.unsafeUpdate_
458
459 -- | TODO (//)
460 (//) :: Vector a -> [(Int, a)] -> Vector a
461 {-# INLINE (//) #-}
462 (//) = (G.//)
463
464 -- | TODO update
465 update :: Vector a -> Vector (Int, a) -> Vector a
466 {-# INLINE update #-}
467 update = G.update
468
469 -- | TODO update_
470 update_ :: Vector a -> Vector Int -> Vector a -> Vector a
471 {-# INLINE update_ #-}
472 update_ = G.update_
473
474 -- | backpermute, courtesy Blelloch. The back-permute is a gather\/get operation.
475 backpermute :: Vector a -> Vector Int -> Vector a
476 {-# INLINE backpermute #-}
477 backpermute = G.backpermute
478
479 -- | TODO unsafeBackpermute
480 unsafeBackpermute :: Vector a -> Vector Int -> Vector a
481 {-# INLINE unsafeBackpermute #-}
482 unsafeBackpermute = G.unsafeBackpermute
483
484 -- | /O(n)/, reverse the elements of the given vector.
485 reverse :: Vector a -> Vector a
486 {-# INLINE reverse #-}
487 reverse = G.reverse
488
489 -- Mapping
490 -- -------
491
492 -- | /O(n)/, Map a function over a vector
493 map :: (a -> b) -> Vector a -> Vector b
494 {-# INLINE map #-}
495 map = G.map
496
497 -- | /O(n)/, Apply a function to every index/value pair yielding a new vector
498 imap :: (Int -> a -> b) -> Vector a -> Vector b
499 {-# INLINE imap #-}
500 imap = G.imap
501
502 -- | /O(n)/, generate a vector from each element of the input vector, then join the results.
503 concatMap :: (a -> Vector b) -> Vector a -> Vector b
504 {-# INLINE concatMap #-}
505 concatMap = G.concatMap
506
507 -- Zipping/unzipping
508 -- -----------------
509
510 -- |/O(n)/, Zip two vectors with the given function.
511 zipWith :: (a -> b -> c) -> Vector a -> Vector b -> Vector c
512 {-# INLINE zipWith #-}
513 zipWith = G.zipWith
514
515 -- |/O(n)/, Zip three vectors with the given function.
516 zipWith3 :: (a -> b -> c -> d) -> Vector a -> Vector b -> Vector c -> Vector d
517 {-# INLINE zipWith3 #-}
518 zipWith3 = G.zipWith3
519
520 -- |/O(n)/, Zip four vectors with the given function.
521 zipWith4 :: (a -> b -> c -> d -> e)
522 -> Vector a -> Vector b -> Vector c -> Vector d -> Vector e
523 {-# INLINE zipWith4 #-}
524 zipWith4 = G.zipWith4
525
526 -- |/O(n)/, Zip five vectors with the given function.
527 zipWith5 :: (a -> b -> c -> d -> e -> f)
528 -> Vector a -> Vector b -> Vector c -> Vector d -> Vector e
529 -> Vector f
530 {-# INLINE zipWith5 #-}
531 zipWith5 = G.zipWith5
532
533 -- |/O(n)/, Zip six vectors with the given function.
534 zipWith6 :: (a -> b -> c -> d -> e -> f -> g)
535 -> Vector a -> Vector b -> Vector c -> Vector d -> Vector e
536 -> Vector f -> Vector g
537 {-# INLINE zipWith6 #-}
538 zipWith6 = G.zipWith6
539
540 -- |/O(n)/, Zip two vectors and their indices with the given function.
541 izipWith :: (Int -> a -> b -> c) -> Vector a -> Vector b -> Vector c
542 {-# INLINE izipWith #-}
543 izipWith = G.izipWith
544
545 -- |/O(n)/, Zip three vectors and their indices with the given function.
546 izipWith3 :: (Int -> a -> b -> c -> d)
547 -> Vector a -> Vector b -> Vector c -> Vector d
548 {-# INLINE izipWith3 #-}
549 izipWith3 = G.izipWith3
550
551 -- |/O(n)/, Zip four vectors and their indices with the given function.
552 izipWith4 :: (Int -> a -> b -> c -> d -> e)
553 -> Vector a -> Vector b -> Vector c -> Vector d -> Vector e
554 {-# INLINE izipWith4 #-}
555 izipWith4 = G.izipWith4
556
557 -- |/O(n)/, Zip five vectors and their indices with the given function.
558 izipWith5 :: (Int -> a -> b -> c -> d -> e -> f)
559 -> Vector a -> Vector b -> Vector c -> Vector d -> Vector e
560 -> Vector f
561 {-# INLINE izipWith5 #-}
562 izipWith5 = G.izipWith5
563
564 -- |/O(n)/, Zip six vectors and their indices with the given function.
565 izipWith6 :: (Int -> a -> b -> c -> d -> e -> f -> g)
566 -> Vector a -> Vector b -> Vector c -> Vector d -> Vector e
567 -> Vector f -> Vector g
568 {-# INLINE izipWith6 #-}
569 izipWith6 = G.izipWith6
570
571 -- | Elementwise pairing of array elements.
572 zip :: Vector a -> Vector b -> Vector (a, b)
573 {-# INLINE zip #-}
574 zip = G.zip
575
576 -- | zip together three vectors into a vector of triples
577 zip3 :: Vector a -> Vector b -> Vector c -> Vector (a, b, c)
578 {-# INLINE zip3 #-}
579 zip3 = G.zip3
580
581 zip4 :: Vector a -> Vector b -> Vector c -> Vector d
582 -> Vector (a, b, c, d)
583 {-# INLINE zip4 #-}
584 zip4 = G.zip4
585
586 zip5 :: Vector a -> Vector b -> Vector c -> Vector d -> Vector e
587 -> Vector (a, b, c, d, e)
588 {-# INLINE zip5 #-}
589 zip5 = G.zip5
590
591 zip6 :: Vector a -> Vector b -> Vector c -> Vector d -> Vector e -> Vector f
592 -> Vector (a, b, c, d, e, f)
593 {-# INLINE zip6 #-}
594 zip6 = G.zip6
595
596 -- | Elementwise unpairing of array elements.
597 unzip :: Vector (a, b) -> (Vector a, Vector b)
598 {-# INLINE unzip #-}
599 unzip = G.unzip
600
601 unzip3 :: Vector (a, b, c) -> (Vector a, Vector b, Vector c)
602 {-# INLINE unzip3 #-}
603 unzip3 = G.unzip3
604
605 unzip4 :: Vector (a, b, c, d) -> (Vector a, Vector b, Vector c, Vector d)
606 {-# INLINE unzip4 #-}
607 unzip4 = G.unzip4
608
609 unzip5 :: Vector (a, b, c, d, e)
610 -> (Vector a, Vector b, Vector c, Vector d, Vector e)
611 {-# INLINE unzip5 #-}
612 unzip5 = G.unzip5
613
614 unzip6 :: Vector (a, b, c, d, e, f)
615 -> (Vector a, Vector b, Vector c, Vector d, Vector e, Vector f)
616 {-# INLINE unzip6 #-}
617 unzip6 = G.unzip6
618
619 -- Filtering
620 -- ---------
621
622 -- |/O(n)/, Remove elements from the vector which do not satisfy the predicate
623 filter :: (a -> Bool) -> Vector a -> Vector a
624 {-# INLINE filter #-}
625 filter = G.filter
626
627 -- |/O(n)/, Drop elements that do not satisfy the predicate (applied to values and
628 -- their indices)
629 ifilter :: (Int -> a -> Bool) -> Vector a -> Vector a
630 {-# INLINE ifilter #-}
631 ifilter = G.ifilter
632
633 -- |/O(n)/, Yield the longest prefix of elements satisfying the predicate.
634 takeWhile :: (a -> Bool) -> Vector a -> Vector a
635 {-# INLINE takeWhile #-}
636 takeWhile = G.takeWhile
637
638 -- |/O(n)/, Drop the longest prefix of elements that satisfy the predicate.
639 dropWhile :: (a -> Bool) -> Vector a -> Vector a
640 {-# INLINE dropWhile #-}
641 dropWhile = G.dropWhile
642
643 -- | Split the vector in two parts, the first one containing those elements
644 -- that satisfy the predicate and the second one those that don't. The
645 -- relative order of the elements is preserved at the cost of a (sometimes)
646 -- reduced performance compared to 'unstablePartition'.
647 partition :: (a -> Bool) -> Vector a -> (Vector a, Vector a)
648 {-# INLINE partition #-}
649 partition = G.partition
650
651 -- |/O(n)/, Split the vector in two parts, the first one containing those elements
652 -- that satisfy the predicate and the second one those that don't. The order
653 -- of the elements is not preserved.
654 unstablePartition :: (a -> Bool) -> Vector a -> (Vector a, Vector a)
655 {-# INLINE unstablePartition #-}
656 unstablePartition = G.unstablePartition
657
658 -- |/O(n)/, Split the vector into the longest prefix of elements that satisfy the
659 -- predicate and the rest.
660 span :: (a -> Bool) -> Vector a -> (Vector a, Vector a)
661 {-# INLINE span #-}
662 span = G.span
663
664 -- | Split the vector into the longest prefix of elements that do not satisfy
665 -- the predicate and the rest.
666 break :: (a -> Bool) -> Vector a -> (Vector a, Vector a)
667 {-# INLINE break #-}
668 break = G.break
669
670 -- Searching
671 -- ---------
672
673 infix 4 `elem`
674 -- | Check whether the vector contains an element
675 elem :: Eq a => a -> Vector a -> Bool
676 {-# INLINE elem #-}
677 elem = G.elem
678
679 infix 4 `notElem`
680 -- | Inverse of `elem`
681 notElem :: Eq a => a -> Vector a -> Bool
682 {-# INLINE notElem #-}
683 notElem = G.notElem
684
685 -- | Yield 'Just' the first element matching the predicate or 'Nothing' if no
686 -- such element exists.
687 find :: (a -> Bool) -> Vector a -> Maybe a
688 {-# INLINE find #-}
689 find = G.find
690
691 -- | Yield 'Just' the index of the first element matching the predicate or
692 -- 'Nothing' if no such element exists.
693 findIndex :: (a -> Bool) -> Vector a -> Maybe Int
694 {-# INLINE findIndex #-}
695 findIndex = G.findIndex
696
697 -- | Yield the indices of elements satisfying the predicate
698 findIndices :: (a -> Bool) -> Vector a -> Vector Int
699 {-# INLINE findIndices #-}
700 findIndices = G.findIndices
701
702 -- | Yield 'Just' the index of the first occurence of the given element or
703 -- 'Nothing' if the vector does not contain the element
704 elemIndex :: Eq a => a -> Vector a -> Maybe Int
705 {-# INLINE elemIndex #-}
706 elemIndex = G.elemIndex
707
708 -- | Yield the indices of all occurences of the given element
709 elemIndices :: Eq a => a -> Vector a -> Vector Int
710 {-# INLINE elemIndices #-}
711 elemIndices = G.elemIndices
712
713 -- Folding
714 -- -------
715
716 -- | Left fold
717 foldl :: (a -> b -> a) -> a -> Vector b -> a
718 {-# INLINE foldl #-}
719 foldl = G.foldl
720
721 -- | Left fold on non-empty vectors
722 foldl1 :: (a -> a -> a) -> Vector a -> a
723 {-# INLINE foldl1 #-}
724 foldl1 = G.foldl1
725
726 -- | Left fold with strict accumulator
727 foldl' :: (a -> b -> a) -> a -> Vector b -> a
728 {-# INLINE foldl' #-}
729 foldl' = G.foldl'
730
731 -- | Left fold on non-empty vectors with strict accumulator
732 foldl1' :: (a -> a -> a) -> Vector a -> a
733 {-# INLINE foldl1' #-}
734 foldl1' = G.foldl1'
735
736 -- | Right fold
737 foldr :: (a -> b -> b) -> b -> Vector a -> b
738 {-# INLINE foldr #-}
739 foldr = G.foldr
740
741 -- | Right fold on non-empty vectors
742 foldr1 :: (a -> a -> a) -> Vector a -> a
743 {-# INLINE foldr1 #-}
744 foldr1 = G.foldr1
745
746 -- | Right fold with a strict accumulator
747 foldr' :: (a -> b -> b) -> b -> Vector a -> b
748 {-# INLINE foldr' #-}
749 foldr' = G.foldr'
750
751 -- | Right fold on non-empty vectors with strict accumulator
752 foldr1' :: (a -> a -> a) -> Vector a -> a
753 {-# INLINE foldr1' #-}
754 foldr1' = G.foldr1'
755
756 -- | Left fold (function applied to each element and its index)
757 ifoldl :: (a -> Int -> b -> a) -> a -> Vector b -> a
758 {-# INLINE ifoldl #-}
759 ifoldl = G.ifoldl
760
761 -- | Left fold with strict accumulator (function applied to each element and
762 -- its index)
763 ifoldl' :: (a -> Int -> b -> a) -> a -> Vector b -> a
764 {-# INLINE ifoldl' #-}
765 ifoldl' = G.ifoldl'
766
767 -- | Right fold (function applied to each element and its index)
768 ifoldr :: (Int -> a -> b -> b) -> b -> Vector a -> b
769 {-# INLINE ifoldr #-}
770 ifoldr = G.ifoldr
771
772 -- | Right fold with strict accumulator (function applied to each element and
773 -- its index)
774 ifoldr' :: (Int -> a -> b -> b) -> b -> Vector a -> b
775 {-# INLINE ifoldr' #-}
776 ifoldr' = G.ifoldr'
777
778 -- Specialised folds
779 -- -----------------
780
781 -- |/O(n)/. @'all' p u@ determines whether all elements in array @u@ satisfy
782 -- predicate @p@.
783 all :: (a -> Bool) -> Vector a -> Bool
784 {-# INLINE all #-}
785 all = G.all
786
787 -- |/O(n)/. @'any' p u@ determines whether any element in array @u@ satisfies
788 -- predicate @p@.
789 any :: (a -> Bool) -> Vector a -> Bool
790 {-# INLINE any #-}
791 any = G.any
792
793 -- |/O(n)/. 'and' yields the conjunction of a boolean array.
794 and :: Vector Bool -> Bool
795 {-# INLINE and #-}
796 and = G.and
797
798 -- |/O(n)/. 'or' yields the disjunction of a boolean array.
799 or :: Vector Bool -> Bool
800 {-# INLINE or #-}
801 or = G.or
802
803 -- |/O(n)/. 'sum' computes the sum (with @(+)@) of an array of elements.
804 sum :: Num a => Vector a -> a
805 {-# INLINE sum #-}
806 sum = G.sum
807
808 -- |/O(n)/. 'sum' computes the product (with @(*)@) of an array of elements.
809 product :: Num a => Vector a -> a
810 {-# INLINE product #-}
811 product = G.product
812
813 -- |/O(n)/. 'maximum' finds the maximum element in an array of orderable elements.
814 maximum :: Ord a => Vector a -> a
815 {-# INLINE maximum #-}
816 maximum = G.maximum
817
818 -- |/O(n)/. 'maximumBy' finds the maximum element in an array under the given ordering.
819 maximumBy :: (a -> a -> Ordering) -> Vector a -> a
820 {-# INLINE maximumBy #-}
821 maximumBy = G.maximumBy
822
823 -- |/O(n)/. 'minimum' finds the minimum element in an array of orderable elements.
824 minimum :: Ord a => Vector a -> a
825 {-# INLINE minimum #-}
826 minimum = G.minimum
827
828 -- |/O(n)/. 'minimumBy' finds the minimum element in an array under the given ordering.
829 minimumBy :: (a -> a -> Ordering) -> Vector a -> a
830 {-# INLINE minimumBy #-}
831 minimumBy = G.minimumBy
832
833 -- | TODO maxIndex
834 maxIndex :: Ord a => Vector a -> Int
835 {-# INLINE maxIndex #-}
836 maxIndex = G.maxIndex
837
838 -- | TODO maxIndexBy
839 maxIndexBy :: (a -> a -> Ordering) -> Vector a -> Int
840 {-# INLINE maxIndexBy #-}
841 maxIndexBy = G.maxIndexBy
842
843 -- | TODO minIndex
844 minIndex :: Ord a => Vector a -> Int
845 {-# INLINE minIndex #-}
846 minIndex = G.minIndex
847
848 -- | TODO minIndexBy
849 minIndexBy :: (a -> a -> Ordering) -> Vector a -> Int
850 {-# INLINE minIndexBy #-}
851 minIndexBy = G.minIndexBy
852
853 -- Unfolding
854 -- ---------
855
856 -- | The 'unfoldr' function is a \`dual\' to 'foldr': while 'foldr'
857 -- reduces a vector to a summary value, 'unfoldr' builds a list from
858 -- a seed value. The function takes the element and returns 'Nothing'
859 -- if it is done generating the vector or returns 'Just' @(a,b)@, in which
860 -- case, @a@ is a prepended to the vector and @b@ is used as the next
861 -- element in a recursive call.
862 --
863 -- A simple use of unfoldr:
864 --
865 -- > unfoldr (\b -> if b == 0 then Nothing else Just (b, b-1)) 10
866 -- > [10,9,8,7,6,5,4,3,2,1]
867 --
868 unfoldr :: (b -> Maybe (a, b)) -> b -> Vector a
869 {-# INLINE unfoldr #-}
870 unfoldr = G.unfoldr
871
872 -- | Unfold at most @n@ elements
873 unfoldrN :: Int -> (b -> Maybe (a, b)) -> b -> Vector a
874 {-# INLINE unfoldrN #-}
875 unfoldrN = G.unfoldrN
876
877 -- Scans
878 -- -----
879
880 -- | Prefix scan
881 prescanl :: (a -> b -> a) -> a -> Vector b -> Vector a
882 {-# INLINE prescanl #-}
883 prescanl = G.prescanl
884
885 -- | Prefix scan with strict accumulator
886 prescanl' :: (a -> b -> a) -> a -> Vector b -> Vector a
887 {-# INLINE prescanl' #-}
888 prescanl' = G.prescanl'
889
890 -- | Suffix scan
891 postscanl :: (a -> b -> a) -> a -> Vector b -> Vector a
892 {-# INLINE postscanl #-}
893 postscanl = G.postscanl
894
895 -- | Suffix scan with strict accumulator
896 postscanl' :: (a -> b -> a) -> a -> Vector b -> Vector a
897 {-# INLINE postscanl' #-}
898 postscanl' = G.postscanl'
899
900 -- | Haskell-style scan function.
901 scanl :: (a -> b -> a) -> a -> Vector b -> Vector a
902 {-# INLINE scanl #-}
903 scanl = G.scanl
904
905 -- | Haskell-style scan with strict accumulator
906 scanl' :: (a -> b -> a) -> a -> Vector b -> Vector a
907 {-# INLINE scanl' #-}
908 scanl' = G.scanl'
909
910 -- | Scan over a non-empty 'Vector'
911 scanl1 :: (a -> a -> a) -> Vector a -> Vector a
912 {-# INLINE scanl1 #-}
913 scanl1 = G.scanl1
914
915 -- | Scan over a non-empty 'Vector' with a strict accumulator
916 scanl1' :: (a -> a -> a) -> Vector a -> Vector a
917 {-# INLINE scanl1' #-}
918 scanl1' = G.scanl1'
919
920 -- | Prefix right-to-left scan
921 prescanr :: (a -> b -> b) -> b -> Vector a -> Vector b
922 {-# INLINE prescanr #-}
923 prescanr = G.prescanr
924
925 -- | Prefix right-to-left scan with strict accumulator
926 prescanr' :: (a -> b -> b) -> b -> Vector a -> Vector b
927 {-# INLINE prescanr' #-}
928 prescanr' = G.prescanr'
929
930 -- | Suffix right-to-left scan
931 postscanr :: (a -> b -> b) -> b -> Vector a -> Vector b
932 {-# INLINE postscanr #-}
933 postscanr = G.postscanr
934
935 -- | Suffix right-to-left scan with strict accumulator
936 postscanr' :: (a -> b -> b) -> b -> Vector a -> Vector b
937 {-# INLINE postscanr' #-}
938 postscanr' = G.postscanr'
939
940 -- | Haskell-style right-to-left scan
941 scanr :: (a -> b -> b) -> b -> Vector a -> Vector b
942 {-# INLINE scanr #-}
943 scanr = G.scanr
944
945 -- | Haskell-style right-to-left scan with strict accumulator
946 scanr' :: (a -> b -> b) -> b -> Vector a -> Vector b
947 {-# INLINE scanr' #-}
948 scanr' = G.scanr'
949
950 -- | Right-to-left scan over a non-empty vector
951 scanr1 :: (a -> a -> a) -> Vector a -> Vector a
952 {-# INLINE scanr1 #-}
953 scanr1 = G.scanr1
954
955 -- | Right-to-left scan over a non-empty vector with a strict accumulator
956 scanr1' :: (a -> a -> a) -> Vector a -> Vector a
957 {-# INLINE scanr1' #-}
958 scanr1' = G.scanr1'
959
960 -- Enumeration
961 -- -----------
962
963 -- | Yield a vector of the given length containing the values @x@, @x+1@ etc.
964 -- This operation is usually more efficient than 'enumFromTo'.
965 enumFromN :: Num a => a -> Int -> Vector a
966 {-# INLINE enumFromN #-}
967 enumFromN = G.enumFromN
968
969 -- | Yield a vector of the given length containing the values @x@, @x+y@,
970 -- @x+y+y@ etc. This operations is usually more efficient than
971 -- 'enumFromThenTo'.
972 enumFromStepN :: Num a => a -> a -> Int -> Vector a
973 {-# INLINE enumFromStepN #-}
974 enumFromStepN = G.enumFromStepN
975
976 -- | Enumerate values from @x@ to @y@.
977 --
978 -- /WARNING:/ This operation can be very inefficient. If at all possible, use
979 -- 'enumFromN' instead.
980 enumFromTo :: Enum a => a -> a -> Vector a
981 {-# INLINE enumFromTo #-}
982 enumFromTo = G.enumFromTo
983
984 -- | Enumerate values from @x@ to @y@ with a specific step @z@.
985 --
986 -- /WARNING:/ This operation can be very inefficient. If at all possible, use
987 -- 'enumFromStepN' instead.
988 enumFromThenTo :: Enum a => a -> a -> a -> Vector a
989 {-# INLINE enumFromThenTo #-}
990 enumFromThenTo = G.enumFromThenTo
991
992 -- Conversion to/from lists
993 -- ------------------------
994
995 -- | Convert a vector to a list
996 toList :: Vector a -> [a]
997 {-# INLINE toList #-}
998 toList = G.toList
999
1000 -- | Convert a list to a vector
1001 fromList :: [a] -> Vector a
1002 {-# INLINE fromList #-}
1003 fromList = G.fromList
1004
1005 -- | Convert the first @n@ elements of a list to a vector
1006 --
1007 -- > fromListN n xs = fromList (take n xs)
1008 fromListN :: Int -> [a] -> Vector a
1009 {-# INLINE fromListN #-}
1010 fromListN = G.fromListN
1011
1012 -- Monadic operations
1013 -- ------------------
1014
1015 -- | Perform the monadic action the given number of times and store the
1016 -- results in a vector.
1017 replicateM :: Monad m => Int -> m a -> m (Vector a)
1018 {-# INLINE replicateM #-}
1019 replicateM = G.replicateM
1020
1021 -- | Apply the monadic action to all elements of the vector, yielding a vector
1022 -- of results
1023 mapM :: Monad m => (a -> m b) -> Vector a -> m (Vector b)
1024 {-# INLINE mapM #-}
1025 mapM = G.mapM
1026
1027 -- | Apply the monadic action to all elements of a vector and ignore the
1028 -- results
1029 mapM_ :: Monad m => (a -> m b) -> Vector a -> m ()
1030 {-# INLINE mapM_ #-}
1031 mapM_ = G.mapM_
1032
1033 -- | Apply the monadic action to all elements of the vector, yielding a vector
1034 -- of results
1035 forM :: Monad m => Vector a -> (a -> m b) -> m (Vector b)
1036 {-# INLINE forM #-}
1037 forM = G.forM
1038
1039 -- | Apply the monadic action to all elements of a vector and ignore the
1040 -- results
1041 forM_ :: Monad m => Vector a -> (a -> m b) -> m ()
1042 {-# INLINE forM_ #-}
1043 forM_ = G.forM_
1044
1045 -- | Zip the two vectors with the monadic action and yield a vector of results
1046 zipWithM :: Monad m
1047 => (a -> b -> m c) -> Vector a -> Vector b -> m (Vector c)
1048 {-# INLINE zipWithM #-}
1049 zipWithM = G.zipWithM
1050
1051 -- | Zip the two vectors with the monadic action and ignore the results
1052 zipWithM_ :: Monad m
1053 => (a -> b -> m c) -> Vector a -> Vector b -> m ()
1054 {-# INLINE zipWithM_ #-}
1055 zipWithM_ = G.zipWithM_
1056
1057 -- | Drop elements that do not satisfy the monadic predicate
1058 filterM :: Monad m => (a -> m Bool) -> Vector a -> m (Vector a)
1059 {-# INLINE filterM #-}
1060 filterM = G.filterM
1061
1062 -- | Monadic fold
1063 foldM :: Monad m => (a -> b -> m a) -> a -> Vector b -> m a
1064 {-# INLINE foldM #-}
1065 foldM = G.foldM
1066
1067 -- | Monadic fold over non-empty vectors
1068 fold1M :: Monad m => (a -> a -> m a) -> Vector a -> m a
1069 {-# INLINE fold1M #-}
1070 fold1M = G.fold1M
1071
1072 -- | Monadic fold with strict accumulator
1073 foldM' :: Monad m => (a -> b -> m a) -> a -> Vector b -> m a
1074 {-# INLINE foldM' #-}
1075 foldM' = G.foldM'
1076
1077 -- | Monad fold over non-empty vectors with strict accumulator
1078 fold1M' :: Monad m => (a -> a -> m a) -> Vector a -> m a
1079 {-# INLINE fold1M' #-}
1080 fold1M' = G.fold1M'
1081
1082 -- Destructive operations
1083 -- ----------------------
1084
1085 -- | Destructively initialise a vector.
1086 create :: (forall s. ST s (MVector s a)) -> Vector a
1087 {-# INLINE create #-}
1088 create = G.create
1089
1090 -- | Apply a destructive operation to a vector. The operation is applied to a
1091 -- copy of the vector unless it can be safely performed in place.
1092 modify :: (forall s. MVector s a -> ST s ()) -> Vector a -> Vector a
1093 {-# INLINE modify #-}
1094 modify = G.modify
1095
1096 -- | Copy an immutable vector into a mutable one. The two vectors must have
1097 -- the same length. This is not checked.
1098 unsafeCopy :: PrimMonad m => MVector (PrimState m) a -> Vector a -> m ()
1099 {-# INLINE unsafeCopy #-}
1100 unsafeCopy = G.unsafeCopy
1101
1102 -- | Copy an immutable vector into a mutable one. The two vectors must have the
1103 -- same length.
1104 copy :: PrimMonad m => MVector (PrimState m) a -> Vector a -> m ()
1105 {-# INLINE copy #-}
1106 copy = G.copy
1107