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