Move code
[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 -- * Length information
20 length, null,
21
22 -- * Construction
23 empty, singleton, cons, snoc, replicate, generate, (++), force,
24
25 -- * Accessing individual elements
26 (!), head, last, indexM, headM, lastM,
27 unsafeIndex, unsafeHead, unsafeLast,
28 unsafeIndexM, unsafeHeadM, unsafeLastM,
29
30 -- * Subvectors
31 slice, init, tail, take, drop,
32 unsafeSlice, unsafeInit, unsafeTail, unsafeTake, unsafeDrop,
33
34 -- * Permutations
35 accum, accumulate, accumulate_,
36 (//), update, update_,
37 backpermute, reverse,
38 unsafeAccum, unsafeAccumulate, unsafeAccumulate_,
39 unsafeUpd, unsafeUpdate, unsafeUpdate_,
40 unsafeBackpermute,
41
42 -- * Mapping
43 map, imap, concatMap,
44
45 -- * Zipping and unzipping
46 zipWith, zipWith3, zipWith4, zipWith5, zipWith6,
47 izipWith, izipWith3, izipWith4, izipWith5, izipWith6,
48 zip, zip3, zip4, zip5, zip6,
49 unzip, unzip3, unzip4, unzip5, unzip6,
50
51 -- * Comparisons
52 eq, cmp,
53
54 -- * Filtering
55 filter, ifilter, takeWhile, dropWhile,
56 partition, unstablePartition, span, break,
57
58 -- * Searching
59 elem, notElem, find, findIndex, findIndices, elemIndex, elemIndices,
60
61 -- * Folding
62 foldl, foldl1, foldl', foldl1', foldr, foldr1, foldr', foldr1',
63 ifoldl, ifoldl', ifoldr, ifoldr',
64
65 -- * Specialised folds
66 all, any, and, or,
67 sum, product,
68 maximum, maximumBy, minimum, minimumBy,
69 minIndex, minIndexBy, maxIndex, maxIndexBy,
70
71 -- * Unfolding
72 unfoldr, unfoldrN,
73
74 -- * Scans
75 prescanl, prescanl',
76 postscanl, postscanl',
77 scanl, scanl', scanl1, scanl1',
78 prescanr, prescanr',
79 postscanr, postscanr',
80 scanr, scanr', scanr1, scanr1',
81
82 -- * Enumeration
83 enumFromN, enumFromStepN, enumFromTo, enumFromThenTo,
84
85 -- * Conversion to/from lists
86 toList, fromList, fromListN,
87
88 -- * Destructive operations
89 create, modify, copy, unsafeCopy,
90
91 -- * Conversion to/from Streams
92 stream, unstream, streamR, unstreamR,
93
94 -- * Recycling support
95 new, clone,
96
97 -- * Utilities for defining Data instances
98 gfoldl, dataCast, mkType
99 ) where
100
101 import Data.Vector.Generic.Base
102
103 import Data.Vector.Generic.Mutable ( MVector )
104 import qualified Data.Vector.Generic.Mutable as M
105
106 import qualified Data.Vector.Generic.New as New
107 import Data.Vector.Generic.New ( New )
108
109 import qualified Data.Vector.Fusion.Stream as Stream
110 import Data.Vector.Fusion.Stream ( Stream, MStream, inplace )
111 import qualified Data.Vector.Fusion.Stream.Monadic as MStream
112 import Data.Vector.Fusion.Stream.Size
113 import Data.Vector.Fusion.Util
114
115 import Control.Monad.ST ( ST, runST )
116 import Control.Monad.Primitive
117 import Prelude hiding ( length, null,
118 replicate, (++),
119 head, last,
120 init, tail, take, drop, reverse,
121 map, concatMap,
122 zipWith, zipWith3, zip, zip3, unzip, unzip3,
123 filter, takeWhile, dropWhile, span, break,
124 elem, notElem,
125 foldl, foldl1, foldr, foldr1,
126 all, any, and, or, sum, product, maximum, minimum,
127 scanl, scanl1, scanr, scanr1,
128 enumFromTo, enumFromThenTo )
129
130 import Data.Typeable ( Typeable1, gcast1 )
131 import Data.Data ( Data, DataType, mkNorepType )
132
133 #include "vector.h"
134
135 -- Fusion
136 -- ------
137
138 -- | Construct a pure vector from a monadic initialiser
139 new :: Vector v a => New v a -> v a
140 {-# INLINE_STREAM new #-}
141 new m = m `seq` runST (unsafeFreeze =<< New.run m)
142
143 clone :: Vector v a => v a -> New v a
144 {-# INLINE_STREAM clone #-}
145 clone v = v `seq` New.create (
146 do
147 mv <- M.new (length v)
148 unsafeCopy mv v
149 return mv)
150
151 -- | Convert a vector to a 'Stream'
152 stream :: Vector v a => v a -> Stream a
153 {-# INLINE_STREAM stream #-}
154 stream v = v `seq` (Stream.unfoldr get 0 `Stream.sized` Exact n)
155 where
156 n = length v
157
158 -- NOTE: the False case comes first in Core so making it the recursive one
159 -- makes the code easier to read
160 {-# INLINE get #-}
161 get i | i >= n = Nothing
162 | otherwise = case basicUnsafeIndexM v i of Box x -> Just (x, i+1)
163
164 -- | Create a vector from a 'Stream'
165 unstream :: Vector v a => Stream a -> v a
166 {-# INLINE unstream #-}
167 unstream s = new (New.unstream s)
168
169 {-# RULES
170
171 "stream/unstream [Vector]" forall s.
172 stream (new (New.unstream s)) = s
173
174 "New.unstream/stream [Vector]" forall v.
175 New.unstream (stream v) = clone v
176
177 "clone/new [Vector]" forall p.
178 clone (new p) = p
179
180 #-}
181
182 {-# RULES
183
184 "inplace [Vector]"
185 forall (f :: forall m. Monad m => MStream m a -> MStream m a) m.
186 New.unstream (inplace f (stream (new m))) = New.transform f m
187
188 "uninplace [Vector]"
189 forall (f :: forall m. Monad m => MStream m a -> MStream m a) m.
190 stream (new (New.transform f m)) = inplace f (stream (new m))
191
192 #-}
193
194 -- | Convert a vector to a 'Stream'
195 streamR :: Vector v a => v a -> Stream a
196 {-# INLINE_STREAM streamR #-}
197 streamR v = v `seq` (Stream.unfoldr get n `Stream.sized` Exact n)
198 where
199 n = length v
200
201 {-# INLINE get #-}
202 get 0 = Nothing
203 get i = let i' = i-1
204 in
205 case basicUnsafeIndexM v i' of Box x -> Just (x, i')
206
207 -- | Create a vector from a 'Stream'
208 unstreamR :: Vector v a => Stream a -> v a
209 {-# INLINE unstreamR #-}
210 unstreamR s = new (New.unstreamR s)
211
212 {-# RULES
213
214 "streamR/unstreamR [Vector]" forall s.
215 streamR (new (New.unstreamR s)) = s
216
217 "New.unstreamR/streamR/new [Vector]" forall p.
218 New.unstreamR (streamR (new p)) = p
219
220 #-}
221
222 {-# RULES
223
224 "inplace [Vector]"
225 forall (f :: forall m. Monad m => MStream m a -> MStream m a) m.
226 New.unstreamR (inplace f (streamR (new m))) = New.transformR f m
227
228 "uninplace [Vector]"
229 forall (f :: forall m. Monad m => MStream m a -> MStream m a) m.
230 streamR (new (New.transformR f m)) = inplace f (streamR (new m))
231
232 #-}
233
234 -- Length
235 -- ------
236
237 length :: Vector v a => v a -> Int
238 {-# INLINE_STREAM length #-}
239 length v = basicLength v
240
241 {-# RULES
242
243 "length/unstream [Vector]" forall s.
244 length (new (New.unstream s)) = Stream.length s
245
246 #-}
247
248 null :: Vector v a => v a -> Bool
249 {-# INLINE_STREAM null #-}
250 null v = basicLength v == 0
251
252 {-# RULES
253
254 "null/unstream [Vector]" forall s.
255 null (new (New.unstream s)) = Stream.null s
256
257 #-}
258
259 -- Construction
260 -- ------------
261
262 -- | Empty vector
263 empty :: Vector v a => v a
264 {-# INLINE empty #-}
265 empty = unstream Stream.empty
266
267 -- | Vector with exaclty one element
268 singleton :: forall v a. Vector v a => a -> v a
269 {-# INLINE singleton #-}
270 singleton x = elemseq (undefined :: v a) x
271 $ unstream (Stream.singleton x)
272
273 -- | Vector of the given length with the given value in each position
274 replicate :: forall v a. Vector v a => Int -> a -> v a
275 {-# INLINE replicate #-}
276 replicate n x = elemseq (undefined :: v a) x
277 $ unstream
278 $ Stream.replicate n x
279
280 -- | Generate a vector of the given length by applying the function to each
281 -- index
282 generate :: Vector v a => Int -> (Int -> a) -> v a
283 {-# INLINE generate #-}
284 generate n f = unstream (Stream.generate n f)
285
286 -- | Prepend an element
287 cons :: forall v a. Vector v a => a -> v a -> v a
288 {-# INLINE cons #-}
289 cons x v = elemseq (undefined :: v a) x
290 $ unstream
291 $ Stream.cons x
292 $ stream v
293
294 -- | Append an element
295 snoc :: forall v a. Vector v a => v a -> a -> v a
296 {-# INLINE snoc #-}
297 snoc v x = elemseq (undefined :: v a) x
298 $ unstream
299 $ Stream.snoc (stream v) x
300
301 infixr 5 ++
302 -- | Concatenate two vectors
303 (++) :: Vector v a => v a -> v a -> v a
304 {-# INLINE (++) #-}
305 v ++ w = unstream (stream v Stream.++ stream w)
306
307 -- | Create a copy of a vector. Useful when dealing with slices.
308 force :: Vector v a => v a -> v a
309 {-# INLINE_STREAM force #-}
310 force v = new (clone v)
311
312 -- Accessing individual elements
313 -- -----------------------------
314
315 -- | Indexing
316 (!) :: Vector v a => v a -> Int -> a
317 {-# INLINE_STREAM (!) #-}
318 v ! i = BOUNDS_CHECK(checkIndex) "(!)" i (length v)
319 $ unId (basicUnsafeIndexM v i)
320
321 -- | First element
322 head :: Vector v a => v a -> a
323 {-# INLINE_STREAM head #-}
324 head v = v ! 0
325
326 -- | Last element
327 last :: Vector v a => v a -> a
328 {-# INLINE_STREAM last #-}
329 last v = v ! (length v - 1)
330
331 -- | Unsafe indexing without bounds checking
332 unsafeIndex :: Vector v a => v a -> Int -> a
333 {-# INLINE_STREAM unsafeIndex #-}
334 unsafeIndex v i = UNSAFE_CHECK(checkIndex) "unsafeIndex" i (length v)
335 $ unId (basicUnsafeIndexM v i)
336
337 -- | Yield the first element of a vector without checking if the vector is
338 -- empty
339 unsafeHead :: Vector v a => v a -> a
340 {-# INLINE_STREAM unsafeHead #-}
341 unsafeHead v = unsafeIndex v 0
342
343 -- | Yield the last element of a vector without checking if the vector is
344 -- empty
345 unsafeLast :: Vector v a => v a -> a
346 {-# INLINE_STREAM unsafeLast #-}
347 unsafeLast v = unsafeIndex v (length v - 1)
348
349 {-# RULES
350
351 "(!)/unstream [Vector]" forall i s.
352 new (New.unstream s) ! i = s Stream.!! i
353
354 "head/unstream [Vector]" forall s.
355 head (new (New.unstream s)) = Stream.head s
356
357 "last/unstream [Vector]" forall s.
358 last (new (New.unstream s)) = Stream.last s
359
360 "unsafeIndex/unstream [Vector]" forall i s.
361 unsafeIndex (new (New.unstream s)) i = s Stream.!! i
362
363 "unsafeHead/unstream [Vector]" forall s.
364 unsafeHead (new (New.unstream s)) = Stream.head s
365
366 "unsafeLast/unstream [Vector]" forall s.
367 unsafeLast (new (New.unstream s)) = Stream.last s
368
369 #-}
370
371 -- | Monadic indexing which can be strict in the vector while remaining lazy in
372 -- the element.
373 indexM :: (Vector v a, Monad m) => v a -> Int -> m a
374 {-# INLINE_STREAM indexM #-}
375 indexM v i = BOUNDS_CHECK(checkIndex) "indexM" i (length v)
376 $ basicUnsafeIndexM v i
377
378 headM :: (Vector v a, Monad m) => v a -> m a
379 {-# INLINE_STREAM headM #-}
380 headM v = indexM v 0
381
382 lastM :: (Vector v a, Monad m) => v a -> m a
383 {-# INLINE_STREAM lastM #-}
384 lastM v = indexM v (length v - 1)
385
386 -- | Unsafe monadic indexing without bounds checks
387 unsafeIndexM :: (Vector v a, Monad m) => v a -> Int -> m a
388 {-# INLINE_STREAM unsafeIndexM #-}
389 unsafeIndexM v i = UNSAFE_CHECK(checkIndex) "unsafeIndexM" i (length v)
390 $ basicUnsafeIndexM v i
391
392 unsafeHeadM :: (Vector v a, Monad m) => v a -> m a
393 {-# INLINE_STREAM unsafeHeadM #-}
394 unsafeHeadM v = unsafeIndexM v 0
395
396 unsafeLastM :: (Vector v a, Monad m) => v a -> m a
397 {-# INLINE_STREAM unsafeLastM #-}
398 unsafeLastM v = unsafeIndexM v (length v - 1)
399
400 -- FIXME: the rhs of these rules are lazy in the stream which is WRONG
401 {- RULES
402
403 "indexM/unstream [Vector]" forall v i s.
404 indexM (new' v (New.unstream s)) i = return (s Stream.!! i)
405
406 "headM/unstream [Vector]" forall v s.
407 headM (new' v (New.unstream s)) = return (Stream.head s)
408
409 "lastM/unstream [Vector]" forall v s.
410 lastM (new' v (New.unstream s)) = return (Stream.last s)
411
412 -}
413
414 -- Subarrays
415 -- ---------
416
417 -- | Yield a part of the vector without copying it.
418 slice :: Vector v a => Int -- ^ starting index
419 -> Int -- ^ length
420 -> v a
421 -> v a
422 {-# INLINE_STREAM slice #-}
423 slice i n v = BOUNDS_CHECK(checkSlice) "slice" i n (length v)
424 $ basicUnsafeSlice i n v
425
426 -- | Yield all but the last element without copying.
427 init :: Vector v a => v a -> v a
428 {-# INLINE_STREAM init #-}
429 init v = slice 0 (length v - 1) v
430
431 -- | All but the first element (without copying).
432 tail :: Vector v a => v a -> v a
433 {-# INLINE_STREAM tail #-}
434 tail v = slice 1 (length v - 1) v
435
436 -- | Yield the first @n@ elements without copying.
437 take :: Vector v a => Int -> v a -> v a
438 {-# INLINE_STREAM take #-}
439 take n v = unsafeSlice 0 (delay_inline min n' (length v)) v
440 where n' = max n 0
441
442 -- | Yield all but the first @n@ elements without copying.
443 drop :: Vector v a => Int -> v a -> v a
444 {-# INLINE_STREAM drop #-}
445 drop n v = unsafeSlice (delay_inline min n' len)
446 (delay_inline max 0 (len - n')) v
447 where n' = max n 0
448 len = length v
449
450 -- | Unsafely yield a part of the vector without copying it and without
451 -- performing bounds checks.
452 unsafeSlice :: Vector v a => Int -- ^ starting index
453 -> Int -- ^ length
454 -> v a
455 -> v a
456 {-# INLINE_STREAM unsafeSlice #-}
457 unsafeSlice i n v = UNSAFE_CHECK(checkSlice) "unsafeSlice" i n (length v)
458 $ basicUnsafeSlice i n v
459
460 unsafeInit :: Vector v a => v a -> v a
461 {-# INLINE_STREAM unsafeInit #-}
462 unsafeInit v = unsafeSlice 0 (length v - 1) v
463
464 unsafeTail :: Vector v a => v a -> v a
465 {-# INLINE_STREAM unsafeTail #-}
466 unsafeTail v = unsafeSlice 1 (length v - 1) v
467
468 unsafeTake :: Vector v a => Int -> v a -> v a
469 {-# INLINE unsafeTake #-}
470 unsafeTake n v = unsafeSlice 0 n v
471
472 unsafeDrop :: Vector v a => Int -> v a -> v a
473 {-# INLINE unsafeDrop #-}
474 unsafeDrop n v = unsafeSlice n (length v - n) v
475
476 {-# RULES
477
478 "slice/new [Vector]" forall i n p.
479 slice i n (new p) = new (New.slice i n p)
480
481 "init/new [Vector]" forall p.
482 init (new p) = new (New.init p)
483
484 "tail/new [Vector]" forall p.
485 tail (new p) = new (New.tail p)
486
487 "take/new [Vector]" forall n p.
488 take n (new p) = new (New.take n p)
489
490 "drop/new [Vector]" forall n p.
491 drop n (new p) = new (New.drop n p)
492
493 "unsafeSlice/new [Vector]" forall i n p.
494 unsafeSlice i n (new p) = new (New.unsafeSlice i n p)
495
496 "unsafeInit/new [Vector]" forall p.
497 unsafeInit (new p) = new (New.unsafeInit p)
498
499 "unsafeTail/new [Vector]" forall p.
500 unsafeTail (new p) = new (New.unsafeTail p)
501
502 #-}
503
504 -- Permutations
505 -- ------------
506
507 unsafeAccum_stream
508 :: Vector v a => (a -> b -> a) -> v a -> Stream (Int,b) -> v a
509 {-# INLINE unsafeAccum_stream #-}
510 unsafeAccum_stream f v s = s `seq` modify (\mv -> M.unsafeAccum f mv s) v
511
512 unsafeAccum :: Vector v a => (a -> b -> a) -> v a -> [(Int,b)] -> v a
513 {-# INLINE unsafeAccum #-}
514 unsafeAccum f v us = unsafeAccum_stream f v (Stream.fromList us)
515
516 unsafeAccumulate :: (Vector v a, Vector v (Int, b))
517 => (a -> b -> a) -> v a -> v (Int,b) -> v a
518 {-# INLINE unsafeAccumulate #-}
519 unsafeAccumulate f v us = unsafeAccum_stream f v (stream us)
520
521 unsafeAccumulate_ :: (Vector v a, Vector v Int, Vector v b)
522 => (a -> b -> a) -> v a -> v Int -> v b -> v a
523 {-# INLINE unsafeAccumulate_ #-}
524 unsafeAccumulate_ f v is xs
525 = unsafeAccum_stream f v (Stream.zipWith (,) (stream is) (stream xs))
526
527 accum_stream :: Vector v a => (a -> b -> a) -> v a -> Stream (Int,b) -> v a
528 {-# INLINE accum_stream #-}
529 accum_stream f v s = s `seq` modify (\mv -> M.accum f mv s) v
530
531 accum :: Vector v a => (a -> b -> a) -> v a -> [(Int,b)] -> v a
532 {-# INLINE accum #-}
533 accum f v us = accum_stream f v (Stream.fromList us)
534
535 accumulate :: (Vector v a, Vector v (Int, b))
536 => (a -> b -> a) -> v a -> v (Int,b) -> v a
537 {-# INLINE accumulate #-}
538 accumulate f v us = accum_stream f v (stream us)
539
540 accumulate_ :: (Vector v a, Vector v Int, Vector v b)
541 => (a -> b -> a) -> v a -> v Int -> v b -> v a
542 {-# INLINE accumulate_ #-}
543 accumulate_ f v is xs = accum_stream f v (Stream.zipWith (,) (stream is)
544 (stream xs))
545
546
547 unsafeUpdate_stream :: Vector v a => v a -> Stream (Int,a) -> v a
548 {-# INLINE unsafeUpdate_stream #-}
549 unsafeUpdate_stream v s = s `seq` modify (\mv -> M.unsafeUpdate mv s) v
550
551 unsafeUpd :: Vector v a => v a -> [(Int, a)] -> v a
552 {-# INLINE unsafeUpd #-}
553 unsafeUpd v us = unsafeUpdate_stream v (Stream.fromList us)
554
555 unsafeUpdate :: (Vector v a, Vector v (Int, a)) => v a -> v (Int, a) -> v a
556 {-# INLINE unsafeUpdate #-}
557 unsafeUpdate v w = unsafeUpdate_stream v (stream w)
558
559 unsafeUpdate_ :: (Vector v a, Vector v Int) => v a -> v Int -> v a -> v a
560 {-# INLINE unsafeUpdate_ #-}
561 unsafeUpdate_ v is w
562 = unsafeUpdate_stream v (Stream.zipWith (,) (stream is) (stream w))
563
564 update_stream :: Vector v a => v a -> Stream (Int,a) -> v a
565 {-# INLINE update_stream #-}
566 update_stream v s = s `seq` modify (\mv -> M.update mv s) v
567
568 (//) :: Vector v a => v a -> [(Int, a)] -> v a
569 {-# INLINE (//) #-}
570 v // us = update_stream v (Stream.fromList us)
571
572 update :: (Vector v a, Vector v (Int, a)) => v a -> v (Int, a) -> v a
573 {-# INLINE update #-}
574 update v w = update_stream v (stream w)
575
576 update_ :: (Vector v a, Vector v Int) => v a -> v Int -> v a -> v a
577 {-# INLINE update_ #-}
578 update_ v is w = update_stream v (Stream.zipWith (,) (stream is) (stream w))
579
580 -- This somewhat non-intuitive definition ensures that the resulting vector
581 -- does not retain references to the original one even if it is lazy in its
582 -- elements. This would not be the case if we simply used
583 --
584 -- backpermute v is = map (v!) is
585 backpermute :: (Vector v a, Vector v Int) => v a -> v Int -> v a
586 {-# INLINE backpermute #-}
587 backpermute v is = seq v
588 $ unstream
589 $ Stream.unbox
590 $ Stream.map (indexM v)
591 $ stream is
592
593 unsafeBackpermute :: (Vector v a, Vector v Int) => v a -> v Int -> v a
594 {-# INLINE unsafeBackpermute #-}
595 unsafeBackpermute v is = seq v
596 $ unstream
597 $ Stream.unbox
598 $ Stream.map (unsafeIndexM v)
599 $ stream is
600
601 -- FIXME: make this fuse better, add support for recycling
602 reverse :: (Vector v a) => v a -> v a
603 {-# INLINE reverse #-}
604 reverse = unstream . streamR
605
606 -- Mapping
607 -- -------
608
609 -- | Map a function over a vector
610 map :: (Vector v a, Vector v b) => (a -> b) -> v a -> v b
611 {-# INLINE map #-}
612 map f = unstream . inplace (MStream.map f) . stream
613
614 -- | Apply a function to every index/value pair
615 imap :: (Vector v a, Vector v b) => (Int -> a -> b) -> v a -> v b
616 {-# INLINE imap #-}
617 imap f = unstream . inplace (MStream.map (uncurry f) . MStream.indexed)
618 . stream
619
620 concatMap :: (Vector v a, Vector v b) => (a -> v b) -> v a -> v b
621 {-# INLINE concatMap #-}
622 concatMap f = unstream . Stream.concatMap (stream . f) . stream
623
624 -- Zipping/unzipping
625 -- -----------------
626
627 -- | Zip two vectors with the given function.
628 zipWith :: (Vector v a, Vector v b, Vector v c)
629 => (a -> b -> c) -> v a -> v b -> v c
630 {-# INLINE zipWith #-}
631 zipWith f xs ys = unstream (Stream.zipWith f (stream xs) (stream ys))
632
633 -- | Zip three vectors with the given function.
634 zipWith3 :: (Vector v a, Vector v b, Vector v c, Vector v d)
635 => (a -> b -> c -> d) -> v a -> v b -> v c -> v d
636 {-# INLINE zipWith3 #-}
637 zipWith3 f as bs cs = unstream (Stream.zipWith3 f (stream as)
638 (stream bs)
639 (stream cs))
640
641 zipWith4 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e)
642 => (a -> b -> c -> d -> e) -> v a -> v b -> v c -> v d -> v e
643 {-# INLINE zipWith4 #-}
644 zipWith4 f as bs cs ds
645 = unstream (Stream.zipWith4 f (stream as)
646 (stream bs)
647 (stream cs)
648 (stream ds))
649
650 zipWith5 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e,
651 Vector v f)
652 => (a -> b -> c -> d -> e -> f) -> v a -> v b -> v c -> v d -> v e
653 -> v f
654 {-# INLINE zipWith5 #-}
655 zipWith5 f as bs cs ds es
656 = unstream (Stream.zipWith5 f (stream as)
657 (stream bs)
658 (stream cs)
659 (stream ds)
660 (stream es))
661
662 zipWith6 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e,
663 Vector v f, Vector v g)
664 => (a -> b -> c -> d -> e -> f -> g)
665 -> v a -> v b -> v c -> v d -> v e -> v f -> v g
666 {-# INLINE zipWith6 #-}
667 zipWith6 f as bs cs ds es fs
668 = unstream (Stream.zipWith6 f (stream as)
669 (stream bs)
670 (stream cs)
671 (stream ds)
672 (stream es)
673 (stream fs))
674
675 -- | Zip two vectors and their indices with the given function.
676 izipWith :: (Vector v a, Vector v b, Vector v c)
677 => (Int -> a -> b -> c) -> v a -> v b -> v c
678 {-# INLINE izipWith #-}
679 izipWith f xs ys = unstream
680 (Stream.zipWith (uncurry f) (Stream.indexed (stream xs))
681 (stream ys))
682
683 -- | Zip three vectors and their indices with the given function.
684 izipWith3 :: (Vector v a, Vector v b, Vector v c, Vector v d)
685 => (Int -> a -> b -> c -> d) -> v a -> v b -> v c -> v d
686 {-# INLINE izipWith3 #-}
687 izipWith3 f as bs cs
688 = unstream (Stream.zipWith3 (uncurry f) (Stream.indexed (stream as))
689 (stream bs)
690 (stream cs))
691
692 izipWith4 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e)
693 => (Int -> a -> b -> c -> d -> e) -> v a -> v b -> v c -> v d -> v e
694 {-# INLINE izipWith4 #-}
695 izipWith4 f as bs cs ds
696 = unstream (Stream.zipWith4 (uncurry f) (Stream.indexed (stream as))
697 (stream bs)
698 (stream cs)
699 (stream ds))
700
701 izipWith5 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e,
702 Vector v f)
703 => (Int -> a -> b -> c -> d -> e -> f) -> v a -> v b -> v c -> v d
704 -> v e -> v f
705 {-# INLINE izipWith5 #-}
706 izipWith5 f as bs cs ds es
707 = unstream (Stream.zipWith5 (uncurry f) (Stream.indexed (stream as))
708 (stream bs)
709 (stream cs)
710 (stream ds)
711 (stream es))
712
713 izipWith6 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e,
714 Vector v f, Vector v g)
715 => (Int -> a -> b -> c -> d -> e -> f -> g)
716 -> v a -> v b -> v c -> v d -> v e -> v f -> v g
717 {-# INLINE izipWith6 #-}
718 izipWith6 f as bs cs ds es fs
719 = unstream (Stream.zipWith6 (uncurry f) (Stream.indexed (stream as))
720 (stream bs)
721 (stream cs)
722 (stream ds)
723 (stream es)
724 (stream fs))
725
726 zip :: (Vector v a, Vector v b, Vector v (a,b)) => v a -> v b -> v (a, b)
727 {-# INLINE zip #-}
728 zip = zipWith (,)
729
730 zip3 :: (Vector v a, Vector v b, Vector v c, Vector v (a, b, c))
731 => v a -> v b -> v c -> v (a, b, c)
732 {-# INLINE zip3 #-}
733 zip3 = zipWith3 (,,)
734
735 zip4 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v (a, b, c, d))
736 => v a -> v b -> v c -> v d -> v (a, b, c, d)
737 {-# INLINE zip4 #-}
738 zip4 = zipWith4 (,,,)
739
740 zip5 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e,
741 Vector v (a, b, c, d, e))
742 => v a -> v b -> v c -> v d -> v e -> v (a, b, c, d, e)
743 {-# INLINE zip5 #-}
744 zip5 = zipWith5 (,,,,)
745
746 zip6 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e,
747 Vector v f, Vector v (a, b, c, d, e, f))
748 => v a -> v b -> v c -> v d -> v e -> v f -> v (a, b, c, d, e, f)
749 {-# INLINE zip6 #-}
750 zip6 = zipWith6 (,,,,,)
751
752 unzip :: (Vector v a, Vector v b, Vector v (a,b)) => v (a, b) -> (v a, v b)
753 {-# INLINE unzip #-}
754 unzip xs = (map fst xs, map snd xs)
755
756 unzip3 :: (Vector v a, Vector v b, Vector v c, Vector v (a, b, c))
757 => v (a, b, c) -> (v a, v b, v c)
758 {-# INLINE unzip3 #-}
759 unzip3 xs = (map (\(a, b, c) -> a) xs,
760 map (\(a, b, c) -> b) xs,
761 map (\(a, b, c) -> c) xs)
762
763 unzip4 :: (Vector v a, Vector v b, Vector v c, Vector v d,
764 Vector v (a, b, c, d))
765 => v (a, b, c, d) -> (v a, v b, v c, v d)
766 {-# INLINE unzip4 #-}
767 unzip4 xs = (map (\(a, b, c, d) -> a) xs,
768 map (\(a, b, c, d) -> b) xs,
769 map (\(a, b, c, d) -> c) xs,
770 map (\(a, b, c, d) -> d) xs)
771
772 unzip5 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e,
773 Vector v (a, b, c, d, e))
774 => v (a, b, c, d, e) -> (v a, v b, v c, v d, v e)
775 {-# INLINE unzip5 #-}
776 unzip5 xs = (map (\(a, b, c, d, e) -> a) xs,
777 map (\(a, b, c, d, e) -> b) xs,
778 map (\(a, b, c, d, e) -> c) xs,
779 map (\(a, b, c, d, e) -> d) xs,
780 map (\(a, b, c, d, e) -> e) xs)
781
782 unzip6 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e,
783 Vector v f, Vector v (a, b, c, d, e, f))
784 => v (a, b, c, d, e, f) -> (v a, v b, v c, v d, v e, v f)
785 {-# INLINE unzip6 #-}
786 unzip6 xs = (map (\(a, b, c, d, e, f) -> a) xs,
787 map (\(a, b, c, d, e, f) -> b) xs,
788 map (\(a, b, c, d, e, f) -> c) xs,
789 map (\(a, b, c, d, e, f) -> d) xs,
790 map (\(a, b, c, d, e, f) -> e) xs,
791 map (\(a, b, c, d, e, f) -> f) xs)
792
793 -- Comparisons
794 -- -----------
795
796 eq :: (Vector v a, Eq a) => v a -> v a -> Bool
797 {-# INLINE eq #-}
798 xs `eq` ys = stream xs == stream ys
799
800 cmp :: (Vector v a, Ord a) => v a -> v a -> Ordering
801 {-# INLINE cmp #-}
802 cmp xs ys = compare (stream xs) (stream ys)
803
804 -- Filtering
805 -- ---------
806
807 -- | Drop elements that do not satisfy the predicate
808 filter :: Vector v a => (a -> Bool) -> v a -> v a
809 {-# INLINE filter #-}
810 filter f = unstream . inplace (MStream.filter f) . stream
811
812 -- | Drop elements that do not satisfy the predicate (applied to values and
813 -- their indices)
814 ifilter :: Vector v a => (Int -> a -> Bool) -> v a -> v a
815 {-# INLINE ifilter #-}
816 ifilter f = unstream
817 . inplace (MStream.map snd . MStream.filter (uncurry f)
818 . MStream.indexed)
819 . stream
820
821 -- | Yield the longest prefix of elements satisfying the predicate.
822 takeWhile :: Vector v a => (a -> Bool) -> v a -> v a
823 {-# INLINE takeWhile #-}
824 takeWhile f = unstream . Stream.takeWhile f . stream
825
826 -- | Drop the longest prefix of elements that satisfy the predicate.
827 dropWhile :: Vector v a => (a -> Bool) -> v a -> v a
828 {-# INLINE dropWhile #-}
829 dropWhile f = unstream . Stream.dropWhile f . stream
830
831 -- | Split the vector in two parts, the first one containing those elements
832 -- that satisfy the predicate and the second one those that don't. The
833 -- relative order of the elements is preserved at the cost of a (sometimes)
834 -- reduced performance compared to 'unstablePartition'.
835 partition :: Vector v a => (a -> Bool) -> v a -> (v a, v a)
836 {-# INLINE partition #-}
837 partition f = partition_stream f . stream
838
839 -- FIXME: Make this inplace-fusible (look at how stable_partition is
840 -- implemented in C++)
841
842 partition_stream :: Vector v a => (a -> Bool) -> Stream a -> (v a, v a)
843 {-# INLINE_STREAM partition_stream #-}
844 partition_stream f s = s `seq` runST (
845 do
846 (mv1,mv2) <- M.partitionStream f s
847 v1 <- unsafeFreeze mv1
848 v2 <- unsafeFreeze mv2
849 return (v1,v2))
850
851 -- | Split the vector in two parts, the first one containing those elements
852 -- that satisfy the predicate and the second one those that don't. The order
853 -- of the elements is not preserved but the operation is often faster than
854 -- 'partition'.
855 unstablePartition :: Vector v a => (a -> Bool) -> v a -> (v a, v a)
856 {-# INLINE unstablePartition #-}
857 unstablePartition f = unstablePartition_stream f . stream
858
859 unstablePartition_stream
860 :: Vector v a => (a -> Bool) -> Stream a -> (v a, v a)
861 {-# INLINE_STREAM unstablePartition_stream #-}
862 unstablePartition_stream f s = s `seq` runST (
863 do
864 (mv1,mv2) <- M.unstablePartitionStream f s
865 v1 <- unsafeFreeze mv1
866 v2 <- unsafeFreeze mv2
867 return (v1,v2))
868
869 unstablePartition_new :: Vector v a => (a -> Bool) -> New v a -> (v a, v a)
870 {-# INLINE_STREAM unstablePartition_new #-}
871 unstablePartition_new f (New.New p) = runST (
872 do
873 mv <- p
874 i <- M.unstablePartition f mv
875 v <- unsafeFreeze mv
876 return (unsafeTake i v, unsafeDrop i v))
877
878 {-# RULES
879
880 "unstablePartition" forall f p.
881 unstablePartition_stream f (stream (new p))
882 = unstablePartition_new f p
883
884 #-}
885
886
887 -- FIXME: make span and break fusible
888
889 -- | Split the vector into the longest prefix of elements that satisfy the
890 -- predicate and the rest.
891 span :: Vector v a => (a -> Bool) -> v a -> (v a, v a)
892 {-# INLINE span #-}
893 span f = break (not . f)
894
895 -- | Split the vector into the longest prefix of elements that do not satisfy
896 -- the predicate and the rest.
897 break :: Vector v a => (a -> Bool) -> v a -> (v a, v a)
898 {-# INLINE break #-}
899 break f xs = case findIndex f xs of
900 Just i -> (unsafeSlice 0 i xs, unsafeSlice i (length xs - i) xs)
901 Nothing -> (xs, empty)
902
903
904 -- Searching
905 -- ---------
906
907 infix 4 `elem`
908 -- | Check whether the vector contains an element
909 elem :: (Vector v a, Eq a) => a -> v a -> Bool
910 {-# INLINE elem #-}
911 elem x = Stream.elem x . stream
912
913 infix 4 `notElem`
914 -- | Inverse of `elem`
915 notElem :: (Vector v a, Eq a) => a -> v a -> Bool
916 {-# INLINE notElem #-}
917 notElem x = Stream.notElem x . stream
918
919 -- | Yield 'Just' the first element matching the predicate or 'Nothing' if no
920 -- such element exists.
921 find :: Vector v a => (a -> Bool) -> v a -> Maybe a
922 {-# INLINE find #-}
923 find f = Stream.find f . stream
924
925 -- | Yield 'Just' the index of the first element matching the predicate or
926 -- 'Nothing' if no such element exists.
927 findIndex :: Vector v a => (a -> Bool) -> v a -> Maybe Int
928 {-# INLINE findIndex #-}
929 findIndex f = Stream.findIndex f . stream
930
931 -- | Yield the indices of elements satisfying the predicate
932 findIndices :: (Vector v a, Vector v Int) => (a -> Bool) -> v a -> v Int
933 {-# INLINE findIndices #-}
934 findIndices f = unstream
935 . inplace (MStream.map fst . MStream.filter (f . snd)
936 . MStream.indexed)
937 . stream
938
939 -- | Yield 'Just' the index of the first occurence of the given element or
940 -- 'Nothing' if the vector does not contain the element
941 elemIndex :: (Vector v a, Eq a) => a -> v a -> Maybe Int
942 {-# INLINE elemIndex #-}
943 elemIndex x = findIndex (x==)
944
945 -- | Yield the indices of all occurences of the given element
946 elemIndices :: (Vector v a, Vector v Int, Eq a) => a -> v a -> v Int
947 {-# INLINE elemIndices #-}
948 elemIndices x = findIndices (x==)
949
950 -- Folding
951 -- -------
952
953 -- | Left fold
954 foldl :: Vector v b => (a -> b -> a) -> a -> v b -> a
955 {-# INLINE foldl #-}
956 foldl f z = Stream.foldl f z . stream
957
958 -- | Left fold on non-empty vectors
959 foldl1 :: Vector v a => (a -> a -> a) -> v a -> a
960 {-# INLINE foldl1 #-}
961 foldl1 f = Stream.foldl1 f . stream
962
963 -- | Left fold with strict accumulator
964 foldl' :: Vector v b => (a -> b -> a) -> a -> v b -> a
965 {-# INLINE foldl' #-}
966 foldl' f z = Stream.foldl' f z . stream
967
968 -- | Left fold on non-empty vectors with strict accumulator
969 foldl1' :: Vector v a => (a -> a -> a) -> v a -> a
970 {-# INLINE foldl1' #-}
971 foldl1' f = Stream.foldl1' f . stream
972
973 -- | Right fold
974 foldr :: Vector v a => (a -> b -> b) -> b -> v a -> b
975 {-# INLINE foldr #-}
976 foldr f z = Stream.foldr f z . stream
977
978 -- | Right fold on non-empty vectors
979 foldr1 :: Vector v a => (a -> a -> a) -> v a -> a
980 {-# INLINE foldr1 #-}
981 foldr1 f = Stream.foldr1 f . stream
982
983 -- | Right fold with a strict accumulator
984 foldr' :: Vector v a => (a -> b -> b) -> b -> v a -> b
985 {-# INLINE foldr' #-}
986 foldr' f z = Stream.foldl' (flip f) z . streamR
987
988 -- | Right fold on non-empty vectors with strict accumulator
989 foldr1' :: Vector v a => (a -> a -> a) -> v a -> a
990 {-# INLINE foldr1' #-}
991 foldr1' f = Stream.foldl1' (flip f) . streamR
992
993 -- | Left fold (function applied to each element and its index)
994 ifoldl :: Vector v b => (a -> Int -> b -> a) -> a -> v b -> a
995 {-# INLINE ifoldl #-}
996 ifoldl f z = Stream.foldl (uncurry . f) z . Stream.indexed . stream
997
998 -- | Left fold with strict accumulator (function applied to each element and
999 -- its index)
1000 ifoldl' :: Vector v b => (a -> Int -> b -> a) -> a -> v b -> a
1001 {-# INLINE ifoldl' #-}
1002 ifoldl' f z = Stream.foldl' (uncurry . f) z . Stream.indexed . stream
1003
1004 -- | Right fold (function applied to each element and its index)
1005 ifoldr :: Vector v a => (Int -> a -> b -> b) -> b -> v a -> b
1006 {-# INLINE ifoldr #-}
1007 ifoldr f z = Stream.foldr (uncurry f) z . Stream.indexed . stream
1008
1009 -- | Right fold with strict accumulator (function applied to each element and
1010 -- its index)
1011 ifoldr' :: Vector v a => (Int -> a -> b -> b) -> b -> v a -> b
1012 {-# INLINE ifoldr' #-}
1013 ifoldr' f z xs = Stream.foldl' (flip (uncurry f)) z
1014 $ Stream.indexedR (length xs) $ streamR xs
1015
1016 -- Specialised folds
1017 -- -----------------
1018
1019 all :: Vector v a => (a -> Bool) -> v a -> Bool
1020 {-# INLINE all #-}
1021 all f = Stream.and . Stream.map f . stream
1022
1023 any :: Vector v a => (a -> Bool) -> v a -> Bool
1024 {-# INLINE any #-}
1025 any f = Stream.or . Stream.map f . stream
1026
1027 and :: Vector v Bool => v Bool -> Bool
1028 {-# INLINE and #-}
1029 and = Stream.and . stream
1030
1031 or :: Vector v Bool => v Bool -> Bool
1032 {-# INLINE or #-}
1033 or = Stream.or . stream
1034
1035 sum :: (Vector v a, Num a) => v a -> a
1036 {-# INLINE sum #-}
1037 sum = Stream.foldl' (+) 0 . stream
1038
1039 product :: (Vector v a, Num a) => v a -> a
1040 {-# INLINE product #-}
1041 product = Stream.foldl' (*) 1 . stream
1042
1043 maximum :: (Vector v a, Ord a) => v a -> a
1044 {-# INLINE maximum #-}
1045 maximum = Stream.foldl1' max . stream
1046
1047 maximumBy :: Vector v a => (a -> a -> Ordering) -> v a -> a
1048 {-# INLINE maximumBy #-}
1049 maximumBy cmp = Stream.foldl1' maxBy . stream
1050 where
1051 {-# INLINE maxBy #-}
1052 maxBy x y = case cmp x y of
1053 LT -> y
1054 _ -> x
1055
1056 minimum :: (Vector v a, Ord a) => v a -> a
1057 {-# INLINE minimum #-}
1058 minimum = Stream.foldl1' min . stream
1059
1060 minimumBy :: Vector v a => (a -> a -> Ordering) -> v a -> a
1061 {-# INLINE minimumBy #-}
1062 minimumBy cmp = Stream.foldl1' minBy . stream
1063 where
1064 {-# INLINE minBy #-}
1065 minBy x y = case cmp x y of
1066 GT -> y
1067 _ -> x
1068
1069 maxIndex :: (Vector v a, Ord a) => v a -> Int
1070 {-# INLINE maxIndex #-}
1071 maxIndex = maxIndexBy compare
1072
1073 maxIndexBy :: Vector v a => (a -> a -> Ordering) -> v a -> Int
1074 {-# INLINE maxIndexBy #-}
1075 maxIndexBy cmp = fst . Stream.foldl1' imax . Stream.indexed . stream
1076 where
1077 imax (i,x) (j,y) = case cmp x y of
1078 LT -> (j,y)
1079 _ -> (i,x)
1080
1081 minIndex :: (Vector v a, Ord a) => v a -> Int
1082 {-# INLINE minIndex #-}
1083 minIndex = minIndexBy compare
1084
1085 minIndexBy :: Vector v a => (a -> a -> Ordering) -> v a -> Int
1086 {-# INLINE minIndexBy #-}
1087 minIndexBy cmp = fst . Stream.foldl1' imin . Stream.indexed . stream
1088 where
1089 imin (i,x) (j,y) = case cmp x y of
1090 GT -> (j,y)
1091 _ -> (i,x)
1092
1093
1094 -- Unfolding
1095 -- ---------
1096
1097 -- | Unfold
1098 unfoldr :: Vector v a => (b -> Maybe (a, b)) -> b -> v a
1099 {-# INLINE unfoldr #-}
1100 unfoldr f = unstream . Stream.unfoldr f
1101
1102 -- | Unfoldr at most @n@ elements.
1103 unfoldrN :: Vector v a => Int -> (b -> Maybe (a, b)) -> b -> v a
1104 {-# INLINE unfoldrN #-}
1105 unfoldrN n f = unstream . Stream.unfoldrN n f
1106
1107 -- Scans
1108 -- -----
1109
1110 -- | Prefix scan
1111 prescanl :: (Vector v a, Vector v b) => (a -> b -> a) -> a -> v b -> v a
1112 {-# INLINE prescanl #-}
1113 prescanl f z = unstream . inplace (MStream.prescanl f z) . stream
1114
1115 -- | Prefix scan with strict accumulator
1116 prescanl' :: (Vector v a, Vector v b) => (a -> b -> a) -> a -> v b -> v a
1117 {-# INLINE prescanl' #-}
1118 prescanl' f z = unstream . inplace (MStream.prescanl' f z) . stream
1119
1120 -- | Suffix scan
1121 postscanl :: (Vector v a, Vector v b) => (a -> b -> a) -> a -> v b -> v a
1122 {-# INLINE postscanl #-}
1123 postscanl f z = unstream . inplace (MStream.postscanl f z) . stream
1124
1125 -- | Suffix scan with strict accumulator
1126 postscanl' :: (Vector v a, Vector v b) => (a -> b -> a) -> a -> v b -> v a
1127 {-# INLINE postscanl' #-}
1128 postscanl' f z = unstream . inplace (MStream.postscanl' f z) . stream
1129
1130 -- | Haskell-style scan
1131 scanl :: (Vector v a, Vector v b) => (a -> b -> a) -> a -> v b -> v a
1132 {-# INLINE scanl #-}
1133 scanl f z = unstream . Stream.scanl f z . stream
1134
1135 -- | Haskell-style scan with strict accumulator
1136 scanl' :: (Vector v a, Vector v b) => (a -> b -> a) -> a -> v b -> v a
1137 {-# INLINE scanl' #-}
1138 scanl' f z = unstream . Stream.scanl' f z . stream
1139
1140 -- | Scan over a non-empty vector
1141 scanl1 :: Vector v a => (a -> a -> a) -> v a -> v a
1142 {-# INLINE scanl1 #-}
1143 scanl1 f = unstream . inplace (MStream.scanl1 f) . stream
1144
1145 -- | Scan over a non-empty vector with a strict accumulator
1146 scanl1' :: Vector v a => (a -> a -> a) -> v a -> v a
1147 {-# INLINE scanl1' #-}
1148 scanl1' f = unstream . inplace (MStream.scanl1' f) . stream
1149
1150
1151 -- | Prefix right-to-left scan
1152 prescanr :: (Vector v a, Vector v b) => (a -> b -> b) -> b -> v a -> v b
1153 {-# INLINE prescanr #-}
1154 prescanr f z = unstreamR . inplace (MStream.prescanl (flip f) z) . streamR
1155
1156 -- | Prefix right-to-left scan with strict accumulator
1157 prescanr' :: (Vector v a, Vector v b) => (a -> b -> b) -> b -> v a -> v b
1158 {-# INLINE prescanr' #-}
1159 prescanr' f z = unstreamR . inplace (MStream.prescanl' (flip f) z) . streamR
1160
1161 -- | Suffix right-to-left scan
1162 postscanr :: (Vector v a, Vector v b) => (a -> b -> b) -> b -> v a -> v b
1163 {-# INLINE postscanr #-}
1164 postscanr f z = unstreamR . inplace (MStream.postscanl (flip f) z) . streamR
1165
1166 -- | Suffix right-to-left scan with strict accumulator
1167 postscanr' :: (Vector v a, Vector v b) => (a -> b -> b) -> b -> v a -> v b
1168 {-# INLINE postscanr' #-}
1169 postscanr' f z = unstreamR . inplace (MStream.postscanl' (flip f) z) . streamR
1170
1171 -- | Haskell-style right-to-left scan
1172 scanr :: (Vector v a, Vector v b) => (a -> b -> b) -> b -> v a -> v b
1173 {-# INLINE scanr #-}
1174 scanr f z = unstreamR . Stream.scanl (flip f) z . streamR
1175
1176 -- | Haskell-style right-to-left scan with strict accumulator
1177 scanr' :: (Vector v a, Vector v b) => (a -> b -> b) -> b -> v a -> v b
1178 {-# INLINE scanr' #-}
1179 scanr' f z = unstreamR . Stream.scanl' (flip f) z . streamR
1180
1181 -- | Right-to-left scan over a non-empty vector
1182 scanr1 :: Vector v a => (a -> a -> a) -> v a -> v a
1183 {-# INLINE scanr1 #-}
1184 scanr1 f = unstreamR . inplace (MStream.scanl1 (flip f)) . streamR
1185
1186 -- | Right-to-left scan over a non-empty vector with a strict accumulator
1187 scanr1' :: Vector v a => (a -> a -> a) -> v a -> v a
1188 {-# INLINE scanr1' #-}
1189 scanr1' f = unstreamR . inplace (MStream.scanl1' (flip f)) . streamR
1190
1191 -- Enumeration
1192 -- -----------
1193
1194 -- | Yield a vector of the given length containing the values @x@, @x+1@ etc.
1195 -- This operation is usually more efficient than 'enumFromTo'.
1196 enumFromN :: (Vector v a, Num a) => a -> Int -> v a
1197 {-# INLINE enumFromN #-}
1198 enumFromN x n = enumFromStepN x 1 n
1199
1200 -- | Yield a vector of the given length containing the values @x@, @x+y@,
1201 -- @x+y+y@ etc. This operations is usually more efficient than
1202 -- 'enumFromThenTo'.
1203 enumFromStepN :: forall v a. (Vector v a, Num a) => a -> a -> Int -> v a
1204 {-# INLINE enumFromStepN #-}
1205 enumFromStepN x y n = elemseq (undefined :: v a) x
1206 $ elemseq (undefined :: v a) y
1207 $ unstream
1208 $ Stream.enumFromStepN x y n
1209
1210 -- | Enumerate values from @x@ to @y@.
1211 --
1212 -- /WARNING:/ This operation can be very inefficient. If at all possible, use
1213 -- 'enumFromN' instead.
1214 enumFromTo :: (Vector v a, Enum a) => a -> a -> v a
1215 {-# INLINE enumFromTo #-}
1216 enumFromTo x y = unstream (Stream.enumFromTo x y)
1217
1218 -- | Enumerate values from @x@ to @y@ with a specific step @z@.
1219 --
1220 -- /WARNING:/ This operation can be very inefficient. If at all possible, use
1221 -- 'enumFromStepN' instead.
1222 enumFromThenTo :: (Vector v a, Enum a) => a -> a -> a -> v a
1223 {-# INLINE enumFromThenTo #-}
1224 enumFromThenTo x y z = unstream (Stream.enumFromThenTo x y z)
1225
1226 -- Conversion to/from lists
1227 -- ------------------------
1228
1229 -- | Convert a vector to a list
1230 toList :: Vector v a => v a -> [a]
1231 {-# INLINE toList #-}
1232 toList = Stream.toList . stream
1233
1234 -- | Convert a list to a vector
1235 fromList :: Vector v a => [a] -> v a
1236 {-# INLINE fromList #-}
1237 fromList = unstream . Stream.fromList
1238
1239 -- | Convert the first @n@ elements of a list to a vector
1240 --
1241 -- > fromListN n xs = fromList (take n xs)
1242 fromListN :: Vector v a => Int -> [a] -> v a
1243 {-# INLINE fromListN #-}
1244 fromListN n = unstream . Stream.fromListN n
1245
1246 -- Destructive operations
1247 -- ----------------------
1248
1249 -- | Destructively initialise a vector.
1250 create :: Vector v a => (forall s. ST s (Mutable v s a)) -> v a
1251 {-# INLINE create #-}
1252 create p = new (New.create p)
1253
1254 -- | Apply a destructive operation to a vector. The operation is applied to a
1255 -- copy of the vector unless it can be safely performed in place.
1256 modify :: Vector v a => (forall s. Mutable v s a -> ST s ()) -> v a -> v a
1257 {-# INLINE modify #-}
1258 modify p = new . New.modify p . clone
1259
1260 -- | Copy an immutable vector into a mutable one. The two vectors must have
1261 -- the same length. This is not checked.
1262 unsafeCopy
1263 :: (PrimMonad m, Vector v a) => Mutable v (PrimState m) a -> v a -> m ()
1264 {-# INLINE unsafeCopy #-}
1265 unsafeCopy dst src = UNSAFE_CHECK(check) "unsafeCopy" "length mismatch"
1266 (M.length dst == length src)
1267 $ (dst `seq` src `seq` basicUnsafeCopy dst src)
1268
1269 -- | Copy an immutable vector into a mutable one. The two vectors must have the
1270 -- same length.
1271 copy
1272 :: (PrimMonad m, Vector v a) => Mutable v (PrimState m) a -> v a -> m ()
1273 {-# INLINE copy #-}
1274 copy dst src = BOUNDS_CHECK(check) "copy" "length mismatch"
1275 (M.length dst == length src)
1276 $ unsafeCopy dst src
1277
1278 -- Utilities for defining Data instances
1279 -- -------------------------------------
1280
1281 -- | Generic definion of 'Data.Data.gfoldl' that views a 'Vector' as a
1282 -- list.
1283 gfoldl :: (Vector v a, Data a)
1284 => (forall d b. Data d => c (d -> b) -> d -> c b)
1285 -> (forall g. g -> c g)
1286 -> v a
1287 -> c (v a)
1288 {-# INLINE gfoldl #-}
1289 gfoldl f z v = z fromList `f` toList v
1290
1291 mkType :: String -> DataType
1292 {-# INLINE mkType #-}
1293 mkType = mkNorepType
1294
1295 dataCast :: (Vector v a, Data a, Typeable1 v, Typeable1 t)
1296 => (forall d. Data d => c (t d)) -> Maybe (c (v a))
1297 {-# INLINE dataCast #-}
1298 dataCast f = gcast1 f
1299