Add generate
[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-2009
6 -- License : BSD-style
7 --
8 -- Maintainer : Roman Leshchinskiy <rl@cse.unsw.edu.au>
9 -- Stability : experimental
10 -- Portability : non-portable
11 --
12 -- Generic interface to pure vectors
13 --
14
15 module Data.Vector.Generic (
16 -- * Immutable vectors
17 Vector(..), Mutable,
18
19 -- * Length information
20 length, null,
21
22 -- * Construction
23 empty, singleton, cons, snoc, replicate, generate, (++), copy,
24
25 -- * Accessing individual elements
26 (!), head, last, indexM, headM, lastM,
27
28 -- * Subvectors
29 slice, init, tail, take, drop,
30 unsafeSlice,
31
32 -- * Permutations
33 accum, accumulate, accumulate_,
34 (//), update, update_,
35 backpermute, reverse,
36
37 -- * Mapping
38 map, imap, concatMap,
39
40 -- * Zipping and unzipping
41 zipWith, zipWith3, zipWith4, zipWith5, zipWith6,
42 izipWith, izipWith3, izipWith4, izipWith5, izipWith6,
43 zip, zip3, zip4, zip5, zip6,
44 unzip, unzip3, unzip4, unzip5, unzip6,
45
46 -- * Comparisons
47 eq, cmp,
48
49 -- * Filtering
50 filter, ifilter, takeWhile, dropWhile,
51
52 -- * Searching
53 elem, notElem, find, findIndex, findIndices, elemIndex, elemIndices,
54
55 -- * Folding
56 foldl, foldl1, foldl', foldl1', foldr, foldr1,
57 ifoldl, ifoldl', ifoldr,
58
59 -- * Specialised folds
60 all, any, and, or,
61 sum, product,
62 maximum, maximumBy, minimum, minimumBy,
63 minIndex, minIndexBy, maxIndex, maxIndexBy,
64
65 -- * Unfolding
66 unfoldr,
67
68 -- * Scans
69 prescanl, prescanl',
70 postscanl, postscanl',
71 scanl, scanl', scanl1, scanl1',
72
73 -- * Enumeration
74 enumFromTo, enumFromThenTo,
75
76 -- * Conversion to/from lists
77 toList, fromList,
78
79 -- * Conversion to/from Streams
80 stream, unstream,
81
82 -- * MVector-based initialisation
83 new,
84
85 -- * Unsafe operations
86 unsafeIndex, unsafeIndexM,
87 unsafeAccum, unsafeAccumulate, unsafeAccumulate_,
88 unsafeUpd, unsafeUpdate, unsafeUpdate_
89 ) where
90
91 import Data.Vector.Generic.Mutable ( MVector )
92
93 import qualified Data.Vector.Generic.New as New
94 import Data.Vector.Generic.New ( New )
95
96 import qualified Data.Vector.Fusion.Stream as Stream
97 import Data.Vector.Fusion.Stream ( Stream, MStream, inplace )
98 import qualified Data.Vector.Fusion.Stream.Monadic as MStream
99 import Data.Vector.Fusion.Stream.Size
100 import Data.Vector.Fusion.Util
101
102 import Control.Monad.ST ( runST )
103 import Control.Monad.Primitive
104 import Prelude hiding ( length, null,
105 replicate, (++),
106 head, last,
107 init, tail, take, drop, reverse,
108 map, concatMap,
109 zipWith, zipWith3, zip, zip3, unzip, unzip3,
110 filter, takeWhile, dropWhile,
111 elem, notElem,
112 foldl, foldl1, foldr, foldr1,
113 all, any, and, or, sum, product, maximum, minimum,
114 scanl, scanl1,
115 enumFromTo, enumFromThenTo )
116
117 #include "vector.h"
118
119 type family Mutable (v :: * -> *) :: * -> * -> *
120
121 -- | Class of immutable vectors.
122 --
123 class MVector (Mutable v) a => Vector v a where
124 -- | Unsafely convert a mutable vector to its immutable version
125 -- without copying. The mutable vector may not be used after
126 -- this operation.
127 unsafeFreeze :: PrimMonad m => Mutable v (PrimState m) a -> m (v a)
128
129 -- | Length of the vector (not fusible!)
130 basicLength :: v a -> Int
131
132 -- | Yield a part of the vector without copying it. No range checks!
133 basicUnsafeSlice :: v a -> Int -> Int -> v a
134
135 -- | Yield the element at the given position in a monad. The monad allows us
136 -- to be strict in the vector if we want. Suppose we had
137 --
138 -- > unsafeIndex :: v a -> Int -> a
139 --
140 -- instead. Now, if we wanted to copy a vector, we'd do something like
141 --
142 -- > copy mv v ... = ... unsafeWrite mv i (unsafeIndex v i) ...
143 --
144 -- For lazy vectors, the indexing would not be evaluated which means that we
145 -- would retain a reference to the original vector in each element we write.
146 -- This is not what we want!
147 --
148 -- With 'basicUnsafeIndexM', we can do
149 --
150 -- > copy mv v ... = ... case basicUnsafeIndexM v i of
151 -- > Box x -> unsafeWrite mv i x ...
152 --
153 -- which does not have this problem because indexing (but not the returned
154 -- element!) is evaluated immediately.
155 --
156 basicUnsafeIndexM :: Monad m => v a -> Int -> m a
157
158 elemseq :: v a -> a -> b -> b
159
160 {-# INLINE elemseq #-}
161 elemseq _ = \_ x -> x
162
163 -- Fusion
164 -- ------
165
166 -- | Construct a pure vector from a monadic initialiser
167 new :: Vector v a => New a -> v a
168 {-# INLINE new #-}
169 new m = new' undefined m
170
171 -- | Same as 'new' but with a dummy argument necessary for correctly typing
172 -- the rule @uninplace@.
173 --
174 -- See http://hackage.haskell.org/trac/ghc/ticket/2600
175 new' :: Vector v a => v a -> New a -> v a
176 {-# INLINE_STREAM new' #-}
177 new' _ m = m `seq` runST (do
178 mv <- New.run m
179 unsafeFreeze mv)
180
181 -- | Convert a vector to a 'Stream'
182 stream :: Vector v a => v a -> Stream a
183 {-# INLINE_STREAM stream #-}
184 stream v = v `seq` (Stream.unfoldr get 0 `Stream.sized` Exact n)
185 where
186 n = length v
187
188 -- NOTE: the False case comes first in Core so making it the recursive one
189 -- makes the code easier to read
190 {-# INLINE get #-}
191 get i | i >= n = Nothing
192 | otherwise = case basicUnsafeIndexM v i of Box x -> Just (x, i+1)
193
194 -- | Create a vector from a 'Stream'
195 unstream :: Vector v a => Stream a -> v a
196 {-# INLINE unstream #-}
197 unstream s = new (New.unstream s)
198
199 {-# RULES
200
201 "stream/unstream [Vector]" forall v s.
202 stream (new' v (New.unstream s)) = s
203
204 "New.unstream/stream/new [Vector]" forall v p.
205 New.unstream (stream (new' v p)) = p
206
207 #-}
208
209 {-# RULES
210
211 "inplace [Vector]"
212 forall (f :: forall m. Monad m => MStream m a -> MStream m a) v m.
213 New.unstream (inplace f (stream (new' v m))) = New.transform f m
214
215 "uninplace [Vector]"
216 forall (f :: forall m. Monad m => MStream m a -> MStream m a) v m.
217 stream (new' v (New.transform f m)) = inplace f (stream (new' v m))
218
219 #-}
220
221 -- Length
222 -- ------
223
224 length :: Vector v a => v a -> Int
225 {-# INLINE_STREAM length #-}
226 length v = basicLength v
227
228 {-# RULES
229
230 "length/unstream [Vector]" forall v s.
231 length (new' v (New.unstream s)) = Stream.length s
232
233 #-}
234
235 null :: Vector v a => v a -> Bool
236 {-# INLINE null #-}
237 null v = length v == 0
238
239 -- Construction
240 -- ------------
241
242 -- | Empty vector
243 empty :: Vector v a => v a
244 {-# INLINE empty #-}
245 empty = unstream Stream.empty
246
247 -- | Vector with exaclty one element
248 singleton :: forall v a. Vector v a => a -> v a
249 {-# INLINE singleton #-}
250 singleton x = elemseq (undefined :: v a) x
251 $ unstream (Stream.singleton x)
252
253 -- | Vector of the given length with the given value in each position
254 replicate :: forall v a. Vector v a => Int -> a -> v a
255 {-# INLINE replicate #-}
256 replicate n x = elemseq (undefined :: v a) x
257 $ unstream
258 $ Stream.replicate n x
259
260 -- | Generate a vector of the given length by applying the function to each
261 -- index
262 generate :: Vector v a => Int -> (Int -> a) -> v a
263 {-# INLINE generate #-}
264 generate n f = unstream (Stream.generate n f)
265
266 -- | Prepend an element
267 cons :: forall v a. Vector v a => a -> v a -> v a
268 {-# INLINE cons #-}
269 cons x v = elemseq (undefined :: v a) x
270 $ unstream
271 $ Stream.cons x
272 $ stream v
273
274 -- | Append an element
275 snoc :: forall v a. Vector v a => v a -> a -> v a
276 {-# INLINE snoc #-}
277 snoc v x = elemseq (undefined :: v a) x
278 $ unstream
279 $ Stream.snoc (stream v) x
280
281 infixr 5 ++
282 -- | Concatenate two vectors
283 (++) :: Vector v a => v a -> v a -> v a
284 {-# INLINE (++) #-}
285 v ++ w = unstream (stream v Stream.++ stream w)
286
287 -- | Create a copy of a vector. Useful when dealing with slices.
288 copy :: Vector v a => v a -> v a
289 {-# INLINE_STREAM copy #-}
290 copy = unstream . stream
291
292 {-# RULES
293
294 "copy/unstream [Vector]" forall v s.
295 copy (new' v (New.unstream s)) = new' v (New.unstream s)
296
297 #-}
298
299 -- Accessing individual elements
300 -- -----------------------------
301
302 -- | Indexing
303 (!) :: Vector v a => v a -> Int -> a
304 {-# INLINE_STREAM (!) #-}
305 v ! i = BOUNDS_CHECK(checkIndex) "(!)" i (length v)
306 $ unId (basicUnsafeIndexM v i)
307
308 -- | Unsafe indexing without bounds checking
309 unsafeIndex :: Vector v a => v a -> Int -> a
310 {-# INLINE_STREAM unsafeIndex #-}
311 unsafeIndex v i = UNSAFE_CHECK(checkIndex) "unsafeIndex" i (length v)
312 $ unId (basicUnsafeIndexM v i)
313
314 -- | First element
315 head :: Vector v a => v a -> a
316 {-# INLINE_STREAM head #-}
317 head v = v ! 0
318
319 -- | Last element
320 last :: Vector v a => v a -> a
321 {-# INLINE_STREAM last #-}
322 last v = v ! (length v - 1)
323
324 {-# RULES
325
326 "(!)/unstream [Vector]" forall v i s.
327 new' v (New.unstream s) ! i = s Stream.!! i
328
329 "unsafeIndex/unstream [Vector]" forall v i s.
330 unsafeIndex (new' v (New.unstream s)) i = s Stream.!! i
331
332 "head/unstream [Vector]" forall v s.
333 head (new' v (New.unstream s)) = Stream.head s
334
335 "last/unstream [Vector]" forall v s.
336 last (new' v (New.unstream s)) = Stream.last s
337
338 #-}
339
340 -- | Monadic indexing which can be strict in the vector while remaining lazy in
341 -- the element.
342 indexM :: (Vector v a, Monad m) => v a -> Int -> m a
343 {-# INLINE_STREAM indexM #-}
344 indexM v i = BOUNDS_CHECK(checkIndex) "indexM" i (length v)
345 $ basicUnsafeIndexM v i
346
347 -- | Unsafe monadic indexing without bounds checks
348 unsafeIndexM :: (Vector v a, Monad m) => v a -> Int -> m a
349 {-# INLINE_STREAM unsafeIndexM #-}
350 unsafeIndexM v i = UNSAFE_CHECK(checkIndex) "unsafeIndexM" i (length v)
351 $ basicUnsafeIndexM v i
352
353 headM :: (Vector v a, Monad m) => v a -> m a
354 {-# INLINE_STREAM headM #-}
355 headM v = indexM v 0
356
357 lastM :: (Vector v a, Monad m) => v a -> m a
358 {-# INLINE_STREAM lastM #-}
359 lastM v = indexM v (length v - 1)
360
361 -- FIXME: the rhs of these rules are lazy in the stream which is WRONG
362 {- RULES
363
364 "indexM/unstream [Vector]" forall v i s.
365 indexM (new' v (New.unstream s)) i = return (s Stream.!! i)
366
367 "headM/unstream [Vector]" forall v s.
368 headM (new' v (New.unstream s)) = return (Stream.head s)
369
370 "lastM/unstream [Vector]" forall v s.
371 lastM (new' v (New.unstream s)) = return (Stream.last s)
372
373 -}
374
375 -- Subarrays
376 -- ---------
377
378 -- FIXME: slicing doesn't work with the inplace stuff at the moment
379
380 -- | Yield a part of the vector without copying it.
381 slice :: Vector v a => v a -> Int -- ^ starting index
382 -> Int -- ^ length
383 -> v a
384 {-# INLINE_STREAM slice #-}
385 slice v i n = BOUNDS_CHECK(checkSlice) "slice" i n (length v)
386 $ basicUnsafeSlice v i n
387
388 -- | Unsafely yield a part of the vector without copying it and without
389 -- performing bounds checks.
390 unsafeSlice :: Vector v a => v a -> Int -- ^ starting index
391 -> Int -- ^ length
392 -> v a
393 {-# INLINE_STREAM unsafeSlice #-}
394 unsafeSlice v i n = UNSAFE_CHECK(checkSlice) "unsafeSlice" i n (length v)
395 $ basicUnsafeSlice v i n
396
397 -- | Yield all but the last element without copying.
398 init :: Vector v a => v a -> v a
399 {-# INLINE_STREAM init #-}
400 init v = slice v 0 (length v - 1)
401
402 -- | All but the first element (without copying).
403 tail :: Vector v a => v a -> v a
404 {-# INLINE_STREAM tail #-}
405 tail v = slice v 1 (length v - 1)
406
407 -- | Yield the first @n@ elements without copying.
408 take :: Vector v a => Int -> v a -> v a
409 {-# INLINE_STREAM take #-}
410 take n v = slice v 0 (min n' (length v))
411 where n' = max n 0
412
413 -- | Yield all but the first @n@ elements without copying.
414 drop :: Vector v a => Int -> v a -> v a
415 {-# INLINE_STREAM drop #-}
416 drop n v = slice v (min n' len) (max 0 (len - n'))
417 where n' = max n 0
418 len = length v
419
420 {-# RULES
421
422 "slice/new [Vector]" forall v p i n.
423 slice (new' v p) i n = new' v (New.slice p i n)
424
425 "unsafeSlice/new [Vector]" forall v p i n.
426 unsafeSlice (new' v p) i n = new' v (New.unsafeSlice p i n)
427
428 "init/new [Vector]" forall v p.
429 init (new' v p) = new' v (New.init p)
430
431 "tail/new [Vector]" forall v p.
432 tail (new' v p) = new' v (New.tail p)
433
434 "take/new [Vector]" forall n v p.
435 take n (new' v p) = new' v (New.take n p)
436
437 "drop/new [Vector]" forall n v p.
438 drop n (new' v p) = new' v (New.drop n p)
439
440 #-}
441
442 -- Permutations
443 -- ------------
444
445 unsafeAccum_stream
446 :: Vector v a => (a -> b -> a) -> v a -> Stream (Int,b) -> v a
447 {-# INLINE unsafeAccum_stream #-}
448 unsafeAccum_stream f v s = new (New.accum f (New.unstream (stream v)) s)
449
450 unsafeAccum :: Vector v a => (a -> b -> a) -> v a -> [(Int,b)] -> v a
451 {-# INLINE unsafeAccum #-}
452 unsafeAccum f v us = unsafeAccum_stream f v (Stream.fromList us)
453
454 unsafeAccumulate :: (Vector v a, Vector v (Int, b))
455 => (a -> b -> a) -> v a -> v (Int,b) -> v a
456 {-# INLINE unsafeAccumulate #-}
457 unsafeAccumulate f v us = unsafeAccum_stream f v (stream us)
458
459 unsafeAccumulate_ :: (Vector v a, Vector v Int, Vector v b)
460 => (a -> b -> a) -> v a -> v Int -> v b -> v a
461 {-# INLINE unsafeAccumulate_ #-}
462 unsafeAccumulate_ f v is xs
463 = unsafeAccum_stream f v (Stream.zipWith (,) (stream is) (stream xs))
464
465 accum_stream :: Vector v a => (a -> b -> a) -> v a -> Stream (Int,b) -> v a
466 {-# INLINE accum_stream #-}
467 accum_stream f v s = new (New.accum f (New.unstream (stream v)) s)
468
469 accum :: Vector v a => (a -> b -> a) -> v a -> [(Int,b)] -> v a
470 {-# INLINE accum #-}
471 accum f v us = accum_stream f v (Stream.fromList us)
472
473 accumulate :: (Vector v a, Vector v (Int, b))
474 => (a -> b -> a) -> v a -> v (Int,b) -> v a
475 {-# INLINE accumulate #-}
476 accumulate f v us = accum_stream f v (stream us)
477
478 accumulate_ :: (Vector v a, Vector v Int, Vector v b)
479 => (a -> b -> a) -> v a -> v Int -> v b -> v a
480 {-# INLINE accumulate_ #-}
481 accumulate_ f v is xs = accum_stream f v (Stream.zipWith (,) (stream is)
482 (stream xs))
483
484
485 unsafeUpdate_stream :: Vector v a => v a -> Stream (Int,a) -> v a
486 {-# INLINE unsafeUpdate_stream #-}
487 unsafeUpdate_stream v s = new (New.unsafeUpdate (New.unstream (stream v)) s)
488
489 unsafeUpd :: Vector v a => v a -> [(Int, a)] -> v a
490 {-# INLINE unsafeUpd #-}
491 unsafeUpd v us = unsafeUpdate_stream v (Stream.fromList us)
492
493 unsafeUpdate :: (Vector v a, Vector v (Int, a)) => v a -> v (Int, a) -> v a
494 {-# INLINE unsafeUpdate #-}
495 unsafeUpdate v w = unsafeUpdate_stream v (stream w)
496
497 unsafeUpdate_ :: (Vector v a, Vector v Int) => v a -> v Int -> v a -> v a
498 {-# INLINE unsafeUpdate_ #-}
499 unsafeUpdate_ v is w
500 = unsafeUpdate_stream v (Stream.zipWith (,) (stream is) (stream w))
501
502 update_stream :: Vector v a => v a -> Stream (Int,a) -> v a
503 {-# INLINE update_stream #-}
504 update_stream v s = new (New.update (New.unstream (stream v)) s)
505
506 (//) :: Vector v a => v a -> [(Int, a)] -> v a
507 {-# INLINE (//) #-}
508 v // us = update_stream v (Stream.fromList us)
509
510 update :: (Vector v a, Vector v (Int, a)) => v a -> v (Int, a) -> v a
511 {-# INLINE update #-}
512 update v w = update_stream v (stream w)
513
514 update_ :: (Vector v a, Vector v Int) => v a -> v Int -> v a -> v a
515 {-# INLINE update_ #-}
516 update_ v is w = update_stream v (Stream.zipWith (,) (stream is) (stream w))
517
518 -- This somewhat non-intuitive definition ensures that the resulting vector
519 -- does not retain references to the original one even if it is lazy in its
520 -- elements. This would not be the case if we simply used
521 --
522 -- backpermute v is = map (v!) is
523 backpermute :: (Vector v a, Vector v Int) => v a -> v Int -> v a
524 {-# INLINE backpermute #-}
525 backpermute v is = seq v
526 $ unstream
527 $ Stream.unbox
528 $ Stream.map (indexM v)
529 $ stream is
530
531 reverse :: (Vector v a) => v a -> v a
532 {-# INLINE reverse #-}
533 reverse = new . New.reverse . New.unstream . stream
534
535 -- Mapping
536 -- -------
537
538 -- | Map a function over a vector
539 map :: (Vector v a, Vector v b) => (a -> b) -> v a -> v b
540 {-# INLINE map #-}
541 map f = unstream . inplace (MStream.map f) . stream
542
543 -- | Apply a function to every index/value pair
544 imap :: (Vector v a, Vector v b) => (Int -> a -> b) -> v a -> v b
545 {-# INLINE imap #-}
546 imap f = unstream . inplace (MStream.map (uncurry f) . MStream.indexed)
547 . stream
548
549 concatMap :: (Vector v a, Vector v b) => (a -> v b) -> v a -> v b
550 {-# INLINE concatMap #-}
551 concatMap f = unstream . Stream.concatMap (stream . f) . stream
552
553 -- Zipping/unzipping
554 -- -----------------
555
556 -- | Zip two vectors with the given function.
557 zipWith :: (Vector v a, Vector v b, Vector v c)
558 => (a -> b -> c) -> v a -> v b -> v c
559 {-# INLINE zipWith #-}
560 zipWith f xs ys = unstream (Stream.zipWith f (stream xs) (stream ys))
561
562 -- | Zip three vectors with the given function.
563 zipWith3 :: (Vector v a, Vector v b, Vector v c, Vector v d)
564 => (a -> b -> c -> d) -> v a -> v b -> v c -> v d
565 {-# INLINE zipWith3 #-}
566 zipWith3 f as bs cs = unstream (Stream.zipWith3 f (stream as)
567 (stream bs)
568 (stream cs))
569
570 zipWith4 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e)
571 => (a -> b -> c -> d -> e) -> v a -> v b -> v c -> v d -> v e
572 {-# INLINE zipWith4 #-}
573 zipWith4 f as bs cs ds
574 = unstream (Stream.zipWith4 f (stream as)
575 (stream bs)
576 (stream cs)
577 (stream ds))
578
579 zipWith5 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e,
580 Vector v f)
581 => (a -> b -> c -> d -> e -> f) -> v a -> v b -> v c -> v d -> v e
582 -> v f
583 {-# INLINE zipWith5 #-}
584 zipWith5 f as bs cs ds es
585 = unstream (Stream.zipWith5 f (stream as)
586 (stream bs)
587 (stream cs)
588 (stream ds)
589 (stream es))
590
591 zipWith6 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e,
592 Vector v f, Vector v g)
593 => (a -> b -> c -> d -> e -> f -> g)
594 -> v a -> v b -> v c -> v d -> v e -> v f -> v g
595 {-# INLINE zipWith6 #-}
596 zipWith6 f as bs cs ds es fs
597 = unstream (Stream.zipWith6 f (stream as)
598 (stream bs)
599 (stream cs)
600 (stream ds)
601 (stream es)
602 (stream fs))
603
604 -- | Zip two vectors and their indices with the given function.
605 izipWith :: (Vector v a, Vector v b, Vector v c)
606 => (Int -> a -> b -> c) -> v a -> v b -> v c
607 {-# INLINE izipWith #-}
608 izipWith f xs ys = unstream
609 (Stream.zipWith (uncurry f) (Stream.indexed (stream xs))
610 (stream ys))
611
612 -- | Zip three vectors and their indices with the given function.
613 izipWith3 :: (Vector v a, Vector v b, Vector v c, Vector v d)
614 => (Int -> a -> b -> c -> d) -> v a -> v b -> v c -> v d
615 {-# INLINE izipWith3 #-}
616 izipWith3 f as bs cs
617 = unstream (Stream.zipWith3 (uncurry f) (Stream.indexed (stream as))
618 (stream bs)
619 (stream cs))
620
621 izipWith4 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e)
622 => (Int -> a -> b -> c -> d -> e) -> v a -> v b -> v c -> v d -> v e
623 {-# INLINE izipWith4 #-}
624 izipWith4 f as bs cs ds
625 = unstream (Stream.zipWith4 (uncurry f) (Stream.indexed (stream as))
626 (stream bs)
627 (stream cs)
628 (stream ds))
629
630 izipWith5 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e,
631 Vector v f)
632 => (Int -> a -> b -> c -> d -> e -> f) -> v a -> v b -> v c -> v d
633 -> v e -> v f
634 {-# INLINE izipWith5 #-}
635 izipWith5 f as bs cs ds es
636 = unstream (Stream.zipWith5 (uncurry f) (Stream.indexed (stream as))
637 (stream bs)
638 (stream cs)
639 (stream ds)
640 (stream es))
641
642 izipWith6 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e,
643 Vector v f, Vector v g)
644 => (Int -> a -> b -> c -> d -> e -> f -> g)
645 -> v a -> v b -> v c -> v d -> v e -> v f -> v g
646 {-# INLINE izipWith6 #-}
647 izipWith6 f as bs cs ds es fs
648 = unstream (Stream.zipWith6 (uncurry f) (Stream.indexed (stream as))
649 (stream bs)
650 (stream cs)
651 (stream ds)
652 (stream es)
653 (stream fs))
654
655 zip :: (Vector v a, Vector v b, Vector v (a,b)) => v a -> v b -> v (a, b)
656 {-# INLINE zip #-}
657 zip = zipWith (,)
658
659 zip3 :: (Vector v a, Vector v b, Vector v c, Vector v (a, b, c))
660 => v a -> v b -> v c -> v (a, b, c)
661 {-# INLINE zip3 #-}
662 zip3 = zipWith3 (,,)
663
664 zip4 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v (a, b, c, d))
665 => v a -> v b -> v c -> v d -> v (a, b, c, d)
666 {-# INLINE zip4 #-}
667 zip4 = zipWith4 (,,,)
668
669 zip5 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e,
670 Vector v (a, b, c, d, e))
671 => v a -> v b -> v c -> v d -> v e -> v (a, b, c, d, e)
672 {-# INLINE zip5 #-}
673 zip5 = zipWith5 (,,,,)
674
675 zip6 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e,
676 Vector v f, Vector v (a, b, c, d, e, f))
677 => v a -> v b -> v c -> v d -> v e -> v f -> v (a, b, c, d, e, f)
678 {-# INLINE zip6 #-}
679 zip6 = zipWith6 (,,,,,)
680
681 unzip :: (Vector v a, Vector v b, Vector v (a,b)) => v (a, b) -> (v a, v b)
682 {-# INLINE unzip #-}
683 unzip xs = (map fst xs, map snd xs)
684
685 unzip3 :: (Vector v a, Vector v b, Vector v c, Vector v (a, b, c))
686 => v (a, b, c) -> (v a, v b, v c)
687 {-# INLINE unzip3 #-}
688 unzip3 xs = (map (\(a, b, c) -> a) xs,
689 map (\(a, b, c) -> b) xs,
690 map (\(a, b, c) -> c) xs)
691
692 unzip4 :: (Vector v a, Vector v b, Vector v c, Vector v d,
693 Vector v (a, b, c, d))
694 => v (a, b, c, d) -> (v a, v b, v c, v d)
695 {-# INLINE unzip4 #-}
696 unzip4 xs = (map (\(a, b, c, d) -> a) xs,
697 map (\(a, b, c, d) -> b) xs,
698 map (\(a, b, c, d) -> c) xs,
699 map (\(a, b, c, d) -> d) xs)
700
701 unzip5 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e,
702 Vector v (a, b, c, d, e))
703 => v (a, b, c, d, e) -> (v a, v b, v c, v d, v e)
704 {-# INLINE unzip5 #-}
705 unzip5 xs = (map (\(a, b, c, d, e) -> a) xs,
706 map (\(a, b, c, d, e) -> b) xs,
707 map (\(a, b, c, d, e) -> c) xs,
708 map (\(a, b, c, d, e) -> d) xs,
709 map (\(a, b, c, d, e) -> e) xs)
710
711 unzip6 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e,
712 Vector v f, Vector v (a, b, c, d, e, f))
713 => v (a, b, c, d, e, f) -> (v a, v b, v c, v d, v e, v f)
714 {-# INLINE unzip6 #-}
715 unzip6 xs = (map (\(a, b, c, d, e, f) -> a) xs,
716 map (\(a, b, c, d, e, f) -> b) xs,
717 map (\(a, b, c, d, e, f) -> c) xs,
718 map (\(a, b, c, d, e, f) -> d) xs,
719 map (\(a, b, c, d, e, f) -> e) xs,
720 map (\(a, b, c, d, e, f) -> f) xs)
721
722 -- Comparisons
723 -- -----------
724
725 eq :: (Vector v a, Eq a) => v a -> v a -> Bool
726 {-# INLINE eq #-}
727 xs `eq` ys = stream xs == stream ys
728
729 cmp :: (Vector v a, Ord a) => v a -> v a -> Ordering
730 {-# INLINE cmp #-}
731 cmp xs ys = compare (stream xs) (stream ys)
732
733 -- Filtering
734 -- ---------
735
736 -- | Drop elements that do not satisfy the predicate
737 filter :: Vector v a => (a -> Bool) -> v a -> v a
738 {-# INLINE filter #-}
739 filter f = unstream . inplace (MStream.filter f) . stream
740
741 -- | Drop elements that do not satisfy the predicate (applied to values and
742 -- their indices)
743 ifilter :: Vector v a => (Int -> a -> Bool) -> v a -> v a
744 {-# INLINE ifilter #-}
745 ifilter f = unstream
746 . inplace (MStream.map snd . MStream.filter (uncurry f)
747 . MStream.indexed)
748 . stream
749
750 -- | Yield the longest prefix of elements satisfying the predicate.
751 takeWhile :: Vector v a => (a -> Bool) -> v a -> v a
752 {-# INLINE takeWhile #-}
753 takeWhile f = unstream . Stream.takeWhile f . stream
754
755 -- | Drop the longest prefix of elements that satisfy the predicate.
756 dropWhile :: Vector v a => (a -> Bool) -> v a -> v a
757 {-# INLINE dropWhile #-}
758 dropWhile f = unstream . Stream.dropWhile f . stream
759
760 -- Searching
761 -- ---------
762
763 infix 4 `elem`
764 -- | Check whether the vector contains an element
765 elem :: (Vector v a, Eq a) => a -> v a -> Bool
766 {-# INLINE elem #-}
767 elem x = Stream.elem x . stream
768
769 infix 4 `notElem`
770 -- | Inverse of `elem`
771 notElem :: (Vector v a, Eq a) => a -> v a -> Bool
772 {-# INLINE notElem #-}
773 notElem x = Stream.notElem x . stream
774
775 -- | Yield 'Just' the first element matching the predicate or 'Nothing' if no
776 -- such element exists.
777 find :: Vector v a => (a -> Bool) -> v a -> Maybe a
778 {-# INLINE find #-}
779 find f = Stream.find f . stream
780
781 -- | Yield 'Just' the index of the first element matching the predicate or
782 -- 'Nothing' if no such element exists.
783 findIndex :: Vector v a => (a -> Bool) -> v a -> Maybe Int
784 {-# INLINE findIndex #-}
785 findIndex f = Stream.findIndex f . stream
786
787 -- | Yield the indices of elements satisfying the predicate
788 findIndices :: (Vector v a, Vector v Int) => (a -> Bool) -> v a -> v Int
789 {-# INLINE findIndices #-}
790 findIndices f = unstream
791 . Stream.map fst
792 . Stream.filter (f . snd)
793 . Stream.indexed
794 . stream
795
796 -- | Yield 'Just' the index of the first occurence of the given element or
797 -- 'Nothing' if the vector does not contain the element
798 elemIndex :: (Vector v a, Eq a) => a -> v a -> Maybe Int
799 {-# INLINE elemIndex #-}
800 elemIndex x = findIndex (x==)
801
802 -- | Yield the indices of all occurences of the given element
803 elemIndices :: (Vector v a, Vector v Int, Eq a) => a -> v a -> v Int
804 {-# INLINE elemIndices #-}
805 elemIndices x = findIndices (x==)
806
807 -- Folding
808 -- -------
809
810 -- | Left fold
811 foldl :: Vector v b => (a -> b -> a) -> a -> v b -> a
812 {-# INLINE foldl #-}
813 foldl f z = Stream.foldl f z . stream
814
815 -- | Left fold on non-empty vectors
816 foldl1 :: Vector v a => (a -> a -> a) -> v a -> a
817 {-# INLINE foldl1 #-}
818 foldl1 f = Stream.foldl1 f . stream
819
820 -- | Left fold with strict accumulator
821 foldl' :: Vector v b => (a -> b -> a) -> a -> v b -> a
822 {-# INLINE foldl' #-}
823 foldl' f z = Stream.foldl' f z . stream
824
825 -- | Left fold on non-empty vectors with strict accumulator
826 foldl1' :: Vector v a => (a -> a -> a) -> v a -> a
827 {-# INLINE foldl1' #-}
828 foldl1' f = Stream.foldl1' f . stream
829
830 -- | Right fold
831 foldr :: Vector v a => (a -> b -> b) -> b -> v a -> b
832 {-# INLINE foldr #-}
833 foldr f z = Stream.foldr f z . stream
834
835 -- | Right fold on non-empty vectors
836 foldr1 :: Vector v a => (a -> a -> a) -> v a -> a
837 {-# INLINE foldr1 #-}
838 foldr1 f = Stream.foldr1 f . stream
839
840 -- | Left fold (function applied to each element and its index)
841 ifoldl :: Vector v b => (a -> Int -> b -> a) -> a -> v b -> a
842 {-# INLINE ifoldl #-}
843 ifoldl f z = Stream.foldl (uncurry . f) z . Stream.indexed . stream
844
845 -- | Left fold with strict accumulator (function applied to each element and
846 -- its index)
847 ifoldl' :: Vector v b => (a -> Int -> b -> a) -> a -> v b -> a
848 {-# INLINE ifoldl' #-}
849 ifoldl' f z = Stream.foldl' (uncurry . f) z . Stream.indexed . stream
850
851 -- | Right fold (function applied to each element and its index)
852 ifoldr :: Vector v a => (Int -> a -> b -> b) -> b -> v a -> b
853 {-# INLINE ifoldr #-}
854 ifoldr f z = Stream.foldr (uncurry f) z . Stream.indexed . stream
855
856 -- Specialised folds
857 -- -----------------
858
859 all :: Vector v a => (a -> Bool) -> v a -> Bool
860 {-# INLINE all #-}
861 all f = Stream.and . Stream.map f . stream
862
863 any :: Vector v a => (a -> Bool) -> v a -> Bool
864 {-# INLINE any #-}
865 any f = Stream.or . Stream.map f . stream
866
867 and :: Vector v Bool => v Bool -> Bool
868 {-# INLINE and #-}
869 and = Stream.and . stream
870
871 or :: Vector v Bool => v Bool -> Bool
872 {-# INLINE or #-}
873 or = Stream.or . stream
874
875 sum :: (Vector v a, Num a) => v a -> a
876 {-# INLINE sum #-}
877 sum = Stream.foldl' (+) 0 . stream
878
879 product :: (Vector v a, Num a) => v a -> a
880 {-# INLINE product #-}
881 product = Stream.foldl' (*) 1 . stream
882
883 maximum :: (Vector v a, Ord a) => v a -> a
884 {-# INLINE maximum #-}
885 maximum = Stream.foldl1' max . stream
886
887 maximumBy :: Vector v a => (a -> a -> Ordering) -> v a -> a
888 {-# INLINE maximumBy #-}
889 maximumBy cmp = Stream.foldl1' maxBy . stream
890 where
891 {-# INLINE maxBy #-}
892 maxBy x y = case cmp x y of
893 LT -> y
894 _ -> x
895
896 minimum :: (Vector v a, Ord a) => v a -> a
897 {-# INLINE minimum #-}
898 minimum = Stream.foldl1' min . stream
899
900 minimumBy :: Vector v a => (a -> a -> Ordering) -> v a -> a
901 {-# INLINE minimumBy #-}
902 minimumBy cmp = Stream.foldl1' minBy . stream
903 where
904 {-# INLINE minBy #-}
905 minBy x y = case cmp x y of
906 GT -> y
907 _ -> x
908
909 maxIndex :: (Vector v a, Ord a) => v a -> Int
910 {-# INLINE maxIndex #-}
911 maxIndex = maxIndexBy compare
912
913 maxIndexBy :: Vector v a => (a -> a -> Ordering) -> v a -> Int
914 {-# INLINE maxIndexBy #-}
915 maxIndexBy cmp = fst . Stream.foldl1' imax . Stream.indexed . stream
916 where
917 imax (i,x) (j,y) = case cmp x y of
918 LT -> (j,y)
919 _ -> (i,x)
920
921 minIndex :: (Vector v a, Ord a) => v a -> Int
922 {-# INLINE minIndex #-}
923 minIndex = minIndexBy compare
924
925 minIndexBy :: Vector v a => (a -> a -> Ordering) -> v a -> Int
926 {-# INLINE minIndexBy #-}
927 minIndexBy cmp = fst . Stream.foldl1' imin . Stream.indexed . stream
928 where
929 imin (i,x) (j,y) = case cmp x y of
930 GT -> (j,y)
931 _ -> (i,x)
932
933
934 -- Unfolding
935 -- ---------
936
937 unfoldr :: Vector v a => (b -> Maybe (a, b)) -> b -> v a
938 {-# INLINE unfoldr #-}
939 unfoldr f = unstream . Stream.unfoldr f
940
941 -- Scans
942 -- -----
943
944 -- | Prefix scan
945 prescanl :: (Vector v a, Vector v b) => (a -> b -> a) -> a -> v b -> v a
946 {-# INLINE prescanl #-}
947 prescanl f z = unstream . inplace (MStream.prescanl f z) . stream
948
949 -- | Prefix scan with strict accumulator
950 prescanl' :: (Vector v a, Vector v b) => (a -> b -> a) -> a -> v b -> v a
951 {-# INLINE prescanl' #-}
952 prescanl' f z = unstream . inplace (MStream.prescanl' f z) . stream
953
954 -- | Suffix scan
955 postscanl :: (Vector v a, Vector v b) => (a -> b -> a) -> a -> v b -> v a
956 {-# INLINE postscanl #-}
957 postscanl f z = unstream . inplace (MStream.postscanl f z) . stream
958
959 -- | Suffix scan with strict accumulator
960 postscanl' :: (Vector v a, Vector v b) => (a -> b -> a) -> a -> v b -> v a
961 {-# INLINE postscanl' #-}
962 postscanl' f z = unstream . inplace (MStream.postscanl' f z) . stream
963
964 -- | Haskell-style scan
965 scanl :: (Vector v a, Vector v b) => (a -> b -> a) -> a -> v b -> v a
966 {-# INLINE scanl #-}
967 scanl f z = unstream . Stream.scanl f z . stream
968
969 -- | Haskell-style scan with strict accumulator
970 scanl' :: (Vector v a, Vector v b) => (a -> b -> a) -> a -> v b -> v a
971 {-# INLINE scanl' #-}
972 scanl' f z = unstream . Stream.scanl' f z . stream
973
974 -- | Scan over a non-empty vector
975 scanl1 :: Vector v a => (a -> a -> a) -> v a -> v a
976 {-# INLINE scanl1 #-}
977 scanl1 f = unstream . inplace (MStream.scanl1 f) . stream
978
979 -- | Scan over a non-empty vector with a strict accumulator
980 scanl1' :: Vector v a => (a -> a -> a) -> v a -> v a
981 {-# INLINE scanl1' #-}
982 scanl1' f = unstream . inplace (MStream.scanl1' f) . stream
983
984 -- Enumeration
985 -- -----------
986
987 enumFromTo :: (Vector v a, Enum a) => a -> a -> v a
988 {-# INLINE enumFromTo #-}
989 enumFromTo x y = unstream (Stream.enumFromTo x y)
990
991 enumFromThenTo :: (Vector v a, Enum a) => a -> a -> a -> v a
992 {-# INLINE enumFromThenTo #-}
993 enumFromThenTo x y z = unstream (Stream.enumFromThenTo x y z)
994
995 -- | Convert a vector to a list
996 toList :: Vector v a => v a -> [a]
997 {-# INLINE toList #-}
998 toList = Stream.toList . stream
999
1000 -- | Convert a list to a vector
1001 fromList :: Vector v a => [a] -> v a
1002 {-# INLINE fromList #-}
1003 fromList = unstream . Stream.fromList
1004