Data.Vector.reverse
[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,
26
27 -- * Subvectors
28 slice, init, tail, take, drop,
29
30 -- * Permutations
31 accum, (//), update, backpermute, reverse,
32
33 -- * Mapping and zipping
34 map, zipWith, zip,
35
36 -- * Filtering
37 filter, takeWhile, dropWhile,
38
39 -- * Searching
40 elem, notElem, find, findIndex,
41
42 -- * Folding
43 foldl, foldl1, foldl', foldl1', foldr, foldr1,
44
45 -- * Scans
46 prescanl, prescanl',
47
48 -- * Conversion to/from lists
49 toList, fromList
50 ) where
51
52 import Data.Vector.IVector ( IVector(..) )
53 import qualified Data.Vector.IVector as IV
54 import qualified Data.Vector.Mutable.ST as Mut
55
56 import Control.Monad.ST ( runST )
57
58 import GHC.ST ( ST(..) )
59 import GHC.Prim ( Array#, unsafeFreezeArray#, indexArray#, (+#) )
60 import GHC.Base ( Int(..) )
61
62 import Prelude hiding ( length, null,
63 replicate, (++),
64 head, last,
65 init, tail, take, drop, reverse,
66 map, zipWith, zip,
67 filter, takeWhile, dropWhile,
68 elem, notElem,
69 foldl, foldl1, foldr, foldr1 )
70
71 import qualified Prelude
72
73 data Vector a = Vector {-# UNPACK #-} !Int
74 {-# UNPACK #-} !Int
75 (Array# a)
76
77 instance Show a => Show (Vector a) where
78 show = (Prelude.++ " :: Data.Vector.Vector") . ("fromList " Prelude.++) . show . toList
79
80 instance IVector Vector a where
81 {-# INLINE vnew #-}
82 vnew init = runST (do
83 Mut.Vector i n marr# <- init
84 ST (\s# -> case unsafeFreezeArray# marr# s# of
85 (# s2#, arr# #) -> (# s2#, Vector i n arr# #)))
86
87 {-# INLINE vlength #-}
88 vlength (Vector _ n _) = n
89
90 {-# INLINE unsafeSlice #-}
91 unsafeSlice (Vector i _ arr#) j n = Vector (i+j) n arr#
92
93 {-# INLINE unsafeIndex #-}
94 unsafeIndex (Vector (I# i#) _ arr#) (I# j#) f
95 = case indexArray# arr# (i# +# j#) of (# x #) -> f x
96
97 instance Eq a => Eq (Vector a) where
98 {-# INLINE (==) #-}
99 (==) = IV.eq
100
101 instance Ord a => Ord (Vector a) where
102 {-# INLINE compare #-}
103 compare = IV.cmp
104
105 -- Length
106 -- ------
107
108 length :: Vector a -> Int
109 {-# INLINE length #-}
110 length = IV.length
111
112 null :: Vector a -> Bool
113 {-# INLINE null #-}
114 null = IV.null
115
116 -- Construction
117 -- ------------
118
119 -- | Empty vector
120 empty :: Vector a
121 {-# INLINE empty #-}
122 empty = IV.empty
123
124 -- | Vector with exaclty one element
125 singleton :: a -> Vector a
126 {-# INLINE singleton #-}
127 singleton = IV.singleton
128
129 -- | Vector of the given length with the given value in each position
130 replicate :: Int -> a -> Vector a
131 {-# INLINE replicate #-}
132 replicate = IV.replicate
133
134 -- | Prepend an element
135 cons :: a -> Vector a -> Vector a
136 {-# INLINE cons #-}
137 cons = IV.cons
138
139 -- | Append an element
140 snoc :: Vector a -> a -> Vector a
141 {-# INLINE snoc #-}
142 snoc = IV.snoc
143
144 infixr 5 ++
145 -- | Concatenate two vectors
146 (++) :: Vector a -> Vector a -> Vector a
147 {-# INLINE (++) #-}
148 (++) = (IV.++)
149
150 -- | Create a copy of a vector. Useful when dealing with slices.
151 copy :: Vector a -> Vector a
152 {-# INLINE copy #-}
153 copy = IV.copy
154
155 -- Accessing individual elements
156 -- -----------------------------
157
158 -- | Indexing
159 (!) :: Vector a -> Int -> a
160 {-# INLINE (!) #-}
161 (!) = (IV.!)
162
163 -- | First element
164 head :: Vector a -> a
165 {-# INLINE head #-}
166 head = IV.head
167
168 -- | Last element
169 last :: Vector a -> a
170 {-# INLINE last #-}
171 last = IV.last
172
173 -- Subarrays
174 -- ---------
175
176 -- | Yield a part of the vector without copying it. Safer version of
177 -- 'unsafeSlice'.
178 slice :: Vector a -> Int -- ^ starting index
179 -> Int -- ^ length
180 -> Vector a
181 {-# INLINE slice #-}
182 slice = IV.slice
183
184 -- | Yield all but the last element without copying.
185 init :: Vector a -> Vector a
186 {-# INLINE init #-}
187 init = IV.init
188
189 -- | All but the first element (without copying).
190 tail :: Vector a -> Vector a
191 {-# INLINE tail #-}
192 tail = IV.tail
193
194 -- | Yield the first @n@ elements without copying.
195 take :: Int -> Vector a -> Vector a
196 {-# INLINE take #-}
197 take = IV.take
198
199 -- | Yield all but the first @n@ elements without copying.
200 drop :: Int -> Vector a -> Vector a
201 {-# INLINE drop #-}
202 drop = IV.drop
203
204 -- Permutations
205 -- ------------
206
207 accum :: (a -> b -> a) -> Vector a -> [(Int,b)] -> Vector a
208 {-# INLINE accum #-}
209 accum = IV.accum
210
211 (//) :: Vector a -> [(Int, a)] -> Vector a
212 {-# INLINE (//) #-}
213 (//) = (IV.//)
214
215 update :: Vector a -> Vector (Int, a) -> Vector a
216 {-# INLINE update #-}
217 update = IV.update
218
219 backpermute :: Vector a -> Vector Int -> Vector a
220 {-# INLINE backpermute #-}
221 backpermute = IV.backpermute
222
223 reverse :: Vector a -> Vector a
224 {-# INLINE reverse #-}
225 reverse = IV.reverse
226
227 -- Mapping/zipping
228 -- ---------------
229
230 -- | Map a function over a vector
231 map :: (a -> b) -> Vector a -> Vector b
232 {-# INLINE map #-}
233 map = IV.map
234
235 -- | Zip two vectors with the given function.
236 zipWith :: (a -> b -> c) -> Vector a -> Vector b -> Vector c
237 {-# INLINE zipWith #-}
238 zipWith = IV.zipWith
239
240 zip :: Vector a -> Vector b -> Vector (a, b)
241 {-# INLINE zip #-}
242 zip = IV.zip
243
244 -- Filtering
245 -- ---------
246
247 -- | Drop elements which do not satisfy the predicate
248 filter :: (a -> Bool) -> Vector a -> Vector a
249 {-# INLINE filter #-}
250 filter = IV.filter
251
252 -- | Yield the longest prefix of elements satisfying the predicate.
253 takeWhile :: (a -> Bool) -> Vector a -> Vector a
254 {-# INLINE takeWhile #-}
255 takeWhile = IV.takeWhile
256
257 -- | Drop the longest prefix of elements that satisfy the predicate.
258 dropWhile :: (a -> Bool) -> Vector a -> Vector a
259 {-# INLINE dropWhile #-}
260 dropWhile = IV.dropWhile
261
262 -- Searching
263 -- ---------
264
265 infix 4 `elem`
266 -- | Check whether the vector contains an element
267 elem :: Eq a => a -> Vector a -> Bool
268 {-# INLINE elem #-}
269 elem = IV.elem
270
271 infix 4 `notElem`
272 -- | Inverse of `elem`
273 notElem :: Eq a => a -> Vector a -> Bool
274 {-# INLINE notElem #-}
275 notElem = IV.notElem
276
277 -- | Yield 'Just' the first element matching the predicate or 'Nothing' if no
278 -- such element exists.
279 find :: (a -> Bool) -> Vector a -> Maybe a
280 {-# INLINE find #-}
281 find = IV.find
282
283 -- | Yield 'Just' the index of the first element matching the predicate or
284 -- 'Nothing' if no such element exists.
285 findIndex :: (a -> Bool) -> Vector a -> Maybe Int
286 {-# INLINE findIndex #-}
287 findIndex = IV.findIndex
288
289 -- Folding
290 -- -------
291
292 -- | Left fold
293 foldl :: (a -> b -> a) -> a -> Vector b -> a
294 {-# INLINE foldl #-}
295 foldl = IV.foldl
296
297 -- | Lefgt fold on non-empty vectors
298 foldl1 :: (a -> a -> a) -> Vector a -> a
299 {-# INLINE foldl1 #-}
300 foldl1 = IV.foldl1
301
302 -- | Left fold with strict accumulator
303 foldl' :: (a -> b -> a) -> a -> Vector b -> a
304 {-# INLINE foldl' #-}
305 foldl' = IV.foldl'
306
307 -- | Left fold on non-empty vectors with strict accumulator
308 foldl1' :: (a -> a -> a) -> Vector a -> a
309 {-# INLINE foldl1' #-}
310 foldl1' = IV.foldl1'
311
312 -- | Right fold
313 foldr :: (a -> b -> b) -> b -> Vector a -> b
314 {-# INLINE foldr #-}
315 foldr = IV.foldr
316
317 -- | Right fold on non-empty vectors
318 foldr1 :: (a -> a -> a) -> Vector a -> a
319 {-# INLINE foldr1 #-}
320 foldr1 = IV.foldr1
321
322 -- Scans
323 -- -----
324
325 -- | Prefix scan
326 prescanl :: (a -> b -> a) -> a -> Vector b -> Vector a
327 {-# INLINE prescanl #-}
328 prescanl = IV.prescanl
329
330 -- | Prefix scan with strict accumulator
331 prescanl' :: (a -> b -> a) -> a -> Vector b -> Vector a
332 {-# INLINE prescanl' #-}
333 prescanl' = IV.prescanl'
334
335 -- | Convert a vector to a list
336 toList :: Vector a -> [a]
337 {-# INLINE toList #-}
338 toList = IV.toList
339
340 -- | Convert a list to a vector
341 fromList :: [a] -> Vector a
342 {-# INLINE fromList #-}
343 fromList = IV.fromList
344