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