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