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