Fix doc typo
[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 {-# INLINE replicateM #-}
624 replicateM n m = unstreamM (MStream.replicateM n m)
625
626 -- | Execute the monadic action and freeze the resulting vector.
627 --
628 -- @
629 -- create (do { v \<- 'M.new' 2; 'M.write' v 0 \'a\'; 'M.write' v 1 \'b\' }) = \<'a','b'\>
630 -- @
631 create :: Vector v a => (forall s. ST s (Mutable v s a)) -> v a
632 {-# INLINE create #-}
633 create p = new (New.create p)
634
635 -- Restricting memory usage
636 -- ------------------------
637
638 -- | /O(n)/ Yield the argument but force it not to retain any extra memory,
639 -- possibly by copying it.
640 --
641 -- This is especially useful when dealing with slices. For example:
642 --
643 -- > force (slice 0 2 <huge vector>)
644 --
645 -- Here, the slice retains a reference to the huge vector. Forcing it creates
646 -- a copy of just the elements that belong to the slice and allows the huge
647 -- vector to be garbage collected.
648 force :: Vector v a => v a -> v a
649 -- FIXME: we probably ought to inline this later as the rules still might fire
650 -- otherwise
651 {-# INLINE_STREAM force #-}
652 force v = new (clone v)
653
654 -- Bulk updates
655 -- ------------
656
657 -- | /O(m+n)/ For each pair @(i,a)@ from the list, replace the vector
658 -- element at position @i@ by @a@.
659 --
660 -- > <5,9,2,7> // [(2,1),(0,3),(2,8)] = <3,9,8,7>
661 --
662 (//) :: Vector v a => v a -- ^ initial vector (of length @m@)
663 -> [(Int, a)] -- ^ list of index/value pairs (of length @n@)
664 -> v a
665 {-# INLINE (//) #-}
666 v // us = update_stream v (Stream.fromList us)
667
668 -- | /O(m+n)/ For each pair @(i,a)@ from the vector of index/value pairs,
669 -- replace the vector element at position @i@ by @a@.
670 --
671 -- > update <5,9,2,7> <(2,1),(0,3),(2,8)> = <3,9,8,7>
672 --
673 update :: (Vector v a, Vector v (Int, a))
674 => v a -- ^ initial vector (of length @m@)
675 -> v (Int, a) -- ^ vector of index/value pairs (of length @n@)
676 -> v a
677 {-# INLINE update #-}
678 update v w = update_stream v (stream w)
679
680 -- | /O(m+min(n1,n2))/ For each index @i@ from the index vector and the
681 -- corresponding value @a@ from the value vector, replace the element of the
682 -- initial vector at position @i@ by @a@.
683 --
684 -- > update_ <5,9,2,7> <2,0,2> <1,3,8> = <3,9,8,7>
685 --
686 -- This function is useful for instances of 'Vector' that cannot store pairs.
687 -- Otherwise, 'update' is probably more convenient.
688 --
689 -- @
690 -- update_ xs is ys = 'update' xs ('zip' is ys)
691 -- @
692 update_ :: (Vector v a, Vector v Int)
693 => v a -- ^ initial vector (of length @m@)
694 -> v Int -- ^ index vector (of length @n1@)
695 -> v a -- ^ value vector (of length @n2@)
696 -> v a
697 {-# INLINE update_ #-}
698 update_ v is w = update_stream v (Stream.zipWith (,) (stream is) (stream w))
699
700 update_stream :: Vector v a => v a -> Stream (Int,a) -> v a
701 {-# INLINE update_stream #-}
702 update_stream = modifyWithStream M.update
703
704 -- | Same as ('//') but without bounds checking.
705 unsafeUpd :: Vector v a => v a -> [(Int, a)] -> v a
706 {-# INLINE unsafeUpd #-}
707 unsafeUpd v us = unsafeUpdate_stream v (Stream.fromList us)
708
709 -- | Same as 'update' but without bounds checking.
710 unsafeUpdate :: (Vector v a, Vector v (Int, a)) => v a -> v (Int, a) -> v a
711 {-# INLINE unsafeUpdate #-}
712 unsafeUpdate v w = unsafeUpdate_stream v (stream w)
713
714 -- | Same as 'update_' but without bounds checking.
715 unsafeUpdate_ :: (Vector v a, Vector v Int) => v a -> v Int -> v a -> v a
716 {-# INLINE unsafeUpdate_ #-}
717 unsafeUpdate_ v is w
718 = unsafeUpdate_stream v (Stream.zipWith (,) (stream is) (stream w))
719
720 unsafeUpdate_stream :: Vector v a => v a -> Stream (Int,a) -> v a
721 {-# INLINE unsafeUpdate_stream #-}
722 unsafeUpdate_stream = modifyWithStream M.unsafeUpdate
723
724 -- Accumulations
725 -- -------------
726
727 -- | /O(m+n)/ For each pair @(i,b)@ from the list, replace the vector element
728 -- @a@ at position @i@ by @f a b@.
729 --
730 -- > accum (+) <5,9,2> [(2,4),(1,6),(0,3),(1,7)] = <5+3, 9+6+7, 2+4>
731 accum :: Vector v a
732 => (a -> b -> a) -- ^ accumulating function @f@
733 -> v a -- ^ initial vector (of length @m@)
734 -> [(Int,b)] -- ^ list of index/value pairs (of length @n@)
735 -> v a
736 {-# INLINE accum #-}
737 accum f v us = accum_stream f v (Stream.fromList us)
738
739 -- | /O(m+n)/ For each pair @(i,b)@ from the vector of pairs, replace the vector
740 -- element @a@ at position @i@ by @f a b@.
741 --
742 -- > accumulate (+) <5,9,2> <(2,4),(1,6),(0,3),(1,7)> = <5+3, 9+6+7, 2+4>
743 accumulate :: (Vector v a, Vector v (Int, b))
744 => (a -> b -> a) -- ^ accumulating function @f@
745 -> v a -- ^ initial vector (of length @m@)
746 -> v (Int,b) -- ^ vector of index/value pairs (of length @n@)
747 -> v a
748 {-# INLINE accumulate #-}
749 accumulate f v us = accum_stream f v (stream us)
750
751 -- | /O(m+min(n1,n2))/ For each index @i@ from the index vector and the
752 -- corresponding value @b@ from the the value vector,
753 -- replace the element of the initial vector at
754 -- position @i@ by @f a b@.
755 --
756 -- > accumulate_ (+) <5,9,2> <2,1,0,1> <4,6,3,7> = <5+3, 9+6+7, 2+4>
757 --
758 -- This function is useful for instances of 'Vector' that cannot store pairs.
759 -- Otherwise, 'accumulate' is probably more convenient:
760 --
761 -- @
762 -- accumulate_ f as is bs = 'accumulate' f as ('zip' is bs)
763 -- @
764 accumulate_ :: (Vector v a, Vector v Int, Vector v b)
765 => (a -> b -> a) -- ^ accumulating function @f@
766 -> v a -- ^ initial vector (of length @m@)
767 -> v Int -- ^ index vector (of length @n1@)
768 -> v b -- ^ value vector (of length @n2@)
769 -> v a
770 {-# INLINE accumulate_ #-}
771 accumulate_ f v is xs = accum_stream f v (Stream.zipWith (,) (stream is)
772 (stream xs))
773
774
775 accum_stream :: Vector v a => (a -> b -> a) -> v a -> Stream (Int,b) -> v a
776 {-# INLINE accum_stream #-}
777 accum_stream f = modifyWithStream (M.accum f)
778
779 -- | Same as 'accum' but without bounds checking.
780 unsafeAccum :: Vector v a => (a -> b -> a) -> v a -> [(Int,b)] -> v a
781 {-# INLINE unsafeAccum #-}
782 unsafeAccum f v us = unsafeAccum_stream f v (Stream.fromList us)
783
784 -- | Same as 'accumulate' but without bounds checking.
785 unsafeAccumulate :: (Vector v a, Vector v (Int, b))
786 => (a -> b -> a) -> v a -> v (Int,b) -> v a
787 {-# INLINE unsafeAccumulate #-}
788 unsafeAccumulate f v us = unsafeAccum_stream f v (stream us)
789
790 -- | Same as 'accumulate_' but without bounds checking.
791 unsafeAccumulate_ :: (Vector v a, Vector v Int, Vector v b)
792 => (a -> b -> a) -> v a -> v Int -> v b -> v a
793 {-# INLINE unsafeAccumulate_ #-}
794 unsafeAccumulate_ f v is xs
795 = unsafeAccum_stream f v (Stream.zipWith (,) (stream is) (stream xs))
796
797 unsafeAccum_stream
798 :: Vector v a => (a -> b -> a) -> v a -> Stream (Int,b) -> v a
799 {-# INLINE unsafeAccum_stream #-}
800 unsafeAccum_stream f = modifyWithStream (M.unsafeAccum f)
801
802 -- Permutations
803 -- ------------
804
805 -- | /O(n)/ Reverse a vector
806 reverse :: (Vector v a) => v a -> v a
807 {-# INLINE reverse #-}
808 -- FIXME: make this fuse better, add support for recycling
809 reverse = unstream . streamR
810
811 -- | /O(n)/ Yield the vector obtained by replacing each element @i@ of the
812 -- index vector by @xs'!'i@. This is equivalent to @'map' (xs'!') is@ but is
813 -- often much more efficient.
814 --
815 -- > backpermute <a,b,c,d> <0,3,2,3,1,0> = <a,d,c,d,b,a>
816 backpermute :: (Vector v a, Vector v Int)
817 => v a -- ^ @xs@ value vector
818 -> v Int -- ^ @is@ index vector (of length @n@)
819 -> v a
820 {-# INLINE backpermute #-}
821 -- This somewhat non-intuitive definition ensures that the resulting vector
822 -- does not retain references to the original one even if it is lazy in its
823 -- elements. This would not be the case if we simply used map (v!)
824 backpermute v is = seq v
825 $ seq n
826 $ unstream
827 $ Stream.unbox
828 $ Stream.map index
829 $ stream is
830 where
831 n = length v
832
833 {-# INLINE index #-}
834 -- NOTE: we do it this way to avoid triggering LiberateCase on n in
835 -- polymorphic code
836 index i = BOUNDS_CHECK(checkIndex) "backpermute" i n
837 $ basicUnsafeIndexM v i
838
839 -- | Same as 'backpermute' but without bounds checking.
840 unsafeBackpermute :: (Vector v a, Vector v Int) => v a -> v Int -> v a
841 {-# INLINE unsafeBackpermute #-}
842 unsafeBackpermute v is = seq v
843 $ seq n
844 $ unstream
845 $ Stream.unbox
846 $ Stream.map index
847 $ stream is
848 where
849 n = length v
850
851 {-# INLINE index #-}
852 -- NOTE: we do it this way to avoid triggering LiberateCase on n in
853 -- polymorphic code
854 index i = UNSAFE_CHECK(checkIndex) "unsafeBackpermute" i n
855 $ basicUnsafeIndexM v i
856
857 -- Safe destructive updates
858 -- ------------------------
859
860 -- | Apply a destructive operation to a vector. The operation will be
861 -- performed in place if it is safe to do so and will modify a copy of the
862 -- vector otherwise.
863 --
864 -- @
865 -- modify (\\v -> 'M.write' v 0 \'x\') ('replicate' 3 \'a\') = \<\'x\',\'a\',\'a\'\>
866 -- @
867 modify :: Vector v a => (forall s. Mutable v s a -> ST s ()) -> v a -> v a
868 {-# INLINE modify #-}
869 modify p = new . New.modify p . clone
870
871 -- We have to make sure that this is strict in the stream but we can't seq on
872 -- it while fusion is happening. Hence this ugliness.
873 modifyWithStream :: Vector v a
874 => (forall s. Mutable v s a -> Stream b -> ST s ())
875 -> v a -> Stream b -> v a
876 {-# INLINE modifyWithStream #-}
877 modifyWithStream p v s = new (New.modifyWithStream p (clone v) s)
878
879 -- Indexing
880 -- --------
881
882 -- | /O(n)/ Pair each element in a vector with its index
883 indexed :: (Vector v a, Vector v (Int,a)) => v a -> v (Int,a)
884 {-# INLINE indexed #-}
885 indexed = unstream . Stream.indexed . stream
886
887 -- Mapping
888 -- -------
889
890 -- | /O(n)/ Map a function over a vector
891 map :: (Vector v a, Vector v b) => (a -> b) -> v a -> v b
892 {-# INLINE map #-}
893 map f = unstream . inplace (MStream.map f) . stream
894
895 -- | /O(n)/ Apply a function to every element of a vector and its index
896 imap :: (Vector v a, Vector v b) => (Int -> a -> b) -> v a -> v b
897 {-# INLINE imap #-}
898 imap f = unstream . inplace (MStream.map (uncurry f) . MStream.indexed)
899 . stream
900
901 -- | Map a function over a vector and concatenate the results.
902 concatMap :: (Vector v a, Vector v b) => (a -> v b) -> v a -> v b
903 {-# INLINE concatMap #-}
904 -- NOTE: We can't fuse concatMap anyway so don't pretend we do.
905 -- concatMap f = unstream . Stream.concatMap (stream . f) . stream
906 concatMap f = concat . Stream.toList . Stream.map f . stream
907
908 -- Monadic mapping
909 -- ---------------
910
911 -- | /O(n)/ Apply the monadic action to all elements of the vector, yielding a
912 -- vector of results
913 mapM :: (Monad m, Vector v a, Vector v b) => (a -> m b) -> v a -> m (v b)
914 {-# INLINE mapM #-}
915 mapM f = unstreamM . Stream.mapM f . stream
916
917 -- | /O(n)/ Apply the monadic action to all elements of a vector and ignore the
918 -- results
919 mapM_ :: (Monad m, Vector v a) => (a -> m b) -> v a -> m ()
920 {-# INLINE mapM_ #-}
921 mapM_ f = Stream.mapM_ f . stream
922
923 -- | /O(n)/ Apply the monadic action to all elements of the vector, yielding a
924 -- vector of results. Equvalent to @flip 'mapM'@.
925 forM :: (Monad m, Vector v a, Vector v b) => v a -> (a -> m b) -> m (v b)
926 {-# INLINE forM #-}
927 forM as f = mapM f as
928
929 -- | /O(n)/ Apply the monadic action to all elements of a vector and ignore the
930 -- results. Equivalent to @flip 'mapM_'@.
931 forM_ :: (Monad m, Vector v a) => v a -> (a -> m b) -> m ()
932 {-# INLINE forM_ #-}
933 forM_ as f = mapM_ f as
934
935 -- Zipping
936 -- -------
937
938 -- | /O(min(m,n))/ Zip two vectors with the given function.
939 zipWith :: (Vector v a, Vector v b, Vector v c)
940 => (a -> b -> c) -> v a -> v b -> v c
941 {-# INLINE zipWith #-}
942 zipWith f xs ys = unstream (Stream.zipWith f (stream xs) (stream ys))
943
944 -- | Zip three vectors with the given function.
945 zipWith3 :: (Vector v a, Vector v b, Vector v c, Vector v d)
946 => (a -> b -> c -> d) -> v a -> v b -> v c -> v d
947 {-# INLINE zipWith3 #-}
948 zipWith3 f as bs cs = unstream (Stream.zipWith3 f (stream as)
949 (stream bs)
950 (stream cs))
951
952 zipWith4 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e)
953 => (a -> b -> c -> d -> e) -> v a -> v b -> v c -> v d -> v e
954 {-# INLINE zipWith4 #-}
955 zipWith4 f as bs cs ds
956 = unstream (Stream.zipWith4 f (stream as)
957 (stream bs)
958 (stream cs)
959 (stream ds))
960
961 zipWith5 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e,
962 Vector v f)
963 => (a -> b -> c -> d -> e -> f) -> v a -> v b -> v c -> v d -> v e
964 -> v f
965 {-# INLINE zipWith5 #-}
966 zipWith5 f as bs cs ds es
967 = unstream (Stream.zipWith5 f (stream as)
968 (stream bs)
969 (stream cs)
970 (stream ds)
971 (stream es))
972
973 zipWith6 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e,
974 Vector v f, Vector v g)
975 => (a -> b -> c -> d -> e -> f -> g)
976 -> v a -> v b -> v c -> v d -> v e -> v f -> v g
977 {-# INLINE zipWith6 #-}
978 zipWith6 f as bs cs ds es fs
979 = unstream (Stream.zipWith6 f (stream as)
980 (stream bs)
981 (stream cs)
982 (stream ds)
983 (stream es)
984 (stream fs))
985
986 -- | /O(min(m,n))/ Zip two vectors with a function that also takes the
987 -- elements' indices.
988 izipWith :: (Vector v a, Vector v b, Vector v c)
989 => (Int -> a -> b -> c) -> v a -> v b -> v c
990 {-# INLINE izipWith #-}
991 izipWith f xs ys = unstream
992 (Stream.zipWith (uncurry f) (Stream.indexed (stream xs))
993 (stream ys))
994
995 izipWith3 :: (Vector v a, Vector v b, Vector v c, Vector v d)
996 => (Int -> a -> b -> c -> d) -> v a -> v b -> v c -> v d
997 {-# INLINE izipWith3 #-}
998 izipWith3 f as bs cs
999 = unstream (Stream.zipWith3 (uncurry f) (Stream.indexed (stream as))
1000 (stream bs)
1001 (stream cs))
1002
1003 izipWith4 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e)
1004 => (Int -> a -> b -> c -> d -> e) -> v a -> v b -> v c -> v d -> v e
1005 {-# INLINE izipWith4 #-}
1006 izipWith4 f as bs cs ds
1007 = unstream (Stream.zipWith4 (uncurry f) (Stream.indexed (stream as))
1008 (stream bs)
1009 (stream cs)
1010 (stream ds))
1011
1012 izipWith5 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e,
1013 Vector v f)
1014 => (Int -> a -> b -> c -> d -> e -> f) -> v a -> v b -> v c -> v d
1015 -> v e -> v f
1016 {-# INLINE izipWith5 #-}
1017 izipWith5 f as bs cs ds es
1018 = unstream (Stream.zipWith5 (uncurry f) (Stream.indexed (stream as))
1019 (stream bs)
1020 (stream cs)
1021 (stream ds)
1022 (stream es))
1023
1024 izipWith6 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e,
1025 Vector v f, Vector v g)
1026 => (Int -> a -> b -> c -> d -> e -> f -> g)
1027 -> v a -> v b -> v c -> v d -> v e -> v f -> v g
1028 {-# INLINE izipWith6 #-}
1029 izipWith6 f as bs cs ds es fs
1030 = unstream (Stream.zipWith6 (uncurry f) (Stream.indexed (stream as))
1031 (stream bs)
1032 (stream cs)
1033 (stream ds)
1034 (stream es)
1035 (stream fs))
1036
1037 -- | /O(min(m,n))/ Zip two vectors
1038 zip :: (Vector v a, Vector v b, Vector v (a,b)) => v a -> v b -> v (a, b)
1039 {-# INLINE zip #-}
1040 zip = zipWith (,)
1041
1042 zip3 :: (Vector v a, Vector v b, Vector v c, Vector v (a, b, c))
1043 => v a -> v b -> v c -> v (a, b, c)
1044 {-# INLINE zip3 #-}
1045 zip3 = zipWith3 (,,)
1046
1047 zip4 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v (a, b, c, d))
1048 => v a -> v b -> v c -> v d -> v (a, b, c, d)
1049 {-# INLINE zip4 #-}
1050 zip4 = zipWith4 (,,,)
1051
1052 zip5 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e,
1053 Vector v (a, b, c, d, e))
1054 => v a -> v b -> v c -> v d -> v e -> v (a, b, c, d, e)
1055 {-# INLINE zip5 #-}
1056 zip5 = zipWith5 (,,,,)
1057
1058 zip6 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e,
1059 Vector v f, Vector v (a, b, c, d, e, f))
1060 => v a -> v b -> v c -> v d -> v e -> v f -> v (a, b, c, d, e, f)
1061 {-# INLINE zip6 #-}
1062 zip6 = zipWith6 (,,,,,)
1063
1064 -- Monadic zipping
1065 -- ---------------
1066
1067 -- | /O(min(m,n))/ Zip the two vectors with the monadic action and yield a
1068 -- vector of results
1069 zipWithM :: (Monad m, Vector v a, Vector v b, Vector v c)
1070 => (a -> b -> m c) -> v a -> v b -> m (v c)
1071 -- FIXME: specialise for ST and IO?
1072 {-# INLINE zipWithM #-}
1073 zipWithM f as bs = unstreamM $ Stream.zipWithM f (stream as) (stream bs)
1074
1075 -- | /O(min(m,n))/ Zip the two vectors with the monadic action and ignore the
1076 -- results
1077 zipWithM_ :: (Monad m, Vector v a, Vector v b)
1078 => (a -> b -> m c) -> v a -> v b -> m ()
1079 {-# INLINE zipWithM_ #-}
1080 zipWithM_ f as bs = Stream.zipWithM_ f (stream as) (stream bs)
1081
1082 -- Unzipping
1083 -- ---------
1084
1085 -- | /O(min(m,n))/ Unzip a vector of pairs.
1086 unzip :: (Vector v a, Vector v b, Vector v (a,b)) => v (a, b) -> (v a, v b)
1087 {-# INLINE unzip #-}
1088 unzip xs = (map fst xs, map snd xs)
1089
1090 unzip3 :: (Vector v a, Vector v b, Vector v c, Vector v (a, b, c))
1091 => v (a, b, c) -> (v a, v b, v c)
1092 {-# INLINE unzip3 #-}
1093 unzip3 xs = (map (\(a, b, c) -> a) xs,
1094 map (\(a, b, c) -> b) xs,
1095 map (\(a, b, c) -> c) xs)
1096
1097 unzip4 :: (Vector v a, Vector v b, Vector v c, Vector v d,
1098 Vector v (a, b, c, d))
1099 => v (a, b, c, d) -> (v a, v b, v c, v d)
1100 {-# INLINE unzip4 #-}
1101 unzip4 xs = (map (\(a, b, c, d) -> a) xs,
1102 map (\(a, b, c, d) -> b) xs,
1103 map (\(a, b, c, d) -> c) xs,
1104 map (\(a, b, c, d) -> d) xs)
1105
1106 unzip5 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e,
1107 Vector v (a, b, c, d, e))
1108 => v (a, b, c, d, e) -> (v a, v b, v c, v d, v e)
1109 {-# INLINE unzip5 #-}
1110 unzip5 xs = (map (\(a, b, c, d, e) -> a) xs,
1111 map (\(a, b, c, d, e) -> b) xs,
1112 map (\(a, b, c, d, e) -> c) xs,
1113 map (\(a, b, c, d, e) -> d) xs,
1114 map (\(a, b, c, d, e) -> e) xs)
1115
1116 unzip6 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e,
1117 Vector v f, Vector v (a, b, c, d, e, f))
1118 => v (a, b, c, d, e, f) -> (v a, v b, v c, v d, v e, v f)
1119 {-# INLINE unzip6 #-}
1120 unzip6 xs = (map (\(a, b, c, d, e, f) -> a) xs,
1121 map (\(a, b, c, d, e, f) -> b) xs,
1122 map (\(a, b, c, d, e, f) -> c) xs,
1123 map (\(a, b, c, d, e, f) -> d) xs,
1124 map (\(a, b, c, d, e, f) -> e) xs,
1125 map (\(a, b, c, d, e, f) -> f) xs)
1126
1127 -- Filtering
1128 -- ---------
1129
1130 -- | /O(n)/ Drop elements that do not satisfy the predicate
1131 filter :: Vector v a => (a -> Bool) -> v a -> v a
1132 {-# INLINE filter #-}
1133 filter f = unstream . inplace (MStream.filter f) . stream
1134
1135 -- | /O(n)/ Drop elements that do not satisfy the predicate which is applied to
1136 -- values and their indices
1137 ifilter :: Vector v a => (Int -> a -> Bool) -> v a -> v a
1138 {-# INLINE ifilter #-}
1139 ifilter f = unstream
1140 . inplace (MStream.map snd . MStream.filter (uncurry f)
1141 . MStream.indexed)
1142 . stream
1143
1144 -- | /O(n)/ Drop elements that do not satisfy the monadic predicate
1145 filterM :: (Monad m, Vector v a) => (a -> m Bool) -> v a -> m (v a)
1146 {-# INLINE filterM #-}
1147 filterM f = unstreamM . Stream.filterM f . stream
1148
1149 -- | /O(n)/ Yield the longest prefix of elements satisfying the predicate
1150 -- without copying.
1151 takeWhile :: Vector v a => (a -> Bool) -> v a -> v a
1152 {-# INLINE takeWhile #-}
1153 takeWhile f = unstream . Stream.takeWhile f . stream
1154
1155 -- | /O(n)/ Drop the longest prefix of elements that satisfy the predicate
1156 -- without copying.
1157 dropWhile :: Vector v a => (a -> Bool) -> v a -> v a
1158 {-# INLINE dropWhile #-}
1159 dropWhile f = unstream . Stream.dropWhile f . stream
1160
1161 -- Parititioning
1162 -- -------------
1163
1164 -- | /O(n)/ Split the vector in two parts, the first one containing those
1165 -- elements that satisfy the predicate and the second one those that don't. The
1166 -- relative order of the elements is preserved at the cost of a sometimes
1167 -- reduced performance compared to 'unstablePartition'.
1168 partition :: Vector v a => (a -> Bool) -> v a -> (v a, v a)
1169 {-# INLINE partition #-}
1170 partition f = partition_stream f . stream
1171
1172 -- FIXME: Make this inplace-fusible (look at how stable_partition is
1173 -- implemented in C++)
1174
1175 partition_stream :: Vector v a => (a -> Bool) -> Stream a -> (v a, v a)
1176 {-# INLINE_STREAM partition_stream #-}
1177 partition_stream f s = s `seq` runST (
1178 do
1179 (mv1,mv2) <- M.partitionStream f s
1180 v1 <- unsafeFreeze mv1
1181 v2 <- unsafeFreeze mv2
1182 return (v1,v2))
1183
1184 -- | /O(n)/ Split the vector in two parts, the first one containing those
1185 -- elements that satisfy the predicate and the second one those that don't.
1186 -- The order of the elements is not preserved but the operation is often
1187 -- faster than 'partition'.
1188 unstablePartition :: Vector v a => (a -> Bool) -> v a -> (v a, v a)
1189 {-# INLINE unstablePartition #-}
1190 unstablePartition f = unstablePartition_stream f . stream
1191
1192 unstablePartition_stream
1193 :: Vector v a => (a -> Bool) -> Stream a -> (v a, v a)
1194 {-# INLINE_STREAM unstablePartition_stream #-}
1195 unstablePartition_stream f s = s `seq` runST (
1196 do
1197 (mv1,mv2) <- M.unstablePartitionStream f s
1198 v1 <- unsafeFreeze mv1
1199 v2 <- unsafeFreeze mv2
1200 return (v1,v2))
1201
1202 unstablePartition_new :: Vector v a => (a -> Bool) -> New v a -> (v a, v a)
1203 {-# INLINE_STREAM unstablePartition_new #-}
1204 unstablePartition_new f (New.New p) = runST (
1205 do
1206 mv <- p
1207 i <- M.unstablePartition f mv
1208 v <- unsafeFreeze mv
1209 return (unsafeTake i v, unsafeDrop i v))
1210
1211 {-# RULES
1212
1213 "unstablePartition" forall f p.
1214 unstablePartition_stream f (stream (new p))
1215 = unstablePartition_new f p
1216
1217 #-}
1218
1219
1220 -- FIXME: make span and break fusible
1221
1222 -- | /O(n)/ Split the vector into the longest prefix of elements that satisfy
1223 -- the predicate and the rest without copying.
1224 span :: Vector v a => (a -> Bool) -> v a -> (v a, v a)
1225 {-# INLINE span #-}
1226 span f = break (not . f)
1227
1228 -- | /O(n)/ Split the vector into the longest prefix of elements that do not
1229 -- satisfy the predicate and the rest without copying.
1230 break :: Vector v a => (a -> Bool) -> v a -> (v a, v a)
1231 {-# INLINE break #-}
1232 break f xs = case findIndex f xs of
1233 Just i -> (unsafeSlice 0 i xs, unsafeSlice i (length xs - i) xs)
1234 Nothing -> (xs, empty)
1235
1236
1237 -- Searching
1238 -- ---------
1239
1240 infix 4 `elem`
1241 -- | /O(n)/ Check if the vector contains an element
1242 elem :: (Vector v a, Eq a) => a -> v a -> Bool
1243 {-# INLINE elem #-}
1244 elem x = Stream.elem x . stream
1245
1246 infix 4 `notElem`
1247 -- | /O(n)/ Check if the vector does not contain an element (inverse of 'elem')
1248 notElem :: (Vector v a, Eq a) => a -> v a -> Bool
1249 {-# INLINE notElem #-}
1250 notElem x = Stream.notElem x . stream
1251
1252 -- | /O(n)/ Yield 'Just' the first element matching the predicate or 'Nothing'
1253 -- if no such element exists.
1254 find :: Vector v a => (a -> Bool) -> v a -> Maybe a
1255 {-# INLINE find #-}
1256 find f = Stream.find f . stream
1257
1258 -- | /O(n)/ Yield 'Just' the index of the first element matching the predicate
1259 -- or 'Nothing' if no such element exists.
1260 findIndex :: Vector v a => (a -> Bool) -> v a -> Maybe Int
1261 {-# INLINE findIndex #-}
1262 findIndex f = Stream.findIndex f . stream
1263
1264 -- | /O(n)/ Yield the indices of elements satisfying the predicate in ascending
1265 -- order.
1266 findIndices :: (Vector v a, Vector v Int) => (a -> Bool) -> v a -> v Int
1267 {-# INLINE findIndices #-}
1268 findIndices f = unstream
1269 . inplace (MStream.map fst . MStream.filter (f . snd)
1270 . MStream.indexed)
1271 . stream
1272
1273 -- | /O(n)/ Yield 'Just' the index of the first occurence of the given element or
1274 -- 'Nothing' if the vector does not contain the element. This is a specialised
1275 -- version of 'findIndex'.
1276 elemIndex :: (Vector v a, Eq a) => a -> v a -> Maybe Int
1277 {-# INLINE elemIndex #-}
1278 elemIndex x = findIndex (x==)
1279
1280 -- | /O(n)/ Yield the indices of all occurences of the given element in
1281 -- ascending order. This is a specialised version of 'findIndices'.
1282 elemIndices :: (Vector v a, Vector v Int, Eq a) => a -> v a -> v Int
1283 {-# INLINE elemIndices #-}
1284 elemIndices x = findIndices (x==)
1285
1286 -- Folding
1287 -- -------
1288
1289 -- | /O(n)/ Left fold
1290 foldl :: Vector v b => (a -> b -> a) -> a -> v b -> a
1291 {-# INLINE foldl #-}
1292 foldl f z = Stream.foldl f z . stream
1293
1294 -- | /O(n)/ Left fold on non-empty vectors
1295 foldl1 :: Vector v a => (a -> a -> a) -> v a -> a
1296 {-# INLINE foldl1 #-}
1297 foldl1 f = Stream.foldl1 f . stream
1298
1299 -- | /O(n)/ Left fold with strict accumulator
1300 foldl' :: Vector v b => (a -> b -> a) -> a -> v b -> a
1301 {-# INLINE foldl' #-}
1302 foldl' f z = Stream.foldl' f z . stream
1303
1304 -- | /O(n)/ Left fold on non-empty vectors with strict accumulator
1305 foldl1' :: Vector v a => (a -> a -> a) -> v a -> a
1306 {-# INLINE foldl1' #-}
1307 foldl1' f = Stream.foldl1' f . stream
1308
1309 -- | /O(n)/ Right fold
1310 foldr :: Vector v a => (a -> b -> b) -> b -> v a -> b
1311 {-# INLINE foldr #-}
1312 foldr f z = Stream.foldr f z . stream
1313
1314 -- | /O(n)/ Right fold on non-empty vectors
1315 foldr1 :: Vector v a => (a -> a -> a) -> v a -> a
1316 {-# INLINE foldr1 #-}
1317 foldr1 f = Stream.foldr1 f . stream
1318
1319 -- | /O(n)/ Right fold with a strict accumulator
1320 foldr' :: Vector v a => (a -> b -> b) -> b -> v a -> b
1321 {-# INLINE foldr' #-}
1322 foldr' f z = Stream.foldl' (flip f) z . streamR
1323
1324 -- | /O(n)/ Right fold on non-empty vectors with strict accumulator
1325 foldr1' :: Vector v a => (a -> a -> a) -> v a -> a
1326 {-# INLINE foldr1' #-}
1327 foldr1' f = Stream.foldl1' (flip f) . streamR
1328
1329 -- | /O(n)/ Left fold (function applied to each element and its index)
1330 ifoldl :: Vector v b => (a -> Int -> b -> a) -> a -> v b -> a
1331 {-# INLINE ifoldl #-}
1332 ifoldl f z = Stream.foldl (uncurry . f) z . Stream.indexed . stream
1333
1334 -- | /O(n)/ Left fold with strict accumulator (function applied to each element
1335 -- and its index)
1336 ifoldl' :: Vector v b => (a -> Int -> b -> a) -> a -> v b -> a
1337 {-# INLINE ifoldl' #-}
1338 ifoldl' f z = Stream.foldl' (uncurry . f) z . Stream.indexed . stream
1339
1340 -- | /O(n)/ Right fold (function applied to each element and its index)
1341 ifoldr :: Vector v a => (Int -> a -> b -> b) -> b -> v a -> b
1342 {-# INLINE ifoldr #-}
1343 ifoldr f z = Stream.foldr (uncurry f) z . Stream.indexed . stream
1344
1345 -- | /O(n)/ Right fold with strict accumulator (function applied to each
1346 -- element and its index)
1347 ifoldr' :: Vector v a => (Int -> a -> b -> b) -> b -> v a -> b
1348 {-# INLINE ifoldr' #-}
1349 ifoldr' f z xs = Stream.foldl' (flip (uncurry f)) z
1350 $ Stream.indexedR (length xs) $ streamR xs
1351
1352 -- Specialised folds
1353 -- -----------------
1354
1355 -- | /O(n)/ Check if all elements satisfy the predicate.
1356 all :: Vector v a => (a -> Bool) -> v a -> Bool
1357 {-# INLINE all #-}
1358 all f = Stream.and . Stream.map f . stream
1359
1360 -- | /O(n)/ Check if any element satisfies the predicate.
1361 any :: Vector v a => (a -> Bool) -> v a -> Bool
1362 {-# INLINE any #-}
1363 any f = Stream.or . Stream.map f . stream
1364
1365 -- | /O(n)/ Check if all elements are 'True'
1366 and :: Vector v Bool => v Bool -> Bool
1367 {-# INLINE and #-}
1368 and = Stream.and . stream
1369
1370 -- | /O(n)/ Check if any element is 'True'
1371 or :: Vector v Bool => v Bool -> Bool
1372 {-# INLINE or #-}
1373 or = Stream.or . stream
1374
1375 -- | /O(n)/ Compute the sum of the elements
1376 sum :: (Vector v a, Num a) => v a -> a
1377 {-# INLINE sum #-}
1378 sum = Stream.foldl' (+) 0 . stream
1379
1380 -- | /O(n)/ Compute the produce of the elements
1381 product :: (Vector v a, Num a) => v a -> a
1382 {-# INLINE product #-}
1383 product = Stream.foldl' (*) 1 . stream
1384
1385 -- | /O(n)/ Yield the maximum element of the vector. The vector may not be
1386 -- empty.
1387 maximum :: (Vector v a, Ord a) => v a -> a
1388 {-# INLINE maximum #-}
1389 maximum = Stream.foldl1' max . stream
1390
1391 -- | /O(n)/ Yield the maximum element of the vector according to the given
1392 -- comparison function. The vector may not be empty.
1393 maximumBy :: Vector v a => (a -> a -> Ordering) -> v a -> a
1394 {-# INLINE maximumBy #-}
1395 maximumBy cmp = Stream.foldl1' maxBy . stream
1396 where
1397 {-# INLINE maxBy #-}
1398 maxBy x y = case cmp x y of
1399 LT -> y
1400 _ -> x
1401
1402 -- | /O(n)/ Yield the minimum element of the vector. The vector may not be
1403 -- empty.
1404 minimum :: (Vector v a, Ord a) => v a -> a
1405 {-# INLINE minimum #-}
1406 minimum = Stream.foldl1' min . stream
1407
1408 -- | /O(n)/ Yield the minimum element of the vector according to the given
1409 -- comparison function. The vector may not be empty.
1410 minimumBy :: Vector v a => (a -> a -> Ordering) -> v a -> a
1411 {-# INLINE minimumBy #-}
1412 minimumBy cmp = Stream.foldl1' minBy . stream
1413 where
1414 {-# INLINE minBy #-}
1415 minBy x y = case cmp x y of
1416 GT -> y
1417 _ -> x
1418
1419 -- | /O(n)/ Yield the index of the maximum element of the vector. The vector
1420 -- may not be empty.
1421 maxIndex :: (Vector v a, Ord a) => v a -> Int
1422 {-# INLINE maxIndex #-}
1423 maxIndex = maxIndexBy compare
1424
1425 -- | /O(n)/ Yield the index of the maximum element of the vector according to
1426 -- the given comparison function. The vector may not be empty.
1427 maxIndexBy :: Vector v a => (a -> a -> Ordering) -> v a -> Int
1428 {-# INLINE maxIndexBy #-}
1429 maxIndexBy cmp = fst . Stream.foldl1' imax . Stream.indexed . stream
1430 where
1431 imax (i,x) (j,y) = i `seq` j `seq`
1432 case cmp x y of
1433 LT -> (j,y)
1434 _ -> (i,x)
1435
1436 -- | /O(n)/ Yield the index of the minimum element of the vector. The vector
1437 -- may not be empty.
1438 minIndex :: (Vector v a, Ord a) => v a -> Int
1439 {-# INLINE minIndex #-}
1440 minIndex = minIndexBy compare
1441
1442 -- | /O(n)/ Yield the index of the minimum element of the vector according to
1443 -- the given comparison function. The vector may not be empty.
1444 minIndexBy :: Vector v a => (a -> a -> Ordering) -> v a -> Int
1445 {-# INLINE minIndexBy #-}
1446 minIndexBy cmp = fst . Stream.foldl1' imin . Stream.indexed . stream
1447 where
1448 imin (i,x) (j,y) = i `seq` j `seq`
1449 case cmp x y of
1450 GT -> (j,y)
1451 _ -> (i,x)
1452
1453 -- Monadic folds
1454 -- -------------
1455
1456 -- | /O(n)/ Monadic fold
1457 foldM :: (Monad m, Vector v b) => (a -> b -> m a) -> a -> v b -> m a
1458 {-# INLINE foldM #-}
1459 foldM m z = Stream.foldM m z . stream
1460
1461 -- | /O(n)/ Monadic fold over non-empty vectors
1462 fold1M :: (Monad m, Vector v a) => (a -> a -> m a) -> v a -> m a
1463 {-# INLINE fold1M #-}
1464 fold1M m = Stream.fold1M m . stream
1465
1466 -- | /O(n)/ Monadic fold with strict accumulator
1467 foldM' :: (Monad m, Vector v b) => (a -> b -> m a) -> a -> v b -> m a
1468 {-# INLINE foldM' #-}
1469 foldM' m z = Stream.foldM' m z . stream
1470
1471 -- | /O(n)/ Monadic fold over non-empty vectors with strict accumulator
1472 fold1M' :: (Monad m, Vector v a) => (a -> a -> m a) -> v a -> m a
1473 {-# INLINE fold1M' #-}
1474 fold1M' m = Stream.fold1M' m . stream
1475
1476 -- Prefix sums (scans)
1477 -- -------------------
1478
1479 -- | /O(n)/ Prescan
1480 --
1481 -- @
1482 -- prescanl f z = 'init' . 'scanl' f z
1483 -- @
1484 --
1485 -- Example: @prescanl (+) 0 \<1,2,3,4\> = \<0,1,3,6\>@
1486 --
1487 prescanl :: (Vector v a, Vector v b) => (a -> b -> a) -> a -> v b -> v a
1488 {-# INLINE prescanl #-}
1489 prescanl f z = unstream . inplace (MStream.prescanl f z) . stream
1490
1491 -- | /O(n)/ Prescan with strict accumulator
1492 prescanl' :: (Vector v a, Vector v b) => (a -> b -> a) -> a -> v b -> v a
1493 {-# INLINE prescanl' #-}
1494 prescanl' f z = unstream . inplace (MStream.prescanl' f z) . stream
1495
1496 -- | /O(n)/ Scan
1497 --
1498 -- @
1499 -- postscanl f z = 'tail' . 'scanl' f z
1500 -- @
1501 --
1502 -- Example: @postscanl (+) 0 \<1,2,3,4\> = \<1,3,6,10\>@
1503 --
1504 postscanl :: (Vector v a, Vector v b) => (a -> b -> a) -> a -> v b -> v a
1505 {-# INLINE postscanl #-}
1506 postscanl f z = unstream . inplace (MStream.postscanl f z) . stream
1507
1508 -- | /O(n)/ Scan with strict accumulator
1509 postscanl' :: (Vector v a, Vector v b) => (a -> b -> a) -> a -> v b -> v a
1510 {-# INLINE postscanl' #-}
1511 postscanl' f z = unstream . inplace (MStream.postscanl' f z) . stream
1512
1513 -- | /O(n)/ Haskell-style scan
1514 --
1515 -- > scanl f z <x1,...,xn> = <y1,...,y(n+1)>
1516 -- > where y1 = z
1517 -- > yi = f y(i-1) x(i-1)
1518 --
1519 -- Example: @scanl (+) 0 \<1,2,3,4\> = \<0,1,3,6,10\>@
1520 --
1521 scanl :: (Vector v a, Vector v b) => (a -> b -> a) -> a -> v b -> v a
1522 {-# INLINE scanl #-}
1523 scanl f z = unstream . Stream.scanl f z . stream
1524
1525 -- | /O(n)/ Haskell-style scan with strict accumulator
1526 scanl' :: (Vector v a, Vector v b) => (a -> b -> a) -> a -> v b -> v a
1527 {-# INLINE scanl' #-}
1528 scanl' f z = unstream . Stream.scanl' f z . stream
1529
1530 -- | /O(n)/ Scan over a non-empty vector
1531 --
1532 -- > scanl f <x1,...,xn> = <y1,...,yn>
1533 -- > where y1 = x1
1534 -- > yi = f y(i-1) xi
1535 --
1536 scanl1 :: Vector v a => (a -> a -> a) -> v a -> v a
1537 {-# INLINE scanl1 #-}
1538 scanl1 f = unstream . inplace (MStream.scanl1 f) . stream
1539
1540 -- | /O(n)/ Scan over a non-empty vector with a strict accumulator
1541 scanl1' :: Vector v a => (a -> a -> a) -> v a -> v a
1542 {-# INLINE scanl1' #-}
1543 scanl1' f = unstream . inplace (MStream.scanl1' f) . stream
1544
1545 -- | /O(n)/ Right-to-left prescan
1546 --
1547 -- @
1548 -- prescanr f z = 'reverse' . 'prescanl' (flip f) z . 'reverse'
1549 -- @
1550 --
1551 prescanr :: (Vector v a, Vector v b) => (a -> b -> b) -> b -> v a -> v b
1552 {-# INLINE prescanr #-}
1553 prescanr f z = unstreamR . inplace (MStream.prescanl (flip f) z) . streamR
1554
1555 -- | /O(n)/ Right-to-left prescan with strict accumulator
1556 prescanr' :: (Vector v a, Vector v b) => (a -> b -> b) -> b -> v a -> v b
1557 {-# INLINE prescanr' #-}
1558 prescanr' f z = unstreamR . inplace (MStream.prescanl' (flip f) z) . streamR
1559
1560 -- | /O(n)/ Right-to-left scan
1561 postscanr :: (Vector v a, Vector v b) => (a -> b -> b) -> b -> v a -> v b
1562 {-# INLINE postscanr #-}
1563 postscanr f z = unstreamR . inplace (MStream.postscanl (flip f) z) . streamR
1564
1565 -- | /O(n)/ Right-to-left scan with strict accumulator
1566 postscanr' :: (Vector v a, Vector v b) => (a -> b -> b) -> b -> v a -> v b
1567 {-# INLINE postscanr' #-}
1568 postscanr' f z = unstreamR . inplace (MStream.postscanl' (flip f) z) . streamR
1569
1570 -- | /O(n)/ Right-to-left Haskell-style scan
1571 scanr :: (Vector v a, Vector v b) => (a -> b -> b) -> b -> v a -> v b
1572 {-# INLINE scanr #-}
1573 scanr f z = unstreamR . Stream.scanl (flip f) z . streamR
1574
1575 -- | /O(n)/ Right-to-left Haskell-style scan with strict accumulator
1576 scanr' :: (Vector v a, Vector v b) => (a -> b -> b) -> b -> v a -> v b
1577 {-# INLINE scanr' #-}
1578 scanr' f z = unstreamR . Stream.scanl' (flip f) z . streamR
1579
1580 -- | /O(n)/ Right-to-left scan over a non-empty vector
1581 scanr1 :: Vector v a => (a -> a -> a) -> v a -> v a
1582 {-# INLINE scanr1 #-}
1583 scanr1 f = unstreamR . inplace (MStream.scanl1 (flip f)) . streamR
1584
1585 -- | /O(n)/ Right-to-left scan over a non-empty vector with a strict
1586 -- accumulator
1587 scanr1' :: Vector v a => (a -> a -> a) -> v a -> v a
1588 {-# INLINE scanr1' #-}
1589 scanr1' f = unstreamR . inplace (MStream.scanl1' (flip f)) . streamR
1590
1591 -- Conversions - Lists
1592 -- ------------------------
1593
1594 -- | /O(n)/ Convert a vector to a list
1595 toList :: Vector v a => v a -> [a]
1596 {-# INLINE toList #-}
1597 toList = Stream.toList . stream
1598
1599 -- | /O(n)/ Convert a list to a vector
1600 fromList :: Vector v a => [a] -> v a
1601 {-# INLINE fromList #-}
1602 fromList = unstream . Stream.fromList
1603
1604 -- | /O(n)/ Convert the first @n@ elements of a list to a vector
1605 --
1606 -- @
1607 -- fromListN n xs = 'fromList' ('take' n xs)
1608 -- @
1609 fromListN :: Vector v a => Int -> [a] -> v a
1610 {-# INLINE fromListN #-}
1611 fromListN n = unstream . Stream.fromListN n
1612
1613 -- Conversions - Immutable vectors
1614 -- -------------------------------
1615
1616 -- | /O(n)/ Convert different vector types
1617 convert :: (Vector v a, Vector w a) => v a -> w a
1618 {-# INLINE convert #-}
1619 convert = unstream . stream
1620
1621 -- Conversions - Mutable vectors
1622 -- -----------------------------
1623
1624 -- | /O(1)/ Unsafe convert a mutable vector to an immutable one without
1625 -- copying. The mutable vector may not be used after this operation.
1626 unsafeFreeze
1627 :: (PrimMonad m, Vector v a) => Mutable v (PrimState m) a -> m (v a)
1628 {-# INLINE unsafeFreeze #-}
1629 unsafeFreeze = basicUnsafeFreeze
1630
1631
1632 -- | /O(1)/ Unsafely convert an immutable vector to a mutable one without
1633 -- copying. The immutable vector may not be used after this operation.
1634 unsafeThaw :: (PrimMonad m, Vector v a) => v a -> m (Mutable v (PrimState m) a)
1635 {-# INLINE unsafeThaw #-}
1636 unsafeThaw = basicUnsafeThaw
1637
1638 -- | /O(n)/ Yield a mutable copy of the immutable vector.
1639 thaw :: (PrimMonad m, Vector v a) => v a -> m (Mutable v (PrimState m) a)
1640 {-# INLINE_STREAM thaw #-}
1641 thaw v = do
1642 mv <- M.unsafeNew (length v)
1643 unsafeCopy mv v
1644 return mv
1645
1646 -- | /O(n)/ Yield an immutable copy of the mutable vector.
1647 freeze :: (PrimMonad m, Vector v a) => Mutable v (PrimState m) a -> m (v a)
1648 {-# INLINE freeze #-}
1649 freeze mv = unsafeFreeze =<< M.clone mv
1650
1651 {-
1652 -- | /O(n)/ Yield a mutable vector containing copies of each vector in the
1653 -- list.
1654 thawMany :: (PrimMonad m, Vector v a) => [v a] -> m (Mutable v (PrimState m) a)
1655 {-# INLINE_STREAM thawMany #-}
1656 -- FIXME: add rule for (stream (new (New.create (thawMany vs))))
1657 -- NOTE: We don't try to consume the list lazily as this wouldn't significantly
1658 -- change the space requirements anyway.
1659 thawMany vs = do
1660 mv <- M.new n
1661 thaw_loop mv vs
1662 return mv
1663 where
1664 n = List.foldl' (\k v -> k + length v) 0 vs
1665
1666 thaw_loop mv [] = mv `seq` return ()
1667 thaw_loop mv (v:vs)
1668 = do
1669 let n = length v
1670 unsafeCopy (M.unsafeTake n mv) v
1671 thaw_loop (M.unsafeDrop n mv) vs
1672 -}
1673
1674 -- | /O(n)/ Copy an immutable vector into a mutable one. The two vectors must
1675 -- have the same length.
1676 copy
1677 :: (PrimMonad m, Vector v a) => Mutable v (PrimState m) a -> v a -> m ()
1678 {-# INLINE copy #-}
1679 copy dst src = BOUNDS_CHECK(check) "copy" "length mismatch"
1680 (M.length dst == length src)
1681 $ unsafeCopy dst src
1682
1683 -- | /O(n)/ Copy an immutable vector into a mutable one. The two vectors must
1684 -- have the same length. This is not checked.
1685 unsafeCopy
1686 :: (PrimMonad m, Vector v a) => Mutable v (PrimState m) a -> v a -> m ()
1687 {-# INLINE unsafeCopy #-}
1688 unsafeCopy dst src = UNSAFE_CHECK(check) "unsafeCopy" "length mismatch"
1689 (M.length dst == length src)
1690 $ (dst `seq` src `seq` basicUnsafeCopy dst src)
1691
1692 -- Conversions to/from Streams
1693 -- ---------------------------
1694
1695 -- | /O(1)/ Convert a vector to a 'Stream'
1696 stream :: Vector v a => v a -> Stream a
1697 {-# INLINE_STREAM stream #-}
1698 stream v = v `seq` n `seq` (Stream.unfoldr get 0 `Stream.sized` Exact n)
1699 where
1700 n = length v
1701
1702 -- NOTE: the False case comes first in Core so making it the recursive one
1703 -- makes the code easier to read
1704 {-# INLINE get #-}
1705 get i | i >= n = Nothing
1706 | otherwise = case basicUnsafeIndexM v i of Box x -> Just (x, i+1)
1707
1708 -- | /O(n)/ Construct a vector from a 'Stream'
1709 unstream :: Vector v a => Stream a -> v a
1710 {-# INLINE unstream #-}
1711 unstream s = new (New.unstream s)
1712
1713 {-# RULES
1714
1715 "stream/unstream [Vector]" forall s.
1716 stream (new (New.unstream s)) = s
1717
1718 "New.unstream/stream [Vector]" forall v.
1719 New.unstream (stream v) = clone v
1720
1721 "clone/new [Vector]" forall p.
1722 clone (new p) = p
1723
1724 "inplace [Vector]"
1725 forall (f :: forall m. Monad m => MStream m a -> MStream m a) m.
1726 New.unstream (inplace f (stream (new m))) = New.transform f m
1727
1728 "uninplace [Vector]"
1729 forall (f :: forall m. Monad m => MStream m a -> MStream m a) m.
1730 stream (new (New.transform f m)) = inplace f (stream (new m))
1731
1732 #-}
1733
1734 -- | /O(1)/ Convert a vector to a 'Stream', proceeding from right to left
1735 streamR :: Vector v a => v a -> Stream a
1736 {-# INLINE_STREAM streamR #-}
1737 streamR v = v `seq` n `seq` (Stream.unfoldr get n `Stream.sized` Exact n)
1738 where
1739 n = length v
1740
1741 {-# INLINE get #-}
1742 get 0 = Nothing
1743 get i = let i' = i-1
1744 in
1745 case basicUnsafeIndexM v i' of Box x -> Just (x, i')
1746
1747 -- | /O(n)/ Construct a vector from a 'Stream', proceeding from right to left
1748 unstreamR :: Vector v a => Stream a -> v a
1749 {-# INLINE unstreamR #-}
1750 unstreamR s = new (New.unstreamR s)
1751
1752 {-# RULES
1753
1754 "streamR/unstreamR [Vector]" forall s.
1755 streamR (new (New.unstreamR s)) = s
1756
1757 "New.unstreamR/streamR/new [Vector]" forall p.
1758 New.unstreamR (streamR (new p)) = p
1759
1760 "inplace right [Vector]"
1761 forall (f :: forall m. Monad m => MStream m a -> MStream m a) m.
1762 New.unstreamR (inplace f (streamR (new m))) = New.transformR f m
1763
1764 "uninplace right [Vector]"
1765 forall (f :: forall m. Monad m => MStream m a -> MStream m a) m.
1766 streamR (new (New.transformR f m)) = inplace f (streamR (new m))
1767
1768 #-}
1769
1770 unstreamM :: (Monad m, Vector v a) => MStream m a -> m (v a)
1771 {-# INLINE_STREAM unstreamM #-}
1772 unstreamM s = do
1773 xs <- MStream.toList s
1774 return $ unstream $ Stream.unsafeFromList (MStream.size s) xs
1775
1776 unstreamPrimM :: (PrimMonad m, Vector v a) => MStream m a -> m (v a)
1777 {-# INLINE_STREAM unstreamPrimM #-}
1778 unstreamPrimM s = M.munstream s >>= unsafeFreeze
1779
1780 -- FIXME: the next two functions are only necessary for the specialisations
1781 unstreamPrimM_IO :: Vector v a => MStream IO a -> IO (v a)
1782 {-# INLINE unstreamPrimM_IO #-}
1783 unstreamPrimM_IO = unstreamPrimM
1784
1785 unstreamPrimM_ST :: Vector v a => MStream (ST s) a -> ST s (v a)
1786 {-# INLINE unstreamPrimM_ST #-}
1787 unstreamPrimM_ST = unstreamPrimM
1788
1789 {-# RULES
1790
1791 "unstreamM[IO]" unstreamM = unstreamPrimM_IO
1792 "unstreamM[ST]" unstreamM = unstreamPrimM_ST
1793
1794 #-}
1795
1796
1797 -- Recycling support
1798 -- -----------------
1799
1800 -- | Construct a vector from a monadic initialiser.
1801 new :: Vector v a => New v a -> v a
1802 {-# INLINE_STREAM new #-}
1803 new m = m `seq` runST (unsafeFreeze =<< New.run m)
1804
1805 -- | Convert a vector to an initialiser which, when run, produces a copy of
1806 -- the vector.
1807 clone :: Vector v a => v a -> New v a
1808 {-# INLINE_STREAM clone #-}
1809 clone v = v `seq` New.create (
1810 do
1811 mv <- M.new (length v)
1812 unsafeCopy mv v
1813 return mv)
1814
1815 -- Comparisons
1816 -- -----------
1817
1818 -- | /O(n)/ Check if two vectors are equal. All 'Vector' instances are also
1819 -- instances of 'Eq' and it is usually more appropriate to use those. This
1820 -- function is primarily intended for implementing 'Eq' instances for new
1821 -- vector types.
1822 eq :: (Vector v a, Eq a) => v a -> v a -> Bool
1823 {-# INLINE eq #-}
1824 xs `eq` ys = stream xs == stream ys
1825
1826 -- | /O(n)/ Compare two vectors lexicographically. All 'Vector' instances are
1827 -- also instances of 'Ord' and it is usually more appropriate to use those. This
1828 -- function is primarily intended for implementing 'Ord' instances for new
1829 -- vector types.
1830 cmp :: (Vector v a, Ord a) => v a -> v a -> Ordering
1831 {-# INLINE cmp #-}
1832 cmp xs ys = compare (stream xs) (stream ys)
1833
1834 -- Data and Typeable
1835 -- -----------------
1836
1837 -- | Generic definion of 'Data.Data.gfoldl' that views a 'Vector' as a
1838 -- list.
1839 gfoldl :: (Vector v a, Data a)
1840 => (forall d b. Data d => c (d -> b) -> d -> c b)
1841 -> (forall g. g -> c g)
1842 -> v a
1843 -> c (v a)
1844 {-# INLINE gfoldl #-}
1845 gfoldl f z v = z fromList `f` toList v
1846
1847 mkType :: String -> DataType
1848 {-# INLINE mkType #-}
1849 mkType = mkNoRepType
1850
1851 dataCast :: (Vector v a, Data a, Typeable1 v, Typeable1 t)
1852 => (forall d. Data d => c (t d)) -> Maybe (c (v a))
1853 {-# INLINE dataCast #-}
1854 dataCast f = gcast1 f
1855