Remove 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 reverse :: (Vector v a) => v a -> v a
643 {-# INLINE reverse #-}
644 reverse = unstream . streamR
645
646 -- Mapping
647 -- -------
648
649 -- | Map a function over a vector
650 map :: (Vector v a, Vector v b) => (a -> b) -> v a -> v b
651 {-# INLINE map #-}
652 map f = unstream . inplace (MStream.map f) . stream
653
654 -- | Apply a function to every index/value pair
655 imap :: (Vector v a, Vector v b) => (Int -> a -> b) -> v a -> v b
656 {-# INLINE imap #-}
657 imap f = unstream . inplace (MStream.map (uncurry f) . MStream.indexed)
658 . stream
659
660 concatMap :: (Vector v a, Vector v b) => (a -> v b) -> v a -> v b
661 {-# INLINE concatMap #-}
662 concatMap f = unstream . Stream.concatMap (stream . f) . stream
663
664 -- Zipping/unzipping
665 -- -----------------
666
667 -- | Zip two vectors with the given function.
668 zipWith :: (Vector v a, Vector v b, Vector v c)
669 => (a -> b -> c) -> v a -> v b -> v c
670 {-# INLINE zipWith #-}
671 zipWith f xs ys = unstream (Stream.zipWith f (stream xs) (stream ys))
672
673 -- | Zip three vectors with the given function.
674 zipWith3 :: (Vector v a, Vector v b, Vector v c, Vector v d)
675 => (a -> b -> c -> d) -> v a -> v b -> v c -> v d
676 {-# INLINE zipWith3 #-}
677 zipWith3 f as bs cs = unstream (Stream.zipWith3 f (stream as)
678 (stream bs)
679 (stream cs))
680
681 zipWith4 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e)
682 => (a -> b -> c -> d -> e) -> v a -> v b -> v c -> v d -> v e
683 {-# INLINE zipWith4 #-}
684 zipWith4 f as bs cs ds
685 = unstream (Stream.zipWith4 f (stream as)
686 (stream bs)
687 (stream cs)
688 (stream ds))
689
690 zipWith5 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e,
691 Vector v f)
692 => (a -> b -> c -> d -> e -> f) -> v a -> v b -> v c -> v d -> v e
693 -> v f
694 {-# INLINE zipWith5 #-}
695 zipWith5 f as bs cs ds es
696 = unstream (Stream.zipWith5 f (stream as)
697 (stream bs)
698 (stream cs)
699 (stream ds)
700 (stream es))
701
702 zipWith6 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e,
703 Vector v f, Vector v g)
704 => (a -> b -> c -> d -> e -> f -> g)
705 -> v a -> v b -> v c -> v d -> v e -> v f -> v g
706 {-# INLINE zipWith6 #-}
707 zipWith6 f as bs cs ds es fs
708 = unstream (Stream.zipWith6 f (stream as)
709 (stream bs)
710 (stream cs)
711 (stream ds)
712 (stream es)
713 (stream fs))
714
715 -- | Zip two vectors and their indices with the given function.
716 izipWith :: (Vector v a, Vector v b, Vector v c)
717 => (Int -> a -> b -> c) -> v a -> v b -> v c
718 {-# INLINE izipWith #-}
719 izipWith f xs ys = unstream
720 (Stream.zipWith (uncurry f) (Stream.indexed (stream xs))
721 (stream ys))
722
723 -- | Zip three vectors and their indices with the given function.
724 izipWith3 :: (Vector v a, Vector v b, Vector v c, Vector v d)
725 => (Int -> a -> b -> c -> d) -> v a -> v b -> v c -> v d
726 {-# INLINE izipWith3 #-}
727 izipWith3 f as bs cs
728 = unstream (Stream.zipWith3 (uncurry f) (Stream.indexed (stream as))
729 (stream bs)
730 (stream cs))
731
732 izipWith4 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e)
733 => (Int -> a -> b -> c -> d -> e) -> v a -> v b -> v c -> v d -> v e
734 {-# INLINE izipWith4 #-}
735 izipWith4 f as bs cs ds
736 = unstream (Stream.zipWith4 (uncurry f) (Stream.indexed (stream as))
737 (stream bs)
738 (stream cs)
739 (stream ds))
740
741 izipWith5 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e,
742 Vector v f)
743 => (Int -> a -> b -> c -> d -> e -> f) -> v a -> v b -> v c -> v d
744 -> v e -> v f
745 {-# INLINE izipWith5 #-}
746 izipWith5 f as bs cs ds es
747 = unstream (Stream.zipWith5 (uncurry f) (Stream.indexed (stream as))
748 (stream bs)
749 (stream cs)
750 (stream ds)
751 (stream es))
752
753 izipWith6 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e,
754 Vector v f, Vector v g)
755 => (Int -> a -> b -> c -> d -> e -> f -> g)
756 -> v a -> v b -> v c -> v d -> v e -> v f -> v g
757 {-# INLINE izipWith6 #-}
758 izipWith6 f as bs cs ds es fs
759 = unstream (Stream.zipWith6 (uncurry f) (Stream.indexed (stream as))
760 (stream bs)
761 (stream cs)
762 (stream ds)
763 (stream es)
764 (stream fs))
765
766 zip :: (Vector v a, Vector v b, Vector v (a,b)) => v a -> v b -> v (a, b)
767 {-# INLINE zip #-}
768 zip = zipWith (,)
769
770 zip3 :: (Vector v a, Vector v b, Vector v c, Vector v (a, b, c))
771 => v a -> v b -> v c -> v (a, b, c)
772 {-# INLINE zip3 #-}
773 zip3 = zipWith3 (,,)
774
775 zip4 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v (a, b, c, d))
776 => v a -> v b -> v c -> v d -> v (a, b, c, d)
777 {-# INLINE zip4 #-}
778 zip4 = zipWith4 (,,,)
779
780 zip5 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e,
781 Vector v (a, b, c, d, e))
782 => v a -> v b -> v c -> v d -> v e -> v (a, b, c, d, e)
783 {-# INLINE zip5 #-}
784 zip5 = zipWith5 (,,,,)
785
786 zip6 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e,
787 Vector v f, Vector v (a, b, c, d, e, f))
788 => v a -> v b -> v c -> v d -> v e -> v f -> v (a, b, c, d, e, f)
789 {-# INLINE zip6 #-}
790 zip6 = zipWith6 (,,,,,)
791
792 unzip :: (Vector v a, Vector v b, Vector v (a,b)) => v (a, b) -> (v a, v b)
793 {-# INLINE unzip #-}
794 unzip xs = (map fst xs, map snd xs)
795
796 unzip3 :: (Vector v a, Vector v b, Vector v c, Vector v (a, b, c))
797 => v (a, b, c) -> (v a, v b, v c)
798 {-# INLINE unzip3 #-}
799 unzip3 xs = (map (\(a, b, c) -> a) xs,
800 map (\(a, b, c) -> b) xs,
801 map (\(a, b, c) -> c) xs)
802
803 unzip4 :: (Vector v a, Vector v b, Vector v c, Vector v d,
804 Vector v (a, b, c, d))
805 => v (a, b, c, d) -> (v a, v b, v c, v d)
806 {-# INLINE unzip4 #-}
807 unzip4 xs = (map (\(a, b, c, d) -> a) xs,
808 map (\(a, b, c, d) -> b) xs,
809 map (\(a, b, c, d) -> c) xs,
810 map (\(a, b, c, d) -> d) xs)
811
812 unzip5 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e,
813 Vector v (a, b, c, d, e))
814 => v (a, b, c, d, e) -> (v a, v b, v c, v d, v e)
815 {-# INLINE unzip5 #-}
816 unzip5 xs = (map (\(a, b, c, d, e) -> a) xs,
817 map (\(a, b, c, d, e) -> b) xs,
818 map (\(a, b, c, d, e) -> c) xs,
819 map (\(a, b, c, d, e) -> d) xs,
820 map (\(a, b, c, d, e) -> e) xs)
821
822 unzip6 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e,
823 Vector v f, Vector v (a, b, c, d, e, f))
824 => v (a, b, c, d, e, f) -> (v a, v b, v c, v d, v e, v f)
825 {-# INLINE unzip6 #-}
826 unzip6 xs = (map (\(a, b, c, d, e, f) -> a) xs,
827 map (\(a, b, c, d, e, f) -> b) xs,
828 map (\(a, b, c, d, e, f) -> c) xs,
829 map (\(a, b, c, d, e, f) -> d) xs,
830 map (\(a, b, c, d, e, f) -> e) xs,
831 map (\(a, b, c, d, e, f) -> f) xs)
832
833 -- Comparisons
834 -- -----------
835
836 eq :: (Vector v a, Eq a) => v a -> v a -> Bool
837 {-# INLINE eq #-}
838 xs `eq` ys = stream xs == stream ys
839
840 cmp :: (Vector v a, Ord a) => v a -> v a -> Ordering
841 {-# INLINE cmp #-}
842 cmp xs ys = compare (stream xs) (stream ys)
843
844 -- Filtering
845 -- ---------
846
847 -- | Drop elements that do not satisfy the predicate
848 filter :: Vector v a => (a -> Bool) -> v a -> v a
849 {-# INLINE filter #-}
850 filter f = unstream . inplace (MStream.filter f) . stream
851
852 -- | Drop elements that do not satisfy the predicate (applied to values and
853 -- their indices)
854 ifilter :: Vector v a => (Int -> a -> Bool) -> v a -> v a
855 {-# INLINE ifilter #-}
856 ifilter f = unstream
857 . inplace (MStream.map snd . MStream.filter (uncurry f)
858 . MStream.indexed)
859 . stream
860
861 -- | Yield the longest prefix of elements satisfying the predicate.
862 takeWhile :: Vector v a => (a -> Bool) -> v a -> v a
863 {-# INLINE takeWhile #-}
864 takeWhile f = unstream . Stream.takeWhile f . stream
865
866 -- | Drop the longest prefix of elements that satisfy the predicate.
867 dropWhile :: Vector v a => (a -> Bool) -> v a -> v a
868 {-# INLINE dropWhile #-}
869 dropWhile f = unstream . Stream.dropWhile f . stream
870
871 -- | Split the vector in two parts, the first one containing those elements
872 -- that satisfy the predicate and the second one those that don't. The
873 -- relative order of the elements is preserved at the cost of a (sometimes)
874 -- reduced performance compared to 'unstablePartition'.
875 partition :: Vector v a => (a -> Bool) -> v a -> (v a, v a)
876 {-# INLINE partition #-}
877 partition f = partition_stream f . stream
878
879 -- FIXME: Make this inplace-fusible (look at how stable_partition is
880 -- implemented in C++)
881
882 partition_stream :: Vector v a => (a -> Bool) -> Stream a -> (v a, v a)
883 {-# INLINE_STREAM partition_stream #-}
884 partition_stream f s = s `seq` runST (
885 do
886 (mv1,mv2) <- M.partitionStream f s
887 v1 <- unsafeFreeze mv1
888 v2 <- unsafeFreeze mv2
889 return (v1,v2))
890
891 -- | Split the vector in two parts, the first one containing those elements
892 -- that satisfy the predicate and the second one those that don't. The order
893 -- of the elements is not preserved but the operation is often faster than
894 -- 'partition'.
895 unstablePartition :: Vector v a => (a -> Bool) -> v a -> (v a, v a)
896 {-# INLINE unstablePartition #-}
897 unstablePartition f = unstablePartition_stream f . stream
898
899 unstablePartition_stream
900 :: Vector v a => (a -> Bool) -> Stream a -> (v a, v a)
901 {-# INLINE_STREAM unstablePartition_stream #-}
902 unstablePartition_stream f s = s `seq` runST (
903 do
904 (mv1,mv2) <- M.unstablePartitionStream f s
905 v1 <- unsafeFreeze mv1
906 v2 <- unsafeFreeze mv2
907 return (v1,v2))
908
909 unstablePartition_new :: Vector v a => (a -> Bool) -> New a -> (v a, v a)
910 {-# INLINE_STREAM unstablePartition_new #-}
911 unstablePartition_new f (New.New p) = runST (
912 do
913 mv <- p
914 i <- M.unstablePartition f mv
915 v <- unsafeFreeze mv
916 return (unsafeTake i v, unsafeDrop i v))
917
918 {-# RULES
919
920 "unstablePartition" forall f v p.
921 unstablePartition_stream f (stream (new' v p))
922 = unstablePartition_new f p
923
924 #-}
925
926
927 -- FIXME: make span and break fusible
928
929 -- | Split the vector into the longest prefix of elements that satisfy the
930 -- predicate and the rest.
931 span :: Vector v a => (a -> Bool) -> v a -> (v a, v a)
932 {-# INLINE span #-}
933 span f = break (not . f)
934
935 -- | Split the vector into the longest prefix of elements that do not satisfy
936 -- the predicate and the rest.
937 break :: Vector v a => (a -> Bool) -> v a -> (v a, v a)
938 {-# INLINE break #-}
939 break f xs = case findIndex f xs of
940 Just i -> (unsafeSlice 0 i xs, unsafeSlice i (length xs - i) xs)
941 Nothing -> (xs, empty)
942
943
944 -- Searching
945 -- ---------
946
947 infix 4 `elem`
948 -- | Check whether the vector contains an element
949 elem :: (Vector v a, Eq a) => a -> v a -> Bool
950 {-# INLINE elem #-}
951 elem x = Stream.elem x . stream
952
953 infix 4 `notElem`
954 -- | Inverse of `elem`
955 notElem :: (Vector v a, Eq a) => a -> v a -> Bool
956 {-# INLINE notElem #-}
957 notElem x = Stream.notElem x . stream
958
959 -- | Yield 'Just' the first element matching the predicate or 'Nothing' if no
960 -- such element exists.
961 find :: Vector v a => (a -> Bool) -> v a -> Maybe a
962 {-# INLINE find #-}
963 find f = Stream.find f . stream
964
965 -- | Yield 'Just' the index of the first element matching the predicate or
966 -- 'Nothing' if no such element exists.
967 findIndex :: Vector v a => (a -> Bool) -> v a -> Maybe Int
968 {-# INLINE findIndex #-}
969 findIndex f = Stream.findIndex f . stream
970
971 -- | Yield the indices of elements satisfying the predicate
972 findIndices :: (Vector v a, Vector v Int) => (a -> Bool) -> v a -> v Int
973 {-# INLINE findIndices #-}
974 findIndices f = unstream
975 . inplace (MStream.map fst . MStream.filter (f . snd)
976 . MStream.indexed)
977 . stream
978
979 -- | Yield 'Just' the index of the first occurence of the given element or
980 -- 'Nothing' if the vector does not contain the element
981 elemIndex :: (Vector v a, Eq a) => a -> v a -> Maybe Int
982 {-# INLINE elemIndex #-}
983 elemIndex x = findIndex (x==)
984
985 -- | Yield the indices of all occurences of the given element
986 elemIndices :: (Vector v a, Vector v Int, Eq a) => a -> v a -> v Int
987 {-# INLINE elemIndices #-}
988 elemIndices x = findIndices (x==)
989
990 -- Folding
991 -- -------
992
993 -- | Left fold
994 foldl :: Vector v b => (a -> b -> a) -> a -> v b -> a
995 {-# INLINE foldl #-}
996 foldl f z = Stream.foldl f z . stream
997
998 -- | Left fold on non-empty vectors
999 foldl1 :: Vector v a => (a -> a -> a) -> v a -> a
1000 {-# INLINE foldl1 #-}
1001 foldl1 f = Stream.foldl1 f . stream
1002
1003 -- | Left fold with strict accumulator
1004 foldl' :: Vector v b => (a -> b -> a) -> a -> v b -> a
1005 {-# INLINE foldl' #-}
1006 foldl' f z = Stream.foldl' f z . stream
1007
1008 -- | Left fold on non-empty vectors with strict accumulator
1009 foldl1' :: Vector v a => (a -> a -> a) -> v a -> a
1010 {-# INLINE foldl1' #-}
1011 foldl1' f = Stream.foldl1' f . stream
1012
1013 -- | Right fold
1014 foldr :: Vector v a => (a -> b -> b) -> b -> v a -> b
1015 {-# INLINE foldr #-}
1016 foldr f z = Stream.foldr f z . stream
1017
1018 -- | Right fold on non-empty vectors
1019 foldr1 :: Vector v a => (a -> a -> a) -> v a -> a
1020 {-# INLINE foldr1 #-}
1021 foldr1 f = Stream.foldr1 f . stream
1022
1023 -- | Right fold with a strict accumulator
1024 foldr' :: Vector v a => (a -> b -> b) -> b -> v a -> b
1025 {-# INLINE foldr' #-}
1026 foldr' f z = Stream.foldl' (flip f) z . streamR
1027
1028 -- | Right fold on non-empty vectors with strict accumulator
1029 foldr1' :: Vector v a => (a -> a -> a) -> v a -> a
1030 {-# INLINE foldr1' #-}
1031 foldr1' f = Stream.foldl1' (flip f) . streamR
1032
1033 -- | Left fold (function applied to each element and 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 -- | Left fold with strict accumulator (function applied to each element and
1039 -- its index)
1040 ifoldl' :: Vector v b => (a -> Int -> b -> a) -> a -> v b -> a
1041 {-# INLINE ifoldl' #-}
1042 ifoldl' f z = Stream.foldl' (uncurry . f) z . Stream.indexed . stream
1043
1044 -- | Right fold (function applied to each element and its index)
1045 ifoldr :: Vector v a => (Int -> a -> b -> b) -> b -> v a -> b
1046 {-# INLINE ifoldr #-}
1047 ifoldr f z = Stream.foldr (uncurry f) z . Stream.indexed . stream
1048
1049 -- | Right fold with strict accumulator (function applied to each element and
1050 -- its index)
1051 ifoldr' :: Vector v a => (Int -> a -> b -> b) -> b -> v a -> b
1052 {-# INLINE ifoldr' #-}
1053 ifoldr' f z xs = Stream.foldl' (flip (uncurry f)) z
1054 $ Stream.indexedR (length xs) $ streamR xs
1055
1056 -- Specialised folds
1057 -- -----------------
1058
1059 all :: Vector v a => (a -> Bool) -> v a -> Bool
1060 {-# INLINE all #-}
1061 all f = Stream.and . Stream.map f . stream
1062
1063 any :: Vector v a => (a -> Bool) -> v a -> Bool
1064 {-# INLINE any #-}
1065 any f = Stream.or . Stream.map f . stream
1066
1067 and :: Vector v Bool => v Bool -> Bool
1068 {-# INLINE and #-}
1069 and = Stream.and . stream
1070
1071 or :: Vector v Bool => v Bool -> Bool
1072 {-# INLINE or #-}
1073 or = Stream.or . stream
1074
1075 sum :: (Vector v a, Num a) => v a -> a
1076 {-# INLINE sum #-}
1077 sum = Stream.foldl' (+) 0 . stream
1078
1079 product :: (Vector v a, Num a) => v a -> a
1080 {-# INLINE product #-}
1081 product = Stream.foldl' (*) 1 . stream
1082
1083 maximum :: (Vector v a, Ord a) => v a -> a
1084 {-# INLINE maximum #-}
1085 maximum = Stream.foldl1' max . stream
1086
1087 maximumBy :: Vector v a => (a -> a -> Ordering) -> v a -> a
1088 {-# INLINE maximumBy #-}
1089 maximumBy cmp = Stream.foldl1' maxBy . stream
1090 where
1091 {-# INLINE maxBy #-}
1092 maxBy x y = case cmp x y of
1093 LT -> y
1094 _ -> x
1095
1096 minimum :: (Vector v a, Ord a) => v a -> a
1097 {-# INLINE minimum #-}
1098 minimum = Stream.foldl1' min . stream
1099
1100 minimumBy :: Vector v a => (a -> a -> Ordering) -> v a -> a
1101 {-# INLINE minimumBy #-}
1102 minimumBy cmp = Stream.foldl1' minBy . stream
1103 where
1104 {-# INLINE minBy #-}
1105 minBy x y = case cmp x y of
1106 GT -> y
1107 _ -> x
1108
1109 maxIndex :: (Vector v a, Ord a) => v a -> Int
1110 {-# INLINE maxIndex #-}
1111 maxIndex = maxIndexBy compare
1112
1113 maxIndexBy :: Vector v a => (a -> a -> Ordering) -> v a -> Int
1114 {-# INLINE maxIndexBy #-}
1115 maxIndexBy cmp = fst . Stream.foldl1' imax . Stream.indexed . stream
1116 where
1117 imax (i,x) (j,y) = case cmp x y of
1118 LT -> (j,y)
1119 _ -> (i,x)
1120
1121 minIndex :: (Vector v a, Ord a) => v a -> Int
1122 {-# INLINE minIndex #-}
1123 minIndex = minIndexBy compare
1124
1125 minIndexBy :: Vector v a => (a -> a -> Ordering) -> v a -> Int
1126 {-# INLINE minIndexBy #-}
1127 minIndexBy cmp = fst . Stream.foldl1' imin . Stream.indexed . stream
1128 where
1129 imin (i,x) (j,y) = case cmp x y of
1130 GT -> (j,y)
1131 _ -> (i,x)
1132
1133
1134 -- Unfolding
1135 -- ---------
1136
1137 -- | Unfold
1138 unfoldr :: Vector v a => (b -> Maybe (a, b)) -> b -> v a
1139 {-# INLINE unfoldr #-}
1140 unfoldr f = unstream . Stream.unfoldr f
1141
1142 -- | Unfoldr at most @n@ elements.
1143 unfoldrN :: Vector v a => Int -> (b -> Maybe (a, b)) -> b -> v a
1144 {-# INLINE unfoldrN #-}
1145 unfoldrN n f = unstream . Stream.unfoldrN n f
1146
1147 -- Scans
1148 -- -----
1149
1150 -- | Prefix scan
1151 prescanl :: (Vector v a, Vector v b) => (a -> b -> a) -> a -> v b -> v a
1152 {-# INLINE prescanl #-}
1153 prescanl f z = unstream . inplace (MStream.prescanl f z) . stream
1154
1155 -- | Prefix scan with strict accumulator
1156 prescanl' :: (Vector v a, Vector v b) => (a -> b -> a) -> a -> v b -> v a
1157 {-# INLINE prescanl' #-}
1158 prescanl' f z = unstream . inplace (MStream.prescanl' f z) . stream
1159
1160 -- | Suffix scan
1161 postscanl :: (Vector v a, Vector v b) => (a -> b -> a) -> a -> v b -> v a
1162 {-# INLINE postscanl #-}
1163 postscanl f z = unstream . inplace (MStream.postscanl f z) . stream
1164
1165 -- | Suffix scan with strict accumulator
1166 postscanl' :: (Vector v a, Vector v b) => (a -> b -> a) -> a -> v b -> v a
1167 {-# INLINE postscanl' #-}
1168 postscanl' f z = unstream . inplace (MStream.postscanl' f z) . stream
1169
1170 -- | Haskell-style scan
1171 scanl :: (Vector v a, Vector v b) => (a -> b -> a) -> a -> v b -> v a
1172 {-# INLINE scanl #-}
1173 scanl f z = unstream . Stream.scanl f z . stream
1174
1175 -- | Haskell-style scan with strict accumulator
1176 scanl' :: (Vector v a, Vector v b) => (a -> b -> a) -> a -> v b -> v a
1177 {-# INLINE scanl' #-}
1178 scanl' f z = unstream . Stream.scanl' f z . stream
1179
1180 -- | Scan over a non-empty vector
1181 scanl1 :: Vector v a => (a -> a -> a) -> v a -> v a
1182 {-# INLINE scanl1 #-}
1183 scanl1 f = unstream . inplace (MStream.scanl1 f) . stream
1184
1185 -- | Scan over a non-empty vector with a strict accumulator
1186 scanl1' :: Vector v a => (a -> a -> a) -> v a -> v a
1187 {-# INLINE scanl1' #-}
1188 scanl1' f = unstream . inplace (MStream.scanl1' f) . stream
1189
1190
1191 -- | Prefix right-to-left scan
1192 prescanr :: (Vector v a, Vector v b) => (a -> b -> b) -> b -> v a -> v b
1193 {-# INLINE prescanr #-}
1194 prescanr f z = unstreamR . inplace (MStream.prescanl (flip f) z) . streamR
1195
1196 -- | Prefix right-to-left scan with strict accumulator
1197 prescanr' :: (Vector v a, Vector v b) => (a -> b -> b) -> b -> v a -> v b
1198 {-# INLINE prescanr' #-}
1199 prescanr' f z = unstreamR . inplace (MStream.prescanl' (flip f) z) . streamR
1200
1201 -- | Suffix right-to-left scan
1202 postscanr :: (Vector v a, Vector v b) => (a -> b -> b) -> b -> v a -> v b
1203 {-# INLINE postscanr #-}
1204 postscanr f z = unstreamR . inplace (MStream.postscanl (flip f) z) . streamR
1205
1206 -- | Suffix right-to-left scan with strict accumulator
1207 postscanr' :: (Vector v a, Vector v b) => (a -> b -> b) -> b -> v a -> v b
1208 {-# INLINE postscanr' #-}
1209 postscanr' f z = unstreamR . inplace (MStream.postscanl' (flip f) z) . streamR
1210
1211 -- | Haskell-style right-to-left scan
1212 scanr :: (Vector v a, Vector v b) => (a -> b -> b) -> b -> v a -> v b
1213 {-# INLINE scanr #-}
1214 scanr f z = unstreamR . Stream.scanl (flip f) z . streamR
1215
1216 -- | Haskell-style right-to-left scan with strict accumulator
1217 scanr' :: (Vector v a, Vector v b) => (a -> b -> b) -> b -> v a -> v b
1218 {-# INLINE scanr' #-}
1219 scanr' f z = unstreamR . Stream.scanl' (flip f) z . streamR
1220
1221 -- | Right-to-left scan over a non-empty vector
1222 scanr1 :: Vector v a => (a -> a -> a) -> v a -> v a
1223 {-# INLINE scanr1 #-}
1224 scanr1 f = unstreamR . inplace (MStream.scanl1 (flip f)) . streamR
1225
1226 -- | Right-to-left scan over a non-empty vector with a strict accumulator
1227 scanr1' :: Vector v a => (a -> a -> a) -> v a -> v a
1228 {-# INLINE scanr1' #-}
1229 scanr1' f = unstreamR . inplace (MStream.scanl1' (flip f)) . streamR
1230
1231 -- Enumeration
1232 -- -----------
1233
1234 -- | Yield a vector of the given length containing the values @x@, @x+1@ etc.
1235 -- This operation is usually more efficient than 'enumFromTo'.
1236 enumFromN :: (Vector v a, Num a) => a -> Int -> v a
1237 {-# INLINE enumFromN #-}
1238 enumFromN x n = enumFromStepN x 1 n
1239
1240 -- | Yield a vector of the given length containing the values @x@, @x+y@,
1241 -- @x+y+y@ etc. This operations is usually more efficient than
1242 -- 'enumFromThenTo'.
1243 enumFromStepN :: forall v a. (Vector v a, Num a) => a -> a -> Int -> v a
1244 {-# INLINE enumFromStepN #-}
1245 enumFromStepN x y n = elemseq (undefined :: v a) x
1246 $ elemseq (undefined :: v a) y
1247 $ unstream
1248 $ Stream.enumFromStepN x y n
1249
1250 -- | Enumerate values from @x@ to @y@.
1251 --
1252 -- /WARNING:/ This operation can be very inefficient. If at all possible, use
1253 -- 'enumFromN' instead.
1254 enumFromTo :: (Vector v a, Enum a) => a -> a -> v a
1255 {-# INLINE enumFromTo #-}
1256 enumFromTo x y = unstream (Stream.enumFromTo x y)
1257
1258 -- | Enumerate values from @x@ to @y@ with a specific step @z@.
1259 --
1260 -- /WARNING:/ This operation can be very inefficient. If at all possible, use
1261 -- 'enumFromStepN' instead.
1262 enumFromThenTo :: (Vector v a, Enum a) => a -> a -> a -> v a
1263 {-# INLINE enumFromThenTo #-}
1264 enumFromThenTo x y z = unstream (Stream.enumFromThenTo x y z)
1265
1266 -- | Convert a vector to a list
1267 toList :: Vector v a => v a -> [a]
1268 {-# INLINE toList #-}
1269 toList = Stream.toList . stream
1270
1271 -- | Convert a list to a vector
1272 fromList :: Vector v a => [a] -> v a
1273 {-# INLINE fromList #-}
1274 fromList = unstream . Stream.fromList
1275
1276 -- | Convert the first @n@ elements of a list to a vector
1277 --
1278 -- > fromListN n xs = fromList (take n xs)
1279 fromListN :: Vector v a => Int -> [a] -> v a
1280 {-# INLINE fromListN #-}
1281 fromListN n = unstream . Stream.fromListN n
1282