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