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