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