Add Stream.flatten and use it to implement concat
[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, thawMany, 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 -- | /O(n)/ Yield a mutable vector containing copies of each vector in the
1578 -- list.
1579 thawMany :: (PrimMonad m, Vector v a) => [v a] -> m (Mutable v (PrimState m) a)
1580 {-# INLINE_STREAM thawMany #-}
1581 -- FIXME: add rule for (stream (new (New.create (thawMany vs))))
1582 -- NOTE: We don't try to consume the list lazily as this wouldn't significantly
1583 -- change the space requirements anyway.
1584 thawMany vs = do
1585 mv <- M.new n
1586 thaw_loop mv vs
1587 return mv
1588 where
1589 n = List.foldl' (\k v -> k + length v) 0 vs
1590
1591 thaw_loop mv [] = mv `seq` return ()
1592 thaw_loop mv (v:vs)
1593 = do
1594 let n = length v
1595 unsafeCopy (M.unsafeTake n mv) v
1596 thaw_loop (M.unsafeDrop n mv) vs
1597
1598 -- | /O(n)/ Copy an immutable vector into a mutable one. The two vectors must
1599 -- have the same length.
1600 copy
1601 :: (PrimMonad m, Vector v a) => Mutable v (PrimState m) a -> v a -> m ()
1602 {-# INLINE copy #-}
1603 copy dst src = BOUNDS_CHECK(check) "copy" "length mismatch"
1604 (M.length dst == length src)
1605 $ unsafeCopy dst src
1606
1607 -- | /O(n)/ Copy an immutable vector into a mutable one. The two vectors must
1608 -- have the same length. This is not checked.
1609 unsafeCopy
1610 :: (PrimMonad m, Vector v a) => Mutable v (PrimState m) a -> v a -> m ()
1611 {-# INLINE unsafeCopy #-}
1612 unsafeCopy dst src = UNSAFE_CHECK(check) "unsafeCopy" "length mismatch"
1613 (M.length dst == length src)
1614 $ (dst `seq` src `seq` basicUnsafeCopy dst src)
1615
1616 -- Conversions to/from Streams
1617 -- ---------------------------
1618
1619 -- | /O(1)/ Convert a vector to a 'Stream'
1620 stream :: Vector v a => v a -> Stream a
1621 {-# INLINE_STREAM stream #-}
1622 stream v = v `seq` (Stream.unfoldr get 0 `Stream.sized` Exact n)
1623 where
1624 n = length v
1625
1626 -- NOTE: the False case comes first in Core so making it the recursive one
1627 -- makes the code easier to read
1628 {-# INLINE get #-}
1629 get i | i >= n = Nothing
1630 | otherwise = case basicUnsafeIndexM v i of Box x -> Just (x, i+1)
1631
1632 -- | /O(n)/ Construct a vector from a 'Stream'
1633 unstream :: Vector v a => Stream a -> v a
1634 {-# INLINE unstream #-}
1635 unstream s = new (New.unstream s)
1636
1637 {-# RULES
1638
1639 "stream/unstream [Vector]" forall s.
1640 stream (new (New.unstream s)) = s
1641
1642 "New.unstream/stream [Vector]" forall v.
1643 New.unstream (stream v) = clone v
1644
1645 "clone/new [Vector]" forall p.
1646 clone (new p) = p
1647
1648 "inplace [Vector]"
1649 forall (f :: forall m. Monad m => MStream m a -> MStream m a) m.
1650 New.unstream (inplace f (stream (new m))) = New.transform f m
1651
1652 "uninplace [Vector]"
1653 forall (f :: forall m. Monad m => MStream m a -> MStream m a) m.
1654 stream (new (New.transform f m)) = inplace f (stream (new m))
1655
1656 #-}
1657
1658 -- | /O(1)/ Convert a vector to a 'Stream', proceeding from right to left
1659 streamR :: Vector v a => v a -> Stream a
1660 {-# INLINE_STREAM streamR #-}
1661 streamR v = v `seq` (Stream.unfoldr get n `Stream.sized` Exact n)
1662 where
1663 n = length v
1664
1665 {-# INLINE get #-}
1666 get 0 = Nothing
1667 get i = let i' = i-1
1668 in
1669 case basicUnsafeIndexM v i' of Box x -> Just (x, i')
1670
1671 -- | /O(n)/ Construct a vector from a 'Stream', proceeding from right to left
1672 unstreamR :: Vector v a => Stream a -> v a
1673 {-# INLINE unstreamR #-}
1674 unstreamR s = new (New.unstreamR s)
1675
1676 {-# RULES
1677
1678 "streamR/unstreamR [Vector]" forall s.
1679 streamR (new (New.unstreamR s)) = s
1680
1681 "New.unstreamR/streamR/new [Vector]" forall p.
1682 New.unstreamR (streamR (new p)) = p
1683
1684 "inplace right [Vector]"
1685 forall (f :: forall m. Monad m => MStream m a -> MStream m a) m.
1686 New.unstreamR (inplace f (streamR (new m))) = New.transformR f m
1687
1688 "uninplace right [Vector]"
1689 forall (f :: forall m. Monad m => MStream m a -> MStream m a) m.
1690 streamR (new (New.transformR f m)) = inplace f (streamR (new m))
1691
1692 #-}
1693
1694 unstreamM :: (Vector v a, Monad m) => MStream m a -> m (v a)
1695 {-# INLINE_STREAM unstreamM #-}
1696 unstreamM s = do
1697 xs <- MStream.toList s
1698 return $ unstream $ Stream.unsafeFromList (MStream.size s) xs
1699
1700 -- Recycling support
1701 -- -----------------
1702
1703 -- | Construct a vector from a monadic initialiser.
1704 new :: Vector v a => New v a -> v a
1705 {-# INLINE_STREAM new #-}
1706 new m = m `seq` runST (unsafeFreeze =<< New.run m)
1707
1708 -- | Convert a vector to an initialiser which, when run, produces a copy of
1709 -- the vector.
1710 clone :: Vector v a => v a -> New v a
1711 {-# INLINE_STREAM clone #-}
1712 clone v = v `seq` New.create (
1713 do
1714 mv <- M.new (length v)
1715 unsafeCopy mv v
1716 return mv)
1717
1718 -- Comparisons
1719 -- -----------
1720
1721 -- | /O(n)/ Check if two vectors are equal. All 'Vector' instances are also
1722 -- instances of 'Eq' and it is usually more appropriate to use those. This
1723 -- function is primarily intended for implementing 'Eq' instances for new
1724 -- vector types.
1725 eq :: (Vector v a, Eq a) => v a -> v a -> Bool
1726 {-# INLINE eq #-}
1727 xs `eq` ys = stream xs == stream ys
1728
1729 -- | /O(n)/ Compare two vectors lexicographically. All 'Vector' instances are
1730 -- also instances of 'Ord' and it is usually more appropriate to use those. This
1731 -- function is primarily intended for implementing 'Ord' instances for new
1732 -- vector types.
1733 cmp :: (Vector v a, Ord a) => v a -> v a -> Ordering
1734 {-# INLINE cmp #-}
1735 cmp xs ys = compare (stream xs) (stream ys)
1736
1737 -- Data and Typeable
1738 -- -----------------
1739
1740 -- | Generic definion of 'Data.Data.gfoldl' that views a 'Vector' as a
1741 -- list.
1742 gfoldl :: (Vector v a, Data a)
1743 => (forall d b. Data d => c (d -> b) -> d -> c b)
1744 -> (forall g. g -> c g)
1745 -> v a
1746 -> c (v a)
1747 {-# INLINE gfoldl #-}
1748 gfoldl f z v = z fromList `f` toList v
1749
1750 mkType :: String -> DataType
1751 {-# INLINE mkType #-}
1752 mkType = mkNorepType
1753
1754 dataCast :: (Vector v a, Data a, Typeable1 v, Typeable1 t)
1755 => (forall d. Data d => c (t d)) -> Maybe (c (v a))
1756 {-# INLINE dataCast #-}
1757 dataCast f = gcast1 f
1758