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