Rename rule
[darcs-mirrors/vector.git] / Data / Vector / IVector.hs
1 {-# LANGUAGE Rank2Types, MultiParamTypeClasses #-}
2 -- |
3 -- Module : Data.Vector.IVector
4 -- Copyright : (c) Roman Leshchinskiy 2008
5 -- License : BSD-style
6 --
7 -- Maintainer : rl@cse.unsw.edu.au
8 -- Stability : experimental
9 -- Portability : non-portable
10 --
11 -- Generic interface to pure vectors
12 --
13
14 #include "phases.h"
15
16 module Data.Vector.IVector (
17 -- * Immutable vectors
18 IVector,
19
20 -- * Length information
21 length,
22
23 -- * Construction
24 empty, singleton, cons, snoc, replicate, (++),
25
26 -- * Accessing individual elements
27 (!), head, last,
28
29 -- * Subvectors
30 slice, takeSlice, take, dropSlice, drop,
31
32 -- * Mapping and zipping
33 map, zipWith,
34
35 -- * Filtering
36 filter, takeWhileSlice, takeWhile, dropWhileSlice, dropWhile,
37
38 -- * Searching
39 elem, notElem, find, findIndex,
40
41 -- * Folding
42 foldl, foldl1, foldl', foldl1', foldr, foldr1,
43
44 -- * Conversion to/from lists
45 toList, fromList,
46
47 -- * Conversion to/from Streams
48 stream, unstream,
49
50 -- * MVector-based initialisation
51 create,
52
53 -- * Unsafe functions
54 unsafeSlice, unsafeIndex
55 ) where
56
57 import qualified Data.Vector.MVector as MVector
58 import Data.Vector.MVector ( MVector )
59
60 import qualified Data.Vector.Stream as Stream
61 import Data.Vector.Stream ( Stream )
62 import Data.Vector.Stream.Size
63
64 import Control.Exception ( assert )
65
66 import Prelude hiding ( length,
67 replicate, (++),
68 head, last,
69 init, tail, take, drop,
70 map, zipWith,
71 filter, takeWhile, dropWhile,
72 elem, notElem,
73 foldl, foldl1, foldr, foldr1 )
74
75 -- | Class of immutable vectors. Just like with 'MVector', the type of the
76 -- elements can be restricted by using GADTs.
77 --
78 class IVector v a where
79 -- | Construct a pure vector from a monadic initialiser.
80 create :: (forall mv m. MVector mv m a => m (mv m a)) -> v a
81
82 -- | Length of the vector
83 length :: v a -> Int
84
85 -- | Yield a part of the vector without copying it. No range checks!
86 unsafeSlice :: v a -> Int -> Int -> v a
87
88 -- | Apply the given function to the element at the given position. This
89 -- interface prevents us from being too lazy. Suppose we had
90 --
91 -- > unsafeIndex' :: v a -> Int -> a
92 --
93 -- instead. Now, if we wanted to copy a vector, we'd do something like
94 --
95 -- > copy mv v ... = ... unsafeWrite mv i (unsafeIndex' v i) ...
96 --
97 -- For lazy vectors, the indexing would not be evaluated which means that we
98 -- would retain a reference to the original vector in each element we write.
99 -- This would be bad!
100 --
101 -- With 'unsafeIndex', we can do
102 --
103 -- > copy mv v ... = ... unsafeIndex v i (unsafeWrite mv i) ...
104 --
105 -- which does not have this problem.
106 --
107 unsafeIndex :: v a -> Int -> (a -> b) -> b
108
109 -- | Convert a vector to a 'Stream'
110 stream :: IVector v a => v a -> Stream a
111 {-# INLINE_STREAM stream #-}
112 stream v = v `seq` (Stream.unfold get 0 `Stream.sized` Exact n)
113 where
114 n = length v
115
116 {-# INLINE get #-}
117 get i | i < n = unsafeIndex v i $ \x -> Just (x, i+1)
118 | otherwise = Nothing
119
120 -- | Create a vector from a 'Stream'
121 unstream :: IVector v a => Stream a -> v a
122 {-# INLINE_STREAM unstream #-}
123 unstream s = create (MVector.unstream s)
124
125 {-# RULES
126
127 "stream/unstream [IVector]" forall s.
128 stream (unstream s) = s
129
130 #-}
131
132 -- Construction
133 -- ------------
134
135 -- | Empty vector
136 empty :: IVector v a => v a
137 {-# INLINE empty #-}
138 empty = unstream Stream.empty
139
140 -- | Vector with exaclty one element
141 singleton :: IVector v a => a -> v a
142 {-# INLINE singleton #-}
143 singleton x = unstream (Stream.singleton x)
144
145 -- | Vector of the given length with the given value in each position
146 replicate :: IVector v a => Int -> a -> v a
147 {-# INLINE replicate #-}
148 replicate n = unstream . Stream.replicate n
149
150 -- | Prepend an element
151 cons :: IVector v a => a -> v a -> v a
152 {-# INLINE cons #-}
153 cons x = unstream . Stream.cons x . stream
154
155 -- | Append an element
156 snoc :: IVector v a => v a -> a -> v a
157 {-# INLINE snoc #-}
158 snoc v = unstream . Stream.snoc (stream v)
159
160 infixr 5 ++
161 -- | Concatenate two vectors
162 (++) :: IVector v a => v a -> v a -> v a
163 {-# INLINE (++) #-}
164 v ++ w = unstream (stream v Stream.++ stream w)
165
166 -- Accessing individual elements
167 -- -----------------------------
168
169 -- | Indexing
170 (!) :: IVector v a => v a -> Int -> a
171 {-# INLINE (!) #-}
172 v ! i = assert (i >= 0 && i < length v)
173 $ unsafeIndex v i id
174
175 -- | First element
176 head :: IVector v a => v a -> a
177 {-# INLINE head #-}
178 head v = v ! 0
179
180 -- | Last element
181 last :: IVector v a => v a -> a
182 {-# INLINE last #-}
183 last v = v ! (length v - 1)
184
185 -- Subarrays
186 -- ---------
187
188 -- | Yield a part of the vector without copying it. Safer version of
189 -- 'unsafeSlice'.
190 slice :: IVector v a => v a -> Int -- ^ starting index
191 -> Int -- ^ length
192 -> v a
193 {-# INLINE slice #-}
194 slice v i n = assert (i >= 0 && n >= 0 && i+n <= length v)
195 $ unsafeSlice v i n
196
197 -- | Yield the first @n@ elements without copying.
198 takeSlice :: IVector v a => Int -> v a -> v a
199 {-# INLINE takeSlice #-}
200 takeSlice n v = slice v 0 n
201
202 -- | Copy the first @n@ elements to a new vector.
203 take :: IVector v a => Int -> v a -> v a
204 {-# INLINE take #-}
205 take n = unstream . Stream.take n . stream
206
207 -- | Yield all but the first @n@ elements without copying.
208 dropSlice :: IVector v a => Int -> v a -> v a
209 {-# INLINE dropSlice #-}
210 dropSlice n v = slice v n (length v - n)
211
212 -- | Copy all but the first @n@ elements to a new vectors.
213 drop :: IVector v a => Int -> v a -> v a
214 {-# INLINE drop #-}
215 drop n = unstream . Stream.drop n . stream
216
217 -- Mapping/zipping
218 -- ---------------
219
220 -- | Map a function over a vector
221 map :: (IVector v a, IVector v b) => (a -> b) -> v a -> v b
222 {-# INLINE map #-}
223 map f = unstream . Stream.map f . stream
224
225 -- | Zip two vectors with the given function.
226 zipWith :: (IVector v a, IVector v b, IVector v c) => (a -> b -> c) -> v a -> v b -> v c
227 {-# INLINE zipWith #-}
228 zipWith f xs ys = unstream (Stream.zipWith f (stream xs) (stream ys))
229
230 -- Filtering
231 -- ---------
232
233 -- | Drop elements which do not satisfy the predicate
234 filter :: IVector v a => (a -> Bool) -> v a -> v a
235 {-# INLINE filter #-}
236 filter f = unstream . Stream.filter f . stream
237
238 -- | Yield the longest prefix of elements satisfying the predicate without
239 -- copying.
240 takeWhileSlice :: IVector v a => (a -> Bool) -> v a -> v a
241 {-# INLINE takeWhileSlice #-}
242 takeWhileSlice f v = case findIndex (not . f) v of
243 Just n -> takeSlice n v
244 Nothing -> v
245
246 -- | Copy the longest prefix of elements satisfying the predicate to a new
247 -- vector
248 takeWhile :: IVector v a => (a -> Bool) -> v a -> v a
249 {-# INLINE takeWhile #-}
250 takeWhile f = unstream . Stream.takeWhile f . stream
251
252 -- | Drop the longest prefix of elements that satisfy the predicate without
253 -- copying
254 dropWhileSlice :: IVector v a => (a -> Bool) -> v a -> v a
255 {-# INLINE dropWhileSlice #-}
256 dropWhileSlice f v = case findIndex (not . f) v of
257 Just n -> dropSlice n v
258 Nothing -> v
259
260 -- | Drop the longest prefix of elements that satisfy the predicate and copy
261 -- the rest to a new vector.
262 dropWhile :: IVector v a => (a -> Bool) -> v a -> v a
263 {-# INLINE dropWhile #-}
264 dropWhile f = unstream . Stream.dropWhile f . stream
265
266 -- Searching
267 -- ---------
268
269 infix 4 `elem`
270 -- | Check whether the vector contains an element
271 elem :: (IVector v a, Eq a) => a -> v a -> Bool
272 {-# INLINE elem #-}
273 elem x = Stream.elem x . stream
274
275 infix 4 `notElem`
276 -- | Inverse of `elem`
277 notElem :: (IVector v a, Eq a) => a -> v a -> Bool
278 {-# INLINE notElem #-}
279 notElem x = Stream.notElem x . stream
280
281 -- | Yield 'Just' the first element matching the predicate or 'Nothing' if no
282 -- such element exists.
283 find :: IVector v a => (a -> Bool) -> v a -> Maybe a
284 {-# INLINE find #-}
285 find f = Stream.find f . stream
286
287 -- | Yield 'Just' the index of the first element matching the predicate or
288 -- 'Nothing' if no such element exists.
289 findIndex :: IVector v a => (a -> Bool) -> v a -> Maybe Int
290 {-# INLINE findIndex #-}
291 findIndex f = Stream.findIndex f . stream
292
293 -- Folding
294 -- -------
295
296 -- | Left fold
297 foldl :: IVector v b => (a -> b -> a) -> a -> v b -> a
298 {-# INLINE foldl #-}
299 foldl f z = Stream.foldl f z . stream
300
301 -- | Lefgt fold on non-empty vectors
302 foldl1 :: IVector v a => (a -> a -> a) -> v a -> a
303 {-# INLINE foldl1 #-}
304 foldl1 f = Stream.foldl1 f . stream
305
306 -- | Left fold with strict accumulator
307 foldl' :: IVector v b => (a -> b -> a) -> a -> v b -> a
308 {-# INLINE foldl' #-}
309 foldl' f z = Stream.foldl' f z . stream
310
311 -- | Left fold on non-empty vectors with strict accumulator
312 foldl1' :: IVector v a => (a -> a -> a) -> v a -> a
313 {-# INLINE foldl1' #-}
314 foldl1' f = Stream.foldl1' f . stream
315
316 -- | Right fold
317 foldr :: IVector v a => (a -> b -> b) -> b -> v a -> b
318 {-# INLINE foldr #-}
319 foldr f z = Stream.foldr f z . stream
320
321 -- | Right fold on non-empty vectors
322 foldr1 :: IVector v a => (a -> a -> a) -> v a -> a
323 {-# INLINE foldr1 #-}
324 foldr1 f = Stream.foldr1 f . stream
325
326 -- | Convert a vector to a list
327 toList :: IVector v a => v a -> [a]
328 {-# INLINE toList #-}
329 toList = Stream.toList . stream
330
331 -- | Convert a list to a vector
332 fromList :: IVector v a => [a] -> v a
333 {-# INLINE fromList #-}
334 fromList = unstream . Stream.fromList
335