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