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