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