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