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