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