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