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