Add generateM
[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 -- * Boxed vectors
27 Vector, MVector,
28
29 -- * Accessors
30
31 -- ** Length information
32 length, null,
33
34 -- ** Indexing
35 (!), (!?), head, last,
36 unsafeIndex, unsafeHead, unsafeLast,
37
38 -- ** Monadic indexing
39 indexM, headM, lastM,
40 unsafeIndexM, unsafeHeadM, unsafeLastM,
41
42 -- ** Extracting subvectors (slicing)
43 slice, init, tail, take, drop, splitAt,
44 unsafeSlice, unsafeInit, unsafeTail, unsafeTake, unsafeDrop,
45
46 -- * Construction
47
48 -- ** Initialisation
49 empty, singleton, replicate, generate,
50
51 -- ** Monadic initialisation
52 replicateM, generateM, create,
53
54 -- ** Unfolding
55 unfoldr, unfoldrN,
56
57 -- ** Enumeration
58 enumFromN, enumFromStepN, enumFromTo, enumFromThenTo,
59
60 -- ** Concatenation
61 cons, snoc, (++), concat,
62
63 -- ** Restricting memory usage
64 force,
65
66 -- * Modifying vectors
67
68 -- ** Bulk updates
69 (//), update, update_,
70 unsafeUpd, unsafeUpdate, unsafeUpdate_,
71
72 -- ** Accumulations
73 accum, accumulate, accumulate_,
74 unsafeAccum, unsafeAccumulate, unsafeAccumulate_,
75
76 -- ** Permutations
77 reverse, backpermute, unsafeBackpermute,
78
79 -- ** Safe destructive updates
80 modify,
81
82 -- * Elementwise operations
83
84 -- ** Indexing
85 indexed,
86
87 -- ** Mapping
88 map, imap, concatMap,
89
90 -- ** Monadic mapping
91 mapM, mapM_, forM, forM_,
92
93 -- ** Zipping
94 zipWith, zipWith3, zipWith4, zipWith5, zipWith6,
95 izipWith, izipWith3, izipWith4, izipWith5, izipWith6,
96 zip, zip3, zip4, zip5, zip6,
97
98 -- ** Monadic zipping
99 zipWithM, zipWithM_,
100
101 -- ** Unzipping
102 unzip, unzip3, unzip4, unzip5, unzip6,
103
104 -- * Working with predicates
105
106 -- ** Filtering
107 filter, ifilter, filterM,
108 takeWhile, dropWhile,
109
110 -- ** Partitioning
111 partition, unstablePartition, span, break,
112
113 -- ** Searching
114 elem, notElem, find, findIndex, findIndices, elemIndex, elemIndices,
115
116 -- * Folding
117 foldl, foldl1, foldl', foldl1', foldr, foldr1, foldr', foldr1',
118 ifoldl, ifoldl', ifoldr, ifoldr',
119
120 -- ** Specialised folds
121 all, any, and, or,
122 sum, product,
123 maximum, maximumBy, minimum, minimumBy,
124 minIndex, minIndexBy, maxIndex, maxIndexBy,
125
126 -- ** Monadic folds
127 foldM, foldM', fold1M, fold1M',
128 foldM_, foldM'_, fold1M_, fold1M'_,
129
130 -- ** Monadic sequencing
131 sequence, sequence_,
132
133 -- * Prefix sums (scans)
134 prescanl, prescanl',
135 postscanl, postscanl',
136 scanl, scanl', scanl1, scanl1',
137 prescanr, prescanr',
138 postscanr, postscanr',
139 scanr, scanr', scanr1, scanr1',
140
141 -- * Conversions
142
143 -- ** Lists
144 toList, fromList, fromListN,
145
146 -- ** Other vector types
147 G.convert,
148
149 -- ** Mutable vectors
150 freeze, thaw, copy, unsafeFreeze, unsafeThaw, unsafeCopy
151 ) where
152
153 import qualified Data.Vector.Generic as G
154 import Data.Vector.Mutable ( MVector(..) )
155 import Data.Primitive.Array
156 import qualified Data.Vector.Fusion.Stream as Stream
157
158 import Control.Monad ( liftM )
159 import Control.Monad.ST ( ST )
160 import Control.Monad.Primitive
161
162 import Prelude hiding ( length, null,
163 replicate, (++), concat,
164 head, last,
165 init, tail, take, drop, splitAt, reverse,
166 map, concatMap,
167 zipWith, zipWith3, zip, zip3, unzip, unzip3,
168 filter, takeWhile, dropWhile, span, break,
169 elem, notElem,
170 foldl, foldl1, foldr, foldr1,
171 all, any, and, or, sum, product, minimum, maximum,
172 scanl, scanl1, scanr, scanr1,
173 enumFromTo, enumFromThenTo,
174 mapM, mapM_, sequence, sequence_ )
175
176 import qualified Prelude
177
178 import Data.Typeable ( Typeable )
179 import Data.Data ( Data(..) )
180
181 import Data.Monoid ( Monoid(..) )
182
183 -- | Boxed vectors, supporting efficient slicing.
184 data Vector a = Vector {-# UNPACK #-} !Int
185 {-# UNPACK #-} !Int
186 {-# UNPACK #-} !(Array a)
187 deriving ( Typeable )
188
189 instance Show a => Show (Vector a) where
190 show = (Prelude.++ " :: Data.Vector.Vector") . ("fromList " Prelude.++) . show . toList
191
192 instance Data a => Data (Vector a) where
193 gfoldl = G.gfoldl
194 toConstr _ = error "toConstr"
195 gunfold _ _ = error "gunfold"
196 dataTypeOf _ = G.mkType "Data.Vector.Vector"
197 dataCast1 = G.dataCast
198
199 type instance G.Mutable Vector = MVector
200
201 instance G.Vector Vector a where
202 {-# INLINE basicUnsafeFreeze #-}
203 basicUnsafeFreeze (MVector i n marr)
204 = Vector i n `liftM` unsafeFreezeArray marr
205
206 {-# INLINE basicUnsafeThaw #-}
207 basicUnsafeThaw (Vector i n arr)
208 = MVector i n `liftM` unsafeThawArray arr
209
210 {-# INLINE basicLength #-}
211 basicLength (Vector _ n _) = n
212
213 {-# INLINE basicUnsafeSlice #-}
214 basicUnsafeSlice j n (Vector i _ arr) = Vector (i+j) n arr
215
216 {-# INLINE basicUnsafeIndexM #-}
217 basicUnsafeIndexM (Vector i _ arr) j = indexArrayM arr (i+j)
218
219 -- See http://trac.haskell.org/vector/ticket/12
220 instance Eq a => Eq (Vector a) where
221 {-# INLINE (==) #-}
222 xs == ys = Stream.eq (G.stream xs) (G.stream ys)
223
224 {-# INLINE (/=) #-}
225 xs /= ys = not (Stream.eq (G.stream xs) (G.stream ys))
226
227 -- See http://trac.haskell.org/vector/ticket/12
228 instance Ord a => Ord (Vector a) where
229 {-# INLINE compare #-}
230 compare xs ys = Stream.cmp (G.stream xs) (G.stream ys)
231
232 {-# INLINE (<) #-}
233 xs < ys = Stream.cmp (G.stream xs) (G.stream ys) == LT
234
235 {-# INLINE (<=) #-}
236 xs <= ys = Stream.cmp (G.stream xs) (G.stream ys) /= GT
237
238 {-# INLINE (>) #-}
239 xs > ys = Stream.cmp (G.stream xs) (G.stream ys) == GT
240
241 {-# INLINE (>=) #-}
242 xs >= ys = Stream.cmp (G.stream xs) (G.stream ys) /= LT
243
244 instance Monoid (Vector a) where
245 {-# INLINE mempty #-}
246 mempty = empty
247
248 {-# INLINE mappend #-}
249 mappend = (++)
250
251 {-# INLINE mconcat #-}
252 mconcat = concat
253
254 -- Length information
255 -- ------------------
256
257 -- | /O(1)/ Yield the length of the vector.
258 length :: Vector a -> Int
259 {-# INLINE length #-}
260 length = G.length
261
262 -- | /O(1)/ Test whether a vector if empty
263 null :: Vector a -> Bool
264 {-# INLINE null #-}
265 null = G.null
266
267 -- Indexing
268 -- --------
269
270 -- | O(1) Indexing
271 (!) :: Vector a -> Int -> a
272 {-# INLINE (!) #-}
273 (!) = (G.!)
274
275 -- | O(1) Safe indexing
276 (!?) :: Vector a -> Int -> Maybe a
277 {-# INLINE (!?) #-}
278 (!?) = (G.!?)
279
280 -- | /O(1)/ First element
281 head :: Vector a -> a
282 {-# INLINE head #-}
283 head = G.head
284
285 -- | /O(1)/ Last element
286 last :: Vector a -> a
287 {-# INLINE last #-}
288 last = G.last
289
290 -- | /O(1)/ Unsafe indexing without bounds checking
291 unsafeIndex :: Vector a -> Int -> a
292 {-# INLINE unsafeIndex #-}
293 unsafeIndex = G.unsafeIndex
294
295 -- | /O(1)/ First element without checking if the vector is empty
296 unsafeHead :: Vector a -> a
297 {-# INLINE unsafeHead #-}
298 unsafeHead = G.unsafeHead
299
300 -- | /O(1)/ Last element without checking if the vector is empty
301 unsafeLast :: Vector a -> a
302 {-# INLINE unsafeLast #-}
303 unsafeLast = G.unsafeLast
304
305 -- Monadic indexing
306 -- ----------------
307
308 -- | /O(1)/ Indexing in a monad.
309 --
310 -- The monad allows operations to be strict in the vector when necessary.
311 -- Suppose vector copying is implemented like this:
312 --
313 -- > copy mv v = ... write mv i (v ! i) ...
314 --
315 -- For lazy vectors, @v ! i@ would not be evaluated which means that @mv@
316 -- would unnecessarily retain a reference to @v@ in each element written.
317 --
318 -- With 'indexM', copying can be implemented like this instead:
319 --
320 -- > copy mv v = ... do
321 -- > x <- indexM v i
322 -- > write mv i x
323 --
324 -- Here, no references to @v@ are retained because indexing (but /not/ the
325 -- elements) is evaluated eagerly.
326 --
327 indexM :: Monad m => Vector a -> Int -> m a
328 {-# INLINE indexM #-}
329 indexM = G.indexM
330
331 -- | /O(1)/ First element of a vector in a monad. See 'indexM' for an
332 -- explanation of why this is useful.
333 headM :: Monad m => Vector a -> m a
334 {-# INLINE headM #-}
335 headM = G.headM
336
337 -- | /O(1)/ Last element of a vector in a monad. See 'indexM' for an
338 -- explanation of why this is useful.
339 lastM :: Monad m => Vector a -> m a
340 {-# INLINE lastM #-}
341 lastM = G.lastM
342
343 -- | /O(1)/ Indexing in a monad without bounds checks. See 'indexM' for an
344 -- explanation of why this is useful.
345 unsafeIndexM :: Monad m => Vector a -> Int -> m a
346 {-# INLINE unsafeIndexM #-}
347 unsafeIndexM = G.unsafeIndexM
348
349 -- | /O(1)/ First element in a monad without checking for empty vectors.
350 -- See 'indexM' for an explanation of why this is useful.
351 unsafeHeadM :: Monad m => Vector a -> m a
352 {-# INLINE unsafeHeadM #-}
353 unsafeHeadM = G.unsafeHeadM
354
355 -- | /O(1)/ Last element in a monad without checking for empty vectors.
356 -- See 'indexM' for an explanation of why this is useful.
357 unsafeLastM :: Monad m => Vector a -> m a
358 {-# INLINE unsafeLastM #-}
359 unsafeLastM = G.unsafeLastM
360
361 -- Extracting subvectors (slicing)
362 -- -------------------------------
363
364 -- | /O(1)/ Yield a slice of the vector without copying it. The vector must
365 -- contain at least @i+n@ elements.
366 slice :: Int -- ^ @i@ starting index
367 -> Int -- ^ @n@ length
368 -> Vector a
369 -> Vector a
370 {-# INLINE slice #-}
371 slice = G.slice
372
373 -- | /O(1)/ Yield all but the last element without copying. The vector may not
374 -- be empty.
375 init :: Vector a -> Vector a
376 {-# INLINE init #-}
377 init = G.init
378
379 -- | /O(1)/ Yield all but the first element without copying. The vector may not
380 -- be empty.
381 tail :: Vector a -> Vector a
382 {-# INLINE tail #-}
383 tail = G.tail
384
385 -- | /O(1)/ Yield at the first @n@ elements without copying. The vector may
386 -- contain less than @n@ elements in which case it is returned unchanged.
387 take :: Int -> Vector a -> Vector a
388 {-# INLINE take #-}
389 take = G.take
390
391 -- | /O(1)/ Yield all but the first @n@ elements without copying. The vector may
392 -- contain less than @n@ elements in which case an empty vector is returned.
393 drop :: Int -> Vector a -> Vector a
394 {-# INLINE drop #-}
395 drop = G.drop
396
397 -- | /O(1)/ Yield the first @n@ elements paired with the remainder without copying.
398 --
399 -- Note that @'splitAt' n v@ is equivalent to @('take' n v, 'drop' n v)@
400 -- but slightly more efficient.
401 {-# INLINE splitAt #-}
402 splitAt :: Int -> Vector a -> (Vector a, Vector a)
403 splitAt = G.splitAt
404
405 -- | /O(1)/ Yield a slice of the vector without copying. The vector must
406 -- contain at least @i+n@ elements but this is not checked.
407 unsafeSlice :: Int -- ^ @i@ starting index
408 -> Int -- ^ @n@ length
409 -> Vector a
410 -> Vector a
411 {-# INLINE unsafeSlice #-}
412 unsafeSlice = G.unsafeSlice
413
414 -- | /O(1)/ Yield all but the last element without copying. The vector may not
415 -- be empty but this is not checked.
416 unsafeInit :: Vector a -> Vector a
417 {-# INLINE unsafeInit #-}
418 unsafeInit = G.unsafeInit
419
420 -- | /O(1)/ Yield all but the first element without copying. The vector may not
421 -- be empty but this is not checked.
422 unsafeTail :: Vector a -> Vector a
423 {-# INLINE unsafeTail #-}
424 unsafeTail = G.unsafeTail
425
426 -- | /O(1)/ Yield the first @n@ elements without copying. The vector must
427 -- contain at least @n@ elements but this is not checked.
428 unsafeTake :: Int -> Vector a -> Vector a
429 {-# INLINE unsafeTake #-}
430 unsafeTake = G.unsafeTake
431
432 -- | /O(1)/ Yield all but the first @n@ elements without copying. The vector
433 -- must contain at least @n@ elements but this is not checked.
434 unsafeDrop :: Int -> Vector a -> Vector a
435 {-# INLINE unsafeDrop #-}
436 unsafeDrop = G.unsafeDrop
437
438 -- Initialisation
439 -- --------------
440
441 -- | /O(1)/ Empty vector
442 empty :: Vector a
443 {-# INLINE empty #-}
444 empty = G.empty
445
446 -- | /O(1)/ Vector with exactly one element
447 singleton :: a -> Vector a
448 {-# INLINE singleton #-}
449 singleton = G.singleton
450
451 -- | /O(n)/ Vector of the given length with the same value in each position
452 replicate :: Int -> a -> Vector a
453 {-# INLINE replicate #-}
454 replicate = G.replicate
455
456 -- | /O(n)/ Construct a vector of the given length by applying the function to
457 -- each index
458 generate :: Int -> (Int -> a) -> Vector a
459 {-# INLINE generate #-}
460 generate = G.generate
461
462 -- Unfolding
463 -- ---------
464
465 -- | /O(n)/ Construct a vector by repeatedly applying the generator function
466 -- to a seed. The generator function yields 'Just' the next element and the
467 -- new seed or 'Nothing' if there are no more elements.
468 --
469 -- > unfoldr (\n -> if n == 0 then Nothing else Just (n,n-1)) 10
470 -- > = <10,9,8,7,6,5,4,3,2,1>
471 unfoldr :: (b -> Maybe (a, b)) -> b -> Vector a
472 {-# INLINE unfoldr #-}
473 unfoldr = G.unfoldr
474
475 -- | /O(n)/ Construct a vector with at most @n@ by repeatedly applying the
476 -- generator function to the a seed. The generator function yields 'Just' the
477 -- next element and the new seed or 'Nothing' if there are no more elements.
478 --
479 -- > unfoldrN 3 (\n -> Just (n,n-1)) 10 = <10,9,8>
480 unfoldrN :: Int -> (b -> Maybe (a, b)) -> b -> Vector a
481 {-# INLINE unfoldrN #-}
482 unfoldrN = G.unfoldrN
483
484 -- Enumeration
485 -- -----------
486
487 -- | /O(n)/ Yield a vector of the given length containing the values @x@, @x+1@
488 -- etc. This operation is usually more efficient than 'enumFromTo'.
489 --
490 -- > enumFromN 5 3 = <5,6,7>
491 enumFromN :: Num a => a -> Int -> Vector a
492 {-# INLINE enumFromN #-}
493 enumFromN = G.enumFromN
494
495 -- | /O(n)/ Yield a vector of the given length containing the values @x@, @x+y@,
496 -- @x+y+y@ etc. This operations is usually more efficient than 'enumFromThenTo'.
497 --
498 -- > enumFromStepN 1 0.1 5 = <1,1.1,1.2,1.3,1.4>
499 enumFromStepN :: Num a => a -> a -> Int -> Vector a
500 {-# INLINE enumFromStepN #-}
501 enumFromStepN = G.enumFromStepN
502
503 -- | /O(n)/ Enumerate values from @x@ to @y@.
504 --
505 -- /WARNING:/ This operation can be very inefficient. If at all possible, use
506 -- 'enumFromN' instead.
507 enumFromTo :: Enum a => a -> a -> Vector a
508 {-# INLINE enumFromTo #-}
509 enumFromTo = G.enumFromTo
510
511 -- | /O(n)/ Enumerate values from @x@ to @y@ with a specific step @z@.
512 --
513 -- /WARNING:/ This operation can be very inefficient. If at all possible, use
514 -- 'enumFromStepN' instead.
515 enumFromThenTo :: Enum a => a -> a -> a -> Vector a
516 {-# INLINE enumFromThenTo #-}
517 enumFromThenTo = G.enumFromThenTo
518
519 -- Concatenation
520 -- -------------
521
522 -- | /O(n)/ Prepend an element
523 cons :: a -> Vector a -> Vector a
524 {-# INLINE cons #-}
525 cons = G.cons
526
527 -- | /O(n)/ Append an element
528 snoc :: Vector a -> a -> Vector a
529 {-# INLINE snoc #-}
530 snoc = G.snoc
531
532 infixr 5 ++
533 -- | /O(m+n)/ Concatenate two vectors
534 (++) :: Vector a -> Vector a -> Vector a
535 {-# INLINE (++) #-}
536 (++) = (G.++)
537
538 -- | /O(n)/ Concatenate all vectors in the list
539 concat :: [Vector a] -> Vector a
540 {-# INLINE concat #-}
541 concat = G.concat
542
543 -- Monadic initialisation
544 -- ----------------------
545
546 -- | /O(n)/ Execute the monadic action the given number of times and store the
547 -- results in a vector.
548 replicateM :: Monad m => Int -> m a -> m (Vector a)
549 {-# INLINE replicateM #-}
550 replicateM = G.replicateM
551
552 -- | /O(n)/ Construct a vector of the given length by applying the monadic
553 -- action to each index
554 generateM :: Monad m => Int -> (Int -> m a) -> m (Vector a)
555 {-# INLINE generateM #-}
556 generateM = G.generateM
557
558 -- | Execute the monadic action and freeze the resulting vector.
559 --
560 -- @
561 -- create (do { v \<- new 2; write v 0 \'a\'; write v 1 \'b\' }) = \<'a','b'\>
562 -- @
563 create :: (forall s. ST s (MVector s a)) -> Vector a
564 {-# INLINE create #-}
565 -- NOTE: eta-expanded due to http://hackage.haskell.org/trac/ghc/ticket/4120
566 create p = G.create p
567
568
569
570 -- Restricting memory usage
571 -- ------------------------
572
573 -- | /O(n)/ Yield the argument but force it not to retain any extra memory,
574 -- possibly by copying it.
575 --
576 -- This is especially useful when dealing with slices. For example:
577 --
578 -- > force (slice 0 2 <huge vector>)
579 --
580 -- Here, the slice retains a reference to the huge vector. Forcing it creates
581 -- a copy of just the elements that belong to the slice and allows the huge
582 -- vector to be garbage collected.
583 force :: Vector a -> Vector a
584 {-# INLINE force #-}
585 force = G.force
586
587 -- Bulk updates
588 -- ------------
589
590 -- | /O(m+n)/ For each pair @(i,a)@ from the list, replace the vector
591 -- element at position @i@ by @a@.
592 --
593 -- > <5,9,2,7> // [(2,1),(0,3),(2,8)] = <3,9,8,7>
594 --
595 (//) :: Vector a -- ^ initial vector (of length @m@)
596 -> [(Int, a)] -- ^ list of index/value pairs (of length @n@)
597 -> Vector a
598 {-# INLINE (//) #-}
599 (//) = (G.//)
600
601 -- | /O(m+n)/ For each pair @(i,a)@ from the vector of index/value pairs,
602 -- replace the vector element at position @i@ by @a@.
603 --
604 -- > update <5,9,2,7> <(2,1),(0,3),(2,8)> = <3,9,8,7>
605 --
606 update :: Vector a -- ^ initial vector (of length @m@)
607 -> Vector (Int, a) -- ^ vector of index/value pairs (of length @n@)
608 -> Vector a
609 {-# INLINE update #-}
610 update = G.update
611
612 -- | /O(m+min(n1,n2))/ For each index @i@ from the index vector and the
613 -- corresponding value @a@ from the value vector, replace the element of the
614 -- initial vector at position @i@ by @a@.
615 --
616 -- > update_ <5,9,2,7> <2,0,2> <1,3,8> = <3,9,8,7>
617 --
618 -- The function 'update' provides the same functionality and is usually more
619 -- convenient.
620 --
621 -- @
622 -- update_ xs is ys = 'update' xs ('zip' is ys)
623 -- @
624 update_ :: Vector a -- ^ initial vector (of length @m@)
625 -> Vector Int -- ^ index vector (of length @n1@)
626 -> Vector a -- ^ value vector (of length @n2@)
627 -> Vector a
628 {-# INLINE update_ #-}
629 update_ = G.update_
630
631 -- | Same as ('//') but without bounds checking.
632 unsafeUpd :: Vector a -> [(Int, a)] -> Vector a
633 {-# INLINE unsafeUpd #-}
634 unsafeUpd = G.unsafeUpd
635
636 -- | Same as 'update' but without bounds checking.
637 unsafeUpdate :: Vector a -> Vector (Int, a) -> Vector a
638 {-# INLINE unsafeUpdate #-}
639 unsafeUpdate = G.unsafeUpdate
640
641 -- | Same as 'update_' but without bounds checking.
642 unsafeUpdate_ :: Vector a -> Vector Int -> Vector a -> Vector a
643 {-# INLINE unsafeUpdate_ #-}
644 unsafeUpdate_ = G.unsafeUpdate_
645
646 -- Accumulations
647 -- -------------
648
649 -- | /O(m+n)/ For each pair @(i,b)@ from the list, replace the vector element
650 -- @a@ at position @i@ by @f a b@.
651 --
652 -- > accum (+) <5,9,2> [(2,4),(1,6),(0,3),(1,7)] = <5+3, 9+6+7, 2+4>
653 accum :: (a -> b -> a) -- ^ accumulating function @f@
654 -> Vector a -- ^ initial vector (of length @m@)
655 -> [(Int,b)] -- ^ list of index/value pairs (of length @n@)
656 -> Vector a
657 {-# INLINE accum #-}
658 accum = G.accum
659
660 -- | /O(m+n)/ For each pair @(i,b)@ from the vector of pairs, replace the vector
661 -- element @a@ at position @i@ by @f a b@.
662 --
663 -- > accumulate (+) <5,9,2> <(2,4),(1,6),(0,3),(1,7)> = <5+3, 9+6+7, 2+4>
664 accumulate :: (a -> b -> a) -- ^ accumulating function @f@
665 -> Vector a -- ^ initial vector (of length @m@)
666 -> Vector (Int,b) -- ^ vector of index/value pairs (of length @n@)
667 -> Vector a
668 {-# INLINE accumulate #-}
669 accumulate = G.accumulate
670
671 -- | /O(m+min(n1,n2))/ For each index @i@ from the index vector and the
672 -- corresponding value @b@ from the the value vector,
673 -- replace the element of the initial vector at
674 -- position @i@ by @f a b@.
675 --
676 -- > accumulate_ (+) <5,9,2> <2,1,0,1> <4,6,3,7> = <5+3, 9+6+7, 2+4>
677 --
678 -- The function 'accumulate' provides the same functionality and is usually more
679 -- convenient.
680 --
681 -- @
682 -- accumulate_ f as is bs = 'accumulate' f as ('zip' is bs)
683 -- @
684 accumulate_ :: (a -> b -> a) -- ^ accumulating function @f@
685 -> Vector a -- ^ initial vector (of length @m@)
686 -> Vector Int -- ^ index vector (of length @n1@)
687 -> Vector b -- ^ value vector (of length @n2@)
688 -> Vector a
689 {-# INLINE accumulate_ #-}
690 accumulate_ = G.accumulate_
691
692 -- | Same as 'accum' but without bounds checking.
693 unsafeAccum :: (a -> b -> a) -> Vector a -> [(Int,b)] -> Vector a
694 {-# INLINE unsafeAccum #-}
695 unsafeAccum = G.unsafeAccum
696
697 -- | Same as 'accumulate' but without bounds checking.
698 unsafeAccumulate :: (a -> b -> a) -> Vector a -> Vector (Int,b) -> Vector a
699 {-# INLINE unsafeAccumulate #-}
700 unsafeAccumulate = G.unsafeAccumulate
701
702 -- | Same as 'accumulate_' but without bounds checking.
703 unsafeAccumulate_
704 :: (a -> b -> a) -> Vector a -> Vector Int -> Vector b -> Vector a
705 {-# INLINE unsafeAccumulate_ #-}
706 unsafeAccumulate_ = G.unsafeAccumulate_
707
708 -- Permutations
709 -- ------------
710
711 -- | /O(n)/ Reverse a vector
712 reverse :: Vector a -> Vector a
713 {-# INLINE reverse #-}
714 reverse = G.reverse
715
716 -- | /O(n)/ Yield the vector obtained by replacing each element @i@ of the
717 -- index vector by @xs'!'i@. This is equivalent to @'map' (xs'!') is@ but is
718 -- often much more efficient.
719 --
720 -- > backpermute <a,b,c,d> <0,3,2,3,1,0> = <a,d,c,d,b,a>
721 backpermute :: Vector a -> Vector Int -> Vector a
722 {-# INLINE backpermute #-}
723 backpermute = G.backpermute
724
725 -- | Same as 'backpermute' but without bounds checking.
726 unsafeBackpermute :: Vector a -> Vector Int -> Vector a
727 {-# INLINE unsafeBackpermute #-}
728 unsafeBackpermute = G.unsafeBackpermute
729
730 -- Safe destructive updates
731 -- ------------------------
732
733 -- | Apply a destructive operation to a vector. The operation will be
734 -- performed in place if it is safe to do so and will modify a copy of the
735 -- vector otherwise.
736 --
737 -- @
738 -- modify (\\v -> write v 0 \'x\') ('replicate' 3 \'a\') = \<\'x\',\'a\',\'a\'\>
739 -- @
740 modify :: (forall s. MVector s a -> ST s ()) -> Vector a -> Vector a
741 {-# INLINE modify #-}
742 modify p = G.modify p
743
744 -- Indexing
745 -- --------
746
747 -- | /O(n)/ Pair each element in a vector with its index
748 indexed :: Vector a -> Vector (Int,a)
749 {-# INLINE indexed #-}
750 indexed = G.indexed
751
752 -- Mapping
753 -- -------
754
755 -- | /O(n)/ Map a function over a vector
756 map :: (a -> b) -> Vector a -> Vector b
757 {-# INLINE map #-}
758 map = G.map
759
760 -- | /O(n)/ Apply a function to every element of a vector and its index
761 imap :: (Int -> a -> b) -> Vector a -> Vector b
762 {-# INLINE imap #-}
763 imap = G.imap
764
765 -- | Map a function over a vector and concatenate the results.
766 concatMap :: (a -> Vector b) -> Vector a -> Vector b
767 {-# INLINE concatMap #-}
768 concatMap = G.concatMap
769
770 -- Monadic mapping
771 -- ---------------
772
773 -- | /O(n)/ Apply the monadic action to all elements of the vector, yielding a
774 -- vector of results
775 mapM :: Monad m => (a -> m b) -> Vector a -> m (Vector b)
776 {-# INLINE mapM #-}
777 mapM = G.mapM
778
779 -- | /O(n)/ Apply the monadic action to all elements of a vector and ignore the
780 -- results
781 mapM_ :: Monad m => (a -> m b) -> Vector a -> m ()
782 {-# INLINE mapM_ #-}
783 mapM_ = G.mapM_
784
785 -- | /O(n)/ Apply the monadic action to all elements of the vector, yielding a
786 -- vector of results. Equvalent to @flip 'mapM'@.
787 forM :: Monad m => Vector a -> (a -> m b) -> m (Vector b)
788 {-# INLINE forM #-}
789 forM = G.forM
790
791 -- | /O(n)/ Apply the monadic action to all elements of a vector and ignore the
792 -- results. Equivalent to @flip 'mapM_'@.
793 forM_ :: Monad m => Vector a -> (a -> m b) -> m ()
794 {-# INLINE forM_ #-}
795 forM_ = G.forM_
796
797 -- Zipping
798 -- -------
799
800 -- | /O(min(m,n))/ Zip two vectors with the given function.
801 zipWith :: (a -> b -> c) -> Vector a -> Vector b -> Vector c
802 {-# INLINE zipWith #-}
803 zipWith = G.zipWith
804
805 -- | Zip three vectors with the given function.
806 zipWith3 :: (a -> b -> c -> d) -> Vector a -> Vector b -> Vector c -> Vector d
807 {-# INLINE zipWith3 #-}
808 zipWith3 = G.zipWith3
809
810 zipWith4 :: (a -> b -> c -> d -> e)
811 -> Vector a -> Vector b -> Vector c -> Vector d -> Vector e
812 {-# INLINE zipWith4 #-}
813 zipWith4 = G.zipWith4
814
815 zipWith5 :: (a -> b -> c -> d -> e -> f)
816 -> Vector a -> Vector b -> Vector c -> Vector d -> Vector e
817 -> Vector f
818 {-# INLINE zipWith5 #-}
819 zipWith5 = G.zipWith5
820
821 zipWith6 :: (a -> b -> c -> d -> e -> f -> g)
822 -> Vector a -> Vector b -> Vector c -> Vector d -> Vector e
823 -> Vector f -> Vector g
824 {-# INLINE zipWith6 #-}
825 zipWith6 = G.zipWith6
826
827 -- | /O(min(m,n))/ Zip two vectors with a function that also takes the
828 -- elements' indices.
829 izipWith :: (Int -> a -> b -> c) -> Vector a -> Vector b -> Vector c
830 {-# INLINE izipWith #-}
831 izipWith = G.izipWith
832
833 -- | Zip three vectors and their indices with the given function.
834 izipWith3 :: (Int -> a -> b -> c -> d)
835 -> Vector a -> Vector b -> Vector c -> Vector d
836 {-# INLINE izipWith3 #-}
837 izipWith3 = G.izipWith3
838
839 izipWith4 :: (Int -> a -> b -> c -> d -> e)
840 -> Vector a -> Vector b -> Vector c -> Vector d -> Vector e
841 {-# INLINE izipWith4 #-}
842 izipWith4 = G.izipWith4
843
844 izipWith5 :: (Int -> a -> b -> c -> d -> e -> f)
845 -> Vector a -> Vector b -> Vector c -> Vector d -> Vector e
846 -> Vector f
847 {-# INLINE izipWith5 #-}
848 izipWith5 = G.izipWith5
849
850 izipWith6 :: (Int -> a -> b -> c -> d -> e -> f -> g)
851 -> Vector a -> Vector b -> Vector c -> Vector d -> Vector e
852 -> Vector f -> Vector g
853 {-# INLINE izipWith6 #-}
854 izipWith6 = G.izipWith6
855
856 -- | Elementwise pairing of array elements.
857 zip :: Vector a -> Vector b -> Vector (a, b)
858 {-# INLINE zip #-}
859 zip = G.zip
860
861 -- | zip together three vectors into a vector of triples
862 zip3 :: Vector a -> Vector b -> Vector c -> Vector (a, b, c)
863 {-# INLINE zip3 #-}
864 zip3 = G.zip3
865
866 zip4 :: Vector a -> Vector b -> Vector c -> Vector d
867 -> Vector (a, b, c, d)
868 {-# INLINE zip4 #-}
869 zip4 = G.zip4
870
871 zip5 :: Vector a -> Vector b -> Vector c -> Vector d -> Vector e
872 -> Vector (a, b, c, d, e)
873 {-# INLINE zip5 #-}
874 zip5 = G.zip5
875
876 zip6 :: Vector a -> Vector b -> Vector c -> Vector d -> Vector e -> Vector f
877 -> Vector (a, b, c, d, e, f)
878 {-# INLINE zip6 #-}
879 zip6 = G.zip6
880
881 -- Unzipping
882 -- ---------
883
884 -- | /O(min(m,n))/ Unzip a vector of pairs.
885 unzip :: Vector (a, b) -> (Vector a, Vector b)
886 {-# INLINE unzip #-}
887 unzip = G.unzip
888
889 unzip3 :: Vector (a, b, c) -> (Vector a, Vector b, Vector c)
890 {-# INLINE unzip3 #-}
891 unzip3 = G.unzip3
892
893 unzip4 :: Vector (a, b, c, d) -> (Vector a, Vector b, Vector c, Vector d)
894 {-# INLINE unzip4 #-}
895 unzip4 = G.unzip4
896
897 unzip5 :: Vector (a, b, c, d, e)
898 -> (Vector a, Vector b, Vector c, Vector d, Vector e)
899 {-# INLINE unzip5 #-}
900 unzip5 = G.unzip5
901
902 unzip6 :: Vector (a, b, c, d, e, f)
903 -> (Vector a, Vector b, Vector c, Vector d, Vector e, Vector f)
904 {-# INLINE unzip6 #-}
905 unzip6 = G.unzip6
906
907 -- Monadic zipping
908 -- ---------------
909
910 -- | /O(min(m,n))/ Zip the two vectors with the monadic action and yield a
911 -- vector of results
912 zipWithM :: Monad m => (a -> b -> m c) -> Vector a -> Vector b -> m (Vector c)
913 {-# INLINE zipWithM #-}
914 zipWithM = G.zipWithM
915
916 -- | /O(min(m,n))/ Zip the two vectors with the monadic action and ignore the
917 -- results
918 zipWithM_ :: Monad m => (a -> b -> m c) -> Vector a -> Vector b -> m ()
919 {-# INLINE zipWithM_ #-}
920 zipWithM_ = G.zipWithM_
921
922 -- Filtering
923 -- ---------
924
925 -- | /O(n)/ Drop elements that do not satisfy the predicate
926 filter :: (a -> Bool) -> Vector a -> Vector a
927 {-# INLINE filter #-}
928 filter = G.filter
929
930 -- | /O(n)/ Drop elements that do not satisfy the predicate which is applied to
931 -- values and their indices
932 ifilter :: (Int -> a -> Bool) -> Vector a -> Vector a
933 {-# INLINE ifilter #-}
934 ifilter = G.ifilter
935
936 -- | /O(n)/ Drop elements that do not satisfy the monadic predicate
937 filterM :: Monad m => (a -> m Bool) -> Vector a -> m (Vector a)
938 {-# INLINE filterM #-}
939 filterM = G.filterM
940
941 -- | /O(n)/ Yield the longest prefix of elements satisfying the predicate
942 -- without copying.
943 takeWhile :: (a -> Bool) -> Vector a -> Vector a
944 {-# INLINE takeWhile #-}
945 takeWhile = G.takeWhile
946
947 -- | /O(n)/ Drop the longest prefix of elements that satisfy the predicate
948 -- without copying.
949 dropWhile :: (a -> Bool) -> Vector a -> Vector a
950 {-# INLINE dropWhile #-}
951 dropWhile = G.dropWhile
952
953 -- Parititioning
954 -- -------------
955
956 -- | /O(n)/ Split the vector in two parts, the first one containing those
957 -- elements that satisfy the predicate and the second one those that don't. The
958 -- relative order of the elements is preserved at the cost of a sometimes
959 -- reduced performance compared to 'unstablePartition'.
960 partition :: (a -> Bool) -> Vector a -> (Vector a, Vector a)
961 {-# INLINE partition #-}
962 partition = G.partition
963
964 -- | /O(n)/ Split the vector in two parts, the first one containing those
965 -- elements that satisfy the predicate and the second one those that don't.
966 -- The order of the elements is not preserved but the operation is often
967 -- faster than 'partition'.
968 unstablePartition :: (a -> Bool) -> Vector a -> (Vector a, Vector a)
969 {-# INLINE unstablePartition #-}
970 unstablePartition = G.unstablePartition
971
972 -- | /O(n)/ Split the vector into the longest prefix of elements that satisfy
973 -- the predicate and the rest without copying.
974 span :: (a -> Bool) -> Vector a -> (Vector a, Vector a)
975 {-# INLINE span #-}
976 span = G.span
977
978 -- | /O(n)/ Split the vector into the longest prefix of elements that do not
979 -- satisfy the predicate and the rest without copying.
980 break :: (a -> Bool) -> Vector a -> (Vector a, Vector a)
981 {-# INLINE break #-}
982 break = G.break
983
984 -- Searching
985 -- ---------
986
987 infix 4 `elem`
988 -- | /O(n)/ Check if the vector contains an element
989 elem :: Eq a => a -> Vector a -> Bool
990 {-# INLINE elem #-}
991 elem = G.elem
992
993 infix 4 `notElem`
994 -- | /O(n)/ Check if the vector does not contain an element (inverse of 'elem')
995 notElem :: Eq a => a -> Vector a -> Bool
996 {-# INLINE notElem #-}
997 notElem = G.notElem
998
999 -- | /O(n)/ Yield 'Just' the first element matching the predicate or 'Nothing'
1000 -- if no such element exists.
1001 find :: (a -> Bool) -> Vector a -> Maybe a
1002 {-# INLINE find #-}
1003 find = G.find
1004
1005 -- | /O(n)/ Yield 'Just' the index of the first element matching the predicate
1006 -- or 'Nothing' if no such element exists.
1007 findIndex :: (a -> Bool) -> Vector a -> Maybe Int
1008 {-# INLINE findIndex #-}
1009 findIndex = G.findIndex
1010
1011 -- | /O(n)/ Yield the indices of elements satisfying the predicate in ascending
1012 -- order.
1013 findIndices :: (a -> Bool) -> Vector a -> Vector Int
1014 {-# INLINE findIndices #-}
1015 findIndices = G.findIndices
1016
1017 -- | /O(n)/ Yield 'Just' the index of the first occurence of the given element or
1018 -- 'Nothing' if the vector does not contain the element. This is a specialised
1019 -- version of 'findIndex'.
1020 elemIndex :: Eq a => a -> Vector a -> Maybe Int
1021 {-# INLINE elemIndex #-}
1022 elemIndex = G.elemIndex
1023
1024 -- | /O(n)/ Yield the indices of all occurences of the given element in
1025 -- ascending order. This is a specialised version of 'findIndices'.
1026 elemIndices :: Eq a => a -> Vector a -> Vector Int
1027 {-# INLINE elemIndices #-}
1028 elemIndices = G.elemIndices
1029
1030 -- Folding
1031 -- -------
1032
1033 -- | /O(n)/ Left fold
1034 foldl :: (a -> b -> a) -> a -> Vector b -> a
1035 {-# INLINE foldl #-}
1036 foldl = G.foldl
1037
1038 -- | /O(n)/ Left fold on non-empty vectors
1039 foldl1 :: (a -> a -> a) -> Vector a -> a
1040 {-# INLINE foldl1 #-}
1041 foldl1 = G.foldl1
1042
1043 -- | /O(n)/ Left fold with strict accumulator
1044 foldl' :: (a -> b -> a) -> a -> Vector b -> a
1045 {-# INLINE foldl' #-}
1046 foldl' = G.foldl'
1047
1048 -- | /O(n)/ Left fold on non-empty vectors with strict accumulator
1049 foldl1' :: (a -> a -> a) -> Vector a -> a
1050 {-# INLINE foldl1' #-}
1051 foldl1' = G.foldl1'
1052
1053 -- | /O(n)/ Right fold
1054 foldr :: (a -> b -> b) -> b -> Vector a -> b
1055 {-# INLINE foldr #-}
1056 foldr = G.foldr
1057
1058 -- | /O(n)/ Right fold on non-empty vectors
1059 foldr1 :: (a -> a -> a) -> Vector a -> a
1060 {-# INLINE foldr1 #-}
1061 foldr1 = G.foldr1
1062
1063 -- | /O(n)/ Right fold with a strict accumulator
1064 foldr' :: (a -> b -> b) -> b -> Vector a -> b
1065 {-# INLINE foldr' #-}
1066 foldr' = G.foldr'
1067
1068 -- | /O(n)/ Right fold on non-empty vectors with strict accumulator
1069 foldr1' :: (a -> a -> a) -> Vector a -> a
1070 {-# INLINE foldr1' #-}
1071 foldr1' = G.foldr1'
1072
1073 -- | /O(n)/ Left fold (function applied to each element and its index)
1074 ifoldl :: (a -> Int -> b -> a) -> a -> Vector b -> a
1075 {-# INLINE ifoldl #-}
1076 ifoldl = G.ifoldl
1077
1078 -- | /O(n)/ Left fold with strict accumulator (function applied to each element
1079 -- and its index)
1080 ifoldl' :: (a -> Int -> b -> a) -> a -> Vector b -> a
1081 {-# INLINE ifoldl' #-}
1082 ifoldl' = G.ifoldl'
1083
1084 -- | /O(n)/ Right fold (function applied to each element and its index)
1085 ifoldr :: (Int -> a -> b -> b) -> b -> Vector a -> b
1086 {-# INLINE ifoldr #-}
1087 ifoldr = G.ifoldr
1088
1089 -- | /O(n)/ Right fold with strict accumulator (function applied to each
1090 -- element and its index)
1091 ifoldr' :: (Int -> a -> b -> b) -> b -> Vector a -> b
1092 {-# INLINE ifoldr' #-}
1093 ifoldr' = G.ifoldr'
1094
1095 -- Specialised folds
1096 -- -----------------
1097
1098 -- | /O(n)/ Check if all elements satisfy the predicate.
1099 all :: (a -> Bool) -> Vector a -> Bool
1100 {-# INLINE all #-}
1101 all = G.all
1102
1103 -- | /O(n)/ Check if any element satisfies the predicate.
1104 any :: (a -> Bool) -> Vector a -> Bool
1105 {-# INLINE any #-}
1106 any = G.any
1107
1108 -- | /O(n)/ Check if all elements are 'True'
1109 and :: Vector Bool -> Bool
1110 {-# INLINE and #-}
1111 and = G.and
1112
1113 -- | /O(n)/ Check if any element is 'True'
1114 or :: Vector Bool -> Bool
1115 {-# INLINE or #-}
1116 or = G.or
1117
1118 -- | /O(n)/ Compute the sum of the elements
1119 sum :: Num a => Vector a -> a
1120 {-# INLINE sum #-}
1121 sum = G.sum
1122
1123 -- | /O(n)/ Compute the produce of the elements
1124 product :: Num a => Vector a -> a
1125 {-# INLINE product #-}
1126 product = G.product
1127
1128 -- | /O(n)/ Yield the maximum element of the vector. The vector may not be
1129 -- empty.
1130 maximum :: Ord a => Vector a -> a
1131 {-# INLINE maximum #-}
1132 maximum = G.maximum
1133
1134 -- | /O(n)/ Yield the maximum element of the vector according to the given
1135 -- comparison function. The vector may not be empty.
1136 maximumBy :: (a -> a -> Ordering) -> Vector a -> a
1137 {-# INLINE maximumBy #-}
1138 maximumBy = G.maximumBy
1139
1140 -- | /O(n)/ Yield the minimum element of the vector. The vector may not be
1141 -- empty.
1142 minimum :: Ord a => Vector a -> a
1143 {-# INLINE minimum #-}
1144 minimum = G.minimum
1145
1146 -- | /O(n)/ Yield the minimum element of the vector according to the given
1147 -- comparison function. The vector may not be empty.
1148 minimumBy :: (a -> a -> Ordering) -> Vector a -> a
1149 {-# INLINE minimumBy #-}
1150 minimumBy = G.minimumBy
1151
1152 -- | /O(n)/ Yield the index of the maximum element of the vector. The vector
1153 -- may not be empty.
1154 maxIndex :: Ord a => Vector a -> Int
1155 {-# INLINE maxIndex #-}
1156 maxIndex = G.maxIndex
1157
1158 -- | /O(n)/ Yield the index of the maximum element of the vector according to
1159 -- the given comparison function. The vector may not be empty.
1160 maxIndexBy :: (a -> a -> Ordering) -> Vector a -> Int
1161 {-# INLINE maxIndexBy #-}
1162 maxIndexBy = G.maxIndexBy
1163
1164 -- | /O(n)/ Yield the index of the minimum element of the vector. The vector
1165 -- may not be empty.
1166 minIndex :: Ord a => Vector a -> Int
1167 {-# INLINE minIndex #-}
1168 minIndex = G.minIndex
1169
1170 -- | /O(n)/ Yield the index of the minimum element of the vector according to
1171 -- the given comparison function. The vector may not be empty.
1172 minIndexBy :: (a -> a -> Ordering) -> Vector a -> Int
1173 {-# INLINE minIndexBy #-}
1174 minIndexBy = G.minIndexBy
1175
1176 -- Monadic folds
1177 -- -------------
1178
1179 -- | /O(n)/ Monadic fold
1180 foldM :: Monad m => (a -> b -> m a) -> a -> Vector b -> m a
1181 {-# INLINE foldM #-}
1182 foldM = G.foldM
1183
1184 -- | /O(n)/ Monadic fold over non-empty vectors
1185 fold1M :: Monad m => (a -> a -> m a) -> Vector a -> m a
1186 {-# INLINE fold1M #-}
1187 fold1M = G.fold1M
1188
1189 -- | /O(n)/ Monadic fold with strict accumulator
1190 foldM' :: Monad m => (a -> b -> m a) -> a -> Vector b -> m a
1191 {-# INLINE foldM' #-}
1192 foldM' = G.foldM'
1193
1194 -- | /O(n)/ Monadic fold over non-empty vectors with strict accumulator
1195 fold1M' :: Monad m => (a -> a -> m a) -> Vector a -> m a
1196 {-# INLINE fold1M' #-}
1197 fold1M' = G.fold1M'
1198
1199 -- | /O(n)/ Monadic fold that discards the result
1200 foldM_ :: Monad m => (a -> b -> m a) -> a -> Vector b -> m ()
1201 {-# INLINE foldM_ #-}
1202 foldM_ = G.foldM_
1203
1204 -- | /O(n)/ Monadic fold over non-empty vectors that discards the result
1205 fold1M_ :: Monad m => (a -> a -> m a) -> Vector a -> m ()
1206 {-# INLINE fold1M_ #-}
1207 fold1M_ = G.fold1M_
1208
1209 -- | /O(n)/ Monadic fold with strict accumulator that discards the result
1210 foldM'_ :: Monad m => (a -> b -> m a) -> a -> Vector b -> m ()
1211 {-# INLINE foldM'_ #-}
1212 foldM'_ = G.foldM'_
1213
1214 -- | /O(n)/ Monadic fold over non-empty vectors with strict accumulator
1215 -- that discards the result
1216 fold1M'_ :: Monad m => (a -> a -> m a) -> Vector a -> m ()
1217 {-# INLINE fold1M'_ #-}
1218 fold1M'_ = G.fold1M'_
1219
1220 -- Monadic sequencing
1221 -- ------------------
1222
1223 -- | Evaluate each action and collect the results
1224 sequence :: Monad m => Vector (m a) -> m (Vector a)
1225 {-# INLINE sequence #-}
1226 sequence = G.sequence
1227
1228 -- | Evaluate each action and discard the results
1229 sequence_ :: Monad m => Vector (m a) -> m ()
1230 {-# INLINE sequence_ #-}
1231 sequence_ = G.sequence_
1232
1233 -- Prefix sums (scans)
1234 -- -------------------
1235
1236 -- | /O(n)/ Prescan
1237 --
1238 -- @
1239 -- prescanl f z = 'init' . 'scanl' f z
1240 -- @
1241 --
1242 -- Example: @prescanl (+) 0 \<1,2,3,4\> = \<0,1,3,6\>@
1243 --
1244 prescanl :: (a -> b -> a) -> a -> Vector b -> Vector a
1245 {-# INLINE prescanl #-}
1246 prescanl = G.prescanl
1247
1248 -- | /O(n)/ Prescan with strict accumulator
1249 prescanl' :: (a -> b -> a) -> a -> Vector b -> Vector a
1250 {-# INLINE prescanl' #-}
1251 prescanl' = G.prescanl'
1252
1253 -- | /O(n)/ Scan
1254 --
1255 -- @
1256 -- postscanl f z = 'tail' . 'scanl' f z
1257 -- @
1258 --
1259 -- Example: @postscanl (+) 0 \<1,2,3,4\> = \<1,3,6,10\>@
1260 --
1261 postscanl :: (a -> b -> a) -> a -> Vector b -> Vector a
1262 {-# INLINE postscanl #-}
1263 postscanl = G.postscanl
1264
1265 -- | /O(n)/ Scan with strict accumulator
1266 postscanl' :: (a -> b -> a) -> a -> Vector b -> Vector a
1267 {-# INLINE postscanl' #-}
1268 postscanl' = G.postscanl'
1269
1270 -- | /O(n)/ Haskell-style scan
1271 --
1272 -- > scanl f z <x1,...,xn> = <y1,...,y(n+1)>
1273 -- > where y1 = z
1274 -- > yi = f y(i-1) x(i-1)
1275 --
1276 -- Example: @scanl (+) 0 \<1,2,3,4\> = \<0,1,3,6,10\>@
1277 --
1278 scanl :: (a -> b -> a) -> a -> Vector b -> Vector a
1279 {-# INLINE scanl #-}
1280 scanl = G.scanl
1281
1282 -- | /O(n)/ Haskell-style scan with strict accumulator
1283 scanl' :: (a -> b -> a) -> a -> Vector b -> Vector a
1284 {-# INLINE scanl' #-}
1285 scanl' = G.scanl'
1286
1287 -- | /O(n)/ Scan over a non-empty vector
1288 --
1289 -- > scanl f <x1,...,xn> = <y1,...,yn>
1290 -- > where y1 = x1
1291 -- > yi = f y(i-1) xi
1292 --
1293 scanl1 :: (a -> a -> a) -> Vector a -> Vector a
1294 {-# INLINE scanl1 #-}
1295 scanl1 = G.scanl1
1296
1297 -- | /O(n)/ Scan over a non-empty vector with a strict accumulator
1298 scanl1' :: (a -> a -> a) -> Vector a -> Vector a
1299 {-# INLINE scanl1' #-}
1300 scanl1' = G.scanl1'
1301
1302 -- | /O(n)/ Right-to-left prescan
1303 --
1304 -- @
1305 -- prescanr f z = 'reverse' . 'prescanl' (flip f) z . 'reverse'
1306 -- @
1307 --
1308 prescanr :: (a -> b -> b) -> b -> Vector a -> Vector b
1309 {-# INLINE prescanr #-}
1310 prescanr = G.prescanr
1311
1312 -- | /O(n)/ Right-to-left prescan with strict accumulator
1313 prescanr' :: (a -> b -> b) -> b -> Vector a -> Vector b
1314 {-# INLINE prescanr' #-}
1315 prescanr' = G.prescanr'
1316
1317 -- | /O(n)/ Right-to-left scan
1318 postscanr :: (a -> b -> b) -> b -> Vector a -> Vector b
1319 {-# INLINE postscanr #-}
1320 postscanr = G.postscanr
1321
1322 -- | /O(n)/ Right-to-left scan with strict accumulator
1323 postscanr' :: (a -> b -> b) -> b -> Vector a -> Vector b
1324 {-# INLINE postscanr' #-}
1325 postscanr' = G.postscanr'
1326
1327 -- | /O(n)/ Right-to-left Haskell-style scan
1328 scanr :: (a -> b -> b) -> b -> Vector a -> Vector b
1329 {-# INLINE scanr #-}
1330 scanr = G.scanr
1331
1332 -- | /O(n)/ Right-to-left Haskell-style scan with strict accumulator
1333 scanr' :: (a -> b -> b) -> b -> Vector a -> Vector b
1334 {-# INLINE scanr' #-}
1335 scanr' = G.scanr'
1336
1337 -- | /O(n)/ Right-to-left scan over a non-empty vector
1338 scanr1 :: (a -> a -> a) -> Vector a -> Vector a
1339 {-# INLINE scanr1 #-}
1340 scanr1 = G.scanr1
1341
1342 -- | /O(n)/ Right-to-left scan over a non-empty vector with a strict
1343 -- accumulator
1344 scanr1' :: (a -> a -> a) -> Vector a -> Vector a
1345 {-# INLINE scanr1' #-}
1346 scanr1' = G.scanr1'
1347
1348 -- Conversions - Lists
1349 -- ------------------------
1350
1351 -- | /O(n)/ Convert a vector to a list
1352 toList :: Vector a -> [a]
1353 {-# INLINE toList #-}
1354 toList = G.toList
1355
1356 -- | /O(n)/ Convert a list to a vector
1357 fromList :: [a] -> Vector a
1358 {-# INLINE fromList #-}
1359 fromList = G.fromList
1360
1361 -- | /O(n)/ Convert the first @n@ elements of a list to a vector
1362 --
1363 -- @
1364 -- fromListN n xs = 'fromList' ('take' n xs)
1365 -- @
1366 fromListN :: Int -> [a] -> Vector a
1367 {-# INLINE fromListN #-}
1368 fromListN = G.fromListN
1369
1370 -- Conversions - Mutable vectors
1371 -- -----------------------------
1372
1373 -- | /O(1)/ Unsafe convert a mutable vector to an immutable one without
1374 -- copying. The mutable vector may not be used after this operation.
1375 unsafeFreeze :: PrimMonad m => MVector (PrimState m) a -> m (Vector a)
1376 {-# INLINE unsafeFreeze #-}
1377 unsafeFreeze = G.unsafeFreeze
1378
1379 -- | /O(1)/ Unsafely convert an immutable vector to a mutable one without
1380 -- copying. The immutable vector may not be used after this operation.
1381 unsafeThaw :: PrimMonad m => Vector a -> m (MVector (PrimState m) a)
1382 {-# INLINE unsafeThaw #-}
1383 unsafeThaw = G.unsafeThaw
1384
1385 -- | /O(n)/ Yield a mutable copy of the immutable vector.
1386 thaw :: PrimMonad m => Vector a -> m (MVector (PrimState m) a)
1387 {-# INLINE thaw #-}
1388 thaw = G.thaw
1389
1390 -- | /O(n)/ Yield an immutable copy of the mutable vector.
1391 freeze :: PrimMonad m => MVector (PrimState m) a -> m (Vector a)
1392 {-# INLINE freeze #-}
1393 freeze = G.freeze
1394
1395 -- | /O(n)/ Copy an immutable vector into a mutable one. The two vectors must
1396 -- have the same length. This is not checked.
1397 unsafeCopy :: PrimMonad m => MVector (PrimState m) a -> Vector a -> m ()
1398 {-# INLINE unsafeCopy #-}
1399 unsafeCopy = G.unsafeCopy
1400
1401 -- | /O(n)/ Copy an immutable vector into a mutable one. The two vectors must
1402 -- have the same length.
1403 copy :: PrimMonad m => MVector (PrimState m) a -> Vector a -> m ()
1404 {-# INLINE copy #-}
1405 copy = G.copy
1406