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