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