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