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