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