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