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