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