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