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