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