Add unsafe versions of accum/update operations
[darcs-mirrors/vector.git] / Data / Vector.hs
1 {-# LANGUAGE FlexibleInstances, MultiParamTypeClasses, TypeFamilies #-}
2
3 -- |
4 -- Module : Data.Vector
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 -- Boxed vectors
13 --
14
15 module Data.Vector (
16 Vector, MVector,
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, indexM, headM, lastM,
26
27 -- * Subvectors
28 slice, init, tail, take, drop,
29 unsafeSlice,
30
31 -- * Permutations
32 accum, accumulate, accumulate_,
33 (//), update, update_,
34 backpermute, reverse,
35
36 -- * Mapping
37 map, concatMap,
38
39 -- * Zipping and unzipping
40 zipWith, zipWith3, zipWith4, zipWith5, zipWith6,
41 zip, zip3, zip4, zip5, zip6,
42 unzip, unzip3, unzip4, unzip5, unzip6,
43
44 -- * Filtering
45 filter, takeWhile, dropWhile,
46
47 -- * Searching
48 elem, notElem, find, findIndex,
49
50 -- * Folding
51 foldl, foldl1, foldl', foldl1', foldr, foldr1,
52
53 -- * Specialised folds
54 and, or, sum, product, maximum, minimum,
55
56 -- * Unfolding
57 unfoldr,
58
59 -- * Scans
60 prescanl, prescanl',
61 postscanl, postscanl',
62 scanl, scanl', scanl1, scanl1',
63
64 -- * Enumeration
65 enumFromTo, enumFromThenTo,
66
67 -- * Conversion to/from lists
68 toList, fromList,
69
70 -- * Unsafe operations
71 unsafeIndex, unsafeIndexM,
72 unsafeAccum, unsafeAccumulate, unsafeAccumulate_,
73 unsafeUpd, unsafeUpdate, unsafeUpdate_
74 ) where
75
76 import qualified Data.Vector.Generic as G
77 import Data.Vector.Mutable ( MVector(..) )
78 import Data.Primitive.Array
79
80 import Control.Monad ( liftM )
81
82 import Prelude hiding ( length, null,
83 replicate, (++),
84 head, last,
85 init, tail, take, drop, reverse,
86 map, concatMap,
87 zipWith, zipWith3, zip, zip3, unzip, unzip3,
88 filter, takeWhile, dropWhile,
89 elem, notElem,
90 foldl, foldl1, foldr, foldr1,
91 and, or, sum, product, minimum, maximum,
92 scanl, scanl1,
93 enumFromTo, enumFromThenTo )
94
95 import qualified Prelude
96
97 data Vector a = Vector {-# UNPACK #-} !Int
98 {-# UNPACK #-} !Int
99 {-# UNPACK #-} !(Array a)
100
101 instance Show a => Show (Vector a) where
102 show = (Prelude.++ " :: Data.Vector.Vector") . ("fromList " Prelude.++) . show . toList
103
104 type instance G.Mutable Vector = MVector
105
106 instance G.Vector Vector a where
107 {-# INLINE unsafeFreeze #-}
108 unsafeFreeze (MVector i n marr)
109 = Vector i n `liftM` unsafeFreezeArray marr
110
111 {-# INLINE basicLength #-}
112 basicLength (Vector _ n _) = n
113
114 {-# INLINE basicUnsafeSlice #-}
115 basicUnsafeSlice (Vector i _ arr) j n = Vector (i+j) n arr
116
117 {-# INLINE basicUnsafeIndexM #-}
118 basicUnsafeIndexM (Vector i _ arr) j = indexArrayM arr (i+j)
119
120 instance Eq a => Eq (Vector a) where
121 {-# INLINE (==) #-}
122 (==) = G.eq
123
124 instance Ord a => Ord (Vector a) where
125 {-# INLINE compare #-}
126 compare = G.cmp
127
128 -- Length
129 -- ------
130
131 length :: Vector a -> Int
132 {-# INLINE length #-}
133 length = G.length
134
135 null :: Vector a -> Bool
136 {-# INLINE null #-}
137 null = G.null
138
139 -- Construction
140 -- ------------
141
142 -- | Empty vector
143 empty :: Vector a
144 {-# INLINE empty #-}
145 empty = G.empty
146
147 -- | Vector with exaclty one element
148 singleton :: a -> Vector a
149 {-# INLINE singleton #-}
150 singleton = G.singleton
151
152 -- | Vector of the given length with the given value in each position
153 replicate :: Int -> a -> Vector a
154 {-# INLINE replicate #-}
155 replicate = G.replicate
156
157 -- | Prepend an element
158 cons :: a -> Vector a -> Vector a
159 {-# INLINE cons #-}
160 cons = G.cons
161
162 -- | Append an element
163 snoc :: Vector a -> a -> Vector a
164 {-# INLINE snoc #-}
165 snoc = G.snoc
166
167 infixr 5 ++
168 -- | Concatenate two vectors
169 (++) :: Vector a -> Vector a -> Vector a
170 {-# INLINE (++) #-}
171 (++) = (G.++)
172
173 -- | Create a copy of a vector. Useful when dealing with slices.
174 copy :: Vector a -> Vector a
175 {-# INLINE copy #-}
176 copy = G.copy
177
178 -- Accessing individual elements
179 -- -----------------------------
180
181 -- | Indexing
182 (!) :: Vector a -> Int -> a
183 {-# INLINE (!) #-}
184 (!) = (G.!)
185
186 -- | Unsafe indexing without bounds checks
187 unsafeIndex :: Vector a -> Int -> a
188 {-# INLINE unsafeIndex #-}
189 unsafeIndex = G.unsafeIndex
190
191 -- | First element
192 head :: Vector a -> a
193 {-# INLINE head #-}
194 head = G.head
195
196 -- | Last element
197 last :: Vector a -> a
198 {-# INLINE last #-}
199 last = G.last
200
201 -- | Monadic indexing which can be strict in the vector while remaining lazy in
202 -- the element
203 indexM :: Monad m => Vector a -> Int -> m a
204 {-# INLINE indexM #-}
205 indexM = G.indexM
206
207 -- | Unsafe monadic indexing without bounds checks
208 unsafeIndexM :: Monad m => Vector a -> Int -> m a
209 {-# INLINE unsafeIndexM #-}
210 unsafeIndexM = G.unsafeIndexM
211
212 headM :: Monad m => Vector a -> m a
213 {-# INLINE headM #-}
214 headM = G.headM
215
216 lastM :: Monad m => Vector a -> m a
217 {-# INLINE lastM #-}
218 lastM = G.lastM
219
220 -- Subarrays
221 -- ---------
222
223 -- | Yield a part of the vector without copying it. Safer version of
224 -- 'basicUnsafeSlice'.
225 slice :: Vector a -> Int -- ^ starting index
226 -> Int -- ^ length
227 -> Vector a
228 {-# INLINE slice #-}
229 slice = G.slice
230
231 -- | Unsafely yield a part of the vector without copying it and without
232 -- performing bounds checks.
233 unsafeSlice :: Vector a -> Int -- ^ starting index
234 -> Int -- ^ length
235 -> Vector a
236 {-# INLINE unsafeSlice #-}
237 unsafeSlice = G.unsafeSlice
238
239 -- | Yield all but the last element without copying.
240 init :: Vector a -> Vector a
241 {-# INLINE init #-}
242 init = G.init
243
244 -- | All but the first element (without copying).
245 tail :: Vector a -> Vector a
246 {-# INLINE tail #-}
247 tail = G.tail
248
249 -- | Yield the first @n@ elements without copying.
250 take :: Int -> Vector a -> Vector a
251 {-# INLINE take #-}
252 take = G.take
253
254 -- | Yield all but the first @n@ elements without copying.
255 drop :: Int -> Vector a -> Vector a
256 {-# INLINE drop #-}
257 drop = G.drop
258
259 -- Permutations
260 -- ------------
261
262 unsafeAccum :: (a -> b -> a) -> Vector a -> [(Int,b)] -> Vector a
263 {-# INLINE unsafeAccum #-}
264 unsafeAccum = G.unsafeAccum
265
266 unsafeAccumulate :: (a -> b -> a) -> Vector a -> Vector (Int,b) -> Vector a
267 {-# INLINE unsafeAccumulate #-}
268 unsafeAccumulate = G.unsafeAccumulate
269
270 unsafeAccumulate_
271 :: (a -> b -> a) -> Vector a -> Vector Int -> Vector b -> Vector a
272 {-# INLINE unsafeAccumulate_ #-}
273 unsafeAccumulate_ = G.unsafeAccumulate_
274
275 accum :: (a -> b -> a) -> Vector a -> [(Int,b)] -> Vector a
276 {-# INLINE accum #-}
277 accum = G.accum
278
279 accumulate :: (a -> b -> a) -> Vector a -> Vector (Int,b) -> Vector a
280 {-# INLINE accumulate #-}
281 accumulate = G.accumulate
282
283 accumulate_ :: (a -> b -> a) -> Vector a -> Vector Int -> Vector b -> Vector a
284 {-# INLINE accumulate_ #-}
285 accumulate_ = G.accumulate_
286
287 unsafeUpd :: Vector a -> [(Int, a)] -> Vector a
288 {-# INLINE unsafeUpd #-}
289 unsafeUpd = G.unsafeUpd
290
291 unsafeUpdate :: Vector a -> Vector (Int, a) -> Vector a
292 {-# INLINE unsafeUpdate #-}
293 unsafeUpdate = G.unsafeUpdate
294
295 unsafeUpdate_ :: Vector a -> Vector Int -> Vector a -> Vector a
296 {-# INLINE unsafeUpdate_ #-}
297 unsafeUpdate_ = G.unsafeUpdate_
298
299 (//) :: Vector a -> [(Int, a)] -> Vector a
300 {-# INLINE (//) #-}
301 (//) = (G.//)
302
303 update :: Vector a -> Vector (Int, a) -> Vector a
304 {-# INLINE update #-}
305 update = G.update
306
307 update_ :: Vector a -> Vector Int -> Vector a -> Vector a
308 {-# INLINE update_ #-}
309 update_ = G.update_
310
311 backpermute :: Vector a -> Vector Int -> Vector a
312 {-# INLINE backpermute #-}
313 backpermute = G.backpermute
314
315 reverse :: Vector a -> Vector a
316 {-# INLINE reverse #-}
317 reverse = G.reverse
318
319 -- Mapping
320 -- -------
321
322 -- | Map a function over a vector
323 map :: (a -> b) -> Vector a -> Vector b
324 {-# INLINE map #-}
325 map = G.map
326
327 concatMap :: (a -> Vector b) -> Vector a -> Vector b
328 {-# INLINE concatMap #-}
329 concatMap = G.concatMap
330
331 -- Zipping/unzipping
332 -- -----------------
333
334 -- | Zip two vectors with the given function.
335 zipWith :: (a -> b -> c) -> Vector a -> Vector b -> Vector c
336 {-# INLINE zipWith #-}
337 zipWith = G.zipWith
338
339 -- | Zip three vectors with the given function.
340 zipWith3 :: (a -> b -> c -> d) -> Vector a -> Vector b -> Vector c -> Vector d
341 {-# INLINE zipWith3 #-}
342 zipWith3 = G.zipWith3
343
344 zipWith4 :: (a -> b -> c -> d -> e)
345 -> Vector a -> Vector b -> Vector c -> Vector d -> Vector e
346 {-# INLINE zipWith4 #-}
347 zipWith4 = G.zipWith4
348
349 zipWith5 :: (a -> b -> c -> d -> e -> f)
350 -> Vector a -> Vector b -> Vector c -> Vector d -> Vector e
351 -> Vector f
352 {-# INLINE zipWith5 #-}
353 zipWith5 = G.zipWith5
354
355 zipWith6 :: (a -> b -> c -> d -> e -> f -> g)
356 -> Vector a -> Vector b -> Vector c -> Vector d -> Vector e
357 -> Vector f -> Vector g
358 {-# INLINE zipWith6 #-}
359 zipWith6 = G.zipWith6
360
361 zip :: Vector a -> Vector b -> Vector (a, b)
362 {-# INLINE zip #-}
363 zip = G.zip
364
365 zip3 :: Vector a -> Vector b -> Vector c -> Vector (a, b, c)
366 {-# INLINE zip3 #-}
367 zip3 = G.zip3
368
369 zip4 :: Vector a -> Vector b -> Vector c -> Vector d
370 -> Vector (a, b, c, d)
371 {-# INLINE zip4 #-}
372 zip4 = G.zip4
373
374 zip5 :: Vector a -> Vector b -> Vector c -> Vector d -> Vector e
375 -> Vector (a, b, c, d, e)
376 {-# INLINE zip5 #-}
377 zip5 = G.zip5
378
379 zip6 :: Vector a -> Vector b -> Vector c -> Vector d -> Vector e -> Vector f
380 -> Vector (a, b, c, d, e, f)
381 {-# INLINE zip6 #-}
382 zip6 = G.zip6
383
384 unzip :: Vector (a, b) -> (Vector a, Vector b)
385 {-# INLINE unzip #-}
386 unzip = G.unzip
387
388 unzip3 :: Vector (a, b, c) -> (Vector a, Vector b, Vector c)
389 {-# INLINE unzip3 #-}
390 unzip3 = G.unzip3
391
392 unzip4 :: Vector (a, b, c, d) -> (Vector a, Vector b, Vector c, Vector d)
393 {-# INLINE unzip4 #-}
394 unzip4 = G.unzip4
395
396 unzip5 :: Vector (a, b, c, d, e)
397 -> (Vector a, Vector b, Vector c, Vector d, Vector e)
398 {-# INLINE unzip5 #-}
399 unzip5 = G.unzip5
400
401 unzip6 :: Vector (a, b, c, d, e, f)
402 -> (Vector a, Vector b, Vector c, Vector d, Vector e, Vector f)
403 {-# INLINE unzip6 #-}
404 unzip6 = G.unzip6
405
406 -- Filtering
407 -- ---------
408
409 -- | Drop elements which do not satisfy the predicate
410 filter :: (a -> Bool) -> Vector a -> Vector a
411 {-# INLINE filter #-}
412 filter = G.filter
413
414 -- | Yield the longest prefix of elements satisfying the predicate.
415 takeWhile :: (a -> Bool) -> Vector a -> Vector a
416 {-# INLINE takeWhile #-}
417 takeWhile = G.takeWhile
418
419 -- | Drop the longest prefix of elements that satisfy the predicate.
420 dropWhile :: (a -> Bool) -> Vector a -> Vector a
421 {-# INLINE dropWhile #-}
422 dropWhile = G.dropWhile
423
424 -- Searching
425 -- ---------
426
427 infix 4 `elem`
428 -- | Check whether the vector contains an element
429 elem :: Eq a => a -> Vector a -> Bool
430 {-# INLINE elem #-}
431 elem = G.elem
432
433 infix 4 `notElem`
434 -- | Inverse of `elem`
435 notElem :: Eq a => a -> Vector a -> Bool
436 {-# INLINE notElem #-}
437 notElem = G.notElem
438
439 -- | Yield 'Just' the first element matching the predicate or 'Nothing' if no
440 -- such element exists.
441 find :: (a -> Bool) -> Vector a -> Maybe a
442 {-# INLINE find #-}
443 find = G.find
444
445 -- | Yield 'Just' the index of the first element matching the predicate or
446 -- 'Nothing' if no such element exists.
447 findIndex :: (a -> Bool) -> Vector a -> Maybe Int
448 {-# INLINE findIndex #-}
449 findIndex = G.findIndex
450
451 -- Folding
452 -- -------
453
454 -- | Left fold
455 foldl :: (a -> b -> a) -> a -> Vector b -> a
456 {-# INLINE foldl #-}
457 foldl = G.foldl
458
459 -- | Lefgt fold on non-empty vectors
460 foldl1 :: (a -> a -> a) -> Vector a -> a
461 {-# INLINE foldl1 #-}
462 foldl1 = G.foldl1
463
464 -- | Left fold with strict accumulator
465 foldl' :: (a -> b -> a) -> a -> Vector b -> a
466 {-# INLINE foldl' #-}
467 foldl' = G.foldl'
468
469 -- | Left fold on non-empty vectors with strict accumulator
470 foldl1' :: (a -> a -> a) -> Vector a -> a
471 {-# INLINE foldl1' #-}
472 foldl1' = G.foldl1'
473
474 -- | Right fold
475 foldr :: (a -> b -> b) -> b -> Vector a -> b
476 {-# INLINE foldr #-}
477 foldr = G.foldr
478
479 -- | Right fold on non-empty vectors
480 foldr1 :: (a -> a -> a) -> Vector a -> a
481 {-# INLINE foldr1 #-}
482 foldr1 = G.foldr1
483
484 -- Specialised folds
485 -- -----------------
486
487 and :: Vector Bool -> Bool
488 {-# INLINE and #-}
489 and = G.and
490
491 or :: Vector Bool -> Bool
492 {-# INLINE or #-}
493 or = G.or
494
495 sum :: Num a => Vector a -> a
496 {-# INLINE sum #-}
497 sum = G.sum
498
499 product :: Num a => Vector a -> a
500 {-# INLINE product #-}
501 product = G.product
502
503 maximum :: Ord a => Vector a -> a
504 {-# INLINE maximum #-}
505 maximum = G.maximum
506
507 minimum :: Ord a => Vector a -> a
508 {-# INLINE minimum #-}
509 minimum = G.minimum
510
511 -- Unfolding
512 -- ---------
513
514 unfoldr :: (b -> Maybe (a, b)) -> b -> Vector a
515 {-# INLINE unfoldr #-}
516 unfoldr = G.unfoldr
517
518 -- Scans
519 -- -----
520
521 -- | Prefix scan
522 prescanl :: (a -> b -> a) -> a -> Vector b -> Vector a
523 {-# INLINE prescanl #-}
524 prescanl = G.prescanl
525
526 -- | Prefix scan with strict accumulator
527 prescanl' :: (a -> b -> a) -> a -> Vector b -> Vector a
528 {-# INLINE prescanl' #-}
529 prescanl' = G.prescanl'
530
531 -- | Suffix scan
532 postscanl :: (a -> b -> a) -> a -> Vector b -> Vector a
533 {-# INLINE postscanl #-}
534 postscanl = G.postscanl
535
536 -- | Suffix scan with strict accumulator
537 postscanl' :: (a -> b -> a) -> a -> Vector b -> Vector a
538 {-# INLINE postscanl' #-}
539 postscanl' = G.postscanl'
540
541 -- | Haskell-style scan
542 scanl :: (a -> b -> a) -> a -> Vector b -> Vector a
543 {-# INLINE scanl #-}
544 scanl = G.scanl
545
546 -- | Haskell-style scan with strict accumulator
547 scanl' :: (a -> b -> a) -> a -> Vector b -> Vector a
548 {-# INLINE scanl' #-}
549 scanl' = G.scanl'
550
551 -- | Scan over a non-empty 'Vector'
552 scanl1 :: (a -> a -> a) -> Vector a -> Vector a
553 {-# INLINE scanl1 #-}
554 scanl1 = G.scanl1
555
556 -- | Scan over a non-empty 'Vector' with a strict accumulator
557 scanl1' :: (a -> a -> a) -> Vector a -> Vector a
558 {-# INLINE scanl1' #-}
559 scanl1' = G.scanl1'
560
561 -- Enumeration
562 -- -----------
563
564 enumFromTo :: Enum a => a -> a -> Vector a
565 {-# INLINE enumFromTo #-}
566 enumFromTo = G.enumFromTo
567
568 enumFromThenTo :: Enum a => a -> a -> a -> Vector a
569 {-# INLINE enumFromThenTo #-}
570 enumFromThenTo = G.enumFromThenTo
571
572 -- Conversion to/from lists
573 -- ------------------------
574
575 -- | Convert a vector to a list
576 toList :: Vector a -> [a]
577 {-# INLINE toList #-}
578 toList = G.toList
579
580 -- | Convert a list to a vector
581 fromList :: [a] -> Vector a
582 {-# INLINE fromList #-}
583 fromList = G.fromList
584