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