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