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