Add maximumBy, minimumBy, maxIndexBy, minIndexBy
[darcs-mirrors/vector.git] / Data / Vector / Unboxed.hs
1 -- |
2 -- Module : Data.Vector.Unboxed
3 -- Copyright : (c) Roman Leshchinskiy 2009
4 -- License : BSD-style
5 --
6 -- Maintainer : Roman Leshchinskiy <rl@cse.unsw.edu.au>
7 -- Stability : experimental
8 -- Portability : non-portable
9 --
10 -- Adaptive unboxed vectors
11 --
12
13 module Data.Vector.Unboxed (
14 Vector, MVector(..), Unbox,
15
16 -- * Length information
17 length, null,
18
19 -- * Construction
20 empty, singleton, cons, snoc, replicate, (++), copy,
21
22 -- * Accessing individual elements
23 (!), head, last,
24
25 -- * Subvectors
26 slice, init, tail, take, drop,
27 unsafeSlice,
28
29 -- * Permutations
30 accum, accumulate, accumulate_,
31 (//), update, update_,
32 backpermute, reverse,
33
34 -- * Mapping
35 map, imap, concatMap,
36
37 -- * Zipping and unzipping
38 zipWith, zipWith3, zipWith4, zipWith5, zipWith6,
39 izipWith, izipWith3, izipWith4, izipWith5, izipWith6,
40 zip, zip3, zip4, zip5, zip6,
41 unzip, unzip3, unzip4, unzip5, unzip6,
42
43 -- * Filtering
44 filter, ifilter, takeWhile, dropWhile,
45
46 -- * Searching
47 elem, notElem, find, findIndex, findIndices, elemIndex, elemIndices,
48
49 -- * Folding
50 foldl, foldl1, foldl', foldl1', foldr, foldr1,
51 ifoldl, ifoldl', ifoldr,
52
53 -- * Specialised folds
54 and, or, sum, product,
55 maximum, maximumBy, minimum, minimumBy,
56 minIndex, minIndexBy, maxIndex, maxIndexBy,
57
58 -- * Unfolding
59 unfoldr,
60
61 -- * Scans
62 prescanl, prescanl',
63 postscanl, postscanl',
64 scanl, scanl', scanl1, scanl1',
65
66 -- * Enumeration
67 enumFromTo, enumFromThenTo,
68
69 -- * Conversion to/from lists
70 toList, fromList,
71
72 -- * Unsafe operations
73 unsafeIndex,
74 unsafeAccum, unsafeAccumulate, unsafeAccumulate_,
75 unsafeUpd, unsafeUpdate, unsafeUpdate_
76 ) where
77
78 import Data.Vector.Unboxed.Base
79 import qualified Data.Vector.Generic as G
80 import qualified Data.Vector.Fusion.Stream as Stream
81
82 import Prelude hiding ( length, null,
83 replicate, (++),
84 head, last,
85 init, tail, take, drop, reverse,
86 map, concatMap,
87 zipWith, zipWith3, zip, zip3, unzip, unzip3,
88 filter, takeWhile, dropWhile,
89 elem, notElem,
90 foldl, foldl1, foldr, foldr1,
91 and, or, sum, product, minimum, maximum,
92 scanl, scanl1,
93 enumFromTo, enumFromThenTo )
94
95 #include "vector.h"
96
97 instance (Unbox a, Eq a) => Eq (Vector a) where
98 {-# INLINE (==) #-}
99 (==) = G.eq
100
101 instance (Unbox a, Ord a) => Ord (Vector a) where
102 {-# INLINE compare #-}
103 compare = G.cmp
104
105 -- Length
106 -- ------
107
108 length :: Unbox a => Vector a -> Int
109 {-# INLINE length #-}
110 length = G.length
111
112 null :: Unbox a => Vector a -> Bool
113 {-# INLINE null #-}
114 null = G.null
115
116 -- Construction
117 -- ------------
118
119 -- | Empty vector
120 empty :: Unbox a => Vector a
121 {-# INLINE empty #-}
122 empty = G.empty
123
124 -- | Vector with exaclty one element
125 singleton :: Unbox a => a -> Vector a
126 {-# INLINE singleton #-}
127 singleton = G.singleton
128
129 -- | Vector of the given length with the given value in each position
130 replicate :: Unbox a => Int -> a -> Vector a
131 {-# INLINE replicate #-}
132 replicate = G.replicate
133
134 -- | Prepend an element
135 cons :: Unbox a => a -> Vector a -> Vector a
136 {-# INLINE cons #-}
137 cons = G.cons
138
139 -- | Append an element
140 snoc :: Unbox a => Vector a -> a -> Vector a
141 {-# INLINE snoc #-}
142 snoc = G.snoc
143
144 infixr 5 ++
145 -- | Concatenate two vectors
146 (++) :: Unbox a => Vector a -> Vector a -> Vector a
147 {-# INLINE (++) #-}
148 (++) = (G.++)
149
150 -- | Create a copy of a vector. Useful when dealing with slices.
151 copy :: Unbox a => Vector a -> Vector a
152 {-# INLINE copy #-}
153 copy = G.copy
154
155 -- Accessing individual elements
156 -- -----------------------------
157
158 -- | Indexing
159 (!) :: Unbox a => Vector a -> Int -> a
160 {-# INLINE (!) #-}
161 (!) = (G.!)
162
163 -- | Unsafe indexing without bounds checks
164 unsafeIndex :: Unbox a => Vector a -> Int -> a
165 {-# INLINE unsafeIndex #-}
166 unsafeIndex = G.unsafeIndex
167
168 -- | First element
169 head :: Unbox a => Vector a -> a
170 {-# INLINE head #-}
171 head = G.head
172
173 -- | Last element
174 last :: Unbox a => Vector a -> a
175 {-# INLINE last #-}
176 last = G.last
177
178 -- Subarrays
179 -- ---------
180
181 -- | Yield a part of the vector without copying it. Safer version of
182 -- 'basicUnsafeSlice'.
183 slice :: Unbox a => Vector a -> Int -- ^ starting index
184 -> Int -- ^ length
185 -> Vector a
186 {-# INLINE slice #-}
187 slice = G.slice
188
189 -- | Unsafely yield a part of the vector without copying it and without
190 -- performing bounds checks.
191 unsafeSlice :: Unbox a => Vector a -> Int -- ^ starting index
192 -> Int -- ^ length
193 -> Vector a
194 {-# INLINE unsafeSlice #-}
195 unsafeSlice = G.unsafeSlice
196
197 -- | Yield all but the last element without copying.
198 init :: Unbox a => Vector a -> Vector a
199 {-# INLINE init #-}
200 init = G.init
201
202 -- | All but the first element (without copying).
203 tail :: Unbox a => Vector a -> Vector a
204 {-# INLINE tail #-}
205 tail = G.tail
206
207 -- | Yield the first @n@ elements without copying.
208 take :: Unbox a => Int -> Vector a -> Vector a
209 {-# INLINE take #-}
210 take = G.take
211
212 -- | Yield all but the first @n@ elements without copying.
213 drop :: Unbox a => Int -> Vector a -> Vector a
214 {-# INLINE drop #-}
215 drop = G.drop
216
217 -- Permutations
218 -- ------------
219
220 unsafeAccum :: Unbox a => (a -> b -> a) -> Vector a -> [(Int,b)] -> Vector a
221 {-# INLINE unsafeAccum #-}
222 unsafeAccum = G.unsafeAccum
223
224 unsafeAccumulate :: (Unbox a, Unbox b)
225 => (a -> b -> a) -> Vector a -> Vector (Int,b) -> Vector a
226 {-# INLINE unsafeAccumulate #-}
227 unsafeAccumulate = G.unsafeAccumulate
228
229 unsafeAccumulate_ :: (Unbox a, Unbox b) =>
230 (a -> b -> a) -> Vector a -> Vector Int -> Vector b -> Vector a
231 {-# INLINE unsafeAccumulate_ #-}
232 unsafeAccumulate_ = G.unsafeAccumulate_
233
234 accum :: Unbox a => (a -> b -> a) -> Vector a -> [(Int,b)] -> Vector a
235 {-# INLINE accum #-}
236 accum = G.accum
237
238 accumulate :: (Unbox a, Unbox b)
239 => (a -> b -> a) -> Vector a -> Vector (Int,b) -> Vector a
240 {-# INLINE accumulate #-}
241 accumulate = G.accumulate
242
243 accumulate_ :: (Unbox a, Unbox b) =>
244 (a -> b -> a) -> Vector a -> Vector Int -> Vector b -> Vector a
245 {-# INLINE accumulate_ #-}
246 accumulate_ = G.accumulate_
247
248 unsafeUpd :: Unbox a => Vector a -> [(Int, a)] -> Vector a
249 {-# INLINE unsafeUpd #-}
250 unsafeUpd = G.unsafeUpd
251
252 unsafeUpdate :: Unbox a => Vector a -> Vector (Int, a) -> Vector a
253 {-# INLINE unsafeUpdate #-}
254 unsafeUpdate = G.unsafeUpdate
255
256 unsafeUpdate_ :: Unbox a => Vector a -> Vector Int -> Vector a -> Vector a
257 {-# INLINE unsafeUpdate_ #-}
258 unsafeUpdate_ = G.unsafeUpdate_
259
260 (//) :: Unbox a => Vector a -> [(Int, a)] -> Vector a
261 {-# INLINE (//) #-}
262 (//) = (G.//)
263
264 update :: Unbox a => Vector a -> Vector (Int, a) -> Vector a
265 {-# INLINE update #-}
266 update = G.update
267
268 update_ :: Unbox a => Vector a -> Vector Int -> Vector a -> Vector a
269 {-# INLINE update_ #-}
270 update_ = G.update_
271
272 backpermute :: Unbox a => Vector a -> Vector Int -> Vector a
273 {-# INLINE backpermute #-}
274 backpermute = G.backpermute
275
276 reverse :: Unbox a => Vector a -> Vector a
277 {-# INLINE reverse #-}
278 reverse = G.reverse
279
280 -- Mapping
281 -- -------
282
283 -- | Map a function over a vector
284 map :: (Unbox a, Unbox b) => (a -> b) -> Vector a -> Vector b
285 {-# INLINE map #-}
286 map = G.map
287
288 -- | Apply a function to every index/value pair
289 imap :: (Unbox a, Unbox b) => (Int -> a -> b) -> Vector a -> Vector b
290 {-# INLINE imap #-}
291 imap = G.imap
292
293 concatMap :: (Unbox a, Unbox b) => (a -> Vector b) -> Vector a -> Vector b
294 {-# INLINE concatMap #-}
295 concatMap = G.concatMap
296
297 -- Zipping/unzipping
298 -- -----------------
299
300 -- | Zip two vectors with the given function.
301 zipWith :: (Unbox a, Unbox b, Unbox c)
302 => (a -> b -> c) -> Vector a -> Vector b -> Vector c
303 {-# INLINE zipWith #-}
304 zipWith = G.zipWith
305
306 -- | Zip three vectors with the given function.
307 zipWith3 :: (Unbox a, Unbox b, Unbox c, Unbox d)
308 => (a -> b -> c -> d) -> Vector a -> Vector b -> Vector c -> Vector d
309 {-# INLINE zipWith3 #-}
310 zipWith3 = G.zipWith3
311
312 zipWith4 :: (Unbox a, Unbox b, Unbox c, Unbox d, Unbox e)
313 => (a -> b -> c -> d -> e)
314 -> Vector a -> Vector b -> Vector c -> Vector d -> Vector e
315 {-# INLINE zipWith4 #-}
316 zipWith4 = G.zipWith4
317
318 zipWith5 :: (Unbox a, Unbox b, Unbox c, Unbox d, Unbox e, Unbox f)
319 => (a -> b -> c -> d -> e -> f)
320 -> Vector a -> Vector b -> Vector c -> Vector d -> Vector e
321 -> Vector f
322 {-# INLINE zipWith5 #-}
323 zipWith5 = G.zipWith5
324
325 zipWith6 :: (Unbox a, Unbox b, Unbox c, Unbox d, Unbox e, Unbox f, Unbox g)
326 => (a -> b -> c -> d -> e -> f -> g)
327 -> Vector a -> Vector b -> Vector c -> Vector d -> Vector e
328 -> Vector f -> Vector g
329 {-# INLINE zipWith6 #-}
330 zipWith6 = G.zipWith6
331
332 -- | Zip two vectors and their indices with the given function.
333 izipWith :: (Unbox a, Unbox b, Unbox c)
334 => (Int -> a -> b -> c) -> Vector a -> Vector b -> Vector c
335 {-# INLINE izipWith #-}
336 izipWith = G.izipWith
337
338 -- | Zip three vectors and their indices with the given function.
339 izipWith3 :: (Unbox a, Unbox b, Unbox c, Unbox d)
340 => (Int -> a -> b -> c -> d)
341 -> Vector a -> Vector b -> Vector c -> Vector d
342 {-# INLINE izipWith3 #-}
343 izipWith3 = G.izipWith3
344
345 izipWith4 :: (Unbox a, Unbox b, Unbox c, Unbox d, Unbox e)
346 => (Int -> a -> b -> c -> d -> e)
347 -> Vector a -> Vector b -> Vector c -> Vector d -> Vector e
348 {-# INLINE izipWith4 #-}
349 izipWith4 = G.izipWith4
350
351 izipWith5 :: (Unbox a, Unbox b, Unbox c, Unbox d, Unbox e, Unbox f)
352 => (Int -> a -> b -> c -> d -> e -> f)
353 -> Vector a -> Vector b -> Vector c -> Vector d -> Vector e
354 -> Vector f
355 {-# INLINE izipWith5 #-}
356 izipWith5 = G.izipWith5
357
358 izipWith6 :: (Unbox a, Unbox b, Unbox c, Unbox d, Unbox e, Unbox f, Unbox g)
359 => (Int -> a -> b -> c -> d -> e -> f -> g)
360 -> Vector a -> Vector b -> Vector c -> Vector d -> Vector e
361 -> Vector f -> Vector g
362 {-# INLINE izipWith6 #-}
363 izipWith6 = G.izipWith6
364
365 -- Filtering
366 -- ---------
367
368 -- | Drop elements which do not satisfy the predicate
369 filter :: Unbox a => (a -> Bool) -> Vector a -> Vector a
370 {-# INLINE filter #-}
371 filter = G.filter
372
373 -- | Drop elements that do not satisfy the predicate (applied to values and
374 -- their indices)
375 ifilter :: Unbox a => (Int -> a -> Bool) -> Vector a -> Vector a
376 {-# INLINE ifilter #-}
377 ifilter = G.ifilter
378
379 -- | Yield the longest prefix of elements satisfying the predicate.
380 takeWhile :: Unbox a => (a -> Bool) -> Vector a -> Vector a
381 {-# INLINE takeWhile #-}
382 takeWhile = G.takeWhile
383
384 -- | Drop the longest prefix of elements that satisfy the predicate.
385 dropWhile :: Unbox a => (a -> Bool) -> Vector a -> Vector a
386 {-# INLINE dropWhile #-}
387 dropWhile = G.dropWhile
388
389 -- Searching
390 -- ---------
391
392 infix 4 `elem`
393 -- | Check whether the vector contains an element
394 elem :: (Unbox a, Eq a) => a -> Vector a -> Bool
395 {-# INLINE elem #-}
396 elem = G.elem
397
398 infix 4 `notElem`
399 -- | Inverse of `elem`
400 notElem :: (Unbox a, Eq a) => a -> Vector a -> Bool
401 {-# INLINE notElem #-}
402 notElem = G.notElem
403
404 -- | Yield 'Just' the first element matching the predicate or 'Nothing' if no
405 -- such element exists.
406 find :: Unbox a => (a -> Bool) -> Vector a -> Maybe a
407 {-# INLINE find #-}
408 find = G.find
409
410 -- | Yield 'Just' the index of the first element matching the predicate or
411 -- 'Nothing' if no such element exists.
412 findIndex :: Unbox a => (a -> Bool) -> Vector a -> Maybe Int
413 {-# INLINE findIndex #-}
414 findIndex = G.findIndex
415
416 -- | Yield the indices of elements satisfying the predicate
417 findIndices :: Unbox a => (a -> Bool) -> Vector a -> Vector Int
418 {-# INLINE findIndices #-}
419 findIndices = G.findIndices
420
421 -- | Yield 'Just' the index of the first occurence of the given element or
422 -- 'Nothing' if the vector does not contain the element
423 elemIndex :: (Unbox a, Eq a) => a -> Vector a -> Maybe Int
424 {-# INLINE elemIndex #-}
425 elemIndex = G.elemIndex
426
427 -- | Yield the indices of all occurences of the given element
428 elemIndices :: (Unbox a, Eq a) => a -> Vector a -> Vector Int
429 {-# INLINE elemIndices #-}
430 elemIndices = G.elemIndices
431
432 -- Folding
433 -- -------
434
435 -- | Left fold
436 foldl :: Unbox b => (a -> b -> a) -> a -> Vector b -> a
437 {-# INLINE foldl #-}
438 foldl = G.foldl
439
440 -- | Lefgt fold on non-empty vectors
441 foldl1 :: Unbox a => (a -> a -> a) -> Vector a -> a
442 {-# INLINE foldl1 #-}
443 foldl1 = G.foldl1
444
445 -- | Left fold with strict accumulator
446 foldl' :: Unbox b => (a -> b -> a) -> a -> Vector b -> a
447 {-# INLINE foldl' #-}
448 foldl' = G.foldl'
449
450 -- | Left fold on non-empty vectors with strict accumulator
451 foldl1' :: Unbox a => (a -> a -> a) -> Vector a -> a
452 {-# INLINE foldl1' #-}
453 foldl1' = G.foldl1'
454
455 -- | Right fold
456 foldr :: Unbox a => (a -> b -> b) -> b -> Vector a -> b
457 {-# INLINE foldr #-}
458 foldr = G.foldr
459
460 -- | Right fold on non-empty vectors
461 foldr1 :: Unbox a => (a -> a -> a) -> Vector a -> a
462 {-# INLINE foldr1 #-}
463 foldr1 = G.foldr1
464
465 -- | Left fold (function applied to each element and its index)
466 ifoldl :: Unbox b => (a -> Int -> b -> a) -> a -> Vector b -> a
467 {-# INLINE ifoldl #-}
468 ifoldl = G.ifoldl
469
470 -- | Left fold with strict accumulator (function applied to each element and
471 -- its index)
472 ifoldl' :: Unbox b => (a -> Int -> b -> a) -> a -> Vector b -> a
473 {-# INLINE ifoldl' #-}
474 ifoldl' = G.ifoldl'
475
476 -- | Right fold (function applied to each element and its index)
477 ifoldr :: Unbox a => (Int -> a -> b -> b) -> b -> Vector a -> b
478 {-# INLINE ifoldr #-}
479 ifoldr = G.ifoldr
480
481 -- Specialised folds
482 -- -----------------
483
484 and :: Vector Bool -> Bool
485 {-# INLINE and #-}
486 and = G.and
487
488 or :: Vector Bool -> Bool
489 {-# INLINE or #-}
490 or = G.or
491
492 sum :: (Unbox a, Num a) => Vector a -> a
493 {-# INLINE sum #-}
494 sum = G.sum
495
496 product :: (Unbox a, Num a) => Vector a -> a
497 {-# INLINE product #-}
498 product = G.product
499
500 maximum :: (Unbox a, Ord a) => Vector a -> a
501 {-# INLINE maximum #-}
502 maximum = G.maximum
503
504 maximumBy :: Unbox a => (a -> a -> Ordering) -> Vector a -> a
505 {-# INLINE maximumBy #-}
506 maximumBy = G.maximumBy
507
508 minimum :: (Unbox a, Ord a) => Vector a -> a
509 {-# INLINE minimum #-}
510 minimum = G.minimum
511
512 minimumBy :: Unbox a => (a -> a -> Ordering) -> Vector a -> a
513 {-# INLINE minimumBy #-}
514 minimumBy = G.minimumBy
515
516 maxIndex :: (Unbox a, Ord a) => Vector a -> Int
517 {-# INLINE maxIndex #-}
518 maxIndex = G.maxIndex
519
520 maxIndexBy :: Unbox a => (a -> a -> Ordering) -> Vector a -> Int
521 {-# INLINE maxIndexBy #-}
522 maxIndexBy = G.maxIndexBy
523
524 minIndex :: (Unbox a, Ord a) => Vector a -> Int
525 {-# INLINE minIndex #-}
526 minIndex = G.minIndex
527
528 minIndexBy :: Unbox a => (a -> a -> Ordering) -> Vector a -> Int
529 {-# INLINE minIndexBy #-}
530 minIndexBy = G.minIndexBy
531
532 -- Unfolding
533 -- ---------
534
535 unfoldr :: Unbox a => (b -> Maybe (a, b)) -> b -> Vector a
536 {-# INLINE unfoldr #-}
537 unfoldr = G.unfoldr
538
539 -- Scans
540 -- -----
541
542 -- | Prefix scan
543 prescanl :: (Unbox a, Unbox b) => (a -> b -> a) -> a -> Vector b -> Vector a
544 {-# INLINE prescanl #-}
545 prescanl = G.prescanl
546
547 -- | Prefix scan with strict accumulator
548 prescanl' :: (Unbox a, Unbox b) => (a -> b -> a) -> a -> Vector b -> Vector a
549 {-# INLINE prescanl' #-}
550 prescanl' = G.prescanl'
551
552 -- | Suffix scan
553 postscanl :: (Unbox a, Unbox b) => (a -> b -> a) -> a -> Vector b -> Vector a
554 {-# INLINE postscanl #-}
555 postscanl = G.postscanl
556
557 -- | Suffix scan with strict accumulator
558 postscanl' :: (Unbox a, Unbox b) => (a -> b -> a) -> a -> Vector b -> Vector a
559 {-# INLINE postscanl' #-}
560 postscanl' = G.postscanl'
561
562 -- | Haskell-style scan
563 scanl :: (Unbox a, Unbox b) => (a -> b -> a) -> a -> Vector b -> Vector a
564 {-# INLINE scanl #-}
565 scanl = G.scanl
566
567 -- | Haskell-style scan with strict accumulator
568 scanl' :: (Unbox a, Unbox b) => (a -> b -> a) -> a -> Vector b -> Vector a
569 {-# INLINE scanl' #-}
570 scanl' = G.scanl'
571
572 -- | Scan over a non-empty 'Vector'
573 scanl1 :: Unbox a => (a -> a -> a) -> Vector a -> Vector a
574 {-# INLINE scanl1 #-}
575 scanl1 = G.scanl1
576
577 -- | Scan over a non-empty 'Vector' with a strict accumulator
578 scanl1' :: Unbox a => (a -> a -> a) -> Vector a -> Vector a
579 {-# INLINE scanl1' #-}
580 scanl1' = G.scanl1'
581
582 -- Enumeration
583 -- -----------
584
585 enumFromTo :: (Unbox a, Enum a) => a -> a -> Vector a
586 {-# INLINE enumFromTo #-}
587 enumFromTo = G.enumFromTo
588
589 enumFromThenTo :: (Unbox a, Enum a) => a -> a -> a -> Vector a
590 {-# INLINE enumFromThenTo #-}
591 enumFromThenTo = G.enumFromThenTo
592
593 -- Conversion to/from lists
594 -- ------------------------
595
596 -- | Convert a vector to a list
597 toList :: Unbox a => Vector a -> [a]
598 {-# INLINE toList #-}
599 toList = G.toList
600
601 -- | Convert a list to a vector
602 fromList :: Unbox a => [a] -> Vector a
603 {-# INLINE fromList #-}
604 fromList = G.fromList
605
606 #define DEFINE_IMMUTABLE
607 #include "unbox-tuple-instances"
608