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