Change handling of Monad in MVector and get rid of GADTs
[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, extract, 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
56 -- * Utility functions
57 vlength
58 ) where
59
60 import qualified Data.Vector.MVector as MVector
61 import Data.Vector.MVector ( MVector )
62
63 import qualified Data.Vector.Stream as Stream
64 import Data.Vector.Stream ( Stream )
65 import Data.Vector.Stream.Size
66
67 import Control.Exception ( assert )
68
69 import Prelude hiding ( length,
70 replicate, (++),
71 head, last,
72 init, tail, take, drop,
73 map, zipWith,
74 filter, takeWhile, dropWhile,
75 elem, notElem,
76 foldl, foldl1, foldr, foldr1 )
77
78 -- | Class of immutable vectors.
79 --
80 class IVector v a where
81 -- | Construct a pure vector from a monadic initialiser.
82 create :: (forall mv m. MVector mv m a => m (mv a)) -> v a
83
84 -- | Length of the vector (not fusible!)
85 vlength :: v a -> Int
86
87 -- | Yield a part of the vector without copying it. No range checks!
88 unsafeSlice :: v a -> Int -> Int -> v a
89
90 -- | Apply the given function to the element at the given position. This
91 -- interface prevents us from being too lazy. Suppose we had
92 --
93 -- > unsafeIndex' :: v a -> Int -> a
94 --
95 -- instead. Now, if we wanted to copy a vector, we'd do something like
96 --
97 -- > copy mv v ... = ... unsafeWrite mv i (unsafeIndex' v i) ...
98 --
99 -- For lazy vectors, the indexing would not be evaluated which means that we
100 -- would retain a reference to the original vector in each element we write.
101 -- This would be bad!
102 --
103 -- With 'unsafeIndex', we can do
104 --
105 -- > copy mv v ... = ... unsafeIndex v i (unsafeWrite mv i) ...
106 --
107 -- which does not have this problem.
108 --
109 unsafeIndex :: v a -> Int -> (a -> b) -> b
110
111 -- | Convert a vector to a 'Stream'
112 stream :: IVector v a => v a -> Stream a
113 {-# INLINE_STREAM stream #-}
114 stream v = v `seq` (Stream.unfold get 0 `Stream.sized` Exact n)
115 where
116 n = length v
117
118 {-# INLINE get #-}
119 get i | i < n = unsafeIndex v i $ \x -> Just (x, i+1)
120 | otherwise = Nothing
121
122 -- | Create a vector from a 'Stream'
123 unstream :: IVector v a => Stream a -> v a
124 {-# INLINE_STREAM unstream #-}
125 unstream s = create (MVector.unstream s)
126
127 {-# RULES
128
129 "stream/unstream [IVector]" forall s.
130 stream (unstream s) = s
131
132 #-}
133
134 -- Length
135 -- ------
136
137 length :: IVector v a => v a -> Int
138 {-# INLINE_STREAM length #-}
139 length v = vlength v
140
141 {-# RULES
142
143 "length/unstream [IVector]" forall s.
144 length (unstream s) = Stream.length s
145
146 #-}
147
148 -- Construction
149 -- ------------
150
151 -- | Empty vector
152 empty :: IVector v a => v a
153 {-# INLINE empty #-}
154 empty = unstream Stream.empty
155
156 -- | Vector with exaclty one element
157 singleton :: IVector v a => a -> v a
158 {-# INLINE singleton #-}
159 singleton x = unstream (Stream.singleton x)
160
161 -- | Vector of the given length with the given value in each position
162 replicate :: IVector v a => Int -> a -> v a
163 {-# INLINE replicate #-}
164 replicate n = unstream . Stream.replicate n
165
166 -- | Prepend an element
167 cons :: IVector v a => a -> v a -> v a
168 {-# INLINE cons #-}
169 cons x = unstream . Stream.cons x . stream
170
171 -- | Append an element
172 snoc :: IVector v a => v a -> a -> v a
173 {-# INLINE snoc #-}
174 snoc v = unstream . Stream.snoc (stream v)
175
176 infixr 5 ++
177 -- | Concatenate two vectors
178 (++) :: IVector v a => v a -> v a -> v a
179 {-# INLINE (++) #-}
180 v ++ w = unstream (stream v Stream.++ stream w)
181
182 -- Accessing individual elements
183 -- -----------------------------
184
185 -- | Indexing
186 (!) :: IVector v a => v a -> Int -> a
187 {-# INLINE_STREAM (!) #-}
188 v ! i = assert (i >= 0 && i < length v)
189 $ unsafeIndex v i id
190
191 -- | First element
192 head :: IVector v a => v a -> a
193 {-# INLINE_STREAM head #-}
194 head v = v ! 0
195
196 -- | Last element
197 last :: IVector v a => v a -> a
198 {-# INLINE_STREAM last #-}
199 last v = v ! (length v - 1)
200
201 {-# RULES
202
203 "(!)/unstream [IVector]" forall i s.
204 unstream s ! i = s Stream.!! i
205
206 "head/unstream [IVector]" forall s.
207 head (unstream s) = Stream.head s
208
209 "last/unstream [IVector]" forall s.
210 last (unstream s) = Stream.last s
211
212 #-}
213
214 -- Subarrays
215 -- ---------
216
217 -- | Yield a part of the vector without copying it. Safer version of
218 -- 'unsafeSlice'.
219 slice :: IVector v a => v a -> Int -- ^ starting index
220 -> Int -- ^ length
221 -> v a
222 {-# INLINE slice #-}
223 slice v i n = assert (i >= 0 && n >= 0 && i+n <= length v)
224 $ unsafeSlice v i n
225
226 -- | Copy @n@ elements starting at the given position to a new vector.
227 extract :: IVector v a => v a -> Int -- ^ starting index
228 -> Int -- ^ length
229 -> v a
230 {-# INLINE extract #-}
231 extract v i n = unstream (Stream.extract (stream v) i n)
232
233 -- | Yield the first @n@ elements without copying.
234 takeSlice :: IVector v a => Int -> v a -> v a
235 {-# INLINE takeSlice #-}
236 takeSlice n v = slice v 0 n
237
238 -- | Copy the first @n@ elements to a new vector.
239 take :: IVector v a => Int -> v a -> v a
240 {-# INLINE take #-}
241 take n = unstream . Stream.take n . stream
242
243 -- | Yield all but the first @n@ elements without copying.
244 dropSlice :: IVector v a => Int -> v a -> v a
245 {-# INLINE dropSlice #-}
246 dropSlice n v = slice v n (length v - n)
247
248 -- | Copy all but the first @n@ elements to a new vectors.
249 drop :: IVector v a => Int -> v a -> v a
250 {-# INLINE drop #-}
251 drop n = unstream . Stream.drop n . stream
252
253 {-# RULES
254
255 "slice/extract [IVector]" forall i n s.
256 slice (unstream s) i n = extract (unstream s) i n
257
258 "takeSlice/unstream [IVector]" forall n s.
259 takeSlice n (unstream s) = take n (unstream s)
260
261 "dropSlice/unstream [IVector]" forall n s.
262 dropSlice n (unstream s) = drop n (unstream s)
263
264 #-}
265
266 -- Mapping/zipping
267 -- ---------------
268
269 -- | Map a function over a vector
270 map :: (IVector v a, IVector v b) => (a -> b) -> v a -> v b
271 {-# INLINE map #-}
272 map f = unstream . Stream.map f . stream
273
274 -- | Zip two vectors with the given function.
275 zipWith :: (IVector v a, IVector v b, IVector v c) => (a -> b -> c) -> v a -> v b -> v c
276 {-# INLINE zipWith #-}
277 zipWith f xs ys = unstream (Stream.zipWith f (stream xs) (stream ys))
278
279 -- Filtering
280 -- ---------
281
282 -- | Drop elements which do not satisfy the predicate
283 filter :: IVector v a => (a -> Bool) -> v a -> v a
284 {-# INLINE filter #-}
285 filter f = unstream . Stream.filter f . stream
286
287 -- | Yield the longest prefix of elements satisfying the predicate without
288 -- copying.
289 takeWhileSlice :: IVector v a => (a -> Bool) -> v a -> v a
290 {-# INLINE takeWhileSlice #-}
291 takeWhileSlice f v = case findIndex (not . f) v of
292 Just n -> takeSlice n v
293 Nothing -> v
294
295 -- | Copy the longest prefix of elements satisfying the predicate to a new
296 -- vector
297 takeWhile :: IVector v a => (a -> Bool) -> v a -> v a
298 {-# INLINE takeWhile #-}
299 takeWhile f = unstream . Stream.takeWhile f . stream
300
301 -- | Drop the longest prefix of elements that satisfy the predicate without
302 -- copying
303 dropWhileSlice :: IVector v a => (a -> Bool) -> v a -> v a
304 {-# INLINE dropWhileSlice #-}
305 dropWhileSlice f v = case findIndex (not . f) v of
306 Just n -> dropSlice n v
307 Nothing -> v
308
309 -- | Drop the longest prefix of elements that satisfy the predicate and copy
310 -- the rest to a new vector.
311 dropWhile :: IVector v a => (a -> Bool) -> v a -> v a
312 {-# INLINE dropWhile #-}
313 dropWhile f = unstream . Stream.dropWhile f . stream
314
315 {-# RULES
316
317 "takeWhileSlice/unstream" forall f s.
318 takeWhileSlice f (unstream s) = takeWhile f (unstream s)
319
320 "dropWhileSlice/unstream" forall f s.
321 dropWhileSlice f (unstream s) = dropWhile f (unstream s)
322
323 #-}
324
325 -- Searching
326 -- ---------
327
328 infix 4 `elem`
329 -- | Check whether the vector contains an element
330 elem :: (IVector v a, Eq a) => a -> v a -> Bool
331 {-# INLINE elem #-}
332 elem x = Stream.elem x . stream
333
334 infix 4 `notElem`
335 -- | Inverse of `elem`
336 notElem :: (IVector v a, Eq a) => a -> v a -> Bool
337 {-# INLINE notElem #-}
338 notElem x = Stream.notElem x . stream
339
340 -- | Yield 'Just' the first element matching the predicate or 'Nothing' if no
341 -- such element exists.
342 find :: IVector v a => (a -> Bool) -> v a -> Maybe a
343 {-# INLINE find #-}
344 find f = Stream.find f . stream
345
346 -- | Yield 'Just' the index of the first element matching the predicate or
347 -- 'Nothing' if no such element exists.
348 findIndex :: IVector v a => (a -> Bool) -> v a -> Maybe Int
349 {-# INLINE findIndex #-}
350 findIndex f = Stream.findIndex f . stream
351
352 -- Folding
353 -- -------
354
355 -- | Left fold
356 foldl :: IVector v b => (a -> b -> a) -> a -> v b -> a
357 {-# INLINE foldl #-}
358 foldl f z = Stream.foldl f z . stream
359
360 -- | Lefgt fold on non-empty vectors
361 foldl1 :: IVector v a => (a -> a -> a) -> v a -> a
362 {-# INLINE foldl1 #-}
363 foldl1 f = Stream.foldl1 f . stream
364
365 -- | Left fold with strict accumulator
366 foldl' :: IVector v b => (a -> b -> a) -> a -> v b -> a
367 {-# INLINE foldl' #-}
368 foldl' f z = Stream.foldl' f z . stream
369
370 -- | Left fold on non-empty vectors with strict accumulator
371 foldl1' :: IVector v a => (a -> a -> a) -> v a -> a
372 {-# INLINE foldl1' #-}
373 foldl1' f = Stream.foldl1' f . stream
374
375 -- | Right fold
376 foldr :: IVector v a => (a -> b -> b) -> b -> v a -> b
377 {-# INLINE foldr #-}
378 foldr f z = Stream.foldr f z . stream
379
380 -- | Right fold on non-empty vectors
381 foldr1 :: IVector v a => (a -> a -> a) -> v a -> a
382 {-# INLINE foldr1 #-}
383 foldr1 f = Stream.foldr1 f . stream
384
385 -- | Convert a vector to a list
386 toList :: IVector v a => v a -> [a]
387 {-# INLINE toList #-}
388 toList = Stream.toList . stream
389
390 -- | Convert a list to a vector
391 fromList :: IVector v a => [a] -> v a
392 {-# INLINE fromList #-}
393 fromList = unstream . Stream.fromList
394