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