Export create, modify and copy/unsafeCopy
[darcs-mirrors/vector.git] / Data / Vector.hs
1 {-# LANGUAGE FlexibleInstances, MultiParamTypeClasses, TypeFamilies, Rank2Types #-}
2
3 -- |
4 -- Module : Data.Vector
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 -- A library for boxed vectors (that is, polymorphic arrays capable of
13 -- holding any Haskell value). The vectors come in two flavors:
14 --
15 -- * mutable
16 --
17 -- * immutable
18 --
19 -- and support a rich interface of both list-like operations, and bulk
20 -- array operations.
21 --
22 -- For unboxed arrays, use the 'Data.Vector.Unboxed' interface.
23 --
24
25 module Data.Vector (
26
27 -- * The pure and mutable array types
28 Vector, MVector,
29
30 -- * Constructing vectors
31 empty,
32 singleton,
33 cons,
34 snoc,
35 (++),
36 replicate,
37 generate,
38 force,
39
40 -- * Operations based on length information
41 length,
42 null,
43
44 -- * Accessing individual elements
45 (!),
46 head,
47 last,
48
49 -- ** Accessors in a monad
50 indexM,
51 headM,
52 lastM,
53
54 -- ** Accessor functions with no bounds checking
55 unsafeIndex, unsafeHead, unsafeLast,
56 unsafeIndexM, unsafeHeadM, unsafeLastM,
57
58 -- * Subvectors
59 init,
60 tail,
61 take,
62 drop,
63 slice,
64
65 -- * Subvector construction without bounds checks
66 unsafeSlice, unsafeInit, unsafeTail, unsafeTake, unsafeDrop,
67
68 -- * Permutations
69 accum, accumulate, accumulate_,
70 (//), update, update_,
71 backpermute, reverse,
72 unsafeAccum, unsafeAccumulate, unsafeAccumulate_,
73 unsafeUpd, unsafeUpdate, unsafeUpdate_,
74 unsafeBackpermute,
75
76 -- * Mapping
77 map, imap, concatMap,
78
79 -- * Zipping and unzipping
80 zipWith, zipWith3, zipWith4, zipWith5, zipWith6,
81 izipWith, izipWith3, izipWith4, izipWith5, izipWith6,
82 zip, zip3, zip4, zip5, zip6,
83 unzip, unzip3, unzip4, unzip5, unzip6,
84
85 -- * Filtering
86 filter, ifilter, takeWhile, dropWhile,
87 partition, unstablePartition, span, break,
88
89 -- * Searching
90 elem, notElem, find, findIndex, findIndices, elemIndex, elemIndices,
91
92 -- * Folding
93 foldl, foldl1, foldl', foldl1', foldr, foldr1, foldr', foldr1',
94 ifoldl, ifoldl', ifoldr, ifoldr',
95
96 -- * Specialised folds
97 all, any, and, or,
98 sum, product,
99 maximum, maximumBy, minimum, minimumBy,
100 minIndex, minIndexBy, maxIndex, maxIndexBy,
101
102 -- * Unfolding
103 unfoldr, unfoldrN,
104
105 -- * Scans
106 prescanl, prescanl',
107 postscanl, postscanl',
108 scanl, scanl', scanl1, scanl1',
109 prescanr, prescanr',
110 postscanr, postscanr',
111 scanr, scanr', scanr1, scanr1',
112
113 -- * Enumeration
114 enumFromN, enumFromStepN, enumFromTo, enumFromThenTo,
115
116 -- * Conversion to/from lists
117 toList, fromList, fromListN,
118
119 -- * Destructive operations
120 create, modify, copy, unsafeCopy
121 ) where
122
123 import qualified Data.Vector.Generic as G
124 import Data.Vector.Mutable ( MVector(..) )
125 import Data.Primitive.Array
126 import qualified Data.Vector.Fusion.Stream as Stream
127
128 import Control.Monad ( liftM )
129 import Control.Monad.ST ( ST )
130 import Control.Monad.Primitive
131
132 import Prelude hiding ( length, null,
133 replicate, (++),
134 head, last,
135 init, tail, take, drop, reverse,
136 map, concatMap,
137 zipWith, zipWith3, zip, zip3, unzip, unzip3,
138 filter, takeWhile, dropWhile, span, break,
139 elem, notElem,
140 foldl, foldl1, foldr, foldr1,
141 all, any, and, or, sum, product, minimum, maximum,
142 scanl, scanl1, scanr, scanr1,
143 enumFromTo, enumFromThenTo )
144
145 import qualified Prelude
146
147 import Data.Typeable ( Typeable )
148 import Data.Data ( Data(..) )
149
150 -- | Boxed vectors, supporting efficient slicing.
151 data Vector a = Vector {-# UNPACK #-} !Int
152 {-# UNPACK #-} !Int
153 {-# UNPACK #-} !(Array a)
154 deriving ( Typeable )
155
156 instance Show a => Show (Vector a) where
157 show = (Prelude.++ " :: Data.Vector.Vector") . ("fromList " Prelude.++) . show . toList
158
159 instance Data a => Data (Vector a) where
160 gfoldl = G.gfoldl
161 toConstr _ = error "toConstr"
162 gunfold _ _ = error "gunfold"
163 dataTypeOf _ = G.mkType "Data.Vector.Vector"
164 dataCast1 = G.dataCast
165
166 type instance G.Mutable Vector = MVector
167
168 instance G.Vector Vector a where
169 {-# INLINE unsafeFreeze #-}
170 unsafeFreeze (MVector i n marr)
171 = Vector i n `liftM` unsafeFreezeArray marr
172
173 {-# INLINE basicLength #-}
174 basicLength (Vector _ n _) = n
175
176 {-# INLINE basicUnsafeSlice #-}
177 basicUnsafeSlice j n (Vector i _ arr) = Vector (i+j) n arr
178
179 {-# INLINE basicUnsafeIndexM #-}
180 basicUnsafeIndexM (Vector i _ arr) j = indexArrayM arr (i+j)
181
182 -- See [HACKS:Eq and Ord instances]
183 instance Eq a => Eq (Vector a) where
184 {-# INLINE (==) #-}
185 xs == ys = Stream.eq (G.stream xs) (G.stream ys)
186
187 {-# INLINE (/=) #-}
188 xs /= ys = not (Stream.eq (G.stream xs) (G.stream ys))
189
190 -- See [HACKS:Eq and Ord instances]
191 instance Ord a => Ord (Vector a) where
192 {-# INLINE compare #-}
193 compare xs ys = Stream.cmp (G.stream xs) (G.stream ys)
194
195 {-# INLINE (<) #-}
196 xs < ys = Stream.cmp (G.stream xs) (G.stream ys) == LT
197
198 {-# INLINE (<=) #-}
199 xs <= ys = Stream.cmp (G.stream xs) (G.stream ys) /= GT
200
201 {-# INLINE (>) #-}
202 xs > ys = Stream.cmp (G.stream xs) (G.stream ys) == GT
203
204 {-# INLINE (>=) #-}
205 xs >= ys = Stream.cmp (G.stream xs) (G.stream ys) /= LT
206
207 -- Length
208 -- ------
209
210 -- |/O(1)/. Yield the length of a vector as an 'Int'
211 length :: Vector a -> Int
212 {-# INLINE length #-}
213 length = G.length
214
215 -- |/O(1)/. 'null' tests whether the given array is empty.
216 null :: Vector a -> Bool
217 {-# INLINE null #-}
218 null = G.null
219
220 -- Construction
221 -- ------------
222
223 -- |/O(1)/. 'empty' builds a vector of size zero.
224 empty :: Vector a
225 {-# INLINE empty #-}
226 empty = G.empty
227
228 -- |/O(1)/, Vector with exactly one element
229 singleton :: a -> Vector a
230 {-# INLINE singleton #-}
231 singleton = G.singleton
232
233 -- |/O(n)/. @'replicate' n e@ yields a vector of length @n@ storing @e@ at each position
234 replicate :: Int -> a -> Vector a
235 {-# INLINE replicate #-}
236 replicate = G.replicate
237
238 -- |/O(n)/, Generate a vector of the given length by applying a (pure)
239 -- generator function to each index
240 generate :: Int -> (Int -> a) -> Vector a
241 {-# INLINE generate #-}
242 generate = G.generate
243
244 -- |/O(n)/, Prepend an element to an array.
245 cons :: a -> Vector a -> Vector a
246 {-# INLINE cons #-}
247 cons = G.cons
248
249 -- |/O(n)/, Append an element to an array.
250 snoc :: Vector a -> a -> Vector a
251 {-# INLINE snoc #-}
252 snoc = G.snoc
253
254 infixr 5 ++
255
256 -- |/O(n)/, Concatenate two vectors
257 (++) :: Vector a -> Vector a -> Vector a
258 {-# INLINE (++) #-}
259 (++) = (G.++)
260
261 -- |/O(n)/, Create a copy of a vector.
262 -- @force@ is useful when dealing with slices, as the garbage collector
263 -- may be able to free the original vector if no further references are held.
264 --
265 force :: Vector a -> Vector a
266 {-# INLINE force #-}
267 force = G.force
268
269 -- Accessing individual elements
270 -- -----------------------------
271
272 -- |/O(1)/. Read the element in the vector at the given index.
273 (!) :: Vector a -> Int -> a
274 {-# INLINE (!) #-}
275 (!) = (G.!)
276
277 -- |/O(1)/. 'head' returns the first element of the vector
278 head :: Vector a -> a
279 {-# INLINE head #-}
280 head = G.head
281
282 -- |/O(n)/. 'last' yields the last element of an array.
283 last :: Vector a -> a
284 {-# INLINE last #-}
285 last = G.last
286
287 -- |/O(1)/, Unsafe indexing without bounds checking
288 --
289 -- By not performing bounds checks, this function may be faster when
290 -- this function is used in an inner loop)
291 --
292 unsafeIndex :: Vector a -> Int -> a
293 {-# INLINE unsafeIndex #-}
294 unsafeIndex = G.unsafeIndex
295
296 -- |/O(1)/, Yield the first element of a vector without checking if the vector is empty
297 --
298 -- By not performing bounds checks, this function may be faster when
299 -- this function is used in an inner loop)
300 unsafeHead :: Vector a -> a
301 {-# INLINE unsafeHead #-}
302 unsafeHead = G.unsafeHead
303
304 -- | Yield the last element of a vector without checking if the vector is empty
305 --
306 -- By not performing bounds checks, this function may be faster when
307 -- this function is used in an inner loop)
308 unsafeLast :: Vector a -> a
309 {-# INLINE unsafeLast #-}
310 unsafeLast = G.unsafeLast
311
312 -- | Monadic indexing which can be strict in the vector while remaining lazy in the element
313 indexM :: Monad m => Vector a -> Int -> m a
314 {-# INLINE indexM #-}
315 indexM = G.indexM
316
317 -- | Monadic head which can be strict in the vector while remaining lazy in the element
318 headM :: Monad m => Vector a -> m a
319 {-# INLINE headM #-}
320 headM = G.headM
321
322 -- | Monadic last which can be strict in the vector while remaining lazy in the element
323 lastM :: Monad m => Vector a -> m a
324 {-# INLINE lastM #-}
325 lastM = G.lastM
326
327 -- | Unsafe monadic indexing without bounds checks
328 unsafeIndexM :: Monad m => Vector a -> Int -> m a
329 {-# INLINE unsafeIndexM #-}
330 unsafeIndexM = G.unsafeIndexM
331
332 -- | Unsafe monadic head (access the first element) without bounds checks
333 unsafeHeadM :: Monad m => Vector a -> m a
334 {-# INLINE unsafeHeadM #-}
335 unsafeHeadM = G.unsafeHeadM
336
337 -- | Unsafe monadic last (access the last element) without bounds checks
338 unsafeLastM :: Monad m => Vector a -> m a
339 {-# INLINE unsafeLastM #-}
340 unsafeLastM = G.unsafeLastM
341
342 -- Subarrays
343 -- ---------
344
345 -- | /O(1)/, Yield a part of the vector without copying it.
346 --
347 slice :: Int -- ^ starting index
348 -> Int -- ^ length
349 -> Vector a
350 -> Vector a
351 {-# INLINE slice #-}
352 slice = G.slice
353
354 -- |/O(1)/, Yield all but the last element without copying.
355 init :: Vector a -> Vector a
356 {-# INLINE init #-}
357 init = G.init
358
359 -- |/O(1), Yield all but the first element (without copying).
360 tail :: Vector a -> Vector a
361 {-# INLINE tail #-}
362 tail = G.tail
363
364 -- |/O(1)/, Yield the first @n@ elements without copying.
365 take :: Int -> Vector a -> Vector a
366 {-# INLINE take #-}
367 take = G.take
368
369 -- |/O(1)/, Yield all but the first @n@ elements without copying.
370 drop :: Int -> Vector a -> Vector a
371 {-# INLINE drop #-}
372 drop = G.drop
373
374 -- |/O(1)/, Unsafely yield a part of the vector without copying it and without
375 -- performing bounds checks.
376 unsafeSlice :: Int -- ^ starting index
377 -> Int -- ^ length
378 -> Vector a
379 -> Vector a
380 {-# INLINE unsafeSlice #-}
381 unsafeSlice = G.unsafeSlice
382
383 -- |/O(1)/, Zero-copying 'init' without bounds checks.
384 unsafeInit :: Vector a -> Vector a
385 {-# INLINE unsafeInit #-}
386 unsafeInit = G.unsafeInit
387
388 -- |/O(1)/, Zero-copying 'tail' without bounds checks.
389 unsafeTail :: Vector a -> Vector a
390 {-# INLINE unsafeTail #-}
391 unsafeTail = G.unsafeTail
392
393 -- |/O(1)/, Zero-copying 'take' without bounds checks.
394 unsafeTake :: Int -> Vector a -> Vector a
395 {-# INLINE unsafeTake #-}
396 unsafeTake = G.unsafeTake
397
398 -- |/O(1)/, Zero-copying 'drop' without bounds checks.
399 unsafeDrop :: Int -> Vector a -> Vector a
400 {-# INLINE unsafeDrop #-}
401 unsafeDrop = G.unsafeDrop
402
403 -- Permutations
404 -- ------------
405
406 -- TODO there is no documentation for the accum* family of functions
407
408 -- | TODO unsafeAccum.
409 unsafeAccum :: (a -> b -> a) -> Vector a -> [(Int,b)] -> Vector a
410 {-# INLINE unsafeAccum #-}
411 unsafeAccum = G.unsafeAccum
412
413 -- | TODO unsafeAccumulate
414 unsafeAccumulate :: (a -> b -> a) -> Vector a -> Vector (Int,b) -> Vector a
415 {-# INLINE unsafeAccumulate #-}
416 unsafeAccumulate = G.unsafeAccumulate
417
418 -- | TODO unsafeAccumulate_
419 unsafeAccumulate_
420 :: (a -> b -> a) -> Vector a -> Vector Int -> Vector b -> Vector a
421 {-# INLINE unsafeAccumulate_ #-}
422 unsafeAccumulate_ = G.unsafeAccumulate_
423
424 -- | TODO accum
425 accum :: (a -> b -> a) -> Vector a -> [(Int,b)] -> Vector a
426 {-# INLINE accum #-}
427 accum = G.accum
428
429 -- | TODO accumulate
430 accumulate :: (a -> b -> a) -> Vector a -> Vector (Int,b) -> Vector a
431 {-# INLINE accumulate #-}
432 accumulate = G.accumulate
433
434 -- | TODO accumulate_
435 accumulate_ :: (a -> b -> a) -> Vector a -> Vector Int -> Vector b -> Vector a
436 {-# INLINE accumulate_ #-}
437 accumulate_ = G.accumulate_
438
439 -- | TODO unsafeUpd
440 unsafeUpd :: Vector a -> [(Int, a)] -> Vector a
441 {-# INLINE unsafeUpd #-}
442 unsafeUpd = G.unsafeUpd
443
444 -- | TODO unsafeUpdate
445 unsafeUpdate :: Vector a -> Vector (Int, a) -> Vector a
446 {-# INLINE unsafeUpdate #-}
447 unsafeUpdate = G.unsafeUpdate
448
449 -- | TODO unsafeUpdate_
450 unsafeUpdate_ :: Vector a -> Vector Int -> Vector a -> Vector a
451 {-# INLINE unsafeUpdate_ #-}
452 unsafeUpdate_ = G.unsafeUpdate_
453
454 -- | TODO (//)
455 (//) :: Vector a -> [(Int, a)] -> Vector a
456 {-# INLINE (//) #-}
457 (//) = (G.//)
458
459 -- | TODO update
460 update :: Vector a -> Vector (Int, a) -> Vector a
461 {-# INLINE update #-}
462 update = G.update
463
464 -- | TODO update_
465 update_ :: Vector a -> Vector Int -> Vector a -> Vector a
466 {-# INLINE update_ #-}
467 update_ = G.update_
468
469 -- | backpermute, courtesy Blelloch. The back-permute is a gather\/get operation.
470 backpermute :: Vector a -> Vector Int -> Vector a
471 {-# INLINE backpermute #-}
472 backpermute = G.backpermute
473
474 -- | TODO unsafeBackpermute
475 unsafeBackpermute :: Vector a -> Vector Int -> Vector a
476 {-# INLINE unsafeBackpermute #-}
477 unsafeBackpermute = G.unsafeBackpermute
478
479 -- | /O(n)/, reverse the elements of the given vector.
480 reverse :: Vector a -> Vector a
481 {-# INLINE reverse #-}
482 reverse = G.reverse
483
484 -- Mapping
485 -- -------
486
487 -- | /O(n)/, Map a function over a vector
488 map :: (a -> b) -> Vector a -> Vector b
489 {-# INLINE map #-}
490 map = G.map
491
492 -- | /O(n)/, Apply a function to every index/value pair yielding a new vector
493 imap :: (Int -> a -> b) -> Vector a -> Vector b
494 {-# INLINE imap #-}
495 imap = G.imap
496
497 -- | /O(n)/, generate a vector from each element of the input vector, then join the results.
498 concatMap :: (a -> Vector b) -> Vector a -> Vector b
499 {-# INLINE concatMap #-}
500 concatMap = G.concatMap
501
502 -- Zipping/unzipping
503 -- -----------------
504
505 -- |/O(n)/, Zip two vectors with the given function.
506 zipWith :: (a -> b -> c) -> Vector a -> Vector b -> Vector c
507 {-# INLINE zipWith #-}
508 zipWith = G.zipWith
509
510 -- |/O(n)/, Zip three vectors with the given function.
511 zipWith3 :: (a -> b -> c -> d) -> Vector a -> Vector b -> Vector c -> Vector d
512 {-# INLINE zipWith3 #-}
513 zipWith3 = G.zipWith3
514
515 -- |/O(n)/, Zip four vectors with the given function.
516 zipWith4 :: (a -> b -> c -> d -> e)
517 -> Vector a -> Vector b -> Vector c -> Vector d -> Vector e
518 {-# INLINE zipWith4 #-}
519 zipWith4 = G.zipWith4
520
521 -- |/O(n)/, Zip five vectors with the given function.
522 zipWith5 :: (a -> b -> c -> d -> e -> f)
523 -> Vector a -> Vector b -> Vector c -> Vector d -> Vector e
524 -> Vector f
525 {-# INLINE zipWith5 #-}
526 zipWith5 = G.zipWith5
527
528 -- |/O(n)/, Zip six vectors with the given function.
529 zipWith6 :: (a -> b -> c -> d -> e -> f -> g)
530 -> Vector a -> Vector b -> Vector c -> Vector d -> Vector e
531 -> Vector f -> Vector g
532 {-# INLINE zipWith6 #-}
533 zipWith6 = G.zipWith6
534
535 -- |/O(n)/, Zip two vectors and their indices with the given function.
536 izipWith :: (Int -> a -> b -> c) -> Vector a -> Vector b -> Vector c
537 {-# INLINE izipWith #-}
538 izipWith = G.izipWith
539
540 -- |/O(n)/, Zip three vectors and their indices with the given function.
541 izipWith3 :: (Int -> a -> b -> c -> d)
542 -> Vector a -> Vector b -> Vector c -> Vector d
543 {-# INLINE izipWith3 #-}
544 izipWith3 = G.izipWith3
545
546 -- |/O(n)/, Zip four vectors and their indices with the given function.
547 izipWith4 :: (Int -> a -> b -> c -> d -> e)
548 -> Vector a -> Vector b -> Vector c -> Vector d -> Vector e
549 {-# INLINE izipWith4 #-}
550 izipWith4 = G.izipWith4
551
552 -- |/O(n)/, Zip five vectors and their indices with the given function.
553 izipWith5 :: (Int -> a -> b -> c -> d -> e -> f)
554 -> Vector a -> Vector b -> Vector c -> Vector d -> Vector e
555 -> Vector f
556 {-# INLINE izipWith5 #-}
557 izipWith5 = G.izipWith5
558
559 -- |/O(n)/, Zip six vectors and their indices with the given function.
560 izipWith6 :: (Int -> a -> b -> c -> d -> e -> f -> g)
561 -> Vector a -> Vector b -> Vector c -> Vector d -> Vector e
562 -> Vector f -> Vector g
563 {-# INLINE izipWith6 #-}
564 izipWith6 = G.izipWith6
565
566 -- | Elementwise pairing of array elements.
567 zip :: Vector a -> Vector b -> Vector (a, b)
568 {-# INLINE zip #-}
569 zip = G.zip
570
571 -- | zip together three vectors into a vector of triples
572 zip3 :: Vector a -> Vector b -> Vector c -> Vector (a, b, c)
573 {-# INLINE zip3 #-}
574 zip3 = G.zip3
575
576 zip4 :: Vector a -> Vector b -> Vector c -> Vector d
577 -> Vector (a, b, c, d)
578 {-# INLINE zip4 #-}
579 zip4 = G.zip4
580
581 zip5 :: Vector a -> Vector b -> Vector c -> Vector d -> Vector e
582 -> Vector (a, b, c, d, e)
583 {-# INLINE zip5 #-}
584 zip5 = G.zip5
585
586 zip6 :: Vector a -> Vector b -> Vector c -> Vector d -> Vector e -> Vector f
587 -> Vector (a, b, c, d, e, f)
588 {-# INLINE zip6 #-}
589 zip6 = G.zip6
590
591 -- | Elementwise unpairing of array elements.
592 unzip :: Vector (a, b) -> (Vector a, Vector b)
593 {-# INLINE unzip #-}
594 unzip = G.unzip
595
596 unzip3 :: Vector (a, b, c) -> (Vector a, Vector b, Vector c)
597 {-# INLINE unzip3 #-}
598 unzip3 = G.unzip3
599
600 unzip4 :: Vector (a, b, c, d) -> (Vector a, Vector b, Vector c, Vector d)
601 {-# INLINE unzip4 #-}
602 unzip4 = G.unzip4
603
604 unzip5 :: Vector (a, b, c, d, e)
605 -> (Vector a, Vector b, Vector c, Vector d, Vector e)
606 {-# INLINE unzip5 #-}
607 unzip5 = G.unzip5
608
609 unzip6 :: Vector (a, b, c, d, e, f)
610 -> (Vector a, Vector b, Vector c, Vector d, Vector e, Vector f)
611 {-# INLINE unzip6 #-}
612 unzip6 = G.unzip6
613
614 -- Filtering
615 -- ---------
616
617 -- |/O(n)/, Remove elements from the vector which do not satisfy the predicate
618 filter :: (a -> Bool) -> Vector a -> Vector a
619 {-# INLINE filter #-}
620 filter = G.filter
621
622 -- |/O(n)/, Drop elements that do not satisfy the predicate (applied to values and
623 -- their indices)
624 ifilter :: (Int -> a -> Bool) -> Vector a -> Vector a
625 {-# INLINE ifilter #-}
626 ifilter = G.ifilter
627
628 -- |/O(n)/, Yield the longest prefix of elements satisfying the predicate.
629 takeWhile :: (a -> Bool) -> Vector a -> Vector a
630 {-# INLINE takeWhile #-}
631 takeWhile = G.takeWhile
632
633 -- |/O(n)/, Drop the longest prefix of elements that satisfy the predicate.
634 dropWhile :: (a -> Bool) -> Vector a -> Vector a
635 {-# INLINE dropWhile #-}
636 dropWhile = G.dropWhile
637
638 -- | Split the vector in two parts, the first one containing those elements
639 -- that satisfy the predicate and the second one those that don't. The
640 -- relative order of the elements is preserved at the cost of a (sometimes)
641 -- reduced performance compared to 'unstablePartition'.
642 partition :: (a -> Bool) -> Vector a -> (Vector a, Vector a)
643 {-# INLINE partition #-}
644 partition = G.partition
645
646 -- |/O(n)/, Split the vector in two parts, the first one containing those elements
647 -- that satisfy the predicate and the second one those that don't. The order
648 -- of the elements is not preserved.
649 unstablePartition :: (a -> Bool) -> Vector a -> (Vector a, Vector a)
650 {-# INLINE unstablePartition #-}
651 unstablePartition = G.unstablePartition
652
653 -- |/O(n)/, Split the vector into the longest prefix of elements that satisfy the
654 -- predicate and the rest.
655 span :: (a -> Bool) -> Vector a -> (Vector a, Vector a)
656 {-# INLINE span #-}
657 span = G.span
658
659 -- | Split the vector into the longest prefix of elements that do not satisfy
660 -- the predicate and the rest.
661 break :: (a -> Bool) -> Vector a -> (Vector a, Vector a)
662 {-# INLINE break #-}
663 break = G.break
664
665 -- Searching
666 -- ---------
667
668 infix 4 `elem`
669 -- | Check whether the vector contains an element
670 elem :: Eq a => a -> Vector a -> Bool
671 {-# INLINE elem #-}
672 elem = G.elem
673
674 infix 4 `notElem`
675 -- | Inverse of `elem`
676 notElem :: Eq a => a -> Vector a -> Bool
677 {-# INLINE notElem #-}
678 notElem = G.notElem
679
680 -- | Yield 'Just' the first element matching the predicate or 'Nothing' if no
681 -- such element exists.
682 find :: (a -> Bool) -> Vector a -> Maybe a
683 {-# INLINE find #-}
684 find = G.find
685
686 -- | Yield 'Just' the index of the first element matching the predicate or
687 -- 'Nothing' if no such element exists.
688 findIndex :: (a -> Bool) -> Vector a -> Maybe Int
689 {-# INLINE findIndex #-}
690 findIndex = G.findIndex
691
692 -- | Yield the indices of elements satisfying the predicate
693 findIndices :: (a -> Bool) -> Vector a -> Vector Int
694 {-# INLINE findIndices #-}
695 findIndices = G.findIndices
696
697 -- | Yield 'Just' the index of the first occurence of the given element or
698 -- 'Nothing' if the vector does not contain the element
699 elemIndex :: Eq a => a -> Vector a -> Maybe Int
700 {-# INLINE elemIndex #-}
701 elemIndex = G.elemIndex
702
703 -- | Yield the indices of all occurences of the given element
704 elemIndices :: Eq a => a -> Vector a -> Vector Int
705 {-# INLINE elemIndices #-}
706 elemIndices = G.elemIndices
707
708 -- Folding
709 -- -------
710
711 -- | Left fold
712 foldl :: (a -> b -> a) -> a -> Vector b -> a
713 {-# INLINE foldl #-}
714 foldl = G.foldl
715
716 -- | Left fold on non-empty vectors
717 foldl1 :: (a -> a -> a) -> Vector a -> a
718 {-# INLINE foldl1 #-}
719 foldl1 = G.foldl1
720
721 -- | Left fold with strict accumulator
722 foldl' :: (a -> b -> a) -> a -> Vector b -> a
723 {-# INLINE foldl' #-}
724 foldl' = G.foldl'
725
726 -- | Left fold on non-empty vectors with strict accumulator
727 foldl1' :: (a -> a -> a) -> Vector a -> a
728 {-# INLINE foldl1' #-}
729 foldl1' = G.foldl1'
730
731 -- | Right fold
732 foldr :: (a -> b -> b) -> b -> Vector a -> b
733 {-# INLINE foldr #-}
734 foldr = G.foldr
735
736 -- | Right fold on non-empty vectors
737 foldr1 :: (a -> a -> a) -> Vector a -> a
738 {-# INLINE foldr1 #-}
739 foldr1 = G.foldr1
740
741 -- | Right fold with a strict accumulator
742 foldr' :: (a -> b -> b) -> b -> Vector a -> b
743 {-# INLINE foldr' #-}
744 foldr' = G.foldr'
745
746 -- | Right fold on non-empty vectors with strict accumulator
747 foldr1' :: (a -> a -> a) -> Vector a -> a
748 {-# INLINE foldr1' #-}
749 foldr1' = G.foldr1'
750
751 -- | Left fold (function applied to each element and its index)
752 ifoldl :: (a -> Int -> b -> a) -> a -> Vector b -> a
753 {-# INLINE ifoldl #-}
754 ifoldl = G.ifoldl
755
756 -- | Left fold with strict accumulator (function applied to each element and
757 -- its index)
758 ifoldl' :: (a -> Int -> b -> a) -> a -> Vector b -> a
759 {-# INLINE ifoldl' #-}
760 ifoldl' = G.ifoldl'
761
762 -- | Right fold (function applied to each element and its index)
763 ifoldr :: (Int -> a -> b -> b) -> b -> Vector a -> b
764 {-# INLINE ifoldr #-}
765 ifoldr = G.ifoldr
766
767 -- | Right fold with strict accumulator (function applied to each element and
768 -- its index)
769 ifoldr' :: (Int -> a -> b -> b) -> b -> Vector a -> b
770 {-# INLINE ifoldr' #-}
771 ifoldr' = G.ifoldr'
772
773 -- Specialised folds
774 -- -----------------
775
776 -- |/O(n)/. @'all' p u@ determines whether all elements in array @u@ satisfy
777 -- predicate @p@.
778 all :: (a -> Bool) -> Vector a -> Bool
779 {-# INLINE all #-}
780 all = G.all
781
782 -- |/O(n)/. @'any' p u@ determines whether any element in array @u@ satisfies
783 -- predicate @p@.
784 any :: (a -> Bool) -> Vector a -> Bool
785 {-# INLINE any #-}
786 any = G.any
787
788 -- |/O(n)/. 'and' yields the conjunction of a boolean array.
789 and :: Vector Bool -> Bool
790 {-# INLINE and #-}
791 and = G.and
792
793 -- |/O(n)/. 'or' yields the disjunction of a boolean array.
794 or :: Vector Bool -> Bool
795 {-# INLINE or #-}
796 or = G.or
797
798 -- |/O(n)/. 'sum' computes the sum (with @(+)@) of an array of elements.
799 sum :: Num a => Vector a -> a
800 {-# INLINE sum #-}
801 sum = G.sum
802
803 -- |/O(n)/. 'sum' computes the product (with @(*)@) of an array of elements.
804 product :: Num a => Vector a -> a
805 {-# INLINE product #-}
806 product = G.product
807
808 -- |/O(n)/. 'maximum' finds the maximum element in an array of orderable elements.
809 maximum :: Ord a => Vector a -> a
810 {-# INLINE maximum #-}
811 maximum = G.maximum
812
813 -- |/O(n)/. 'maximumBy' finds the maximum element in an array under the given ordering.
814 maximumBy :: (a -> a -> Ordering) -> Vector a -> a
815 {-# INLINE maximumBy #-}
816 maximumBy = G.maximumBy
817
818 -- |/O(n)/. 'minimum' finds the minimum element in an array of orderable elements.
819 minimum :: Ord a => Vector a -> a
820 {-# INLINE minimum #-}
821 minimum = G.minimum
822
823 -- |/O(n)/. 'minimumBy' finds the minimum element in an array under the given ordering.
824 minimumBy :: (a -> a -> Ordering) -> Vector a -> a
825 {-# INLINE minimumBy #-}
826 minimumBy = G.minimumBy
827
828 -- | TODO maxIndex
829 maxIndex :: Ord a => Vector a -> Int
830 {-# INLINE maxIndex #-}
831 maxIndex = G.maxIndex
832
833 -- | TODO maxIndexBy
834 maxIndexBy :: (a -> a -> Ordering) -> Vector a -> Int
835 {-# INLINE maxIndexBy #-}
836 maxIndexBy = G.maxIndexBy
837
838 -- | TODO minIndex
839 minIndex :: Ord a => Vector a -> Int
840 {-# INLINE minIndex #-}
841 minIndex = G.minIndex
842
843 -- | TODO minIndexBy
844 minIndexBy :: (a -> a -> Ordering) -> Vector a -> Int
845 {-# INLINE minIndexBy #-}
846 minIndexBy = G.minIndexBy
847
848 -- Unfolding
849 -- ---------
850
851 -- | The 'unfoldr' function is a \`dual\' to 'foldr': while 'foldr'
852 -- reduces a vector to a summary value, 'unfoldr' builds a list from
853 -- a seed value. The function takes the element and returns 'Nothing'
854 -- if it is done generating the vector or returns 'Just' @(a,b)@, in which
855 -- case, @a@ is a prepended to the vector and @b@ is used as the next
856 -- element in a recursive call.
857 --
858 -- A simple use of unfoldr:
859 --
860 -- > unfoldr (\b -> if b == 0 then Nothing else Just (b, b-1)) 10
861 -- > [10,9,8,7,6,5,4,3,2,1]
862 --
863 unfoldr :: (b -> Maybe (a, b)) -> b -> Vector a
864 {-# INLINE unfoldr #-}
865 unfoldr = G.unfoldr
866
867 -- | Unfold at most @n@ elements
868 unfoldrN :: Int -> (b -> Maybe (a, b)) -> b -> Vector a
869 {-# INLINE unfoldrN #-}
870 unfoldrN = G.unfoldrN
871
872 -- Scans
873 -- -----
874
875 -- | Prefix scan
876 prescanl :: (a -> b -> a) -> a -> Vector b -> Vector a
877 {-# INLINE prescanl #-}
878 prescanl = G.prescanl
879
880 -- | Prefix scan with strict accumulator
881 prescanl' :: (a -> b -> a) -> a -> Vector b -> Vector a
882 {-# INLINE prescanl' #-}
883 prescanl' = G.prescanl'
884
885 -- | Suffix scan
886 postscanl :: (a -> b -> a) -> a -> Vector b -> Vector a
887 {-# INLINE postscanl #-}
888 postscanl = G.postscanl
889
890 -- | Suffix scan with strict accumulator
891 postscanl' :: (a -> b -> a) -> a -> Vector b -> Vector a
892 {-# INLINE postscanl' #-}
893 postscanl' = G.postscanl'
894
895 -- | Haskell-style scan function.
896 scanl :: (a -> b -> a) -> a -> Vector b -> Vector a
897 {-# INLINE scanl #-}
898 scanl = G.scanl
899
900 -- | Haskell-style scan with strict accumulator
901 scanl' :: (a -> b -> a) -> a -> Vector b -> Vector a
902 {-# INLINE scanl' #-}
903 scanl' = G.scanl'
904
905 -- | Scan over a non-empty 'Vector'
906 scanl1 :: (a -> a -> a) -> Vector a -> Vector a
907 {-# INLINE scanl1 #-}
908 scanl1 = G.scanl1
909
910 -- | Scan over a non-empty 'Vector' with a strict accumulator
911 scanl1' :: (a -> a -> a) -> Vector a -> Vector a
912 {-# INLINE scanl1' #-}
913 scanl1' = G.scanl1'
914
915 -- | Prefix right-to-left scan
916 prescanr :: (a -> b -> b) -> b -> Vector a -> Vector b
917 {-# INLINE prescanr #-}
918 prescanr = G.prescanr
919
920 -- | Prefix right-to-left scan with strict accumulator
921 prescanr' :: (a -> b -> b) -> b -> Vector a -> Vector b
922 {-# INLINE prescanr' #-}
923 prescanr' = G.prescanr'
924
925 -- | Suffix right-to-left scan
926 postscanr :: (a -> b -> b) -> b -> Vector a -> Vector b
927 {-# INLINE postscanr #-}
928 postscanr = G.postscanr
929
930 -- | Suffix right-to-left scan with strict accumulator
931 postscanr' :: (a -> b -> b) -> b -> Vector a -> Vector b
932 {-# INLINE postscanr' #-}
933 postscanr' = G.postscanr'
934
935 -- | Haskell-style right-to-left scan
936 scanr :: (a -> b -> b) -> b -> Vector a -> Vector b
937 {-# INLINE scanr #-}
938 scanr = G.scanr
939
940 -- | Haskell-style right-to-left scan with strict accumulator
941 scanr' :: (a -> b -> b) -> b -> Vector a -> Vector b
942 {-# INLINE scanr' #-}
943 scanr' = G.scanr'
944
945 -- | Right-to-left scan over a non-empty vector
946 scanr1 :: (a -> a -> a) -> Vector a -> Vector a
947 {-# INLINE scanr1 #-}
948 scanr1 = G.scanr1
949
950 -- | Right-to-left scan over a non-empty vector with a strict accumulator
951 scanr1' :: (a -> a -> a) -> Vector a -> Vector a
952 {-# INLINE scanr1' #-}
953 scanr1' = G.scanr1'
954
955 -- Enumeration
956 -- -----------
957
958 -- | Yield a vector of the given length containing the values @x@, @x+1@ etc.
959 -- This operation is usually more efficient than 'enumFromTo'.
960 enumFromN :: Num a => a -> Int -> Vector a
961 {-# INLINE enumFromN #-}
962 enumFromN = G.enumFromN
963
964 -- | Yield a vector of the given length containing the values @x@, @x+y@,
965 -- @x+y+y@ etc. This operations is usually more efficient than
966 -- 'enumFromThenTo'.
967 enumFromStepN :: Num a => a -> a -> Int -> Vector a
968 {-# INLINE enumFromStepN #-}
969 enumFromStepN = G.enumFromStepN
970
971 -- | Enumerate values from @x@ to @y@.
972 --
973 -- /WARNING:/ This operation can be very inefficient. If at all possible, use
974 -- 'enumFromN' instead.
975 enumFromTo :: Enum a => a -> a -> Vector a
976 {-# INLINE enumFromTo #-}
977 enumFromTo = G.enumFromTo
978
979 -- | Enumerate values from @x@ to @y@ with a specific step @z@.
980 --
981 -- /WARNING:/ This operation can be very inefficient. If at all possible, use
982 -- 'enumFromStepN' instead.
983 enumFromThenTo :: Enum a => a -> a -> a -> Vector a
984 {-# INLINE enumFromThenTo #-}
985 enumFromThenTo = G.enumFromThenTo
986
987 -- Conversion to/from lists
988 -- ------------------------
989
990 -- | Convert a vector to a list
991 toList :: Vector a -> [a]
992 {-# INLINE toList #-}
993 toList = G.toList
994
995 -- | Convert a list to a vector
996 fromList :: [a] -> Vector a
997 {-# INLINE fromList #-}
998 fromList = G.fromList
999
1000 -- | Convert the first @n@ elements of a list to a vector
1001 --
1002 -- > fromListN n xs = fromList (take n xs)
1003 fromListN :: Int -> [a] -> Vector a
1004 {-# INLINE fromListN #-}
1005 fromListN = G.fromListN
1006
1007 -- Destructive operations
1008 -- ----------------------
1009
1010 -- | Destructively initialise a vector.
1011 create :: (forall s. ST s (MVector s a)) -> Vector a
1012 {-# INLINE create #-}
1013 create = G.create
1014
1015 -- | Apply a destructive operation to a vector. The operation is applied to a
1016 -- copy of the vector unless it can be safely performed in place.
1017 modify :: (forall s. MVector s a -> ST s ()) -> Vector a -> Vector a
1018 {-# INLINE modify #-}
1019 modify = G.modify
1020
1021 -- | Copy an immutable vector into a mutable one. The two vectors must have
1022 -- the same length. This is not checked.
1023 unsafeCopy :: PrimMonad m => MVector (PrimState m) a -> Vector a -> m ()
1024 {-# INLINE unsafeCopy #-}
1025 unsafeCopy = G.unsafeCopy
1026
1027 -- | Copy an immutable vector into a mutable one. The two vectors must have the
1028 -- same length.
1029 copy :: PrimMonad m => MVector (PrimState m) a -> Vector a -> m ()
1030 {-# INLINE copy #-}
1031 copy = G.copy
1032