Resolve conflict
[darcs-mirrors/vector.git] / Data / Vector / Generic.hs
1 {-# LANGUAGE Rank2Types, MultiParamTypeClasses, FlexibleContexts,
2 TypeFamilies, ScopedTypeVariables, BangPatterns #-}
3 -- |
4 -- Module : Data.Vector.Generic
5 -- Copyright : (c) Roman Leshchinskiy 2008-2010
6 -- License : BSD-style
7 --
8 -- Maintainer : Roman Leshchinskiy <rl@cse.unsw.edu.au>
9 -- Stability : experimental
10 -- Portability : non-portable
11 --
12 -- Generic interface to pure vectors.
13 --
14
15 module Data.Vector.Generic (
16 -- * Immutable vectors
17 Vector(..), Mutable,
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, update_,
61 unsafeUpd, unsafeUpdate, unsafeUpdate_,
62
63 -- ** Accumulations
64 accum, accumulate, accumulate_,
65 unsafeAccum, unsafeAccumulate, unsafeAccumulate_,
66
67 -- ** Permutations
68 reverse, backpermute, unsafeBackpermute,
69
70 -- ** Safe destructive updates
71 modify,
72
73 -- * Elementwise operations
74
75 -- ** Indexing
76 indexed,
77
78 -- ** Mapping
79 map, imap, concatMap,
80
81 -- ** Monadic mapping
82 mapM, mapM_, forM, forM_,
83
84 -- ** Zipping
85 zipWith, zipWith3, zipWith4, zipWith5, zipWith6,
86 izipWith, izipWith3, izipWith4, izipWith5, izipWith6,
87 zip, zip3, zip4, zip5, zip6,
88
89 -- ** Monadic zipping
90 zipWithM, zipWithM_,
91
92 -- ** Unzipping
93 unzip, unzip3, unzip4, unzip5, unzip6,
94
95 -- * Working with predicates
96
97 -- ** Filtering
98 filter, ifilter, filterM,
99 takeWhile, dropWhile,
100
101 -- ** Partitioning
102 partition, unstablePartition, span, break,
103
104 -- ** Searching
105 elem, notElem, find, findIndex, findIndices, elemIndex, elemIndices,
106
107 -- * Folding
108 foldl, foldl1, foldl', foldl1', foldr, foldr1, foldr', foldr1',
109 ifoldl, ifoldl', ifoldr, ifoldr',
110
111 -- ** Specialised folds
112 all, any, and, or,
113 sum, product,
114 maximum, maximumBy, minimum, minimumBy,
115 minIndex, minIndexBy, maxIndex, maxIndexBy,
116
117 -- ** Monadic folds
118 foldM, foldM', fold1M, fold1M',
119 foldM_, foldM'_, fold1M_, fold1M'_,
120
121 -- ** Monadic sequencing
122 sequence, sequence_,
123
124 -- * Prefix sums (scans)
125 prescanl, prescanl',
126 postscanl, postscanl',
127 scanl, scanl', scanl1, scanl1',
128 prescanr, prescanr',
129 postscanr, postscanr',
130 scanr, scanr', scanr1, scanr1',
131
132 -- * Conversions
133
134 -- ** Lists
135 toList, fromList, fromListN,
136
137 -- ** Different vector types
138 convert,
139
140 -- ** Mutable vectors
141 freeze, thaw, copy, unsafeFreeze, unsafeThaw, unsafeCopy,
142
143 -- * Fusion support
144
145 -- ** Conversion to/from Bundles
146 stream, unstream, streamR, unstreamR,
147
148 -- ** Recycling support
149 new, clone,
150
151 -- * Utilities
152
153 -- ** Comparisons
154 eq, cmp,
155
156 -- ** Show and Read
157 showsPrec, readPrec,
158
159 -- ** @Data@ and @Typeable@
160 gfoldl, dataCast, mkType
161 ) where
162
163 import Data.Vector.Generic.Base
164
165 import Data.Vector.Generic.Mutable ( MVector )
166 import qualified Data.Vector.Generic.Mutable as M
167
168 import qualified Data.Vector.Generic.New as New
169 import Data.Vector.Generic.New ( New )
170
171 import qualified Data.Vector.Fusion.Bundle as Bundle
172 import Data.Vector.Fusion.Bundle ( Bundle, MBundle, Step(..), lift, inplace )
173 import qualified Data.Vector.Fusion.Bundle.Monadic as MBundle
174 import Data.Vector.Fusion.Stream.Monadic ( Stream )
175 import qualified Data.Vector.Fusion.Stream.Monadic as S
176 import Data.Vector.Fusion.Bundle.Size
177 import Data.Vector.Fusion.Util
178
179 import Control.Monad.ST ( ST, runST )
180 import Control.Monad.Primitive
181 import qualified Control.Monad as Monad
182 import qualified Data.List as List
183 import Prelude hiding ( length, null,
184 replicate, (++), concat,
185 head, last,
186 init, tail, take, drop, splitAt, reverse,
187 map, concat, concatMap,
188 zipWith, zipWith3, zip, zip3, unzip, unzip3,
189 filter, takeWhile, dropWhile, span, break,
190 elem, notElem,
191 foldl, foldl1, foldr, foldr1,
192 all, any, and, or, sum, product, maximum, minimum,
193 scanl, scanl1, scanr, scanr1,
194 enumFromTo, enumFromThenTo,
195 mapM, mapM_, sequence, sequence_,
196 showsPrec )
197
198 import qualified Text.Read as Read
199 import Data.Typeable ( Typeable1, gcast1 )
200
201 #include "vector.h"
202
203 import Data.Data ( Data, DataType )
204 #if MIN_VERSION_base(4,2,0)
205 import Data.Data ( mkNoRepType )
206 #else
207 import Data.Data ( mkNorepType )
208 mkNoRepType :: String -> DataType
209 mkNoRepType = mkNorepType
210 #endif
211
212 -- Length information
213 -- ------------------
214
215 -- | /O(1)/ Yield the length of the vector.
216 length :: Vector v a => v a -> Int
217 {-# INLINE length #-}
218 length = Bundle.length . stream
219
220 -- | /O(1)/ Test whether a vector if empty
221 null :: Vector v a => v a -> Bool
222 {-# INLINE null #-}
223 null = Bundle.null . stream
224
225 -- Indexing
226 -- --------
227
228 infixl 9 !
229 -- | O(1) Indexing
230 (!) :: Vector v a => v a -> Int -> a
231 {-# INLINE_FUSED (!) #-}
232 (!) v i = BOUNDS_CHECK(checkIndex) "(!)" i (length v)
233 $ unId (basicUnsafeIndexM v i)
234
235 infixl 9 !?
236 -- | O(1) Safe indexing
237 (!?) :: Vector v a => v a -> Int -> Maybe a
238 {-# INLINE_FUSED (!?) #-}
239 v !? i | i < 0 || i >= length v = Nothing
240 | otherwise = Just $ unsafeIndex v i
241
242 -- | /O(1)/ First element
243 head :: Vector v a => v a -> a
244 {-# INLINE_FUSED head #-}
245 head v = v ! 0
246
247 -- | /O(1)/ Last element
248 last :: Vector v a => v a -> a
249 {-# INLINE_FUSED last #-}
250 last v = v ! (length v - 1)
251
252 -- | /O(1)/ Unsafe indexing without bounds checking
253 unsafeIndex :: Vector v a => v a -> Int -> a
254 {-# INLINE_FUSED unsafeIndex #-}
255 unsafeIndex v i = UNSAFE_CHECK(checkIndex) "unsafeIndex" i (length v)
256 $ unId (basicUnsafeIndexM v i)
257
258 -- | /O(1)/ First element without checking if the vector is empty
259 unsafeHead :: Vector v a => v a -> a
260 {-# INLINE_FUSED unsafeHead #-}
261 unsafeHead v = unsafeIndex v 0
262
263 -- | /O(1)/ Last element without checking if the vector is empty
264 unsafeLast :: Vector v a => v a -> a
265 {-# INLINE_FUSED unsafeLast #-}
266 unsafeLast v = unsafeIndex v (length v - 1)
267
268 {-# RULES
269
270 "(!)/unstream [Vector]" forall i s.
271 new (New.unstream s) ! i = s Bundle.!! i
272
273 "(!?)/unstream [Vector]" forall i s.
274 new (New.unstream s) !? i = s Bundle.!? i
275
276 "head/unstream [Vector]" forall s.
277 head (new (New.unstream s)) = Bundle.head s
278
279 "last/unstream [Vector]" forall s.
280 last (new (New.unstream s)) = Bundle.last s
281
282 "unsafeIndex/unstream [Vector]" forall i s.
283 unsafeIndex (new (New.unstream s)) i = s Bundle.!! i
284
285 "unsafeHead/unstream [Vector]" forall s.
286 unsafeHead (new (New.unstream s)) = Bundle.head s
287
288 "unsafeLast/unstream [Vector]" forall s.
289 unsafeLast (new (New.unstream s)) = Bundle.last s
290
291 #-}
292
293 -- Monadic indexing
294 -- ----------------
295
296 -- | /O(1)/ Indexing in a monad.
297 --
298 -- The monad allows operations to be strict in the vector when necessary.
299 -- Suppose vector copying is implemented like this:
300 --
301 -- > copy mv v = ... write mv i (v ! i) ...
302 --
303 -- For lazy vectors, @v ! i@ would not be evaluated which means that @mv@
304 -- would unnecessarily retain a reference to @v@ in each element written.
305 --
306 -- With 'indexM', copying can be implemented like this instead:
307 --
308 -- > copy mv v = ... do
309 -- > x <- indexM v i
310 -- > write mv i x
311 --
312 -- Here, no references to @v@ are retained because indexing (but /not/ the
313 -- elements) is evaluated eagerly.
314 --
315 indexM :: (Vector v a, Monad m) => v a -> Int -> m a
316 {-# INLINE_FUSED indexM #-}
317 indexM v i = BOUNDS_CHECK(checkIndex) "indexM" i (length v)
318 $ basicUnsafeIndexM v i
319
320 -- | /O(1)/ First element of a vector in a monad. See 'indexM' for an
321 -- explanation of why this is useful.
322 headM :: (Vector v a, Monad m) => v a -> m a
323 {-# INLINE_FUSED headM #-}
324 headM v = indexM v 0
325
326 -- | /O(1)/ Last element of a vector in a monad. See 'indexM' for an
327 -- explanation of why this is useful.
328 lastM :: (Vector v a, Monad m) => v a -> m a
329 {-# INLINE_FUSED lastM #-}
330 lastM v = indexM v (length v - 1)
331
332 -- | /O(1)/ Indexing in a monad without bounds checks. See 'indexM' for an
333 -- explanation of why this is useful.
334 unsafeIndexM :: (Vector v a, Monad m) => v a -> Int -> m a
335 {-# INLINE_FUSED unsafeIndexM #-}
336 unsafeIndexM v i = UNSAFE_CHECK(checkIndex) "unsafeIndexM" i (length v)
337 $ basicUnsafeIndexM v i
338
339 -- | /O(1)/ First element in a monad without checking for empty vectors.
340 -- See 'indexM' for an explanation of why this is useful.
341 unsafeHeadM :: (Vector v a, Monad m) => v a -> m a
342 {-# INLINE_FUSED unsafeHeadM #-}
343 unsafeHeadM v = unsafeIndexM v 0
344
345 -- | /O(1)/ Last element in a monad without checking for empty vectors.
346 -- See 'indexM' for an explanation of why this is useful.
347 unsafeLastM :: (Vector v a, Monad m) => v a -> m a
348 {-# INLINE_FUSED unsafeLastM #-}
349 unsafeLastM v = unsafeIndexM v (length v - 1)
350
351 {-# RULES
352
353 "indexM/unstream [Vector]" forall s i.
354 indexM (new (New.unstream s)) i = lift s MBundle.!! i
355
356 "headM/unstream [Vector]" forall s.
357 headM (new (New.unstream s)) = MBundle.head (lift s)
358
359 "lastM/unstream [Vector]" forall s.
360 lastM (new (New.unstream s)) = MBundle.last (lift s)
361
362 "unsafeIndexM/unstream [Vector]" forall s i.
363 unsafeIndexM (new (New.unstream s)) i = lift s MBundle.!! i
364
365 "unsafeHeadM/unstream [Vector]" forall s.
366 unsafeHeadM (new (New.unstream s)) = MBundle.head (lift s)
367
368 "unsafeLastM/unstream [Vector]" forall s.
369 unsafeLastM (new (New.unstream s)) = MBundle.last (lift s)
370
371 #-}
372
373 -- Extracting subvectors (slicing)
374 -- -------------------------------
375
376 -- | /O(1)/ Yield a slice of the vector without copying it. The vector must
377 -- contain at least @i+n@ elements.
378 slice :: Vector v a => Int -- ^ @i@ starting index
379 -> Int -- ^ @n@ length
380 -> v a
381 -> v a
382 {-# INLINE_FUSED slice #-}
383 slice i n v = BOUNDS_CHECK(checkSlice) "slice" i n (length v)
384 $ basicUnsafeSlice i n v
385
386 -- | /O(1)/ Yield all but the last element without copying. The vector may not
387 -- be empty.
388 init :: Vector v a => v a -> v a
389 {-# INLINE_FUSED init #-}
390 init v = slice 0 (length v - 1) v
391
392 -- | /O(1)/ Yield all but the first element without copying. The vector may not
393 -- be empty.
394 tail :: Vector v a => v a -> v a
395 {-# INLINE_FUSED tail #-}
396 tail v = slice 1 (length v - 1) v
397
398 -- | /O(1)/ Yield the first @n@ elements without copying. The vector may
399 -- contain less than @n@ elements in which case it is returned unchanged.
400 take :: Vector v a => Int -> v a -> v a
401 {-# INLINE_FUSED take #-}
402 take n v = unsafeSlice 0 (delay_inline min n' (length v)) v
403 where n' = max n 0
404
405 -- | /O(1)/ Yield all but the first @n@ elements without copying. The vector may
406 -- contain less than @n@ elements in which case an empty vector is returned.
407 drop :: Vector v a => Int -> v a -> v a
408 {-# INLINE_FUSED drop #-}
409 drop n v = unsafeSlice (delay_inline min n' len)
410 (delay_inline max 0 (len - n')) v
411 where n' = max n 0
412 len = length v
413
414 -- | /O(1)/ Yield the first @n@ elements paired with the remainder without copying.
415 --
416 -- Note that @'splitAt' n v@ is equivalent to @('take' n v, 'drop' n v)@
417 -- but slightly more efficient.
418 {-# INLINE_FUSED splitAt #-}
419 splitAt :: Vector v a => Int -> v a -> (v a, v a)
420 splitAt n v = ( unsafeSlice 0 m v
421 , unsafeSlice m (delay_inline max 0 (len - n')) v
422 )
423 where
424 m = delay_inline min n' len
425 n' = max n 0
426 len = length v
427
428 -- | /O(1)/ Yield a slice of the vector without copying. The vector must
429 -- contain at least @i+n@ elements but this is not checked.
430 unsafeSlice :: Vector v a => Int -- ^ @i@ starting index
431 -> Int -- ^ @n@ length
432 -> v a
433 -> v a
434 {-# INLINE_FUSED unsafeSlice #-}
435 unsafeSlice i n v = UNSAFE_CHECK(checkSlice) "unsafeSlice" i n (length v)
436 $ basicUnsafeSlice i n v
437
438 -- | /O(1)/ Yield all but the last element without copying. The vector may not
439 -- be empty but this is not checked.
440 unsafeInit :: Vector v a => v a -> v a
441 {-# INLINE_FUSED unsafeInit #-}
442 unsafeInit v = unsafeSlice 0 (length v - 1) v
443
444 -- | /O(1)/ Yield all but the first element without copying. The vector may not
445 -- be empty but this is not checked.
446 unsafeTail :: Vector v a => v a -> v a
447 {-# INLINE_FUSED unsafeTail #-}
448 unsafeTail v = unsafeSlice 1 (length v - 1) v
449
450 -- | /O(1)/ Yield the first @n@ elements without copying. The vector must
451 -- contain at least @n@ elements but this is not checked.
452 unsafeTake :: Vector v a => Int -> v a -> v a
453 {-# INLINE unsafeTake #-}
454 unsafeTake n v = unsafeSlice 0 n v
455
456 -- | /O(1)/ Yield all but the first @n@ elements without copying. The vector
457 -- must contain at least @n@ elements but this is not checked.
458 unsafeDrop :: Vector v a => Int -> v a -> v a
459 {-# INLINE unsafeDrop #-}
460 unsafeDrop n v = unsafeSlice n (length v - n) v
461
462 {-# RULES
463
464 "slice/new [Vector]" forall i n p.
465 slice i n (new p) = new (New.slice i n p)
466
467 "init/new [Vector]" forall p.
468 init (new p) = new (New.init p)
469
470 "tail/new [Vector]" forall p.
471 tail (new p) = new (New.tail p)
472
473 "take/new [Vector]" forall n p.
474 take n (new p) = new (New.take n p)
475
476 "drop/new [Vector]" forall n p.
477 drop n (new p) = new (New.drop n p)
478
479 "unsafeSlice/new [Vector]" forall i n p.
480 unsafeSlice i n (new p) = new (New.unsafeSlice i n p)
481
482 "unsafeInit/new [Vector]" forall p.
483 unsafeInit (new p) = new (New.unsafeInit p)
484
485 "unsafeTail/new [Vector]" forall p.
486 unsafeTail (new p) = new (New.unsafeTail p)
487
488 #-}
489
490 -- Initialisation
491 -- --------------
492
493 -- | /O(1)/ Empty vector
494 empty :: Vector v a => v a
495 {-# INLINE empty #-}
496 empty = unstream Bundle.empty
497
498 -- | /O(1)/ Vector with exactly one element
499 singleton :: forall v a. Vector v a => a -> v a
500 {-# INLINE singleton #-}
501 singleton x = elemseq (undefined :: v a) x
502 $ unstream (Bundle.singleton x)
503
504 -- | /O(n)/ Vector of the given length with the same value in each position
505 replicate :: forall v a. Vector v a => Int -> a -> v a
506 {-# INLINE replicate #-}
507 replicate n x = elemseq (undefined :: v a) x
508 $ unstream
509 $ Bundle.replicate n x
510
511 -- | /O(n)/ Construct a vector of the given length by applying the function to
512 -- each index
513 generate :: Vector v a => Int -> (Int -> a) -> v a
514 {-# INLINE generate #-}
515 generate n f = unstream (Bundle.generate n f)
516
517 -- | /O(n)/ Apply function n times to value. Zeroth element is original value.
518 iterateN :: Vector v a => Int -> (a -> a) -> a -> v a
519 {-# INLINE iterateN #-}
520 iterateN n f x = unstream (Bundle.iterateN n f x)
521
522 -- Unfolding
523 -- ---------
524
525 -- | /O(n)/ Construct a vector by repeatedly applying the generator function
526 -- to a seed. The generator function yields 'Just' the next element and the
527 -- new seed or 'Nothing' if there are no more elements.
528 --
529 -- > unfoldr (\n -> if n == 0 then Nothing else Just (n,n-1)) 10
530 -- > = <10,9,8,7,6,5,4,3,2,1>
531 unfoldr :: Vector v a => (b -> Maybe (a, b)) -> b -> v a
532 {-# INLINE unfoldr #-}
533 unfoldr f = unstream . Bundle.unfoldr f
534
535 -- | /O(n)/ Construct a vector with at most @n@ by repeatedly applying the
536 -- generator function to the a seed. The generator function yields 'Just' the
537 -- next element and the new seed or 'Nothing' if there are no more elements.
538 --
539 -- > unfoldrN 3 (\n -> Just (n,n-1)) 10 = <10,9,8>
540 unfoldrN :: Vector v a => Int -> (b -> Maybe (a, b)) -> b -> v a
541 {-# INLINE unfoldrN #-}
542 unfoldrN n f = unstream . Bundle.unfoldrN n f
543
544 -- | /O(n)/ Construct a vector with @n@ elements by repeatedly applying the
545 -- generator function to the already constructed part of the vector.
546 --
547 -- > constructN 3 f = let a = f <> ; b = f <a> ; c = f <a,b> in f <a,b,c>
548 --
549 constructN :: forall v a. Vector v a => Int -> (v a -> a) -> v a
550 {-# INLINE constructN #-}
551 -- NOTE: We *CANNOT* wrap this in New and then fuse because the elements
552 -- might contain references to the immutable vector!
553 constructN !n f = runST (
554 do
555 v <- M.new n
556 v' <- unsafeFreeze v
557 fill v' 0
558 )
559 where
560 fill :: forall s. v a -> Int -> ST s (v a)
561 fill !v i | i < n = let x = f (unsafeTake i v)
562 in
563 elemseq v x $
564 do
565 v' <- unsafeThaw v
566 M.unsafeWrite v' i x
567 v'' <- unsafeFreeze v'
568 fill v'' (i+1)
569
570 fill v i = return v
571
572 -- | /O(n)/ Construct a vector with @n@ elements from right to left by
573 -- repeatedly applying the generator function to the already constructed part
574 -- of the vector.
575 --
576 -- > constructrN 3 f = let a = f <> ; b = f<a> ; c = f <b,a> in f <c,b,a>
577 --
578 constructrN :: forall v a. Vector v a => Int -> (v a -> a) -> v a
579 {-# INLINE constructrN #-}
580 -- NOTE: We *CANNOT* wrap this in New and then fuse because the elements
581 -- might contain references to the immutable vector!
582 constructrN !n f = runST (
583 do
584 v <- n `seq` M.new n
585 v' <- unsafeFreeze v
586 fill v' 0
587 )
588 where
589 fill :: forall s. v a -> Int -> ST s (v a)
590 fill !v i | i < n = let x = f (unsafeSlice (n-i) i v)
591 in
592 elemseq v x $
593 do
594 v' <- unsafeThaw v
595 M.unsafeWrite v' (n-i-1) x
596 v'' <- unsafeFreeze v'
597 fill v'' (i+1)
598
599 fill v i = return v
600
601
602 -- Enumeration
603 -- -----------
604
605 -- | /O(n)/ Yield a vector of the given length containing the values @x@, @x+1@
606 -- etc. This operation is usually more efficient than 'enumFromTo'.
607 --
608 -- > enumFromN 5 3 = <5,6,7>
609 enumFromN :: (Vector v a, Num a) => a -> Int -> v a
610 {-# INLINE enumFromN #-}
611 enumFromN x n = enumFromStepN x 1 n
612
613 -- | /O(n)/ Yield a vector of the given length containing the values @x@, @x+y@,
614 -- @x+y+y@ etc. This operations is usually more efficient than 'enumFromThenTo'.
615 --
616 -- > enumFromStepN 1 0.1 5 = <1,1.1,1.2,1.3,1.4>
617 enumFromStepN :: forall v a. (Vector v a, Num a) => a -> a -> Int -> v a
618 {-# INLINE enumFromStepN #-}
619 enumFromStepN x y n = elemseq (undefined :: v a) x
620 $ elemseq (undefined :: v a) y
621 $ unstream
622 $ Bundle.enumFromStepN x y n
623
624 -- | /O(n)/ Enumerate values from @x@ to @y@.
625 --
626 -- /WARNING:/ This operation can be very inefficient. If at all possible, use
627 -- 'enumFromN' instead.
628 enumFromTo :: (Vector v a, Enum a) => a -> a -> v a
629 {-# INLINE enumFromTo #-}
630 enumFromTo x y = unstream (Bundle.enumFromTo x y)
631
632 -- | /O(n)/ Enumerate values from @x@ to @y@ with a specific step @z@.
633 --
634 -- /WARNING:/ This operation can be very inefficient. If at all possible, use
635 -- 'enumFromStepN' instead.
636 enumFromThenTo :: (Vector v a, Enum a) => a -> a -> a -> v a
637 {-# INLINE enumFromThenTo #-}
638 enumFromThenTo x y z = unstream (Bundle.enumFromThenTo x y z)
639
640 -- Concatenation
641 -- -------------
642
643 -- | /O(n)/ Prepend an element
644 cons :: forall v a. Vector v a => a -> v a -> v a
645 {-# INLINE cons #-}
646 cons x v = elemseq (undefined :: v a) x
647 $ unstream
648 $ Bundle.cons x
649 $ stream v
650
651 -- | /O(n)/ Append an element
652 snoc :: forall v a. Vector v a => v a -> a -> v a
653 {-# INLINE snoc #-}
654 snoc v x = elemseq (undefined :: v a) x
655 $ unstream
656 $ Bundle.snoc (stream v) x
657
658 infixr 5 ++
659 -- | /O(m+n)/ Concatenate two vectors
660 (++) :: Vector v a => v a -> v a -> v a
661 {-# INLINE (++) #-}
662 v ++ w = unstream (stream v Bundle.++ stream w)
663
664 -- | /O(n)/ Concatenate all vectors in the list
665 concat :: Vector v a => [v a] -> v a
666 {-# INLINE concat #-}
667 concat = unstream . Bundle.fromVectors
668 {-
669 concat vs = unstream (Bundle.flatten mk step (Exact n) (Bundle.fromList vs))
670 where
671 n = List.foldl' (\k v -> k + length v) 0 vs
672
673 {-# INLINE_INNER step #-}
674 step (v,i,k)
675 | i < k = case unsafeIndexM v i of
676 Box x -> Bundle.Yield x (v,i+1,k)
677 | otherwise = Bundle.Done
678
679 {-# INLINE mk #-}
680 mk v = let k = length v
681 in
682 k `seq` (v,0,k)
683 -}
684
685 -- Monadic initialisation
686 -- ----------------------
687
688 -- | /O(n)/ Execute the monadic action the given number of times and store the
689 -- results in a vector.
690 replicateM :: (Monad m, Vector v a) => Int -> m a -> m (v a)
691 {-# INLINE replicateM #-}
692 replicateM n m = unstreamM (MBundle.replicateM n m)
693
694 -- | /O(n)/ Construct a vector of the given length by applying the monadic
695 -- action to each index
696 generateM :: (Monad m, Vector v a) => Int -> (Int -> m a) -> m (v a)
697 {-# INLINE generateM #-}
698 generateM n f = unstreamM (MBundle.generateM n f)
699
700 -- | Execute the monadic action and freeze the resulting vector.
701 --
702 -- @
703 -- create (do { v \<- 'M.new' 2; 'M.write' v 0 \'a\'; 'M.write' v 1 \'b\'; return v }) = \<'a','b'\>
704 -- @
705 create :: Vector v a => (forall s. ST s (Mutable v s a)) -> v a
706 {-# INLINE create #-}
707 create p = new (New.create p)
708
709 -- Restricting memory usage
710 -- ------------------------
711
712 -- | /O(n)/ Yield the argument but force it not to retain any extra memory,
713 -- possibly by copying it.
714 --
715 -- This is especially useful when dealing with slices. For example:
716 --
717 -- > force (slice 0 2 <huge vector>)
718 --
719 -- Here, the slice retains a reference to the huge vector. Forcing it creates
720 -- a copy of just the elements that belong to the slice and allows the huge
721 -- vector to be garbage collected.
722 force :: Vector v a => v a -> v a
723 -- FIXME: we probably ought to inline this later as the rules still might fire
724 -- otherwise
725 {-# INLINE_FUSED force #-}
726 force v = new (clone v)
727
728 -- Bulk updates
729 -- ------------
730
731 -- | /O(m+n)/ For each pair @(i,a)@ from the list, replace the vector
732 -- element at position @i@ by @a@.
733 --
734 -- > <5,9,2,7> // [(2,1),(0,3),(2,8)] = <3,9,8,7>
735 --
736 (//) :: Vector v a => v a -- ^ initial vector (of length @m@)
737 -> [(Int, a)] -- ^ list of index/value pairs (of length @n@)
738 -> v a
739 {-# INLINE (//) #-}
740 v // us = update_stream v (Bundle.fromList us)
741
742 -- | /O(m+n)/ For each pair @(i,a)@ from the vector of index/value pairs,
743 -- replace the vector element at position @i@ by @a@.
744 --
745 -- > update <5,9,2,7> <(2,1),(0,3),(2,8)> = <3,9,8,7>
746 --
747 update :: (Vector v a, Vector v (Int, a))
748 => v a -- ^ initial vector (of length @m@)
749 -> v (Int, a) -- ^ vector of index/value pairs (of length @n@)
750 -> v a
751 {-# INLINE update #-}
752 update v w = update_stream v (stream w)
753
754 -- | /O(m+min(n1,n2))/ For each index @i@ from the index vector and the
755 -- corresponding value @a@ from the value vector, replace the element of the
756 -- initial vector at position @i@ by @a@.
757 --
758 -- > update_ <5,9,2,7> <2,0,2> <1,3,8> = <3,9,8,7>
759 --
760 -- This function is useful for instances of 'Vector' that cannot store pairs.
761 -- Otherwise, 'update' is probably more convenient.
762 --
763 -- @
764 -- update_ xs is ys = 'update' xs ('zip' is ys)
765 -- @
766 update_ :: (Vector v a, Vector v Int)
767 => v a -- ^ initial vector (of length @m@)
768 -> v Int -- ^ index vector (of length @n1@)
769 -> v a -- ^ value vector (of length @n2@)
770 -> v a
771 {-# INLINE update_ #-}
772 update_ v is w = update_stream v (Bundle.zipWith (,) (stream is) (stream w))
773
774 update_stream :: Vector v a => v a -> Bundle u (Int,a) -> v a
775 {-# INLINE update_stream #-}
776 update_stream = modifyWithBundle M.update
777
778 -- | Same as ('//') but without bounds checking.
779 unsafeUpd :: Vector v a => v a -> [(Int, a)] -> v a
780 {-# INLINE unsafeUpd #-}
781 unsafeUpd v us = unsafeUpdate_stream v (Bundle.fromList us)
782
783 -- | Same as 'update' but without bounds checking.
784 unsafeUpdate :: (Vector v a, Vector v (Int, a)) => v a -> v (Int, a) -> v a
785 {-# INLINE unsafeUpdate #-}
786 unsafeUpdate v w = unsafeUpdate_stream v (stream w)
787
788 -- | Same as 'update_' but without bounds checking.
789 unsafeUpdate_ :: (Vector v a, Vector v Int) => v a -> v Int -> v a -> v a
790 {-# INLINE unsafeUpdate_ #-}
791 unsafeUpdate_ v is w
792 = unsafeUpdate_stream v (Bundle.zipWith (,) (stream is) (stream w))
793
794 unsafeUpdate_stream :: Vector v a => v a -> Bundle u (Int,a) -> v a
795 {-# INLINE unsafeUpdate_stream #-}
796 unsafeUpdate_stream = modifyWithBundle M.unsafeUpdate
797
798 -- Accumulations
799 -- -------------
800
801 -- | /O(m+n)/ For each pair @(i,b)@ from the list, replace the vector element
802 -- @a@ at position @i@ by @f a b@.
803 --
804 -- > accum (+) <5,9,2> [(2,4),(1,6),(0,3),(1,7)] = <5+3, 9+6+7, 2+4>
805 accum :: Vector v a
806 => (a -> b -> a) -- ^ accumulating function @f@
807 -> v a -- ^ initial vector (of length @m@)
808 -> [(Int,b)] -- ^ list of index/value pairs (of length @n@)
809 -> v a
810 {-# INLINE accum #-}
811 accum f v us = accum_stream f v (Bundle.fromList us)
812
813 -- | /O(m+n)/ For each pair @(i,b)@ from the vector of pairs, replace the vector
814 -- element @a@ at position @i@ by @f a b@.
815 --
816 -- > accumulate (+) <5,9,2> <(2,4),(1,6),(0,3),(1,7)> = <5+3, 9+6+7, 2+4>
817 accumulate :: (Vector v a, Vector v (Int, b))
818 => (a -> b -> a) -- ^ accumulating function @f@
819 -> v a -- ^ initial vector (of length @m@)
820 -> v (Int,b) -- ^ vector of index/value pairs (of length @n@)
821 -> v a
822 {-# INLINE accumulate #-}
823 accumulate f v us = accum_stream f v (stream us)
824
825 -- | /O(m+min(n1,n2))/ For each index @i@ from the index vector and the
826 -- corresponding value @b@ from the the value vector,
827 -- replace the element of the initial vector at
828 -- position @i@ by @f a b@.
829 --
830 -- > accumulate_ (+) <5,9,2> <2,1,0,1> <4,6,3,7> = <5+3, 9+6+7, 2+4>
831 --
832 -- This function is useful for instances of 'Vector' that cannot store pairs.
833 -- Otherwise, 'accumulate' is probably more convenient:
834 --
835 -- @
836 -- accumulate_ f as is bs = 'accumulate' f as ('zip' is bs)
837 -- @
838 accumulate_ :: (Vector v a, Vector v Int, Vector v b)
839 => (a -> b -> a) -- ^ accumulating function @f@
840 -> v a -- ^ initial vector (of length @m@)
841 -> v Int -- ^ index vector (of length @n1@)
842 -> v b -- ^ value vector (of length @n2@)
843 -> v a
844 {-# INLINE accumulate_ #-}
845 accumulate_ f v is xs = accum_stream f v (Bundle.zipWith (,) (stream is)
846 (stream xs))
847
848
849 accum_stream :: Vector v a => (a -> b -> a) -> v a -> Bundle u (Int,b) -> v a
850 {-# INLINE accum_stream #-}
851 accum_stream f = modifyWithBundle (M.accum f)
852
853 -- | Same as 'accum' but without bounds checking.
854 unsafeAccum :: Vector v a => (a -> b -> a) -> v a -> [(Int,b)] -> v a
855 {-# INLINE unsafeAccum #-}
856 unsafeAccum f v us = unsafeAccum_stream f v (Bundle.fromList us)
857
858 -- | Same as 'accumulate' but without bounds checking.
859 unsafeAccumulate :: (Vector v a, Vector v (Int, b))
860 => (a -> b -> a) -> v a -> v (Int,b) -> v a
861 {-# INLINE unsafeAccumulate #-}
862 unsafeAccumulate f v us = unsafeAccum_stream f v (stream us)
863
864 -- | Same as 'accumulate_' but without bounds checking.
865 unsafeAccumulate_ :: (Vector v a, Vector v Int, Vector v b)
866 => (a -> b -> a) -> v a -> v Int -> v b -> v a
867 {-# INLINE unsafeAccumulate_ #-}
868 unsafeAccumulate_ f v is xs
869 = unsafeAccum_stream f v (Bundle.zipWith (,) (stream is) (stream xs))
870
871 unsafeAccum_stream
872 :: Vector v a => (a -> b -> a) -> v a -> Bundle u (Int,b) -> v a
873 {-# INLINE unsafeAccum_stream #-}
874 unsafeAccum_stream f = modifyWithBundle (M.unsafeAccum f)
875
876 -- Permutations
877 -- ------------
878
879 -- | /O(n)/ Reverse a vector
880 reverse :: (Vector v a) => v a -> v a
881 {-# INLINE reverse #-}
882 -- FIXME: make this fuse better, add support for recycling
883 reverse = unstream . streamR
884
885 -- | /O(n)/ Yield the vector obtained by replacing each element @i@ of the
886 -- index vector by @xs'!'i@. This is equivalent to @'map' (xs'!') is@ but is
887 -- often much more efficient.
888 --
889 -- > backpermute <a,b,c,d> <0,3,2,3,1,0> = <a,d,c,d,b,a>
890 backpermute :: (Vector v a, Vector v Int)
891 => v a -- ^ @xs@ value vector
892 -> v Int -- ^ @is@ index vector (of length @n@)
893 -> v a
894 {-# INLINE backpermute #-}
895 -- This somewhat non-intuitive definition ensures that the resulting vector
896 -- does not retain references to the original one even if it is lazy in its
897 -- elements. This would not be the case if we simply used map (v!)
898 backpermute v is = seq v
899 $ seq n
900 $ unstream
901 $ Bundle.unbox
902 $ Bundle.map index
903 $ stream is
904 where
905 n = length v
906
907 {-# INLINE index #-}
908 -- NOTE: we do it this way to avoid triggering LiberateCase on n in
909 -- polymorphic code
910 index i = BOUNDS_CHECK(checkIndex) "backpermute" i n
911 $ basicUnsafeIndexM v i
912
913 -- | Same as 'backpermute' but without bounds checking.
914 unsafeBackpermute :: (Vector v a, Vector v Int) => v a -> v Int -> v a
915 {-# INLINE unsafeBackpermute #-}
916 unsafeBackpermute v is = seq v
917 $ seq n
918 $ unstream
919 $ Bundle.unbox
920 $ Bundle.map index
921 $ stream is
922 where
923 n = length v
924
925 {-# INLINE index #-}
926 -- NOTE: we do it this way to avoid triggering LiberateCase on n in
927 -- polymorphic code
928 index i = UNSAFE_CHECK(checkIndex) "unsafeBackpermute" i n
929 $ basicUnsafeIndexM v i
930
931 -- Safe destructive updates
932 -- ------------------------
933
934 -- | Apply a destructive operation to a vector. The operation will be
935 -- performed in place if it is safe to do so and will modify a copy of the
936 -- vector otherwise.
937 --
938 -- @
939 -- modify (\\v -> 'M.write' v 0 \'x\') ('replicate' 3 \'a\') = \<\'x\',\'a\',\'a\'\>
940 -- @
941 modify :: Vector v a => (forall s. Mutable v s a -> ST s ()) -> v a -> v a
942 {-# INLINE modify #-}
943 modify p = new . New.modify p . clone
944
945 -- We have to make sure that this is strict in the stream but we can't seq on
946 -- it while fusion is happening. Hence this ugliness.
947 modifyWithBundle :: Vector v a
948 => (forall s. Mutable v s a -> Bundle u b -> ST s ())
949 -> v a -> Bundle u b -> v a
950 {-# INLINE modifyWithBundle #-}
951 modifyWithBundle p v s = new (New.modifyWithBundle p (clone v) s)
952
953 -- Indexing
954 -- --------
955
956 -- | /O(n)/ Pair each element in a vector with its index
957 indexed :: (Vector v a, Vector v (Int,a)) => v a -> v (Int,a)
958 {-# INLINE indexed #-}
959 indexed = unstream . Bundle.indexed . stream
960
961 -- Mapping
962 -- -------
963
964 -- | /O(n)/ Map a function over a vector
965 map :: (Vector v a, Vector v b) => (a -> b) -> v a -> v b
966 {-# INLINE map #-}
967 map f = unstream . inplace (S.map f) id . stream
968
969 -- | /O(n)/ Apply a function to every element of a vector and its index
970 imap :: (Vector v a, Vector v b) => (Int -> a -> b) -> v a -> v b
971 {-# INLINE imap #-}
972 imap f = unstream . inplace (S.map (uncurry f) . S.indexed) id
973 . stream
974
975 -- | Map a function over a vector and concatenate the results.
976 concatMap :: (Vector v a, Vector v b) => (a -> v b) -> v a -> v b
977 {-# INLINE concatMap #-}
978 -- NOTE: We can't fuse concatMap anyway so don't pretend we do.
979 -- This seems to be slightly slower
980 -- concatMap f = concat . Bundle.toList . Bundle.map f . stream
981
982 -- Slowest
983 -- concatMap f = unstream . Bundle.concatMap (stream . f) . stream
984
985 -- Used to be fastest
986 {-
987 concatMap f = unstream
988 . Bundle.flatten mk step Unknown
989 . stream
990 where
991 {-# INLINE_INNER step #-}
992 step (v,i,k)
993 | i < k = case unsafeIndexM v i of
994 Box x -> Bundle.Yield x (v,i+1,k)
995 | otherwise = Bundle.Done
996
997 {-# INLINE mk #-}
998 mk x = let v = f x
999 k = length v
1000 in
1001 k `seq` (v,0,k)
1002 -}
1003
1004 -- This seems to be fastest now
1005 concatMap f = unstream
1006 . Bundle.concatVectors
1007 . Bundle.map f
1008 . stream
1009
1010 -- Monadic mapping
1011 -- ---------------
1012
1013 -- | /O(n)/ Apply the monadic action to all elements of the vector, yielding a
1014 -- vector of results
1015 mapM :: (Monad m, Vector v a, Vector v b) => (a -> m b) -> v a -> m (v b)
1016 {-# INLINE mapM #-}
1017 mapM f = unstreamM . Bundle.mapM f . stream
1018
1019 -- | /O(n)/ Apply the monadic action to all elements of a vector and ignore the
1020 -- results
1021 mapM_ :: (Monad m, Vector v a) => (a -> m b) -> v a -> m ()
1022 {-# INLINE mapM_ #-}
1023 mapM_ f = Bundle.mapM_ f . stream
1024
1025 -- | /O(n)/ Apply the monadic action to all elements of the vector, yielding a
1026 -- vector of results. Equvalent to @flip 'mapM'@.
1027 forM :: (Monad m, Vector v a, Vector v b) => v a -> (a -> m b) -> m (v b)
1028 {-# INLINE forM #-}
1029 forM as f = mapM f as
1030
1031 -- | /O(n)/ Apply the monadic action to all elements of a vector and ignore the
1032 -- results. Equivalent to @flip 'mapM_'@.
1033 forM_ :: (Monad m, Vector v a) => v a -> (a -> m b) -> m ()
1034 {-# INLINE forM_ #-}
1035 forM_ as f = mapM_ f as
1036
1037 -- Zipping
1038 -- -------
1039
1040 -- | /O(min(m,n))/ Zip two vectors with the given function.
1041 zipWith :: (Vector v a, Vector v b, Vector v c)
1042 => (a -> b -> c) -> v a -> v b -> v c
1043 {-# INLINE zipWith #-}
1044 zipWith f xs ys = unstream (Bundle.zipWith f (stream xs) (stream ys))
1045
1046 -- | Zip three vectors with the given function.
1047 zipWith3 :: (Vector v a, Vector v b, Vector v c, Vector v d)
1048 => (a -> b -> c -> d) -> v a -> v b -> v c -> v d
1049 {-# INLINE zipWith3 #-}
1050 zipWith3 f as bs cs = unstream (Bundle.zipWith3 f (stream as)
1051 (stream bs)
1052 (stream cs))
1053
1054 zipWith4 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e)
1055 => (a -> b -> c -> d -> e) -> v a -> v b -> v c -> v d -> v e
1056 {-# INLINE zipWith4 #-}
1057 zipWith4 f as bs cs ds
1058 = unstream (Bundle.zipWith4 f (stream as)
1059 (stream bs)
1060 (stream cs)
1061 (stream ds))
1062
1063 zipWith5 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e,
1064 Vector v f)
1065 => (a -> b -> c -> d -> e -> f) -> v a -> v b -> v c -> v d -> v e
1066 -> v f
1067 {-# INLINE zipWith5 #-}
1068 zipWith5 f as bs cs ds es
1069 = unstream (Bundle.zipWith5 f (stream as)
1070 (stream bs)
1071 (stream cs)
1072 (stream ds)
1073 (stream es))
1074
1075 zipWith6 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e,
1076 Vector v f, Vector v g)
1077 => (a -> b -> c -> d -> e -> f -> g)
1078 -> v a -> v b -> v c -> v d -> v e -> v f -> v g
1079 {-# INLINE zipWith6 #-}
1080 zipWith6 f as bs cs ds es fs
1081 = unstream (Bundle.zipWith6 f (stream as)
1082 (stream bs)
1083 (stream cs)
1084 (stream ds)
1085 (stream es)
1086 (stream fs))
1087
1088 -- | /O(min(m,n))/ Zip two vectors with a function that also takes the
1089 -- elements' indices.
1090 izipWith :: (Vector v a, Vector v b, Vector v c)
1091 => (Int -> a -> b -> c) -> v a -> v b -> v c
1092 {-# INLINE izipWith #-}
1093 izipWith f xs ys = unstream
1094 (Bundle.zipWith (uncurry f) (Bundle.indexed (stream xs))
1095 (stream ys))
1096
1097 izipWith3 :: (Vector v a, Vector v b, Vector v c, Vector v d)
1098 => (Int -> a -> b -> c -> d) -> v a -> v b -> v c -> v d
1099 {-# INLINE izipWith3 #-}
1100 izipWith3 f as bs cs
1101 = unstream (Bundle.zipWith3 (uncurry f) (Bundle.indexed (stream as))
1102 (stream bs)
1103 (stream cs))
1104
1105 izipWith4 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e)
1106 => (Int -> a -> b -> c -> d -> e) -> v a -> v b -> v c -> v d -> v e
1107 {-# INLINE izipWith4 #-}
1108 izipWith4 f as bs cs ds
1109 = unstream (Bundle.zipWith4 (uncurry f) (Bundle.indexed (stream as))
1110 (stream bs)
1111 (stream cs)
1112 (stream ds))
1113
1114 izipWith5 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e,
1115 Vector v f)
1116 => (Int -> a -> b -> c -> d -> e -> f) -> v a -> v b -> v c -> v d
1117 -> v e -> v f
1118 {-# INLINE izipWith5 #-}
1119 izipWith5 f as bs cs ds es
1120 = unstream (Bundle.zipWith5 (uncurry f) (Bundle.indexed (stream as))
1121 (stream bs)
1122 (stream cs)
1123 (stream ds)
1124 (stream es))
1125
1126 izipWith6 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e,
1127 Vector v f, Vector v g)
1128 => (Int -> a -> b -> c -> d -> e -> f -> g)
1129 -> v a -> v b -> v c -> v d -> v e -> v f -> v g
1130 {-# INLINE izipWith6 #-}
1131 izipWith6 f as bs cs ds es fs
1132 = unstream (Bundle.zipWith6 (uncurry f) (Bundle.indexed (stream as))
1133 (stream bs)
1134 (stream cs)
1135 (stream ds)
1136 (stream es)
1137 (stream fs))
1138
1139 -- | /O(min(m,n))/ Zip two vectors
1140 zip :: (Vector v a, Vector v b, Vector v (a,b)) => v a -> v b -> v (a, b)
1141 {-# INLINE zip #-}
1142 zip = zipWith (,)
1143
1144 zip3 :: (Vector v a, Vector v b, Vector v c, Vector v (a, b, c))
1145 => v a -> v b -> v c -> v (a, b, c)
1146 {-# INLINE zip3 #-}
1147 zip3 = zipWith3 (,,)
1148
1149 zip4 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v (a, b, c, d))
1150 => v a -> v b -> v c -> v d -> v (a, b, c, d)
1151 {-# INLINE zip4 #-}
1152 zip4 = zipWith4 (,,,)
1153
1154 zip5 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e,
1155 Vector v (a, b, c, d, e))
1156 => v a -> v b -> v c -> v d -> v e -> v (a, b, c, d, e)
1157 {-# INLINE zip5 #-}
1158 zip5 = zipWith5 (,,,,)
1159
1160 zip6 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e,
1161 Vector v f, Vector v (a, b, c, d, e, f))
1162 => v a -> v b -> v c -> v d -> v e -> v f -> v (a, b, c, d, e, f)
1163 {-# INLINE zip6 #-}
1164 zip6 = zipWith6 (,,,,,)
1165
1166 -- Monadic zipping
1167 -- ---------------
1168
1169 -- | /O(min(m,n))/ Zip the two vectors with the monadic action and yield a
1170 -- vector of results
1171 zipWithM :: (Monad m, Vector v a, Vector v b, Vector v c)
1172 => (a -> b -> m c) -> v a -> v b -> m (v c)
1173 -- FIXME: specialise for ST and IO?
1174 {-# INLINE zipWithM #-}
1175 zipWithM f as bs = unstreamM $ Bundle.zipWithM f (stream as) (stream bs)
1176
1177 -- | /O(min(m,n))/ Zip the two vectors with the monadic action and ignore the
1178 -- results
1179 zipWithM_ :: (Monad m, Vector v a, Vector v b)
1180 => (a -> b -> m c) -> v a -> v b -> m ()
1181 {-# INLINE zipWithM_ #-}
1182 zipWithM_ f as bs = Bundle.zipWithM_ f (stream as) (stream bs)
1183
1184 -- Unzipping
1185 -- ---------
1186
1187 -- | /O(min(m,n))/ Unzip a vector of pairs.
1188 unzip :: (Vector v a, Vector v b, Vector v (a,b)) => v (a, b) -> (v a, v b)
1189 {-# INLINE unzip #-}
1190 unzip xs = (map fst xs, map snd xs)
1191
1192 unzip3 :: (Vector v a, Vector v b, Vector v c, Vector v (a, b, c))
1193 => v (a, b, c) -> (v a, v b, v c)
1194 {-# INLINE unzip3 #-}
1195 unzip3 xs = (map (\(a, b, c) -> a) xs,
1196 map (\(a, b, c) -> b) xs,
1197 map (\(a, b, c) -> c) xs)
1198
1199 unzip4 :: (Vector v a, Vector v b, Vector v c, Vector v d,
1200 Vector v (a, b, c, d))
1201 => v (a, b, c, d) -> (v a, v b, v c, v d)
1202 {-# INLINE unzip4 #-}
1203 unzip4 xs = (map (\(a, b, c, d) -> a) xs,
1204 map (\(a, b, c, d) -> b) xs,
1205 map (\(a, b, c, d) -> c) xs,
1206 map (\(a, b, c, d) -> d) xs)
1207
1208 unzip5 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e,
1209 Vector v (a, b, c, d, e))
1210 => v (a, b, c, d, e) -> (v a, v b, v c, v d, v e)
1211 {-# INLINE unzip5 #-}
1212 unzip5 xs = (map (\(a, b, c, d, e) -> a) xs,
1213 map (\(a, b, c, d, e) -> b) xs,
1214 map (\(a, b, c, d, e) -> c) xs,
1215 map (\(a, b, c, d, e) -> d) xs,
1216 map (\(a, b, c, d, e) -> e) xs)
1217
1218 unzip6 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e,
1219 Vector v f, Vector v (a, b, c, d, e, f))
1220 => v (a, b, c, d, e, f) -> (v a, v b, v c, v d, v e, v f)
1221 {-# INLINE unzip6 #-}
1222 unzip6 xs = (map (\(a, b, c, d, e, f) -> a) xs,
1223 map (\(a, b, c, d, e, f) -> b) xs,
1224 map (\(a, b, c, d, e, f) -> c) xs,
1225 map (\(a, b, c, d, e, f) -> d) xs,
1226 map (\(a, b, c, d, e, f) -> e) xs,
1227 map (\(a, b, c, d, e, f) -> f) xs)
1228
1229 -- Filtering
1230 -- ---------
1231
1232 -- | /O(n)/ Drop elements that do not satisfy the predicate
1233 filter :: Vector v a => (a -> Bool) -> v a -> v a
1234 {-# INLINE filter #-}
1235 filter f = unstream . inplace (S.filter f) toMax . stream
1236
1237 -- | /O(n)/ Drop elements that do not satisfy the predicate which is applied to
1238 -- values and their indices
1239 ifilter :: Vector v a => (Int -> a -> Bool) -> v a -> v a
1240 {-# INLINE ifilter #-}
1241 ifilter f = unstream
1242 . inplace (S.map snd . S.filter (uncurry f) . S.indexed) toMax
1243 . stream
1244
1245 -- | /O(n)/ Drop elements that do not satisfy the monadic predicate
1246 filterM :: (Monad m, Vector v a) => (a -> m Bool) -> v a -> m (v a)
1247 {-# INLINE filterM #-}
1248 filterM f = unstreamM . Bundle.filterM f . stream
1249
1250 -- | /O(n)/ Yield the longest prefix of elements satisfying the predicate
1251 -- without copying.
1252 takeWhile :: Vector v a => (a -> Bool) -> v a -> v a
1253 {-# INLINE takeWhile #-}
1254 takeWhile f = unstream . Bundle.takeWhile f . stream
1255
1256 -- | /O(n)/ Drop the longest prefix of elements that satisfy the predicate
1257 -- without copying.
1258 dropWhile :: Vector v a => (a -> Bool) -> v a -> v a
1259 {-# INLINE dropWhile #-}
1260 dropWhile f = unstream . Bundle.dropWhile f . stream
1261
1262 -- Parititioning
1263 -- -------------
1264
1265 -- | /O(n)/ Split the vector in two parts, the first one containing those
1266 -- elements that satisfy the predicate and the second one those that don't. The
1267 -- relative order of the elements is preserved at the cost of a sometimes
1268 -- reduced performance compared to 'unstablePartition'.
1269 partition :: Vector v a => (a -> Bool) -> v a -> (v a, v a)
1270 {-# INLINE partition #-}
1271 partition f = partition_stream f . stream
1272
1273 -- FIXME: Make this inplace-fusible (look at how stable_partition is
1274 -- implemented in C++)
1275
1276 partition_stream :: Vector v a => (a -> Bool) -> Bundle u a -> (v a, v a)
1277 {-# INLINE_FUSED partition_stream #-}
1278 partition_stream f s = s `seq` runST (
1279 do
1280 (mv1,mv2) <- M.partitionBundle f s
1281 v1 <- unsafeFreeze mv1
1282 v2 <- unsafeFreeze mv2
1283 return (v1,v2))
1284
1285 -- | /O(n)/ Split the vector in two parts, the first one containing those
1286 -- elements that satisfy the predicate and the second one those that don't.
1287 -- The order of the elements is not preserved but the operation is often
1288 -- faster than 'partition'.
1289 unstablePartition :: Vector v a => (a -> Bool) -> v a -> (v a, v a)
1290 {-# INLINE unstablePartition #-}
1291 unstablePartition f = unstablePartition_stream f . stream
1292
1293 unstablePartition_stream
1294 :: Vector v a => (a -> Bool) -> Bundle u a -> (v a, v a)
1295 {-# INLINE_FUSED unstablePartition_stream #-}
1296 unstablePartition_stream f s = s `seq` runST (
1297 do
1298 (mv1,mv2) <- M.unstablePartitionBundle f s
1299 v1 <- unsafeFreeze mv1
1300 v2 <- unsafeFreeze mv2
1301 return (v1,v2))
1302
1303 unstablePartition_new :: Vector v a => (a -> Bool) -> New v a -> (v a, v a)
1304 {-# INLINE_FUSED unstablePartition_new #-}
1305 unstablePartition_new f (New.New p) = runST (
1306 do
1307 mv <- p
1308 i <- M.unstablePartition f mv
1309 v <- unsafeFreeze mv
1310 return (unsafeTake i v, unsafeDrop i v))
1311
1312 {-# RULES
1313
1314 "unstablePartition" forall f p.
1315 unstablePartition_stream f (stream (new p))
1316 = unstablePartition_new f p
1317
1318 #-}
1319
1320
1321 -- FIXME: make span and break fusible
1322
1323 -- | /O(n)/ Split the vector into the longest prefix of elements that satisfy
1324 -- the predicate and the rest without copying.
1325 span :: Vector v a => (a -> Bool) -> v a -> (v a, v a)
1326 {-# INLINE span #-}
1327 span f = break (not . f)
1328
1329 -- | /O(n)/ Split the vector into the longest prefix of elements that do not
1330 -- satisfy the predicate and the rest without copying.
1331 break :: Vector v a => (a -> Bool) -> v a -> (v a, v a)
1332 {-# INLINE break #-}
1333 break f xs = case findIndex f xs of
1334 Just i -> (unsafeSlice 0 i xs, unsafeSlice i (length xs - i) xs)
1335 Nothing -> (xs, empty)
1336
1337
1338 -- Searching
1339 -- ---------
1340
1341 infix 4 `elem`
1342 -- | /O(n)/ Check if the vector contains an element
1343 elem :: (Vector v a, Eq a) => a -> v a -> Bool
1344 {-# INLINE elem #-}
1345 elem x = Bundle.elem x . stream
1346
1347 infix 4 `notElem`
1348 -- | /O(n)/ Check if the vector does not contain an element (inverse of 'elem')
1349 notElem :: (Vector v a, Eq a) => a -> v a -> Bool
1350 {-# INLINE notElem #-}
1351 notElem x = Bundle.notElem x . stream
1352
1353 -- | /O(n)/ Yield 'Just' the first element matching the predicate or 'Nothing'
1354 -- if no such element exists.
1355 find :: Vector v a => (a -> Bool) -> v a -> Maybe a
1356 {-# INLINE find #-}
1357 find f = Bundle.find f . stream
1358
1359 -- | /O(n)/ Yield 'Just' the index of the first element matching the predicate
1360 -- or 'Nothing' if no such element exists.
1361 findIndex :: Vector v a => (a -> Bool) -> v a -> Maybe Int
1362 {-# INLINE findIndex #-}
1363 findIndex f = Bundle.findIndex f . stream
1364
1365 -- | /O(n)/ Yield the indices of elements satisfying the predicate in ascending
1366 -- order.
1367 findIndices :: (Vector v a, Vector v Int) => (a -> Bool) -> v a -> v Int
1368 {-# INLINE findIndices #-}
1369 findIndices f = unstream
1370 . inplace (S.map fst . S.filter (f . snd) . S.indexed) toMax
1371 . stream
1372
1373 -- | /O(n)/ Yield 'Just' the index of the first occurence of the given element or
1374 -- 'Nothing' if the vector does not contain the element. This is a specialised
1375 -- version of 'findIndex'.
1376 elemIndex :: (Vector v a, Eq a) => a -> v a -> Maybe Int
1377 {-# INLINE elemIndex #-}
1378 elemIndex x = findIndex (x==)
1379
1380 -- | /O(n)/ Yield the indices of all occurences of the given element in
1381 -- ascending order. This is a specialised version of 'findIndices'.
1382 elemIndices :: (Vector v a, Vector v Int, Eq a) => a -> v a -> v Int
1383 {-# INLINE elemIndices #-}
1384 elemIndices x = findIndices (x==)
1385
1386 -- Folding
1387 -- -------
1388
1389 -- | /O(n)/ Left fold
1390 foldl :: Vector v b => (a -> b -> a) -> a -> v b -> a
1391 {-# INLINE foldl #-}
1392 foldl f z = Bundle.foldl f z . stream
1393
1394 -- | /O(n)/ Left fold on non-empty vectors
1395 foldl1 :: Vector v a => (a -> a -> a) -> v a -> a
1396 {-# INLINE foldl1 #-}
1397 foldl1 f = Bundle.foldl1 f . stream
1398
1399 -- | /O(n)/ Left fold with strict accumulator
1400 foldl' :: Vector v b => (a -> b -> a) -> a -> v b -> a
1401 {-# INLINE foldl' #-}
1402 foldl' f z = Bundle.foldl' f z . stream
1403
1404 -- | /O(n)/ Left fold on non-empty vectors with strict accumulator
1405 foldl1' :: Vector v a => (a -> a -> a) -> v a -> a
1406 {-# INLINE foldl1' #-}
1407 foldl1' f = Bundle.foldl1' f . stream
1408
1409 -- | /O(n)/ Right fold
1410 foldr :: Vector v a => (a -> b -> b) -> b -> v a -> b
1411 {-# INLINE foldr #-}
1412 foldr f z = Bundle.foldr f z . stream
1413
1414 -- | /O(n)/ Right fold on non-empty vectors
1415 foldr1 :: Vector v a => (a -> a -> a) -> v a -> a
1416 {-# INLINE foldr1 #-}
1417 foldr1 f = Bundle.foldr1 f . stream
1418
1419 -- | /O(n)/ Right fold with a strict accumulator
1420 foldr' :: Vector v a => (a -> b -> b) -> b -> v a -> b
1421 {-# INLINE foldr' #-}
1422 foldr' f z = Bundle.foldl' (flip f) z . streamR
1423
1424 -- | /O(n)/ Right fold on non-empty vectors with strict accumulator
1425 foldr1' :: Vector v a => (a -> a -> a) -> v a -> a
1426 {-# INLINE foldr1' #-}
1427 foldr1' f = Bundle.foldl1' (flip f) . streamR
1428
1429 -- | /O(n)/ Left fold (function applied to each element and its index)
1430 ifoldl :: Vector v b => (a -> Int -> b -> a) -> a -> v b -> a
1431 {-# INLINE ifoldl #-}
1432 ifoldl f z = Bundle.foldl (uncurry . f) z . Bundle.indexed . stream
1433
1434 -- | /O(n)/ Left fold with strict accumulator (function applied to each element
1435 -- and its index)
1436 ifoldl' :: Vector v b => (a -> Int -> b -> a) -> a -> v b -> a
1437 {-# INLINE ifoldl' #-}
1438 ifoldl' f z = Bundle.foldl' (uncurry . f) z . Bundle.indexed . stream
1439
1440 -- | /O(n)/ Right fold (function applied to each element and its index)
1441 ifoldr :: Vector v a => (Int -> a -> b -> b) -> b -> v a -> b
1442 {-# INLINE ifoldr #-}
1443 ifoldr f z = Bundle.foldr (uncurry f) z . Bundle.indexed . stream
1444
1445 -- | /O(n)/ Right fold with strict accumulator (function applied to each
1446 -- element and its index)
1447 ifoldr' :: Vector v a => (Int -> a -> b -> b) -> b -> v a -> b
1448 {-# INLINE ifoldr' #-}
1449 ifoldr' f z xs = Bundle.foldl' (flip (uncurry f)) z
1450 $ Bundle.indexedR (length xs) $ streamR xs
1451
1452 -- Specialised folds
1453 -- -----------------
1454
1455 -- | /O(n)/ Check if all elements satisfy the predicate.
1456 all :: Vector v a => (a -> Bool) -> v a -> Bool
1457 {-# INLINE all #-}
1458 all f = Bundle.and . Bundle.map f . stream
1459
1460 -- | /O(n)/ Check if any element satisfies the predicate.
1461 any :: Vector v a => (a -> Bool) -> v a -> Bool
1462 {-# INLINE any #-}
1463 any f = Bundle.or . Bundle.map f . stream
1464
1465 -- | /O(n)/ Check if all elements are 'True'
1466 and :: Vector v Bool => v Bool -> Bool
1467 {-# INLINE and #-}
1468 and = Bundle.and . stream
1469
1470 -- | /O(n)/ Check if any element is 'True'
1471 or :: Vector v Bool => v Bool -> Bool
1472 {-# INLINE or #-}
1473 or = Bundle.or . stream
1474
1475 -- | /O(n)/ Compute the sum of the elements
1476 sum :: (Vector v a, Num a) => v a -> a
1477 {-# INLINE sum #-}
1478 sum = Bundle.foldl' (+) 0 . stream
1479
1480 -- | /O(n)/ Compute the produce of the elements
1481 product :: (Vector v a, Num a) => v a -> a
1482 {-# INLINE product #-}
1483 product = Bundle.foldl' (*) 1 . stream
1484
1485 -- | /O(n)/ Yield the maximum element of the vector. The vector may not be
1486 -- empty.
1487 maximum :: (Vector v a, Ord a) => v a -> a
1488 {-# INLINE maximum #-}
1489 maximum = Bundle.foldl1' max . stream
1490
1491 -- | /O(n)/ Yield the maximum element of the vector according to the given
1492 -- comparison function. The vector may not be empty.
1493 maximumBy :: Vector v a => (a -> a -> Ordering) -> v a -> a
1494 {-# INLINE maximumBy #-}
1495 maximumBy cmp = Bundle.foldl1' maxBy . stream
1496 where
1497 {-# INLINE maxBy #-}
1498 maxBy x y = case cmp x y of
1499 LT -> y
1500 _ -> x
1501
1502 -- | /O(n)/ Yield the minimum element of the vector. The vector may not be
1503 -- empty.
1504 minimum :: (Vector v a, Ord a) => v a -> a
1505 {-# INLINE minimum #-}
1506 minimum = Bundle.foldl1' min . stream
1507
1508 -- | /O(n)/ Yield the minimum element of the vector according to the given
1509 -- comparison function. The vector may not be empty.
1510 minimumBy :: Vector v a => (a -> a -> Ordering) -> v a -> a
1511 {-# INLINE minimumBy #-}
1512 minimumBy cmp = Bundle.foldl1' minBy . stream
1513 where
1514 {-# INLINE minBy #-}
1515 minBy x y = case cmp x y of
1516 GT -> y
1517 _ -> x
1518
1519 -- | /O(n)/ Yield the index of the maximum element of the vector. The vector
1520 -- may not be empty.
1521 maxIndex :: (Vector v a, Ord a) => v a -> Int
1522 {-# INLINE maxIndex #-}
1523 maxIndex = maxIndexBy compare
1524
1525 -- | /O(n)/ Yield the index of the maximum element of the vector according to
1526 -- the given comparison function. The vector may not be empty.
1527 maxIndexBy :: Vector v a => (a -> a -> Ordering) -> v a -> Int
1528 {-# INLINE maxIndexBy #-}
1529 maxIndexBy cmp = fst . Bundle.foldl1' imax . Bundle.indexed . stream
1530 where
1531 imax (i,x) (j,y) = i `seq` j `seq`
1532 case cmp x y of
1533 LT -> (j,y)
1534 _ -> (i,x)
1535
1536 -- | /O(n)/ Yield the index of the minimum element of the vector. The vector
1537 -- may not be empty.
1538 minIndex :: (Vector v a, Ord a) => v a -> Int
1539 {-# INLINE minIndex #-}
1540 minIndex = minIndexBy compare
1541
1542 -- | /O(n)/ Yield the index of the minimum element of the vector according to
1543 -- the given comparison function. The vector may not be empty.
1544 minIndexBy :: Vector v a => (a -> a -> Ordering) -> v a -> Int
1545 {-# INLINE minIndexBy #-}
1546 minIndexBy cmp = fst . Bundle.foldl1' imin . Bundle.indexed . stream
1547 where
1548 imin (i,x) (j,y) = i `seq` j `seq`
1549 case cmp x y of
1550 GT -> (j,y)
1551 _ -> (i,x)
1552
1553 -- Monadic folds
1554 -- -------------
1555
1556 -- | /O(n)/ Monadic fold
1557 foldM :: (Monad m, Vector v b) => (a -> b -> m a) -> a -> v b -> m a
1558 {-# INLINE foldM #-}
1559 foldM m z = Bundle.foldM m z . stream
1560
1561 -- | /O(n)/ Monadic fold over non-empty vectors
1562 fold1M :: (Monad m, Vector v a) => (a -> a -> m a) -> v a -> m a
1563 {-# INLINE fold1M #-}
1564 fold1M m = Bundle.fold1M m . stream
1565
1566 -- | /O(n)/ Monadic fold with strict accumulator
1567 foldM' :: (Monad m, Vector v b) => (a -> b -> m a) -> a -> v b -> m a
1568 {-# INLINE foldM' #-}
1569 foldM' m z = Bundle.foldM' m z . stream
1570
1571 -- | /O(n)/ Monadic fold over non-empty vectors with strict accumulator
1572 fold1M' :: (Monad m, Vector v a) => (a -> a -> m a) -> v a -> m a
1573 {-# INLINE fold1M' #-}
1574 fold1M' m = Bundle.fold1M' m . stream
1575
1576 discard :: Monad m => m a -> m ()
1577 {-# INLINE discard #-}
1578 discard m = m >> return ()
1579
1580 -- | /O(n)/ Monadic fold that discards the result
1581 foldM_ :: (Monad m, Vector v b) => (a -> b -> m a) -> a -> v b -> m ()
1582 {-# INLINE foldM_ #-}
1583 foldM_ m z = discard . Bundle.foldM m z . stream
1584
1585 -- | /O(n)/ Monadic fold over non-empty vectors that discards the result
1586 fold1M_ :: (Monad m, Vector v a) => (a -> a -> m a) -> v a -> m ()
1587 {-# INLINE fold1M_ #-}
1588 fold1M_ m = discard . Bundle.fold1M m . stream
1589
1590 -- | /O(n)/ Monadic fold with strict accumulator that discards the result
1591 foldM'_ :: (Monad m, Vector v b) => (a -> b -> m a) -> a -> v b -> m ()
1592 {-# INLINE foldM'_ #-}
1593 foldM'_ m z = discard . Bundle.foldM' m z . stream
1594
1595 -- | /O(n)/ Monad fold over non-empty vectors with strict accumulator
1596 -- that discards the result
1597 fold1M'_ :: (Monad m, Vector v a) => (a -> a -> m a) -> v a -> m ()
1598 {-# INLINE fold1M'_ #-}
1599 fold1M'_ m = discard . Bundle.fold1M' m . stream
1600
1601 -- Monadic sequencing
1602 -- ------------------
1603
1604 -- | Evaluate each action and collect the results
1605 sequence :: (Monad m, Vector v a, Vector v (m a)) => v (m a) -> m (v a)
1606 {-# INLINE sequence #-}
1607 sequence = mapM id
1608
1609 -- | Evaluate each action and discard the results
1610 sequence_ :: (Monad m, Vector v (m a)) => v (m a) -> m ()
1611 {-# INLINE sequence_ #-}
1612 sequence_ = mapM_ id
1613
1614 -- Prefix sums (scans)
1615 -- -------------------
1616
1617 -- | /O(n)/ Prescan
1618 --
1619 -- @
1620 -- prescanl f z = 'init' . 'scanl' f z
1621 -- @
1622 --
1623 -- Example: @prescanl (+) 0 \<1,2,3,4\> = \<0,1,3,6\>@
1624 --
1625 prescanl :: (Vector v a, Vector v b) => (a -> b -> a) -> a -> v b -> v a
1626 {-# INLINE prescanl #-}
1627 prescanl f z = unstream . inplace (S.prescanl f z) id . stream
1628
1629 -- | /O(n)/ Prescan with strict accumulator
1630 prescanl' :: (Vector v a, Vector v b) => (a -> b -> a) -> a -> v b -> v a
1631 {-# INLINE prescanl' #-}
1632 prescanl' f z = unstream . inplace (S.prescanl' f z) id . stream
1633
1634 -- | /O(n)/ Scan
1635 --
1636 -- @
1637 -- postscanl f z = 'tail' . 'scanl' f z
1638 -- @
1639 --
1640 -- Example: @postscanl (+) 0 \<1,2,3,4\> = \<1,3,6,10\>@
1641 --
1642 postscanl :: (Vector v a, Vector v b) => (a -> b -> a) -> a -> v b -> v a
1643 {-# INLINE postscanl #-}
1644 postscanl f z = unstream . inplace (S.postscanl f z) id . stream
1645
1646 -- | /O(n)/ Scan with strict accumulator
1647 postscanl' :: (Vector v a, Vector v b) => (a -> b -> a) -> a -> v b -> v a
1648 {-# INLINE postscanl' #-}
1649 postscanl' f z = unstream . inplace (S.postscanl' f z) id . stream
1650
1651 -- | /O(n)/ Haskell-style scan
1652 --
1653 -- > scanl f z <x1,...,xn> = <y1,...,y(n+1)>
1654 -- > where y1 = z
1655 -- > yi = f y(i-1) x(i-1)
1656 --
1657 -- Example: @scanl (+) 0 \<1,2,3,4\> = \<0,1,3,6,10\>@
1658 --
1659 scanl :: (Vector v a, Vector v b) => (a -> b -> a) -> a -> v b -> v a
1660 {-# INLINE scanl #-}
1661 scanl f z = unstream . Bundle.scanl f z . stream
1662
1663 -- | /O(n)/ Haskell-style scan with strict accumulator
1664 scanl' :: (Vector v a, Vector v b) => (a -> b -> a) -> a -> v b -> v a
1665 {-# INLINE scanl' #-}
1666 scanl' f z = unstream . Bundle.scanl' f z . stream
1667
1668 -- | /O(n)/ Scan over a non-empty vector
1669 --
1670 -- > scanl f <x1,...,xn> = <y1,...,yn>
1671 -- > where y1 = x1
1672 -- > yi = f y(i-1) xi
1673 --
1674 scanl1 :: Vector v a => (a -> a -> a) -> v a -> v a
1675 {-# INLINE scanl1 #-}
1676 scanl1 f = unstream . inplace (S.scanl1 f) id . stream
1677
1678 -- | /O(n)/ Scan over a non-empty vector with a strict accumulator
1679 scanl1' :: Vector v a => (a -> a -> a) -> v a -> v a
1680 {-# INLINE scanl1' #-}
1681 scanl1' f = unstream . inplace (S.scanl1' f) id . stream
1682
1683 -- | /O(n)/ Right-to-left prescan
1684 --
1685 -- @
1686 -- prescanr f z = 'reverse' . 'prescanl' (flip f) z . 'reverse'
1687 -- @
1688 --
1689 prescanr :: (Vector v a, Vector v b) => (a -> b -> b) -> b -> v a -> v b
1690 {-# INLINE prescanr #-}
1691 prescanr f z = unstreamR . inplace (S.prescanl (flip f) z) id . streamR
1692
1693 -- | /O(n)/ Right-to-left prescan with strict accumulator
1694 prescanr' :: (Vector v a, Vector v b) => (a -> b -> b) -> b -> v a -> v b
1695 {-# INLINE prescanr' #-}
1696 prescanr' f z = unstreamR . inplace (S.prescanl' (flip f) z) id . streamR
1697
1698 -- | /O(n)/ Right-to-left scan
1699 postscanr :: (Vector v a, Vector v b) => (a -> b -> b) -> b -> v a -> v b
1700 {-# INLINE postscanr #-}
1701 postscanr f z = unstreamR . inplace (S.postscanl (flip f) z) id . streamR
1702
1703 -- | /O(n)/ Right-to-left scan with strict accumulator
1704 postscanr' :: (Vector v a, Vector v b) => (a -> b -> b) -> b -> v a -> v b
1705 {-# INLINE postscanr' #-}
1706 postscanr' f z = unstreamR . inplace (S.postscanl' (flip f) z) id . streamR
1707
1708 -- | /O(n)/ Right-to-left Haskell-style scan
1709 scanr :: (Vector v a, Vector v b) => (a -> b -> b) -> b -> v a -> v b
1710 {-# INLINE scanr #-}
1711 scanr f z = unstreamR . Bundle.scanl (flip f) z . streamR
1712
1713 -- | /O(n)/ Right-to-left Haskell-style scan with strict accumulator
1714 scanr' :: (Vector v a, Vector v b) => (a -> b -> b) -> b -> v a -> v b
1715 {-# INLINE scanr' #-}
1716 scanr' f z = unstreamR . Bundle.scanl' (flip f) z . streamR
1717
1718 -- | /O(n)/ Right-to-left scan over a non-empty vector
1719 scanr1 :: Vector v a => (a -> a -> a) -> v a -> v a
1720 {-# INLINE scanr1 #-}
1721 scanr1 f = unstreamR . inplace (S.scanl1 (flip f)) id . streamR
1722
1723 -- | /O(n)/ Right-to-left scan over a non-empty vector with a strict
1724 -- accumulator
1725 scanr1' :: Vector v a => (a -> a -> a) -> v a -> v a
1726 {-# INLINE scanr1' #-}
1727 scanr1' f = unstreamR . inplace (S.scanl1' (flip f)) id . streamR
1728
1729 -- Conversions - Lists
1730 -- ------------------------
1731
1732 -- | /O(n)/ Convert a vector to a list
1733 toList :: Vector v a => v a -> [a]
1734 {-# INLINE toList #-}
1735 toList = Bundle.toList . stream
1736
1737 -- | /O(n)/ Convert a list to a vector
1738 fromList :: Vector v a => [a] -> v a
1739 {-# INLINE fromList #-}
1740 fromList = unstream . Bundle.fromList
1741
1742 -- | /O(n)/ Convert the first @n@ elements of a list to a vector
1743 --
1744 -- @
1745 -- fromListN n xs = 'fromList' ('take' n xs)
1746 -- @
1747 fromListN :: Vector v a => Int -> [a] -> v a
1748 {-# INLINE fromListN #-}
1749 fromListN n = unstream . Bundle.fromListN n
1750
1751 -- Conversions - Immutable vectors
1752 -- -------------------------------
1753
1754 -- | /O(n)/ Convert different vector types
1755 convert :: (Vector v a, Vector w a) => v a -> w a
1756 {-# INLINE convert #-}
1757 convert = unstream . Bundle.reVector . stream
1758
1759 -- Conversions - Mutable vectors
1760 -- -----------------------------
1761
1762 -- | /O(1)/ Unsafe convert a mutable vector to an immutable one without
1763 -- copying. The mutable vector may not be used after this operation.
1764 unsafeFreeze
1765 :: (PrimMonad m, Vector v a) => Mutable v (PrimState m) a -> m (v a)
1766 {-# INLINE unsafeFreeze #-}
1767 unsafeFreeze = basicUnsafeFreeze
1768
1769 -- | /O(n)/ Yield an immutable copy of the mutable vector.
1770 freeze :: (PrimMonad m, Vector v a) => Mutable v (PrimState m) a -> m (v a)
1771 {-# INLINE freeze #-}
1772 freeze mv = unsafeFreeze =<< M.clone mv
1773
1774 -- | /O(1)/ Unsafely convert an immutable vector to a mutable one without
1775 -- copying. The immutable vector may not be used after this operation.
1776 unsafeThaw :: (PrimMonad m, Vector v a) => v a -> m (Mutable v (PrimState m) a)
1777 {-# INLINE_FUSED unsafeThaw #-}
1778 unsafeThaw = basicUnsafeThaw
1779
1780 -- | /O(n)/ Yield a mutable copy of the immutable vector.
1781 thaw :: (PrimMonad m, Vector v a) => v a -> m (Mutable v (PrimState m) a)
1782 {-# INLINE_FUSED thaw #-}
1783 thaw v = do
1784 mv <- M.unsafeNew (length v)
1785 unsafeCopy mv v
1786 return mv
1787
1788 {-# RULES
1789
1790 "unsafeThaw/new [Vector]" forall p.
1791 unsafeThaw (new p) = New.runPrim p
1792
1793 "thaw/new [Vector]" forall p.
1794 thaw (new p) = New.runPrim p
1795
1796 #-}
1797
1798 {-
1799 -- | /O(n)/ Yield a mutable vector containing copies of each vector in the
1800 -- list.
1801 thawMany :: (PrimMonad m, Vector v a) => [v a] -> m (Mutable v (PrimState m) a)
1802 {-# INLINE_FUSED thawMany #-}
1803 -- FIXME: add rule for (stream (new (New.create (thawMany vs))))
1804 -- NOTE: We don't try to consume the list lazily as this wouldn't significantly
1805 -- change the space requirements anyway.
1806 thawMany vs = do
1807 mv <- M.new n
1808 thaw_loop mv vs
1809 return mv
1810 where
1811 n = List.foldl' (\k v -> k + length v) 0 vs
1812
1813 thaw_loop mv [] = mv `seq` return ()
1814 thaw_loop mv (v:vs)
1815 = do
1816 let n = length v
1817 unsafeCopy (M.unsafeTake n mv) v
1818 thaw_loop (M.unsafeDrop n mv) vs
1819 -}
1820
1821 -- | /O(n)/ Copy an immutable vector into a mutable one. The two vectors must
1822 -- have the same length.
1823 copy
1824 :: (PrimMonad m, Vector v a) => Mutable v (PrimState m) a -> v a -> m ()
1825 {-# INLINE copy #-}
1826 copy dst src = BOUNDS_CHECK(check) "copy" "length mismatch"
1827 (M.length dst == length src)
1828 $ unsafeCopy dst src
1829
1830 -- | /O(n)/ Copy an immutable vector into a mutable one. The two vectors must
1831 -- have the same length. This is not checked.
1832 unsafeCopy
1833 :: (PrimMonad m, Vector v a) => Mutable v (PrimState m) a -> v a -> m ()
1834 {-# INLINE unsafeCopy #-}
1835 unsafeCopy dst src = UNSAFE_CHECK(check) "unsafeCopy" "length mismatch"
1836 (M.length dst == length src)
1837 $ (dst `seq` src `seq` basicUnsafeCopy dst src)
1838
1839 -- Conversions to/from Bundles
1840 -- ---------------------------
1841
1842 -- | /O(1)/ Convert a vector to a 'Bundle'
1843 stream :: Vector v a => v a -> Bundle v a
1844 {-# INLINE_FUSED stream #-}
1845 stream v = Bundle.fromVector v
1846
1847 {-
1848 stream v = v `seq` n `seq` (Bundle.unfoldr get 0 `Bundle.sized` Exact n)
1849 where
1850 n = length v
1851
1852 -- NOTE: the False case comes first in Core so making it the recursive one
1853 -- makes the code easier to read
1854 {-# INLINE get #-}
1855 get i | i >= n = Nothing
1856 | otherwise = case basicUnsafeIndexM v i of Box x -> Just (x, i+1)
1857 -}
1858
1859 -- | /O(n)/ Construct a vector from a 'Bundle'
1860 unstream :: Vector v a => Bundle v a -> v a
1861 {-# INLINE unstream #-}
1862 unstream s = new (New.unstream s)
1863
1864 {-# RULES
1865
1866 "stream/unstream [Vector]" forall s.
1867 stream (new (New.unstream s)) = s
1868
1869 "New.unstream/stream [Vector]" forall v.
1870 New.unstream (stream v) = clone v
1871
1872 "clone/new [Vector]" forall p.
1873 clone (new p) = p
1874
1875 "inplace [Vector]"
1876 forall (f :: forall m. Monad m => Stream m a -> Stream m a) g m.
1877 New.unstream (inplace f g (stream (new m))) = New.transform f g m
1878
1879 "uninplace [Vector]"
1880 forall (f :: forall m. Monad m => Stream m a -> Stream m a) g m.
1881 stream (new (New.transform f g m)) = inplace f g (stream (new m))
1882
1883 #-}
1884
1885 -- | /O(1)/ Convert a vector to a 'Bundle', proceeding from right to left
1886 streamR :: Vector v a => v a -> Bundle u a
1887 {-# INLINE_FUSED streamR #-}
1888 streamR v = v `seq` n `seq` (Bundle.unfoldr get n `Bundle.sized` Exact n)
1889 where
1890 n = length v
1891
1892 {-# INLINE get #-}
1893 get 0 = Nothing
1894 get i = let i' = i-1
1895 in
1896 case basicUnsafeIndexM v i' of Box x -> Just (x, i')
1897
1898 -- | /O(n)/ Construct a vector from a 'Bundle', proceeding from right to left
1899 unstreamR :: Vector v a => Bundle v a -> v a
1900 {-# INLINE unstreamR #-}
1901 unstreamR s = new (New.unstreamR s)
1902
1903 {-# RULES
1904
1905 "streamR/unstreamR [Vector]" forall s.
1906 streamR (new (New.unstreamR s)) = s
1907
1908 "New.unstreamR/streamR/new [Vector]" forall p.
1909 New.unstreamR (streamR (new p)) = p
1910
1911 "New.unstream/streamR/new [Vector]" forall p.
1912 New.unstream (streamR (new p)) = New.modify M.reverse p
1913
1914 "New.unstreamR/stream/new [Vector]" forall p.
1915 New.unstreamR (stream (new p)) = New.modify M.reverse p
1916
1917 "inplace right [Vector]"
1918 forall (f :: forall m. Monad m => Stream m a -> Stream m a) g m.
1919 New.unstreamR (inplace f g (streamR (new m))) = New.transformR f g m
1920
1921 "uninplace right [Vector]"
1922 forall (f :: forall m. Monad m => Stream m a -> Stream m a) g m.
1923 streamR (new (New.transformR f g m)) = inplace f g (streamR (new m))
1924
1925 #-}
1926
1927 unstreamM :: (Monad m, Vector v a) => MBundle m u a -> m (v a)
1928 {-# INLINE_FUSED unstreamM #-}
1929 unstreamM s = do
1930 xs <- MBundle.toList s
1931 return $ unstream $ Bundle.unsafeFromList (MBundle.size s) xs
1932
1933 unstreamPrimM :: (PrimMonad m, Vector v a) => MBundle m u a -> m (v a)
1934 {-# INLINE_FUSED unstreamPrimM #-}
1935 unstreamPrimM s = M.munstream s >>= unsafeFreeze
1936
1937 -- FIXME: the next two functions are only necessary for the specialisations
1938 unstreamPrimM_IO :: Vector v a => MBundle IO u a -> IO (v a)
1939 {-# INLINE unstreamPrimM_IO #-}
1940 unstreamPrimM_IO = unstreamPrimM
1941
1942 unstreamPrimM_ST :: Vector v a => MBundle (ST s) u a -> ST s (v a)
1943 {-# INLINE unstreamPrimM_ST #-}
1944 unstreamPrimM_ST = unstreamPrimM
1945
1946 {-# RULES
1947
1948 "unstreamM[IO]" unstreamM = unstreamPrimM_IO
1949 "unstreamM[ST]" unstreamM = unstreamPrimM_ST
1950
1951 #-}
1952
1953
1954 -- Recycling support
1955 -- -----------------
1956
1957 -- | Construct a vector from a monadic initialiser.
1958 new :: Vector v a => New v a -> v a
1959 {-# INLINE_FUSED new #-}
1960 new m = m `seq` runST (unsafeFreeze =<< New.run m)
1961
1962 -- | Convert a vector to an initialiser which, when run, produces a copy of
1963 -- the vector.
1964 clone :: Vector v a => v a -> New v a
1965 {-# INLINE_FUSED clone #-}
1966 clone v = v `seq` New.create (
1967 do
1968 mv <- M.new (length v)
1969 unsafeCopy mv v
1970 return mv)
1971
1972 -- Comparisons
1973 -- -----------
1974
1975 -- | /O(n)/ Check if two vectors are equal. All 'Vector' instances are also
1976 -- instances of 'Eq' and it is usually more appropriate to use those. This
1977 -- function is primarily intended for implementing 'Eq' instances for new
1978 -- vector types.
1979 eq :: (Vector v a, Eq a) => v a -> v a -> Bool
1980 {-# INLINE eq #-}
1981 xs `eq` ys = stream xs == stream ys
1982
1983 -- | /O(n)/ Compare two vectors lexicographically. All 'Vector' instances are
1984 -- also instances of 'Ord' and it is usually more appropriate to use those. This
1985 -- function is primarily intended for implementing 'Ord' instances for new
1986 -- vector types.
1987 cmp :: (Vector v a, Ord a) => v a -> v a -> Ordering
1988 {-# INLINE cmp #-}
1989 cmp xs ys = compare (stream xs) (stream ys)
1990
1991 -- Show
1992 -- ----
1993
1994 -- | Generic definition of 'Prelude.showsPrec'
1995 showsPrec :: (Vector v a, Show a) => Int -> v a -> ShowS
1996 {-# INLINE showsPrec #-}
1997 showsPrec p v = showParen (p > 10) $ showString "fromList " . shows (toList v)
1998
1999 -- | Generic definition of 'Text.Read.readPrec'
2000 readPrec :: (Vector v a, Read a) => Read.ReadPrec (v a)
2001 {-# INLINE readPrec #-}
2002 readPrec = Read.parens $ Read.prec 10 $ do
2003 Read.Ident "fromList" <- Read.lexP
2004 xs <- Read.readPrec
2005 return (fromList xs)
2006
2007 -- Data and Typeable
2008 -- -----------------
2009
2010 -- | Generic definion of 'Data.Data.gfoldl' that views a 'Vector' as a
2011 -- list.
2012 gfoldl :: (Vector v a, Data a)
2013 => (forall d b. Data d => c (d -> b) -> d -> c b)
2014 -> (forall g. g -> c g)
2015 -> v a
2016 -> c (v a)
2017 {-# INLINE gfoldl #-}
2018 gfoldl f z v = z fromList `f` toList v
2019
2020 mkType :: String -> DataType
2021 {-# INLINE mkType #-}
2022 mkType = mkNoRepType
2023
2024 dataCast :: (Vector v a, Data a, Typeable1 v, Typeable1 t)
2025 => (forall d. Data d => c (t d)) -> Maybe (c (v a))
2026 {-# INLINE dataCast #-}
2027 dataCast f = gcast1 f
2028