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