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