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