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