Add concat and make concatMap more efficient
[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 -- ** Mutable vectors
140 thaw, thawMany, 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, (++), concat,
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 -- | /O(n)/ Concatenate all vectors in the list
500 concat :: [Vector a] -> Vector a
501 {-# INLINE concat #-}
502 concat = G.concat
503
504 -- Monadic initialisation
505 -- ----------------------
506
507 -- | /O(n)/ Execute the monadic action the given number of times and store the
508 -- results in a vector.
509 replicateM :: Monad m => Int -> m a -> m (Vector a)
510 {-# INLINE replicateM #-}
511 replicateM = G.replicateM
512
513 -- | Execute the monadic action and freeze the resulting vector.
514 --
515 -- @
516 -- create (do { v \<- new 2; write v 0 \'a\'; write v 1 \'b\' }) = \<'a','b'\>
517 -- @
518 create :: (forall s. ST s (MVector s a)) -> Vector a
519 {-# INLINE create #-}
520 create = G.create
521
522
523
524 -- Restricting memory usage
525 -- ------------------------
526
527 -- | /O(n)/ Yield the argument but force it not to retain any extra memory,
528 -- possibly by copying it.
529 --
530 -- This is especially useful when dealing with slices. For example:
531 --
532 -- > force (slice 0 2 <huge vector>)
533 --
534 -- Here, the slice retains a reference to the huge vector. Forcing it creates
535 -- a copy of just the elements that belong to the slice and allows the huge
536 -- vector to be garbage collected.
537 force :: Vector a -> Vector a
538 {-# INLINE force #-}
539 force = G.force
540
541 -- Bulk updates
542 -- ------------
543
544 -- | /O(m+n)/ For each pair @(i,a)@ from the list, replace the vector
545 -- element at position @i@ by @a@.
546 --
547 -- > <5,9,2,7> // [(2,1),(0,3),(2,8)] = <3,9,8,7>
548 --
549 (//) :: Vector a -- ^ initial vector (of length @m@)
550 -> [(Int, a)] -- ^ list of index/value pairs (of length @n@)
551 -> Vector a
552 {-# INLINE (//) #-}
553 (//) = (G.//)
554
555 -- | /O(m+n)/ For each pair @(i,a)@ from the vector of index/value pairs,
556 -- replace the vector element at position @i@ by @a@.
557 --
558 -- > update <5,9,2,7> <(2,1),(0,3),(2,8)> = <3,9,8,7>
559 --
560 update :: Vector a -- ^ initial vector (of length @m@)
561 -> Vector (Int, a) -- ^ vector of index/value pairs (of length @n@)
562 -> Vector a
563 {-# INLINE update #-}
564 update = G.update
565
566 -- | /O(m+min(n1,n2))/ For each index @i@ from the index vector and the
567 -- corresponding value @a@ from the value vector, replace the element of the
568 -- initial vector at position @i@ by @a@.
569 --
570 -- > update_ <5,9,2,7> <2,0,2> <1,3,8> = <3,9,8,7>
571 --
572 -- The function 'update' provides the same functionality and is usually more
573 -- convenient.
574 --
575 -- @
576 -- update_ xs is ys = 'update' xs ('zip' is ys)
577 -- @
578 update_ :: Vector a -- ^ initial vector (of length @m@)
579 -> Vector Int -- ^ index vector (of length @n1@)
580 -> Vector a -- ^ value vector (of length @n2@)
581 -> Vector a
582 {-# INLINE update_ #-}
583 update_ = G.update_
584
585 -- | Same as ('//') but without bounds checking.
586 unsafeUpd :: Vector a -> [(Int, a)] -> Vector a
587 {-# INLINE unsafeUpd #-}
588 unsafeUpd = G.unsafeUpd
589
590 -- | Same as 'update' but without bounds checking.
591 unsafeUpdate :: Vector a -> Vector (Int, a) -> Vector a
592 {-# INLINE unsafeUpdate #-}
593 unsafeUpdate = G.unsafeUpdate
594
595 -- | Same as 'update_' but without bounds checking.
596 unsafeUpdate_ :: Vector a -> Vector Int -> Vector a -> Vector a
597 {-# INLINE unsafeUpdate_ #-}
598 unsafeUpdate_ = G.unsafeUpdate_
599
600 -- Accumulations
601 -- -------------
602
603 -- | /O(m+n)/ For each pair @(i,b)@ from the list, replace the vector element
604 -- @a@ at position @i@ by @f a b@.
605 --
606 -- > accum (+) <5,9,2> [(2,4),(1,6),(0,3),(1,7)] = <5+3, 9+6+7, 2+4>
607 accum :: (a -> b -> a) -- ^ accumulating function @f@
608 -> Vector a -- ^ initial vector (of length @m@)
609 -> [(Int,b)] -- ^ list of index/value pairs (of length @n@)
610 -> Vector a
611 {-# INLINE accum #-}
612 accum = G.accum
613
614 -- | /O(m+n)/ For each pair @(i,b)@ from the vector of pairs, replace the vector
615 -- element @a@ at position @i@ by @f a b@.
616 --
617 -- > accumulate (+) <5,9,2> <(2,4),(1,6),(0,3),(1,7)> = <5+3, 9+6+7, 2+4>
618 accumulate :: (a -> b -> a) -- ^ accumulating function @f@
619 -> Vector a -- ^ initial vector (of length @m@)
620 -> Vector (Int,b) -- ^ vector of index/value pairs (of length @n@)
621 -> Vector a
622 {-# INLINE accumulate #-}
623 accumulate = G.accumulate
624
625 -- | /O(m+min(n1,n2))/ For each index @i@ from the index vector and the
626 -- corresponding value @b@ from the the value vector,
627 -- replace the element of the initial vector at
628 -- position @i@ by @f a b@.
629 --
630 -- > accumulate_ (+) <5,9,2> <2,1,0,1> <4,6,3,7> = <5+3, 9+6+7, 2+4>
631 --
632 -- The function 'accumulate' provides the same functionality and is usually more
633 -- convenient.
634 --
635 -- @
636 -- accumulate_ f as is bs = 'accumulate' f as ('zip' is bs)
637 -- @
638 accumulate_ :: (a -> b -> a) -- ^ accumulating function @f@
639 -> Vector a -- ^ initial vector (of length @m@)
640 -> Vector Int -- ^ index vector (of length @n1@)
641 -> Vector b -- ^ value vector (of length @n2@)
642 -> Vector a
643 {-# INLINE accumulate_ #-}
644 accumulate_ = G.accumulate_
645
646 -- | Same as 'accum' but without bounds checking.
647 unsafeAccum :: (a -> b -> a) -> Vector a -> [(Int,b)] -> Vector a
648 {-# INLINE unsafeAccum #-}
649 unsafeAccum = G.unsafeAccum
650
651 -- | Same as 'accumulate' but without bounds checking.
652 unsafeAccumulate :: (a -> b -> a) -> Vector a -> Vector (Int,b) -> Vector a
653 {-# INLINE unsafeAccumulate #-}
654 unsafeAccumulate = G.unsafeAccumulate
655
656 -- | Same as 'accumulate_' but without bounds checking.
657 unsafeAccumulate_
658 :: (a -> b -> a) -> Vector a -> Vector Int -> Vector b -> Vector a
659 {-# INLINE unsafeAccumulate_ #-}
660 unsafeAccumulate_ = G.unsafeAccumulate_
661
662 -- Permutations
663 -- ------------
664
665 -- | /O(n)/ Reverse a vector
666 reverse :: Vector a -> Vector a
667 {-# INLINE reverse #-}
668 reverse = G.reverse
669
670 -- | /O(n)/ Yield the vector obtained by replacing each element @i@ of the
671 -- index vector by @xs'!'i@. This is equivalent to @'map' (xs'!') is@ but is
672 -- often much more efficient.
673 --
674 -- > backpermute <a,b,c,d> <0,3,2,3,1,0> = <a,d,c,d,b,a>
675 backpermute :: Vector a -> Vector Int -> Vector a
676 {-# INLINE backpermute #-}
677 backpermute = G.backpermute
678
679 -- | Same as 'backpermute' but without bounds checking.
680 unsafeBackpermute :: Vector a -> Vector Int -> Vector a
681 {-# INLINE unsafeBackpermute #-}
682 unsafeBackpermute = G.unsafeBackpermute
683
684 -- Safe destructive updates
685 -- ------------------------
686
687 -- | Apply a destructive operation to a vector. The operation will be
688 -- performed in place if it is safe to do so and will modify a copy of the
689 -- vector otherwise.
690 --
691 -- @
692 -- modify (\\v -> write v 0 \'x\') ('replicate' 3 \'a\') = \<\'x\',\'a\',\'a\'\>
693 -- @
694 modify :: (forall s. MVector s a -> ST s ()) -> Vector a -> Vector a
695 {-# INLINE modify #-}
696 modify = G.modify
697
698 -- Mapping
699 -- -------
700
701 -- | /O(n)/ Map a function over a vector
702 map :: (a -> b) -> Vector a -> Vector b
703 {-# INLINE map #-}
704 map = G.map
705
706 -- | /O(n)/ Apply a function to every element of a vector and its index
707 imap :: (Int -> a -> b) -> Vector a -> Vector b
708 {-# INLINE imap #-}
709 imap = G.imap
710
711 -- | Map a function over a vector and concatenate the results.
712 concatMap :: (a -> Vector b) -> Vector a -> Vector b
713 {-# INLINE concatMap #-}
714 concatMap = G.concatMap
715
716 -- Monadic mapping
717 -- ---------------
718
719 -- | /O(n)/ Apply the monadic action to all elements of the vector, yielding a
720 -- vector of results
721 mapM :: Monad m => (a -> m b) -> Vector a -> m (Vector b)
722 {-# INLINE mapM #-}
723 mapM = G.mapM
724
725 -- | /O(n)/ Apply the monadic action to all elements of a vector and ignore the
726 -- results
727 mapM_ :: Monad m => (a -> m b) -> Vector a -> m ()
728 {-# INLINE mapM_ #-}
729 mapM_ = G.mapM_
730
731 -- | /O(n)/ Apply the monadic action to all elements of the vector, yielding a
732 -- vector of results. Equvalent to @flip 'mapM'@.
733 forM :: Monad m => Vector a -> (a -> m b) -> m (Vector b)
734 {-# INLINE forM #-}
735 forM = G.forM
736
737 -- | /O(n)/ Apply the monadic action to all elements of a vector and ignore the
738 -- results. Equivalent to @flip 'mapM_'@.
739 forM_ :: Monad m => Vector a -> (a -> m b) -> m ()
740 {-# INLINE forM_ #-}
741 forM_ = G.forM_
742
743 -- Zipping
744 -- -------
745
746 -- | /O(min(m,n))/ Zip two vectors with the given function.
747 zipWith :: (a -> b -> c) -> Vector a -> Vector b -> Vector c
748 {-# INLINE zipWith #-}
749 zipWith = G.zipWith
750
751 -- | Zip three vectors with the given function.
752 zipWith3 :: (a -> b -> c -> d) -> Vector a -> Vector b -> Vector c -> Vector d
753 {-# INLINE zipWith3 #-}
754 zipWith3 = G.zipWith3
755
756 zipWith4 :: (a -> b -> c -> d -> e)
757 -> Vector a -> Vector b -> Vector c -> Vector d -> Vector e
758 {-# INLINE zipWith4 #-}
759 zipWith4 = G.zipWith4
760
761 zipWith5 :: (a -> b -> c -> d -> e -> f)
762 -> Vector a -> Vector b -> Vector c -> Vector d -> Vector e
763 -> Vector f
764 {-# INLINE zipWith5 #-}
765 zipWith5 = G.zipWith5
766
767 zipWith6 :: (a -> b -> c -> d -> e -> f -> g)
768 -> Vector a -> Vector b -> Vector c -> Vector d -> Vector e
769 -> Vector f -> Vector g
770 {-# INLINE zipWith6 #-}
771 zipWith6 = G.zipWith6
772
773 -- | /O(min(m,n))/ Zip two vectors with a function that also takes the
774 -- elements' indices.
775 izipWith :: (Int -> a -> b -> c) -> Vector a -> Vector b -> Vector c
776 {-# INLINE izipWith #-}
777 izipWith = G.izipWith
778
779 -- | Zip three vectors and their indices with the given function.
780 izipWith3 :: (Int -> a -> b -> c -> d)
781 -> Vector a -> Vector b -> Vector c -> Vector d
782 {-# INLINE izipWith3 #-}
783 izipWith3 = G.izipWith3
784
785 izipWith4 :: (Int -> a -> b -> c -> d -> e)
786 -> Vector a -> Vector b -> Vector c -> Vector d -> Vector e
787 {-# INLINE izipWith4 #-}
788 izipWith4 = G.izipWith4
789
790 izipWith5 :: (Int -> a -> b -> c -> d -> e -> f)
791 -> Vector a -> Vector b -> Vector c -> Vector d -> Vector e
792 -> Vector f
793 {-# INLINE izipWith5 #-}
794 izipWith5 = G.izipWith5
795
796 izipWith6 :: (Int -> a -> b -> c -> d -> e -> f -> g)
797 -> Vector a -> Vector b -> Vector c -> Vector d -> Vector e
798 -> Vector f -> Vector g
799 {-# INLINE izipWith6 #-}
800 izipWith6 = G.izipWith6
801
802 -- | Elementwise pairing of array elements.
803 zip :: Vector a -> Vector b -> Vector (a, b)
804 {-# INLINE zip #-}
805 zip = G.zip
806
807 -- | zip together three vectors into a vector of triples
808 zip3 :: Vector a -> Vector b -> Vector c -> Vector (a, b, c)
809 {-# INLINE zip3 #-}
810 zip3 = G.zip3
811
812 zip4 :: Vector a -> Vector b -> Vector c -> Vector d
813 -> Vector (a, b, c, d)
814 {-# INLINE zip4 #-}
815 zip4 = G.zip4
816
817 zip5 :: Vector a -> Vector b -> Vector c -> Vector d -> Vector e
818 -> Vector (a, b, c, d, e)
819 {-# INLINE zip5 #-}
820 zip5 = G.zip5
821
822 zip6 :: Vector a -> Vector b -> Vector c -> Vector d -> Vector e -> Vector f
823 -> Vector (a, b, c, d, e, f)
824 {-# INLINE zip6 #-}
825 zip6 = G.zip6
826
827 -- Unzipping
828 -- ---------
829
830 -- | /O(min(m,n))/ Unzip a vector of pairs.
831 unzip :: Vector (a, b) -> (Vector a, Vector b)
832 {-# INLINE unzip #-}
833 unzip = G.unzip
834
835 unzip3 :: Vector (a, b, c) -> (Vector a, Vector b, Vector c)
836 {-# INLINE unzip3 #-}
837 unzip3 = G.unzip3
838
839 unzip4 :: Vector (a, b, c, d) -> (Vector a, Vector b, Vector c, Vector d)
840 {-# INLINE unzip4 #-}
841 unzip4 = G.unzip4
842
843 unzip5 :: Vector (a, b, c, d, e)
844 -> (Vector a, Vector b, Vector c, Vector d, Vector e)
845 {-# INLINE unzip5 #-}
846 unzip5 = G.unzip5
847
848 unzip6 :: Vector (a, b, c, d, e, f)
849 -> (Vector a, Vector b, Vector c, Vector d, Vector e, Vector f)
850 {-# INLINE unzip6 #-}
851 unzip6 = G.unzip6
852
853 -- Monadic zipping
854 -- ---------------
855
856 -- | /O(min(m,n))/ Zip the two vectors with the monadic action and yield a
857 -- vector of results
858 zipWithM :: Monad m => (a -> b -> m c) -> Vector a -> Vector b -> m (Vector c)
859 {-# INLINE zipWithM #-}
860 zipWithM = G.zipWithM
861
862 -- | /O(min(m,n))/ Zip the two vectors with the monadic action and ignore the
863 -- results
864 zipWithM_ :: Monad m => (a -> b -> m c) -> Vector a -> Vector b -> m ()
865 {-# INLINE zipWithM_ #-}
866 zipWithM_ = G.zipWithM_
867
868 -- Filtering
869 -- ---------
870
871 -- | /O(n)/ Drop elements that do not satisfy the predicate
872 filter :: (a -> Bool) -> Vector a -> Vector a
873 {-# INLINE filter #-}
874 filter = G.filter
875
876 -- | /O(n)/ Drop elements that do not satisfy the predicate which is applied to
877 -- values and their indices
878 ifilter :: (Int -> a -> Bool) -> Vector a -> Vector a
879 {-# INLINE ifilter #-}
880 ifilter = G.ifilter
881
882 -- | /O(n)/ Drop elements that do not satisfy the monadic predicate
883 filterM :: Monad m => (a -> m Bool) -> Vector a -> m (Vector a)
884 {-# INLINE filterM #-}
885 filterM = G.filterM
886
887 -- | /O(n)/ Yield the longest prefix of elements satisfying the predicate
888 -- without copying.
889 takeWhile :: (a -> Bool) -> Vector a -> Vector a
890 {-# INLINE takeWhile #-}
891 takeWhile = G.takeWhile
892
893 -- | /O(n)/ Drop the longest prefix of elements that satisfy the predicate
894 -- without copying.
895 dropWhile :: (a -> Bool) -> Vector a -> Vector a
896 {-# INLINE dropWhile #-}
897 dropWhile = G.dropWhile
898
899 -- Parititioning
900 -- -------------
901
902 -- | /O(n)/ Split the vector in two parts, the first one containing those
903 -- elements that satisfy the predicate and the second one those that don't. The
904 -- relative order of the elements is preserved at the cost of a sometimes
905 -- reduced performance compared to 'unstablePartition'.
906 partition :: (a -> Bool) -> Vector a -> (Vector a, Vector a)
907 {-# INLINE partition #-}
908 partition = G.partition
909
910 -- | /O(n)/ Split the vector in two parts, the first one containing those
911 -- elements that satisfy the predicate and the second one those that don't.
912 -- The order of the elements is not preserved but the operation is often
913 -- faster than 'partition'.
914 unstablePartition :: (a -> Bool) -> Vector a -> (Vector a, Vector a)
915 {-# INLINE unstablePartition #-}
916 unstablePartition = G.unstablePartition
917
918 -- | /O(n)/ Split the vector into the longest prefix of elements that satisfy
919 -- the predicate and the rest without copying.
920 span :: (a -> Bool) -> Vector a -> (Vector a, Vector a)
921 {-# INLINE span #-}
922 span = G.span
923
924 -- | /O(n)/ Split the vector into the longest prefix of elements that do not
925 -- satisfy the predicate and the rest without copying.
926 break :: (a -> Bool) -> Vector a -> (Vector a, Vector a)
927 {-# INLINE break #-}
928 break = G.break
929
930 -- Searching
931 -- ---------
932
933 infix 4 `elem`
934 -- | /O(n)/ Check if the vector contains an element
935 elem :: Eq a => a -> Vector a -> Bool
936 {-# INLINE elem #-}
937 elem = G.elem
938
939 infix 4 `notElem`
940 -- | /O(n)/ Check if the vector does not contain an element (inverse of 'elem')
941 notElem :: Eq a => a -> Vector a -> Bool
942 {-# INLINE notElem #-}
943 notElem = G.notElem
944
945 -- | /O(n)/ Yield 'Just' the first element matching the predicate or 'Nothing'
946 -- if no such element exists.
947 find :: (a -> Bool) -> Vector a -> Maybe a
948 {-# INLINE find #-}
949 find = G.find
950
951 -- | /O(n)/ Yield 'Just' the index of the first element matching the predicate
952 -- or 'Nothing' if no such element exists.
953 findIndex :: (a -> Bool) -> Vector a -> Maybe Int
954 {-# INLINE findIndex #-}
955 findIndex = G.findIndex
956
957 -- | /O(n)/ Yield the indices of elements satisfying the predicate in ascending
958 -- order.
959 findIndices :: (a -> Bool) -> Vector a -> Vector Int
960 {-# INLINE findIndices #-}
961 findIndices = G.findIndices
962
963 -- | /O(n)/ Yield 'Just' the index of the first occurence of the given element or
964 -- 'Nothing' if the vector does not contain the element. This is a specialised
965 -- version of 'findIndex'.
966 elemIndex :: Eq a => a -> Vector a -> Maybe Int
967 {-# INLINE elemIndex #-}
968 elemIndex = G.elemIndex
969
970 -- | /O(n)/ Yield the indices of all occurences of the given element in
971 -- ascending order. This is a specialised version of 'findIndices'.
972 elemIndices :: Eq a => a -> Vector a -> Vector Int
973 {-# INLINE elemIndices #-}
974 elemIndices = G.elemIndices
975
976 -- Folding
977 -- -------
978
979 -- | /O(n)/ Left fold
980 foldl :: (a -> b -> a) -> a -> Vector b -> a
981 {-# INLINE foldl #-}
982 foldl = G.foldl
983
984 -- | /O(n)/ Left fold on non-empty vectors
985 foldl1 :: (a -> a -> a) -> Vector a -> a
986 {-# INLINE foldl1 #-}
987 foldl1 = G.foldl1
988
989 -- | /O(n)/ Left fold with strict accumulator
990 foldl' :: (a -> b -> a) -> a -> Vector b -> a
991 {-# INLINE foldl' #-}
992 foldl' = G.foldl'
993
994 -- | /O(n)/ Left fold on non-empty vectors with strict accumulator
995 foldl1' :: (a -> a -> a) -> Vector a -> a
996 {-# INLINE foldl1' #-}
997 foldl1' = G.foldl1'
998
999 -- | /O(n)/ Right fold
1000 foldr :: (a -> b -> b) -> b -> Vector a -> b
1001 {-# INLINE foldr #-}
1002 foldr = G.foldr
1003
1004 -- | /O(n)/ Right fold on non-empty vectors
1005 foldr1 :: (a -> a -> a) -> Vector a -> a
1006 {-# INLINE foldr1 #-}
1007 foldr1 = G.foldr1
1008
1009 -- | /O(n)/ Right fold with a strict accumulator
1010 foldr' :: (a -> b -> b) -> b -> Vector a -> b
1011 {-# INLINE foldr' #-}
1012 foldr' = G.foldr'
1013
1014 -- | /O(n)/ Right fold on non-empty vectors with strict accumulator
1015 foldr1' :: (a -> a -> a) -> Vector a -> a
1016 {-# INLINE foldr1' #-}
1017 foldr1' = G.foldr1'
1018
1019 -- | /O(n)/ Left fold (function applied to each element and its index)
1020 ifoldl :: (a -> Int -> b -> a) -> a -> Vector b -> a
1021 {-# INLINE ifoldl #-}
1022 ifoldl = G.ifoldl
1023
1024 -- | /O(n)/ Left fold with strict accumulator (function applied to each element
1025 -- and its index)
1026 ifoldl' :: (a -> Int -> b -> a) -> a -> Vector b -> a
1027 {-# INLINE ifoldl' #-}
1028 ifoldl' = G.ifoldl'
1029
1030 -- | /O(n)/ Right fold (function applied to each element and its index)
1031 ifoldr :: (Int -> a -> b -> b) -> b -> Vector a -> b
1032 {-# INLINE ifoldr #-}
1033 ifoldr = G.ifoldr
1034
1035 -- | /O(n)/ Right fold with strict accumulator (function applied to each
1036 -- element and its index)
1037 ifoldr' :: (Int -> a -> b -> b) -> b -> Vector a -> b
1038 {-# INLINE ifoldr' #-}
1039 ifoldr' = G.ifoldr'
1040
1041 -- Specialised folds
1042 -- -----------------
1043
1044 -- | /O(n)/ Check if all elements satisfy the predicate.
1045 all :: (a -> Bool) -> Vector a -> Bool
1046 {-# INLINE all #-}
1047 all = G.all
1048
1049 -- | /O(n)/ Check if any element satisfies the predicate.
1050 any :: (a -> Bool) -> Vector a -> Bool
1051 {-# INLINE any #-}
1052 any = G.any
1053
1054 -- | /O(n)/ Check if all elements are 'True'
1055 and :: Vector Bool -> Bool
1056 {-# INLINE and #-}
1057 and = G.and
1058
1059 -- | /O(n)/ Check if any element is 'True'
1060 or :: Vector Bool -> Bool
1061 {-# INLINE or #-}
1062 or = G.or
1063
1064 -- | /O(n)/ Compute the sum of the elements
1065 sum :: Num a => Vector a -> a
1066 {-# INLINE sum #-}
1067 sum = G.sum
1068
1069 -- | /O(n)/ Compute the produce of the elements
1070 product :: Num a => Vector a -> a
1071 {-# INLINE product #-}
1072 product = G.product
1073
1074 -- | /O(n)/ Yield the maximum element of the vector. The vector may not be
1075 -- empty.
1076 maximum :: Ord a => Vector a -> a
1077 {-# INLINE maximum #-}
1078 maximum = G.maximum
1079
1080 -- | /O(n)/ Yield the maximum element of the vector according to the given
1081 -- comparison function. The vector may not be empty.
1082 maximumBy :: (a -> a -> Ordering) -> Vector a -> a
1083 {-# INLINE maximumBy #-}
1084 maximumBy = G.maximumBy
1085
1086 -- | /O(n)/ Yield the minimum element of the vector. The vector may not be
1087 -- empty.
1088 minimum :: Ord a => Vector a -> a
1089 {-# INLINE minimum #-}
1090 minimum = G.minimum
1091
1092 -- | /O(n)/ Yield the minimum element of the vector according to the given
1093 -- comparison function. The vector may not be empty.
1094 minimumBy :: (a -> a -> Ordering) -> Vector a -> a
1095 {-# INLINE minimumBy #-}
1096 minimumBy = G.minimumBy
1097
1098 -- | /O(n)/ Yield the index of the maximum element of the vector. The vector
1099 -- may not be empty.
1100 maxIndex :: Ord a => Vector a -> Int
1101 {-# INLINE maxIndex #-}
1102 maxIndex = G.maxIndex
1103
1104 -- | /O(n)/ Yield the index of the maximum element of the vector according to
1105 -- the given comparison function. The vector may not be empty.
1106 maxIndexBy :: (a -> a -> Ordering) -> Vector a -> Int
1107 {-# INLINE maxIndexBy #-}
1108 maxIndexBy = G.maxIndexBy
1109
1110 -- | /O(n)/ Yield the index of the minimum element of the vector. The vector
1111 -- may not be empty.
1112 minIndex :: Ord a => Vector a -> Int
1113 {-# INLINE minIndex #-}
1114 minIndex = G.minIndex
1115
1116 -- | /O(n)/ Yield the index of the minimum element of the vector according to
1117 -- the given comparison function. The vector may not be empty.
1118 minIndexBy :: (a -> a -> Ordering) -> Vector a -> Int
1119 {-# INLINE minIndexBy #-}
1120 minIndexBy = G.minIndexBy
1121
1122 -- Monadic folds
1123 -- -------------
1124
1125 -- | /O(n)/ Monadic fold
1126 foldM :: Monad m => (a -> b -> m a) -> a -> Vector b -> m a
1127 {-# INLINE foldM #-}
1128 foldM = G.foldM
1129
1130 -- | /O(n)/ Monadic fold over non-empty vectors
1131 fold1M :: Monad m => (a -> a -> m a) -> Vector a -> m a
1132 {-# INLINE fold1M #-}
1133 fold1M = G.fold1M
1134
1135 -- | /O(n)/ Monadic fold with strict accumulator
1136 foldM' :: Monad m => (a -> b -> m a) -> a -> Vector b -> m a
1137 {-# INLINE foldM' #-}
1138 foldM' = G.foldM'
1139
1140 -- | /O(n)/ Monad fold over non-empty vectors with strict accumulator
1141 fold1M' :: Monad m => (a -> a -> m a) -> Vector a -> m a
1142 {-# INLINE fold1M' #-}
1143 fold1M' = G.fold1M'
1144
1145 -- Prefix sums (scans)
1146 -- -------------------
1147
1148 -- | /O(n)/ Prescan
1149 --
1150 -- @
1151 -- prescanl f z = 'init' . 'scanl' f z
1152 -- @
1153 --
1154 -- Example: @prescanl (+) 0 \<1,2,3,4\> = \<0,1,3,6\>@
1155 --
1156 prescanl :: (a -> b -> a) -> a -> Vector b -> Vector a
1157 {-# INLINE prescanl #-}
1158 prescanl = G.prescanl
1159
1160 -- | /O(n)/ Prescan with strict accumulator
1161 prescanl' :: (a -> b -> a) -> a -> Vector b -> Vector a
1162 {-# INLINE prescanl' #-}
1163 prescanl' = G.prescanl'
1164
1165 -- | /O(n)/ Scan
1166 --
1167 -- @
1168 -- postscanl f z = 'tail' . 'scanl' f z
1169 -- @
1170 --
1171 -- Example: @postscanl (+) 0 \<1,2,3,4\> = \<1,3,6,10\>@
1172 --
1173 postscanl :: (a -> b -> a) -> a -> Vector b -> Vector a
1174 {-# INLINE postscanl #-}
1175 postscanl = G.postscanl
1176
1177 -- | /O(n)/ Scan with strict accumulator
1178 postscanl' :: (a -> b -> a) -> a -> Vector b -> Vector a
1179 {-# INLINE postscanl' #-}
1180 postscanl' = G.postscanl'
1181
1182 -- | /O(n)/ Haskell-style scan
1183 --
1184 -- > scanl f z <x1,...,xn> = <y1,...,y(n+1)>
1185 -- > where y1 = z
1186 -- > yi = f y(i-1) x(i-1)
1187 --
1188 -- Example: @scanl (+) 0 \<1,2,3,4\> = \<0,1,3,6,10\>@
1189 --
1190 scanl :: (a -> b -> a) -> a -> Vector b -> Vector a
1191 {-# INLINE scanl #-}
1192 scanl = G.scanl
1193
1194 -- | /O(n)/ Haskell-style scan with strict accumulator
1195 scanl' :: (a -> b -> a) -> a -> Vector b -> Vector a
1196 {-# INLINE scanl' #-}
1197 scanl' = G.scanl'
1198
1199 -- | /O(n)/ Scan over a non-empty vector
1200 --
1201 -- > scanl f <x1,...,xn> = <y1,...,yn>
1202 -- > where y1 = x1
1203 -- > yi = f y(i-1) xi
1204 --
1205 scanl1 :: (a -> a -> a) -> Vector a -> Vector a
1206 {-# INLINE scanl1 #-}
1207 scanl1 = G.scanl1
1208
1209 -- | /O(n)/ Scan over a non-empty vector with a strict accumulator
1210 scanl1' :: (a -> a -> a) -> Vector a -> Vector a
1211 {-# INLINE scanl1' #-}
1212 scanl1' = G.scanl1'
1213
1214 -- | /O(n)/ Right-to-left prescan
1215 --
1216 -- @
1217 -- prescanr f z = 'reverse' . 'prescanl' (flip f) z . 'reverse'
1218 -- @
1219 --
1220 prescanr :: (a -> b -> b) -> b -> Vector a -> Vector b
1221 {-# INLINE prescanr #-}
1222 prescanr = G.prescanr
1223
1224 -- | /O(n)/ Right-to-left prescan with strict accumulator
1225 prescanr' :: (a -> b -> b) -> b -> Vector a -> Vector b
1226 {-# INLINE prescanr' #-}
1227 prescanr' = G.prescanr'
1228
1229 -- | /O(n)/ Right-to-left scan
1230 postscanr :: (a -> b -> b) -> b -> Vector a -> Vector b
1231 {-# INLINE postscanr #-}
1232 postscanr = G.postscanr
1233
1234 -- | /O(n)/ Right-to-left scan with strict accumulator
1235 postscanr' :: (a -> b -> b) -> b -> Vector a -> Vector b
1236 {-# INLINE postscanr' #-}
1237 postscanr' = G.postscanr'
1238
1239 -- | /O(n)/ Right-to-left Haskell-style scan
1240 scanr :: (a -> b -> b) -> b -> Vector a -> Vector b
1241 {-# INLINE scanr #-}
1242 scanr = G.scanr
1243
1244 -- | /O(n)/ Right-to-left Haskell-style scan with strict accumulator
1245 scanr' :: (a -> b -> b) -> b -> Vector a -> Vector b
1246 {-# INLINE scanr' #-}
1247 scanr' = G.scanr'
1248
1249 -- | /O(n)/ Right-to-left scan over a non-empty vector
1250 scanr1 :: (a -> a -> a) -> Vector a -> Vector a
1251 {-# INLINE scanr1 #-}
1252 scanr1 = G.scanr1
1253
1254 -- | /O(n)/ Right-to-left scan over a non-empty vector with a strict
1255 -- accumulator
1256 scanr1' :: (a -> a -> a) -> Vector a -> Vector a
1257 {-# INLINE scanr1' #-}
1258 scanr1' = G.scanr1'
1259
1260 -- Conversions - Lists
1261 -- ------------------------
1262
1263 -- | /O(n)/ Convert a vector to a list
1264 toList :: Vector a -> [a]
1265 {-# INLINE toList #-}
1266 toList = G.toList
1267
1268 -- | /O(n)/ Convert a list to a vector
1269 fromList :: [a] -> Vector a
1270 {-# INLINE fromList #-}
1271 fromList = G.fromList
1272
1273 -- | /O(n)/ Convert the first @n@ elements of a list to a vector
1274 --
1275 -- @
1276 -- fromListN n xs = 'fromList' ('take' n xs)
1277 -- @
1278 fromListN :: Int -> [a] -> Vector a
1279 {-# INLINE fromListN #-}
1280 fromListN = G.fromListN
1281
1282 -- Conversions - Mutable vectors
1283 -- -----------------------------
1284
1285 -- | /O(n)/ Yield a mutable copy of the immutable vector.
1286 thaw :: PrimMonad m => Vector a -> m (MVector (PrimState m) a)
1287 {-# INLINE thaw #-}
1288 thaw = G.thaw
1289
1290 -- | /O(n)/ Yield a mutable vector containing copies of each vector in the
1291 -- list.
1292 thawMany :: PrimMonad m => [Vector a] -> m (MVector (PrimState m) a)
1293 {-# INLINE thawMany #-}
1294 thawMany = G.thawMany
1295
1296 -- | /O(n)/ Copy an immutable vector into a mutable one. The two vectors must
1297 -- have the same length.
1298 unsafeCopy :: PrimMonad m => MVector (PrimState m) a -> Vector a -> m ()
1299 {-# INLINE unsafeCopy #-}
1300 unsafeCopy = G.unsafeCopy
1301
1302 -- | /O(n)/ Copy an immutable vector into a mutable one. The two vectors must
1303 -- have the same length. This is not checked.
1304 copy :: PrimMonad m => MVector (PrimState m) a -> Vector a -> m ()
1305 {-# INLINE copy #-}
1306 copy = G.copy
1307