50e9e7e6d81cbc016d29d9f1386b3656f76b69cb
[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-2010
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, (++), force,
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, copy, unsafeCopy,
93
94 -- * Utilities for defining Data instances
95 gfoldl, dataCast, mkType
96 ) where
97
98 import Data.Vector.Generic.Base
99
100 import Data.Vector.Generic.Mutable ( MVector )
101 import qualified Data.Vector.Generic.Mutable as M
102
103 import qualified Data.Vector.Generic.New as New
104 import Data.Vector.Generic.New ( New )
105
106 import qualified Data.Vector.Fusion.Stream as Stream
107 import Data.Vector.Fusion.Stream ( Stream, MStream, inplace )
108 import qualified Data.Vector.Fusion.Stream.Monadic as MStream
109 import Data.Vector.Fusion.Stream.Size
110 import Data.Vector.Fusion.Util
111
112 import Control.Monad.ST ( ST, runST )
113 import Control.Monad.Primitive
114 import Prelude hiding ( length, null,
115 replicate, (++),
116 head, last,
117 init, tail, take, drop, reverse,
118 map, concatMap,
119 zipWith, zipWith3, zip, zip3, unzip, unzip3,
120 filter, takeWhile, dropWhile, span, break,
121 elem, notElem,
122 foldl, foldl1, foldr, foldr1,
123 all, any, and, or, sum, product, maximum, minimum,
124 scanl, scanl1, scanr, scanr1,
125 enumFromTo, enumFromThenTo )
126
127 import Data.Typeable ( Typeable1, gcast1 )
128 import Data.Data ( Data, DataType, mkNorepType )
129
130 #include "vector.h"
131
132 -- Fusion
133 -- ------
134
135 -- | Construct a pure vector from a monadic initialiser
136 new :: Vector v a => New v a -> v a
137 {-# INLINE_STREAM new #-}
138 new m = m `seq` runST (unsafeFreeze =<< New.run m)
139
140 clone :: Vector v a => v a -> New v a
141 {-# INLINE_STREAM clone #-}
142 clone v = v `seq` New.create (
143 do
144 mv <- M.new (length v)
145 unsafeCopy mv v
146 return mv)
147
148 -- | Convert a vector to a 'Stream'
149 stream :: Vector v a => v a -> Stream a
150 {-# INLINE_STREAM stream #-}
151 stream v = v `seq` (Stream.unfoldr get 0 `Stream.sized` Exact n)
152 where
153 n = length v
154
155 -- NOTE: the False case comes first in Core so making it the recursive one
156 -- makes the code easier to read
157 {-# INLINE get #-}
158 get i | i >= n = Nothing
159 | otherwise = case basicUnsafeIndexM v i of Box x -> Just (x, i+1)
160
161 -- | Create a vector from a 'Stream'
162 unstream :: Vector v a => Stream a -> v a
163 {-# INLINE unstream #-}
164 unstream s = new (New.unstream s)
165
166 {-# RULES
167
168 "stream/unstream [Vector]" forall s.
169 stream (new (New.unstream s)) = s
170
171 "New.unstream/stream [Vector]" forall v.
172 New.unstream (stream v) = clone v
173
174 "clone/new [Vector]" forall p.
175 clone (new p) = p
176
177 #-}
178
179 {-# RULES
180
181 "inplace [Vector]"
182 forall (f :: forall m. Monad m => MStream m a -> MStream m a) m.
183 New.unstream (inplace f (stream (new m))) = New.transform f m
184
185 "uninplace [Vector]"
186 forall (f :: forall m. Monad m => MStream m a -> MStream m a) m.
187 stream (new (New.transform f m)) = inplace f (stream (new m))
188
189 #-}
190
191 -- | Convert a vector to a 'Stream'
192 streamR :: Vector v a => v a -> Stream a
193 {-# INLINE_STREAM streamR #-}
194 streamR v = v `seq` (Stream.unfoldr get n `Stream.sized` Exact n)
195 where
196 n = length v
197
198 {-# INLINE get #-}
199 get 0 = Nothing
200 get i = let i' = i-1
201 in
202 case basicUnsafeIndexM v i' of Box x -> Just (x, i')
203
204 -- | Create a vector from a 'Stream'
205 unstreamR :: Vector v a => Stream a -> v a
206 {-# INLINE unstreamR #-}
207 unstreamR s = new (New.unstreamR s)
208
209 {-# RULES
210
211 "streamR/unstreamR [Vector]" forall s.
212 streamR (new (New.unstreamR s)) = s
213
214 "New.unstreamR/streamR/new [Vector]" forall p.
215 New.unstreamR (streamR (new p)) = p
216
217 #-}
218
219 {-# RULES
220
221 "inplace [Vector]"
222 forall (f :: forall m. Monad m => MStream m a -> MStream m a) m.
223 New.unstreamR (inplace f (streamR (new m))) = New.transformR f m
224
225 "uninplace [Vector]"
226 forall (f :: forall m. Monad m => MStream m a -> MStream m a) m.
227 streamR (new (New.transformR f m)) = inplace f (streamR (new m))
228
229 #-}
230
231 -- | Copy an immutable vector into a mutable one. The two vectors must have
232 -- the same length. This is not checked.
233 unsafeCopy
234 :: (PrimMonad m, Vector v a) => Mutable v (PrimState m) a -> v a -> m ()
235 {-# INLINE unsafeCopy #-}
236 unsafeCopy dst src = UNSAFE_CHECK(check) "unsafeCopy" "length mismatch"
237 (M.length dst == length src)
238 $ (dst `seq` src `seq` basicUnsafeCopy dst src)
239
240 -- | Copy an immutable vector into a mutale one. The two vectors must have the
241 -- same length.
242 copy
243 :: (PrimMonad m, Vector v a) => Mutable v (PrimState m) a -> v a -> m ()
244 {-# INLINE copy #-}
245 copy dst src = BOUNDS_CHECK(check) "copy" "length mismatch"
246 (M.length dst == length src)
247 $ unsafeCopy dst src
248
249 modify :: Vector v a => (forall mv s. MVector mv a => mv s a -> ST s ())
250 -> v a -> v a
251 {-# INLINE_STREAM modify #-}
252 modify p v = runST (
253 do
254 mv <- M.unsafeNew (length v)
255 unsafeCopy mv v
256 p mv
257 unsafeFreeze mv)
258
259 {-# RULES
260
261 "modify/new [Vector]"
262 forall (f :: forall mv s. MVector mv a => mv s a -> ST s ()) m.
263 modify f (new m) = new (New.modify f m)
264
265 #-}
266
267 -- Length
268 -- ------
269
270 length :: Vector v a => v a -> Int
271 {-# INLINE_STREAM length #-}
272 length v = basicLength v
273
274 {-# RULES
275
276 "length/unstream [Vector]" forall s.
277 length (new (New.unstream s)) = Stream.length s
278
279 #-}
280
281 null :: Vector v a => v a -> Bool
282 {-# INLINE_STREAM null #-}
283 null v = basicLength v == 0
284
285 {-# RULES
286
287 "null/unstream [Vector]" forall s.
288 null (new (New.unstream s)) = Stream.null s
289
290 #-}
291
292 -- Construction
293 -- ------------
294
295 -- | Empty vector
296 empty :: Vector v a => v a
297 {-# INLINE empty #-}
298 empty = unstream Stream.empty
299
300 -- | Vector with exaclty one element
301 singleton :: forall v a. Vector v a => a -> v a
302 {-# INLINE singleton #-}
303 singleton x = elemseq (undefined :: v a) x
304 $ unstream (Stream.singleton x)
305
306 -- | Vector of the given length with the given value in each position
307 replicate :: forall v a. Vector v a => Int -> a -> v a
308 {-# INLINE replicate #-}
309 replicate n x = elemseq (undefined :: v a) x
310 $ unstream
311 $ Stream.replicate n x
312
313 -- | Generate a vector of the given length by applying the function to each
314 -- index
315 generate :: Vector v a => Int -> (Int -> a) -> v a
316 {-# INLINE generate #-}
317 generate n f = unstream (Stream.generate n f)
318
319 -- | Prepend an element
320 cons :: forall v a. Vector v a => a -> v a -> v a
321 {-# INLINE cons #-}
322 cons x v = elemseq (undefined :: v a) x
323 $ unstream
324 $ Stream.cons x
325 $ stream v
326
327 -- | Append an element
328 snoc :: forall v a. Vector v a => v a -> a -> v a
329 {-# INLINE snoc #-}
330 snoc v x = elemseq (undefined :: v a) x
331 $ unstream
332 $ Stream.snoc (stream v) x
333
334 infixr 5 ++
335 -- | Concatenate two vectors
336 (++) :: Vector v a => v a -> v a -> v a
337 {-# INLINE (++) #-}
338 v ++ w = unstream (stream v Stream.++ stream w)
339
340 -- | Create a copy of a vector. Useful when dealing with slices.
341 force :: Vector v a => v a -> v a
342 {-# INLINE_STREAM force #-}
343 force v = new (clone v)
344
345 {-# RULES
346
347 "force/unstream [Vector]" forall s.
348 force (new (New.unstream s)) = new (New.unstream s)
349
350 #-}
351
352 -- Accessing individual elements
353 -- -----------------------------
354
355 -- | Indexing
356 (!) :: Vector v a => v a -> Int -> a
357 {-# INLINE_STREAM (!) #-}
358 v ! i = BOUNDS_CHECK(checkIndex) "(!)" i (length v)
359 $ unId (basicUnsafeIndexM v i)
360
361 -- | First element
362 head :: Vector v a => v a -> a
363 {-# INLINE_STREAM head #-}
364 head v = v ! 0
365
366 -- | Last element
367 last :: Vector v a => v a -> a
368 {-# INLINE_STREAM last #-}
369 last v = v ! (length v - 1)
370
371 -- | Unsafe indexing without bounds checking
372 unsafeIndex :: Vector v a => v a -> Int -> a
373 {-# INLINE_STREAM unsafeIndex #-}
374 unsafeIndex v i = UNSAFE_CHECK(checkIndex) "unsafeIndex" i (length v)
375 $ unId (basicUnsafeIndexM v i)
376
377 -- | Yield the first element of a vector without checking if the vector is
378 -- empty
379 unsafeHead :: Vector v a => v a -> a
380 {-# INLINE_STREAM unsafeHead #-}
381 unsafeHead v = unsafeIndex v 0
382
383 -- | Yield the last element of a vector without checking if the vector is
384 -- empty
385 unsafeLast :: Vector v a => v a -> a
386 {-# INLINE_STREAM unsafeLast #-}
387 unsafeLast v = unsafeIndex v (length v - 1)
388
389 {-# RULES
390
391 "(!)/unstream [Vector]" forall i s.
392 new (New.unstream s) ! i = s Stream.!! i
393
394 "head/unstream [Vector]" forall s.
395 head (new (New.unstream s)) = Stream.head s
396
397 "last/unstream [Vector]" forall s.
398 last (new (New.unstream s)) = Stream.last s
399
400 "unsafeIndex/unstream [Vector]" forall i s.
401 unsafeIndex (new (New.unstream s)) i = s Stream.!! i
402
403 "unsafeHead/unstream [Vector]" forall s.
404 unsafeHead (new (New.unstream s)) = Stream.head s
405
406 "unsafeLast/unstream [Vector]" forall s.
407 unsafeLast (new (New.unstream s)) = Stream.last s
408
409 #-}
410
411 -- | Monadic indexing which can be strict in the vector while remaining lazy in
412 -- the element.
413 indexM :: (Vector v a, Monad m) => v a -> Int -> m a
414 {-# INLINE_STREAM indexM #-}
415 indexM v i = BOUNDS_CHECK(checkIndex) "indexM" i (length v)
416 $ basicUnsafeIndexM v i
417
418 headM :: (Vector v a, Monad m) => v a -> m a
419 {-# INLINE_STREAM headM #-}
420 headM v = indexM v 0
421
422 lastM :: (Vector v a, Monad m) => v a -> m a
423 {-# INLINE_STREAM lastM #-}
424 lastM v = indexM v (length v - 1)
425
426 -- | Unsafe monadic indexing without bounds checks
427 unsafeIndexM :: (Vector v a, Monad m) => v a -> Int -> m a
428 {-# INLINE_STREAM unsafeIndexM #-}
429 unsafeIndexM v i = UNSAFE_CHECK(checkIndex) "unsafeIndexM" i (length v)
430 $ basicUnsafeIndexM v i
431
432 unsafeHeadM :: (Vector v a, Monad m) => v a -> m a
433 {-# INLINE_STREAM unsafeHeadM #-}
434 unsafeHeadM v = unsafeIndexM v 0
435
436 unsafeLastM :: (Vector v a, Monad m) => v a -> m a
437 {-# INLINE_STREAM unsafeLastM #-}
438 unsafeLastM v = unsafeIndexM v (length v - 1)
439
440 -- FIXME: the rhs of these rules are lazy in the stream which is WRONG
441 {- RULES
442
443 "indexM/unstream [Vector]" forall v i s.
444 indexM (new' v (New.unstream s)) i = return (s Stream.!! i)
445
446 "headM/unstream [Vector]" forall v s.
447 headM (new' v (New.unstream s)) = return (Stream.head s)
448
449 "lastM/unstream [Vector]" forall v s.
450 lastM (new' v (New.unstream s)) = return (Stream.last s)
451
452 -}
453
454 -- Subarrays
455 -- ---------
456
457 -- FIXME: slicing doesn't work with the inplace stuff at the moment
458
459 -- | Yield a part of the vector without copying it.
460 slice :: Vector v a => Int -- ^ starting index
461 -> Int -- ^ length
462 -> v a
463 -> v a
464 {-# INLINE_STREAM slice #-}
465 slice i n v = BOUNDS_CHECK(checkSlice) "slice" i n (length v)
466 $ basicUnsafeSlice i n v
467
468 -- | Yield all but the last element without copying.
469 init :: Vector v a => v a -> v a
470 {-# INLINE_STREAM init #-}
471 init v = slice 0 (length v - 1) v
472
473 -- | All but the first element (without copying).
474 tail :: Vector v a => v a -> v a
475 {-# INLINE_STREAM tail #-}
476 tail v = slice 1 (length v - 1) v
477
478 -- | Yield the first @n@ elements without copying.
479 take :: Vector v a => Int -> v a -> v a
480 {-# INLINE_STREAM take #-}
481 take n v = unsafeSlice 0 (delay_inline min n' (length v)) v
482 where n' = max n 0
483
484 -- | Yield all but the first @n@ elements without copying.
485 drop :: Vector v a => Int -> v a -> v a
486 {-# INLINE_STREAM drop #-}
487 drop n v = unsafeSlice (delay_inline min n' len)
488 (delay_inline max 0 (len - n')) v
489 where n' = max n 0
490 len = length v
491
492 -- | Unsafely yield a part of the vector without copying it and without
493 -- performing bounds checks.
494 unsafeSlice :: Vector v a => Int -- ^ starting index
495 -> Int -- ^ length
496 -> v a
497 -> v a
498 {-# INLINE_STREAM unsafeSlice #-}
499 unsafeSlice i n v = UNSAFE_CHECK(checkSlice) "unsafeSlice" i n (length v)
500 $ basicUnsafeSlice i n v
501
502 unsafeInit :: Vector v a => v a -> v a
503 {-# INLINE_STREAM unsafeInit #-}
504 unsafeInit v = unsafeSlice 0 (length v - 1) v
505
506 unsafeTail :: Vector v a => v a -> v a
507 {-# INLINE_STREAM unsafeTail #-}
508 unsafeTail v = unsafeSlice 1 (length v - 1) v
509
510 unsafeTake :: Vector v a => Int -> v a -> v a
511 {-# INLINE unsafeTake #-}
512 unsafeTake n v = unsafeSlice 0 n v
513
514 unsafeDrop :: Vector v a => Int -> v a -> v a
515 {-# INLINE unsafeDrop #-}
516 unsafeDrop n v = unsafeSlice n (length v - n) v
517
518 {-# RULES
519
520 "slice/new [Vector]" forall i n p.
521 slice i n (new p) = new (New.slice i n p)
522
523 "init/new [Vector]" forall p.
524 init (new p) = new (New.init p)
525
526 "tail/new [Vector]" forall p.
527 tail (new p) = new (New.tail p)
528
529 "take/new [Vector]" forall n p.
530 take n (new p) = new (New.take n p)
531
532 "drop/new [Vector]" forall n p.
533 drop n (new p) = new (New.drop n p)
534
535 "unsafeSlice/new [Vector]" forall i n p.
536 unsafeSlice i n (new p) = new (New.unsafeSlice i n p)
537
538 "unsafeInit/new [Vector]" forall p.
539 unsafeInit (new p) = new (New.unsafeInit p)
540
541 "unsafeTail/new [Vector]" forall p.
542 unsafeTail (new p) = new (New.unsafeTail p)
543
544 #-}
545
546 -- Permutations
547 -- ------------
548
549 unsafeAccum_stream
550 :: Vector v a => (a -> b -> a) -> v a -> Stream (Int,b) -> v a
551 {-# INLINE unsafeAccum_stream #-}
552 unsafeAccum_stream f v s = new (New.accum f (clone v) s)
553
554 unsafeAccum :: Vector v a => (a -> b -> a) -> v a -> [(Int,b)] -> v a
555 {-# INLINE unsafeAccum #-}
556 unsafeAccum f v us = unsafeAccum_stream f v (Stream.fromList us)
557
558 unsafeAccumulate :: (Vector v a, Vector v (Int, b))
559 => (a -> b -> a) -> v a -> v (Int,b) -> v a
560 {-# INLINE unsafeAccumulate #-}
561 unsafeAccumulate f v us = unsafeAccum_stream f v (stream us)
562
563 unsafeAccumulate_ :: (Vector v a, Vector v Int, Vector v b)
564 => (a -> b -> a) -> v a -> v Int -> v b -> v a
565 {-# INLINE unsafeAccumulate_ #-}
566 unsafeAccumulate_ f v is xs
567 = unsafeAccum_stream f v (Stream.zipWith (,) (stream is) (stream xs))
568
569 accum_stream :: Vector v a => (a -> b -> a) -> v a -> Stream (Int,b) -> v a
570 {-# INLINE accum_stream #-}
571 accum_stream f v s = new (New.accum f (clone v) s)
572
573 accum :: Vector v a => (a -> b -> a) -> v a -> [(Int,b)] -> v a
574 {-# INLINE accum #-}
575 accum f v us = accum_stream f v (Stream.fromList us)
576
577 accumulate :: (Vector v a, Vector v (Int, b))
578 => (a -> b -> a) -> v a -> v (Int,b) -> v a
579 {-# INLINE accumulate #-}
580 accumulate f v us = accum_stream f v (stream us)
581
582 accumulate_ :: (Vector v a, Vector v Int, Vector v b)
583 => (a -> b -> a) -> v a -> v Int -> v b -> v a
584 {-# INLINE accumulate_ #-}
585 accumulate_ f v is xs = accum_stream f v (Stream.zipWith (,) (stream is)
586 (stream xs))
587
588
589 unsafeUpdate_stream :: Vector v a => v a -> Stream (Int,a) -> v a
590 {-# INLINE unsafeUpdate_stream #-}
591 unsafeUpdate_stream v s = new (New.unsafeUpdate (clone v) s)
592
593 unsafeUpd :: Vector v a => v a -> [(Int, a)] -> v a
594 {-# INLINE unsafeUpd #-}
595 unsafeUpd v us = unsafeUpdate_stream v (Stream.fromList us)
596
597 unsafeUpdate :: (Vector v a, Vector v (Int, a)) => v a -> v (Int, a) -> v a
598 {-# INLINE unsafeUpdate #-}
599 unsafeUpdate v w = unsafeUpdate_stream v (stream w)
600
601 unsafeUpdate_ :: (Vector v a, Vector v Int) => v a -> v Int -> v a -> v a
602 {-# INLINE unsafeUpdate_ #-}
603 unsafeUpdate_ v is w
604 = unsafeUpdate_stream v (Stream.zipWith (,) (stream is) (stream w))
605
606 update_stream :: Vector v a => v a -> Stream (Int,a) -> v a
607 {-# INLINE update_stream #-}
608 update_stream v s = new (New.update (clone v) s)
609
610 (//) :: Vector v a => v a -> [(Int, a)] -> v a
611 {-# INLINE (//) #-}
612 v // us = update_stream v (Stream.fromList us)
613
614 update :: (Vector v a, Vector v (Int, a)) => v a -> v (Int, a) -> v a
615 {-# INLINE update #-}
616 update v w = update_stream v (stream w)
617
618 update_ :: (Vector v a, Vector v Int) => v a -> v Int -> v a -> v a
619 {-# INLINE update_ #-}
620 update_ v is w = update_stream v (Stream.zipWith (,) (stream is) (stream w))
621
622 -- This somewhat non-intuitive definition ensures that the resulting vector
623 -- does not retain references to the original one even if it is lazy in its
624 -- elements. This would not be the case if we simply used
625 --
626 -- backpermute v is = map (v!) is
627 backpermute :: (Vector v a, Vector v Int) => v a -> v Int -> v a
628 {-# INLINE backpermute #-}
629 backpermute v is = seq v
630 $ unstream
631 $ Stream.unbox
632 $ Stream.map (indexM v)
633 $ stream is
634
635 unsafeBackpermute :: (Vector v a, Vector v Int) => v a -> v Int -> v a
636 {-# INLINE unsafeBackpermute #-}
637 unsafeBackpermute v is = seq v
638 $ unstream
639 $ Stream.unbox
640 $ Stream.map (unsafeIndexM v)
641 $ stream is
642
643 -- FIXME: make this fuse better, add support for recycling
644 reverse :: (Vector v a) => v a -> v a
645 {-# INLINE reverse #-}
646 reverse = unstream . streamR
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 v 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 p.
923 unstablePartition_stream f (stream (new 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 -- | Unfold
1140 unfoldr :: Vector v a => (b -> Maybe (a, b)) -> b -> v a
1141 {-# INLINE unfoldr #-}
1142 unfoldr f = unstream . Stream.unfoldr f
1143
1144 -- | Unfoldr at most @n@ elements.
1145 unfoldrN :: Vector v a => Int -> (b -> Maybe (a, b)) -> b -> v a
1146 {-# INLINE unfoldrN #-}
1147 unfoldrN n f = unstream . Stream.unfoldrN n f
1148
1149 -- Scans
1150 -- -----
1151
1152 -- | Prefix scan
1153 prescanl :: (Vector v a, Vector v b) => (a -> b -> a) -> a -> v b -> v a
1154 {-# INLINE prescanl #-}
1155 prescanl f z = unstream . inplace (MStream.prescanl f z) . stream
1156
1157 -- | Prefix scan with strict accumulator
1158 prescanl' :: (Vector v a, Vector v b) => (a -> b -> a) -> a -> v b -> v a
1159 {-# INLINE prescanl' #-}
1160 prescanl' f z = unstream . inplace (MStream.prescanl' f z) . stream
1161
1162 -- | Suffix scan
1163 postscanl :: (Vector v a, Vector v b) => (a -> b -> a) -> a -> v b -> v a
1164 {-# INLINE postscanl #-}
1165 postscanl f z = unstream . inplace (MStream.postscanl f z) . stream
1166
1167 -- | Suffix scan with strict accumulator
1168 postscanl' :: (Vector v a, Vector v b) => (a -> b -> a) -> a -> v b -> v a
1169 {-# INLINE postscanl' #-}
1170 postscanl' f z = unstream . inplace (MStream.postscanl' f z) . stream
1171
1172 -- | Haskell-style scan
1173 scanl :: (Vector v a, Vector v b) => (a -> b -> a) -> a -> v b -> v a
1174 {-# INLINE scanl #-}
1175 scanl f z = unstream . Stream.scanl f z . stream
1176
1177 -- | Haskell-style scan with strict accumulator
1178 scanl' :: (Vector v a, Vector v b) => (a -> b -> a) -> a -> v b -> v a
1179 {-# INLINE scanl' #-}
1180 scanl' f z = unstream . Stream.scanl' f z . stream
1181
1182 -- | Scan over a non-empty vector
1183 scanl1 :: Vector v a => (a -> a -> a) -> v a -> v a
1184 {-# INLINE scanl1 #-}
1185 scanl1 f = unstream . inplace (MStream.scanl1 f) . stream
1186
1187 -- | Scan over a non-empty vector with a strict accumulator
1188 scanl1' :: Vector v a => (a -> a -> a) -> v a -> v a
1189 {-# INLINE scanl1' #-}
1190 scanl1' f = unstream . inplace (MStream.scanl1' f) . stream
1191
1192
1193 -- | Prefix right-to-left scan
1194 prescanr :: (Vector v a, Vector v b) => (a -> b -> b) -> b -> v a -> v b
1195 {-# INLINE prescanr #-}
1196 prescanr f z = unstreamR . inplace (MStream.prescanl (flip f) z) . streamR
1197
1198 -- | Prefix right-to-left scan with strict accumulator
1199 prescanr' :: (Vector v a, Vector v b) => (a -> b -> b) -> b -> v a -> v b
1200 {-# INLINE prescanr' #-}
1201 prescanr' f z = unstreamR . inplace (MStream.prescanl' (flip f) z) . streamR
1202
1203 -- | Suffix right-to-left scan
1204 postscanr :: (Vector v a, Vector v b) => (a -> b -> b) -> b -> v a -> v b
1205 {-# INLINE postscanr #-}
1206 postscanr f z = unstreamR . inplace (MStream.postscanl (flip f) z) . streamR
1207
1208 -- | Suffix right-to-left scan with strict accumulator
1209 postscanr' :: (Vector v a, Vector v b) => (a -> b -> b) -> b -> v a -> v b
1210 {-# INLINE postscanr' #-}
1211 postscanr' f z = unstreamR . inplace (MStream.postscanl' (flip f) z) . streamR
1212
1213 -- | Haskell-style right-to-left scan
1214 scanr :: (Vector v a, Vector v b) => (a -> b -> b) -> b -> v a -> v b
1215 {-# INLINE scanr #-}
1216 scanr f z = unstreamR . Stream.scanl (flip f) z . streamR
1217
1218 -- | Haskell-style right-to-left scan with strict accumulator
1219 scanr' :: (Vector v a, Vector v b) => (a -> b -> b) -> b -> v a -> v b
1220 {-# INLINE scanr' #-}
1221 scanr' f z = unstreamR . Stream.scanl' (flip f) z . streamR
1222
1223 -- | Right-to-left scan over a non-empty vector
1224 scanr1 :: Vector v a => (a -> a -> a) -> v a -> v a
1225 {-# INLINE scanr1 #-}
1226 scanr1 f = unstreamR . inplace (MStream.scanl1 (flip f)) . streamR
1227
1228 -- | Right-to-left scan over a non-empty vector with a strict accumulator
1229 scanr1' :: Vector v a => (a -> a -> a) -> v a -> v a
1230 {-# INLINE scanr1' #-}
1231 scanr1' f = unstreamR . inplace (MStream.scanl1' (flip f)) . streamR
1232
1233 -- Enumeration
1234 -- -----------
1235
1236 -- | Yield a vector of the given length containing the values @x@, @x+1@ etc.
1237 -- This operation is usually more efficient than 'enumFromTo'.
1238 enumFromN :: (Vector v a, Num a) => a -> Int -> v a
1239 {-# INLINE enumFromN #-}
1240 enumFromN x n = enumFromStepN x 1 n
1241
1242 -- | Yield a vector of the given length containing the values @x@, @x+y@,
1243 -- @x+y+y@ etc. This operations is usually more efficient than
1244 -- 'enumFromThenTo'.
1245 enumFromStepN :: forall v a. (Vector v a, Num a) => a -> a -> Int -> v a
1246 {-# INLINE enumFromStepN #-}
1247 enumFromStepN x y n = elemseq (undefined :: v a) x
1248 $ elemseq (undefined :: v a) y
1249 $ unstream
1250 $ Stream.enumFromStepN x y n
1251
1252 -- | Enumerate values from @x@ to @y@.
1253 --
1254 -- /WARNING:/ This operation can be very inefficient. If at all possible, use
1255 -- 'enumFromN' instead.
1256 enumFromTo :: (Vector v a, Enum a) => a -> a -> v a
1257 {-# INLINE enumFromTo #-}
1258 enumFromTo x y = unstream (Stream.enumFromTo x y)
1259
1260 -- | Enumerate values from @x@ to @y@ with a specific step @z@.
1261 --
1262 -- /WARNING:/ This operation can be very inefficient. If at all possible, use
1263 -- 'enumFromStepN' instead.
1264 enumFromThenTo :: (Vector v a, Enum a) => a -> a -> a -> v a
1265 {-# INLINE enumFromThenTo #-}
1266 enumFromThenTo x y z = unstream (Stream.enumFromThenTo x y z)
1267
1268 -- | Convert a vector to a list
1269 toList :: Vector v a => v a -> [a]
1270 {-# INLINE toList #-}
1271 toList = Stream.toList . stream
1272
1273 -- | Convert a list to a vector
1274 fromList :: Vector v a => [a] -> v a
1275 {-# INLINE fromList #-}
1276 fromList = unstream . Stream.fromList
1277
1278 -- | Convert the first @n@ elements of a list to a vector
1279 --
1280 -- > fromListN n xs = fromList (take n xs)
1281 fromListN :: Vector v a => Int -> [a] -> v a
1282 {-# INLINE fromListN #-}
1283 fromListN n = unstream . Stream.fromListN n
1284
1285 -- Utilities for defining Data instances
1286 -- -------------------------------------
1287
1288 -- | Generic definion of 'Data.Data.gfoldl' that views a 'Vector' as a
1289 -- list.
1290 gfoldl :: (Vector v a, Data a)
1291 => (forall d b. Data d => c (d -> b) -> d -> c b)
1292 -> (forall g. g -> c g)
1293 -> v a
1294 -> c (v a)
1295 {-# INLINE gfoldl #-}
1296 gfoldl f z v = z fromList `f` toList v
1297
1298 mkType :: String -> DataType
1299 {-# INLINE mkType #-}
1300 mkType = mkNorepType
1301
1302 dataCast :: (Vector v a, Data a, Typeable1 v, Typeable1 t)
1303 => (forall d. Data d => c (t d)) -> Maybe (c (v a))
1304 {-# INLINE dataCast #-}
1305 dataCast f = gcast1 f
1306