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