Add all, any
[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, (++), 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 -- | Prepend an element
261 cons :: forall v a. Vector v a => a -> v a -> v a
262 {-# INLINE cons #-}
263 cons x v = elemseq (undefined :: v a) x
264 $ unstream
265 $ Stream.cons x
266 $ stream v
267
268 -- | Append an element
269 snoc :: forall v a. Vector v a => v a -> a -> v a
270 {-# INLINE snoc #-}
271 snoc v x = elemseq (undefined :: v a) x
272 $ unstream
273 $ Stream.snoc (stream v) x
274
275 infixr 5 ++
276 -- | Concatenate two vectors
277 (++) :: Vector v a => v a -> v a -> v a
278 {-# INLINE (++) #-}
279 v ++ w = unstream (stream v Stream.++ stream w)
280
281 -- | Create a copy of a vector. Useful when dealing with slices.
282 copy :: Vector v a => v a -> v a
283 {-# INLINE_STREAM copy #-}
284 copy = unstream . stream
285
286 {-# RULES
287
288 "copy/unstream [Vector]" forall v s.
289 copy (new' v (New.unstream s)) = new' v (New.unstream s)
290
291 #-}
292
293 -- Accessing individual elements
294 -- -----------------------------
295
296 -- | Indexing
297 (!) :: Vector v a => v a -> Int -> a
298 {-# INLINE_STREAM (!) #-}
299 v ! i = BOUNDS_CHECK(checkIndex) "(!)" i (length v)
300 $ unId (basicUnsafeIndexM v i)
301
302 -- | Unsafe indexing without bounds checking
303 unsafeIndex :: Vector v a => v a -> Int -> a
304 {-# INLINE_STREAM unsafeIndex #-}
305 unsafeIndex v i = UNSAFE_CHECK(checkIndex) "unsafeIndex" i (length v)
306 $ unId (basicUnsafeIndexM v i)
307
308 -- | First element
309 head :: Vector v a => v a -> a
310 {-# INLINE_STREAM head #-}
311 head v = v ! 0
312
313 -- | Last element
314 last :: Vector v a => v a -> a
315 {-# INLINE_STREAM last #-}
316 last v = v ! (length v - 1)
317
318 {-# RULES
319
320 "(!)/unstream [Vector]" forall v i s.
321 new' v (New.unstream s) ! i = s Stream.!! i
322
323 "unsafeIndex/unstream [Vector]" forall v i s.
324 unsafeIndex (new' v (New.unstream s)) i = s Stream.!! i
325
326 "head/unstream [Vector]" forall v s.
327 head (new' v (New.unstream s)) = Stream.head s
328
329 "last/unstream [Vector]" forall v s.
330 last (new' v (New.unstream s)) = Stream.last s
331
332 #-}
333
334 -- | Monadic indexing which can be strict in the vector while remaining lazy in
335 -- the element.
336 indexM :: (Vector v a, Monad m) => v a -> Int -> m a
337 {-# INLINE_STREAM indexM #-}
338 indexM v i = BOUNDS_CHECK(checkIndex) "indexM" i (length v)
339 $ basicUnsafeIndexM v i
340
341 -- | Unsafe monadic indexing without bounds checks
342 unsafeIndexM :: (Vector v a, Monad m) => v a -> Int -> m a
343 {-# INLINE_STREAM unsafeIndexM #-}
344 unsafeIndexM v i = UNSAFE_CHECK(checkIndex) "unsafeIndexM" i (length v)
345 $ basicUnsafeIndexM v i
346
347 headM :: (Vector v a, Monad m) => v a -> m a
348 {-# INLINE_STREAM headM #-}
349 headM v = indexM v 0
350
351 lastM :: (Vector v a, Monad m) => v a -> m a
352 {-# INLINE_STREAM lastM #-}
353 lastM v = indexM v (length v - 1)
354
355 -- FIXME: the rhs of these rules are lazy in the stream which is WRONG
356 {- RULES
357
358 "indexM/unstream [Vector]" forall v i s.
359 indexM (new' v (New.unstream s)) i = return (s Stream.!! i)
360
361 "headM/unstream [Vector]" forall v s.
362 headM (new' v (New.unstream s)) = return (Stream.head s)
363
364 "lastM/unstream [Vector]" forall v s.
365 lastM (new' v (New.unstream s)) = return (Stream.last s)
366
367 -}
368
369 -- Subarrays
370 -- ---------
371
372 -- FIXME: slicing doesn't work with the inplace stuff at the moment
373
374 -- | Yield a part of the vector without copying it.
375 slice :: Vector v a => v a -> Int -- ^ starting index
376 -> Int -- ^ length
377 -> v a
378 {-# INLINE_STREAM slice #-}
379 slice v i n = BOUNDS_CHECK(checkSlice) "slice" i n (length v)
380 $ basicUnsafeSlice v i n
381
382 -- | Unsafely yield a part of the vector without copying it and without
383 -- performing bounds checks.
384 unsafeSlice :: Vector v a => v a -> Int -- ^ starting index
385 -> Int -- ^ length
386 -> v a
387 {-# INLINE_STREAM unsafeSlice #-}
388 unsafeSlice v i n = UNSAFE_CHECK(checkSlice) "unsafeSlice" i n (length v)
389 $ basicUnsafeSlice v i n
390
391 -- | Yield all but the last element without copying.
392 init :: Vector v a => v a -> v a
393 {-# INLINE_STREAM init #-}
394 init v = slice v 0 (length v - 1)
395
396 -- | All but the first element (without copying).
397 tail :: Vector v a => v a -> v a
398 {-# INLINE_STREAM tail #-}
399 tail v = slice v 1 (length v - 1)
400
401 -- | Yield the first @n@ elements without copying.
402 take :: Vector v a => Int -> v a -> v a
403 {-# INLINE_STREAM take #-}
404 take n v = slice v 0 (min n' (length v))
405 where n' = max n 0
406
407 -- | Yield all but the first @n@ elements without copying.
408 drop :: Vector v a => Int -> v a -> v a
409 {-# INLINE_STREAM drop #-}
410 drop n v = slice v (min n' len) (max 0 (len - n'))
411 where n' = max n 0
412 len = length v
413
414 {-# RULES
415
416 "slice/new [Vector]" forall v p i n.
417 slice (new' v p) i n = new' v (New.slice p i n)
418
419 "unsafeSlice/new [Vector]" forall v p i n.
420 unsafeSlice (new' v p) i n = new' v (New.unsafeSlice p i n)
421
422 "init/new [Vector]" forall v p.
423 init (new' v p) = new' v (New.init p)
424
425 "tail/new [Vector]" forall v p.
426 tail (new' v p) = new' v (New.tail p)
427
428 "take/new [Vector]" forall n v p.
429 take n (new' v p) = new' v (New.take n p)
430
431 "drop/new [Vector]" forall n v p.
432 drop n (new' v p) = new' v (New.drop n p)
433
434 #-}
435
436 -- Permutations
437 -- ------------
438
439 unsafeAccum_stream
440 :: Vector v a => (a -> b -> a) -> v a -> Stream (Int,b) -> v a
441 {-# INLINE unsafeAccum_stream #-}
442 unsafeAccum_stream f v s = new (New.accum f (New.unstream (stream v)) s)
443
444 unsafeAccum :: Vector v a => (a -> b -> a) -> v a -> [(Int,b)] -> v a
445 {-# INLINE unsafeAccum #-}
446 unsafeAccum f v us = unsafeAccum_stream f v (Stream.fromList us)
447
448 unsafeAccumulate :: (Vector v a, Vector v (Int, b))
449 => (a -> b -> a) -> v a -> v (Int,b) -> v a
450 {-# INLINE unsafeAccumulate #-}
451 unsafeAccumulate f v us = unsafeAccum_stream f v (stream us)
452
453 unsafeAccumulate_ :: (Vector v a, Vector v Int, Vector v b)
454 => (a -> b -> a) -> v a -> v Int -> v b -> v a
455 {-# INLINE unsafeAccumulate_ #-}
456 unsafeAccumulate_ f v is xs
457 = unsafeAccum_stream f v (Stream.zipWith (,) (stream is) (stream xs))
458
459 accum_stream :: Vector v a => (a -> b -> a) -> v a -> Stream (Int,b) -> v a
460 {-# INLINE accum_stream #-}
461 accum_stream f v s = new (New.accum f (New.unstream (stream v)) s)
462
463 accum :: Vector v a => (a -> b -> a) -> v a -> [(Int,b)] -> v a
464 {-# INLINE accum #-}
465 accum f v us = accum_stream f v (Stream.fromList us)
466
467 accumulate :: (Vector v a, Vector v (Int, b))
468 => (a -> b -> a) -> v a -> v (Int,b) -> v a
469 {-# INLINE accumulate #-}
470 accumulate f v us = accum_stream f v (stream us)
471
472 accumulate_ :: (Vector v a, Vector v Int, Vector v b)
473 => (a -> b -> a) -> v a -> v Int -> v b -> v a
474 {-# INLINE accumulate_ #-}
475 accumulate_ f v is xs = accum_stream f v (Stream.zipWith (,) (stream is)
476 (stream xs))
477
478
479 unsafeUpdate_stream :: Vector v a => v a -> Stream (Int,a) -> v a
480 {-# INLINE unsafeUpdate_stream #-}
481 unsafeUpdate_stream v s = new (New.unsafeUpdate (New.unstream (stream v)) s)
482
483 unsafeUpd :: Vector v a => v a -> [(Int, a)] -> v a
484 {-# INLINE unsafeUpd #-}
485 unsafeUpd v us = unsafeUpdate_stream v (Stream.fromList us)
486
487 unsafeUpdate :: (Vector v a, Vector v (Int, a)) => v a -> v (Int, a) -> v a
488 {-# INLINE unsafeUpdate #-}
489 unsafeUpdate v w = unsafeUpdate_stream v (stream w)
490
491 unsafeUpdate_ :: (Vector v a, Vector v Int) => v a -> v Int -> v a -> v a
492 {-# INLINE unsafeUpdate_ #-}
493 unsafeUpdate_ v is w
494 = unsafeUpdate_stream v (Stream.zipWith (,) (stream is) (stream w))
495
496 update_stream :: Vector v a => v a -> Stream (Int,a) -> v a
497 {-# INLINE update_stream #-}
498 update_stream v s = new (New.update (New.unstream (stream v)) s)
499
500 (//) :: Vector v a => v a -> [(Int, a)] -> v a
501 {-# INLINE (//) #-}
502 v // us = update_stream v (Stream.fromList us)
503
504 update :: (Vector v a, Vector v (Int, a)) => v a -> v (Int, a) -> v a
505 {-# INLINE update #-}
506 update v w = update_stream v (stream w)
507
508 update_ :: (Vector v a, Vector v Int) => v a -> v Int -> v a -> v a
509 {-# INLINE update_ #-}
510 update_ v is w = update_stream v (Stream.zipWith (,) (stream is) (stream w))
511
512 -- This somewhat non-intuitive definition ensures that the resulting vector
513 -- does not retain references to the original one even if it is lazy in its
514 -- elements. This would not be the case if we simply used
515 --
516 -- backpermute v is = map (v!) is
517 backpermute :: (Vector v a, Vector v Int) => v a -> v Int -> v a
518 {-# INLINE backpermute #-}
519 backpermute v is = seq v
520 $ unstream
521 $ Stream.unbox
522 $ Stream.map (indexM v)
523 $ stream is
524
525 reverse :: (Vector v a) => v a -> v a
526 {-# INLINE reverse #-}
527 reverse = new . New.reverse . New.unstream . stream
528
529 -- Mapping
530 -- -------
531
532 -- | Map a function over a vector
533 map :: (Vector v a, Vector v b) => (a -> b) -> v a -> v b
534 {-# INLINE map #-}
535 map f = unstream . inplace (MStream.map f) . stream
536
537 -- | Apply a function to every index/value pair
538 imap :: (Vector v a, Vector v b) => (Int -> a -> b) -> v a -> v b
539 {-# INLINE imap #-}
540 imap f = unstream . inplace (MStream.map (uncurry f) . MStream.indexed)
541 . stream
542
543 concatMap :: (Vector v a, Vector v b) => (a -> v b) -> v a -> v b
544 {-# INLINE concatMap #-}
545 concatMap f = unstream . Stream.concatMap (stream . f) . stream
546
547 -- Zipping/unzipping
548 -- -----------------
549
550 -- | Zip two vectors with the given function.
551 zipWith :: (Vector v a, Vector v b, Vector v c)
552 => (a -> b -> c) -> v a -> v b -> v c
553 {-# INLINE zipWith #-}
554 zipWith f xs ys = unstream (Stream.zipWith f (stream xs) (stream ys))
555
556 -- | Zip three vectors with the given function.
557 zipWith3 :: (Vector v a, Vector v b, Vector v c, Vector v d)
558 => (a -> b -> c -> d) -> v a -> v b -> v c -> v d
559 {-# INLINE zipWith3 #-}
560 zipWith3 f as bs cs = unstream (Stream.zipWith3 f (stream as)
561 (stream bs)
562 (stream cs))
563
564 zipWith4 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e)
565 => (a -> b -> c -> d -> e) -> v a -> v b -> v c -> v d -> v e
566 {-# INLINE zipWith4 #-}
567 zipWith4 f as bs cs ds
568 = unstream (Stream.zipWith4 f (stream as)
569 (stream bs)
570 (stream cs)
571 (stream ds))
572
573 zipWith5 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e,
574 Vector v f)
575 => (a -> b -> c -> d -> e -> f) -> v a -> v b -> v c -> v d -> v e
576 -> v f
577 {-# INLINE zipWith5 #-}
578 zipWith5 f as bs cs ds es
579 = unstream (Stream.zipWith5 f (stream as)
580 (stream bs)
581 (stream cs)
582 (stream ds)
583 (stream es))
584
585 zipWith6 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e,
586 Vector v f, Vector v g)
587 => (a -> b -> c -> d -> e -> f -> g)
588 -> v a -> v b -> v c -> v d -> v e -> v f -> v g
589 {-# INLINE zipWith6 #-}
590 zipWith6 f as bs cs ds es fs
591 = unstream (Stream.zipWith6 f (stream as)
592 (stream bs)
593 (stream cs)
594 (stream ds)
595 (stream es)
596 (stream fs))
597
598 -- | Zip two vectors and their indices with the given function.
599 izipWith :: (Vector v a, Vector v b, Vector v c)
600 => (Int -> a -> b -> c) -> v a -> v b -> v c
601 {-# INLINE izipWith #-}
602 izipWith f xs ys = unstream
603 (Stream.zipWith (uncurry f) (Stream.indexed (stream xs))
604 (stream ys))
605
606 -- | Zip three vectors and their indices with the given function.
607 izipWith3 :: (Vector v a, Vector v b, Vector v c, Vector v d)
608 => (Int -> a -> b -> c -> d) -> v a -> v b -> v c -> v d
609 {-# INLINE izipWith3 #-}
610 izipWith3 f as bs cs
611 = unstream (Stream.zipWith3 (uncurry f) (Stream.indexed (stream as))
612 (stream bs)
613 (stream cs))
614
615 izipWith4 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e)
616 => (Int -> a -> b -> c -> d -> e) -> v a -> v b -> v c -> v d -> v e
617 {-# INLINE izipWith4 #-}
618 izipWith4 f as bs cs ds
619 = unstream (Stream.zipWith4 (uncurry f) (Stream.indexed (stream as))
620 (stream bs)
621 (stream cs)
622 (stream ds))
623
624 izipWith5 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e,
625 Vector v f)
626 => (Int -> a -> b -> c -> d -> e -> f) -> v a -> v b -> v c -> v d
627 -> v e -> v f
628 {-# INLINE izipWith5 #-}
629 izipWith5 f as bs cs ds es
630 = unstream (Stream.zipWith5 (uncurry f) (Stream.indexed (stream as))
631 (stream bs)
632 (stream cs)
633 (stream ds)
634 (stream es))
635
636 izipWith6 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e,
637 Vector v f, Vector v g)
638 => (Int -> a -> b -> c -> d -> e -> f -> g)
639 -> v a -> v b -> v c -> v d -> v e -> v f -> v g
640 {-# INLINE izipWith6 #-}
641 izipWith6 f as bs cs ds es fs
642 = unstream (Stream.zipWith6 (uncurry f) (Stream.indexed (stream as))
643 (stream bs)
644 (stream cs)
645 (stream ds)
646 (stream es)
647 (stream fs))
648
649 zip :: (Vector v a, Vector v b, Vector v (a,b)) => v a -> v b -> v (a, b)
650 {-# INLINE zip #-}
651 zip = zipWith (,)
652
653 zip3 :: (Vector v a, Vector v b, Vector v c, Vector v (a, b, c))
654 => v a -> v b -> v c -> v (a, b, c)
655 {-# INLINE zip3 #-}
656 zip3 = zipWith3 (,,)
657
658 zip4 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v (a, b, c, d))
659 => v a -> v b -> v c -> v d -> v (a, b, c, d)
660 {-# INLINE zip4 #-}
661 zip4 = zipWith4 (,,,)
662
663 zip5 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e,
664 Vector v (a, b, c, d, e))
665 => v a -> v b -> v c -> v d -> v e -> v (a, b, c, d, e)
666 {-# INLINE zip5 #-}
667 zip5 = zipWith5 (,,,,)
668
669 zip6 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e,
670 Vector v f, Vector v (a, b, c, d, e, f))
671 => v a -> v b -> v c -> v d -> v e -> v f -> v (a, b, c, d, e, f)
672 {-# INLINE zip6 #-}
673 zip6 = zipWith6 (,,,,,)
674
675 unzip :: (Vector v a, Vector v b, Vector v (a,b)) => v (a, b) -> (v a, v b)
676 {-# INLINE unzip #-}
677 unzip xs = (map fst xs, map snd xs)
678
679 unzip3 :: (Vector v a, Vector v b, Vector v c, Vector v (a, b, c))
680 => v (a, b, c) -> (v a, v b, v c)
681 {-# INLINE unzip3 #-}
682 unzip3 xs = (map (\(a, b, c) -> a) xs,
683 map (\(a, b, c) -> b) xs,
684 map (\(a, b, c) -> c) xs)
685
686 unzip4 :: (Vector v a, Vector v b, Vector v c, Vector v d,
687 Vector v (a, b, c, d))
688 => v (a, b, c, d) -> (v a, v b, v c, v d)
689 {-# INLINE unzip4 #-}
690 unzip4 xs = (map (\(a, b, c, d) -> a) xs,
691 map (\(a, b, c, d) -> b) xs,
692 map (\(a, b, c, d) -> c) xs,
693 map (\(a, b, c, d) -> d) xs)
694
695 unzip5 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e,
696 Vector v (a, b, c, d, e))
697 => v (a, b, c, d, e) -> (v a, v b, v c, v d, v e)
698 {-# INLINE unzip5 #-}
699 unzip5 xs = (map (\(a, b, c, d, e) -> a) xs,
700 map (\(a, b, c, d, e) -> b) xs,
701 map (\(a, b, c, d, e) -> c) xs,
702 map (\(a, b, c, d, e) -> d) xs,
703 map (\(a, b, c, d, e) -> e) xs)
704
705 unzip6 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e,
706 Vector v f, Vector v (a, b, c, d, e, f))
707 => v (a, b, c, d, e, f) -> (v a, v b, v c, v d, v e, v f)
708 {-# INLINE unzip6 #-}
709 unzip6 xs = (map (\(a, b, c, d, e, f) -> a) xs,
710 map (\(a, b, c, d, e, f) -> b) xs,
711 map (\(a, b, c, d, e, f) -> c) xs,
712 map (\(a, b, c, d, e, f) -> d) xs,
713 map (\(a, b, c, d, e, f) -> e) xs,
714 map (\(a, b, c, d, e, f) -> f) xs)
715
716 -- Comparisons
717 -- -----------
718
719 eq :: (Vector v a, Eq a) => v a -> v a -> Bool
720 {-# INLINE eq #-}
721 xs `eq` ys = stream xs == stream ys
722
723 cmp :: (Vector v a, Ord a) => v a -> v a -> Ordering
724 {-# INLINE cmp #-}
725 cmp xs ys = compare (stream xs) (stream ys)
726
727 -- Filtering
728 -- ---------
729
730 -- | Drop elements that do not satisfy the predicate
731 filter :: Vector v a => (a -> Bool) -> v a -> v a
732 {-# INLINE filter #-}
733 filter f = unstream . inplace (MStream.filter f) . stream
734
735 -- | Drop elements that do not satisfy the predicate (applied to values and
736 -- their indices)
737 ifilter :: Vector v a => (Int -> a -> Bool) -> v a -> v a
738 {-# INLINE ifilter #-}
739 ifilter f = unstream
740 . inplace (MStream.map snd . MStream.filter (uncurry f)
741 . MStream.indexed)
742 . stream
743
744 -- | Yield the longest prefix of elements satisfying the predicate.
745 takeWhile :: Vector v a => (a -> Bool) -> v a -> v a
746 {-# INLINE takeWhile #-}
747 takeWhile f = unstream . Stream.takeWhile f . stream
748
749 -- | Drop the longest prefix of elements that satisfy the predicate.
750 dropWhile :: Vector v a => (a -> Bool) -> v a -> v a
751 {-# INLINE dropWhile #-}
752 dropWhile f = unstream . Stream.dropWhile f . stream
753
754 -- Searching
755 -- ---------
756
757 infix 4 `elem`
758 -- | Check whether the vector contains an element
759 elem :: (Vector v a, Eq a) => a -> v a -> Bool
760 {-# INLINE elem #-}
761 elem x = Stream.elem x . stream
762
763 infix 4 `notElem`
764 -- | Inverse of `elem`
765 notElem :: (Vector v a, Eq a) => a -> v a -> Bool
766 {-# INLINE notElem #-}
767 notElem x = Stream.notElem x . stream
768
769 -- | Yield 'Just' the first element matching the predicate or 'Nothing' if no
770 -- such element exists.
771 find :: Vector v a => (a -> Bool) -> v a -> Maybe a
772 {-# INLINE find #-}
773 find f = Stream.find f . stream
774
775 -- | Yield 'Just' the index of the first element matching the predicate or
776 -- 'Nothing' if no such element exists.
777 findIndex :: Vector v a => (a -> Bool) -> v a -> Maybe Int
778 {-# INLINE findIndex #-}
779 findIndex f = Stream.findIndex f . stream
780
781 -- | Yield the indices of elements satisfying the predicate
782 findIndices :: (Vector v a, Vector v Int) => (a -> Bool) -> v a -> v Int
783 {-# INLINE findIndices #-}
784 findIndices f = unstream
785 . Stream.map fst
786 . Stream.filter (f . snd)
787 . Stream.indexed
788 . stream
789
790 -- | Yield 'Just' the index of the first occurence of the given element or
791 -- 'Nothing' if the vector does not contain the element
792 elemIndex :: (Vector v a, Eq a) => a -> v a -> Maybe Int
793 {-# INLINE elemIndex #-}
794 elemIndex x = findIndex (x==)
795
796 -- | Yield the indices of all occurences of the given element
797 elemIndices :: (Vector v a, Vector v Int, Eq a) => a -> v a -> v Int
798 {-# INLINE elemIndices #-}
799 elemIndices x = findIndices (x==)
800
801 -- Folding
802 -- -------
803
804 -- | Left fold
805 foldl :: Vector v b => (a -> b -> a) -> a -> v b -> a
806 {-# INLINE foldl #-}
807 foldl f z = Stream.foldl f z . stream
808
809 -- | Left fold on non-empty vectors
810 foldl1 :: Vector v a => (a -> a -> a) -> v a -> a
811 {-# INLINE foldl1 #-}
812 foldl1 f = Stream.foldl1 f . stream
813
814 -- | Left fold with strict accumulator
815 foldl' :: Vector v b => (a -> b -> a) -> a -> v b -> a
816 {-# INLINE foldl' #-}
817 foldl' f z = Stream.foldl' f z . stream
818
819 -- | Left fold on non-empty vectors with strict accumulator
820 foldl1' :: Vector v a => (a -> a -> a) -> v a -> a
821 {-# INLINE foldl1' #-}
822 foldl1' f = Stream.foldl1' f . stream
823
824 -- | Right fold
825 foldr :: Vector v a => (a -> b -> b) -> b -> v a -> b
826 {-# INLINE foldr #-}
827 foldr f z = Stream.foldr f z . stream
828
829 -- | Right fold on non-empty vectors
830 foldr1 :: Vector v a => (a -> a -> a) -> v a -> a
831 {-# INLINE foldr1 #-}
832 foldr1 f = Stream.foldr1 f . stream
833
834 -- | Left fold (function applied to each element and its index)
835 ifoldl :: Vector v b => (a -> Int -> b -> a) -> a -> v b -> a
836 {-# INLINE ifoldl #-}
837 ifoldl f z = Stream.foldl (uncurry . f) z . Stream.indexed . stream
838
839 -- | Left fold with strict accumulator (function applied to each element and
840 -- 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 -- | Right fold (function applied to each element and its index)
846 ifoldr :: Vector v a => (Int -> a -> b -> b) -> b -> v a -> b
847 {-# INLINE ifoldr #-}
848 ifoldr f z = Stream.foldr (uncurry f) z . Stream.indexed . stream
849
850 -- Specialised folds
851 -- -----------------
852
853 all :: Vector v a => (a -> Bool) -> v a -> Bool
854 {-# INLINE all #-}
855 all f = Stream.and . Stream.map f . stream
856
857 any :: Vector v a => (a -> Bool) -> v a -> Bool
858 {-# INLINE any #-}
859 any f = Stream.or . Stream.map f . stream
860
861 and :: Vector v Bool => v Bool -> Bool
862 {-# INLINE and #-}
863 and = Stream.and . stream
864
865 or :: Vector v Bool => v Bool -> Bool
866 {-# INLINE or #-}
867 or = Stream.or . stream
868
869 sum :: (Vector v a, Num a) => v a -> a
870 {-# INLINE sum #-}
871 sum = Stream.foldl' (+) 0 . stream
872
873 product :: (Vector v a, Num a) => v a -> a
874 {-# INLINE product #-}
875 product = Stream.foldl' (*) 1 . stream
876
877 maximum :: (Vector v a, Ord a) => v a -> a
878 {-# INLINE maximum #-}
879 maximum = Stream.foldl1' max . stream
880
881 maximumBy :: Vector v a => (a -> a -> Ordering) -> v a -> a
882 {-# INLINE maximumBy #-}
883 maximumBy cmp = Stream.foldl1' maxBy . stream
884 where
885 {-# INLINE maxBy #-}
886 maxBy x y = case cmp x y of
887 LT -> y
888 _ -> x
889
890 minimum :: (Vector v a, Ord a) => v a -> a
891 {-# INLINE minimum #-}
892 minimum = Stream.foldl1' min . stream
893
894 minimumBy :: Vector v a => (a -> a -> Ordering) -> v a -> a
895 {-# INLINE minimumBy #-}
896 minimumBy cmp = Stream.foldl1' minBy . stream
897 where
898 {-# INLINE minBy #-}
899 minBy x y = case cmp x y of
900 GT -> y
901 _ -> x
902
903 maxIndex :: (Vector v a, Ord a) => v a -> Int
904 {-# INLINE maxIndex #-}
905 maxIndex = maxIndexBy compare
906
907 maxIndexBy :: Vector v a => (a -> a -> Ordering) -> v a -> Int
908 {-# INLINE maxIndexBy #-}
909 maxIndexBy cmp = fst . Stream.foldl1' imax . Stream.indexed . stream
910 where
911 imax (i,x) (j,y) = case cmp x y of
912 LT -> (j,y)
913 _ -> (i,x)
914
915 minIndex :: (Vector v a, Ord a) => v a -> Int
916 {-# INLINE minIndex #-}
917 minIndex = minIndexBy compare
918
919 minIndexBy :: Vector v a => (a -> a -> Ordering) -> v a -> Int
920 {-# INLINE minIndexBy #-}
921 minIndexBy cmp = fst . Stream.foldl1' imin . Stream.indexed . stream
922 where
923 imin (i,x) (j,y) = case cmp x y of
924 GT -> (j,y)
925 _ -> (i,x)
926
927
928 -- Unfolding
929 -- ---------
930
931 unfoldr :: Vector v a => (b -> Maybe (a, b)) -> b -> v a
932 {-# INLINE unfoldr #-}
933 unfoldr f = unstream . Stream.unfoldr f
934
935 -- Scans
936 -- -----
937
938 -- | Prefix scan
939 prescanl :: (Vector v a, Vector v b) => (a -> b -> a) -> a -> v b -> v a
940 {-# INLINE prescanl #-}
941 prescanl f z = unstream . inplace (MStream.prescanl f z) . stream
942
943 -- | Prefix scan with strict accumulator
944 prescanl' :: (Vector v a, Vector v b) => (a -> b -> a) -> a -> v b -> v a
945 {-# INLINE prescanl' #-}
946 prescanl' f z = unstream . inplace (MStream.prescanl' f z) . stream
947
948 -- | Suffix scan
949 postscanl :: (Vector v a, Vector v b) => (a -> b -> a) -> a -> v b -> v a
950 {-# INLINE postscanl #-}
951 postscanl f z = unstream . inplace (MStream.postscanl f z) . stream
952
953 -- | Suffix scan with strict accumulator
954 postscanl' :: (Vector v a, Vector v b) => (a -> b -> a) -> a -> v b -> v a
955 {-# INLINE postscanl' #-}
956 postscanl' f z = unstream . inplace (MStream.postscanl' f z) . stream
957
958 -- | Haskell-style scan
959 scanl :: (Vector v a, Vector v b) => (a -> b -> a) -> a -> v b -> v a
960 {-# INLINE scanl #-}
961 scanl f z = unstream . Stream.scanl f z . stream
962
963 -- | Haskell-style scan with strict accumulator
964 scanl' :: (Vector v a, Vector v b) => (a -> b -> a) -> a -> v b -> v a
965 {-# INLINE scanl' #-}
966 scanl' f z = unstream . Stream.scanl' f z . stream
967
968 -- | Scan over a non-empty vector
969 scanl1 :: Vector v a => (a -> a -> a) -> v a -> v a
970 {-# INLINE scanl1 #-}
971 scanl1 f = unstream . inplace (MStream.scanl1 f) . stream
972
973 -- | Scan over a non-empty vector with a strict accumulator
974 scanl1' :: Vector v a => (a -> a -> a) -> v a -> v a
975 {-# INLINE scanl1' #-}
976 scanl1' f = unstream . inplace (MStream.scanl1' f) . stream
977
978 -- Enumeration
979 -- -----------
980
981 enumFromTo :: (Vector v a, Enum a) => a -> a -> v a
982 {-# INLINE enumFromTo #-}
983 enumFromTo x y = unstream (Stream.enumFromTo x y)
984
985 enumFromThenTo :: (Vector v a, Enum a) => a -> a -> a -> v a
986 {-# INLINE enumFromThenTo #-}
987 enumFromThenTo x y z = unstream (Stream.enumFromThenTo x y z)
988
989 -- | Convert a vector to a list
990 toList :: Vector v a => v a -> [a]
991 {-# INLINE toList #-}
992 toList = Stream.toList . stream
993
994 -- | Convert a list to a vector
995 fromList :: Vector v a => [a] -> v a
996 {-# INLINE fromList #-}
997 fromList = unstream . Stream.fromList
998