Add partition
[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 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 (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 (min n' len) (max 0 (len - n')) v
482 where n' = max n 0
483 len = length v
484
485 -- | Unsafely yield a part of the vector without copying it and without
486 -- performing bounds checks.
487 unsafeSlice :: Vector v a => Int -- ^ starting index
488 -> Int -- ^ length
489 -> v a
490 -> v a
491 {-# INLINE_STREAM unsafeSlice #-}
492 unsafeSlice i n v = UNSAFE_CHECK(checkSlice) "unsafeSlice" i n (length v)
493 $ basicUnsafeSlice i n v
494
495 unsafeInit :: Vector v a => v a -> v a
496 {-# INLINE_STREAM unsafeInit #-}
497 unsafeInit v = unsafeSlice 0 (length v - 1) v
498
499 unsafeTail :: Vector v a => v a -> v a
500 {-# INLINE_STREAM unsafeTail #-}
501 unsafeTail v = unsafeSlice 1 (length v - 1) v
502
503 unsafeTake :: Vector v a => Int -> v a -> v a
504 {-# INLINE unsafeTake #-}
505 unsafeTake n v = unsafeSlice 0 n v
506
507 unsafeDrop :: Vector v a => Int -> v a -> v a
508 {-# INLINE unsafeDrop #-}
509 unsafeDrop n v = unsafeSlice n (length v - n) v
510
511 {-# RULES
512
513 "slice/new [Vector]" forall i n v p.
514 slice i n (new' v p) = new' v (New.slice i n p)
515
516 "init/new [Vector]" forall v p.
517 init (new' v p) = new' v (New.init p)
518
519 "tail/new [Vector]" forall v p.
520 tail (new' v p) = new' v (New.tail p)
521
522 "take/new [Vector]" forall n v p.
523 take n (new' v p) = new' v (New.take n p)
524
525 "drop/new [Vector]" forall n v p.
526 drop n (new' v p) = new' v (New.drop n p)
527
528 "unsafeSlice/new [Vector]" forall i n v p.
529 unsafeSlice i n (new' v p) = new' v (New.unsafeSlice i n p)
530
531 "unsafeInit/new [Vector]" forall v p.
532 unsafeInit (new' v p) = new' v (New.unsafeInit p)
533
534 "unsafeTail/new [Vector]" forall v p.
535 unsafeTail (new' v p) = new' v (New.unsafeTail p)
536
537 #-}
538
539 -- Permutations
540 -- ------------
541
542 unsafeAccum_stream
543 :: Vector v a => (a -> b -> a) -> v a -> Stream (Int,b) -> v a
544 {-# INLINE unsafeAccum_stream #-}
545 unsafeAccum_stream f v s = new (New.accum f (New.unstream (stream v)) s)
546
547 unsafeAccum :: Vector v a => (a -> b -> a) -> v a -> [(Int,b)] -> v a
548 {-# INLINE unsafeAccum #-}
549 unsafeAccum f v us = unsafeAccum_stream f v (Stream.fromList us)
550
551 unsafeAccumulate :: (Vector v a, Vector v (Int, b))
552 => (a -> b -> a) -> v a -> v (Int,b) -> v a
553 {-# INLINE unsafeAccumulate #-}
554 unsafeAccumulate f v us = unsafeAccum_stream f v (stream us)
555
556 unsafeAccumulate_ :: (Vector v a, Vector v Int, Vector v b)
557 => (a -> b -> a) -> v a -> v Int -> v b -> v a
558 {-# INLINE unsafeAccumulate_ #-}
559 unsafeAccumulate_ f v is xs
560 = unsafeAccum_stream f v (Stream.zipWith (,) (stream is) (stream xs))
561
562 accum_stream :: Vector v a => (a -> b -> a) -> v a -> Stream (Int,b) -> v a
563 {-# INLINE accum_stream #-}
564 accum_stream f v s = new (New.accum f (New.unstream (stream v)) s)
565
566 accum :: Vector v a => (a -> b -> a) -> v a -> [(Int,b)] -> v a
567 {-# INLINE accum #-}
568 accum f v us = accum_stream f v (Stream.fromList us)
569
570 accumulate :: (Vector v a, Vector v (Int, b))
571 => (a -> b -> a) -> v a -> v (Int,b) -> v a
572 {-# INLINE accumulate #-}
573 accumulate f v us = accum_stream f v (stream us)
574
575 accumulate_ :: (Vector v a, Vector v Int, Vector v b)
576 => (a -> b -> a) -> v a -> v Int -> v b -> v a
577 {-# INLINE accumulate_ #-}
578 accumulate_ f v is xs = accum_stream f v (Stream.zipWith (,) (stream is)
579 (stream xs))
580
581
582 unsafeUpdate_stream :: Vector v a => v a -> Stream (Int,a) -> v a
583 {-# INLINE unsafeUpdate_stream #-}
584 unsafeUpdate_stream v s = new (New.unsafeUpdate (New.unstream (stream v)) s)
585
586 unsafeUpd :: Vector v a => v a -> [(Int, a)] -> v a
587 {-# INLINE unsafeUpd #-}
588 unsafeUpd v us = unsafeUpdate_stream v (Stream.fromList us)
589
590 unsafeUpdate :: (Vector v a, Vector v (Int, a)) => v a -> v (Int, a) -> v a
591 {-# INLINE unsafeUpdate #-}
592 unsafeUpdate v w = unsafeUpdate_stream v (stream w)
593
594 unsafeUpdate_ :: (Vector v a, Vector v Int) => v a -> v Int -> v a -> v a
595 {-# INLINE unsafeUpdate_ #-}
596 unsafeUpdate_ v is w
597 = unsafeUpdate_stream v (Stream.zipWith (,) (stream is) (stream w))
598
599 update_stream :: Vector v a => v a -> Stream (Int,a) -> v a
600 {-# INLINE update_stream #-}
601 update_stream v s = new (New.update (New.unstream (stream v)) s)
602
603 (//) :: Vector v a => v a -> [(Int, a)] -> v a
604 {-# INLINE (//) #-}
605 v // us = update_stream v (Stream.fromList us)
606
607 update :: (Vector v a, Vector v (Int, a)) => v a -> v (Int, a) -> v a
608 {-# INLINE update #-}
609 update v w = update_stream v (stream w)
610
611 update_ :: (Vector v a, Vector v Int) => v a -> v Int -> v a -> v a
612 {-# INLINE update_ #-}
613 update_ v is w = update_stream v (Stream.zipWith (,) (stream is) (stream w))
614
615 -- This somewhat non-intuitive definition ensures that the resulting vector
616 -- does not retain references to the original one even if it is lazy in its
617 -- elements. This would not be the case if we simply used
618 --
619 -- backpermute v is = map (v!) is
620 backpermute :: (Vector v a, Vector v Int) => v a -> v Int -> v a
621 {-# INLINE backpermute #-}
622 backpermute v is = seq v
623 $ unstream
624 $ Stream.unbox
625 $ Stream.map (indexM v)
626 $ stream is
627
628 unsafeBackpermute :: (Vector v a, Vector v Int) => v a -> v Int -> v a
629 {-# INLINE unsafeBackpermute #-}
630 unsafeBackpermute v is = seq v
631 $ unstream
632 $ Stream.unbox
633 $ Stream.map (unsafeIndexM v)
634 $ stream is
635
636 reverse :: (Vector v a) => v a -> v a
637 {-# INLINE reverse #-}
638 reverse = new . New.reverse . New.unstream . stream
639
640 -- Mapping
641 -- -------
642
643 -- | Map a function over a vector
644 map :: (Vector v a, Vector v b) => (a -> b) -> v a -> v b
645 {-# INLINE map #-}
646 map f = unstream . inplace (MStream.map f) . stream
647
648 -- | Apply a function to every index/value pair
649 imap :: (Vector v a, Vector v b) => (Int -> a -> b) -> v a -> v b
650 {-# INLINE imap #-}
651 imap f = unstream . inplace (MStream.map (uncurry f) . MStream.indexed)
652 . stream
653
654 concatMap :: (Vector v a, Vector v b) => (a -> v b) -> v a -> v b
655 {-# INLINE concatMap #-}
656 concatMap f = unstream . Stream.concatMap (stream . f) . stream
657
658 -- Zipping/unzipping
659 -- -----------------
660
661 -- | Zip two vectors with the given function.
662 zipWith :: (Vector v a, Vector v b, Vector v c)
663 => (a -> b -> c) -> v a -> v b -> v c
664 {-# INLINE zipWith #-}
665 zipWith f xs ys = unstream (Stream.zipWith f (stream xs) (stream ys))
666
667 -- | Zip three vectors with the given function.
668 zipWith3 :: (Vector v a, Vector v b, Vector v c, Vector v d)
669 => (a -> b -> c -> d) -> v a -> v b -> v c -> v d
670 {-# INLINE zipWith3 #-}
671 zipWith3 f as bs cs = unstream (Stream.zipWith3 f (stream as)
672 (stream bs)
673 (stream cs))
674
675 zipWith4 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e)
676 => (a -> b -> c -> d -> e) -> v a -> v b -> v c -> v d -> v e
677 {-# INLINE zipWith4 #-}
678 zipWith4 f as bs cs ds
679 = unstream (Stream.zipWith4 f (stream as)
680 (stream bs)
681 (stream cs)
682 (stream ds))
683
684 zipWith5 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e,
685 Vector v f)
686 => (a -> b -> c -> d -> e -> f) -> v a -> v b -> v c -> v d -> v e
687 -> v f
688 {-# INLINE zipWith5 #-}
689 zipWith5 f as bs cs ds es
690 = unstream (Stream.zipWith5 f (stream as)
691 (stream bs)
692 (stream cs)
693 (stream ds)
694 (stream es))
695
696 zipWith6 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e,
697 Vector v f, Vector v g)
698 => (a -> b -> c -> d -> e -> f -> g)
699 -> v a -> v b -> v c -> v d -> v e -> v f -> v g
700 {-# INLINE zipWith6 #-}
701 zipWith6 f as bs cs ds es fs
702 = unstream (Stream.zipWith6 f (stream as)
703 (stream bs)
704 (stream cs)
705 (stream ds)
706 (stream es)
707 (stream fs))
708
709 -- | Zip two vectors and their indices with the given function.
710 izipWith :: (Vector v a, Vector v b, Vector v c)
711 => (Int -> a -> b -> c) -> v a -> v b -> v c
712 {-# INLINE izipWith #-}
713 izipWith f xs ys = unstream
714 (Stream.zipWith (uncurry f) (Stream.indexed (stream xs))
715 (stream ys))
716
717 -- | Zip three vectors and their indices with the given function.
718 izipWith3 :: (Vector v a, Vector v b, Vector v c, Vector v d)
719 => (Int -> a -> b -> c -> d) -> v a -> v b -> v c -> v d
720 {-# INLINE izipWith3 #-}
721 izipWith3 f as bs cs
722 = unstream (Stream.zipWith3 (uncurry f) (Stream.indexed (stream as))
723 (stream bs)
724 (stream cs))
725
726 izipWith4 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e)
727 => (Int -> a -> b -> c -> d -> e) -> v a -> v b -> v c -> v d -> v e
728 {-# INLINE izipWith4 #-}
729 izipWith4 f as bs cs ds
730 = unstream (Stream.zipWith4 (uncurry f) (Stream.indexed (stream as))
731 (stream bs)
732 (stream cs)
733 (stream ds))
734
735 izipWith5 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e,
736 Vector v f)
737 => (Int -> a -> b -> c -> d -> e -> f) -> v a -> v b -> v c -> v d
738 -> v e -> v f
739 {-# INLINE izipWith5 #-}
740 izipWith5 f as bs cs ds es
741 = unstream (Stream.zipWith5 (uncurry f) (Stream.indexed (stream as))
742 (stream bs)
743 (stream cs)
744 (stream ds)
745 (stream es))
746
747 izipWith6 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e,
748 Vector v f, Vector v g)
749 => (Int -> a -> b -> c -> d -> e -> f -> g)
750 -> v a -> v b -> v c -> v d -> v e -> v f -> v g
751 {-# INLINE izipWith6 #-}
752 izipWith6 f as bs cs ds es fs
753 = unstream (Stream.zipWith6 (uncurry f) (Stream.indexed (stream as))
754 (stream bs)
755 (stream cs)
756 (stream ds)
757 (stream es)
758 (stream fs))
759
760 zip :: (Vector v a, Vector v b, Vector v (a,b)) => v a -> v b -> v (a, b)
761 {-# INLINE zip #-}
762 zip = zipWith (,)
763
764 zip3 :: (Vector v a, Vector v b, Vector v c, Vector v (a, b, c))
765 => v a -> v b -> v c -> v (a, b, c)
766 {-# INLINE zip3 #-}
767 zip3 = zipWith3 (,,)
768
769 zip4 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v (a, b, c, d))
770 => v a -> v b -> v c -> v d -> v (a, b, c, d)
771 {-# INLINE zip4 #-}
772 zip4 = zipWith4 (,,,)
773
774 zip5 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e,
775 Vector v (a, b, c, d, e))
776 => v a -> v b -> v c -> v d -> v e -> v (a, b, c, d, e)
777 {-# INLINE zip5 #-}
778 zip5 = zipWith5 (,,,,)
779
780 zip6 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e,
781 Vector v f, Vector v (a, b, c, d, e, f))
782 => v a -> v b -> v c -> v d -> v e -> v f -> v (a, b, c, d, e, f)
783 {-# INLINE zip6 #-}
784 zip6 = zipWith6 (,,,,,)
785
786 unzip :: (Vector v a, Vector v b, Vector v (a,b)) => v (a, b) -> (v a, v b)
787 {-# INLINE unzip #-}
788 unzip xs = (map fst xs, map snd xs)
789
790 unzip3 :: (Vector v a, Vector v b, Vector v c, Vector v (a, b, c))
791 => v (a, b, c) -> (v a, v b, v c)
792 {-# INLINE unzip3 #-}
793 unzip3 xs = (map (\(a, b, c) -> a) xs,
794 map (\(a, b, c) -> b) xs,
795 map (\(a, b, c) -> c) xs)
796
797 unzip4 :: (Vector v a, Vector v b, Vector v c, Vector v d,
798 Vector v (a, b, c, d))
799 => v (a, b, c, d) -> (v a, v b, v c, v d)
800 {-# INLINE unzip4 #-}
801 unzip4 xs = (map (\(a, b, c, d) -> a) xs,
802 map (\(a, b, c, d) -> b) xs,
803 map (\(a, b, c, d) -> c) xs,
804 map (\(a, b, c, d) -> d) xs)
805
806 unzip5 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e,
807 Vector v (a, b, c, d, e))
808 => v (a, b, c, d, e) -> (v a, v b, v c, v d, v e)
809 {-# INLINE unzip5 #-}
810 unzip5 xs = (map (\(a, b, c, d, e) -> a) xs,
811 map (\(a, b, c, d, e) -> b) xs,
812 map (\(a, b, c, d, e) -> c) xs,
813 map (\(a, b, c, d, e) -> d) xs,
814 map (\(a, b, c, d, e) -> e) xs)
815
816 unzip6 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e,
817 Vector v f, Vector v (a, b, c, d, e, f))
818 => v (a, b, c, d, e, f) -> (v a, v b, v c, v d, v e, v f)
819 {-# INLINE unzip6 #-}
820 unzip6 xs = (map (\(a, b, c, d, e, f) -> a) xs,
821 map (\(a, b, c, d, e, f) -> b) xs,
822 map (\(a, b, c, d, e, f) -> c) xs,
823 map (\(a, b, c, d, e, f) -> d) xs,
824 map (\(a, b, c, d, e, f) -> e) xs,
825 map (\(a, b, c, d, e, f) -> f) xs)
826
827 -- Comparisons
828 -- -----------
829
830 eq :: (Vector v a, Eq a) => v a -> v a -> Bool
831 {-# INLINE eq #-}
832 xs `eq` ys = stream xs == stream ys
833
834 cmp :: (Vector v a, Ord a) => v a -> v a -> Ordering
835 {-# INLINE cmp #-}
836 cmp xs ys = compare (stream xs) (stream ys)
837
838 -- Filtering
839 -- ---------
840
841 -- | Drop elements that do not satisfy the predicate
842 filter :: Vector v a => (a -> Bool) -> v a -> v a
843 {-# INLINE filter #-}
844 filter f = unstream . inplace (MStream.filter f) . stream
845
846 -- | Drop elements that do not satisfy the predicate (applied to values and
847 -- their indices)
848 ifilter :: Vector v a => (Int -> a -> Bool) -> v a -> v a
849 {-# INLINE ifilter #-}
850 ifilter f = unstream
851 . inplace (MStream.map snd . MStream.filter (uncurry f)
852 . MStream.indexed)
853 . stream
854
855 -- | Yield the longest prefix of elements satisfying the predicate.
856 takeWhile :: Vector v a => (a -> Bool) -> v a -> v a
857 {-# INLINE takeWhile #-}
858 takeWhile f = unstream . Stream.takeWhile f . stream
859
860 -- | Drop the longest prefix of elements that satisfy the predicate.
861 dropWhile :: Vector v a => (a -> Bool) -> v a -> v a
862 {-# INLINE dropWhile #-}
863 dropWhile f = unstream . Stream.dropWhile f . stream
864
865 -- | Split the vector in two parts, the first one containing those elements
866 -- that satisfy the predicate and the second one those that don't. The
867 -- relative order of the elements is preserved at the cost of a (sometimes)
868 -- reduced performance compared to 'unstablePartition'.
869 partition :: Vector v a => (a -> Bool) -> v a -> (v a, v a)
870 {-# INLINE partition #-}
871 partition f = partition_stream f . stream
872
873 -- FIXME: Make this inplace-fusible (look at how stable_partition is
874 -- implemented in C++)
875
876 partition_stream :: Vector v a => (a -> Bool) -> Stream a -> (v a, v a)
877 {-# INLINE_STREAM partition_stream #-}
878 partition_stream f s = s `seq` runST (
879 do
880 (mv1,mv2) <- M.partitionStream f s
881 v1 <- unsafeFreeze mv1
882 v2 <- unsafeFreeze mv2
883 return (v1,v2))
884
885 -- | Split the vector in two parts, the first one containing those elements
886 -- that satisfy the predicate and the second one those that don't. The order
887 -- of the elements is not preserved but the operation is often faster than
888 -- 'partition'.
889 unstablePartition :: Vector v a => (a -> Bool) -> v a -> (v a, v a)
890 {-# INLINE unstablePartition #-}
891 unstablePartition f = unstablePartition_stream f . stream
892
893 unstablePartition_stream
894 :: Vector v a => (a -> Bool) -> Stream a -> (v a, v a)
895 {-# INLINE_STREAM unstablePartition_stream #-}
896 unstablePartition_stream f s = s `seq` runST (
897 do
898 (mv1,mv2) <- M.unstablePartitionStream f s
899 v1 <- unsafeFreeze mv1
900 v2 <- unsafeFreeze mv2
901 return (v1,v2))
902
903 unstablePartition_new :: Vector v a => (a -> Bool) -> New a -> (v a, v a)
904 {-# INLINE_STREAM unstablePartition_new #-}
905 unstablePartition_new f (New.New p) = runST (
906 do
907 mv <- p
908 i <- M.unstablePartition f mv
909 v <- unsafeFreeze mv
910 return (unsafeTake i v, unsafeDrop i v))
911
912 {-# RULES
913
914 "unstablePartition" forall f v p.
915 unstablePartition_stream f (stream (new' v p))
916 = unstablePartition_new f p
917
918 #-}
919
920
921 -- FIXME: make span and break fusible
922
923 -- | Split the vector into the longest prefix of elements that satisfy the
924 -- predicate and the rest.
925 span :: Vector v a => (a -> Bool) -> v a -> (v a, v a)
926 {-# INLINE span #-}
927 span f = break (not . f)
928
929 -- | Split the vector into the longest prefix of elements that do not satisfy
930 -- the predicate and the rest.
931 break :: Vector v a => (a -> Bool) -> v a -> (v a, v a)
932 {-# INLINE break #-}
933 break f xs = case findIndex f xs of
934 Just i -> (unsafeSlice 0 i xs, unsafeSlice i (length xs - i) xs)
935 Nothing -> (xs, empty)
936
937
938 -- Searching
939 -- ---------
940
941 infix 4 `elem`
942 -- | Check whether the vector contains an element
943 elem :: (Vector v a, Eq a) => a -> v a -> Bool
944 {-# INLINE elem #-}
945 elem x = Stream.elem x . stream
946
947 infix 4 `notElem`
948 -- | Inverse of `elem`
949 notElem :: (Vector v a, Eq a) => a -> v a -> Bool
950 {-# INLINE notElem #-}
951 notElem x = Stream.notElem x . stream
952
953 -- | Yield 'Just' the first element matching the predicate or 'Nothing' if no
954 -- such element exists.
955 find :: Vector v a => (a -> Bool) -> v a -> Maybe a
956 {-# INLINE find #-}
957 find f = Stream.find f . stream
958
959 -- | Yield 'Just' the index of the first element matching the predicate or
960 -- 'Nothing' if no such element exists.
961 findIndex :: Vector v a => (a -> Bool) -> v a -> Maybe Int
962 {-# INLINE findIndex #-}
963 findIndex f = Stream.findIndex f . stream
964
965 -- | Yield the indices of elements satisfying the predicate
966 findIndices :: (Vector v a, Vector v Int) => (a -> Bool) -> v a -> v Int
967 {-# INLINE findIndices #-}
968 findIndices f = unstream
969 . inplace (MStream.map fst . MStream.filter (f . snd)
970 . MStream.indexed)
971 . stream
972
973 -- | Yield 'Just' the index of the first occurence of the given element or
974 -- 'Nothing' if the vector does not contain the element
975 elemIndex :: (Vector v a, Eq a) => a -> v a -> Maybe Int
976 {-# INLINE elemIndex #-}
977 elemIndex x = findIndex (x==)
978
979 -- | Yield the indices of all occurences of the given element
980 elemIndices :: (Vector v a, Vector v Int, Eq a) => a -> v a -> v Int
981 {-# INLINE elemIndices #-}
982 elemIndices x = findIndices (x==)
983
984 -- Folding
985 -- -------
986
987 -- | Left fold
988 foldl :: Vector v b => (a -> b -> a) -> a -> v b -> a
989 {-# INLINE foldl #-}
990 foldl f z = Stream.foldl f z . stream
991
992 -- | Left fold on non-empty vectors
993 foldl1 :: Vector v a => (a -> a -> a) -> v a -> a
994 {-# INLINE foldl1 #-}
995 foldl1 f = Stream.foldl1 f . stream
996
997 -- | Left fold with strict accumulator
998 foldl' :: Vector v b => (a -> b -> a) -> a -> v b -> a
999 {-# INLINE foldl' #-}
1000 foldl' f z = Stream.foldl' f z . stream
1001
1002 -- | Left fold on non-empty vectors with strict accumulator
1003 foldl1' :: Vector v a => (a -> a -> a) -> v a -> a
1004 {-# INLINE foldl1' #-}
1005 foldl1' f = Stream.foldl1' f . stream
1006
1007 -- | Right fold
1008 foldr :: Vector v a => (a -> b -> b) -> b -> v a -> b
1009 {-# INLINE foldr #-}
1010 foldr f z = Stream.foldr f z . stream
1011
1012 -- | Right fold on non-empty vectors
1013 foldr1 :: Vector v a => (a -> a -> a) -> v a -> a
1014 {-# INLINE foldr1 #-}
1015 foldr1 f = Stream.foldr1 f . stream
1016
1017 -- | Right fold with a strict accumulator
1018 foldr' :: Vector v a => (a -> b -> b) -> b -> v a -> b
1019 {-# INLINE foldr' #-}
1020 foldr' f z = Stream.foldl' (flip f) z . streamR
1021
1022 -- | Right fold on non-empty vectors with strict accumulator
1023 foldr1' :: Vector v a => (a -> a -> a) -> v a -> a
1024 {-# INLINE foldr1' #-}
1025 foldr1' f = Stream.foldl1' (flip f) . streamR
1026
1027 -- | Left fold (function applied to each element and its index)
1028 ifoldl :: Vector v b => (a -> Int -> b -> a) -> a -> v b -> a
1029 {-# INLINE ifoldl #-}
1030 ifoldl f z = Stream.foldl (uncurry . f) z . Stream.indexed . stream
1031
1032 -- | Left fold with strict accumulator (function applied to each element and
1033 -- its index)
1034 ifoldl' :: Vector v b => (a -> Int -> b -> a) -> a -> v b -> a
1035 {-# INLINE ifoldl' #-}
1036 ifoldl' f z = Stream.foldl' (uncurry . f) z . Stream.indexed . stream
1037
1038 -- | Right fold (function applied to each element and its index)
1039 ifoldr :: Vector v a => (Int -> a -> b -> b) -> b -> v a -> b
1040 {-# INLINE ifoldr #-}
1041 ifoldr f z = Stream.foldr (uncurry f) z . Stream.indexed . stream
1042
1043 -- | Right fold with strict accumulator (function applied to each element and
1044 -- its index)
1045 ifoldr' :: Vector v a => (Int -> a -> b -> b) -> b -> v a -> b
1046 {-# INLINE ifoldr' #-}
1047 ifoldr' f z xs = Stream.foldl' (flip (uncurry f)) z
1048 $ Stream.indexedR (length xs) $ streamR xs
1049
1050 -- Specialised folds
1051 -- -----------------
1052
1053 all :: Vector v a => (a -> Bool) -> v a -> Bool
1054 {-# INLINE all #-}
1055 all f = Stream.and . Stream.map f . stream
1056
1057 any :: Vector v a => (a -> Bool) -> v a -> Bool
1058 {-# INLINE any #-}
1059 any f = Stream.or . Stream.map f . stream
1060
1061 and :: Vector v Bool => v Bool -> Bool
1062 {-# INLINE and #-}
1063 and = Stream.and . stream
1064
1065 or :: Vector v Bool => v Bool -> Bool
1066 {-# INLINE or #-}
1067 or = Stream.or . stream
1068
1069 sum :: (Vector v a, Num a) => v a -> a
1070 {-# INLINE sum #-}
1071 sum = Stream.foldl' (+) 0 . stream
1072
1073 product :: (Vector v a, Num a) => v a -> a
1074 {-# INLINE product #-}
1075 product = Stream.foldl' (*) 1 . stream
1076
1077 maximum :: (Vector v a, Ord a) => v a -> a
1078 {-# INLINE maximum #-}
1079 maximum = Stream.foldl1' max . stream
1080
1081 maximumBy :: Vector v a => (a -> a -> Ordering) -> v a -> a
1082 {-# INLINE maximumBy #-}
1083 maximumBy cmp = Stream.foldl1' maxBy . stream
1084 where
1085 {-# INLINE maxBy #-}
1086 maxBy x y = case cmp x y of
1087 LT -> y
1088 _ -> x
1089
1090 minimum :: (Vector v a, Ord a) => v a -> a
1091 {-# INLINE minimum #-}
1092 minimum = Stream.foldl1' min . stream
1093
1094 minimumBy :: Vector v a => (a -> a -> Ordering) -> v a -> a
1095 {-# INLINE minimumBy #-}
1096 minimumBy cmp = Stream.foldl1' minBy . stream
1097 where
1098 {-# INLINE minBy #-}
1099 minBy x y = case cmp x y of
1100 GT -> y
1101 _ -> x
1102
1103 maxIndex :: (Vector v a, Ord a) => v a -> Int
1104 {-# INLINE maxIndex #-}
1105 maxIndex = maxIndexBy compare
1106
1107 maxIndexBy :: Vector v a => (a -> a -> Ordering) -> v a -> Int
1108 {-# INLINE maxIndexBy #-}
1109 maxIndexBy cmp = fst . Stream.foldl1' imax . Stream.indexed . stream
1110 where
1111 imax (i,x) (j,y) = case cmp x y of
1112 LT -> (j,y)
1113 _ -> (i,x)
1114
1115 minIndex :: (Vector v a, Ord a) => v a -> Int
1116 {-# INLINE minIndex #-}
1117 minIndex = minIndexBy compare
1118
1119 minIndexBy :: Vector v a => (a -> a -> Ordering) -> v a -> Int
1120 {-# INLINE minIndexBy #-}
1121 minIndexBy cmp = fst . Stream.foldl1' imin . Stream.indexed . stream
1122 where
1123 imin (i,x) (j,y) = case cmp x y of
1124 GT -> (j,y)
1125 _ -> (i,x)
1126
1127
1128 -- Unfolding
1129 -- ---------
1130
1131 unfoldr :: Vector v a => (b -> Maybe (a, b)) -> b -> v a
1132 {-# INLINE unfoldr #-}
1133 unfoldr f = unstream . Stream.unfoldr f
1134
1135 -- Scans
1136 -- -----
1137
1138 -- | Prefix scan
1139 prescanl :: (Vector v a, Vector v b) => (a -> b -> a) -> a -> v b -> v a
1140 {-# INLINE prescanl #-}
1141 prescanl f z = unstream . inplace (MStream.prescanl f z) . stream
1142
1143 -- | Prefix scan with strict accumulator
1144 prescanl' :: (Vector v a, Vector v b) => (a -> b -> a) -> a -> v b -> v a
1145 {-# INLINE prescanl' #-}
1146 prescanl' f z = unstream . inplace (MStream.prescanl' f z) . stream
1147
1148 -- | Suffix scan
1149 postscanl :: (Vector v a, Vector v b) => (a -> b -> a) -> a -> v b -> v a
1150 {-# INLINE postscanl #-}
1151 postscanl f z = unstream . inplace (MStream.postscanl f z) . stream
1152
1153 -- | Suffix scan with strict accumulator
1154 postscanl' :: (Vector v a, Vector v b) => (a -> b -> a) -> a -> v b -> v a
1155 {-# INLINE postscanl' #-}
1156 postscanl' f z = unstream . inplace (MStream.postscanl' f z) . stream
1157
1158 -- | Haskell-style scan
1159 scanl :: (Vector v a, Vector v b) => (a -> b -> a) -> a -> v b -> v a
1160 {-# INLINE scanl #-}
1161 scanl f z = unstream . Stream.scanl f z . stream
1162
1163 -- | Haskell-style scan with strict accumulator
1164 scanl' :: (Vector v a, Vector v b) => (a -> b -> a) -> a -> v b -> v a
1165 {-# INLINE scanl' #-}
1166 scanl' f z = unstream . Stream.scanl' f z . stream
1167
1168 -- | Scan over a non-empty vector
1169 scanl1 :: Vector v a => (a -> a -> a) -> v a -> v a
1170 {-# INLINE scanl1 #-}
1171 scanl1 f = unstream . inplace (MStream.scanl1 f) . stream
1172
1173 -- | Scan over a non-empty vector with a strict accumulator
1174 scanl1' :: Vector v a => (a -> a -> a) -> v a -> v a
1175 {-# INLINE scanl1' #-}
1176 scanl1' f = unstream . inplace (MStream.scanl1' f) . stream
1177
1178
1179 -- | Prefix right-to-left scan
1180 prescanr :: (Vector v a, Vector v b) => (a -> b -> b) -> b -> v a -> v b
1181 {-# INLINE prescanr #-}
1182 prescanr f z = unstreamR . inplace (MStream.prescanl (flip f) z) . streamR
1183
1184 -- | Prefix right-to-left scan with strict accumulator
1185 prescanr' :: (Vector v a, Vector v b) => (a -> b -> b) -> b -> v a -> v b
1186 {-# INLINE prescanr' #-}
1187 prescanr' f z = unstreamR . inplace (MStream.prescanl' (flip f) z) . streamR
1188
1189 -- | Suffix right-to-left scan
1190 postscanr :: (Vector v a, Vector v b) => (a -> b -> b) -> b -> v a -> v b
1191 {-# INLINE postscanr #-}
1192 postscanr f z = unstreamR . inplace (MStream.postscanl (flip f) z) . streamR
1193
1194 -- | Suffix right-to-left scan with strict accumulator
1195 postscanr' :: (Vector v a, Vector v b) => (a -> b -> b) -> b -> v a -> v b
1196 {-# INLINE postscanr' #-}
1197 postscanr' f z = unstreamR . inplace (MStream.postscanl' (flip f) z) . streamR
1198
1199 -- | Haskell-style right-to-left scan
1200 scanr :: (Vector v a, Vector v b) => (a -> b -> b) -> b -> v a -> v b
1201 {-# INLINE scanr #-}
1202 scanr f z = unstreamR . Stream.scanl (flip f) z . streamR
1203
1204 -- | Haskell-style right-to-left scan with strict accumulator
1205 scanr' :: (Vector v a, Vector v b) => (a -> b -> b) -> b -> v a -> v b
1206 {-# INLINE scanr' #-}
1207 scanr' f z = unstreamR . Stream.scanl' (flip f) z . streamR
1208
1209 -- | Right-to-left scan over a non-empty vector
1210 scanr1 :: Vector v a => (a -> a -> a) -> v a -> v a
1211 {-# INLINE scanr1 #-}
1212 scanr1 f = unstreamR . inplace (MStream.scanl1 (flip f)) . streamR
1213
1214 -- | Right-to-left scan over a non-empty vector with a strict accumulator
1215 scanr1' :: Vector v a => (a -> a -> a) -> v a -> v a
1216 {-# INLINE scanr1' #-}
1217 scanr1' f = unstreamR . inplace (MStream.scanl1' (flip f)) . streamR
1218
1219 -- Enumeration
1220 -- -----------
1221
1222 enumFromTo :: (Vector v a, Enum a) => a -> a -> v a
1223 {-# INLINE enumFromTo #-}
1224 enumFromTo x y = unstream (Stream.enumFromTo x y)
1225
1226 enumFromThenTo :: (Vector v a, Enum a) => a -> a -> a -> v a
1227 {-# INLINE enumFromThenTo #-}
1228 enumFromThenTo x y z = unstream (Stream.enumFromThenTo x y z)
1229
1230 -- | Convert a vector to a list
1231 toList :: Vector v a => v a -> [a]
1232 {-# INLINE toList #-}
1233 toList = Stream.toList . stream
1234
1235 -- | Convert a list to a vector
1236 fromList :: Vector v a => [a] -> v a
1237 {-# INLINE fromList #-}
1238 fromList = unstream . Stream.fromList
1239