Add freeze
[darcs-mirrors/vector.git] / Data / Vector / Generic.hs
1 {-# LANGUAGE Rank2Types, MultiParamTypeClasses, FlexibleContexts,
2 TypeFamilies, ScopedTypeVariables #-}
3 -- |
4 -- Module : Data.Vector.Generic
5 -- Copyright : (c) Roman Leshchinskiy 2008-2010
6 -- License : BSD-style
7 --
8 -- Maintainer : Roman Leshchinskiy <rl@cse.unsw.edu.au>
9 -- Stability : experimental
10 -- Portability : non-portable
11 --
12 -- Generic interface to pure vectors.
13 --
14
15 module Data.Vector.Generic (
16 -- * Immutable vectors
17 Vector(..), Mutable,
18
19 -- * Accessors
20
21 -- ** Length information
22 length, null,
23
24 -- ** Indexing
25 (!), head, last,
26 unsafeIndex, unsafeHead, unsafeLast,
27
28 -- ** Monadic indexing
29 indexM, headM, lastM,
30 unsafeIndexM, unsafeHeadM, unsafeLastM,
31
32 -- ** Extracting subvectors (slicing)
33 slice, init, tail, take, drop,
34 unsafeSlice, unsafeInit, unsafeTail, unsafeTake, unsafeDrop,
35
36 -- * Construction
37
38 -- ** Initialisation
39 empty, singleton, replicate, generate,
40
41 -- ** Monadic initialisation
42 replicateM, create,
43
44 -- ** Unfolding
45 unfoldr, unfoldrN,
46
47 -- ** Enumeration
48 enumFromN, enumFromStepN, enumFromTo, enumFromThenTo,
49
50 -- ** Concatenation
51 cons, snoc, (++), concat,
52
53 -- ** Restricting memory usage
54 force,
55
56 -- * Modifying vectors
57
58 -- ** Bulk updates
59 (//), update, update_,
60 unsafeUpd, unsafeUpdate, unsafeUpdate_,
61
62 -- ** Accumulations
63 accum, accumulate, accumulate_,
64 unsafeAccum, unsafeAccumulate, unsafeAccumulate_,
65
66 -- ** Permutations
67 reverse, backpermute, unsafeBackpermute,
68
69 -- ** Safe destructive updates
70 modify,
71
72 -- * Elementwise operations
73
74 -- ** Mapping
75 map, imap, concatMap,
76
77 -- ** Monadic mapping
78 mapM, mapM_, forM, forM_,
79
80 -- ** Zipping
81 zipWith, zipWith3, zipWith4, zipWith5, zipWith6,
82 izipWith, izipWith3, izipWith4, izipWith5, izipWith6,
83 zip, zip3, zip4, zip5, zip6,
84
85 -- ** Monadic zipping
86 zipWithM, zipWithM_,
87
88 -- ** Unzipping
89 unzip, unzip3, unzip4, unzip5, unzip6,
90
91 -- * Working with predicates
92
93 -- ** Filtering
94 filter, ifilter, filterM,
95 takeWhile, dropWhile,
96
97 -- ** Partitioning
98 partition, unstablePartition, span, break,
99
100 -- ** Searching
101 elem, notElem, find, findIndex, findIndices, elemIndex, elemIndices,
102
103 -- * Folding
104 foldl, foldl1, foldl', foldl1', foldr, foldr1, foldr', foldr1',
105 ifoldl, ifoldl', ifoldr, ifoldr',
106
107 -- ** Specialised folds
108 all, any, and, or,
109 sum, product,
110 maximum, maximumBy, minimum, minimumBy,
111 minIndex, minIndexBy, maxIndex, maxIndexBy,
112
113 -- ** Monadic folds
114 foldM, foldM', fold1M, fold1M',
115
116 -- * Prefix sums (scans)
117 prescanl, prescanl',
118 postscanl, postscanl',
119 scanl, scanl', scanl1, scanl1',
120 prescanr, prescanr',
121 postscanr, postscanr',
122 scanr, scanr', scanr1, scanr1',
123
124 -- * Conversions
125
126 -- ** Lists
127 toList, fromList, fromListN,
128
129 -- ** Different vector types
130 convert,
131
132 -- ** Mutable vectors
133 freeze, thaw, copy, unsafeFreeze, unsafeThaw, unsafeCopy,
134
135 -- * Fusion support
136
137 -- ** Conversion to/from Streams
138 stream, unstream, streamR, unstreamR,
139
140 -- ** Recycling support
141 new, clone,
142
143 -- * Utilities
144
145 -- ** Comparisons
146 eq, cmp,
147
148 -- ** @Data@ and @Typeable@
149 gfoldl, dataCast, mkType
150 ) where
151
152 import Data.Vector.Generic.Base
153
154 import Data.Vector.Generic.Mutable ( MVector )
155 import qualified Data.Vector.Generic.Mutable as M
156
157 import qualified Data.Vector.Generic.New as New
158 import Data.Vector.Generic.New ( New )
159
160 import qualified Data.Vector.Fusion.Stream as Stream
161 import Data.Vector.Fusion.Stream ( Stream, MStream, inplace, liftStream )
162 import qualified Data.Vector.Fusion.Stream.Monadic as MStream
163 import Data.Vector.Fusion.Stream.Size
164 import Data.Vector.Fusion.Util
165
166 import Control.Monad.ST ( ST, runST )
167 import Control.Monad.Primitive
168 import qualified Control.Monad as Monad
169 import qualified Data.List as List
170 import Prelude hiding ( length, null,
171 replicate, (++), concat,
172 head, last,
173 init, tail, take, drop, reverse,
174 map, concat, concatMap,
175 zipWith, zipWith3, zip, zip3, unzip, unzip3,
176 filter, takeWhile, dropWhile, span, break,
177 elem, notElem,
178 foldl, foldl1, foldr, foldr1,
179 all, any, and, or, sum, product, maximum, minimum,
180 scanl, scanl1, scanr, scanr1,
181 enumFromTo, enumFromThenTo,
182 mapM, mapM_ )
183
184 import Data.Typeable ( Typeable1, gcast1 )
185 import Data.Data ( Data, DataType, mkNorepType )
186
187 #include "vector.h"
188
189 -- Length information
190 -- ------------------
191
192 -- | /O(1)/ Yield the length of the vector.
193 length :: Vector v a => v a -> Int
194 {-# INLINE_STREAM length #-}
195 length v = basicLength v
196
197 {-# RULES
198
199 "length/unstream [Vector]" forall s.
200 length (new (New.unstream s)) = Stream.length s
201
202 #-}
203
204 -- | /O(1)/ Test whether a vector if empty
205 null :: Vector v a => v a -> Bool
206 {-# INLINE_STREAM null #-}
207 null v = basicLength v == 0
208
209 {-# RULES
210
211 "null/unstream [Vector]" forall s.
212 null (new (New.unstream s)) = Stream.null s
213
214 #-}
215
216 -- Indexing
217 -- --------
218
219 -- | O(1) Indexing
220 (!) :: Vector v a => v a -> Int -> a
221 {-# INLINE_STREAM (!) #-}
222 v ! i = BOUNDS_CHECK(checkIndex) "(!)" i (length v)
223 $ unId (basicUnsafeIndexM v i)
224
225 -- | /O(1)/ 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 $ seq n
796 $ unstream
797 $ Stream.unbox
798 $ Stream.map index
799 $ stream is
800 where
801 n = length v
802
803 {-# INLINE index #-}
804 -- NOTE: we do it this way to avoid triggering LiberateCase on n in
805 -- polymorphic code
806 index i = BOUNDS_CHECK(checkIndex) "backpermute" i n
807 $ basicUnsafeIndexM v i
808
809 -- | Same as 'backpermute' but without bounds checking.
810 unsafeBackpermute :: (Vector v a, Vector v Int) => v a -> v Int -> v a
811 {-# INLINE unsafeBackpermute #-}
812 unsafeBackpermute v is = seq v
813 $ seq n
814 $ unstream
815 $ Stream.unbox
816 $ Stream.map index
817 $ stream is
818 where
819 n = length v
820
821 {-# INLINE index #-}
822 -- NOTE: we do it this way to avoid triggering LiberateCase on n in
823 -- polymorphic code
824 index i = UNSAFE_CHECK(checkIndex) "unsafeBackpermute" i n
825 $ basicUnsafeIndexM v i
826
827 -- Safe destructive updates
828 -- ------------------------
829
830 -- | Apply a destructive operation to a vector. The operation will be
831 -- performed in place if it is safe to do so and will modify a copy of the
832 -- vector otherwise.
833 --
834 -- @
835 -- modify (\\v -> 'M.write' v 0 \'x\') ('replicate' 3 \'a\') = \<\'x\',\'a\',\'a\'\>
836 -- @
837 modify :: Vector v a => (forall s. Mutable v s a -> ST s ()) -> v a -> v a
838 {-# INLINE modify #-}
839 modify p = new . New.modify p . clone
840
841 -- We have to make sure that this is strict in the stream but we can't seq on
842 -- it while fusion is happening. Hence this ugliness.
843 modifyWithStream :: Vector v a
844 => (forall s. Mutable v s a -> Stream b -> ST s ())
845 -> v a -> Stream b -> v a
846 {-# INLINE modifyWithStream #-}
847 modifyWithStream p v s = new (New.modifyWithStream p (clone v) s)
848
849 -- Mapping
850 -- -------
851
852 -- | /O(n)/ Map a function over a vector
853 map :: (Vector v a, Vector v b) => (a -> b) -> v a -> v b
854 {-# INLINE map #-}
855 map f = unstream . inplace (MStream.map f) . stream
856
857 -- | /O(n)/ Apply a function to every element of a vector and its index
858 imap :: (Vector v a, Vector v b) => (Int -> a -> b) -> v a -> v b
859 {-# INLINE imap #-}
860 imap f = unstream . inplace (MStream.map (uncurry f) . MStream.indexed)
861 . stream
862
863 -- | Map a function over a vector and concatenate the results.
864 concatMap :: (Vector v a, Vector v b) => (a -> v b) -> v a -> v b
865 {-# INLINE concatMap #-}
866 -- NOTE: We can't fuse concatMap anyway so don't pretend we do.
867 -- concatMap f = unstream . Stream.concatMap (stream . f) . stream
868 concatMap f = concat . Stream.toList . Stream.map f . stream
869
870 -- Monadic mapping
871 -- ---------------
872
873 -- | /O(n)/ Apply the monadic action to all elements of the vector, yielding a
874 -- vector of results
875 mapM :: (Monad m, Vector v a, Vector v b) => (a -> m b) -> v a -> m (v b)
876 -- FIXME: specialise for ST and IO?
877 {-# INLINE mapM #-}
878 mapM f = unstreamM . Stream.mapM f . stream
879
880 -- | /O(n)/ Apply the monadic action to all elements of a vector and ignore the
881 -- results
882 mapM_ :: (Monad m, Vector v a) => (a -> m b) -> v a -> m ()
883 {-# INLINE mapM_ #-}
884 mapM_ f = Stream.mapM_ f . stream
885
886 -- | /O(n)/ Apply the monadic action to all elements of the vector, yielding a
887 -- vector of results. Equvalent to @flip 'mapM'@.
888 forM :: (Monad m, Vector v a, Vector v b) => v a -> (a -> m b) -> m (v b)
889 {-# INLINE forM #-}
890 forM as f = mapM f as
891
892 -- | /O(n)/ Apply the monadic action to all elements of a vector and ignore the
893 -- results. Equivalent to @flip 'mapM_'@.
894 forM_ :: (Monad m, Vector v a) => v a -> (a -> m b) -> m ()
895 {-# INLINE forM_ #-}
896 forM_ as f = mapM_ f as
897
898 -- Zipping
899 -- -------
900
901 -- | /O(min(m,n))/ Zip two vectors with the given function.
902 zipWith :: (Vector v a, Vector v b, Vector v c)
903 => (a -> b -> c) -> v a -> v b -> v c
904 {-# INLINE zipWith #-}
905 zipWith f xs ys = unstream (Stream.zipWith f (stream xs) (stream ys))
906
907 -- | Zip three vectors with the given function.
908 zipWith3 :: (Vector v a, Vector v b, Vector v c, Vector v d)
909 => (a -> b -> c -> d) -> v a -> v b -> v c -> v d
910 {-# INLINE zipWith3 #-}
911 zipWith3 f as bs cs = unstream (Stream.zipWith3 f (stream as)
912 (stream bs)
913 (stream cs))
914
915 zipWith4 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e)
916 => (a -> b -> c -> d -> e) -> v a -> v b -> v c -> v d -> v e
917 {-# INLINE zipWith4 #-}
918 zipWith4 f as bs cs ds
919 = unstream (Stream.zipWith4 f (stream as)
920 (stream bs)
921 (stream cs)
922 (stream ds))
923
924 zipWith5 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e,
925 Vector v f)
926 => (a -> b -> c -> d -> e -> f) -> v a -> v b -> v c -> v d -> v e
927 -> v f
928 {-# INLINE zipWith5 #-}
929 zipWith5 f as bs cs ds es
930 = unstream (Stream.zipWith5 f (stream as)
931 (stream bs)
932 (stream cs)
933 (stream ds)
934 (stream es))
935
936 zipWith6 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e,
937 Vector v f, Vector v g)
938 => (a -> b -> c -> d -> e -> f -> g)
939 -> v a -> v b -> v c -> v d -> v e -> v f -> v g
940 {-# INLINE zipWith6 #-}
941 zipWith6 f as bs cs ds es fs
942 = unstream (Stream.zipWith6 f (stream as)
943 (stream bs)
944 (stream cs)
945 (stream ds)
946 (stream es)
947 (stream fs))
948
949 -- | /O(min(m,n))/ Zip two vectors with a function that also takes the
950 -- elements' indices.
951 izipWith :: (Vector v a, Vector v b, Vector v c)
952 => (Int -> a -> b -> c) -> v a -> v b -> v c
953 {-# INLINE izipWith #-}
954 izipWith f xs ys = unstream
955 (Stream.zipWith (uncurry f) (Stream.indexed (stream xs))
956 (stream ys))
957
958 izipWith3 :: (Vector v a, Vector v b, Vector v c, Vector v d)
959 => (Int -> a -> b -> c -> d) -> v a -> v b -> v c -> v d
960 {-# INLINE izipWith3 #-}
961 izipWith3 f as bs cs
962 = unstream (Stream.zipWith3 (uncurry f) (Stream.indexed (stream as))
963 (stream bs)
964 (stream cs))
965
966 izipWith4 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e)
967 => (Int -> a -> b -> c -> d -> e) -> v a -> v b -> v c -> v d -> v e
968 {-# INLINE izipWith4 #-}
969 izipWith4 f as bs cs ds
970 = unstream (Stream.zipWith4 (uncurry f) (Stream.indexed (stream as))
971 (stream bs)
972 (stream cs)
973 (stream ds))
974
975 izipWith5 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e,
976 Vector v f)
977 => (Int -> a -> b -> c -> d -> e -> f) -> v a -> v b -> v c -> v d
978 -> v e -> v f
979 {-# INLINE izipWith5 #-}
980 izipWith5 f as bs cs ds es
981 = unstream (Stream.zipWith5 (uncurry f) (Stream.indexed (stream as))
982 (stream bs)
983 (stream cs)
984 (stream ds)
985 (stream es))
986
987 izipWith6 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e,
988 Vector v f, Vector v g)
989 => (Int -> a -> b -> c -> d -> e -> f -> g)
990 -> v a -> v b -> v c -> v d -> v e -> v f -> v g
991 {-# INLINE izipWith6 #-}
992 izipWith6 f as bs cs ds es fs
993 = unstream (Stream.zipWith6 (uncurry f) (Stream.indexed (stream as))
994 (stream bs)
995 (stream cs)
996 (stream ds)
997 (stream es)
998 (stream fs))
999
1000 -- | /O(min(m,n))/ Zip two vectors
1001 zip :: (Vector v a, Vector v b, Vector v (a,b)) => v a -> v b -> v (a, b)
1002 {-# INLINE zip #-}
1003 zip = zipWith (,)
1004
1005 zip3 :: (Vector v a, Vector v b, Vector v c, Vector v (a, b, c))
1006 => v a -> v b -> v c -> v (a, b, c)
1007 {-# INLINE zip3 #-}
1008 zip3 = zipWith3 (,,)
1009
1010 zip4 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v (a, b, c, d))
1011 => v a -> v b -> v c -> v d -> v (a, b, c, d)
1012 {-# INLINE zip4 #-}
1013 zip4 = zipWith4 (,,,)
1014
1015 zip5 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e,
1016 Vector v (a, b, c, d, e))
1017 => v a -> v b -> v c -> v d -> v e -> v (a, b, c, d, e)
1018 {-# INLINE zip5 #-}
1019 zip5 = zipWith5 (,,,,)
1020
1021 zip6 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e,
1022 Vector v f, Vector v (a, b, c, d, e, f))
1023 => v a -> v b -> v c -> v d -> v e -> v f -> v (a, b, c, d, e, f)
1024 {-# INLINE zip6 #-}
1025 zip6 = zipWith6 (,,,,,)
1026
1027 -- Monadic zipping
1028 -- ---------------
1029
1030 -- | /O(min(m,n))/ Zip the two vectors with the monadic action and yield a
1031 -- vector of results
1032 zipWithM :: (Monad m, Vector v a, Vector v b, Vector v c)
1033 => (a -> b -> m c) -> v a -> v b -> m (v c)
1034 -- FIXME: specialise for ST and IO?
1035 {-# INLINE zipWithM #-}
1036 zipWithM f as bs = unstreamM $ Stream.zipWithM f (stream as) (stream bs)
1037
1038 -- | /O(min(m,n))/ Zip the two vectors with the monadic action and ignore the
1039 -- results
1040 zipWithM_ :: (Monad m, Vector v a, Vector v b)
1041 => (a -> b -> m c) -> v a -> v b -> m ()
1042 {-# INLINE zipWithM_ #-}
1043 zipWithM_ f as bs = Stream.zipWithM_ f (stream as) (stream bs)
1044
1045 -- Unzipping
1046 -- ---------
1047
1048 -- | /O(min(m,n))/ Unzip a vector of pairs.
1049 unzip :: (Vector v a, Vector v b, Vector v (a,b)) => v (a, b) -> (v a, v b)
1050 {-# INLINE unzip #-}
1051 unzip xs = (map fst xs, map snd xs)
1052
1053 unzip3 :: (Vector v a, Vector v b, Vector v c, Vector v (a, b, c))
1054 => v (a, b, c) -> (v a, v b, v c)
1055 {-# INLINE unzip3 #-}
1056 unzip3 xs = (map (\(a, b, c) -> a) xs,
1057 map (\(a, b, c) -> b) xs,
1058 map (\(a, b, c) -> c) xs)
1059
1060 unzip4 :: (Vector v a, Vector v b, Vector v c, Vector v d,
1061 Vector v (a, b, c, d))
1062 => v (a, b, c, d) -> (v a, v b, v c, v d)
1063 {-# INLINE unzip4 #-}
1064 unzip4 xs = (map (\(a, b, c, d) -> a) xs,
1065 map (\(a, b, c, d) -> b) xs,
1066 map (\(a, b, c, d) -> c) xs,
1067 map (\(a, b, c, d) -> d) xs)
1068
1069 unzip5 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e,
1070 Vector v (a, b, c, d, e))
1071 => v (a, b, c, d, e) -> (v a, v b, v c, v d, v e)
1072 {-# INLINE unzip5 #-}
1073 unzip5 xs = (map (\(a, b, c, d, e) -> a) xs,
1074 map (\(a, b, c, d, e) -> b) xs,
1075 map (\(a, b, c, d, e) -> c) xs,
1076 map (\(a, b, c, d, e) -> d) xs,
1077 map (\(a, b, c, d, e) -> e) xs)
1078
1079 unzip6 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e,
1080 Vector v f, Vector v (a, b, c, d, e, f))
1081 => v (a, b, c, d, e, f) -> (v a, v b, v c, v d, v e, v f)
1082 {-# INLINE unzip6 #-}
1083 unzip6 xs = (map (\(a, b, c, d, e, f) -> a) xs,
1084 map (\(a, b, c, d, e, f) -> b) xs,
1085 map (\(a, b, c, d, e, f) -> c) xs,
1086 map (\(a, b, c, d, e, f) -> d) xs,
1087 map (\(a, b, c, d, e, f) -> e) xs,
1088 map (\(a, b, c, d, e, f) -> f) xs)
1089
1090 -- Filtering
1091 -- ---------
1092
1093 -- | /O(n)/ Drop elements that do not satisfy the predicate
1094 filter :: Vector v a => (a -> Bool) -> v a -> v a
1095 {-# INLINE filter #-}
1096 filter f = unstream . inplace (MStream.filter f) . stream
1097
1098 -- | /O(n)/ Drop elements that do not satisfy the predicate which is applied to
1099 -- values and their indices
1100 ifilter :: Vector v a => (Int -> a -> Bool) -> v a -> v a
1101 {-# INLINE ifilter #-}
1102 ifilter f = unstream
1103 . inplace (MStream.map snd . MStream.filter (uncurry f)
1104 . MStream.indexed)
1105 . stream
1106
1107 -- | /O(n)/ Drop elements that do not satisfy the monadic predicate
1108 filterM :: (Monad m, Vector v a) => (a -> m Bool) -> v a -> m (v a)
1109 {-# INLINE filterM #-}
1110 filterM f = unstreamM . Stream.filterM f . stream
1111
1112 -- | /O(n)/ Yield the longest prefix of elements satisfying the predicate
1113 -- without copying.
1114 takeWhile :: Vector v a => (a -> Bool) -> v a -> v a
1115 {-# INLINE takeWhile #-}
1116 takeWhile f = unstream . Stream.takeWhile f . stream
1117
1118 -- | /O(n)/ Drop the longest prefix of elements that satisfy the predicate
1119 -- without copying.
1120 dropWhile :: Vector v a => (a -> Bool) -> v a -> v a
1121 {-# INLINE dropWhile #-}
1122 dropWhile f = unstream . Stream.dropWhile f . stream
1123
1124 -- Parititioning
1125 -- -------------
1126
1127 -- | /O(n)/ Split the vector in two parts, the first one containing those
1128 -- elements that satisfy the predicate and the second one those that don't. The
1129 -- relative order of the elements is preserved at the cost of a sometimes
1130 -- reduced performance compared to 'unstablePartition'.
1131 partition :: Vector v a => (a -> Bool) -> v a -> (v a, v a)
1132 {-# INLINE partition #-}
1133 partition f = partition_stream f . stream
1134
1135 -- FIXME: Make this inplace-fusible (look at how stable_partition is
1136 -- implemented in C++)
1137
1138 partition_stream :: Vector v a => (a -> Bool) -> Stream a -> (v a, v a)
1139 {-# INLINE_STREAM partition_stream #-}
1140 partition_stream f s = s `seq` runST (
1141 do
1142 (mv1,mv2) <- M.partitionStream f s
1143 v1 <- unsafeFreeze mv1
1144 v2 <- unsafeFreeze mv2
1145 return (v1,v2))
1146
1147 -- | /O(n)/ Split the vector in two parts, the first one containing those
1148 -- elements that satisfy the predicate and the second one those that don't.
1149 -- The order of the elements is not preserved but the operation is often
1150 -- faster than 'partition'.
1151 unstablePartition :: Vector v a => (a -> Bool) -> v a -> (v a, v a)
1152 {-# INLINE unstablePartition #-}
1153 unstablePartition f = unstablePartition_stream f . stream
1154
1155 unstablePartition_stream
1156 :: Vector v a => (a -> Bool) -> Stream a -> (v a, v a)
1157 {-# INLINE_STREAM unstablePartition_stream #-}
1158 unstablePartition_stream f s = s `seq` runST (
1159 do
1160 (mv1,mv2) <- M.unstablePartitionStream f s
1161 v1 <- unsafeFreeze mv1
1162 v2 <- unsafeFreeze mv2
1163 return (v1,v2))
1164
1165 unstablePartition_new :: Vector v a => (a -> Bool) -> New v a -> (v a, v a)
1166 {-# INLINE_STREAM unstablePartition_new #-}
1167 unstablePartition_new f (New.New p) = runST (
1168 do
1169 mv <- p
1170 i <- M.unstablePartition f mv
1171 v <- unsafeFreeze mv
1172 return (unsafeTake i v, unsafeDrop i v))
1173
1174 {-# RULES
1175
1176 "unstablePartition" forall f p.
1177 unstablePartition_stream f (stream (new p))
1178 = unstablePartition_new f p
1179
1180 #-}
1181
1182
1183 -- FIXME: make span and break fusible
1184
1185 -- | /O(n)/ Split the vector into the longest prefix of elements that satisfy
1186 -- the predicate and the rest without copying.
1187 span :: Vector v a => (a -> Bool) -> v a -> (v a, v a)
1188 {-# INLINE span #-}
1189 span f = break (not . f)
1190
1191 -- | /O(n)/ Split the vector into the longest prefix of elements that do not
1192 -- satisfy the predicate and the rest without copying.
1193 break :: Vector v a => (a -> Bool) -> v a -> (v a, v a)
1194 {-# INLINE break #-}
1195 break f xs = case findIndex f xs of
1196 Just i -> (unsafeSlice 0 i xs, unsafeSlice i (length xs - i) xs)
1197 Nothing -> (xs, empty)
1198
1199
1200 -- Searching
1201 -- ---------
1202
1203 infix 4 `elem`
1204 -- | /O(n)/ Check if the vector contains an element
1205 elem :: (Vector v a, Eq a) => a -> v a -> Bool
1206 {-# INLINE elem #-}
1207 elem x = Stream.elem x . stream
1208
1209 infix 4 `notElem`
1210 -- | /O(n)/ Check if the vector does not contain an element (inverse of 'elem')
1211 notElem :: (Vector v a, Eq a) => a -> v a -> Bool
1212 {-# INLINE notElem #-}
1213 notElem x = Stream.notElem x . stream
1214
1215 -- | /O(n)/ Yield 'Just' the first element matching the predicate or 'Nothing'
1216 -- if no such element exists.
1217 find :: Vector v a => (a -> Bool) -> v a -> Maybe a
1218 {-# INLINE find #-}
1219 find f = Stream.find f . stream
1220
1221 -- | /O(n)/ Yield 'Just' the index of the first element matching the predicate
1222 -- or 'Nothing' if no such element exists.
1223 findIndex :: Vector v a => (a -> Bool) -> v a -> Maybe Int
1224 {-# INLINE findIndex #-}
1225 findIndex f = Stream.findIndex f . stream
1226
1227 -- | /O(n)/ Yield the indices of elements satisfying the predicate in ascending
1228 -- order.
1229 findIndices :: (Vector v a, Vector v Int) => (a -> Bool) -> v a -> v Int
1230 {-# INLINE findIndices #-}
1231 findIndices f = unstream
1232 . inplace (MStream.map fst . MStream.filter (f . snd)
1233 . MStream.indexed)
1234 . stream
1235
1236 -- | /O(n)/ Yield 'Just' the index of the first occurence of the given element or
1237 -- 'Nothing' if the vector does not contain the element. This is a specialised
1238 -- version of 'findIndex'.
1239 elemIndex :: (Vector v a, Eq a) => a -> v a -> Maybe Int
1240 {-# INLINE elemIndex #-}
1241 elemIndex x = findIndex (x==)
1242
1243 -- | /O(n)/ Yield the indices of all occurences of the given element in
1244 -- ascending order. This is a specialised version of 'findIndices'.
1245 elemIndices :: (Vector v a, Vector v Int, Eq a) => a -> v a -> v Int
1246 {-# INLINE elemIndices #-}
1247 elemIndices x = findIndices (x==)
1248
1249 -- Folding
1250 -- -------
1251
1252 -- | /O(n)/ Left fold
1253 foldl :: Vector v b => (a -> b -> a) -> a -> v b -> a
1254 {-# INLINE foldl #-}
1255 foldl f z = Stream.foldl f z . stream
1256
1257 -- | /O(n)/ Left fold on non-empty vectors
1258 foldl1 :: Vector v a => (a -> a -> a) -> v a -> a
1259 {-# INLINE foldl1 #-}
1260 foldl1 f = Stream.foldl1 f . stream
1261
1262 -- | /O(n)/ Left fold with strict accumulator
1263 foldl' :: Vector v b => (a -> b -> a) -> a -> v b -> a
1264 {-# INLINE foldl' #-}
1265 foldl' f z = Stream.foldl' f z . stream
1266
1267 -- | /O(n)/ Left fold on non-empty vectors with strict accumulator
1268 foldl1' :: Vector v a => (a -> a -> a) -> v a -> a
1269 {-# INLINE foldl1' #-}
1270 foldl1' f = Stream.foldl1' f . stream
1271
1272 -- | /O(n)/ Right fold
1273 foldr :: Vector v a => (a -> b -> b) -> b -> v a -> b
1274 {-# INLINE foldr #-}
1275 foldr f z = Stream.foldr f z . stream
1276
1277 -- | /O(n)/ Right fold on non-empty vectors
1278 foldr1 :: Vector v a => (a -> a -> a) -> v a -> a
1279 {-# INLINE foldr1 #-}
1280 foldr1 f = Stream.foldr1 f . stream
1281
1282 -- | /O(n)/ Right fold with a strict accumulator
1283 foldr' :: Vector v a => (a -> b -> b) -> b -> v a -> b
1284 {-# INLINE foldr' #-}
1285 foldr' f z = Stream.foldl' (flip f) z . streamR
1286
1287 -- | /O(n)/ Right fold on non-empty vectors with strict accumulator
1288 foldr1' :: Vector v a => (a -> a -> a) -> v a -> a
1289 {-# INLINE foldr1' #-}
1290 foldr1' f = Stream.foldl1' (flip f) . streamR
1291
1292 -- | /O(n)/ Left fold (function applied to each element and its index)
1293 ifoldl :: Vector v b => (a -> Int -> b -> a) -> a -> v b -> a
1294 {-# INLINE ifoldl #-}
1295 ifoldl f z = Stream.foldl (uncurry . f) z . Stream.indexed . stream
1296
1297 -- | /O(n)/ Left fold with strict accumulator (function applied to each element
1298 -- and its index)
1299 ifoldl' :: Vector v b => (a -> Int -> b -> a) -> a -> v b -> a
1300 {-# INLINE ifoldl' #-}
1301 ifoldl' f z = Stream.foldl' (uncurry . f) z . Stream.indexed . stream
1302
1303 -- | /O(n)/ Right fold (function applied to each element and its index)
1304 ifoldr :: Vector v a => (Int -> a -> b -> b) -> b -> v a -> b
1305 {-# INLINE ifoldr #-}
1306 ifoldr f z = Stream.foldr (uncurry f) z . Stream.indexed . stream
1307
1308 -- | /O(n)/ Right fold with strict accumulator (function applied to each
1309 -- element and its index)
1310 ifoldr' :: Vector v a => (Int -> a -> b -> b) -> b -> v a -> b
1311 {-# INLINE ifoldr' #-}
1312 ifoldr' f z xs = Stream.foldl' (flip (uncurry f)) z
1313 $ Stream.indexedR (length xs) $ streamR xs
1314
1315 -- Specialised folds
1316 -- -----------------
1317
1318 -- | /O(n)/ Check if all elements satisfy the predicate.
1319 all :: Vector v a => (a -> Bool) -> v a -> Bool
1320 {-# INLINE all #-}
1321 all f = Stream.and . Stream.map f . stream
1322
1323 -- | /O(n)/ Check if any element satisfies the predicate.
1324 any :: Vector v a => (a -> Bool) -> v a -> Bool
1325 {-# INLINE any #-}
1326 any f = Stream.or . Stream.map f . stream
1327
1328 -- | /O(n)/ Check if all elements are 'True'
1329 and :: Vector v Bool => v Bool -> Bool
1330 {-# INLINE and #-}
1331 and = Stream.and . stream
1332
1333 -- | /O(n)/ Check if any element is 'True'
1334 or :: Vector v Bool => v Bool -> Bool
1335 {-# INLINE or #-}
1336 or = Stream.or . stream
1337
1338 -- | /O(n)/ Compute the sum of the elements
1339 sum :: (Vector v a, Num a) => v a -> a
1340 {-# INLINE sum #-}
1341 sum = Stream.foldl' (+) 0 . stream
1342
1343 -- | /O(n)/ Compute the produce of the elements
1344 product :: (Vector v a, Num a) => v a -> a
1345 {-# INLINE product #-}
1346 product = Stream.foldl' (*) 1 . stream
1347
1348 -- | /O(n)/ Yield the maximum element of the vector. The vector may not be
1349 -- empty.
1350 maximum :: (Vector v a, Ord a) => v a -> a
1351 {-# INLINE maximum #-}
1352 maximum = Stream.foldl1' max . stream
1353
1354 -- | /O(n)/ Yield the maximum element of the vector according to the given
1355 -- comparison function. The vector may not be empty.
1356 maximumBy :: Vector v a => (a -> a -> Ordering) -> v a -> a
1357 {-# INLINE maximumBy #-}
1358 maximumBy cmp = Stream.foldl1' maxBy . stream
1359 where
1360 {-# INLINE maxBy #-}
1361 maxBy x y = case cmp x y of
1362 LT -> y
1363 _ -> x
1364
1365 -- | /O(n)/ Yield the minimum element of the vector. The vector may not be
1366 -- empty.
1367 minimum :: (Vector v a, Ord a) => v a -> a
1368 {-# INLINE minimum #-}
1369 minimum = Stream.foldl1' min . stream
1370
1371 -- | /O(n)/ Yield the minimum element of the vector according to the given
1372 -- comparison function. The vector may not be empty.
1373 minimumBy :: Vector v a => (a -> a -> Ordering) -> v a -> a
1374 {-# INLINE minimumBy #-}
1375 minimumBy cmp = Stream.foldl1' minBy . stream
1376 where
1377 {-# INLINE minBy #-}
1378 minBy x y = case cmp x y of
1379 GT -> y
1380 _ -> x
1381
1382 -- | /O(n)/ Yield the index of the maximum element of the vector. The vector
1383 -- may not be empty.
1384 maxIndex :: (Vector v a, Ord a) => v a -> Int
1385 {-# INLINE maxIndex #-}
1386 maxIndex = maxIndexBy compare
1387
1388 -- | /O(n)/ Yield the index of the maximum element of the vector according to
1389 -- the given comparison function. The vector may not be empty.
1390 maxIndexBy :: Vector v a => (a -> a -> Ordering) -> v a -> Int
1391 {-# INLINE maxIndexBy #-}
1392 maxIndexBy cmp = fst . Stream.foldl1' imax . Stream.indexed . stream
1393 where
1394 imax (i,x) (j,y) = i `seq` j `seq`
1395 case cmp x y of
1396 LT -> (j,y)
1397 _ -> (i,x)
1398
1399 -- | /O(n)/ Yield the index of the minimum element of the vector. The vector
1400 -- may not be empty.
1401 minIndex :: (Vector v a, Ord a) => v a -> Int
1402 {-# INLINE minIndex #-}
1403 minIndex = minIndexBy compare
1404
1405 -- | /O(n)/ Yield the index of the minimum element of the vector according to
1406 -- the given comparison function. The vector may not be empty.
1407 minIndexBy :: Vector v a => (a -> a -> Ordering) -> v a -> Int
1408 {-# INLINE minIndexBy #-}
1409 minIndexBy cmp = fst . Stream.foldl1' imin . Stream.indexed . stream
1410 where
1411 imin (i,x) (j,y) = i `seq` j `seq`
1412 case cmp x y of
1413 GT -> (j,y)
1414 _ -> (i,x)
1415
1416 -- Monadic folds
1417 -- -------------
1418
1419 -- | /O(n)/ Monadic fold
1420 foldM :: (Monad m, Vector v b) => (a -> b -> m a) -> a -> v b -> m a
1421 {-# INLINE foldM #-}
1422 foldM m z = Stream.foldM m z . stream
1423
1424 -- | /O(n)/ Monadic fold over non-empty vectors
1425 fold1M :: (Monad m, Vector v a) => (a -> a -> m a) -> v a -> m a
1426 {-# INLINE fold1M #-}
1427 fold1M m = Stream.fold1M m . stream
1428
1429 -- | /O(n)/ Monadic fold with strict accumulator
1430 foldM' :: (Monad m, Vector v b) => (a -> b -> m a) -> a -> v b -> m a
1431 {-# INLINE foldM' #-}
1432 foldM' m z = Stream.foldM' m z . stream
1433
1434 -- | /O(n)/ Monad fold over non-empty vectors with strict accumulator
1435 fold1M' :: (Monad m, Vector v a) => (a -> a -> m a) -> v a -> m a
1436 {-# INLINE fold1M' #-}
1437 fold1M' m = Stream.fold1M' m . stream
1438
1439 -- Prefix sums (scans)
1440 -- -------------------
1441
1442 -- | /O(n)/ Prescan
1443 --
1444 -- @
1445 -- prescanl f z = 'init' . 'scanl' f z
1446 -- @
1447 --
1448 -- Example: @prescanl (+) 0 \<1,2,3,4\> = \<0,1,3,6\>@
1449 --
1450 prescanl :: (Vector v a, Vector v b) => (a -> b -> a) -> a -> v b -> v a
1451 {-# INLINE prescanl #-}
1452 prescanl f z = unstream . inplace (MStream.prescanl f z) . stream
1453
1454 -- | /O(n)/ Prescan with strict accumulator
1455 prescanl' :: (Vector v a, Vector v b) => (a -> b -> a) -> a -> v b -> v a
1456 {-# INLINE prescanl' #-}
1457 prescanl' f z = unstream . inplace (MStream.prescanl' f z) . stream
1458
1459 -- | /O(n)/ Scan
1460 --
1461 -- @
1462 -- postscanl f z = 'tail' . 'scanl' f z
1463 -- @
1464 --
1465 -- Example: @postscanl (+) 0 \<1,2,3,4\> = \<1,3,6,10\>@
1466 --
1467 postscanl :: (Vector v a, Vector v b) => (a -> b -> a) -> a -> v b -> v a
1468 {-# INLINE postscanl #-}
1469 postscanl f z = unstream . inplace (MStream.postscanl f z) . stream
1470
1471 -- | /O(n)/ Scan with strict accumulator
1472 postscanl' :: (Vector v a, Vector v b) => (a -> b -> a) -> a -> v b -> v a
1473 {-# INLINE postscanl' #-}
1474 postscanl' f z = unstream . inplace (MStream.postscanl' f z) . stream
1475
1476 -- | /O(n)/ Haskell-style scan
1477 --
1478 -- > scanl f z <x1,...,xn> = <y1,...,y(n+1)>
1479 -- > where y1 = z
1480 -- > yi = f y(i-1) x(i-1)
1481 --
1482 -- Example: @scanl (+) 0 \<1,2,3,4\> = \<0,1,3,6,10\>@
1483 --
1484 scanl :: (Vector v a, Vector v b) => (a -> b -> a) -> a -> v b -> v a
1485 {-# INLINE scanl #-}
1486 scanl f z = unstream . Stream.scanl f z . stream
1487
1488 -- | /O(n)/ Haskell-style scan with strict accumulator
1489 scanl' :: (Vector v a, Vector v b) => (a -> b -> a) -> a -> v b -> v a
1490 {-# INLINE scanl' #-}
1491 scanl' f z = unstream . Stream.scanl' f z . stream
1492
1493 -- | /O(n)/ Scan over a non-empty vector
1494 --
1495 -- > scanl f <x1,...,xn> = <y1,...,yn>
1496 -- > where y1 = x1
1497 -- > yi = f y(i-1) xi
1498 --
1499 scanl1 :: Vector v a => (a -> a -> a) -> v a -> v a
1500 {-# INLINE scanl1 #-}
1501 scanl1 f = unstream . inplace (MStream.scanl1 f) . stream
1502
1503 -- | /O(n)/ Scan over a non-empty vector with a strict accumulator
1504 scanl1' :: Vector v a => (a -> a -> a) -> v a -> v a
1505 {-# INLINE scanl1' #-}
1506 scanl1' f = unstream . inplace (MStream.scanl1' f) . stream
1507
1508 -- | /O(n)/ Right-to-left prescan
1509 --
1510 -- @
1511 -- prescanr f z = 'reverse' . 'prescanl' (flip f) z . 'reverse'
1512 -- @
1513 --
1514 prescanr :: (Vector v a, Vector v b) => (a -> b -> b) -> b -> v a -> v b
1515 {-# INLINE prescanr #-}
1516 prescanr f z = unstreamR . inplace (MStream.prescanl (flip f) z) . streamR
1517
1518 -- | /O(n)/ Right-to-left prescan with strict accumulator
1519 prescanr' :: (Vector v a, Vector v b) => (a -> b -> b) -> b -> v a -> v b
1520 {-# INLINE prescanr' #-}
1521 prescanr' f z = unstreamR . inplace (MStream.prescanl' (flip f) z) . streamR
1522
1523 -- | /O(n)/ Right-to-left scan
1524 postscanr :: (Vector v a, Vector v b) => (a -> b -> b) -> b -> v a -> v b
1525 {-# INLINE postscanr #-}
1526 postscanr f z = unstreamR . inplace (MStream.postscanl (flip f) z) . streamR
1527
1528 -- | /O(n)/ Right-to-left scan with strict accumulator
1529 postscanr' :: (Vector v a, Vector v b) => (a -> b -> b) -> b -> v a -> v b
1530 {-# INLINE postscanr' #-}
1531 postscanr' f z = unstreamR . inplace (MStream.postscanl' (flip f) z) . streamR
1532
1533 -- | /O(n)/ Right-to-left Haskell-style scan
1534 scanr :: (Vector v a, Vector v b) => (a -> b -> b) -> b -> v a -> v b
1535 {-# INLINE scanr #-}
1536 scanr f z = unstreamR . Stream.scanl (flip f) z . streamR
1537
1538 -- | /O(n)/ Right-to-left Haskell-style scan with strict accumulator
1539 scanr' :: (Vector v a, Vector v b) => (a -> b -> b) -> b -> v a -> v b
1540 {-# INLINE scanr' #-}
1541 scanr' f z = unstreamR . Stream.scanl' (flip f) z . streamR
1542
1543 -- | /O(n)/ Right-to-left scan over a non-empty vector
1544 scanr1 :: Vector v a => (a -> a -> a) -> v a -> v a
1545 {-# INLINE scanr1 #-}
1546 scanr1 f = unstreamR . inplace (MStream.scanl1 (flip f)) . streamR
1547
1548 -- | /O(n)/ Right-to-left scan over a non-empty vector with a strict
1549 -- accumulator
1550 scanr1' :: Vector v a => (a -> a -> a) -> v a -> v a
1551 {-# INLINE scanr1' #-}
1552 scanr1' f = unstreamR . inplace (MStream.scanl1' (flip f)) . streamR
1553
1554 -- Conversions - Lists
1555 -- ------------------------
1556
1557 -- | /O(n)/ Convert a vector to a list
1558 toList :: Vector v a => v a -> [a]
1559 {-# INLINE toList #-}
1560 toList = Stream.toList . stream
1561
1562 -- | /O(n)/ Convert a list to a vector
1563 fromList :: Vector v a => [a] -> v a
1564 {-# INLINE fromList #-}
1565 fromList = unstream . Stream.fromList
1566
1567 -- | /O(n)/ Convert the first @n@ elements of a list to a vector
1568 --
1569 -- @
1570 -- fromListN n xs = 'fromList' ('take' n xs)
1571 -- @
1572 fromListN :: Vector v a => Int -> [a] -> v a
1573 {-# INLINE fromListN #-}
1574 fromListN n = unstream . Stream.fromListN n
1575
1576 -- Conversions - Immutable vectors
1577 -- -------------------------------
1578
1579 -- | /O(n)/ Convert different vector types
1580 convert :: (Vector v a, Vector w a) => v a -> w a
1581 {-# INLINE convert #-}
1582 convert = unstream . stream
1583
1584 -- Conversions - Mutable vectors
1585 -- -----------------------------
1586
1587 -- | /O(1)/ Unsafe convert a mutable vector to an immutable one without
1588 -- copying. The mutable vector may not be used after this operation.
1589 unsafeFreeze
1590 :: (PrimMonad m, Vector v a) => Mutable v (PrimState m) a -> m (v a)
1591 {-# INLINE unsafeFreeze #-}
1592 unsafeFreeze = basicUnsafeFreeze
1593
1594
1595 -- | /O(1)/ Unsafely convert an immutable vector to a mutable one without
1596 -- copying. The immutable vector may not be used after this operation.
1597 unsafeThaw :: (PrimMonad m, Vector v a) => v a -> m (Mutable v (PrimState m) a)
1598 {-# INLINE unsafeThaw #-}
1599 unsafeThaw = basicUnsafeThaw
1600
1601 -- | /O(n)/ Yield a mutable copy of the immutable vector.
1602 thaw :: (PrimMonad m, Vector v a) => v a -> m (Mutable v (PrimState m) a)
1603 {-# INLINE_STREAM thaw #-}
1604 thaw v = do
1605 mv <- M.unsafeNew (length v)
1606 unsafeCopy mv v
1607 return mv
1608
1609 -- | /O(n)/ Yield an immutable copy of the mutable vector.
1610 freeze :: (PrimMonad m, Vector v a) => Mutable v (PrimState m) a -> m (v a)
1611 {-# INLINE freeze #-}
1612 freeze mv = unsafeFreeze =<< M.clone mv
1613
1614 {-
1615 -- | /O(n)/ Yield a mutable vector containing copies of each vector in the
1616 -- list.
1617 thawMany :: (PrimMonad m, Vector v a) => [v a] -> m (Mutable v (PrimState m) a)
1618 {-# INLINE_STREAM thawMany #-}
1619 -- FIXME: add rule for (stream (new (New.create (thawMany vs))))
1620 -- NOTE: We don't try to consume the list lazily as this wouldn't significantly
1621 -- change the space requirements anyway.
1622 thawMany vs = do
1623 mv <- M.new n
1624 thaw_loop mv vs
1625 return mv
1626 where
1627 n = List.foldl' (\k v -> k + length v) 0 vs
1628
1629 thaw_loop mv [] = mv `seq` return ()
1630 thaw_loop mv (v:vs)
1631 = do
1632 let n = length v
1633 unsafeCopy (M.unsafeTake n mv) v
1634 thaw_loop (M.unsafeDrop n mv) vs
1635 -}
1636
1637 -- | /O(n)/ Copy an immutable vector into a mutable one. The two vectors must
1638 -- have the same length.
1639 copy
1640 :: (PrimMonad m, Vector v a) => Mutable v (PrimState m) a -> v a -> m ()
1641 {-# INLINE copy #-}
1642 copy dst src = BOUNDS_CHECK(check) "copy" "length mismatch"
1643 (M.length dst == length src)
1644 $ unsafeCopy dst src
1645
1646 -- | /O(n)/ Copy an immutable vector into a mutable one. The two vectors must
1647 -- have the same length. This is not checked.
1648 unsafeCopy
1649 :: (PrimMonad m, Vector v a) => Mutable v (PrimState m) a -> v a -> m ()
1650 {-# INLINE unsafeCopy #-}
1651 unsafeCopy dst src = UNSAFE_CHECK(check) "unsafeCopy" "length mismatch"
1652 (M.length dst == length src)
1653 $ (dst `seq` src `seq` basicUnsafeCopy dst src)
1654
1655 -- Conversions to/from Streams
1656 -- ---------------------------
1657
1658 -- | /O(1)/ Convert a vector to a 'Stream'
1659 stream :: Vector v a => v a -> Stream a
1660 {-# INLINE_STREAM stream #-}
1661 stream v = v `seq` n `seq` (Stream.unfoldr get 0 `Stream.sized` Exact n)
1662 where
1663 n = length v
1664
1665 -- NOTE: the False case comes first in Core so making it the recursive one
1666 -- makes the code easier to read
1667 {-# INLINE get #-}
1668 get i | i >= n = Nothing
1669 | otherwise = case basicUnsafeIndexM v i of Box x -> Just (x, i+1)
1670
1671 -- | /O(n)/ Construct a vector from a 'Stream'
1672 unstream :: Vector v a => Stream a -> v a
1673 {-# INLINE unstream #-}
1674 unstream s = new (New.unstream s)
1675
1676 {-# RULES
1677
1678 "stream/unstream [Vector]" forall s.
1679 stream (new (New.unstream s)) = s
1680
1681 "New.unstream/stream [Vector]" forall v.
1682 New.unstream (stream v) = clone v
1683
1684 "clone/new [Vector]" forall p.
1685 clone (new p) = p
1686
1687 "inplace [Vector]"
1688 forall (f :: forall m. Monad m => MStream m a -> MStream m a) m.
1689 New.unstream (inplace f (stream (new m))) = New.transform f m
1690
1691 "uninplace [Vector]"
1692 forall (f :: forall m. Monad m => MStream m a -> MStream m a) m.
1693 stream (new (New.transform f m)) = inplace f (stream (new m))
1694
1695 #-}
1696
1697 -- | /O(1)/ Convert a vector to a 'Stream', proceeding from right to left
1698 streamR :: Vector v a => v a -> Stream a
1699 {-# INLINE_STREAM streamR #-}
1700 streamR v = v `seq` n `seq` (Stream.unfoldr get n `Stream.sized` Exact n)
1701 where
1702 n = length v
1703
1704 {-# INLINE get #-}
1705 get 0 = Nothing
1706 get i = let i' = i-1
1707 in
1708 case basicUnsafeIndexM v i' of Box x -> Just (x, i')
1709
1710 -- | /O(n)/ Construct a vector from a 'Stream', proceeding from right to left
1711 unstreamR :: Vector v a => Stream a -> v a
1712 {-# INLINE unstreamR #-}
1713 unstreamR s = new (New.unstreamR s)
1714
1715 {-# RULES
1716
1717 "streamR/unstreamR [Vector]" forall s.
1718 streamR (new (New.unstreamR s)) = s
1719
1720 "New.unstreamR/streamR/new [Vector]" forall p.
1721 New.unstreamR (streamR (new p)) = p
1722
1723 "inplace right [Vector]"
1724 forall (f :: forall m. Monad m => MStream m a -> MStream m a) m.
1725 New.unstreamR (inplace f (streamR (new m))) = New.transformR f m
1726
1727 "uninplace right [Vector]"
1728 forall (f :: forall m. Monad m => MStream m a -> MStream m a) m.
1729 streamR (new (New.transformR f m)) = inplace f (streamR (new m))
1730
1731 #-}
1732
1733 unstreamM :: (Vector v a, Monad m) => MStream m a -> m (v a)
1734 {-# INLINE_STREAM unstreamM #-}
1735 unstreamM s = do
1736 xs <- MStream.toList s
1737 return $ unstream $ Stream.unsafeFromList (MStream.size s) xs
1738
1739 -- Recycling support
1740 -- -----------------
1741
1742 -- | Construct a vector from a monadic initialiser.
1743 new :: Vector v a => New v a -> v a
1744 {-# INLINE_STREAM new #-}
1745 new m = m `seq` runST (unsafeFreeze =<< New.run m)
1746
1747 -- | Convert a vector to an initialiser which, when run, produces a copy of
1748 -- the vector.
1749 clone :: Vector v a => v a -> New v a
1750 {-# INLINE_STREAM clone #-}
1751 clone v = v `seq` New.create (
1752 do
1753 mv <- M.new (length v)
1754 unsafeCopy mv v
1755 return mv)
1756
1757 -- Comparisons
1758 -- -----------
1759
1760 -- | /O(n)/ Check if two vectors are equal. All 'Vector' instances are also
1761 -- instances of 'Eq' and it is usually more appropriate to use those. This
1762 -- function is primarily intended for implementing 'Eq' instances for new
1763 -- vector types.
1764 eq :: (Vector v a, Eq a) => v a -> v a -> Bool
1765 {-# INLINE eq #-}
1766 xs `eq` ys = stream xs == stream ys
1767
1768 -- | /O(n)/ Compare two vectors lexicographically. All 'Vector' instances are
1769 -- also instances of 'Ord' and it is usually more appropriate to use those. This
1770 -- function is primarily intended for implementing 'Ord' instances for new
1771 -- vector types.
1772 cmp :: (Vector v a, Ord a) => v a -> v a -> Ordering
1773 {-# INLINE cmp #-}
1774 cmp xs ys = compare (stream xs) (stream ys)
1775
1776 -- Data and Typeable
1777 -- -----------------
1778
1779 -- | Generic definion of 'Data.Data.gfoldl' that views a 'Vector' as a
1780 -- list.
1781 gfoldl :: (Vector v a, Data a)
1782 => (forall d b. Data d => c (d -> b) -> d -> c b)
1783 -> (forall g. g -> c g)
1784 -> v a
1785 -> c (v a)
1786 {-# INLINE gfoldl #-}
1787 gfoldl f z v = z fromList `f` toList v
1788
1789 mkType :: String -> DataType
1790 {-# INLINE mkType #-}
1791 mkType = mkNorepType
1792
1793 dataCast :: (Vector v a, Data a, Typeable1 v, Typeable1 t)
1794 => (forall d. Data d => c (t d)) -> Maybe (c (v a))
1795 {-# INLINE dataCast #-}
1796 dataCast f = gcast1 f
1797