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