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