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