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