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