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