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