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