7f76ebbe95698a0f946813f3fcbb23742858c6ad
[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, 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 replicateM :: (Monad m, Storable a) => Int -> m a -> m (Vector a)
552 {-# INLINE replicateM #-}
553 replicateM = G.replicateM
554
555 -- | Execute the monadic action and freeze the resulting vector.
556 --
557 -- @
558 -- create (do { v \<- new 2; write v 0 \'a\'; write v 1 \'b\' }) = \<'a','b'\>
559 -- @
560 create :: Storable a => (forall s. ST s (MVector s a)) -> Vector a
561 {-# INLINE create #-}
562 -- NOTE: eta-expanded due to http://hackage.haskell.org/trac/ghc/ticket/4120
563 create p = G.create p
564
565 -- Restricting memory usage
566 -- ------------------------
567
568 -- | /O(n)/ Yield the argument but force it not to retain any extra memory,
569 -- possibly by copying it.
570 --
571 -- This is especially useful when dealing with slices. For example:
572 --
573 -- > force (slice 0 2 <huge vector>)
574 --
575 -- Here, the slice retains a reference to the huge vector. Forcing it creates
576 -- a copy of just the elements that belong to the slice and allows the huge
577 -- vector to be garbage collected.
578 force :: Storable a => Vector a -> Vector a
579 {-# INLINE force #-}
580 force = G.force
581
582 -- Bulk updates
583 -- ------------
584
585 -- | /O(m+n)/ For each pair @(i,a)@ from the list, replace the vector
586 -- element at position @i@ by @a@.
587 --
588 -- > <5,9,2,7> // [(2,1),(0,3),(2,8)] = <3,9,8,7>
589 --
590 (//) :: Storable a => Vector a -- ^ initial vector (of length @m@)
591 -> [(Int, a)] -- ^ list of index/value pairs (of length @n@)
592 -> Vector a
593 {-# INLINE (//) #-}
594 (//) = (G.//)
595
596 -- | /O(m+min(n1,n2))/ For each index @i@ from the index vector and the
597 -- corresponding value @a@ from the value vector, replace the element of the
598 -- initial vector at position @i@ by @a@.
599 --
600 -- > update_ <5,9,2,7> <2,0,2> <1,3,8> = <3,9,8,7>
601 --
602 update_ :: Storable a
603 => Vector a -- ^ initial vector (of length @m@)
604 -> Vector Int -- ^ index vector (of length @n1@)
605 -> Vector a -- ^ value vector (of length @n2@)
606 -> Vector a
607 {-# INLINE update_ #-}
608 update_ = G.update_
609
610 -- | Same as ('//') but without bounds checking.
611 unsafeUpd :: Storable a => Vector a -> [(Int, a)] -> Vector a
612 {-# INLINE unsafeUpd #-}
613 unsafeUpd = G.unsafeUpd
614
615 -- | Same as 'update_' but without bounds checking.
616 unsafeUpdate_ :: Storable a => Vector a -> Vector Int -> Vector a -> Vector a
617 {-# INLINE unsafeUpdate_ #-}
618 unsafeUpdate_ = G.unsafeUpdate_
619
620 -- Accumulations
621 -- -------------
622
623 -- | /O(m+n)/ For each pair @(i,b)@ from the list, replace the vector element
624 -- @a@ at position @i@ by @f a b@.
625 --
626 -- > accum (+) <5,9,2> [(2,4),(1,6),(0,3),(1,7)] = <5+3, 9+6+7, 2+4>
627 accum :: Storable a
628 => (a -> b -> a) -- ^ accumulating function @f@
629 -> Vector a -- ^ initial vector (of length @m@)
630 -> [(Int,b)] -- ^ list of index/value pairs (of length @n@)
631 -> Vector a
632 {-# INLINE accum #-}
633 accum = G.accum
634
635 -- | /O(m+min(n1,n2))/ For each index @i@ from the index vector and the
636 -- corresponding value @b@ from the the value vector,
637 -- replace the element of the initial vector at
638 -- position @i@ by @f a b@.
639 --
640 -- > accumulate_ (+) <5,9,2> <2,1,0,1> <4,6,3,7> = <5+3, 9+6+7, 2+4>
641 --
642 accumulate_ :: (Storable a, Storable b)
643 => (a -> b -> a) -- ^ accumulating function @f@
644 -> Vector a -- ^ initial vector (of length @m@)
645 -> Vector Int -- ^ index vector (of length @n1@)
646 -> Vector b -- ^ value vector (of length @n2@)
647 -> Vector a
648 {-# INLINE accumulate_ #-}
649 accumulate_ = G.accumulate_
650
651 -- | Same as 'accum' but without bounds checking.
652 unsafeAccum :: Storable a => (a -> b -> a) -> Vector a -> [(Int,b)] -> Vector a
653 {-# INLINE unsafeAccum #-}
654 unsafeAccum = G.unsafeAccum
655
656 -- | Same as 'accumulate_' but without bounds checking.
657 unsafeAccumulate_ :: (Storable a, Storable b) =>
658 (a -> b -> a) -> Vector a -> Vector Int -> Vector b -> Vector a
659 {-# INLINE unsafeAccumulate_ #-}
660 unsafeAccumulate_ = G.unsafeAccumulate_
661
662 -- Permutations
663 -- ------------
664
665 -- | /O(n)/ Reverse a vector
666 reverse :: Storable a => Vector a -> Vector a
667 {-# INLINE reverse #-}
668 reverse = G.reverse
669
670 -- | /O(n)/ Yield the vector obtained by replacing each element @i@ of the
671 -- index vector by @xs'!'i@. This is equivalent to @'map' (xs'!') is@ but is
672 -- often much more efficient.
673 --
674 -- > backpermute <a,b,c,d> <0,3,2,3,1,0> = <a,d,c,d,b,a>
675 backpermute :: Storable a => Vector a -> Vector Int -> Vector a
676 {-# INLINE backpermute #-}
677 backpermute = G.backpermute
678
679 -- | Same as 'backpermute' but without bounds checking.
680 unsafeBackpermute :: Storable a => Vector a -> Vector Int -> Vector a
681 {-# INLINE unsafeBackpermute #-}
682 unsafeBackpermute = G.unsafeBackpermute
683
684 -- Safe destructive updates
685 -- ------------------------
686
687 -- | Apply a destructive operation to a vector. The operation will be
688 -- performed in place if it is safe to do so and will modify a copy of the
689 -- vector otherwise.
690 --
691 -- @
692 -- modify (\\v -> write v 0 \'x\') ('replicate' 3 \'a\') = \<\'x\',\'a\',\'a\'\>
693 -- @
694 modify :: Storable a => (forall s. MVector s a -> ST s ()) -> Vector a -> Vector a
695 {-# INLINE modify #-}
696 modify p = G.modify p
697
698 -- Mapping
699 -- -------
700
701 -- | /O(n)/ Map a function over a vector
702 map :: (Storable a, Storable b) => (a -> b) -> Vector a -> Vector b
703 {-# INLINE map #-}
704 map = G.map
705
706 -- | /O(n)/ Apply a function to every element of a vector and its index
707 imap :: (Storable a, Storable b) => (Int -> a -> b) -> Vector a -> Vector b
708 {-# INLINE imap #-}
709 imap = G.imap
710
711 -- | Map a function over a vector and concatenate the results.
712 concatMap :: (Storable a, Storable b) => (a -> Vector b) -> Vector a -> Vector b
713 {-# INLINE concatMap #-}
714 concatMap = G.concatMap
715
716 -- Monadic mapping
717 -- ---------------
718
719 -- | /O(n)/ Apply the monadic action to all elements of the vector, yielding a
720 -- vector of results
721 mapM :: (Monad m, Storable a, Storable b) => (a -> m b) -> Vector a -> m (Vector b)
722 {-# INLINE mapM #-}
723 mapM = G.mapM
724
725 -- | /O(n)/ Apply the monadic action to all elements of a vector and ignore the
726 -- results
727 mapM_ :: (Monad m, Storable a) => (a -> m b) -> Vector a -> m ()
728 {-# INLINE mapM_ #-}
729 mapM_ = G.mapM_
730
731 -- | /O(n)/ Apply the monadic action to all elements of the vector, yielding a
732 -- vector of results. Equvalent to @flip 'mapM'@.
733 forM :: (Monad m, Storable a, Storable b) => Vector a -> (a -> m b) -> m (Vector b)
734 {-# INLINE forM #-}
735 forM = G.forM
736
737 -- | /O(n)/ Apply the monadic action to all elements of a vector and ignore the
738 -- results. Equivalent to @flip 'mapM_'@.
739 forM_ :: (Monad m, Storable a) => Vector a -> (a -> m b) -> m ()
740 {-# INLINE forM_ #-}
741 forM_ = G.forM_
742
743 -- Zipping
744 -- -------
745
746 -- | /O(min(m,n))/ Zip two vectors with the given function.
747 zipWith :: (Storable a, Storable b, Storable c)
748 => (a -> b -> c) -> Vector a -> Vector b -> Vector c
749 {-# INLINE zipWith #-}
750 zipWith = G.zipWith
751
752 -- | Zip three vectors with the given function.
753 zipWith3 :: (Storable a, Storable b, Storable c, Storable d)
754 => (a -> b -> c -> d) -> Vector a -> Vector b -> Vector c -> Vector d
755 {-# INLINE zipWith3 #-}
756 zipWith3 = G.zipWith3
757
758 zipWith4 :: (Storable a, Storable b, Storable c, Storable d, Storable e)
759 => (a -> b -> c -> d -> e)
760 -> Vector a -> Vector b -> Vector c -> Vector d -> Vector e
761 {-# INLINE zipWith4 #-}
762 zipWith4 = G.zipWith4
763
764 zipWith5 :: (Storable a, Storable b, Storable c, Storable d, Storable e,
765 Storable f)
766 => (a -> b -> c -> d -> e -> f)
767 -> Vector a -> Vector b -> Vector c -> Vector d -> Vector e
768 -> Vector f
769 {-# INLINE zipWith5 #-}
770 zipWith5 = G.zipWith5
771
772 zipWith6 :: (Storable a, Storable b, Storable c, Storable d, Storable e,
773 Storable f, Storable g)
774 => (a -> b -> c -> d -> e -> f -> g)
775 -> Vector a -> Vector b -> Vector c -> Vector d -> Vector e
776 -> Vector f -> Vector g
777 {-# INLINE zipWith6 #-}
778 zipWith6 = G.zipWith6
779
780 -- | /O(min(m,n))/ Zip two vectors with a function that also takes the
781 -- elements' indices.
782 izipWith :: (Storable a, Storable b, Storable c)
783 => (Int -> a -> b -> c) -> Vector a -> Vector b -> Vector c
784 {-# INLINE izipWith #-}
785 izipWith = G.izipWith
786
787 -- | Zip three vectors and their indices with the given function.
788 izipWith3 :: (Storable a, Storable b, Storable c, Storable d)
789 => (Int -> a -> b -> c -> d)
790 -> Vector a -> Vector b -> Vector c -> Vector d
791 {-# INLINE izipWith3 #-}
792 izipWith3 = G.izipWith3
793
794 izipWith4 :: (Storable a, Storable b, Storable c, Storable d, Storable e)
795 => (Int -> a -> b -> c -> d -> e)
796 -> Vector a -> Vector b -> Vector c -> Vector d -> Vector e
797 {-# INLINE izipWith4 #-}
798 izipWith4 = G.izipWith4
799
800 izipWith5 :: (Storable a, Storable b, Storable c, Storable d, Storable e,
801 Storable f)
802 => (Int -> a -> b -> c -> d -> e -> f)
803 -> Vector a -> Vector b -> Vector c -> Vector d -> Vector e
804 -> Vector f
805 {-# INLINE izipWith5 #-}
806 izipWith5 = G.izipWith5
807
808 izipWith6 :: (Storable a, Storable b, Storable c, Storable d, Storable e,
809 Storable f, Storable g)
810 => (Int -> a -> b -> c -> d -> e -> f -> g)
811 -> Vector a -> Vector b -> Vector c -> Vector d -> Vector e
812 -> Vector f -> Vector g
813 {-# INLINE izipWith6 #-}
814 izipWith6 = G.izipWith6
815
816 -- Monadic zipping
817 -- ---------------
818
819 -- | /O(min(m,n))/ Zip the two vectors with the monadic action and yield a
820 -- vector of results
821 zipWithM :: (Monad m, Storable a, Storable b, Storable c)
822 => (a -> b -> m c) -> Vector a -> Vector b -> m (Vector c)
823 {-# INLINE zipWithM #-}
824 zipWithM = G.zipWithM
825
826 -- | /O(min(m,n))/ Zip the two vectors with the monadic action and ignore the
827 -- results
828 zipWithM_ :: (Monad m, Storable a, Storable b)
829 => (a -> b -> m c) -> Vector a -> Vector b -> m ()
830 {-# INLINE zipWithM_ #-}
831 zipWithM_ = G.zipWithM_
832
833 -- Filtering
834 -- ---------
835
836 -- | /O(n)/ Drop elements that do not satisfy the predicate
837 filter :: Storable a => (a -> Bool) -> Vector a -> Vector a
838 {-# INLINE filter #-}
839 filter = G.filter
840
841 -- | /O(n)/ Drop elements that do not satisfy the predicate which is applied to
842 -- values and their indices
843 ifilter :: Storable a => (Int -> a -> Bool) -> Vector a -> Vector a
844 {-# INLINE ifilter #-}
845 ifilter = G.ifilter
846
847 -- | /O(n)/ Drop elements that do not satisfy the monadic predicate
848 filterM :: (Monad m, Storable a) => (a -> m Bool) -> Vector a -> m (Vector a)
849 {-# INLINE filterM #-}
850 filterM = G.filterM
851
852 -- | /O(n)/ Yield the longest prefix of elements satisfying the predicate
853 -- without copying.
854 takeWhile :: Storable a => (a -> Bool) -> Vector a -> Vector a
855 {-# INLINE takeWhile #-}
856 takeWhile = G.takeWhile
857
858 -- | /O(n)/ Drop the longest prefix of elements that satisfy the predicate
859 -- without copying.
860 dropWhile :: Storable a => (a -> Bool) -> Vector a -> Vector a
861 {-# INLINE dropWhile #-}
862 dropWhile = G.dropWhile
863
864 -- Parititioning
865 -- -------------
866
867 -- | /O(n)/ Split the vector in two parts, the first one containing those
868 -- elements that satisfy the predicate and the second one those that don't. The
869 -- relative order of the elements is preserved at the cost of a sometimes
870 -- reduced performance compared to 'unstablePartition'.
871 partition :: Storable a => (a -> Bool) -> Vector a -> (Vector a, Vector a)
872 {-# INLINE partition #-}
873 partition = G.partition
874
875 -- | /O(n)/ Split the vector in two parts, the first one containing those
876 -- elements that satisfy the predicate and the second one those that don't.
877 -- The order of the elements is not preserved but the operation is often
878 -- faster than 'partition'.
879 unstablePartition :: Storable a => (a -> Bool) -> Vector a -> (Vector a, Vector a)
880 {-# INLINE unstablePartition #-}
881 unstablePartition = G.unstablePartition
882
883 -- | /O(n)/ Split the vector into the longest prefix of elements that satisfy
884 -- the predicate and the rest without copying.
885 span :: Storable a => (a -> Bool) -> Vector a -> (Vector a, Vector a)
886 {-# INLINE span #-}
887 span = G.span
888
889 -- | /O(n)/ Split the vector into the longest prefix of elements that do not
890 -- satisfy the predicate and the rest without copying.
891 break :: Storable a => (a -> Bool) -> Vector a -> (Vector a, Vector a)
892 {-# INLINE break #-}
893 break = G.break
894
895 -- Searching
896 -- ---------
897
898 infix 4 `elem`
899 -- | /O(n)/ Check if the vector contains an element
900 elem :: (Storable a, Eq a) => a -> Vector a -> Bool
901 {-# INLINE elem #-}
902 elem = G.elem
903
904 infix 4 `notElem`
905 -- | /O(n)/ Check if the vector does not contain an element (inverse of 'elem')
906 notElem :: (Storable a, Eq a) => a -> Vector a -> Bool
907 {-# INLINE notElem #-}
908 notElem = G.notElem
909
910 -- | /O(n)/ Yield 'Just' the first element matching the predicate or 'Nothing'
911 -- if no such element exists.
912 find :: Storable a => (a -> Bool) -> Vector a -> Maybe a
913 {-# INLINE find #-}
914 find = G.find
915
916 -- | /O(n)/ Yield 'Just' the index of the first element matching the predicate
917 -- or 'Nothing' if no such element exists.
918 findIndex :: Storable a => (a -> Bool) -> Vector a -> Maybe Int
919 {-# INLINE findIndex #-}
920 findIndex = G.findIndex
921
922 -- | /O(n)/ Yield the indices of elements satisfying the predicate in ascending
923 -- order.
924 findIndices :: Storable a => (a -> Bool) -> Vector a -> Vector Int
925 {-# INLINE findIndices #-}
926 findIndices = G.findIndices
927
928 -- | /O(n)/ Yield 'Just' the index of the first occurence of the given element or
929 -- 'Nothing' if the vector does not contain the element. This is a specialised
930 -- version of 'findIndex'.
931 elemIndex :: (Storable a, Eq a) => a -> Vector a -> Maybe Int
932 {-# INLINE elemIndex #-}
933 elemIndex = G.elemIndex
934
935 -- | /O(n)/ Yield the indices of all occurences of the given element in
936 -- ascending order. This is a specialised version of 'findIndices'.
937 elemIndices :: (Storable a, Eq a) => a -> Vector a -> Vector Int
938 {-# INLINE elemIndices #-}
939 elemIndices = G.elemIndices
940
941 -- Folding
942 -- -------
943
944 -- | /O(n)/ Left fold
945 foldl :: Storable b => (a -> b -> a) -> a -> Vector b -> a
946 {-# INLINE foldl #-}
947 foldl = G.foldl
948
949 -- | /O(n)/ Left fold on non-empty vectors
950 foldl1 :: Storable a => (a -> a -> a) -> Vector a -> a
951 {-# INLINE foldl1 #-}
952 foldl1 = G.foldl1
953
954 -- | /O(n)/ Left fold with strict accumulator
955 foldl' :: Storable b => (a -> b -> a) -> a -> Vector b -> a
956 {-# INLINE foldl' #-}
957 foldl' = G.foldl'
958
959 -- | /O(n)/ Left fold on non-empty vectors with strict accumulator
960 foldl1' :: Storable a => (a -> a -> a) -> Vector a -> a
961 {-# INLINE foldl1' #-}
962 foldl1' = G.foldl1'
963
964 -- | /O(n)/ Right fold
965 foldr :: Storable a => (a -> b -> b) -> b -> Vector a -> b
966 {-# INLINE foldr #-}
967 foldr = G.foldr
968
969 -- | /O(n)/ Right fold on non-empty vectors
970 foldr1 :: Storable a => (a -> a -> a) -> Vector a -> a
971 {-# INLINE foldr1 #-}
972 foldr1 = G.foldr1
973
974 -- | /O(n)/ Right fold with a strict accumulator
975 foldr' :: Storable a => (a -> b -> b) -> b -> Vector a -> b
976 {-# INLINE foldr' #-}
977 foldr' = G.foldr'
978
979 -- | /O(n)/ Right fold on non-empty vectors with strict accumulator
980 foldr1' :: Storable a => (a -> a -> a) -> Vector a -> a
981 {-# INLINE foldr1' #-}
982 foldr1' = G.foldr1'
983
984 -- | /O(n)/ Left fold (function applied to each element and its index)
985 ifoldl :: Storable b => (a -> Int -> b -> a) -> a -> Vector b -> a
986 {-# INLINE ifoldl #-}
987 ifoldl = G.ifoldl
988
989 -- | /O(n)/ Left fold with strict accumulator (function applied to each element
990 -- and its index)
991 ifoldl' :: Storable b => (a -> Int -> b -> a) -> a -> Vector b -> a
992 {-# INLINE ifoldl' #-}
993 ifoldl' = G.ifoldl'
994
995 -- | /O(n)/ Right fold (function applied to each element and its index)
996 ifoldr :: Storable a => (Int -> a -> b -> b) -> b -> Vector a -> b
997 {-# INLINE ifoldr #-}
998 ifoldr = G.ifoldr
999
1000 -- | /O(n)/ Right fold with strict accumulator (function applied to each
1001 -- element and its index)
1002 ifoldr' :: Storable a => (Int -> a -> b -> b) -> b -> Vector a -> b
1003 {-# INLINE ifoldr' #-}
1004 ifoldr' = G.ifoldr'
1005
1006 -- Specialised folds
1007 -- -----------------
1008
1009 -- | /O(n)/ Check if all elements satisfy the predicate.
1010 all :: Storable a => (a -> Bool) -> Vector a -> Bool
1011 {-# INLINE all #-}
1012 all = G.all
1013
1014 -- | /O(n)/ Check if any element satisfies the predicate.
1015 any :: Storable a => (a -> Bool) -> Vector a -> Bool
1016 {-# INLINE any #-}
1017 any = G.any
1018
1019 -- | /O(n)/ Check if all elements are 'True'
1020 and :: Vector Bool -> Bool
1021 {-# INLINE and #-}
1022 and = G.and
1023
1024 -- | /O(n)/ Check if any element is 'True'
1025 or :: Vector Bool -> Bool
1026 {-# INLINE or #-}
1027 or = G.or
1028
1029 -- | /O(n)/ Compute the sum of the elements
1030 sum :: (Storable a, Num a) => Vector a -> a
1031 {-# INLINE sum #-}
1032 sum = G.sum
1033
1034 -- | /O(n)/ Compute the produce of the elements
1035 product :: (Storable a, Num a) => Vector a -> a
1036 {-# INLINE product #-}
1037 product = G.product
1038
1039 -- | /O(n)/ Yield the maximum element of the vector. The vector may not be
1040 -- empty.
1041 maximum :: (Storable a, Ord a) => Vector a -> a
1042 {-# INLINE maximum #-}
1043 maximum = G.maximum
1044
1045 -- | /O(n)/ Yield the maximum element of the vector according to the given
1046 -- comparison function. The vector may not be empty.
1047 maximumBy :: Storable a => (a -> a -> Ordering) -> Vector a -> a
1048 {-# INLINE maximumBy #-}
1049 maximumBy = G.maximumBy
1050
1051 -- | /O(n)/ Yield the minimum element of the vector. The vector may not be
1052 -- empty.
1053 minimum :: (Storable a, Ord a) => Vector a -> a
1054 {-# INLINE minimum #-}
1055 minimum = G.minimum
1056
1057 -- | /O(n)/ Yield the minimum element of the vector according to the given
1058 -- comparison function. The vector may not be empty.
1059 minimumBy :: Storable a => (a -> a -> Ordering) -> Vector a -> a
1060 {-# INLINE minimumBy #-}
1061 minimumBy = G.minimumBy
1062
1063 -- | /O(n)/ Yield the index of the maximum element of the vector. The vector
1064 -- may not be empty.
1065 maxIndex :: (Storable a, Ord a) => Vector a -> Int
1066 {-# INLINE maxIndex #-}
1067 maxIndex = G.maxIndex
1068
1069 -- | /O(n)/ Yield the index of the maximum element of the vector according to
1070 -- the given comparison function. The vector may not be empty.
1071 maxIndexBy :: Storable a => (a -> a -> Ordering) -> Vector a -> Int
1072 {-# INLINE maxIndexBy #-}
1073 maxIndexBy = G.maxIndexBy
1074
1075 -- | /O(n)/ Yield the index of the minimum element of the vector. The vector
1076 -- may not be empty.
1077 minIndex :: (Storable a, Ord a) => Vector a -> Int
1078 {-# INLINE minIndex #-}
1079 minIndex = G.minIndex
1080
1081 -- | /O(n)/ Yield the index of the minimum element of the vector according to
1082 -- the given comparison function. The vector may not be empty.
1083 minIndexBy :: Storable a => (a -> a -> Ordering) -> Vector a -> Int
1084 {-# INLINE minIndexBy #-}
1085 minIndexBy = G.minIndexBy
1086
1087 -- Monadic folds
1088 -- -------------
1089
1090 -- | /O(n)/ Monadic fold
1091 foldM :: (Monad m, Storable b) => (a -> b -> m a) -> a -> Vector b -> m a
1092 {-# INLINE foldM #-}
1093 foldM = G.foldM
1094
1095 -- | /O(n)/ Monadic fold over non-empty vectors
1096 fold1M :: (Monad m, Storable a) => (a -> a -> m a) -> Vector a -> m a
1097 {-# INLINE fold1M #-}
1098 fold1M = G.fold1M
1099
1100 -- | /O(n)/ Monadic fold with strict accumulator
1101 foldM' :: (Monad m, Storable b) => (a -> b -> m a) -> a -> Vector b -> m a
1102 {-# INLINE foldM' #-}
1103 foldM' = G.foldM'
1104
1105 -- | /O(n)/ Monadic fold over non-empty vectors with strict accumulator
1106 fold1M' :: (Monad m, Storable a) => (a -> a -> m a) -> Vector a -> m a
1107 {-# INLINE fold1M' #-}
1108 fold1M' = G.fold1M'
1109
1110 -- Prefix sums (scans)
1111 -- -------------------
1112
1113 -- | /O(n)/ Prescan
1114 --
1115 -- @
1116 -- prescanl f z = 'init' . 'scanl' f z
1117 -- @
1118 --
1119 -- Example: @prescanl (+) 0 \<1,2,3,4\> = \<0,1,3,6\>@
1120 --
1121 prescanl :: (Storable a, Storable b) => (a -> b -> a) -> a -> Vector b -> Vector a
1122 {-# INLINE prescanl #-}
1123 prescanl = G.prescanl
1124
1125 -- | /O(n)/ Prescan with strict accumulator
1126 prescanl' :: (Storable a, Storable b) => (a -> b -> a) -> a -> Vector b -> Vector a
1127 {-# INLINE prescanl' #-}
1128 prescanl' = G.prescanl'
1129
1130 -- | /O(n)/ Scan
1131 --
1132 -- @
1133 -- postscanl f z = 'tail' . 'scanl' f z
1134 -- @
1135 --
1136 -- Example: @postscanl (+) 0 \<1,2,3,4\> = \<1,3,6,10\>@
1137 --
1138 postscanl :: (Storable a, Storable b) => (a -> b -> a) -> a -> Vector b -> Vector a
1139 {-# INLINE postscanl #-}
1140 postscanl = G.postscanl
1141
1142 -- | /O(n)/ Scan with strict accumulator
1143 postscanl' :: (Storable a, Storable b) => (a -> b -> a) -> a -> Vector b -> Vector a
1144 {-# INLINE postscanl' #-}
1145 postscanl' = G.postscanl'
1146
1147 -- | /O(n)/ Haskell-style scan
1148 --
1149 -- > scanl f z <x1,...,xn> = <y1,...,y(n+1)>
1150 -- > where y1 = z
1151 -- > yi = f y(i-1) x(i-1)
1152 --
1153 -- Example: @scanl (+) 0 \<1,2,3,4\> = \<0,1,3,6,10\>@
1154 --
1155 scanl :: (Storable a, Storable b) => (a -> b -> a) -> a -> Vector b -> Vector a
1156 {-# INLINE scanl #-}
1157 scanl = G.scanl
1158
1159 -- | /O(n)/ Haskell-style scan with strict accumulator
1160 scanl' :: (Storable a, Storable b) => (a -> b -> a) -> a -> Vector b -> Vector a
1161 {-# INLINE scanl' #-}
1162 scanl' = G.scanl'
1163
1164 -- | /O(n)/ Scan over a non-empty vector
1165 --
1166 -- > scanl f <x1,...,xn> = <y1,...,yn>
1167 -- > where y1 = x1
1168 -- > yi = f y(i-1) xi
1169 --
1170 scanl1 :: Storable a => (a -> a -> a) -> Vector a -> Vector a
1171 {-# INLINE scanl1 #-}
1172 scanl1 = G.scanl1
1173
1174 -- | /O(n)/ Scan over a non-empty vector with a strict accumulator
1175 scanl1' :: Storable a => (a -> a -> a) -> Vector a -> Vector a
1176 {-# INLINE scanl1' #-}
1177 scanl1' = G.scanl1'
1178
1179 -- | /O(n)/ Right-to-left prescan
1180 --
1181 -- @
1182 -- prescanr f z = 'reverse' . 'prescanl' (flip f) z . 'reverse'
1183 -- @
1184 --
1185 prescanr :: (Storable a, Storable b) => (a -> b -> b) -> b -> Vector a -> Vector b
1186 {-# INLINE prescanr #-}
1187 prescanr = G.prescanr
1188
1189 -- | /O(n)/ Right-to-left prescan with strict accumulator
1190 prescanr' :: (Storable a, Storable b) => (a -> b -> b) -> b -> Vector a -> Vector b
1191 {-# INLINE prescanr' #-}
1192 prescanr' = G.prescanr'
1193
1194 -- | /O(n)/ Right-to-left scan
1195 postscanr :: (Storable a, Storable b) => (a -> b -> b) -> b -> Vector a -> Vector b
1196 {-# INLINE postscanr #-}
1197 postscanr = G.postscanr
1198
1199 -- | /O(n)/ Right-to-left scan with strict accumulator
1200 postscanr' :: (Storable a, Storable b) => (a -> b -> b) -> b -> Vector a -> Vector b
1201 {-# INLINE postscanr' #-}
1202 postscanr' = G.postscanr'
1203
1204 -- | /O(n)/ Right-to-left Haskell-style scan
1205 scanr :: (Storable a, Storable b) => (a -> b -> b) -> b -> Vector a -> Vector b
1206 {-# INLINE scanr #-}
1207 scanr = G.scanr
1208
1209 -- | /O(n)/ Right-to-left Haskell-style scan with strict accumulator
1210 scanr' :: (Storable a, Storable b) => (a -> b -> b) -> b -> Vector a -> Vector b
1211 {-# INLINE scanr' #-}
1212 scanr' = G.scanr'
1213
1214 -- | /O(n)/ Right-to-left scan over a non-empty vector
1215 scanr1 :: Storable a => (a -> a -> a) -> Vector a -> Vector a
1216 {-# INLINE scanr1 #-}
1217 scanr1 = G.scanr1
1218
1219 -- | /O(n)/ Right-to-left scan over a non-empty vector with a strict
1220 -- accumulator
1221 scanr1' :: Storable a => (a -> a -> a) -> Vector a -> Vector a
1222 {-# INLINE scanr1' #-}
1223 scanr1' = G.scanr1'
1224
1225 -- Conversions - Lists
1226 -- ------------------------
1227
1228 -- | /O(n)/ Convert a vector to a list
1229 toList :: Storable a => Vector a -> [a]
1230 {-# INLINE toList #-}
1231 toList = G.toList
1232
1233 -- | /O(n)/ Convert a list to a vector
1234 fromList :: Storable a => [a] -> Vector a
1235 {-# INLINE fromList #-}
1236 fromList = G.fromList
1237
1238 -- | /O(n)/ Convert the first @n@ elements of a list to a vector
1239 --
1240 -- @
1241 -- fromListN n xs = 'fromList' ('take' n xs)
1242 -- @
1243 fromListN :: Storable a => Int -> [a] -> Vector a
1244 {-# INLINE fromListN #-}
1245 fromListN = G.fromListN
1246
1247 -- Conversions - Mutable vectors
1248 -- -----------------------------
1249
1250 -- | /O(1)/ Unsafe convert a mutable vector to an immutable one without
1251 -- copying. The mutable vector may not be used after this operation.
1252 unsafeFreeze
1253 :: (Storable 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
1260 :: (Storable a, PrimMonad m) => Vector a -> m (MVector (PrimState m) a)
1261 {-# INLINE unsafeThaw #-}
1262 unsafeThaw = G.unsafeThaw
1263
1264 -- | /O(n)/ Yield a mutable copy of the immutable vector.
1265 thaw :: (Storable a, PrimMonad m) => Vector a -> m (MVector (PrimState m) a)
1266 {-# INLINE thaw #-}
1267 thaw = G.thaw
1268
1269 -- | /O(n)/ Yield an immutable copy of the mutable vector.
1270 freeze :: (Storable a, PrimMonad m) => MVector (PrimState m) a -> m (Vector a)
1271 {-# INLINE freeze #-}
1272 freeze = G.freeze
1273
1274 -- | /O(n)/ Copy an immutable vector into a mutable one. The two vectors must
1275 -- have the same length. This is not checked.
1276 unsafeCopy
1277 :: (Storable a, PrimMonad m) => MVector (PrimState m) a -> Vector a -> m ()
1278 {-# INLINE unsafeCopy #-}
1279 unsafeCopy = G.unsafeCopy
1280
1281 -- | /O(n)/ Copy an immutable vector into a mutable one. The two vectors must
1282 -- have the same length.
1283 copy :: (Storable a, PrimMonad m) => MVector (PrimState m) a -> Vector a -> m ()
1284 {-# INLINE copy #-}
1285 copy = G.copy
1286
1287 -- Conversions - Raw pointers
1288 -- --------------------------
1289
1290 -- | /O(1)/ Create a vector from a 'ForeignPtr' with an offset and a length.
1291 -- The data may not be modified through the 'ForeignPtr' afterwards.
1292 unsafeFromForeignPtr :: Storable a
1293 => ForeignPtr a -- ^ pointer
1294 -> Int -- ^ offset
1295 -> Int -- ^ length
1296 -> Vector a
1297 {-# INLINE unsafeFromForeignPtr #-}
1298 unsafeFromForeignPtr fp i n = Vector (offsetToPtr fp i) n fp
1299
1300 -- | /O(1)/ Yield the underlying 'ForeignPtr' together with the offset to the
1301 -- data and its length. The data may not be modified through the 'ForeignPtr'.
1302 unsafeToForeignPtr :: Storable a => Vector a -> (ForeignPtr a, Int, Int)
1303 {-# INLINE unsafeToForeignPtr #-}
1304 unsafeToForeignPtr (Vector p n fp) = (fp, ptrToOffset fp p, n)
1305
1306 -- | Pass a pointer to the vector's data to the IO action. The data may not be
1307 -- modified through the 'Ptr.
1308 unsafeWith :: Storable a => Vector a -> (Ptr a -> IO b) -> IO b
1309 {-# INLINE unsafeWith #-}
1310 unsafeWith (Vector p n fp) m = withForeignPtr fp $ \_ -> m p
1311
1312