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