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