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