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