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