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