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