Export create, modify and copy/unsafeCopy
[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 -- FIXME: slicing doesn't work with the inplace stuff at the moment
458
459 -- | Yield a part of the vector without copying it.
460 slice :: Vector v a => Int -- ^ starting index
461 -> Int -- ^ length
462 -> v a
463 -> v a
464 {-# INLINE_STREAM slice #-}
465 slice i n v = BOUNDS_CHECK(checkSlice) "slice" i n (length v)
466 $ basicUnsafeSlice i n v
467
468 -- | Yield all but the last element without copying.
469 init :: Vector v a => v a -> v a
470 {-# INLINE_STREAM init #-}
471 init v = slice 0 (length v - 1) v
472
473 -- | All but the first element (without copying).
474 tail :: Vector v a => v a -> v a
475 {-# INLINE_STREAM tail #-}
476 tail v = slice 1 (length v - 1) v
477
478 -- | Yield the first @n@ elements without copying.
479 take :: Vector v a => Int -> v a -> v a
480 {-# INLINE_STREAM take #-}
481 take n v = unsafeSlice 0 (delay_inline min n' (length v)) v
482 where n' = max n 0
483
484 -- | Yield all but the first @n@ elements without copying.
485 drop :: Vector v a => Int -> v a -> v a
486 {-# INLINE_STREAM drop #-}
487 drop n v = unsafeSlice (delay_inline min n' len)
488 (delay_inline max 0 (len - n')) v
489 where n' = max n 0
490 len = length v
491
492 -- | Unsafely yield a part of the vector without copying it and without
493 -- performing bounds checks.
494 unsafeSlice :: Vector v a => Int -- ^ starting index
495 -> Int -- ^ length
496 -> v a
497 -> v a
498 {-# INLINE_STREAM unsafeSlice #-}
499 unsafeSlice i n v = UNSAFE_CHECK(checkSlice) "unsafeSlice" i n (length v)
500 $ basicUnsafeSlice i n v
501
502 unsafeInit :: Vector v a => v a -> v a
503 {-# INLINE_STREAM unsafeInit #-}
504 unsafeInit v = unsafeSlice 0 (length v - 1) v
505
506 unsafeTail :: Vector v a => v a -> v a
507 {-# INLINE_STREAM unsafeTail #-}
508 unsafeTail v = unsafeSlice 1 (length v - 1) v
509
510 unsafeTake :: Vector v a => Int -> v a -> v a
511 {-# INLINE unsafeTake #-}
512 unsafeTake n v = unsafeSlice 0 n v
513
514 unsafeDrop :: Vector v a => Int -> v a -> v a
515 {-# INLINE unsafeDrop #-}
516 unsafeDrop n v = unsafeSlice n (length v - n) v
517
518 {-# RULES
519
520 "slice/new [Vector]" forall i n p.
521 slice i n (new p) = new (New.slice i n p)
522
523 "init/new [Vector]" forall p.
524 init (new p) = new (New.init p)
525
526 "tail/new [Vector]" forall p.
527 tail (new p) = new (New.tail p)
528
529 "take/new [Vector]" forall n p.
530 take n (new p) = new (New.take n p)
531
532 "drop/new [Vector]" forall n p.
533 drop n (new p) = new (New.drop n p)
534
535 "unsafeSlice/new [Vector]" forall i n p.
536 unsafeSlice i n (new p) = new (New.unsafeSlice i n p)
537
538 "unsafeInit/new [Vector]" forall p.
539 unsafeInit (new p) = new (New.unsafeInit p)
540
541 "unsafeTail/new [Vector]" forall p.
542 unsafeTail (new p) = new (New.unsafeTail p)
543
544 #-}
545
546 -- Permutations
547 -- ------------
548
549 unsafeAccum_stream
550 :: Vector v a => (a -> b -> a) -> v a -> Stream (Int,b) -> v a
551 {-# INLINE unsafeAccum_stream #-}
552 unsafeAccum_stream f v s = s `seq` modify (\mv -> M.unsafeAccum f mv s) v
553
554 unsafeAccum :: Vector v a => (a -> b -> a) -> v a -> [(Int,b)] -> v a
555 {-# INLINE unsafeAccum #-}
556 unsafeAccum f v us = unsafeAccum_stream f v (Stream.fromList us)
557
558 unsafeAccumulate :: (Vector v a, Vector v (Int, b))
559 => (a -> b -> a) -> v a -> v (Int,b) -> v a
560 {-# INLINE unsafeAccumulate #-}
561 unsafeAccumulate f v us = unsafeAccum_stream f v (stream us)
562
563 unsafeAccumulate_ :: (Vector v a, Vector v Int, Vector v b)
564 => (a -> b -> a) -> v a -> v Int -> v b -> v a
565 {-# INLINE unsafeAccumulate_ #-}
566 unsafeAccumulate_ f v is xs
567 = unsafeAccum_stream f v (Stream.zipWith (,) (stream is) (stream xs))
568
569 accum_stream :: Vector v a => (a -> b -> a) -> v a -> Stream (Int,b) -> v a
570 {-# INLINE accum_stream #-}
571 accum_stream f v s = s `seq` modify (\mv -> M.accum f mv s) v
572
573 accum :: Vector v a => (a -> b -> a) -> v a -> [(Int,b)] -> v a
574 {-# INLINE accum #-}
575 accum f v us = accum_stream f v (Stream.fromList us)
576
577 accumulate :: (Vector v a, Vector v (Int, b))
578 => (a -> b -> a) -> v a -> v (Int,b) -> v a
579 {-# INLINE accumulate #-}
580 accumulate f v us = accum_stream f v (stream us)
581
582 accumulate_ :: (Vector v a, Vector v Int, Vector v b)
583 => (a -> b -> a) -> v a -> v Int -> v b -> v a
584 {-# INLINE accumulate_ #-}
585 accumulate_ f v is xs = accum_stream f v (Stream.zipWith (,) (stream is)
586 (stream xs))
587
588
589 unsafeUpdate_stream :: Vector v a => v a -> Stream (Int,a) -> v a
590 {-# INLINE unsafeUpdate_stream #-}
591 unsafeUpdate_stream v s = s `seq` modify (\mv -> M.unsafeUpdate mv s) v
592
593 unsafeUpd :: Vector v a => v a -> [(Int, a)] -> v a
594 {-# INLINE unsafeUpd #-}
595 unsafeUpd v us = unsafeUpdate_stream v (Stream.fromList us)
596
597 unsafeUpdate :: (Vector v a, Vector v (Int, a)) => v a -> v (Int, a) -> v a
598 {-# INLINE unsafeUpdate #-}
599 unsafeUpdate v w = unsafeUpdate_stream v (stream w)
600
601 unsafeUpdate_ :: (Vector v a, Vector v Int) => v a -> v Int -> v a -> v a
602 {-# INLINE unsafeUpdate_ #-}
603 unsafeUpdate_ v is w
604 = unsafeUpdate_stream v (Stream.zipWith (,) (stream is) (stream w))
605
606 update_stream :: Vector v a => v a -> Stream (Int,a) -> v a
607 {-# INLINE update_stream #-}
608 update_stream v s = s `seq` modify (\mv -> M.update mv s) v
609
610 (//) :: Vector v a => v a -> [(Int, a)] -> v a
611 {-# INLINE (//) #-}
612 v // us = update_stream v (Stream.fromList us)
613
614 update :: (Vector v a, Vector v (Int, a)) => v a -> v (Int, a) -> v a
615 {-# INLINE update #-}
616 update v w = update_stream v (stream w)
617
618 update_ :: (Vector v a, Vector v Int) => v a -> v Int -> v a -> v a
619 {-# INLINE update_ #-}
620 update_ v is w = update_stream v (Stream.zipWith (,) (stream is) (stream w))
621
622 -- This somewhat non-intuitive definition ensures that the resulting vector
623 -- does not retain references to the original one even if it is lazy in its
624 -- elements. This would not be the case if we simply used
625 --
626 -- backpermute v is = map (v!) is
627 backpermute :: (Vector v a, Vector v Int) => v a -> v Int -> v a
628 {-# INLINE backpermute #-}
629 backpermute v is = seq v
630 $ unstream
631 $ Stream.unbox
632 $ Stream.map (indexM v)
633 $ stream is
634
635 unsafeBackpermute :: (Vector v a, Vector v Int) => v a -> v Int -> v a
636 {-# INLINE unsafeBackpermute #-}
637 unsafeBackpermute v is = seq v
638 $ unstream
639 $ Stream.unbox
640 $ Stream.map (unsafeIndexM v)
641 $ stream is
642
643 -- FIXME: make this fuse better, add support for recycling
644 reverse :: (Vector v a) => v a -> v a
645 {-# INLINE reverse #-}
646 reverse = unstream . streamR
647
648 -- Mapping
649 -- -------
650
651 -- | Map a function over a vector
652 map :: (Vector v a, Vector v b) => (a -> b) -> v a -> v b
653 {-# INLINE map #-}
654 map f = unstream . inplace (MStream.map f) . stream
655
656 -- | Apply a function to every index/value pair
657 imap :: (Vector v a, Vector v b) => (Int -> a -> b) -> v a -> v b
658 {-# INLINE imap #-}
659 imap f = unstream . inplace (MStream.map (uncurry f) . MStream.indexed)
660 . stream
661
662 concatMap :: (Vector v a, Vector v b) => (a -> v b) -> v a -> v b
663 {-# INLINE concatMap #-}
664 concatMap f = unstream . Stream.concatMap (stream . f) . stream
665
666 -- Zipping/unzipping
667 -- -----------------
668
669 -- | Zip two vectors with the given function.
670 zipWith :: (Vector v a, Vector v b, Vector v c)
671 => (a -> b -> c) -> v a -> v b -> v c
672 {-# INLINE zipWith #-}
673 zipWith f xs ys = unstream (Stream.zipWith f (stream xs) (stream ys))
674
675 -- | Zip three vectors with the given function.
676 zipWith3 :: (Vector v a, Vector v b, Vector v c, Vector v d)
677 => (a -> b -> c -> d) -> v a -> v b -> v c -> v d
678 {-# INLINE zipWith3 #-}
679 zipWith3 f as bs cs = unstream (Stream.zipWith3 f (stream as)
680 (stream bs)
681 (stream cs))
682
683 zipWith4 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e)
684 => (a -> b -> c -> d -> e) -> v a -> v b -> v c -> v d -> v e
685 {-# INLINE zipWith4 #-}
686 zipWith4 f as bs cs ds
687 = unstream (Stream.zipWith4 f (stream as)
688 (stream bs)
689 (stream cs)
690 (stream ds))
691
692 zipWith5 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e,
693 Vector v f)
694 => (a -> b -> c -> d -> e -> f) -> v a -> v b -> v c -> v d -> v e
695 -> v f
696 {-# INLINE zipWith5 #-}
697 zipWith5 f as bs cs ds es
698 = unstream (Stream.zipWith5 f (stream as)
699 (stream bs)
700 (stream cs)
701 (stream ds)
702 (stream es))
703
704 zipWith6 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e,
705 Vector v f, Vector v g)
706 => (a -> b -> c -> d -> e -> f -> g)
707 -> v a -> v b -> v c -> v d -> v e -> v f -> v g
708 {-# INLINE zipWith6 #-}
709 zipWith6 f as bs cs ds es fs
710 = unstream (Stream.zipWith6 f (stream as)
711 (stream bs)
712 (stream cs)
713 (stream ds)
714 (stream es)
715 (stream fs))
716
717 -- | Zip two vectors and their indices with the given function.
718 izipWith :: (Vector v a, Vector v b, Vector v c)
719 => (Int -> a -> b -> c) -> v a -> v b -> v c
720 {-# INLINE izipWith #-}
721 izipWith f xs ys = unstream
722 (Stream.zipWith (uncurry f) (Stream.indexed (stream xs))
723 (stream ys))
724
725 -- | Zip three vectors and their indices with the given function.
726 izipWith3 :: (Vector v a, Vector v b, Vector v c, Vector v d)
727 => (Int -> a -> b -> c -> d) -> v a -> v b -> v c -> v d
728 {-# INLINE izipWith3 #-}
729 izipWith3 f as bs cs
730 = unstream (Stream.zipWith3 (uncurry f) (Stream.indexed (stream as))
731 (stream bs)
732 (stream cs))
733
734 izipWith4 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e)
735 => (Int -> a -> b -> c -> d -> e) -> v a -> v b -> v c -> v d -> v e
736 {-# INLINE izipWith4 #-}
737 izipWith4 f as bs cs ds
738 = unstream (Stream.zipWith4 (uncurry f) (Stream.indexed (stream as))
739 (stream bs)
740 (stream cs)
741 (stream ds))
742
743 izipWith5 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e,
744 Vector v f)
745 => (Int -> a -> b -> c -> d -> e -> f) -> v a -> v b -> v c -> v d
746 -> v e -> v f
747 {-# INLINE izipWith5 #-}
748 izipWith5 f as bs cs ds es
749 = unstream (Stream.zipWith5 (uncurry f) (Stream.indexed (stream as))
750 (stream bs)
751 (stream cs)
752 (stream ds)
753 (stream es))
754
755 izipWith6 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e,
756 Vector v f, Vector v g)
757 => (Int -> a -> b -> c -> d -> e -> f -> g)
758 -> v a -> v b -> v c -> v d -> v e -> v f -> v g
759 {-# INLINE izipWith6 #-}
760 izipWith6 f as bs cs ds es fs
761 = unstream (Stream.zipWith6 (uncurry f) (Stream.indexed (stream as))
762 (stream bs)
763 (stream cs)
764 (stream ds)
765 (stream es)
766 (stream fs))
767
768 zip :: (Vector v a, Vector v b, Vector v (a,b)) => v a -> v b -> v (a, b)
769 {-# INLINE zip #-}
770 zip = zipWith (,)
771
772 zip3 :: (Vector v a, Vector v b, Vector v c, Vector v (a, b, c))
773 => v a -> v b -> v c -> v (a, b, c)
774 {-# INLINE zip3 #-}
775 zip3 = zipWith3 (,,)
776
777 zip4 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v (a, b, c, d))
778 => v a -> v b -> v c -> v d -> v (a, b, c, d)
779 {-# INLINE zip4 #-}
780 zip4 = zipWith4 (,,,)
781
782 zip5 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e,
783 Vector v (a, b, c, d, e))
784 => v a -> v b -> v c -> v d -> v e -> v (a, b, c, d, e)
785 {-# INLINE zip5 #-}
786 zip5 = zipWith5 (,,,,)
787
788 zip6 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e,
789 Vector v f, Vector v (a, b, c, d, e, f))
790 => v a -> v b -> v c -> v d -> v e -> v f -> v (a, b, c, d, e, f)
791 {-# INLINE zip6 #-}
792 zip6 = zipWith6 (,,,,,)
793
794 unzip :: (Vector v a, Vector v b, Vector v (a,b)) => v (a, b) -> (v a, v b)
795 {-# INLINE unzip #-}
796 unzip xs = (map fst xs, map snd xs)
797
798 unzip3 :: (Vector v a, Vector v b, Vector v c, Vector v (a, b, c))
799 => v (a, b, c) -> (v a, v b, v c)
800 {-# INLINE unzip3 #-}
801 unzip3 xs = (map (\(a, b, c) -> a) xs,
802 map (\(a, b, c) -> b) xs,
803 map (\(a, b, c) -> c) xs)
804
805 unzip4 :: (Vector v a, Vector v b, Vector v c, Vector v d,
806 Vector v (a, b, c, d))
807 => v (a, b, c, d) -> (v a, v b, v c, v d)
808 {-# INLINE unzip4 #-}
809 unzip4 xs = (map (\(a, b, c, d) -> a) xs,
810 map (\(a, b, c, d) -> b) xs,
811 map (\(a, b, c, d) -> c) xs,
812 map (\(a, b, c, d) -> d) xs)
813
814 unzip5 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e,
815 Vector v (a, b, c, d, e))
816 => v (a, b, c, d, e) -> (v a, v b, v c, v d, v e)
817 {-# INLINE unzip5 #-}
818 unzip5 xs = (map (\(a, b, c, d, e) -> a) xs,
819 map (\(a, b, c, d, e) -> b) xs,
820 map (\(a, b, c, d, e) -> c) xs,
821 map (\(a, b, c, d, e) -> d) xs,
822 map (\(a, b, c, d, e) -> e) xs)
823
824 unzip6 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e,
825 Vector v f, Vector v (a, b, c, d, e, f))
826 => v (a, b, c, d, e, f) -> (v a, v b, v c, v d, v e, v f)
827 {-# INLINE unzip6 #-}
828 unzip6 xs = (map (\(a, b, c, d, e, f) -> a) xs,
829 map (\(a, b, c, d, e, f) -> b) xs,
830 map (\(a, b, c, d, e, f) -> c) xs,
831 map (\(a, b, c, d, e, f) -> d) xs,
832 map (\(a, b, c, d, e, f) -> e) xs,
833 map (\(a, b, c, d, e, f) -> f) xs)
834
835 -- Comparisons
836 -- -----------
837
838 eq :: (Vector v a, Eq a) => v a -> v a -> Bool
839 {-# INLINE eq #-}
840 xs `eq` ys = stream xs == stream ys
841
842 cmp :: (Vector v a, Ord a) => v a -> v a -> Ordering
843 {-# INLINE cmp #-}
844 cmp xs ys = compare (stream xs) (stream ys)
845
846 -- Filtering
847 -- ---------
848
849 -- | Drop elements that do not satisfy the predicate
850 filter :: Vector v a => (a -> Bool) -> v a -> v a
851 {-# INLINE filter #-}
852 filter f = unstream . inplace (MStream.filter f) . stream
853
854 -- | Drop elements that do not satisfy the predicate (applied to values and
855 -- their indices)
856 ifilter :: Vector v a => (Int -> a -> Bool) -> v a -> v a
857 {-# INLINE ifilter #-}
858 ifilter f = unstream
859 . inplace (MStream.map snd . MStream.filter (uncurry f)
860 . MStream.indexed)
861 . stream
862
863 -- | Yield the longest prefix of elements satisfying the predicate.
864 takeWhile :: Vector v a => (a -> Bool) -> v a -> v a
865 {-# INLINE takeWhile #-}
866 takeWhile f = unstream . Stream.takeWhile f . stream
867
868 -- | Drop the longest prefix of elements that satisfy the predicate.
869 dropWhile :: Vector v a => (a -> Bool) -> v a -> v a
870 {-# INLINE dropWhile #-}
871 dropWhile f = unstream . Stream.dropWhile f . stream
872
873 -- | Split the vector in two parts, the first one containing those elements
874 -- that satisfy the predicate and the second one those that don't. The
875 -- relative order of the elements is preserved at the cost of a (sometimes)
876 -- reduced performance compared to 'unstablePartition'.
877 partition :: Vector v a => (a -> Bool) -> v a -> (v a, v a)
878 {-# INLINE partition #-}
879 partition f = partition_stream f . stream
880
881 -- FIXME: Make this inplace-fusible (look at how stable_partition is
882 -- implemented in C++)
883
884 partition_stream :: Vector v a => (a -> Bool) -> Stream a -> (v a, v a)
885 {-# INLINE_STREAM partition_stream #-}
886 partition_stream f s = s `seq` runST (
887 do
888 (mv1,mv2) <- M.partitionStream f s
889 v1 <- unsafeFreeze mv1
890 v2 <- unsafeFreeze mv2
891 return (v1,v2))
892
893 -- | Split the vector in two parts, the first one containing those elements
894 -- that satisfy the predicate and the second one those that don't. The order
895 -- of the elements is not preserved but the operation is often faster than
896 -- 'partition'.
897 unstablePartition :: Vector v a => (a -> Bool) -> v a -> (v a, v a)
898 {-# INLINE unstablePartition #-}
899 unstablePartition f = unstablePartition_stream f . stream
900
901 unstablePartition_stream
902 :: Vector v a => (a -> Bool) -> Stream a -> (v a, v a)
903 {-# INLINE_STREAM unstablePartition_stream #-}
904 unstablePartition_stream f s = s `seq` runST (
905 do
906 (mv1,mv2) <- M.unstablePartitionStream f s
907 v1 <- unsafeFreeze mv1
908 v2 <- unsafeFreeze mv2
909 return (v1,v2))
910
911 unstablePartition_new :: Vector v a => (a -> Bool) -> New v a -> (v a, v a)
912 {-# INLINE_STREAM unstablePartition_new #-}
913 unstablePartition_new f (New.New p) = runST (
914 do
915 mv <- p
916 i <- M.unstablePartition f mv
917 v <- unsafeFreeze mv
918 return (unsafeTake i v, unsafeDrop i v))
919
920 {-# RULES
921
922 "unstablePartition" forall f p.
923 unstablePartition_stream f (stream (new p))
924 = unstablePartition_new f p
925
926 #-}
927
928
929 -- FIXME: make span and break fusible
930
931 -- | Split the vector into the longest prefix of elements that satisfy the
932 -- predicate and the rest.
933 span :: Vector v a => (a -> Bool) -> v a -> (v a, v a)
934 {-# INLINE span #-}
935 span f = break (not . f)
936
937 -- | Split the vector into the longest prefix of elements that do not satisfy
938 -- the predicate and the rest.
939 break :: Vector v a => (a -> Bool) -> v a -> (v a, v a)
940 {-# INLINE break #-}
941 break f xs = case findIndex f xs of
942 Just i -> (unsafeSlice 0 i xs, unsafeSlice i (length xs - i) xs)
943 Nothing -> (xs, empty)
944
945
946 -- Searching
947 -- ---------
948
949 infix 4 `elem`
950 -- | Check whether the vector contains an element
951 elem :: (Vector v a, Eq a) => a -> v a -> Bool
952 {-# INLINE elem #-}
953 elem x = Stream.elem x . stream
954
955 infix 4 `notElem`
956 -- | Inverse of `elem`
957 notElem :: (Vector v a, Eq a) => a -> v a -> Bool
958 {-# INLINE notElem #-}
959 notElem x = Stream.notElem x . stream
960
961 -- | Yield 'Just' the first element matching the predicate or 'Nothing' if no
962 -- such element exists.
963 find :: Vector v a => (a -> Bool) -> v a -> Maybe a
964 {-# INLINE find #-}
965 find f = Stream.find f . stream
966
967 -- | Yield 'Just' the index of the first element matching the predicate or
968 -- 'Nothing' if no such element exists.
969 findIndex :: Vector v a => (a -> Bool) -> v a -> Maybe Int
970 {-# INLINE findIndex #-}
971 findIndex f = Stream.findIndex f . stream
972
973 -- | Yield the indices of elements satisfying the predicate
974 findIndices :: (Vector v a, Vector v Int) => (a -> Bool) -> v a -> v Int
975 {-# INLINE findIndices #-}
976 findIndices f = unstream
977 . inplace (MStream.map fst . MStream.filter (f . snd)
978 . MStream.indexed)
979 . stream
980
981 -- | Yield 'Just' the index of the first occurence of the given element or
982 -- 'Nothing' if the vector does not contain the element
983 elemIndex :: (Vector v a, Eq a) => a -> v a -> Maybe Int
984 {-# INLINE elemIndex #-}
985 elemIndex x = findIndex (x==)
986
987 -- | Yield the indices of all occurences of the given element
988 elemIndices :: (Vector v a, Vector v Int, Eq a) => a -> v a -> v Int
989 {-# INLINE elemIndices #-}
990 elemIndices x = findIndices (x==)
991
992 -- Folding
993 -- -------
994
995 -- | Left fold
996 foldl :: Vector v b => (a -> b -> a) -> a -> v b -> a
997 {-# INLINE foldl #-}
998 foldl f z = Stream.foldl f z . stream
999
1000 -- | Left fold on non-empty vectors
1001 foldl1 :: Vector v a => (a -> a -> a) -> v a -> a
1002 {-# INLINE foldl1 #-}
1003 foldl1 f = Stream.foldl1 f . stream
1004
1005 -- | Left fold with strict accumulator
1006 foldl' :: Vector v b => (a -> b -> a) -> a -> v b -> a
1007 {-# INLINE foldl' #-}
1008 foldl' f z = Stream.foldl' f z . stream
1009
1010 -- | Left fold on non-empty vectors with strict accumulator
1011 foldl1' :: Vector v a => (a -> a -> a) -> v a -> a
1012 {-# INLINE foldl1' #-}
1013 foldl1' f = Stream.foldl1' f . stream
1014
1015 -- | Right fold
1016 foldr :: Vector v a => (a -> b -> b) -> b -> v a -> b
1017 {-# INLINE foldr #-}
1018 foldr f z = Stream.foldr f z . stream
1019
1020 -- | Right fold on non-empty vectors
1021 foldr1 :: Vector v a => (a -> a -> a) -> v a -> a
1022 {-# INLINE foldr1 #-}
1023 foldr1 f = Stream.foldr1 f . stream
1024
1025 -- | Right fold with a strict accumulator
1026 foldr' :: Vector v a => (a -> b -> b) -> b -> v a -> b
1027 {-# INLINE foldr' #-}
1028 foldr' f z = Stream.foldl' (flip f) z . streamR
1029
1030 -- | Right fold on non-empty vectors with strict accumulator
1031 foldr1' :: Vector v a => (a -> a -> a) -> v a -> a
1032 {-# INLINE foldr1' #-}
1033 foldr1' f = Stream.foldl1' (flip f) . streamR
1034
1035 -- | Left fold (function applied to each element and its index)
1036 ifoldl :: Vector v b => (a -> Int -> b -> a) -> a -> v b -> a
1037 {-# INLINE ifoldl #-}
1038 ifoldl f z = Stream.foldl (uncurry . f) z . Stream.indexed . stream
1039
1040 -- | Left fold with strict accumulator (function applied to each element and
1041 -- its index)
1042 ifoldl' :: Vector v b => (a -> Int -> b -> a) -> a -> v b -> a
1043 {-# INLINE ifoldl' #-}
1044 ifoldl' f z = Stream.foldl' (uncurry . f) z . Stream.indexed . stream
1045
1046 -- | Right fold (function applied to each element and its index)
1047 ifoldr :: Vector v a => (Int -> a -> b -> b) -> b -> v a -> b
1048 {-# INLINE ifoldr #-}
1049 ifoldr f z = Stream.foldr (uncurry f) z . Stream.indexed . stream
1050
1051 -- | Right fold with strict accumulator (function applied to each element and
1052 -- its index)
1053 ifoldr' :: Vector v a => (Int -> a -> b -> b) -> b -> v a -> b
1054 {-# INLINE ifoldr' #-}
1055 ifoldr' f z xs = Stream.foldl' (flip (uncurry f)) z
1056 $ Stream.indexedR (length xs) $ streamR xs
1057
1058 -- Specialised folds
1059 -- -----------------
1060
1061 all :: Vector v a => (a -> Bool) -> v a -> Bool
1062 {-# INLINE all #-}
1063 all f = Stream.and . Stream.map f . stream
1064
1065 any :: Vector v a => (a -> Bool) -> v a -> Bool
1066 {-# INLINE any #-}
1067 any f = Stream.or . Stream.map f . stream
1068
1069 and :: Vector v Bool => v Bool -> Bool
1070 {-# INLINE and #-}
1071 and = Stream.and . stream
1072
1073 or :: Vector v Bool => v Bool -> Bool
1074 {-# INLINE or #-}
1075 or = Stream.or . stream
1076
1077 sum :: (Vector v a, Num a) => v a -> a
1078 {-# INLINE sum #-}
1079 sum = Stream.foldl' (+) 0 . stream
1080
1081 product :: (Vector v a, Num a) => v a -> a
1082 {-# INLINE product #-}
1083 product = Stream.foldl' (*) 1 . stream
1084
1085 maximum :: (Vector v a, Ord a) => v a -> a
1086 {-# INLINE maximum #-}
1087 maximum = Stream.foldl1' max . stream
1088
1089 maximumBy :: Vector v a => (a -> a -> Ordering) -> v a -> a
1090 {-# INLINE maximumBy #-}
1091 maximumBy cmp = Stream.foldl1' maxBy . stream
1092 where
1093 {-# INLINE maxBy #-}
1094 maxBy x y = case cmp x y of
1095 LT -> y
1096 _ -> x
1097
1098 minimum :: (Vector v a, Ord a) => v a -> a
1099 {-# INLINE minimum #-}
1100 minimum = Stream.foldl1' min . stream
1101
1102 minimumBy :: Vector v a => (a -> a -> Ordering) -> v a -> a
1103 {-# INLINE minimumBy #-}
1104 minimumBy cmp = Stream.foldl1' minBy . stream
1105 where
1106 {-# INLINE minBy #-}
1107 minBy x y = case cmp x y of
1108 GT -> y
1109 _ -> x
1110
1111 maxIndex :: (Vector v a, Ord a) => v a -> Int
1112 {-# INLINE maxIndex #-}
1113 maxIndex = maxIndexBy compare
1114
1115 maxIndexBy :: Vector v a => (a -> a -> Ordering) -> v a -> Int
1116 {-# INLINE maxIndexBy #-}
1117 maxIndexBy cmp = fst . Stream.foldl1' imax . Stream.indexed . stream
1118 where
1119 imax (i,x) (j,y) = case cmp x y of
1120 LT -> (j,y)
1121 _ -> (i,x)
1122
1123 minIndex :: (Vector v a, Ord a) => v a -> Int
1124 {-# INLINE minIndex #-}
1125 minIndex = minIndexBy compare
1126
1127 minIndexBy :: Vector v a => (a -> a -> Ordering) -> v a -> Int
1128 {-# INLINE minIndexBy #-}
1129 minIndexBy cmp = fst . Stream.foldl1' imin . Stream.indexed . stream
1130 where
1131 imin (i,x) (j,y) = case cmp x y of
1132 GT -> (j,y)
1133 _ -> (i,x)
1134
1135
1136 -- Unfolding
1137 -- ---------
1138
1139 -- | Unfold
1140 unfoldr :: Vector v a => (b -> Maybe (a, b)) -> b -> v a
1141 {-# INLINE unfoldr #-}
1142 unfoldr f = unstream . Stream.unfoldr f
1143
1144 -- | Unfoldr at most @n@ elements.
1145 unfoldrN :: Vector v a => Int -> (b -> Maybe (a, b)) -> b -> v a
1146 {-# INLINE unfoldrN #-}
1147 unfoldrN n f = unstream . Stream.unfoldrN n f
1148
1149 -- Scans
1150 -- -----
1151
1152 -- | Prefix scan
1153 prescanl :: (Vector v a, Vector v b) => (a -> b -> a) -> a -> v b -> v a
1154 {-# INLINE prescanl #-}
1155 prescanl f z = unstream . inplace (MStream.prescanl f z) . stream
1156
1157 -- | Prefix scan with strict accumulator
1158 prescanl' :: (Vector v a, Vector v b) => (a -> b -> a) -> a -> v b -> v a
1159 {-# INLINE prescanl' #-}
1160 prescanl' f z = unstream . inplace (MStream.prescanl' f z) . stream
1161
1162 -- | Suffix scan
1163 postscanl :: (Vector v a, Vector v b) => (a -> b -> a) -> a -> v b -> v a
1164 {-# INLINE postscanl #-}
1165 postscanl f z = unstream . inplace (MStream.postscanl f z) . stream
1166
1167 -- | Suffix scan with strict accumulator
1168 postscanl' :: (Vector v a, Vector v b) => (a -> b -> a) -> a -> v b -> v a
1169 {-# INLINE postscanl' #-}
1170 postscanl' f z = unstream . inplace (MStream.postscanl' f z) . stream
1171
1172 -- | Haskell-style scan
1173 scanl :: (Vector v a, Vector v b) => (a -> b -> a) -> a -> v b -> v a
1174 {-# INLINE scanl #-}
1175 scanl f z = unstream . Stream.scanl f z . stream
1176
1177 -- | Haskell-style scan with strict accumulator
1178 scanl' :: (Vector v a, Vector v b) => (a -> b -> a) -> a -> v b -> v a
1179 {-# INLINE scanl' #-}
1180 scanl' f z = unstream . Stream.scanl' f z . stream
1181
1182 -- | Scan over a non-empty vector
1183 scanl1 :: Vector v a => (a -> a -> a) -> v a -> v a
1184 {-# INLINE scanl1 #-}
1185 scanl1 f = unstream . inplace (MStream.scanl1 f) . stream
1186
1187 -- | Scan over a non-empty vector with a strict accumulator
1188 scanl1' :: Vector v a => (a -> a -> a) -> v a -> v a
1189 {-# INLINE scanl1' #-}
1190 scanl1' f = unstream . inplace (MStream.scanl1' f) . stream
1191
1192
1193 -- | Prefix right-to-left scan
1194 prescanr :: (Vector v a, Vector v b) => (a -> b -> b) -> b -> v a -> v b
1195 {-# INLINE prescanr #-}
1196 prescanr f z = unstreamR . inplace (MStream.prescanl (flip f) z) . streamR
1197
1198 -- | Prefix right-to-left scan with strict accumulator
1199 prescanr' :: (Vector v a, Vector v b) => (a -> b -> b) -> b -> v a -> v b
1200 {-# INLINE prescanr' #-}
1201 prescanr' f z = unstreamR . inplace (MStream.prescanl' (flip f) z) . streamR
1202
1203 -- | Suffix right-to-left scan
1204 postscanr :: (Vector v a, Vector v b) => (a -> b -> b) -> b -> v a -> v b
1205 {-# INLINE postscanr #-}
1206 postscanr f z = unstreamR . inplace (MStream.postscanl (flip f) z) . streamR
1207
1208 -- | Suffix right-to-left scan with strict accumulator
1209 postscanr' :: (Vector v a, Vector v b) => (a -> b -> b) -> b -> v a -> v b
1210 {-# INLINE postscanr' #-}
1211 postscanr' f z = unstreamR . inplace (MStream.postscanl' (flip f) z) . streamR
1212
1213 -- | Haskell-style right-to-left scan
1214 scanr :: (Vector v a, Vector v b) => (a -> b -> b) -> b -> v a -> v b
1215 {-# INLINE scanr #-}
1216 scanr f z = unstreamR . Stream.scanl (flip f) z . streamR
1217
1218 -- | Haskell-style right-to-left scan with strict accumulator
1219 scanr' :: (Vector v a, Vector v b) => (a -> b -> b) -> b -> v a -> v b
1220 {-# INLINE scanr' #-}
1221 scanr' f z = unstreamR . Stream.scanl' (flip f) z . streamR
1222
1223 -- | Right-to-left scan over a non-empty vector
1224 scanr1 :: Vector v a => (a -> a -> a) -> v a -> v a
1225 {-# INLINE scanr1 #-}
1226 scanr1 f = unstreamR . inplace (MStream.scanl1 (flip f)) . streamR
1227
1228 -- | Right-to-left scan over a non-empty vector with a strict accumulator
1229 scanr1' :: Vector v a => (a -> a -> a) -> v a -> v a
1230 {-# INLINE scanr1' #-}
1231 scanr1' f = unstreamR . inplace (MStream.scanl1' (flip f)) . streamR
1232
1233 -- Enumeration
1234 -- -----------
1235
1236 -- | Yield a vector of the given length containing the values @x@, @x+1@ etc.
1237 -- This operation is usually more efficient than 'enumFromTo'.
1238 enumFromN :: (Vector v a, Num a) => a -> Int -> v a
1239 {-# INLINE enumFromN #-}
1240 enumFromN x n = enumFromStepN x 1 n
1241
1242 -- | Yield a vector of the given length containing the values @x@, @x+y@,
1243 -- @x+y+y@ etc. This operations is usually more efficient than
1244 -- 'enumFromThenTo'.
1245 enumFromStepN :: forall v a. (Vector v a, Num a) => a -> a -> Int -> v a
1246 {-# INLINE enumFromStepN #-}
1247 enumFromStepN x y n = elemseq (undefined :: v a) x
1248 $ elemseq (undefined :: v a) y
1249 $ unstream
1250 $ Stream.enumFromStepN x y n
1251
1252 -- | Enumerate values from @x@ to @y@.
1253 --
1254 -- /WARNING:/ This operation can be very inefficient. If at all possible, use
1255 -- 'enumFromN' instead.
1256 enumFromTo :: (Vector v a, Enum a) => a -> a -> v a
1257 {-# INLINE enumFromTo #-}
1258 enumFromTo x y = unstream (Stream.enumFromTo x y)
1259
1260 -- | Enumerate values from @x@ to @y@ with a specific step @z@.
1261 --
1262 -- /WARNING:/ This operation can be very inefficient. If at all possible, use
1263 -- 'enumFromStepN' instead.
1264 enumFromThenTo :: (Vector v a, Enum a) => a -> a -> a -> v a
1265 {-# INLINE enumFromThenTo #-}
1266 enumFromThenTo x y z = unstream (Stream.enumFromThenTo x y z)
1267
1268 -- | Convert a vector to a list
1269 toList :: Vector v a => v a -> [a]
1270 {-# INLINE toList #-}
1271 toList = Stream.toList . stream
1272
1273 -- | Convert a list to a vector
1274 fromList :: Vector v a => [a] -> v a
1275 {-# INLINE fromList #-}
1276 fromList = unstream . Stream.fromList
1277
1278 -- | Convert the first @n@ elements of a list to a vector
1279 --
1280 -- > fromListN n xs = fromList (take n xs)
1281 fromListN :: Vector v a => Int -> [a] -> v a
1282 {-# INLINE fromListN #-}
1283 fromListN n = unstream . Stream.fromListN n
1284
1285 -- Utilities for defining Data instances
1286 -- -------------------------------------
1287
1288 -- | Generic definion of 'Data.Data.gfoldl' that views a 'Vector' as a
1289 -- list.
1290 gfoldl :: (Vector v a, Data a)
1291 => (forall d b. Data d => c (d -> b) -> d -> c b)
1292 -> (forall g. g -> c g)
1293 -> v a
1294 -> c (v a)
1295 {-# INLINE gfoldl #-}
1296 gfoldl f z v = z fromList `f` toList v
1297
1298 mkType :: String -> DataType
1299 {-# INLINE mkType #-}
1300 mkType = mkNorepType
1301
1302 dataCast :: (Vector v a, Data a, Typeable1 v, Typeable1 t)
1303 => (forall d. Data d => c (t d)) -> Maybe (c (v a))
1304 {-# INLINE dataCast #-}
1305 dataCast f = gcast1 f
1306