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