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