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