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