Add concat and make concatMap more efficient
[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 -- ** 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, (++), concat,
169 head, last,
170 init, tail, take, drop, reverse,
171 map, concat, 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 -- | /O(n)/ Concatenate all vectors in the list
565 concat :: Vector v a => [v a] -> v a
566 {-# INLINE concat #-}
567 concat vs = create (thawMany vs)
568
569 -- Monadic initialisation
570 -- ----------------------
571
572 -- | /O(n)/ Execute the monadic action the given number of times and store the
573 -- results in a vector.
574 replicateM :: (Monad m, Vector v a) => Int -> m a -> m (v a)
575 -- FIXME: specialise for ST and IO?
576 {-# INLINE replicateM #-}
577 replicateM n m = fromListN n `Monad.liftM` Monad.replicateM n m
578
579 -- | Execute the monadic action and freeze the resulting vector.
580 --
581 -- @
582 -- create (do { v \<- 'M.new' 2; 'M.write' v 0 \'a\'; 'M.write' v 1 \'b\' }) = \<'a','b'\>
583 -- @
584 create :: Vector v a => (forall s. ST s (Mutable v s a)) -> v a
585 {-# INLINE create #-}
586 create p = new (New.create p)
587
588 -- Restricting memory usage
589 -- ------------------------
590
591 -- | /O(n)/ Yield the argument but force it not to retain any extra memory,
592 -- possibly by copying it.
593 --
594 -- This is especially useful when dealing with slices. For example:
595 --
596 -- > force (slice 0 2 <huge vector>)
597 --
598 -- Here, the slice retains a reference to the huge vector. Forcing it creates
599 -- a copy of just the elements that belong to the slice and allows the huge
600 -- vector to be garbage collected.
601 force :: Vector v a => v a -> v a
602 -- FIXME: we probably ought to inline this later as the rules still might fire
603 -- otherwise
604 {-# INLINE_STREAM force #-}
605 force v = new (clone v)
606
607 -- Bulk updates
608 -- ------------
609
610 -- | /O(m+n)/ For each pair @(i,a)@ from the list, replace the vector
611 -- element at position @i@ by @a@.
612 --
613 -- > <5,9,2,7> // [(2,1),(0,3),(2,8)] = <3,9,8,7>
614 --
615 (//) :: Vector v a => v a -- ^ initial vector (of length @m@)
616 -> [(Int, a)] -- ^ list of index/value pairs (of length @n@)
617 -> v a
618 {-# INLINE (//) #-}
619 v // us = update_stream v (Stream.fromList us)
620
621 -- | /O(m+n)/ For each pair @(i,a)@ from the vector of index/value pairs,
622 -- replace the vector element at position @i@ by @a@.
623 --
624 -- > update <5,9,2,7> <(2,1),(0,3),(2,8)> = <3,9,8,7>
625 --
626 update :: (Vector v a, Vector v (Int, a))
627 => v a -- ^ initial vector (of length @m@)
628 -> v (Int, a) -- ^ vector of index/value pairs (of length @n@)
629 -> v a
630 {-# INLINE update #-}
631 update v w = update_stream v (stream w)
632
633 -- | /O(m+min(n1,n2))/ For each index @i@ from the index vector and the
634 -- corresponding value @a@ from the value vector, replace the element of the
635 -- initial vector at position @i@ by @a@.
636 --
637 -- > update_ <5,9,2,7> <2,0,2> <1,3,8> = <3,9,8,7>
638 --
639 -- This function is useful for instances of 'Vector' that cannot store pairs.
640 -- Otherwise, 'update' is probably more convenient.
641 --
642 -- @
643 -- update_ xs is ys = 'update' xs ('zip' is ys)
644 -- @
645 update_ :: (Vector v a, Vector v Int)
646 => v a -- ^ initial vector (of length @m@)
647 -> v Int -- ^ index vector (of length @n1@)
648 -> v a -- ^ value vector (of length @n2@)
649 -> v a
650 {-# INLINE update_ #-}
651 update_ v is w = update_stream v (Stream.zipWith (,) (stream is) (stream w))
652
653 update_stream :: Vector v a => v a -> Stream (Int,a) -> v a
654 {-# INLINE update_stream #-}
655 update_stream = modifyWithStream M.update
656
657 -- | Same as ('//') but without bounds checking.
658 unsafeUpd :: Vector v a => v a -> [(Int, a)] -> v a
659 {-# INLINE unsafeUpd #-}
660 unsafeUpd v us = unsafeUpdate_stream v (Stream.fromList us)
661
662 -- | Same as 'update' but without bounds checking.
663 unsafeUpdate :: (Vector v a, Vector v (Int, a)) => v a -> v (Int, a) -> v a
664 {-# INLINE unsafeUpdate #-}
665 unsafeUpdate v w = unsafeUpdate_stream v (stream w)
666
667 -- | Same as 'update_' but without bounds checking.
668 unsafeUpdate_ :: (Vector v a, Vector v Int) => v a -> v Int -> v a -> v a
669 {-# INLINE unsafeUpdate_ #-}
670 unsafeUpdate_ v is w
671 = unsafeUpdate_stream v (Stream.zipWith (,) (stream is) (stream w))
672
673 unsafeUpdate_stream :: Vector v a => v a -> Stream (Int,a) -> v a
674 {-# INLINE unsafeUpdate_stream #-}
675 unsafeUpdate_stream = modifyWithStream M.unsafeUpdate
676
677 -- Accumulations
678 -- -------------
679
680 -- | /O(m+n)/ For each pair @(i,b)@ from the list, replace the vector element
681 -- @a@ at position @i@ by @f a b@.
682 --
683 -- > accum (+) <5,9,2> [(2,4),(1,6),(0,3),(1,7)] = <5+3, 9+6+7, 2+4>
684 accum :: Vector v a
685 => (a -> b -> a) -- ^ accumulating function @f@
686 -> v a -- ^ initial vector (of length @m@)
687 -> [(Int,b)] -- ^ list of index/value pairs (of length @n@)
688 -> v a
689 {-# INLINE accum #-}
690 accum f v us = accum_stream f v (Stream.fromList us)
691
692 -- | /O(m+n)/ For each pair @(i,b)@ from the vector of pairs, replace the vector
693 -- element @a@ at position @i@ by @f a b@.
694 --
695 -- > accumulate (+) <5,9,2> <(2,4),(1,6),(0,3),(1,7)> = <5+3, 9+6+7, 2+4>
696 accumulate :: (Vector v a, Vector v (Int, b))
697 => (a -> b -> a) -- ^ accumulating function @f@
698 -> v a -- ^ initial vector (of length @m@)
699 -> v (Int,b) -- ^ vector of index/value pairs (of length @n@)
700 -> v a
701 {-# INLINE accumulate #-}
702 accumulate f v us = accum_stream f v (stream us)
703
704 -- | /O(m+min(n1,n2))/ For each index @i@ from the index vector and the
705 -- corresponding value @b@ from the the value vector,
706 -- replace the element of the initial vector at
707 -- position @i@ by @f a b@.
708 --
709 -- > accumulate_ (+) <5,9,2> <2,1,0,1> <4,6,3,7> = <5+3, 9+6+7, 2+4>
710 --
711 -- This function is useful for instances of 'Vector' that cannot store pairs.
712 -- Otherwise, 'accumulate' is probably more convenient:
713 --
714 -- @
715 -- accumulate_ f as is bs = 'accumulate' f as ('zip' is bs)
716 -- @
717 accumulate_ :: (Vector v a, Vector v Int, Vector v b)
718 => (a -> b -> a) -- ^ accumulating function @f@
719 -> v a -- ^ initial vector (of length @m@)
720 -> v Int -- ^ index vector (of length @n1@)
721 -> v b -- ^ value vector (of length @n2@)
722 -> v a
723 {-# INLINE accumulate_ #-}
724 accumulate_ f v is xs = accum_stream f v (Stream.zipWith (,) (stream is)
725 (stream xs))
726
727
728 accum_stream :: Vector v a => (a -> b -> a) -> v a -> Stream (Int,b) -> v a
729 {-# INLINE accum_stream #-}
730 accum_stream f = modifyWithStream (M.accum f)
731
732 -- | Same as 'accum' but without bounds checking.
733 unsafeAccum :: Vector v a => (a -> b -> a) -> v a -> [(Int,b)] -> v a
734 {-# INLINE unsafeAccum #-}
735 unsafeAccum f v us = unsafeAccum_stream f v (Stream.fromList us)
736
737 -- | Same as 'accumulate' but without bounds checking.
738 unsafeAccumulate :: (Vector v a, Vector v (Int, b))
739 => (a -> b -> a) -> v a -> v (Int,b) -> v a
740 {-# INLINE unsafeAccumulate #-}
741 unsafeAccumulate f v us = unsafeAccum_stream f v (stream us)
742
743 -- | Same as 'accumulate_' but without bounds checking.
744 unsafeAccumulate_ :: (Vector v a, Vector v Int, Vector v b)
745 => (a -> b -> a) -> v a -> v Int -> v b -> v a
746 {-# INLINE unsafeAccumulate_ #-}
747 unsafeAccumulate_ f v is xs
748 = unsafeAccum_stream f v (Stream.zipWith (,) (stream is) (stream xs))
749
750 unsafeAccum_stream
751 :: Vector v a => (a -> b -> a) -> v a -> Stream (Int,b) -> v a
752 {-# INLINE unsafeAccum_stream #-}
753 unsafeAccum_stream f = modifyWithStream (M.unsafeAccum f)
754
755 -- Permutations
756 -- ------------
757
758 -- | /O(n)/ Reverse a vector
759 reverse :: (Vector v a) => v a -> v a
760 {-# INLINE reverse #-}
761 -- FIXME: make this fuse better, add support for recycling
762 reverse = unstream . streamR
763
764 -- | /O(n)/ Yield the vector obtained by replacing each element @i@ of the
765 -- index vector by @xs'!'i@. This is equivalent to @'map' (xs'!') is@ but is
766 -- often much more efficient.
767 --
768 -- > backpermute <a,b,c,d> <0,3,2,3,1,0> = <a,d,c,d,b,a>
769 backpermute :: (Vector v a, Vector v Int)
770 => v a -- ^ @xs@ value vector
771 -> v Int -- ^ @is@ index vector (of length @n@)
772 -> v a
773 {-# INLINE backpermute #-}
774 -- This somewhat non-intuitive definition ensures that the resulting vector
775 -- does not retain references to the original one even if it is lazy in its
776 -- elements. This would not be the case if we simply used map (v!)
777 backpermute v is = seq v
778 $ unstream
779 $ Stream.unbox
780 $ Stream.map (indexM v)
781 $ stream is
782
783 -- | Same as 'backpermute' but without bounds checking.
784 unsafeBackpermute :: (Vector v a, Vector v Int) => v a -> v Int -> v a
785 {-# INLINE unsafeBackpermute #-}
786 unsafeBackpermute v is = seq v
787 $ unstream
788 $ Stream.unbox
789 $ Stream.map (unsafeIndexM v)
790 $ stream is
791
792 -- Safe destructive updates
793 -- ------------------------
794
795 -- | Apply a destructive operation to a vector. The operation will be
796 -- performed in place if it is safe to do so and will modify a copy of the
797 -- vector otherwise.
798 --
799 -- @
800 -- modify (\\v -> 'M.write' v 0 \'x\') ('replicate' 3 \'a\') = \<\'x\',\'a\',\'a\'\>
801 -- @
802 modify :: Vector v a => (forall s. Mutable v s a -> ST s ()) -> v a -> v a
803 {-# INLINE modify #-}
804 modify p = new . New.modify p . clone
805
806 -- We have to make sure that this is strict in the stream but we can't seq on
807 -- it while fusion is happening. Hence this ugliness.
808 modifyWithStream :: Vector v a
809 => (forall s. Mutable v s a -> Stream b -> ST s ())
810 -> v a -> Stream b -> v a
811 {-# INLINE modifyWithStream #-}
812 modifyWithStream p v s = new (New.modifyWithStream p (clone v) s)
813
814 -- Mapping
815 -- -------
816
817 -- | /O(n)/ Map a function over a vector
818 map :: (Vector v a, Vector v b) => (a -> b) -> v a -> v b
819 {-# INLINE map #-}
820 map f = unstream . inplace (MStream.map f) . stream
821
822 -- | /O(n)/ Apply a function to every element of a vector and its index
823 imap :: (Vector v a, Vector v b) => (Int -> a -> b) -> v a -> v b
824 {-# INLINE imap #-}
825 imap f = unstream . inplace (MStream.map (uncurry f) . MStream.indexed)
826 . stream
827
828 -- | Map a function over a vector and concatenate the results.
829 concatMap :: (Vector v a, Vector v b) => (a -> v b) -> v a -> v b
830 {-# INLINE concatMap #-}
831 -- NOTE: We can't fuse concatMap anyway so don't pretend we do.
832 -- concatMap f = unstream . Stream.concatMap (stream . f) . stream
833 concatMap f = concat . Stream.toList . Stream.map f . stream
834
835 -- Monadic mapping
836 -- ---------------
837
838 -- | /O(n)/ Apply the monadic action to all elements of the vector, yielding a
839 -- vector of results
840 mapM :: (Monad m, Vector v a, Vector v b) => (a -> m b) -> v a -> m (v b)
841 -- FIXME: specialise for ST and IO?
842 {-# INLINE mapM #-}
843 mapM f = unstreamM . Stream.mapM f . stream
844
845 -- | /O(n)/ Apply the monadic action to all elements of a vector and ignore the
846 -- results
847 mapM_ :: (Monad m, Vector v a) => (a -> m b) -> v a -> m ()
848 {-# INLINE mapM_ #-}
849 mapM_ f = Stream.mapM_ f . stream
850
851 -- | /O(n)/ Apply the monadic action to all elements of the vector, yielding a
852 -- vector of results. Equvalent to @flip 'mapM'@.
853 forM :: (Monad m, Vector v a, Vector v b) => v a -> (a -> m b) -> m (v b)
854 {-# INLINE forM #-}
855 forM as f = mapM f as
856
857 -- | /O(n)/ Apply the monadic action to all elements of a vector and ignore the
858 -- results. Equivalent to @flip 'mapM_'@.
859 forM_ :: (Monad m, Vector v a) => v a -> (a -> m b) -> m ()
860 {-# INLINE forM_ #-}
861 forM_ as f = mapM_ f as
862
863 -- Zipping
864 -- -------
865
866 -- | /O(min(m,n))/ Zip two vectors with the given function.
867 zipWith :: (Vector v a, Vector v b, Vector v c)
868 => (a -> b -> c) -> v a -> v b -> v c
869 {-# INLINE zipWith #-}
870 zipWith f xs ys = unstream (Stream.zipWith f (stream xs) (stream ys))
871
872 -- | Zip three vectors with the given function.
873 zipWith3 :: (Vector v a, Vector v b, Vector v c, Vector v d)
874 => (a -> b -> c -> d) -> v a -> v b -> v c -> v d
875 {-# INLINE zipWith3 #-}
876 zipWith3 f as bs cs = unstream (Stream.zipWith3 f (stream as)
877 (stream bs)
878 (stream cs))
879
880 zipWith4 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e)
881 => (a -> b -> c -> d -> e) -> v a -> v b -> v c -> v d -> v e
882 {-# INLINE zipWith4 #-}
883 zipWith4 f as bs cs ds
884 = unstream (Stream.zipWith4 f (stream as)
885 (stream bs)
886 (stream cs)
887 (stream ds))
888
889 zipWith5 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e,
890 Vector v f)
891 => (a -> b -> c -> d -> e -> f) -> v a -> v b -> v c -> v d -> v e
892 -> v f
893 {-# INLINE zipWith5 #-}
894 zipWith5 f as bs cs ds es
895 = unstream (Stream.zipWith5 f (stream as)
896 (stream bs)
897 (stream cs)
898 (stream ds)
899 (stream es))
900
901 zipWith6 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e,
902 Vector v f, Vector v g)
903 => (a -> b -> c -> d -> e -> f -> g)
904 -> v a -> v b -> v c -> v d -> v e -> v f -> v g
905 {-# INLINE zipWith6 #-}
906 zipWith6 f as bs cs ds es fs
907 = unstream (Stream.zipWith6 f (stream as)
908 (stream bs)
909 (stream cs)
910 (stream ds)
911 (stream es)
912 (stream fs))
913
914 -- | /O(min(m,n))/ Zip two vectors with a function that also takes the
915 -- elements' indices.
916 izipWith :: (Vector v a, Vector v b, Vector v c)
917 => (Int -> a -> b -> c) -> v a -> v b -> v c
918 {-# INLINE izipWith #-}
919 izipWith f xs ys = unstream
920 (Stream.zipWith (uncurry f) (Stream.indexed (stream xs))
921 (stream ys))
922
923 izipWith3 :: (Vector v a, Vector v b, Vector v c, Vector v d)
924 => (Int -> a -> b -> c -> d) -> v a -> v b -> v c -> v d
925 {-# INLINE izipWith3 #-}
926 izipWith3 f as bs cs
927 = unstream (Stream.zipWith3 (uncurry f) (Stream.indexed (stream as))
928 (stream bs)
929 (stream cs))
930
931 izipWith4 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e)
932 => (Int -> a -> b -> c -> d -> e) -> v a -> v b -> v c -> v d -> v e
933 {-# INLINE izipWith4 #-}
934 izipWith4 f as bs cs ds
935 = unstream (Stream.zipWith4 (uncurry f) (Stream.indexed (stream as))
936 (stream bs)
937 (stream cs)
938 (stream ds))
939
940 izipWith5 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e,
941 Vector v f)
942 => (Int -> a -> b -> c -> d -> e -> f) -> v a -> v b -> v c -> v d
943 -> v e -> v f
944 {-# INLINE izipWith5 #-}
945 izipWith5 f as bs cs ds es
946 = unstream (Stream.zipWith5 (uncurry f) (Stream.indexed (stream as))
947 (stream bs)
948 (stream cs)
949 (stream ds)
950 (stream es))
951
952 izipWith6 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e,
953 Vector v f, Vector v g)
954 => (Int -> a -> b -> c -> d -> e -> f -> g)
955 -> v a -> v b -> v c -> v d -> v e -> v f -> v g
956 {-# INLINE izipWith6 #-}
957 izipWith6 f as bs cs ds es fs
958 = unstream (Stream.zipWith6 (uncurry f) (Stream.indexed (stream as))
959 (stream bs)
960 (stream cs)
961 (stream ds)
962 (stream es)
963 (stream fs))
964
965 -- | /O(min(m,n))/ Zip two vectors
966 zip :: (Vector v a, Vector v b, Vector v (a,b)) => v a -> v b -> v (a, b)
967 {-# INLINE zip #-}
968 zip = zipWith (,)
969
970 zip3 :: (Vector v a, Vector v b, Vector v c, Vector v (a, b, c))
971 => v a -> v b -> v c -> v (a, b, c)
972 {-# INLINE zip3 #-}
973 zip3 = zipWith3 (,,)
974
975 zip4 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v (a, b, c, d))
976 => v a -> v b -> v c -> v d -> v (a, b, c, d)
977 {-# INLINE zip4 #-}
978 zip4 = zipWith4 (,,,)
979
980 zip5 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e,
981 Vector v (a, b, c, d, e))
982 => v a -> v b -> v c -> v d -> v e -> v (a, b, c, d, e)
983 {-# INLINE zip5 #-}
984 zip5 = zipWith5 (,,,,)
985
986 zip6 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e,
987 Vector v f, Vector v (a, b, c, d, e, f))
988 => v a -> v b -> v c -> v d -> v e -> v f -> v (a, b, c, d, e, f)
989 {-# INLINE zip6 #-}
990 zip6 = zipWith6 (,,,,,)
991
992 -- Monadic zipping
993 -- ---------------
994
995 -- | /O(min(m,n))/ Zip the two vectors with the monadic action and yield a
996 -- vector of results
997 zipWithM :: (Monad m, Vector v a, Vector v b, Vector v c)
998 => (a -> b -> m c) -> v a -> v b -> m (v c)
999 -- FIXME: specialise for ST and IO?
1000 {-# INLINE zipWithM #-}
1001 zipWithM f as bs = unstreamM $ Stream.zipWithM f (stream as) (stream bs)
1002
1003 -- | /O(min(m,n))/ Zip the two vectors with the monadic action and ignore the
1004 -- results
1005 zipWithM_ :: (Monad m, Vector v a, Vector v b)
1006 => (a -> b -> m c) -> v a -> v b -> m ()
1007 {-# INLINE zipWithM_ #-}
1008 zipWithM_ f as bs = Stream.zipWithM_ f (stream as) (stream bs)
1009
1010 -- Unzipping
1011 -- ---------
1012
1013 -- | /O(min(m,n))/ Unzip a vector of pairs.
1014 unzip :: (Vector v a, Vector v b, Vector v (a,b)) => v (a, b) -> (v a, v b)
1015 {-# INLINE unzip #-}
1016 unzip xs = (map fst xs, map snd xs)
1017
1018 unzip3 :: (Vector v a, Vector v b, Vector v c, Vector v (a, b, c))
1019 => v (a, b, c) -> (v a, v b, v c)
1020 {-# INLINE unzip3 #-}
1021 unzip3 xs = (map (\(a, b, c) -> a) xs,
1022 map (\(a, b, c) -> b) xs,
1023 map (\(a, b, c) -> c) xs)
1024
1025 unzip4 :: (Vector v a, Vector v b, Vector v c, Vector v d,
1026 Vector v (a, b, c, d))
1027 => v (a, b, c, d) -> (v a, v b, v c, v d)
1028 {-# INLINE unzip4 #-}
1029 unzip4 xs = (map (\(a, b, c, d) -> a) xs,
1030 map (\(a, b, c, d) -> b) xs,
1031 map (\(a, b, c, d) -> c) xs,
1032 map (\(a, b, c, d) -> d) xs)
1033
1034 unzip5 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e,
1035 Vector v (a, b, c, d, e))
1036 => v (a, b, c, d, e) -> (v a, v b, v c, v d, v e)
1037 {-# INLINE unzip5 #-}
1038 unzip5 xs = (map (\(a, b, c, d, e) -> a) xs,
1039 map (\(a, b, c, d, e) -> b) xs,
1040 map (\(a, b, c, d, e) -> c) xs,
1041 map (\(a, b, c, d, e) -> d) xs,
1042 map (\(a, b, c, d, e) -> e) xs)
1043
1044 unzip6 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e,
1045 Vector v f, Vector v (a, b, c, d, e, f))
1046 => v (a, b, c, d, e, f) -> (v a, v b, v c, v d, v e, v f)
1047 {-# INLINE unzip6 #-}
1048 unzip6 xs = (map (\(a, b, c, d, e, f) -> a) xs,
1049 map (\(a, b, c, d, e, f) -> b) xs,
1050 map (\(a, b, c, d, e, f) -> c) xs,
1051 map (\(a, b, c, d, e, f) -> d) xs,
1052 map (\(a, b, c, d, e, f) -> e) xs,
1053 map (\(a, b, c, d, e, f) -> f) xs)
1054
1055 -- Filtering
1056 -- ---------
1057
1058 -- | /O(n)/ Drop elements that do not satisfy the predicate
1059 filter :: Vector v a => (a -> Bool) -> v a -> v a
1060 {-# INLINE filter #-}
1061 filter f = unstream . inplace (MStream.filter f) . stream
1062
1063 -- | /O(n)/ Drop elements that do not satisfy the predicate which is applied to
1064 -- values and their indices
1065 ifilter :: Vector v a => (Int -> a -> Bool) -> v a -> v a
1066 {-# INLINE ifilter #-}
1067 ifilter f = unstream
1068 . inplace (MStream.map snd . MStream.filter (uncurry f)
1069 . MStream.indexed)
1070 . stream
1071
1072 -- | /O(n)/ Drop elements that do not satisfy the monadic predicate
1073 filterM :: (Monad m, Vector v a) => (a -> m Bool) -> v a -> m (v a)
1074 {-# INLINE filterM #-}
1075 filterM f = unstreamM . Stream.filterM f . stream
1076
1077 -- | /O(n)/ Yield the longest prefix of elements satisfying the predicate
1078 -- without copying.
1079 takeWhile :: Vector v a => (a -> Bool) -> v a -> v a
1080 {-# INLINE takeWhile #-}
1081 takeWhile f = unstream . Stream.takeWhile f . stream
1082
1083 -- | /O(n)/ Drop the longest prefix of elements that satisfy the predicate
1084 -- without copying.
1085 dropWhile :: Vector v a => (a -> Bool) -> v a -> v a
1086 {-# INLINE dropWhile #-}
1087 dropWhile f = unstream . Stream.dropWhile f . stream
1088
1089 -- Parititioning
1090 -- -------------
1091
1092 -- | /O(n)/ Split the vector in two parts, the first one containing those
1093 -- elements that satisfy the predicate and the second one those that don't. The
1094 -- relative order of the elements is preserved at the cost of a sometimes
1095 -- reduced performance compared to 'unstablePartition'.
1096 partition :: Vector v a => (a -> Bool) -> v a -> (v a, v a)
1097 {-# INLINE partition #-}
1098 partition f = partition_stream f . stream
1099
1100 -- FIXME: Make this inplace-fusible (look at how stable_partition is
1101 -- implemented in C++)
1102
1103 partition_stream :: Vector v a => (a -> Bool) -> Stream a -> (v a, v a)
1104 {-# INLINE_STREAM partition_stream #-}
1105 partition_stream f s = s `seq` runST (
1106 do
1107 (mv1,mv2) <- M.partitionStream f s
1108 v1 <- unsafeFreeze mv1
1109 v2 <- unsafeFreeze mv2
1110 return (v1,v2))
1111
1112 -- | /O(n)/ Split the vector in two parts, the first one containing those
1113 -- elements that satisfy the predicate and the second one those that don't.
1114 -- The order of the elements is not preserved but the operation is often
1115 -- faster than 'partition'.
1116 unstablePartition :: Vector v a => (a -> Bool) -> v a -> (v a, v a)
1117 {-# INLINE unstablePartition #-}
1118 unstablePartition f = unstablePartition_stream f . stream
1119
1120 unstablePartition_stream
1121 :: Vector v a => (a -> Bool) -> Stream a -> (v a, v a)
1122 {-# INLINE_STREAM unstablePartition_stream #-}
1123 unstablePartition_stream f s = s `seq` runST (
1124 do
1125 (mv1,mv2) <- M.unstablePartitionStream f s
1126 v1 <- unsafeFreeze mv1
1127 v2 <- unsafeFreeze mv2
1128 return (v1,v2))
1129
1130 unstablePartition_new :: Vector v a => (a -> Bool) -> New v a -> (v a, v a)
1131 {-# INLINE_STREAM unstablePartition_new #-}
1132 unstablePartition_new f (New.New p) = runST (
1133 do
1134 mv <- p
1135 i <- M.unstablePartition f mv
1136 v <- unsafeFreeze mv
1137 return (unsafeTake i v, unsafeDrop i v))
1138
1139 {-# RULES
1140
1141 "unstablePartition" forall f p.
1142 unstablePartition_stream f (stream (new p))
1143 = unstablePartition_new f p
1144
1145 #-}
1146
1147
1148 -- FIXME: make span and break fusible
1149
1150 -- | /O(n)/ Split the vector into the longest prefix of elements that satisfy
1151 -- the predicate and the rest without copying.
1152 span :: Vector v a => (a -> Bool) -> v a -> (v a, v a)
1153 {-# INLINE span #-}
1154 span f = break (not . f)
1155
1156 -- | /O(n)/ Split the vector into the longest prefix of elements that do not
1157 -- satisfy the predicate and the rest without copying.
1158 break :: Vector v a => (a -> Bool) -> v a -> (v a, v a)
1159 {-# INLINE break #-}
1160 break f xs = case findIndex f xs of
1161 Just i -> (unsafeSlice 0 i xs, unsafeSlice i (length xs - i) xs)
1162 Nothing -> (xs, empty)
1163
1164
1165 -- Searching
1166 -- ---------
1167
1168 infix 4 `elem`
1169 -- | /O(n)/ Check if the vector contains an element
1170 elem :: (Vector v a, Eq a) => a -> v a -> Bool
1171 {-# INLINE elem #-}
1172 elem x = Stream.elem x . stream
1173
1174 infix 4 `notElem`
1175 -- | /O(n)/ Check if the vector does not contain an element (inverse of 'elem')
1176 notElem :: (Vector v a, Eq a) => a -> v a -> Bool
1177 {-# INLINE notElem #-}
1178 notElem x = Stream.notElem x . stream
1179
1180 -- | /O(n)/ Yield 'Just' the first element matching the predicate or 'Nothing'
1181 -- if no such element exists.
1182 find :: Vector v a => (a -> Bool) -> v a -> Maybe a
1183 {-# INLINE find #-}
1184 find f = Stream.find f . stream
1185
1186 -- | /O(n)/ Yield 'Just' the index of the first element matching the predicate
1187 -- or 'Nothing' if no such element exists.
1188 findIndex :: Vector v a => (a -> Bool) -> v a -> Maybe Int
1189 {-# INLINE findIndex #-}
1190 findIndex f = Stream.findIndex f . stream
1191
1192 -- | /O(n)/ Yield the indices of elements satisfying the predicate in ascending
1193 -- order.
1194 findIndices :: (Vector v a, Vector v Int) => (a -> Bool) -> v a -> v Int
1195 {-# INLINE findIndices #-}
1196 findIndices f = unstream
1197 . inplace (MStream.map fst . MStream.filter (f . snd)
1198 . MStream.indexed)
1199 . stream
1200
1201 -- | /O(n)/ Yield 'Just' the index of the first occurence of the given element or
1202 -- 'Nothing' if the vector does not contain the element. This is a specialised
1203 -- version of 'findIndex'.
1204 elemIndex :: (Vector v a, Eq a) => a -> v a -> Maybe Int
1205 {-# INLINE elemIndex #-}
1206 elemIndex x = findIndex (x==)
1207
1208 -- | /O(n)/ Yield the indices of all occurences of the given element in
1209 -- ascending order. This is a specialised version of 'findIndices'.
1210 elemIndices :: (Vector v a, Vector v Int, Eq a) => a -> v a -> v Int
1211 {-# INLINE elemIndices #-}
1212 elemIndices x = findIndices (x==)
1213
1214 -- Folding
1215 -- -------
1216
1217 -- | /O(n)/ Left fold
1218 foldl :: Vector v b => (a -> b -> a) -> a -> v b -> a
1219 {-# INLINE foldl #-}
1220 foldl f z = Stream.foldl f z . stream
1221
1222 -- | /O(n)/ Left fold on non-empty vectors
1223 foldl1 :: Vector v a => (a -> a -> a) -> v a -> a
1224 {-# INLINE foldl1 #-}
1225 foldl1 f = Stream.foldl1 f . stream
1226
1227 -- | /O(n)/ Left fold with strict accumulator
1228 foldl' :: Vector v b => (a -> b -> a) -> a -> v b -> a
1229 {-# INLINE foldl' #-}
1230 foldl' f z = Stream.foldl' f z . stream
1231
1232 -- | /O(n)/ Left fold on non-empty vectors with strict accumulator
1233 foldl1' :: Vector v a => (a -> a -> a) -> v a -> a
1234 {-# INLINE foldl1' #-}
1235 foldl1' f = Stream.foldl1' f . stream
1236
1237 -- | /O(n)/ Right fold
1238 foldr :: Vector v a => (a -> b -> b) -> b -> v a -> b
1239 {-# INLINE foldr #-}
1240 foldr f z = Stream.foldr f z . stream
1241
1242 -- | /O(n)/ Right fold on non-empty vectors
1243 foldr1 :: Vector v a => (a -> a -> a) -> v a -> a
1244 {-# INLINE foldr1 #-}
1245 foldr1 f = Stream.foldr1 f . stream
1246
1247 -- | /O(n)/ Right fold with a strict accumulator
1248 foldr' :: Vector v a => (a -> b -> b) -> b -> v a -> b
1249 {-# INLINE foldr' #-}
1250 foldr' f z = Stream.foldl' (flip f) z . streamR
1251
1252 -- | /O(n)/ Right fold on non-empty vectors with strict accumulator
1253 foldr1' :: Vector v a => (a -> a -> a) -> v a -> a
1254 {-# INLINE foldr1' #-}
1255 foldr1' f = Stream.foldl1' (flip f) . streamR
1256
1257 -- | /O(n)/ Left fold (function applied to each element and its index)
1258 ifoldl :: Vector v b => (a -> Int -> b -> a) -> a -> v b -> a
1259 {-# INLINE ifoldl #-}
1260 ifoldl f z = Stream.foldl (uncurry . f) z . Stream.indexed . stream
1261
1262 -- | /O(n)/ Left fold with strict accumulator (function applied to each element
1263 -- and its index)
1264 ifoldl' :: Vector v b => (a -> Int -> b -> a) -> a -> v b -> a
1265 {-# INLINE ifoldl' #-}
1266 ifoldl' f z = Stream.foldl' (uncurry . f) z . Stream.indexed . stream
1267
1268 -- | /O(n)/ Right fold (function applied to each element and its index)
1269 ifoldr :: Vector v a => (Int -> a -> b -> b) -> b -> v a -> b
1270 {-# INLINE ifoldr #-}
1271 ifoldr f z = Stream.foldr (uncurry f) z . Stream.indexed . stream
1272
1273 -- | /O(n)/ Right fold with strict accumulator (function applied to each
1274 -- element and its index)
1275 ifoldr' :: Vector v a => (Int -> a -> b -> b) -> b -> v a -> b
1276 {-# INLINE ifoldr' #-}
1277 ifoldr' f z xs = Stream.foldl' (flip (uncurry f)) z
1278 $ Stream.indexedR (length xs) $ streamR xs
1279
1280 -- Specialised folds
1281 -- -----------------
1282
1283 -- | /O(n)/ Check if all elements satisfy the predicate.
1284 all :: Vector v a => (a -> Bool) -> v a -> Bool
1285 {-# INLINE all #-}
1286 all f = Stream.and . Stream.map f . stream
1287
1288 -- | /O(n)/ Check if any element satisfies the predicate.
1289 any :: Vector v a => (a -> Bool) -> v a -> Bool
1290 {-# INLINE any #-}
1291 any f = Stream.or . Stream.map f . stream
1292
1293 -- | /O(n)/ Check if all elements are 'True'
1294 and :: Vector v Bool => v Bool -> Bool
1295 {-# INLINE and #-}
1296 and = Stream.and . stream
1297
1298 -- | /O(n)/ Check if any element is 'True'
1299 or :: Vector v Bool => v Bool -> Bool
1300 {-# INLINE or #-}
1301 or = Stream.or . stream
1302
1303 -- | /O(n)/ Compute the sum of the elements
1304 sum :: (Vector v a, Num a) => v a -> a
1305 {-# INLINE sum #-}
1306 sum = Stream.foldl' (+) 0 . stream
1307
1308 -- | /O(n)/ Compute the produce of the elements
1309 product :: (Vector v a, Num a) => v a -> a
1310 {-# INLINE product #-}
1311 product = Stream.foldl' (*) 1 . stream
1312
1313 -- | /O(n)/ Yield the maximum element of the vector. The vector may not be
1314 -- empty.
1315 maximum :: (Vector v a, Ord a) => v a -> a
1316 {-# INLINE maximum #-}
1317 maximum = Stream.foldl1' max . stream
1318
1319 -- | /O(n)/ Yield the maximum element of the vector according to the given
1320 -- comparison function. The vector may not be empty.
1321 maximumBy :: Vector v a => (a -> a -> Ordering) -> v a -> a
1322 {-# INLINE maximumBy #-}
1323 maximumBy cmp = Stream.foldl1' maxBy . stream
1324 where
1325 {-# INLINE maxBy #-}
1326 maxBy x y = case cmp x y of
1327 LT -> y
1328 _ -> x
1329
1330 -- | /O(n)/ Yield the minimum element of the vector. The vector may not be
1331 -- empty.
1332 minimum :: (Vector v a, Ord a) => v a -> a
1333 {-# INLINE minimum #-}
1334 minimum = Stream.foldl1' min . stream
1335
1336 -- | /O(n)/ Yield the minimum element of the vector according to the given
1337 -- comparison function. The vector may not be empty.
1338 minimumBy :: Vector v a => (a -> a -> Ordering) -> v a -> a
1339 {-# INLINE minimumBy #-}
1340 minimumBy cmp = Stream.foldl1' minBy . stream
1341 where
1342 {-# INLINE minBy #-}
1343 minBy x y = case cmp x y of
1344 GT -> y
1345 _ -> x
1346
1347 -- | /O(n)/ Yield the index of the maximum element of the vector. The vector
1348 -- may not be empty.
1349 maxIndex :: (Vector v a, Ord a) => v a -> Int
1350 {-# INLINE maxIndex #-}
1351 maxIndex = maxIndexBy compare
1352
1353 -- | /O(n)/ Yield the index of the maximum element of the vector according to
1354 -- the given comparison function. The vector may not be empty.
1355 maxIndexBy :: Vector v a => (a -> a -> Ordering) -> v a -> Int
1356 {-# INLINE maxIndexBy #-}
1357 maxIndexBy cmp = fst . Stream.foldl1' imax . Stream.indexed . stream
1358 where
1359 imax (i,x) (j,y) = i `seq` j `seq`
1360 case cmp x y of
1361 LT -> (j,y)
1362 _ -> (i,x)
1363
1364 -- | /O(n)/ Yield the index of the minimum element of the vector. The vector
1365 -- may not be empty.
1366 minIndex :: (Vector v a, Ord a) => v a -> Int
1367 {-# INLINE minIndex #-}
1368 minIndex = minIndexBy compare
1369
1370 -- | /O(n)/ Yield the index of the minimum element of the vector according to
1371 -- the given comparison function. The vector may not be empty.
1372 minIndexBy :: Vector v a => (a -> a -> Ordering) -> v a -> Int
1373 {-# INLINE minIndexBy #-}
1374 minIndexBy cmp = fst . Stream.foldl1' imin . Stream.indexed . stream
1375 where
1376 imin (i,x) (j,y) = i `seq` j `seq`
1377 case cmp x y of
1378 GT -> (j,y)
1379 _ -> (i,x)
1380
1381 -- Monadic folds
1382 -- -------------
1383
1384 -- | /O(n)/ Monadic fold
1385 foldM :: (Monad m, Vector v b) => (a -> b -> m a) -> a -> v b -> m a
1386 {-# INLINE foldM #-}
1387 foldM m z = Stream.foldM m z . stream
1388
1389 -- | /O(n)/ Monadic fold over non-empty vectors
1390 fold1M :: (Monad m, Vector v a) => (a -> a -> m a) -> v a -> m a
1391 {-# INLINE fold1M #-}
1392 fold1M m = Stream.fold1M m . stream
1393
1394 -- | /O(n)/ Monadic fold with strict accumulator
1395 foldM' :: (Monad m, Vector v b) => (a -> b -> m a) -> a -> v b -> m a
1396 {-# INLINE foldM' #-}
1397 foldM' m z = Stream.foldM' m z . stream
1398
1399 -- | /O(n)/ Monad fold over non-empty vectors with strict accumulator
1400 fold1M' :: (Monad m, Vector v a) => (a -> a -> m a) -> v a -> m a
1401 {-# INLINE fold1M' #-}
1402 fold1M' m = Stream.fold1M' m . stream
1403
1404 -- Prefix sums (scans)
1405 -- -------------------
1406
1407 -- | /O(n)/ Prescan
1408 --
1409 -- @
1410 -- prescanl f z = 'init' . 'scanl' f z
1411 -- @
1412 --
1413 -- Example: @prescanl (+) 0 \<1,2,3,4\> = \<0,1,3,6\>@
1414 --
1415 prescanl :: (Vector v a, Vector v b) => (a -> b -> a) -> a -> v b -> v a
1416 {-# INLINE prescanl #-}
1417 prescanl f z = unstream . inplace (MStream.prescanl f z) . stream
1418
1419 -- | /O(n)/ Prescan with strict accumulator
1420 prescanl' :: (Vector v a, Vector v b) => (a -> b -> a) -> a -> v b -> v a
1421 {-# INLINE prescanl' #-}
1422 prescanl' f z = unstream . inplace (MStream.prescanl' f z) . stream
1423
1424 -- | /O(n)/ Scan
1425 --
1426 -- @
1427 -- postscanl f z = 'tail' . 'scanl' f z
1428 -- @
1429 --
1430 -- Example: @postscanl (+) 0 \<1,2,3,4\> = \<1,3,6,10\>@
1431 --
1432 postscanl :: (Vector v a, Vector v b) => (a -> b -> a) -> a -> v b -> v a
1433 {-# INLINE postscanl #-}
1434 postscanl f z = unstream . inplace (MStream.postscanl f z) . stream
1435
1436 -- | /O(n)/ Scan with strict accumulator
1437 postscanl' :: (Vector v a, Vector v b) => (a -> b -> a) -> a -> v b -> v a
1438 {-# INLINE postscanl' #-}
1439 postscanl' f z = unstream . inplace (MStream.postscanl' f z) . stream
1440
1441 -- | /O(n)/ Haskell-style scan
1442 --
1443 -- > scanl f z <x1,...,xn> = <y1,...,y(n+1)>
1444 -- > where y1 = z
1445 -- > yi = f y(i-1) x(i-1)
1446 --
1447 -- Example: @scanl (+) 0 \<1,2,3,4\> = \<0,1,3,6,10\>@
1448 --
1449 scanl :: (Vector v a, Vector v b) => (a -> b -> a) -> a -> v b -> v a
1450 {-# INLINE scanl #-}
1451 scanl f z = unstream . Stream.scanl f z . stream
1452
1453 -- | /O(n)/ Haskell-style scan with strict accumulator
1454 scanl' :: (Vector v a, Vector v b) => (a -> b -> a) -> a -> v b -> v a
1455 {-# INLINE scanl' #-}
1456 scanl' f z = unstream . Stream.scanl' f z . stream
1457
1458 -- | /O(n)/ Scan over a non-empty vector
1459 --
1460 -- > scanl f <x1,...,xn> = <y1,...,yn>
1461 -- > where y1 = x1
1462 -- > yi = f y(i-1) xi
1463 --
1464 scanl1 :: Vector v a => (a -> a -> a) -> v a -> v a
1465 {-# INLINE scanl1 #-}
1466 scanl1 f = unstream . inplace (MStream.scanl1 f) . stream
1467
1468 -- | /O(n)/ Scan over a non-empty vector with a strict accumulator
1469 scanl1' :: Vector v a => (a -> a -> a) -> v a -> v a
1470 {-# INLINE scanl1' #-}
1471 scanl1' f = unstream . inplace (MStream.scanl1' f) . stream
1472
1473 -- | /O(n)/ Right-to-left prescan
1474 --
1475 -- @
1476 -- prescanr f z = 'reverse' . 'prescanl' (flip f) z . 'reverse'
1477 -- @
1478 --
1479 prescanr :: (Vector v a, Vector v b) => (a -> b -> b) -> b -> v a -> v b
1480 {-# INLINE prescanr #-}
1481 prescanr f z = unstreamR . inplace (MStream.prescanl (flip f) z) . streamR
1482
1483 -- | /O(n)/ Right-to-left prescan with strict accumulator
1484 prescanr' :: (Vector v a, Vector v b) => (a -> b -> b) -> b -> v a -> v b
1485 {-# INLINE prescanr' #-}
1486 prescanr' f z = unstreamR . inplace (MStream.prescanl' (flip f) z) . streamR
1487
1488 -- | /O(n)/ Right-to-left scan
1489 postscanr :: (Vector v a, Vector v b) => (a -> b -> b) -> b -> v a -> v b
1490 {-# INLINE postscanr #-}
1491 postscanr f z = unstreamR . inplace (MStream.postscanl (flip f) z) . streamR
1492
1493 -- | /O(n)/ Right-to-left scan with strict accumulator
1494 postscanr' :: (Vector v a, Vector v b) => (a -> b -> b) -> b -> v a -> v b
1495 {-# INLINE postscanr' #-}
1496 postscanr' f z = unstreamR . inplace (MStream.postscanl' (flip f) z) . streamR
1497
1498 -- | /O(n)/ Right-to-left Haskell-style scan
1499 scanr :: (Vector v a, Vector v b) => (a -> b -> b) -> b -> v a -> v b
1500 {-# INLINE scanr #-}
1501 scanr f z = unstreamR . Stream.scanl (flip f) z . streamR
1502
1503 -- | /O(n)/ Right-to-left Haskell-style scan with strict accumulator
1504 scanr' :: (Vector v a, Vector v b) => (a -> b -> b) -> b -> v a -> v b
1505 {-# INLINE scanr' #-}
1506 scanr' f z = unstreamR . Stream.scanl' (flip f) z . streamR
1507
1508 -- | /O(n)/ Right-to-left scan over a non-empty vector
1509 scanr1 :: Vector v a => (a -> a -> a) -> v a -> v a
1510 {-# INLINE scanr1 #-}
1511 scanr1 f = unstreamR . inplace (MStream.scanl1 (flip f)) . streamR
1512
1513 -- | /O(n)/ Right-to-left scan over a non-empty vector with a strict
1514 -- accumulator
1515 scanr1' :: Vector v a => (a -> a -> a) -> v a -> v a
1516 {-# INLINE scanr1' #-}
1517 scanr1' f = unstreamR . inplace (MStream.scanl1' (flip f)) . streamR
1518
1519 -- Conversions - Lists
1520 -- ------------------------
1521
1522 -- | /O(n)/ Convert a vector to a list
1523 toList :: Vector v a => v a -> [a]
1524 {-# INLINE toList #-}
1525 toList = Stream.toList . stream
1526
1527 -- | /O(n)/ Convert a list to a vector
1528 fromList :: Vector v a => [a] -> v a
1529 {-# INLINE fromList #-}
1530 fromList = unstream . Stream.fromList
1531
1532 -- | /O(n)/ Convert the first @n@ elements of a list to a vector
1533 --
1534 -- @
1535 -- fromListN n xs = 'fromList' ('take' n xs)
1536 -- @
1537 fromListN :: Vector v a => Int -> [a] -> v a
1538 {-# INLINE fromListN #-}
1539 fromListN n = unstream . Stream.fromListN n
1540
1541 -- Conversions - Mutable vectors
1542 -- -----------------------------
1543
1544 -- | /O(n)/ Yield a mutable copy of the immutable vector.
1545 thaw :: (PrimMonad m, Vector v a) => v a -> m (Mutable v (PrimState m) a)
1546 {-# INLINE_STREAM thaw #-}
1547 thaw v = do
1548 mv <- M.unsafeNew (length v)
1549 unsafeCopy mv v
1550 return mv
1551
1552 -- | /O(n)/ Yield a mutable vector containing copies of each vector in the
1553 -- list.
1554 thawMany :: (PrimMonad m, Vector v a) => [v a] -> m (Mutable v (PrimState m) a)
1555 {-# INLINE_STREAM thawMany #-}
1556 -- FIXME: add rule for (stream (new (New.create (thawMany vs))))
1557 -- NOTE: We don't try to consume the list lazily as this wouldn't significantly
1558 -- change the space requirements anyway.
1559 thawMany vs = do
1560 mv <- M.new n
1561 thaw_loop mv vs
1562 return mv
1563 where
1564 n = List.foldl' (\k v -> k + length v) 0 vs
1565
1566 thaw_loop mv [] = mv `seq` return ()
1567 thaw_loop mv (v:vs)
1568 = do
1569 let n = length v
1570 unsafeCopy (M.unsafeTake n mv) v
1571 thaw_loop (M.unsafeDrop n mv) vs
1572
1573 -- | /O(n)/ Copy an immutable vector into a mutable one. The two vectors must
1574 -- have the same length.
1575 copy
1576 :: (PrimMonad m, Vector v a) => Mutable v (PrimState m) a -> v a -> m ()
1577 {-# INLINE copy #-}
1578 copy dst src = BOUNDS_CHECK(check) "copy" "length mismatch"
1579 (M.length dst == length src)
1580 $ unsafeCopy dst src
1581
1582 -- | /O(n)/ Copy an immutable vector into a mutable one. The two vectors must
1583 -- have the same length. This is not checked.
1584 unsafeCopy
1585 :: (PrimMonad m, Vector v a) => Mutable v (PrimState m) a -> v a -> m ()
1586 {-# INLINE unsafeCopy #-}
1587 unsafeCopy dst src = UNSAFE_CHECK(check) "unsafeCopy" "length mismatch"
1588 (M.length dst == length src)
1589 $ (dst `seq` src `seq` basicUnsafeCopy dst src)
1590
1591 -- Conversions to/from Streams
1592 -- ---------------------------
1593
1594 -- | /O(1)/ Convert a vector to a 'Stream'
1595 stream :: Vector v a => v a -> Stream a
1596 {-# INLINE_STREAM stream #-}
1597 stream v = v `seq` (Stream.unfoldr get 0 `Stream.sized` Exact n)
1598 where
1599 n = length v
1600
1601 -- NOTE: the False case comes first in Core so making it the recursive one
1602 -- makes the code easier to read
1603 {-# INLINE get #-}
1604 get i | i >= n = Nothing
1605 | otherwise = case basicUnsafeIndexM v i of Box x -> Just (x, i+1)
1606
1607 -- | /O(n)/ Construct a vector from a 'Stream'
1608 unstream :: Vector v a => Stream a -> v a
1609 {-# INLINE unstream #-}
1610 unstream s = new (New.unstream s)
1611
1612 {-# RULES
1613
1614 "stream/unstream [Vector]" forall s.
1615 stream (new (New.unstream s)) = s
1616
1617 "New.unstream/stream [Vector]" forall v.
1618 New.unstream (stream v) = clone v
1619
1620 "clone/new [Vector]" forall p.
1621 clone (new p) = p
1622
1623 "inplace [Vector]"
1624 forall (f :: forall m. Monad m => MStream m a -> MStream m a) m.
1625 New.unstream (inplace f (stream (new m))) = New.transform f m
1626
1627 "uninplace [Vector]"
1628 forall (f :: forall m. Monad m => MStream m a -> MStream m a) m.
1629 stream (new (New.transform f m)) = inplace f (stream (new m))
1630
1631 #-}
1632
1633 -- | /O(1)/ Convert a vector to a 'Stream', proceeding from right to left
1634 streamR :: Vector v a => v a -> Stream a
1635 {-# INLINE_STREAM streamR #-}
1636 streamR v = v `seq` (Stream.unfoldr get n `Stream.sized` Exact n)
1637 where
1638 n = length v
1639
1640 {-# INLINE get #-}
1641 get 0 = Nothing
1642 get i = let i' = i-1
1643 in
1644 case basicUnsafeIndexM v i' of Box x -> Just (x, i')
1645
1646 -- | /O(n)/ Construct a vector from a 'Stream', proceeding from right to left
1647 unstreamR :: Vector v a => Stream a -> v a
1648 {-# INLINE unstreamR #-}
1649 unstreamR s = new (New.unstreamR s)
1650
1651 {-# RULES
1652
1653 "streamR/unstreamR [Vector]" forall s.
1654 streamR (new (New.unstreamR s)) = s
1655
1656 "New.unstreamR/streamR/new [Vector]" forall p.
1657 New.unstreamR (streamR (new p)) = p
1658
1659 "inplace right [Vector]"
1660 forall (f :: forall m. Monad m => MStream m a -> MStream m a) m.
1661 New.unstreamR (inplace f (streamR (new m))) = New.transformR f m
1662
1663 "uninplace right [Vector]"
1664 forall (f :: forall m. Monad m => MStream m a -> MStream m a) m.
1665 streamR (new (New.transformR f m)) = inplace f (streamR (new m))
1666
1667 #-}
1668
1669 unstreamM :: (Vector v a, Monad m) => MStream m a -> m (v a)
1670 {-# INLINE_STREAM unstreamM #-}
1671 unstreamM s = do
1672 xs <- MStream.toList s
1673 return $ unstream $ Stream.unsafeFromList (MStream.size s) xs
1674
1675 -- Recycling support
1676 -- -----------------
1677
1678 -- | Construct a vector from a monadic initialiser.
1679 new :: Vector v a => New v a -> v a
1680 {-# INLINE_STREAM new #-}
1681 new m = m `seq` runST (unsafeFreeze =<< New.run m)
1682
1683 -- | Convert a vector to an initialiser which, when run, produces a copy of
1684 -- the vector.
1685 clone :: Vector v a => v a -> New v a
1686 {-# INLINE_STREAM clone #-}
1687 clone v = v `seq` New.create (
1688 do
1689 mv <- M.new (length v)
1690 unsafeCopy mv v
1691 return mv)
1692
1693 -- Comparisons
1694 -- -----------
1695
1696 -- | /O(n)/ Check if two vectors are equal. All 'Vector' instances are also
1697 -- instances of 'Eq' and it is usually more appropriate to use those. This
1698 -- function is primarily intended for implementing 'Eq' instances for new
1699 -- vector types.
1700 eq :: (Vector v a, Eq a) => v a -> v a -> Bool
1701 {-# INLINE eq #-}
1702 xs `eq` ys = stream xs == stream ys
1703
1704 -- | /O(n)/ Compare two vectors lexicographically. All 'Vector' instances are
1705 -- also instances of 'Ord' and it is usually more appropriate to use those. This
1706 -- function is primarily intended for implementing 'Ord' instances for new
1707 -- vector types.
1708 cmp :: (Vector v a, Ord a) => v a -> v a -> Ordering
1709 {-# INLINE cmp #-}
1710 cmp xs ys = compare (stream xs) (stream ys)
1711
1712 -- Data and Typeable
1713 -- -----------------
1714
1715 -- | Generic definion of 'Data.Data.gfoldl' that views a 'Vector' as a
1716 -- list.
1717 gfoldl :: (Vector v a, Data a)
1718 => (forall d b. Data d => c (d -> b) -> d -> c b)
1719 -> (forall g. g -> c g)
1720 -> v a
1721 -> c (v a)
1722 {-# INLINE gfoldl #-}
1723 gfoldl f z v = z fromList `f` toList v
1724
1725 mkType :: String -> DataType
1726 {-# INLINE mkType #-}
1727 mkType = mkNorepType
1728
1729 dataCast :: (Vector v a, Data a, Typeable1 v, Typeable1 t)
1730 => (forall d. Data d => c (t d)) -> Maybe (c (v a))
1731 {-# INLINE dataCast #-}
1732 dataCast f = gcast1 f
1733