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