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