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