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