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