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