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