Sync Data.Vector exports with Data.Vector.IVector
[darcs-mirrors/vector.git] / Data / Vector.hs
1 {-# LANGUAGE MagicHash, UnboxedTuples, FlexibleInstances, MultiParamTypeClasses #-}
2
3 -- |
4 -- Module : Data.Vector
5 -- Copyright : (c) Roman Leshchinskiy 2008
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,
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
30 -- * Permutations
31 accum, (//), update, backpermute, reverse,
32
33 -- * Mapping
34 map, concatMap,
35
36 -- * Zipping and unzipping
37 zipWith, zipWith3, zip, zip3, unzip, unzip3,
38
39 -- * Filtering
40 filter, takeWhile, dropWhile,
41
42 -- * Searching
43 elem, notElem, find, findIndex,
44
45 -- * Folding
46 foldl, foldl1, foldl', foldl1', foldr, foldr1,
47
48 -- * Specialised folds
49 and, or, sum, product, maximum, minimum,
50
51 -- * Unfolding
52 unfoldr,
53
54 -- * Scans
55 prescanl, prescanl',
56
57 -- * Enumeration
58 enumFromTo, enumFromThenTo,
59
60 -- * Conversion to/from lists
61 toList, fromList
62 ) where
63
64 import Data.Vector.IVector ( IVector(..) )
65 import qualified Data.Vector.IVector as IV
66 import qualified Data.Vector.Mutable.ST as Mut
67
68 import Control.Monad.ST ( runST )
69
70 import GHC.ST ( ST(..) )
71 import GHC.Prim ( Array#, unsafeFreezeArray#, indexArray#, (+#) )
72 import GHC.Base ( Int(..) )
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 enumFromTo, enumFromThenTo )
85
86 import qualified Prelude
87
88 data Vector a = Vector {-# UNPACK #-} !Int
89 {-# UNPACK #-} !Int
90 (Array# a)
91
92 instance Show a => Show (Vector a) where
93 show = (Prelude.++ " :: Data.Vector.Vector") . ("fromList " Prelude.++) . show . toList
94
95 instance IVector Vector a where
96 {-# INLINE vnew #-}
97 vnew init = runST (do
98 Mut.Vector i n marr# <- init
99 ST (\s# -> case unsafeFreezeArray# marr# s# of
100 (# s2#, arr# #) -> (# s2#, Vector i n arr# #)))
101
102 {-# INLINE vlength #-}
103 vlength (Vector _ n _) = n
104
105 {-# INLINE unsafeSlice #-}
106 unsafeSlice (Vector i _ arr#) j n = Vector (i+j) n arr#
107
108 {-# INLINE unsafeIndexM #-}
109 unsafeIndexM (Vector (I# i#) _ arr#) (I# j#)
110 = case indexArray# arr# (i# +# j#) of (# x #) -> return x
111
112 instance Eq a => Eq (Vector a) where
113 {-# INLINE (==) #-}
114 (==) = IV.eq
115
116 instance Ord a => Ord (Vector a) where
117 {-# INLINE compare #-}
118 compare = IV.cmp
119
120 -- Length
121 -- ------
122
123 length :: Vector a -> Int
124 {-# INLINE length #-}
125 length = IV.length
126
127 null :: Vector a -> Bool
128 {-# INLINE null #-}
129 null = IV.null
130
131 -- Construction
132 -- ------------
133
134 -- | Empty vector
135 empty :: Vector a
136 {-# INLINE empty #-}
137 empty = IV.empty
138
139 -- | Vector with exaclty one element
140 singleton :: a -> Vector a
141 {-# INLINE singleton #-}
142 singleton = IV.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 = IV.replicate
148
149 -- | Prepend an element
150 cons :: a -> Vector a -> Vector a
151 {-# INLINE cons #-}
152 cons = IV.cons
153
154 -- | Append an element
155 snoc :: Vector a -> a -> Vector a
156 {-# INLINE snoc #-}
157 snoc = IV.snoc
158
159 infixr 5 ++
160 -- | Concatenate two vectors
161 (++) :: Vector a -> Vector a -> Vector a
162 {-# INLINE (++) #-}
163 (++) = (IV.++)
164
165 -- | Create a copy of a vector. Useful when dealing with slices.
166 copy :: Vector a -> Vector a
167 {-# INLINE copy #-}
168 copy = IV.copy
169
170 -- Accessing individual elements
171 -- -----------------------------
172
173 -- | Indexing
174 (!) :: Vector a -> Int -> a
175 {-# INLINE (!) #-}
176 (!) = (IV.!)
177
178 -- | First element
179 head :: Vector a -> a
180 {-# INLINE head #-}
181 head = IV.head
182
183 -- | Last element
184 last :: Vector a -> a
185 {-# INLINE last #-}
186 last = IV.last
187
188 -- | Monadic indexing which can be strict in the vector while remaining lazy in
189 -- the element
190 indexM :: Monad m => Vector a -> Int -> m a
191 {-# INLINE indexM #-}
192 indexM = IV.indexM
193
194 headM :: Monad m => Vector a -> m a
195 {-# INLINE headM #-}
196 headM = IV.headM
197
198 lastM :: Monad m => Vector a -> m a
199 {-# INLINE lastM #-}
200 lastM = IV.lastM
201
202 -- Subarrays
203 -- ---------
204
205 -- | Yield a part of the vector without copying it. Safer version of
206 -- 'unsafeSlice'.
207 slice :: Vector a -> Int -- ^ starting index
208 -> Int -- ^ length
209 -> Vector a
210 {-# INLINE slice #-}
211 slice = IV.slice
212
213 -- | Yield all but the last element without copying.
214 init :: Vector a -> Vector a
215 {-# INLINE init #-}
216 init = IV.init
217
218 -- | All but the first element (without copying).
219 tail :: Vector a -> Vector a
220 {-# INLINE tail #-}
221 tail = IV.tail
222
223 -- | Yield the first @n@ elements without copying.
224 take :: Int -> Vector a -> Vector a
225 {-# INLINE take #-}
226 take = IV.take
227
228 -- | Yield all but the first @n@ elements without copying.
229 drop :: Int -> Vector a -> Vector a
230 {-# INLINE drop #-}
231 drop = IV.drop
232
233 -- Permutations
234 -- ------------
235
236 accum :: (a -> b -> a) -> Vector a -> [(Int,b)] -> Vector a
237 {-# INLINE accum #-}
238 accum = IV.accum
239
240 (//) :: Vector a -> [(Int, a)] -> Vector a
241 {-# INLINE (//) #-}
242 (//) = (IV.//)
243
244 update :: Vector a -> Vector (Int, a) -> Vector a
245 {-# INLINE update #-}
246 update = IV.update
247
248 backpermute :: Vector a -> Vector Int -> Vector a
249 {-# INLINE backpermute #-}
250 backpermute = IV.backpermute
251
252 reverse :: Vector a -> Vector a
253 {-# INLINE reverse #-}
254 reverse = IV.reverse
255
256 -- Mapping
257 -- -------
258
259 -- | Map a function over a vector
260 map :: (a -> b) -> Vector a -> Vector b
261 {-# INLINE map #-}
262 map = IV.map
263
264 concatMap :: (a -> Vector b) -> Vector a -> Vector b
265 {-# INLINE concatMap #-}
266 concatMap = IV.concatMap
267
268 -- Zipping/unzipping
269 -- -----------------
270
271 -- | Zip two vectors with the given function.
272 zipWith :: (a -> b -> c) -> Vector a -> Vector b -> Vector c
273 {-# INLINE zipWith #-}
274 zipWith = IV.zipWith
275
276 -- | Zip three vectors with the given function.
277 zipWith3 :: (a -> b -> c -> d) -> Vector a -> Vector b -> Vector c -> Vector d
278 {-# INLINE zipWith3 #-}
279 zipWith3 = IV.zipWith3
280
281 zip :: Vector a -> Vector b -> Vector (a, b)
282 {-# INLINE zip #-}
283 zip = IV.zip
284
285 zip3 :: Vector a -> Vector b -> Vector c -> Vector (a, b, c)
286 {-# INLINE zip3 #-}
287 zip3 = IV.zip3
288
289 unzip :: Vector (a, b) -> (Vector a, Vector b)
290 {-# INLINE unzip #-}
291 unzip = IV.unzip
292
293 unzip3 :: Vector (a, b, c) -> (Vector a, Vector b, Vector c)
294 {-# INLINE unzip3 #-}
295 unzip3 = IV.unzip3
296
297 -- Filtering
298 -- ---------
299
300 -- | Drop elements which do not satisfy the predicate
301 filter :: (a -> Bool) -> Vector a -> Vector a
302 {-# INLINE filter #-}
303 filter = IV.filter
304
305 -- | Yield the longest prefix of elements satisfying the predicate.
306 takeWhile :: (a -> Bool) -> Vector a -> Vector a
307 {-# INLINE takeWhile #-}
308 takeWhile = IV.takeWhile
309
310 -- | Drop the longest prefix of elements that satisfy the predicate.
311 dropWhile :: (a -> Bool) -> Vector a -> Vector a
312 {-# INLINE dropWhile #-}
313 dropWhile = IV.dropWhile
314
315 -- Searching
316 -- ---------
317
318 infix 4 `elem`
319 -- | Check whether the vector contains an element
320 elem :: Eq a => a -> Vector a -> Bool
321 {-# INLINE elem #-}
322 elem = IV.elem
323
324 infix 4 `notElem`
325 -- | Inverse of `elem`
326 notElem :: Eq a => a -> Vector a -> Bool
327 {-# INLINE notElem #-}
328 notElem = IV.notElem
329
330 -- | Yield 'Just' the first element matching the predicate or 'Nothing' if no
331 -- such element exists.
332 find :: (a -> Bool) -> Vector a -> Maybe a
333 {-# INLINE find #-}
334 find = IV.find
335
336 -- | Yield 'Just' the index of the first element matching the predicate or
337 -- 'Nothing' if no such element exists.
338 findIndex :: (a -> Bool) -> Vector a -> Maybe Int
339 {-# INLINE findIndex #-}
340 findIndex = IV.findIndex
341
342 -- Folding
343 -- -------
344
345 -- | Left fold
346 foldl :: (a -> b -> a) -> a -> Vector b -> a
347 {-# INLINE foldl #-}
348 foldl = IV.foldl
349
350 -- | Lefgt fold on non-empty vectors
351 foldl1 :: (a -> a -> a) -> Vector a -> a
352 {-# INLINE foldl1 #-}
353 foldl1 = IV.foldl1
354
355 -- | Left fold with strict accumulator
356 foldl' :: (a -> b -> a) -> a -> Vector b -> a
357 {-# INLINE foldl' #-}
358 foldl' = IV.foldl'
359
360 -- | Left fold on non-empty vectors with strict accumulator
361 foldl1' :: (a -> a -> a) -> Vector a -> a
362 {-# INLINE foldl1' #-}
363 foldl1' = IV.foldl1'
364
365 -- | Right fold
366 foldr :: (a -> b -> b) -> b -> Vector a -> b
367 {-# INLINE foldr #-}
368 foldr = IV.foldr
369
370 -- | Right fold on non-empty vectors
371 foldr1 :: (a -> a -> a) -> Vector a -> a
372 {-# INLINE foldr1 #-}
373 foldr1 = IV.foldr1
374
375 -- Specialised folds
376 -- -----------------
377
378 and :: Vector Bool -> Bool
379 {-# INLINE and #-}
380 and = IV.and
381
382 or :: Vector Bool -> Bool
383 {-# INLINE or #-}
384 or = IV.or
385
386 sum :: Num a => Vector a -> a
387 {-# INLINE sum #-}
388 sum = IV.sum
389
390 product :: Num a => Vector a -> a
391 {-# INLINE product #-}
392 product = IV.product
393
394 maximum :: Ord a => Vector a -> a
395 {-# INLINE maximum #-}
396 maximum = IV.maximum
397
398 minimum :: Ord a => Vector a -> a
399 {-# INLINE minimum #-}
400 minimum = IV.minimum
401
402 -- Unfolding
403 -- ---------
404
405 unfoldr :: (b -> Maybe (a, b)) -> b -> Vector a
406 {-# INLINE unfoldr #-}
407 unfoldr = IV.unfoldr
408
409 -- Scans
410 -- -----
411
412 -- | Prefix scan
413 prescanl :: (a -> b -> a) -> a -> Vector b -> Vector a
414 {-# INLINE prescanl #-}
415 prescanl = IV.prescanl
416
417 -- | Prefix scan with strict accumulator
418 prescanl' :: (a -> b -> a) -> a -> Vector b -> Vector a
419 {-# INLINE prescanl' #-}
420 prescanl' = IV.prescanl'
421
422 -- Enumeration
423 -- -----------
424
425 enumFromTo :: Enum a => a -> a -> Vector a
426 {-# INLINE enumFromTo #-}
427 enumFromTo = IV.enumFromTo
428
429 enumFromThenTo :: Enum a => a -> a -> a -> Vector a
430 {-# INLINE enumFromThenTo #-}
431 enumFromThenTo = IV.enumFromThenTo
432
433 -- Conversion to/from lists
434 -- ------------------------
435
436 -- | Convert a vector to a list
437 toList :: Vector a -> [a]
438 {-# INLINE toList #-}
439 toList = IV.toList
440
441 -- | Convert a list to a vector
442 fromList :: [a] -> Vector a
443 {-# INLINE fromList #-}
444 fromList = IV.fromList
445