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