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