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