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