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