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