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