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