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