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