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