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