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