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