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