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