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