EXPERIMENTAL: Unboxing infrastructure
[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, (++), 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, concatMap,
36
37 -- * Zipping and unzipping
38 zipWith, zipWith3,
39
40 -- * Filtering
41 filter, takeWhile, dropWhile,
42
43 -- * Searching
44 elem, notElem, find, findIndex,
45
46 -- * Folding
47 foldl, foldl1, foldl', foldl1', foldr, foldr1,
48
49 -- * Specialised folds
50 sum, product, maximum, minimum,
51
52 -- * Unfolding
53 unfoldr,
54
55 -- * Scans
56 prescanl, prescanl',
57 postscanl, postscanl',
58 scanl, scanl', scanl1, scanl1',
59
60 -- * Enumeration
61 enumFromTo, enumFromThenTo,
62
63 -- * Conversion to/from lists
64 toList, fromList,
65
66 -- * Unsafe operations
67 unsafeIndex,
68 unsafeAccum, unsafeAccumulate_,
69 unsafeUpd, unsafeUpdate_
70 ) where
71
72 import qualified Data.Vector.Generic as G
73 import Data.Vector.Primitive.Mutable ( MVector(..) )
74 import Data.Primitive.ByteArray
75 import Data.Primitive ( Prim )
76
77 import Control.Monad ( liftM )
78
79 import Prelude hiding ( length, null,
80 replicate, (++),
81 head, last,
82 init, tail, take, drop, reverse,
83 map, concatMap,
84 zipWith, zipWith3, zip, zip3, unzip, unzip3,
85 filter, takeWhile, dropWhile,
86 elem, notElem,
87 foldl, foldl1, foldr, foldr1,
88 sum, product, minimum, maximum,
89 scanl, scanl1,
90 enumFromTo, enumFromThenTo )
91
92 import qualified Prelude
93
94 -- | Unboxed vectors of primitive types
95 data Vector a = Vector {-# UNPACK #-} !Int
96 {-# UNPACK #-} !Int
97 {-# UNPACK #-} !ByteArray
98
99 instance (Show a, Prim a) => Show (Vector a) where
100 show = (Prelude.++ " :: Data.Vector.Primitive.Vector") . ("fromList " Prelude.++) . show . toList
101
102 type instance G.Mutable Vector = MVector
103
104 instance Prim a => G.Vector Vector a where
105 {-# INLINE unsafeFreeze #-}
106 unsafeFreeze (MVector i n marr)
107 = Vector i n `liftM` unsafeFreezeByteArray marr
108
109 {-# INLINE basicLength #-}
110 basicLength (Vector _ n _) = n
111
112 {-# INLINE basicUnsafeSlice #-}
113 basicUnsafeSlice (Vector i _ arr) j n = Vector (i+j) n arr
114
115 {-# INLINE basicUnsafeIndexM #-}
116 basicUnsafeIndexM (Vector i _ arr) j = return (indexByteArray arr (i+j))
117
118 {-# INLINE elemseq #-}
119 elemseq _ = seq
120
121 instance (Prim a, Eq a) => Eq (Vector a) where
122 {-# INLINE (==) #-}
123 (==) = G.eq
124
125 instance (Prim a, Ord a) => Ord (Vector a) where
126 {-# INLINE compare #-}
127 compare = G.cmp
128
129 -- Length
130 -- ------
131
132 length :: Prim a => Vector a -> Int
133 {-# INLINE length #-}
134 length = G.length
135
136 null :: Prim a => Vector a -> Bool
137 {-# INLINE null #-}
138 null = G.null
139
140 -- Construction
141 -- ------------
142
143 -- | Empty vector
144 empty :: Prim a => Vector a
145 {-# INLINE empty #-}
146 empty = G.empty
147
148 -- | Vector with exaclty one element
149 singleton :: Prim a => a -> Vector a
150 {-# INLINE singleton #-}
151 singleton = G.singleton
152
153 -- | Vector of the given length with the given value in each position
154 replicate :: Prim a => Int -> a -> Vector a
155 {-# INLINE replicate #-}
156 replicate = G.replicate
157
158 -- | Prepend an element
159 cons :: Prim a => a -> Vector a -> Vector a
160 {-# INLINE cons #-}
161 cons = G.cons
162
163 -- | Append an element
164 snoc :: Prim a => Vector a -> a -> Vector a
165 {-# INLINE snoc #-}
166 snoc = G.snoc
167
168 infixr 5 ++
169 -- | Concatenate two vectors
170 (++) :: Prim a => Vector a -> Vector a -> Vector a
171 {-# INLINE (++) #-}
172 (++) = (G.++)
173
174 -- | Create a copy of a vector. Useful when dealing with slices.
175 copy :: Prim a => Vector a -> Vector a
176 {-# INLINE copy #-}
177 copy = G.copy
178
179 -- Accessing individual elements
180 -- -----------------------------
181
182 -- | Indexing
183 (!) :: Prim a => Vector a -> Int -> a
184 {-# INLINE (!) #-}
185 (!) = (G.!)
186
187 -- | Unsafe indexing without bounds checks
188 unsafeIndex :: Prim a => Vector a -> Int -> a
189 {-# INLINE unsafeIndex #-}
190 unsafeIndex = G.unsafeIndex
191
192 -- | First element
193 head :: Prim a => Vector a -> a
194 {-# INLINE head #-}
195 head = G.head
196
197 -- | Last element
198 last :: Prim a => Vector a -> a
199 {-# INLINE last #-}
200 last = G.last
201
202 -- Subarrays
203 -- ---------
204
205 -- | Yield a part of the vector without copying it. Safer version of
206 -- 'basicUnsafeSlice'.
207 slice :: Prim a => Vector a -> Int -- ^ starting index
208 -> Int -- ^ length
209 -> Vector a
210 {-# INLINE slice #-}
211 slice = G.slice
212
213 -- | Unsafely yield a part of the vector without copying it and without
214 -- performing bounds checks.
215 unsafeSlice :: Prim a => Vector a -> Int -- ^ starting index
216 -> Int -- ^ length
217 -> Vector a
218 {-# INLINE unsafeSlice #-}
219 unsafeSlice = G.unsafeSlice
220
221 -- | Yield all but the last element without copying.
222 init :: Prim a => Vector a -> Vector a
223 {-# INLINE init #-}
224 init = G.init
225
226 -- | All but the first element (without copying).
227 tail :: Prim a => Vector a -> Vector a
228 {-# INLINE tail #-}
229 tail = G.tail
230
231 -- | Yield the first @n@ elements without copying.
232 take :: Prim a => Int -> Vector a -> Vector a
233 {-# INLINE take #-}
234 take = G.take
235
236 -- | Yield all but the first @n@ elements without copying.
237 drop :: Prim a => Int -> Vector a -> Vector a
238 {-# INLINE drop #-}
239 drop = G.drop
240
241 -- Permutations
242 -- ------------
243
244 unsafeAccum :: Prim a => (a -> b -> a) -> Vector a -> [(Int,b)] -> Vector a
245 {-# INLINE unsafeAccum #-}
246 unsafeAccum = G.unsafeAccum
247
248 unsafeAccumulate_ :: (Prim a, Prim b) =>
249 (a -> b -> a) -> Vector a -> Vector Int -> Vector b -> Vector a
250 {-# INLINE unsafeAccumulate_ #-}
251 unsafeAccumulate_ = G.unsafeAccumulate_
252
253 accum :: Prim a => (a -> b -> a) -> Vector a -> [(Int,b)] -> Vector a
254 {-# INLINE accum #-}
255 accum = G.accum
256
257 accumulate_ :: (Prim a, Prim b) =>
258 (a -> b -> a) -> Vector a -> Vector Int -> Vector b -> Vector a
259 {-# INLINE accumulate_ #-}
260 accumulate_ = G.accumulate_
261
262 unsafeUpd :: Prim a => Vector a -> [(Int, a)] -> Vector a
263 {-# INLINE unsafeUpd #-}
264 unsafeUpd = G.unsafeUpd
265
266 unsafeUpdate_ :: Prim a => Vector a -> Vector Int -> Vector a -> Vector a
267 {-# INLINE unsafeUpdate_ #-}
268 unsafeUpdate_ = G.unsafeUpdate_
269
270 (//) :: Prim a => Vector a -> [(Int, a)] -> Vector a
271 {-# INLINE (//) #-}
272 (//) = (G.//)
273
274 update_ :: Prim a => Vector a -> Vector Int -> Vector a -> Vector a
275 {-# INLINE update_ #-}
276 update_ = G.update_
277
278 backpermute :: Prim a => Vector a -> Vector Int -> Vector a
279 {-# INLINE backpermute #-}
280 backpermute = G.backpermute
281
282 reverse :: Prim a => Vector a -> Vector a
283 {-# INLINE reverse #-}
284 reverse = G.reverse
285
286 -- Mapping
287 -- -------
288
289 -- | Map a function over a vector
290 map :: (Prim a, Prim b) => (a -> b) -> Vector a -> Vector b
291 {-# INLINE map #-}
292 map = G.map
293
294 concatMap :: (Prim a, Prim b) => (a -> Vector b) -> Vector a -> Vector b
295 {-# INLINE concatMap #-}
296 concatMap = G.concatMap
297
298 -- Zipping/unzipping
299 -- -----------------
300
301 -- | Zip two vectors with the given function.
302 zipWith :: (Prim a, Prim b, Prim c)
303 => (a -> b -> c) -> Vector a -> Vector b -> Vector c
304 {-# INLINE zipWith #-}
305 zipWith = G.zipWith
306
307 -- | Zip three vectors with the given function.
308 zipWith3 :: (Prim a, Prim b, Prim c, Prim d)
309 => (a -> b -> c -> d) -> Vector a -> Vector b -> Vector c -> Vector d
310 {-# INLINE zipWith3 #-}
311 zipWith3 = G.zipWith3
312
313 -- Filtering
314 -- ---------
315
316 -- | Drop elements which do not satisfy the predicate
317 filter :: Prim a => (a -> Bool) -> Vector a -> Vector a
318 {-# INLINE filter #-}
319 filter = G.filter
320
321 -- | Yield the longest prefix of elements satisfying the predicate.
322 takeWhile :: Prim a => (a -> Bool) -> Vector a -> Vector a
323 {-# INLINE takeWhile #-}
324 takeWhile = G.takeWhile
325
326 -- | Drop the longest prefix of elements that satisfy the predicate.
327 dropWhile :: Prim a => (a -> Bool) -> Vector a -> Vector a
328 {-# INLINE dropWhile #-}
329 dropWhile = G.dropWhile
330
331 -- Searching
332 -- ---------
333
334 infix 4 `elem`
335 -- | Check whether the vector contains an element
336 elem :: (Prim a, Eq a) => a -> Vector a -> Bool
337 {-# INLINE elem #-}
338 elem = G.elem
339
340 infix 4 `notElem`
341 -- | Inverse of `elem`
342 notElem :: (Prim a, Eq a) => a -> Vector a -> Bool
343 {-# INLINE notElem #-}
344 notElem = G.notElem
345
346 -- | Yield 'Just' the first element matching the predicate or 'Nothing' if no
347 -- such element exists.
348 find :: Prim a => (a -> Bool) -> Vector a -> Maybe a
349 {-# INLINE find #-}
350 find = G.find
351
352 -- | Yield 'Just' the index of the first element matching the predicate or
353 -- 'Nothing' if no such element exists.
354 findIndex :: Prim a => (a -> Bool) -> Vector a -> Maybe Int
355 {-# INLINE findIndex #-}
356 findIndex = G.findIndex
357
358 -- Folding
359 -- -------
360
361 -- | Left fold
362 foldl :: Prim b => (a -> b -> a) -> a -> Vector b -> a
363 {-# INLINE foldl #-}
364 foldl = G.foldl
365
366 -- | Lefgt fold on non-empty vectors
367 foldl1 :: Prim a => (a -> a -> a) -> Vector a -> a
368 {-# INLINE foldl1 #-}
369 foldl1 = G.foldl1
370
371 -- | Left fold with strict accumulator
372 foldl' :: Prim b => (a -> b -> a) -> a -> Vector b -> a
373 {-# INLINE foldl' #-}
374 foldl' = G.foldl'
375
376 -- | Left fold on non-empty vectors with strict accumulator
377 foldl1' :: Prim a => (a -> a -> a) -> Vector a -> a
378 {-# INLINE foldl1' #-}
379 foldl1' = G.foldl1'
380
381 -- | Right fold
382 foldr :: Prim a => (a -> b -> b) -> b -> Vector a -> b
383 {-# INLINE foldr #-}
384 foldr = G.foldr
385
386 -- | Right fold on non-empty vectors
387 foldr1 :: Prim a => (a -> a -> a) -> Vector a -> a
388 {-# INLINE foldr1 #-}
389 foldr1 = G.foldr1
390
391 -- Specialised folds
392 -- -----------------
393
394 sum :: (Prim a, Num a) => Vector a -> a
395 {-# INLINE sum #-}
396 sum = G.sum
397
398 product :: (Prim a, Num a) => Vector a -> a
399 {-# INLINE product #-}
400 product = G.product
401
402 maximum :: (Prim a, Ord a) => Vector a -> a
403 {-# INLINE maximum #-}
404 maximum = G.maximum
405
406 minimum :: (Prim a, Ord a) => Vector a -> a
407 {-# INLINE minimum #-}
408 minimum = G.minimum
409
410 -- Unfolding
411 -- ---------
412
413 unfoldr :: Prim a => (b -> Maybe (a, b)) -> b -> Vector a
414 {-# INLINE unfoldr #-}
415 unfoldr = G.unfoldr
416
417 -- Scans
418 -- -----
419
420 -- | Prefix scan
421 prescanl :: (Prim a, Prim b) => (a -> b -> a) -> a -> Vector b -> Vector a
422 {-# INLINE prescanl #-}
423 prescanl = G.prescanl
424
425 -- | Prefix scan with strict accumulator
426 prescanl' :: (Prim a, Prim b) => (a -> b -> a) -> a -> Vector b -> Vector a
427 {-# INLINE prescanl' #-}
428 prescanl' = G.prescanl'
429
430 -- | Suffix scan
431 postscanl :: (Prim a, Prim b) => (a -> b -> a) -> a -> Vector b -> Vector a
432 {-# INLINE postscanl #-}
433 postscanl = G.postscanl
434
435 -- | Suffix scan with strict accumulator
436 postscanl' :: (Prim a, Prim b) => (a -> b -> a) -> a -> Vector b -> Vector a
437 {-# INLINE postscanl' #-}
438 postscanl' = G.postscanl'
439
440 -- | Haskell-style scan
441 scanl :: (Prim a, Prim b) => (a -> b -> a) -> a -> Vector b -> Vector a
442 {-# INLINE scanl #-}
443 scanl = G.scanl
444
445 -- | Haskell-style scan with strict accumulator
446 scanl' :: (Prim a, Prim b) => (a -> b -> a) -> a -> Vector b -> Vector a
447 {-# INLINE scanl' #-}
448 scanl' = G.scanl'
449
450 -- | Scan over a non-empty 'Vector'
451 scanl1 :: Prim a => (a -> a -> a) -> Vector a -> Vector a
452 {-# INLINE scanl1 #-}
453 scanl1 = G.scanl1
454
455 -- | Scan over a non-empty 'Vector' with a strict accumulator
456 scanl1' :: Prim a => (a -> a -> a) -> Vector a -> Vector a
457 {-# INLINE scanl1' #-}
458 scanl1' = G.scanl1'
459
460 -- Enumeration
461 -- -----------
462
463 enumFromTo :: (Prim a, Enum a) => a -> a -> Vector a
464 {-# INLINE enumFromTo #-}
465 enumFromTo = G.enumFromTo
466
467 enumFromThenTo :: (Prim a, Enum a) => a -> a -> a -> Vector a
468 {-# INLINE enumFromThenTo #-}
469 enumFromThenTo = G.enumFromThenTo
470
471 -- Conversion to/from lists
472 -- ------------------------
473
474 -- | Convert a vector to a list
475 toList :: Prim a => Vector a -> [a]
476 {-# INLINE toList #-}
477 toList = G.toList
478
479 -- | Convert a list to a vector
480 fromList :: Prim a => [a] -> Vector a
481 {-# INLINE fromList #-}
482 fromList = G.fromList
483