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