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