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