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