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