d3b4c2f498cd6d7c3672f0a19fdbf2a26a2c6e4a
[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 -- * Subvectors
27 slice, takeSlice, take, dropSlice, drop,
28
29 -- * Mapping and zipping
30 map, zipWith,
31
32 -- * Filtering
33 filter, takeWhile, dropWhile,
34
35 -- * Folding
36 foldl, foldl1, foldl', foldl1', foldr, foldr1,
37
38 -- * Conversion to/from lists
39 toList, fromList,
40
41 -- * Conversion to/from Streams
42 stream, unstream,
43
44 -- * MVector-based initialisation
45 create,
46
47 -- * Unsafe functions
48 unsafeSlice, unsafeIndex
49 ) where
50
51 import qualified Data.Vector.MVector as MVector
52 import Data.Vector.MVector ( MVector )
53
54 import qualified Data.Vector.Stream as Stream
55 import Data.Vector.Stream ( Stream )
56 import Data.Vector.Stream.Size
57
58 import Control.Exception ( assert )
59
60 import Prelude hiding ( length,
61 replicate, (++),
62 head, last,
63 init, tail, take, drop,
64 map, zipWith,
65 filter, takeWhile, dropWhile,
66 foldl, foldl1, foldr, foldr1 )
67
68 -- | Class of immutable vectors. Just like with 'MVector', the type of the
69 -- elements can be restricted by using GADTs.
70 --
71 class IVector v a where
72 -- | Construct a pure vector from a monadic initialiser.
73 create :: (forall mv m. MVector mv m a => m (mv m a)) -> v a
74
75 -- | Length of the vector
76 length :: v a -> Int
77
78 -- | Yield a part of the vector without copying it. No range checks!
79 unsafeSlice :: v a -> Int -> Int -> v a
80
81 -- | Apply the given function to the element at the given position. This
82 -- interface prevents us from being too lazy. Suppose we had
83 --
84 -- > unsafeIndex' :: v a -> Int -> a
85 --
86 -- instead. Now, if we wanted to copy a vector, we'd do something like
87 --
88 -- > copy mv v ... = ... unsafeWrite mv i (unsafeIndex' v i) ...
89 --
90 -- For lazy vectors, the indexing would not be evaluated which means that we
91 -- would retain a reference to the original vector in each element we write.
92 -- This would be bad!
93 --
94 -- With 'unsafeIndex', we can do
95 --
96 -- > copy mv v ... = ... unsafeIndex v i (unsafeWrite mv i) ...
97 --
98 -- which does not have this problem.
99 --
100 unsafeIndex :: v a -> Int -> (a -> b) -> b
101
102 -- | Convert a vector to a 'Stream'
103 stream :: IVector v a => v a -> Stream a
104 {-# INLINE_STREAM stream #-}
105 stream v = v `seq` (Stream.unfold get 0 `Stream.sized` Exact n)
106 where
107 n = length v
108
109 {-# INLINE get #-}
110 get i | i < n = unsafeIndex v i $ \x -> Just (x, i+1)
111 | otherwise = Nothing
112
113 -- | Create a vector from a 'Stream'
114 unstream :: IVector v a => Stream a -> v a
115 {-# INLINE_STREAM unstream #-}
116 unstream s = create (MVector.unstream s)
117
118 {-# RULES
119
120 "stream/unstream [Vector.IVector]" forall s.
121 stream (unstream s) = s
122
123 #-}
124
125 -- Construction
126 -- ------------
127
128 -- | Empty vector
129 empty :: IVector v a => v a
130 {-# INLINE empty #-}
131 empty = unstream Stream.empty
132
133 -- | Vector with exaclty one element
134 singleton :: IVector v a => a -> v a
135 {-# INLINE singleton #-}
136 singleton x = unstream (Stream.singleton x)
137
138 -- | Vector of the given length with the given value in each position
139 replicate :: IVector v a => Int -> a -> v a
140 {-# INLINE replicate #-}
141 replicate n = unstream . Stream.replicate n
142
143 -- | Prepend an element
144 cons :: IVector v a => a -> v a -> v a
145 {-# INLINE cons #-}
146 cons x = unstream . Stream.cons x . stream
147
148 -- | Append an element
149 snoc :: IVector v a => v a -> a -> v a
150 {-# INLINE snoc #-}
151 snoc v = unstream . Stream.snoc (stream v)
152
153 infixr 5 ++
154 -- | Concatenate two vectors
155 (++) :: IVector v a => v a -> v a -> v a
156 {-# INLINE (++) #-}
157 v ++ w = unstream (stream v Stream.++ stream w)
158
159 -- Subarrays
160 -- ---------
161
162 -- | Yield a part of the vector without copying it. Safer version of
163 -- 'unsafeSlice'.
164 slice :: IVector v a => v a -> Int -- ^ starting index
165 -> Int -- ^ length
166 -> v a
167 {-# INLINE slice #-}
168 slice v i n = assert (i >= 0 && n >= 0 && i+n <= length v)
169 $ unsafeSlice v i n
170
171 -- | Yield the first @n@ elements without copying.
172 takeSlice :: IVector v a => Int -> v a -> v a
173 {-# INLINE takeSlice #-}
174 takeSlice n v = slice v 0 n
175
176 -- | Copy the first @n@ elements to a new vector.
177 take :: IVector v a => Int -> v a -> v a
178 {-# INLINE take #-}
179 take n = unstream . Stream.take n . stream
180
181 -- | Yield all but the first @n@ elements without copying.
182 dropSlice :: IVector v a => Int -> v a -> v a
183 {-# INLINE dropSlice #-}
184 dropSlice n v = slice v n (length v - n)
185
186 -- | Copy all but the first @n@ elements to a new vectors.
187 drop :: IVector v a => Int -> v a -> v a
188 {-# INLINE drop #-}
189 drop n = unstream . Stream.drop n . stream
190
191 -- Mapping/zipping
192 -- ---------------
193
194 -- | Map a function over a vector
195 map :: (IVector v a, IVector v b) => (a -> b) -> v a -> v b
196 {-# INLINE map #-}
197 map f = unstream . Stream.map f . stream
198
199 -- | Zip two vectors with the given function.
200 zipWith :: (IVector v a, IVector v b, IVector v c) => (a -> b -> c) -> v a -> v b -> v c
201 {-# INLINE zipWith #-}
202 zipWith f xs ys = unstream (Stream.zipWith f (stream xs) (stream ys))
203
204 -- Filtering
205 -- ---------
206
207 -- | Drop elements which do not satisfy the predicate
208 filter :: IVector v a => (a -> Bool) -> v a -> v a
209 {-# INLINE filter #-}
210 filter f = unstream . Stream.filter f . stream
211
212 -- | Copy the longest prefix of elements satisfying the predicate to a new
213 -- vector
214 takeWhile :: IVector v a => (a -> Bool) -> v a -> v a
215 {-# INLINE takeWhile #-}
216 takeWhile f = unstream . Stream.takeWhile f . stream
217
218 -- | Drop the longest prefix of elements that satisfy the predicate and copy
219 -- the rest to a new vector.
220 dropWhile :: IVector v a => (a -> Bool) -> v a -> v a
221 {-# INLINE dropWhile #-}
222 dropWhile f = unstream . Stream.dropWhile f . stream
223
224 -- Folding
225 -- -------
226
227 -- | Left fold
228 foldl :: IVector v b => (a -> b -> a) -> a -> v b -> a
229 {-# INLINE foldl #-}
230 foldl f z = Stream.foldl f z . stream
231
232 -- | Lefgt fold on non-empty vectors
233 foldl1 :: IVector v a => (a -> a -> a) -> v a -> a
234 {-# INLINE foldl1 #-}
235 foldl1 f = Stream.foldl1 f . stream
236
237 -- | Left fold with strict accumulator
238 foldl' :: IVector v b => (a -> b -> a) -> a -> v b -> a
239 {-# INLINE foldl' #-}
240 foldl' f z = Stream.foldl' f z . stream
241
242 -- | Left fold on non-empty vectors with strict accumulator
243 foldl1' :: IVector v a => (a -> a -> a) -> v a -> a
244 {-# INLINE foldl1' #-}
245 foldl1' f = Stream.foldl1' f . stream
246
247 -- | Right fold
248 foldr :: IVector v a => (a -> b -> b) -> b -> v a -> b
249 {-# INLINE foldr #-}
250 foldr f z = Stream.foldr f z . stream
251
252 -- | Right fold on non-empty vectors
253 foldr1 :: IVector v a => (a -> a -> a) -> v a -> a
254 {-# INLINE foldr1 #-}
255 foldr1 f = Stream.foldr1 f . stream
256
257 -- | Convert a vector to a list
258 toList :: IVector v a => v a -> [a]
259 {-# INLINE toList #-}
260 toList = Stream.toList . stream
261
262 -- | Convert a list to a vector
263 fromList :: IVector v a => [a] -> v a
264 {-# INLINE fromList #-}
265 fromList = unstream . Stream.fromList
266