Allow streams to produce entire vectors as well as individual elements
authorRoman Leshchinskiy <rl@cse.unsw.edu.au>
Sat, 7 Jan 2012 11:06:00 +0000 (11:06 +0000)
committerRoman Leshchinskiy <rl@cse.unsw.edu.au>
Sat, 7 Jan 2012 11:06:00 +0000 (11:06 +0000)
This is a signficant extension to the stream fusion mechanism. A Stream is now
parametrised with a vector type and offers two iteration modes: individual
elements and individual elements + vectors. This supports significantly more
efficient implementations of block operations. For instance, (++) will now use
memcpy where possible rather than iterating through the elements in a loop.

Comments are sorely lacking at the moment.

Data/Vector/Fusion/Stream.hs
Data/Vector/Fusion/Stream/Monadic.hs
Data/Vector/Generic.hs
Data/Vector/Generic/Base.hs
Data/Vector/Generic/Mutable.hs
Data/Vector/Generic/Mutable/Base.hs [new file with mode: 0644]
Data/Vector/Generic/New.hs
vector.cabal

index 4ae151c..2c079cd 100644 (file)
@@ -68,6 +68,7 @@ module Data.Vector.Fusion.Stream (
 
   -- * Conversions
   toList, fromList, fromListN, unsafeFromList, liftStream,
 
   -- * Conversions
   toList, fromList, fromListN, unsafeFromList, liftStream,
+  fromVector, reVector,
 
   -- * Monadic combinators
   mapM, mapM_, zipWithM, zipWithM_, filterM, foldM, fold1M, foldM', fold1M',
 
   -- * Monadic combinators
   mapM, mapM_, zipWithM, zipWithM_, filterM, foldM, fold1M, foldM', fold1M',
@@ -75,6 +76,7 @@ module Data.Vector.Fusion.Stream (
   eq, cmp
 ) where
 
   eq, cmp
 ) where
 
+import Data.Vector.Generic.Base ( Vector )
 import Data.Vector.Fusion.Stream.Size
 import Data.Vector.Fusion.Util
 import Data.Vector.Fusion.Stream.Monadic ( Step(..), SPEC(..) )
 import Data.Vector.Fusion.Stream.Size
 import Data.Vector.Fusion.Util
 import Data.Vector.Fusion.Stream.Monadic ( Step(..), SPEC(..) )
@@ -104,33 +106,35 @@ type Stream = M.Stream Id
 -- | Alternative name for monadic streams
 type MStream = M.Stream
 
 -- | Alternative name for monadic streams
 type MStream = M.Stream
 
-inplace :: (forall m. Monad m => M.Stream m a -> M.Stream m b)
-        -> Stream a -> Stream b
+inplace :: (forall m. Monad m => M.Stream m v a -> M.Stream m v b)
+        -> Stream v a -> Stream v b
 {-# INLINE_STREAM inplace #-}
 inplace f s = s `seq` f s
 
 {-# RULES
 
 "inplace/inplace [Vector]"
 {-# INLINE_STREAM inplace #-}
 inplace f s = s `seq` f s
 
 {-# RULES
 
 "inplace/inplace [Vector]"
-  forall (f :: forall m. Monad m => MStream m a -> MStream m a)
-         (g :: forall m. Monad m => MStream m a -> MStream m a)
+  forall (f :: forall m. Monad m => MStream m v a -> MStream m v a)
+         (g :: forall m. Monad m => MStream m v a -> MStream m v a)
          s.
   inplace f (inplace g s) = inplace (f . g) s
 
   #-}
 
 -- | Convert a pure stream to a monadic stream
          s.
   inplace f (inplace g s) = inplace (f . g) s
 
   #-}
 
 -- | Convert a pure stream to a monadic stream
-liftStream :: Monad m => Stream a -> M.Stream m a
+liftStream :: Monad m => Stream v a -> M.Stream m v a
 {-# INLINE_STREAM liftStream #-}
 {-# INLINE_STREAM liftStream #-}
-liftStream (M.Stream step s sz) = M.Stream (return . unId . step) s sz
+liftStream (M.Stream (M.Unf step s) (M.Unf vstep t) sz)
+    = M.Stream (M.Unf (return . unId . step) s)
+               (M.Unf (return . unId . vstep) t) sz
 
 -- | 'Size' hint of a 'Stream'
 
 -- | 'Size' hint of a 'Stream'
-size :: Stream a -> Size
+size :: Stream a -> Size
 {-# INLINE size #-}
 size = M.size
 
 -- | Attach a 'Size' hint to a 'Stream'
 {-# INLINE size #-}
 size = M.size
 
 -- | Attach a 'Size' hint to a 'Stream'
-sized :: Stream a -> Size -> Stream a
+sized :: Stream v a -> Size -> Stream v a
 {-# INLINE sized #-}
 sized = M.sized
 
 {-# INLINE sized #-}
 sized = M.sized
 
@@ -138,12 +142,12 @@ sized = M.sized
 -- ------
 
 -- | Length of a 'Stream'
 -- ------
 
 -- | Length of a 'Stream'
-length :: Stream a -> Int
+length :: Stream a -> Int
 {-# INLINE length #-}
 length = unId . M.length
 
 -- | Check if a 'Stream' is empty
 {-# INLINE length #-}
 length = unId . M.length
 
 -- | Check if a 'Stream' is empty
-null :: Stream a -> Bool
+null :: Stream a -> Bool
 {-# INLINE null #-}
 null = unId . M.null
 
 {-# INLINE null #-}
 null = unId . M.null
 
@@ -151,38 +155,38 @@ null = unId . M.null
 -- ------------
 
 -- | Empty 'Stream'
 -- ------------
 
 -- | Empty 'Stream'
-empty :: Stream a
+empty :: Stream a
 {-# INLINE empty #-}
 empty = M.empty
 
 -- | Singleton 'Stream'
 {-# INLINE empty #-}
 empty = M.empty
 
 -- | Singleton 'Stream'
-singleton :: a -> Stream a
+singleton :: a -> Stream a
 {-# INLINE singleton #-}
 singleton = M.singleton
 
 -- | Replicate a value to a given length
 {-# INLINE singleton #-}
 singleton = M.singleton
 
 -- | Replicate a value to a given length
-replicate :: Int -> a -> Stream a
+replicate :: Int -> a -> Stream a
 {-# INLINE replicate #-}
 replicate = M.replicate
 
 -- | Generate a stream from its indices
 {-# INLINE replicate #-}
 replicate = M.replicate
 
 -- | Generate a stream from its indices
-generate :: Int -> (Int -> a) -> Stream a
+generate :: Int -> (Int -> a) -> Stream a
 {-# INLINE generate #-}
 generate = M.generate
 
 -- | Prepend an element
 {-# INLINE generate #-}
 generate = M.generate
 
 -- | Prepend an element
-cons :: a -> Stream a -> Stream a
+cons :: a -> Stream v a -> Stream v a
 {-# INLINE cons #-}
 cons = M.cons
 
 -- | Append an element
 {-# INLINE cons #-}
 cons = M.cons
 
 -- | Append an element
-snoc :: Stream a -> a -> Stream a
+snoc :: Stream v a -> a -> Stream v a
 {-# INLINE snoc #-}
 snoc = M.snoc
 
 infixr 5 ++
 -- | Concatenate two 'Stream's
 {-# INLINE snoc #-}
 snoc = M.snoc
 
 infixr 5 ++
 -- | Concatenate two 'Stream's
-(++) :: Stream a -> Stream a -> Stream a
+(++) :: Stream v a -> Stream v a -> Stream v a
 {-# INLINE (++) #-}
 (++) = (M.++)
 
 {-# INLINE (++) #-}
 (++) = (M.++)
 
@@ -190,24 +194,24 @@ infixr 5 ++
 -- ------------------
 
 -- | First element of the 'Stream' or error if empty
 -- ------------------
 
 -- | First element of the 'Stream' or error if empty
-head :: Stream a -> a
+head :: Stream a -> a
 {-# INLINE head #-}
 head = unId . M.head
 
 -- | Last element of the 'Stream' or error if empty
 {-# INLINE head #-}
 head = unId . M.head
 
 -- | Last element of the 'Stream' or error if empty
-last :: Stream a -> a
+last :: Stream a -> a
 {-# INLINE last #-}
 last = unId . M.last
 
 infixl 9 !!
 -- | Element at the given position
 {-# INLINE last #-}
 last = unId . M.last
 
 infixl 9 !!
 -- | Element at the given position
-(!!) :: Stream a -> Int -> a
+(!!) :: Stream a -> Int -> a
 {-# INLINE (!!) #-}
 s !! i = unId (s M.!! i)
 
 infixl 9 !?
 -- | Element at the given position or 'Nothing' if out of bounds
 {-# INLINE (!!) #-}
 s !! i = unId (s M.!! i)
 
 infixl 9 !?
 -- | Element at the given position or 'Nothing' if out of bounds
-(!?) :: Stream a -> Int -> Maybe a
+(!?) :: Stream a -> Int -> Maybe a
 {-# INLINE (!?) #-}
 s !? i = unId (s M.!? i)
 
 {-# INLINE (!?) #-}
 s !? i = unId (s M.!? i)
 
@@ -217,28 +221,28 @@ s !? i = unId (s M.!? i)
 -- | Extract a substream of the given length starting at the given position.
 slice :: Int   -- ^ starting index
       -> Int   -- ^ length
 -- | Extract a substream of the given length starting at the given position.
 slice :: Int   -- ^ starting index
       -> Int   -- ^ length
-      -> Stream a
-      -> Stream a
+      -> Stream a
+      -> Stream a
 {-# INLINE slice #-}
 slice = M.slice
 
 -- | All but the last element
 {-# INLINE slice #-}
 slice = M.slice
 
 -- | All but the last element
-init :: Stream a -> Stream a
+init :: Stream v a -> Stream v a
 {-# INLINE init #-}
 init = M.init
 
 -- | All but the first element
 {-# INLINE init #-}
 init = M.init
 
 -- | All but the first element
-tail :: Stream a -> Stream a
+tail :: Stream v a -> Stream v a
 {-# INLINE tail #-}
 tail = M.tail
 
 -- | The first @n@ elements
 {-# INLINE tail #-}
 tail = M.tail
 
 -- | The first @n@ elements
-take :: Int -> Stream a -> Stream a
+take :: Int -> Stream v a -> Stream v a
 {-# INLINE take #-}
 take = M.take
 
 -- | All but the first @n@ elements
 {-# INLINE take #-}
 take = M.take
 
 -- | All but the first @n@ elements
-drop :: Int -> Stream a -> Stream a
+drop :: Int -> Stream v a -> Stream v a
 {-# INLINE drop #-}
 drop = M.drop
 
 {-# INLINE drop #-}
 drop = M.drop
 
@@ -246,15 +250,15 @@ drop = M.drop
 -- ---------------
 
 -- | Map a function over a 'Stream'
 -- ---------------
 
 -- | Map a function over a 'Stream'
-map :: (a -> b) -> Stream a -> Stream b
+map :: (a -> b) -> Stream v a -> Stream v b
 {-# INLINE map #-}
 map = M.map
 
 {-# INLINE map #-}
 map = M.map
 
-unbox :: Stream (Box a) -> Stream a
+unbox :: Stream v (Box a) -> Stream v a
 {-# INLINE unbox #-}
 unbox = M.unbox
 
 {-# INLINE unbox #-}
 unbox = M.unbox
 
-concatMap :: (a -> Stream b) -> Stream a -> Stream b
+concatMap :: (a -> Stream v b) -> Stream v a -> Stream v b
 {-# INLINE concatMap #-}
 concatMap = M.concatMap
 
 {-# INLINE concatMap #-}
 concatMap = M.concatMap
 
@@ -262,64 +266,64 @@ concatMap = M.concatMap
 -- -------
 
 -- | Pair each element in a 'Stream' with its index
 -- -------
 
 -- | Pair each element in a 'Stream' with its index
-indexed :: Stream a -> Stream (Int,a)
+indexed :: Stream v a -> Stream v (Int,a)
 {-# INLINE indexed #-}
 indexed = M.indexed
 
 -- | Pair each element in a 'Stream' with its index, starting from the right
 -- and counting down
 {-# INLINE indexed #-}
 indexed = M.indexed
 
 -- | Pair each element in a 'Stream' with its index, starting from the right
 -- and counting down
-indexedR :: Int -> Stream a -> Stream (Int,a)
+indexedR :: Int -> Stream v a -> Stream v (Int,a)
 {-# INLINE_STREAM indexedR #-}
 indexedR = M.indexedR
 
 -- | Zip two 'Stream's with the given function
 {-# INLINE_STREAM indexedR #-}
 indexedR = M.indexedR
 
 -- | Zip two 'Stream's with the given function
-zipWith :: (a -> b -> c) -> Stream a -> Stream b -> Stream c
+zipWith :: (a -> b -> c) -> Stream v a -> Stream v b -> Stream v c
 {-# INLINE zipWith #-}
 zipWith = M.zipWith
 
 -- | Zip three 'Stream's with the given function
 {-# INLINE zipWith #-}
 zipWith = M.zipWith
 
 -- | Zip three 'Stream's with the given function
-zipWith3 :: (a -> b -> c -> d) -> Stream a -> Stream b -> Stream c -> Stream d
+zipWith3 :: (a -> b -> c -> d) -> Stream v a -> Stream v b -> Stream v c -> Stream v d
 {-# INLINE zipWith3 #-}
 zipWith3 = M.zipWith3
 
 zipWith4 :: (a -> b -> c -> d -> e)
 {-# INLINE zipWith3 #-}
 zipWith3 = M.zipWith3
 
 zipWith4 :: (a -> b -> c -> d -> e)
-                    -> Stream a -> Stream b -> Stream c -> Stream d
-                    -> Stream e
+                    -> Stream v a -> Stream v b -> Stream v c -> Stream v d
+                    -> Stream e
 {-# INLINE zipWith4 #-}
 zipWith4 = M.zipWith4
 
 zipWith5 :: (a -> b -> c -> d -> e -> f)
 {-# INLINE zipWith4 #-}
 zipWith4 = M.zipWith4
 
 zipWith5 :: (a -> b -> c -> d -> e -> f)
-                    -> Stream a -> Stream b -> Stream c -> Stream d
-                    -> Stream e -> Stream f
+                    -> Stream v a -> Stream v b -> Stream v c -> Stream v d
+                    -> Stream v e -> Stream v f
 {-# INLINE zipWith5 #-}
 zipWith5 = M.zipWith5
 
 zipWith6 :: (a -> b -> c -> d -> e -> f -> g)
 {-# INLINE zipWith5 #-}
 zipWith5 = M.zipWith5
 
 zipWith6 :: (a -> b -> c -> d -> e -> f -> g)
-                    -> Stream a -> Stream b -> Stream c -> Stream d
-                    -> Stream e -> Stream f -> Stream g
+                    -> Stream v a -> Stream v b -> Stream v c -> Stream v d
+                    -> Stream v e -> Stream v f -> Stream v g
 {-# INLINE zipWith6 #-}
 zipWith6 = M.zipWith6
 
 {-# INLINE zipWith6 #-}
 zipWith6 = M.zipWith6
 
-zip :: Stream a -> Stream b -> Stream (a,b)
+zip :: Stream v a -> Stream v b -> Stream v (a,b)
 {-# INLINE zip #-}
 zip = M.zip
 
 {-# INLINE zip #-}
 zip = M.zip
 
-zip3 :: Stream a -> Stream b -> Stream c -> Stream (a,b,c)
+zip3 :: Stream v a -> Stream v b -> Stream v c -> Stream v (a,b,c)
 {-# INLINE zip3 #-}
 zip3 = M.zip3
 
 {-# INLINE zip3 #-}
 zip3 = M.zip3
 
-zip4 :: Stream a -> Stream b -> Stream c -> Stream d
-                -> Stream (a,b,c,d)
+zip4 :: Stream v a -> Stream v b -> Stream v c -> Stream v d
+                -> Stream (a,b,c,d)
 {-# INLINE zip4 #-}
 zip4 = M.zip4
 
 {-# INLINE zip4 #-}
 zip4 = M.zip4
 
-zip5 :: Stream a -> Stream b -> Stream c -> Stream d
-                -> Stream e -> Stream (a,b,c,d,e)
+zip5 :: Stream v a -> Stream v b -> Stream v c -> Stream v d
+                -> Stream v e -> Stream v (a,b,c,d,e)
 {-# INLINE zip5 #-}
 zip5 = M.zip5
 
 {-# INLINE zip5 #-}
 zip5 = M.zip5
 
-zip6 :: Stream a -> Stream b -> Stream c -> Stream d
-                -> Stream e -> Stream f -> Stream (a,b,c,d,e,f)
+zip6 :: Stream v a -> Stream v b -> Stream v c -> Stream v d
+                -> Stream v e -> Stream v f -> Stream v (a,b,c,d,e,f)
 {-# INLINE zip6 #-}
 zip6 = M.zip6
 
 {-# INLINE zip6 #-}
 zip6 = M.zip6
 
@@ -327,17 +331,17 @@ zip6 = M.zip6
 -- ---------
 
 -- | Drop elements which do not satisfy the predicate
 -- ---------
 
 -- | Drop elements which do not satisfy the predicate
-filter :: (a -> Bool) -> Stream a -> Stream a
+filter :: (a -> Bool) -> Stream v a -> Stream v a
 {-# INLINE filter #-}
 filter = M.filter
 
 -- | Longest prefix of elements that satisfy the predicate
 {-# INLINE filter #-}
 filter = M.filter
 
 -- | Longest prefix of elements that satisfy the predicate
-takeWhile :: (a -> Bool) -> Stream a -> Stream a
+takeWhile :: (a -> Bool) -> Stream v a -> Stream v a
 {-# INLINE takeWhile #-}
 takeWhile = M.takeWhile
 
 -- | Drop the longest prefix of elements that satisfy the predicate
 {-# INLINE takeWhile #-}
 takeWhile = M.takeWhile
 
 -- | Drop the longest prefix of elements that satisfy the predicate
-dropWhile :: (a -> Bool) -> Stream a -> Stream a
+dropWhile :: (a -> Bool) -> Stream v a -> Stream v a
 {-# INLINE dropWhile #-}
 dropWhile = M.dropWhile
 
 {-# INLINE dropWhile #-}
 dropWhile = M.dropWhile
 
@@ -346,25 +350,25 @@ dropWhile = M.dropWhile
 
 infix 4 `elem`
 -- | Check whether the 'Stream' contains an element
 
 infix 4 `elem`
 -- | Check whether the 'Stream' contains an element
-elem :: Eq a => a -> Stream a -> Bool
+elem :: Eq a => a -> Stream a -> Bool
 {-# INLINE elem #-}
 elem x = unId . M.elem x
 
 infix 4 `notElem`
 -- | Inverse of `elem`
 {-# INLINE elem #-}
 elem x = unId . M.elem x
 
 infix 4 `notElem`
 -- | Inverse of `elem`
-notElem :: Eq a => a -> Stream a -> Bool
+notElem :: Eq a => a -> Stream a -> Bool
 {-# INLINE notElem #-}
 notElem x = unId . M.notElem x
 
 -- | Yield 'Just' the first element matching the predicate or 'Nothing' if no
 -- such element exists.
 {-# INLINE notElem #-}
 notElem x = unId . M.notElem x
 
 -- | Yield 'Just' the first element matching the predicate or 'Nothing' if no
 -- such element exists.
-find :: (a -> Bool) -> Stream a -> Maybe a
+find :: (a -> Bool) -> Stream a -> Maybe a
 {-# INLINE find #-}
 find f = unId . M.find f
 
 -- | Yield 'Just' the index of the first element matching the predicate or
 -- 'Nothing' if no such element exists.
 {-# INLINE find #-}
 find f = unId . M.find f
 
 -- | Yield 'Just' the index of the first element matching the predicate or
 -- 'Nothing' if no such element exists.
-findIndex :: (a -> Bool) -> Stream a -> Maybe Int
+findIndex :: (a -> Bool) -> Stream a -> Maybe Int
 {-# INLINE findIndex #-}
 findIndex f = unId . M.findIndex f
 
 {-# INLINE findIndex #-}
 findIndex f = unId . M.findIndex f
 
@@ -372,43 +376,43 @@ findIndex f = unId . M.findIndex f
 -- -------
 
 -- | Left fold
 -- -------
 
 -- | Left fold
-foldl :: (a -> b -> a) -> a -> Stream b -> a
+foldl :: (a -> b -> a) -> a -> Stream b -> a
 {-# INLINE foldl #-}
 foldl f z = unId . M.foldl f z
 
 -- | Left fold on non-empty 'Stream's
 {-# INLINE foldl #-}
 foldl f z = unId . M.foldl f z
 
 -- | Left fold on non-empty 'Stream's
-foldl1 :: (a -> a -> a) -> Stream a -> a
+foldl1 :: (a -> a -> a) -> Stream a -> a
 {-# INLINE foldl1 #-}
 foldl1 f = unId . M.foldl1 f
 
 -- | Left fold with strict accumulator
 {-# INLINE foldl1 #-}
 foldl1 f = unId . M.foldl1 f
 
 -- | Left fold with strict accumulator
-foldl' :: (a -> b -> a) -> a -> Stream b -> a
+foldl' :: (a -> b -> a) -> a -> Stream b -> a
 {-# INLINE foldl' #-}
 foldl' f z = unId . M.foldl' f z
 
 -- | Left fold on non-empty 'Stream's with strict accumulator
 {-# INLINE foldl' #-}
 foldl' f z = unId . M.foldl' f z
 
 -- | Left fold on non-empty 'Stream's with strict accumulator
-foldl1' :: (a -> a -> a) -> Stream a -> a
+foldl1' :: (a -> a -> a) -> Stream a -> a
 {-# INLINE foldl1' #-}
 foldl1' f = unId . M.foldl1' f
 
 -- | Right fold
 {-# INLINE foldl1' #-}
 foldl1' f = unId . M.foldl1' f
 
 -- | Right fold
-foldr :: (a -> b -> b) -> b -> Stream a -> b
+foldr :: (a -> b -> b) -> b -> Stream a -> b
 {-# INLINE foldr #-}
 foldr f z = unId . M.foldr f z
 
 -- | Right fold on non-empty 'Stream's
 {-# INLINE foldr #-}
 foldr f z = unId . M.foldr f z
 
 -- | Right fold on non-empty 'Stream's
-foldr1 :: (a -> a -> a) -> Stream a -> a
+foldr1 :: (a -> a -> a) -> Stream a -> a
 {-# INLINE foldr1 #-}
 foldr1 f = unId . M.foldr1 f
 
 -- Specialised folds
 -- -----------------
 
 {-# INLINE foldr1 #-}
 foldr1 f = unId . M.foldr1 f
 
 -- Specialised folds
 -- -----------------
 
-and :: Stream Bool -> Bool
+and :: Stream Bool -> Bool
 {-# INLINE and #-}
 and = unId . M.and
 
 {-# INLINE and #-}
 and = unId . M.and
 
-or :: Stream Bool -> Bool
+or :: Stream Bool -> Bool
 {-# INLINE or #-}
 or = unId . M.or
 
 {-# INLINE or #-}
 or = unId . M.or
 
@@ -416,17 +420,17 @@ or = unId . M.or
 -- ---------
 
 -- | Unfold
 -- ---------
 
 -- | Unfold
-unfoldr :: (s -> Maybe (a, s)) -> s -> Stream a
+unfoldr :: (s -> Maybe (a, s)) -> s -> Stream a
 {-# INLINE unfoldr #-}
 unfoldr = M.unfoldr
 
 -- | Unfold at most @n@ elements
 {-# INLINE unfoldr #-}
 unfoldr = M.unfoldr
 
 -- | Unfold at most @n@ elements
-unfoldrN :: Int -> (s -> Maybe (a, s)) -> s -> Stream a
+unfoldrN :: Int -> (s -> Maybe (a, s)) -> s -> Stream a
 {-# INLINE unfoldrN #-}
 unfoldrN = M.unfoldrN
 
 -- | Apply function n-1 times to value. Zeroth element is original value.
 {-# INLINE unfoldrN #-}
 unfoldrN = M.unfoldrN
 
 -- | Apply function n-1 times to value. Zeroth element is original value.
-iterateN :: Int -> (a -> a) -> a -> Stream a
+iterateN :: Int -> (a -> a) -> a -> Stream a
 {-# INLINE iterateN #-}
 iterateN = M.iterateN
 
 {-# INLINE iterateN #-}
 iterateN = M.iterateN
 
@@ -434,42 +438,42 @@ iterateN = M.iterateN
 -- -----
 
 -- | Prefix scan
 -- -----
 
 -- | Prefix scan
-prescanl :: (a -> b -> a) -> a -> Stream b -> Stream a
+prescanl :: (a -> b -> a) -> a -> Stream v b -> Stream v a
 {-# INLINE prescanl #-}
 prescanl = M.prescanl
 
 -- | Prefix scan with strict accumulator
 {-# INLINE prescanl #-}
 prescanl = M.prescanl
 
 -- | Prefix scan with strict accumulator
-prescanl' :: (a -> b -> a) -> a -> Stream b -> Stream a
+prescanl' :: (a -> b -> a) -> a -> Stream v b -> Stream v a
 {-# INLINE prescanl' #-}
 prescanl' = M.prescanl'
 
 -- | Suffix scan
 {-# INLINE prescanl' #-}
 prescanl' = M.prescanl'
 
 -- | Suffix scan
-postscanl :: (a -> b -> a) -> a -> Stream b -> Stream a
+postscanl :: (a -> b -> a) -> a -> Stream v b -> Stream v a
 {-# INLINE postscanl #-}
 postscanl = M.postscanl
 
 -- | Suffix scan with strict accumulator
 {-# INLINE postscanl #-}
 postscanl = M.postscanl
 
 -- | Suffix scan with strict accumulator
-postscanl' :: (a -> b -> a) -> a -> Stream b -> Stream a
+postscanl' :: (a -> b -> a) -> a -> Stream v b -> Stream v a
 {-# INLINE postscanl' #-}
 postscanl' = M.postscanl'
 
 -- | Haskell-style scan
 {-# INLINE postscanl' #-}
 postscanl' = M.postscanl'
 
 -- | Haskell-style scan
-scanl :: (a -> b -> a) -> a -> Stream b -> Stream a
+scanl :: (a -> b -> a) -> a -> Stream v b -> Stream v a
 {-# INLINE scanl #-}
 scanl = M.scanl
 
 -- | Haskell-style scan with strict accumulator
 {-# INLINE scanl #-}
 scanl = M.scanl
 
 -- | Haskell-style scan with strict accumulator
-scanl' :: (a -> b -> a) -> a -> Stream b -> Stream a
+scanl' :: (a -> b -> a) -> a -> Stream v b -> Stream v a
 {-# INLINE scanl' #-}
 scanl' = M.scanl'
 
 -- | Scan over a non-empty 'Stream'
 {-# INLINE scanl' #-}
 scanl' = M.scanl'
 
 -- | Scan over a non-empty 'Stream'
-scanl1 :: (a -> a -> a) -> Stream a -> Stream a
+scanl1 :: (a -> a -> a) -> Stream v a -> Stream v a
 {-# INLINE scanl1 #-}
 scanl1 = M.scanl1
 
 -- | Scan over a non-empty 'Stream' with a strict accumulator
 {-# INLINE scanl1 #-}
 scanl1 = M.scanl1
 
 -- | Scan over a non-empty 'Stream' with a strict accumulator
-scanl1' :: (a -> a -> a) -> Stream a -> Stream a
+scanl1' :: (a -> a -> a) -> Stream v a -> Stream v a
 {-# INLINE scanl1' #-}
 scanl1' = M.scanl1'
 
 {-# INLINE scanl1' #-}
 scanl1' = M.scanl1'
 
@@ -477,17 +481,15 @@ scanl1' = M.scanl1'
 -- Comparisons
 -- -----------
 
 -- Comparisons
 -- -----------
 
--- FIXME: Move these to Monadic
-
 -- | Check if two 'Stream's are equal
 -- | Check if two 'Stream's are equal
-eq :: Eq a => Stream a -> Stream a -> Bool
+eq :: Eq a => Stream v a -> Stream v a -> Bool
 {-# INLINE_STREAM eq #-}
 {-# INLINE_STREAM eq #-}
-eq (M.Stream step1 s1 _) (M.Stream step2 s2 _) = eq_loop0 SPEC s1 s2
+eq (M.Stream (M.Unf step1 s1) _ _) (M.Stream (M.Unf step2 s2) _ _) = eq_loop0 SPEC s1 s2
   where
     eq_loop0 !sPEC s1 s2 = case unId (step1 s1) of
                              Yield x s1' -> eq_loop1 SPEC x s1' s2
                              Skip    s1' -> eq_loop0 SPEC   s1' s2
   where
     eq_loop0 !sPEC s1 s2 = case unId (step1 s1) of
                              Yield x s1' -> eq_loop1 SPEC x s1' s2
                              Skip    s1' -> eq_loop0 SPEC   s1' s2
-                             Done        -> null (M.Stream step2 s2 Unknown)
+                             Done        -> null (M.simple step2 s2 Unknown)
 
     eq_loop1 !sPEC x s1 s2 = case unId (step2 s2) of
                                Yield y s2' -> x == y && eq_loop0 SPEC   s1 s2'
 
     eq_loop1 !sPEC x s1 s2 = case unId (step2 s2) of
                                Yield y s2' -> x == y && eq_loop0 SPEC   s1 s2'
@@ -495,14 +497,14 @@ eq (M.Stream step1 s1 _) (M.Stream step2 s2 _) = eq_loop0 SPEC s1 s2
                                Done        -> False
 
 -- | Lexicographically compare two 'Stream's
                                Done        -> False
 
 -- | Lexicographically compare two 'Stream's
-cmp :: Ord a => Stream a -> Stream a -> Ordering
+cmp :: Ord a => Stream v a -> Stream v a -> Ordering
 {-# INLINE_STREAM cmp #-}
 {-# INLINE_STREAM cmp #-}
-cmp (M.Stream step1 s1 _) (M.Stream step2 s2 _) = cmp_loop0 SPEC s1 s2
+cmp (M.Stream (M.Unf step1 s1) _ _) (M.Stream (M.Unf step2 s2) _ _) = cmp_loop0 SPEC s1 s2
   where
     cmp_loop0 !sPEC s1 s2 = case unId (step1 s1) of
                               Yield x s1' -> cmp_loop1 SPEC x s1' s2
                               Skip    s1' -> cmp_loop0 SPEC   s1' s2
   where
     cmp_loop0 !sPEC s1 s2 = case unId (step1 s1) of
                               Yield x s1' -> cmp_loop1 SPEC x s1' s2
                               Skip    s1' -> cmp_loop0 SPEC   s1' s2
-                              Done        -> if null (M.Stream step2 s2 Unknown)
+                              Done        -> if null (M.simple step2 s2 Unknown)
                                                then EQ else LT
 
     cmp_loop1 !sPEC x s1 s2 = case unId (step2 s2) of
                                                then EQ else LT
 
     cmp_loop1 !sPEC x s1 s2 = case unId (step2 s2) of
@@ -512,11 +514,11 @@ cmp (M.Stream step1 s1 _) (M.Stream step2 s2 _) = cmp_loop0 SPEC s1 s2
                                 Skip    s2' -> cmp_loop1 SPEC x s1 s2'
                                 Done        -> GT
 
                                 Skip    s2' -> cmp_loop1 SPEC x s1 s2'
                                 Done        -> GT
 
-instance Eq a => Eq (M.Stream Id a) where
+instance Eq a => Eq (M.Stream Id a) where
   {-# INLINE (==) #-}
   (==) = eq
 
   {-# INLINE (==) #-}
   (==) = eq
 
-instance Ord a => Ord (M.Stream Id a) where
+instance Ord a => Ord (M.Stream Id a) where
   {-# INLINE compare #-}
   compare = cmp
 
   {-# INLINE compare #-}
   compare = cmp
 
@@ -525,45 +527,45 @@ instance Ord a => Ord (M.Stream Id a) where
 
 -- | Apply a monadic action to each element of the stream, producing a monadic
 -- stream of results
 
 -- | Apply a monadic action to each element of the stream, producing a monadic
 -- stream of results
-mapM :: Monad m => (a -> m b) -> Stream a -> M.Stream m b
+mapM :: Monad m => (a -> m b) -> Stream v a -> M.Stream m v b
 {-# INLINE mapM #-}
 mapM f = M.mapM f . liftStream
 
 -- | Apply a monadic action to each element of the stream
 {-# INLINE mapM #-}
 mapM f = M.mapM f . liftStream
 
 -- | Apply a monadic action to each element of the stream
-mapM_ :: Monad m => (a -> m b) -> Stream a -> m ()
+mapM_ :: Monad m => (a -> m b) -> Stream a -> m ()
 {-# INLINE mapM_ #-}
 mapM_ f = M.mapM_ f . liftStream
 
 {-# INLINE mapM_ #-}
 mapM_ f = M.mapM_ f . liftStream
 
-zipWithM :: Monad m => (a -> b -> m c) -> Stream a -> Stream b -> M.Stream m c
+zipWithM :: Monad m => (a -> b -> m c) -> Stream v a -> Stream v b -> M.Stream m v c
 {-# INLINE zipWithM #-}
 zipWithM f as bs = M.zipWithM f (liftStream as) (liftStream bs)
 
 {-# INLINE zipWithM #-}
 zipWithM f as bs = M.zipWithM f (liftStream as) (liftStream bs)
 
-zipWithM_ :: Monad m => (a -> b -> m c) -> Stream a -> Stream b -> m ()
+zipWithM_ :: Monad m => (a -> b -> m c) -> Stream v a -> Stream v b -> m ()
 {-# INLINE zipWithM_ #-}
 zipWithM_ f as bs = M.zipWithM_ f (liftStream as) (liftStream bs)
 
 -- | Yield a monadic stream of elements that satisfy the monadic predicate
 {-# INLINE zipWithM_ #-}
 zipWithM_ f as bs = M.zipWithM_ f (liftStream as) (liftStream bs)
 
 -- | Yield a monadic stream of elements that satisfy the monadic predicate
-filterM :: Monad m => (a -> m Bool) -> Stream a -> M.Stream m a
+filterM :: Monad m => (a -> m Bool) -> Stream v a -> M.Stream m v a
 {-# INLINE filterM #-}
 filterM f = M.filterM f . liftStream
 
 -- | Monadic fold
 {-# INLINE filterM #-}
 filterM f = M.filterM f . liftStream
 
 -- | Monadic fold
-foldM :: Monad m => (a -> b -> m a) -> a -> Stream b -> m a
+foldM :: Monad m => (a -> b -> m a) -> a -> Stream b -> m a
 {-# INLINE foldM #-}
 foldM m z = M.foldM m z . liftStream
 
 -- | Monadic fold over non-empty stream
 {-# INLINE foldM #-}
 foldM m z = M.foldM m z . liftStream
 
 -- | Monadic fold over non-empty stream
-fold1M :: Monad m => (a -> a -> m a) -> Stream a -> m a
+fold1M :: Monad m => (a -> a -> m a) -> Stream a -> m a
 {-# INLINE fold1M #-}
 fold1M m = M.fold1M m . liftStream
 
 -- | Monadic fold with strict accumulator
 {-# INLINE fold1M #-}
 fold1M m = M.fold1M m . liftStream
 
 -- | Monadic fold with strict accumulator
-foldM' :: Monad m => (a -> b -> m a) -> a -> Stream b -> m a
+foldM' :: Monad m => (a -> b -> m a) -> a -> Stream b -> m a
 {-# INLINE foldM' #-}
 foldM' m z = M.foldM' m z . liftStream
 
 -- | Monad fold over non-empty stream with strict accumulator
 {-# INLINE foldM' #-}
 foldM' m z = M.foldM' m z . liftStream
 
 -- | Monad fold over non-empty stream with strict accumulator
-fold1M' :: Monad m => (a -> a -> m a) -> Stream a -> m a
+fold1M' :: Monad m => (a -> a -> m a) -> Stream a -> m a
 {-# INLINE fold1M' #-}
 fold1M' m = M.fold1M' m . liftStream
 
 {-# INLINE fold1M' #-}
 fold1M' m = M.fold1M' m . liftStream
 
@@ -572,7 +574,7 @@ fold1M' m = M.fold1M' m . liftStream
 
 -- | Yield a 'Stream' of the given length containing the values @x@, @x+y@,
 -- @x+y+y@ etc.
 
 -- | Yield a 'Stream' of the given length containing the values @x@, @x+y@,
 -- @x+y+y@ etc.
-enumFromStepN :: Num a => a -> a -> Int -> Stream a
+enumFromStepN :: Num a => a -> a -> Int -> Stream a
 {-# INLINE enumFromStepN #-}
 enumFromStepN = M.enumFromStepN
 
 {-# INLINE enumFromStepN #-}
 enumFromStepN = M.enumFromStepN
 
@@ -580,7 +582,7 @@ enumFromStepN = M.enumFromStepN
 --
 -- /WARNING:/ This operations can be very inefficient. If at all possible, use
 -- 'enumFromStepN' instead.
 --
 -- /WARNING:/ This operations can be very inefficient. If at all possible, use
 -- 'enumFromStepN' instead.
-enumFromTo :: Enum a => a -> a -> Stream a
+enumFromTo :: Enum a => a -> a -> Stream a
 {-# INLINE enumFromTo #-}
 enumFromTo = M.enumFromTo
 
 {-# INLINE enumFromTo #-}
 enumFromTo = M.enumFromTo
 
@@ -588,7 +590,7 @@ enumFromTo = M.enumFromTo
 --
 -- /WARNING:/ This operations is very inefficient. If at all possible, use
 -- 'enumFromStepN' instead.
 --
 -- /WARNING:/ This operations is very inefficient. If at all possible, use
 -- 'enumFromStepN' instead.
-enumFromThenTo :: Enum a => a -> a -> a -> Stream a
+enumFromThenTo :: Enum a => a -> a -> a -> Stream a
 {-# INLINE enumFromThenTo #-}
 enumFromThenTo = M.enumFromThenTo
 
 {-# INLINE enumFromThenTo #-}
 enumFromThenTo = M.enumFromThenTo
 
@@ -596,15 +598,15 @@ enumFromThenTo = M.enumFromThenTo
 -- -----------
 
 -- | Convert a 'Stream' to a list
 -- -----------
 
 -- | Convert a 'Stream' to a list
-toList :: Stream a -> [a]
+toList :: Stream a -> [a]
 {-# INLINE toList #-}
 -- toList s = unId (M.toList s)
 toList s = build (\c n -> toListFB c n s)
 
 -- This supports foldr/build list fusion that GHC implements
 {-# INLINE toList #-}
 -- toList s = unId (M.toList s)
 toList s = build (\c n -> toListFB c n s)
 
 -- This supports foldr/build list fusion that GHC implements
-toListFB :: (a -> b -> b) -> b -> Stream a -> b
+toListFB :: (a -> b -> b) -> b -> Stream a -> b
 {-# INLINE [0] toListFB #-}
 {-# INLINE [0] toListFB #-}
-toListFB c n (M.Stream step s _) = go s
+toListFB c n (M.Stream (M.Unf step s) _ _) = go s
   where
     go s = case unId (step s) of
              Yield x s' -> x `c` go s'
   where
     go s = case unId (step s) of
              Yield x s' -> x `c` go s'
@@ -612,23 +614,31 @@ toListFB c n (M.Stream step s _) = go s
              Done       -> n
 
 -- | Create a 'Stream' from a list
              Done       -> n
 
 -- | Create a 'Stream' from a list
-fromList :: [a] -> Stream a
+fromList :: [a] -> Stream a
 {-# INLINE fromList #-}
 fromList = M.fromList
 
 -- | Create a 'Stream' from the first @n@ elements of a list
 --
 -- > fromListN n xs = fromList (take n xs)
 {-# INLINE fromList #-}
 fromList = M.fromList
 
 -- | Create a 'Stream' from the first @n@ elements of a list
 --
 -- > fromListN n xs = fromList (take n xs)
-fromListN :: Int -> [a] -> Stream a
+fromListN :: Int -> [a] -> Stream a
 {-# INLINE fromListN #-}
 fromListN = M.fromListN
 
 {-# INLINE fromListN #-}
 fromListN = M.fromListN
 
-unsafeFromList :: Size -> [a] -> Stream a
+unsafeFromList :: Size -> [a] -> Stream a
 {-# INLINE unsafeFromList #-}
 unsafeFromList = M.unsafeFromList
 
 {-# INLINE unsafeFromList #-}
 unsafeFromList = M.unsafeFromList
 
+fromVector :: Vector v a => v a -> Stream v a
+{-# INLINE fromVector #-}
+fromVector = M.fromVector
+
+reVector :: Stream u a -> Stream v a
+{-# INLINE reVector #-}
+reVector = M.reVector
+
 -- | Create a 'Stream' of values from a 'Stream' of streamable things
 -- | Create a 'Stream' of values from a 'Stream' of streamable things
-flatten :: (a -> s) -> (s -> Step s b) -> Size -> Stream a -> Stream b
+flatten :: (a -> s) -> (s -> Step s b) -> Size -> Stream v a -> Stream v b
 {-# INLINE_STREAM flatten #-}
 flatten mk istep sz = M.flatten (return . mk) (return . istep) sz . liftStream
 
 {-# INLINE_STREAM flatten #-}
 flatten mk istep sz = M.flatten (return . mk) (return . istep) sz . liftStream
 
index 51fec75..135360e 100644 (file)
@@ -1,4 +1,4 @@
-{-# LANGUAGE ExistentialQuantification, Rank2Types, BangPatterns #-}
+{-# LANGUAGE ExistentialQuantification, MultiParamTypeClasses, FlexibleInstances, Rank2Types, BangPatterns, KindSignatures, GADTs, ScopedTypeVariables #-}
 
 -- |
 -- Module      : Data.Vector.Fusion.Stream.Monadic
 
 -- |
 -- Module      : Data.Vector.Fusion.Stream.Monadic
@@ -13,7 +13,9 @@
 --
 
 module Data.Vector.Fusion.Stream.Monadic (
 --
 
 module Data.Vector.Fusion.Stream.Monadic (
-  Stream(..), Step(..), SPEC(..),
+  Stream(..), Unf(..), Step(..), SPEC(..),
+
+  simple,
 
   -- * Size hints
   size, sized,
 
   -- * Size hints
   size, sized,
@@ -50,6 +52,8 @@ module Data.Vector.Fusion.Stream.Monadic (
   foldl', foldlM', foldl1', foldl1M', foldM', fold1M',
   foldr, foldrM, foldr1, foldr1M,
 
   foldl', foldlM', foldl1', foldl1M', foldM', fold1M',
   foldr, foldrM, foldr1, foldr1M,
 
+  vfoldlM, vfoldlM',
+
   -- * Specialised folds
   and, or, concatMapM,
 
   -- * Specialised folds
   and, or, concatMapM,
 
@@ -68,9 +72,11 @@ module Data.Vector.Fusion.Stream.Monadic (
   enumFromStepN, enumFromTo, enumFromThenTo,
 
   -- * Conversions
   enumFromStepN, enumFromTo, enumFromThenTo,
 
   -- * Conversions
-  toList, fromList, fromListN, unsafeFromList
+  toList, fromList, fromListN, unsafeFromList,
+  fromVector, reVector
 ) where
 
 ) where
 
+import Data.Vector.Generic.Base
 import Data.Vector.Fusion.Stream.Size
 import Data.Vector.Fusion.Util ( Box(..), delay_inline )
 
 import Data.Vector.Fusion.Stream.Size
 import Data.Vector.Fusion.Util ( Box(..), delay_inline )
 
@@ -111,33 +117,54 @@ emptyStream = "empty stream"
 #define EMPTY_STREAM (\s -> ERROR s emptyStream)
 
 -- | Result of taking a single step in a stream
 #define EMPTY_STREAM (\s -> ERROR s emptyStream)
 
 -- | Result of taking a single step in a stream
-data Step s a = Yield a s  -- ^ a new element and a new seed
-              | Skip    s  -- ^ just a new seed
-              | Done       -- ^ end of stream
+data Step s a where
+  Yield :: a -> s -> Step s a
+  Skip  :: s -> Step s a
+  Done  :: Step s a
+
+instance Functor (Step s) where
+  {-# INLINE fmap #-}
+  fmap f (Yield x s) = Yield (f x) s
+  fmap f (Skip s) = Skip s
+  fmap f Done = Done
+
+data Unf m a = forall s. Unf (s -> m (Step s a)) s
+
+instance Monad m => Functor (Unf m) where
+  {-# INLINE fmap #-}
+  fmap f (Unf step s) = Unf step' s
+    where
+      step' s = do r <- step s ; return (fmap f r)
 
 -- | Monadic streams
 
 -- | Monadic streams
-data Stream m a = forall s. Stream (s -> m (Step s a)) s Size
+data Stream m v a = Stream (Unf m a) (Unf m (Either a (v a))) Size
+
+simple :: Monad m => (s -> m (Step s a)) -> s -> Size -> Stream m v a
+{-# INLINE simple #-}
+simple step s sz = Stream (Unf step s) (Unf step' s) sz
+  where
+    step' s = do r <- step s ; return (fmap Left r)
 
 -- | 'Size' hint of a 'Stream'
 
 -- | 'Size' hint of a 'Stream'
-size :: Stream m a -> Size
+size :: Stream m a -> Size
 {-# INLINE size #-}
 size (Stream _ _ sz) = sz
 
 -- | Attach a 'Size' hint to a 'Stream'
 {-# INLINE size #-}
 size (Stream _ _ sz) = sz
 
 -- | Attach a 'Size' hint to a 'Stream'
-sized :: Stream m a -> Size -> Stream m a
+sized :: Stream m v a -> Size -> Stream m v a
 {-# INLINE_STREAM sized #-}
 {-# INLINE_STREAM sized #-}
-sized (Stream step s _) sz = Stream step s sz
+sized (Stream p q _) sz = Stream p q sz
 
 -- Length
 -- ------
 
 -- | Length of a 'Stream'
 
 -- Length
 -- ------
 
 -- | Length of a 'Stream'
-length :: Monad m => Stream m a -> m Int
+length :: Monad m => Stream m a -> m Int
 {-# INLINE_STREAM length #-}
 length s = foldl' (\n _ -> n+1) 0 s
 
 -- | Check if a 'Stream' is empty
 {-# INLINE_STREAM length #-}
 length s = foldl' (\n _ -> n+1) 0 s
 
 -- | Check if a 'Stream' is empty
-null :: Monad m => Stream m a -> m Bool
+null :: Monad m => Stream m a -> m Bool
 {-# INLINE_STREAM null #-}
 null s = foldr (\_ _ -> False) True s
 
 {-# INLINE_STREAM null #-}
 null s = foldr (\_ _ -> False) True s
 
@@ -146,44 +173,44 @@ null s = foldr (\_ _ -> False) True s
 -- ------------
 
 -- | Empty 'Stream'
 -- ------------
 
 -- | Empty 'Stream'
-empty :: Monad m => Stream m a
+empty :: Monad m => Stream m a
 {-# INLINE_STREAM empty #-}
 {-# INLINE_STREAM empty #-}
-empty = Stream (const (return Done)) () (Exact 0)
+empty = simple (const (return Done)) () (Exact 0)
 
 -- | Singleton 'Stream'
 
 -- | Singleton 'Stream'
-singleton :: Monad m => a -> Stream m a
+singleton :: Monad m => a -> Stream m a
 {-# INLINE_STREAM singleton #-}
 {-# INLINE_STREAM singleton #-}
-singleton x = Stream (return . step) True (Exact 1)
+singleton x = simple (return . step) True (Exact 1)
   where
     {-# INLINE_INNER step #-}
     step True  = Yield x False
     step False = Done
 
 -- | Replicate a value to a given length
   where
     {-# INLINE_INNER step #-}
     step True  = Yield x False
     step False = Done
 
 -- | Replicate a value to a given length
-replicate :: Monad m => Int -> a -> Stream m a
+replicate :: Monad m => Int -> a -> Stream m a
 {-# INLINE replicate #-}
 replicate n x = replicateM n (return x)
 
 -- | Yield a 'Stream' of values obtained by performing the monadic action the
 -- given number of times
 {-# INLINE replicate #-}
 replicate n x = replicateM n (return x)
 
 -- | Yield a 'Stream' of values obtained by performing the monadic action the
 -- given number of times
-replicateM :: Monad m => Int -> m a -> Stream m a
+replicateM :: Monad m => Int -> m a -> Stream m a
 {-# INLINE_STREAM replicateM #-}
 -- NOTE: We delay inlining max here because GHC will create a join point for
 -- the call to newArray# otherwise which is not really nice.
 {-# INLINE_STREAM replicateM #-}
 -- NOTE: We delay inlining max here because GHC will create a join point for
 -- the call to newArray# otherwise which is not really nice.
-replicateM n p = Stream step n (Exact (delay_inline max n 0))
+replicateM n p = simple step n (Exact (delay_inline max n 0))
   where
     {-# INLINE_INNER step #-}
     step i | i <= 0    = return Done
            | otherwise = do { x <- p; return $ Yield x (i-1) }
 
   where
     {-# INLINE_INNER step #-}
     step i | i <= 0    = return Done
            | otherwise = do { x <- p; return $ Yield x (i-1) }
 
-generate :: Monad m => Int -> (Int -> a) -> Stream m a
+generate :: Monad m => Int -> (Int -> a) -> Stream m a
 {-# INLINE generate #-}
 generate n f = generateM n (return . f)
 
 -- | Generate a stream from its indices
 {-# INLINE generate #-}
 generate n f = generateM n (return . f)
 
 -- | Generate a stream from its indices
-generateM :: Monad m => Int -> (Int -> m a) -> Stream m a
+generateM :: Monad m => Int -> (Int -> m a) -> Stream m a
 {-# INLINE_STREAM generateM #-}
 {-# INLINE_STREAM generateM #-}
-generateM n f = n `seq` Stream step 0 (Exact (delay_inline max n 0))
+generateM n f = n `seq` simple step 0 (Exact (delay_inline max n 0))
   where
     {-# INLINE_INNER step #-}
     step i | i < n     = do
   where
     {-# INLINE_INNER step #-}
     step i | i < n     = do
@@ -192,20 +219,22 @@ generateM n f = n `seq` Stream step 0 (Exact (delay_inline max n 0))
            | otherwise = return Done
 
 -- | Prepend an element
            | otherwise = return Done
 
 -- | Prepend an element
-cons :: Monad m => a -> Stream m a -> Stream m a
+cons :: Monad m => a -> Stream m v a -> Stream m v a
 {-# INLINE cons #-}
 cons x s = singleton x ++ s
 
 -- | Append an element
 {-# INLINE cons #-}
 cons x s = singleton x ++ s
 
 -- | Append an element
-snoc :: Monad m => Stream m a -> a -> Stream m a
+snoc :: Monad m => Stream m v a -> a -> Stream m v a
 {-# INLINE snoc #-}
 snoc s x = s ++ singleton x
 
 infixr 5 ++
 -- | Concatenate two 'Stream's
 {-# INLINE snoc #-}
 snoc s x = s ++ singleton x
 
 infixr 5 ++
 -- | Concatenate two 'Stream's
-(++) :: Monad m => Stream m a -> Stream m a -> Stream m a
+(++) :: Monad m => Stream m v a -> Stream m v a -> Stream m v a
 {-# INLINE_STREAM (++) #-}
 {-# INLINE_STREAM (++) #-}
-Stream stepa sa na ++ Stream stepb sb nb = Stream step (Left sa) (na + nb)
+Stream (Unf stepa sa) (Unf vstepa vsa) na
+  ++ Stream (Unf stepb sb) (Unf vstepb vsb) nb
+    = Stream (Unf step (Left sa)) (Unf vstep (Left vsa)) (na + nb)
   where
     {-# INLINE_INNER step #-}
     step (Left  sa) = do
   where
     {-# INLINE_INNER step #-}
     step (Left  sa) = do
@@ -221,13 +250,27 @@ Stream stepa sa na ++ Stream stepb sb nb = Stream step (Left sa) (na + nb)
                           Skip    sb' -> return $ Skip    (Right sb')
                           Done        -> return $ Done
 
                           Skip    sb' -> return $ Skip    (Right sb')
                           Done        -> return $ Done
 
+    {-# INLINE_INNER vstep #-}
+    vstep (Left  vsa) = do
+                          r <- vstepa vsa
+                          case r of
+                            Yield x vsa' -> return $ Yield x (Left  vsa')
+                            Skip    vsa' -> return $ Skip    (Left  vsa')
+                            Done         -> return $ Skip    (Right vsb)
+    vstep (Right vsb) = do
+                        r <- vstepb vsb
+                        case r of
+                          Yield x vsb' -> return $ Yield x (Right vsb')
+                          Skip    vsb' -> return $ Skip    (Right vsb')
+                          Done         -> return $ Done
+
 -- Accessing elements
 -- ------------------
 
 -- | First element of the 'Stream' or error if empty
 -- Accessing elements
 -- ------------------
 
 -- | First element of the 'Stream' or error if empty
-head :: Monad m => Stream m a -> m a
+head :: Monad m => Stream m a -> m a
 {-# INLINE_STREAM head #-}
 {-# INLINE_STREAM head #-}
-head (Stream step s _) = head_loop SPEC s
+head (Stream (Unf step s) _ _) = head_loop SPEC s
   where
     head_loop !sPEC s
       = do
   where
     head_loop !sPEC s
       = do
@@ -240,9 +283,9 @@ head (Stream step s _) = head_loop SPEC s
 
 
 -- | Last element of the 'Stream' or error if empty
 
 
 -- | Last element of the 'Stream' or error if empty
-last :: Monad m => Stream m a -> m a
+last :: Monad m => Stream m a -> m a
 {-# INLINE_STREAM last #-}
 {-# INLINE_STREAM last #-}
-last (Stream step s _) = last_loop0 SPEC s
+last (Stream (Unf step s) _ _) = last_loop0 SPEC s
   where
     last_loop0 !sPEC s
       = do
   where
     last_loop0 !sPEC s
       = do
@@ -262,10 +305,10 @@ last (Stream step s _) = last_loop0 SPEC s
 
 infixl 9 !!
 -- | Element at the given position
 
 infixl 9 !!
 -- | Element at the given position
-(!!) :: Monad m => Stream m a -> Int -> m a
+(!!) :: Monad m => Stream m a -> Int -> m a
 {-# INLINE (!!) #-}
 {-# INLINE (!!) #-}
-Stream step s _ !! i | i < 0     = ERROR "!!" "negative index"
-                     | otherwise = index_loop SPEC s i
+Stream (Unf step s) _ _ !! i | i < 0     = ERROR "!!" "negative index"
+                             | otherwise = index_loop SPEC s i
   where
     index_loop !sPEC s i
       = i `seq`
   where
     index_loop !sPEC s i
       = i `seq`
@@ -279,9 +322,9 @@ Stream step s _ !! i | i < 0     = ERROR "!!" "negative index"
 
 infixl 9 !?
 -- | Element at the given position or 'Nothing' if out of bounds
 
 infixl 9 !?
 -- | Element at the given position or 'Nothing' if out of bounds
-(!?) :: Monad m => Stream m a -> Int -> m (Maybe a)
+(!?) :: Monad m => Stream m a -> Int -> m (Maybe a)
 {-# INLINE (!?) #-}
 {-# INLINE (!?) #-}
-Stream step s _ !? i = index_loop SPEC s i
+Stream (Unf step s) _ _ !? i = index_loop SPEC s i
   where
     index_loop !sPEC s i
       = i `seq`
   where
     index_loop !sPEC s i
       = i `seq`
@@ -299,15 +342,15 @@ Stream step s _ !? i = index_loop SPEC s i
 -- | Extract a substream of the given length starting at the given position.
 slice :: Monad m => Int   -- ^ starting index
                  -> Int   -- ^ length
 -- | Extract a substream of the given length starting at the given position.
 slice :: Monad m => Int   -- ^ starting index
                  -> Int   -- ^ length
-                 -> Stream m a
-                 -> Stream m a
+                 -> Stream m a
+                 -> Stream m a
 {-# INLINE slice #-}
 slice i n s = take n (drop i s)
 
 -- | All but the last element
 {-# INLINE slice #-}
 slice i n s = take n (drop i s)
 
 -- | All but the last element
-init :: Monad m => Stream m a -> Stream m a
+init :: Monad m => Stream m v a -> Stream m v a
 {-# INLINE_STREAM init #-}
 {-# INLINE_STREAM init #-}
-init (Stream step s sz) = Stream step' (Nothing, s) (sz - 1)
+init (Stream (Unf step s) _ sz) = simple step' (Nothing, s) (sz - 1)
   where
     {-# INLINE_INNER step' #-}
     step' (Nothing, s) = liftM (\r ->
   where
     {-# INLINE_INNER step' #-}
     step' (Nothing, s) = liftM (\r ->
@@ -325,9 +368,9 @@ init (Stream step s sz) = Stream step' (Nothing, s) (sz - 1)
                          ) (step s)
 
 -- | All but the first element
                          ) (step s)
 
 -- | All but the first element
-tail :: Monad m => Stream m a -> Stream m a
+tail :: Monad m => Stream m v a -> Stream m v a
 {-# INLINE_STREAM tail #-}
 {-# INLINE_STREAM tail #-}
-tail (Stream step s sz) = Stream step' (Left s) (sz - 1)
+tail (Stream (Unf step s) _ sz) = simple step' (Left s) (sz - 1)
   where
     {-# INLINE_INNER step' #-}
     step' (Left  s) = liftM (\r ->
   where
     {-# INLINE_INNER step' #-}
     step' (Left  s) = liftM (\r ->
@@ -345,9 +388,9 @@ tail (Stream step s sz) = Stream step' (Left s) (sz - 1)
                       ) (step s)
 
 -- | The first @n@ elements
                       ) (step s)
 
 -- | The first @n@ elements
-take :: Monad m => Int -> Stream m a -> Stream m a
+take :: Monad m => Int -> Stream m v a -> Stream m v a
 {-# INLINE_STREAM take #-}
 {-# INLINE_STREAM take #-}
-take n (Stream step s sz) = Stream step' (s, 0) (smaller (Exact n) sz)
+take n (Stream (Unf step s) _ sz) = simple step' (s, 0) (smaller (Exact n) sz)
   where
     {-# INLINE_INNER step' #-}
     step' (s, i) | i < n = liftM (\r ->
   where
     {-# INLINE_INNER step' #-}
     step' (s, i) | i < n = liftM (\r ->
@@ -359,9 +402,9 @@ take n (Stream step s sz) = Stream step' (s, 0) (smaller (Exact n) sz)
     step' (s, i) = return Done
 
 -- | All but the first @n@ elements
     step' (s, i) = return Done
 
 -- | All but the first @n@ elements
-drop :: Monad m => Int -> Stream m a -> Stream m a
+drop :: Monad m => Int -> Stream m v a -> Stream m v a
 {-# INLINE_STREAM drop #-}
 {-# INLINE_STREAM drop #-}
-drop n (Stream step s sz) = Stream step' (s, Just n) (sz - Exact n)
+drop n (Stream (Unf step s) _ sz) = simple step' (s, Just n) (sz - Exact n)
   where
     {-# INLINE_INNER step' #-}
     step' (s, Just i) | i > 0 = liftM (\r ->
   where
     {-# INLINE_INNER step' #-}
     step' (s, Just i) | i > 0 = liftM (\r ->
@@ -382,20 +425,20 @@ drop n (Stream step s sz) = Stream step' (s, Just n) (sz - Exact n)
 -- Mapping
 -- -------
 
 -- Mapping
 -- -------
 
-instance Monad m => Functor (Stream m) where
+instance Monad m => Functor (Stream m v) where
   {-# INLINE fmap #-}
   fmap = map
 
 -- | Map a function over a 'Stream'
   {-# INLINE fmap #-}
   fmap = map
 
 -- | Map a function over a 'Stream'
-map :: Monad m => (a -> b) -> Stream m a -> Stream m b
+map :: Monad m => (a -> b) -> Stream m v a -> Stream m v b
 {-# INLINE map #-}
 map f = mapM (return . f)
 
 
 -- | Map a monadic function over a 'Stream'
 {-# INLINE map #-}
 map f = mapM (return . f)
 
 
 -- | Map a monadic function over a 'Stream'
-mapM :: Monad m => (a -> m b) -> Stream m a -> Stream m b
+mapM :: Monad m => (a -> m b) -> Stream m v a -> Stream m v b
 {-# INLINE_STREAM mapM #-}
 {-# INLINE_STREAM mapM #-}
-mapM f (Stream step s n) = Stream step' s n
+mapM f (Stream (Unf step s) _ n) = simple step' s n
   where
     {-# INLINE_INNER step' #-}
     step' s = do
   where
     {-# INLINE_INNER step' #-}
     step' s = do
@@ -405,9 +448,9 @@ mapM f (Stream step s n) = Stream step' s n
                   Skip    s' -> return (Skip    s')
                   Done       -> return Done
 
                   Skip    s' -> return (Skip    s')
                   Done       -> return Done
 
-consume :: Monad m => Stream m a -> m ()
+consume :: Monad m => Stream m a -> m ()
 {-# INLINE_STREAM consume #-}
 {-# INLINE_STREAM consume #-}
-consume (Stream step s _) = consume_loop SPEC s
+consume (Stream _ (Unf step s) _) = consume_loop SPEC s
   where
     consume_loop !sPEC s
       = do
   where
     consume_loop !sPEC s
       = do
@@ -418,19 +461,19 @@ consume (Stream step s _) = consume_loop SPEC s
             Done       -> return ()
 
 -- | Execute a monadic action for each element of the 'Stream'
             Done       -> return ()
 
 -- | Execute a monadic action for each element of the 'Stream'
-mapM_ :: Monad m => (a -> m b) -> Stream m a -> m ()
+mapM_ :: Monad m => (a -> m b) -> Stream m a -> m ()
 {-# INLINE_STREAM mapM_ #-}
 mapM_ m = consume . mapM m
 
 -- | Transform a 'Stream' to use a different monad
 trans :: (Monad m, Monad m') => (forall a. m a -> m' a)
 {-# INLINE_STREAM mapM_ #-}
 mapM_ m = consume . mapM m
 
 -- | Transform a 'Stream' to use a different monad
 trans :: (Monad m, Monad m') => (forall a. m a -> m' a)
-                             -> Stream m a -> Stream m' a
+                             -> Stream m v a -> Stream m' v a
 {-# INLINE_STREAM trans #-}
 {-# INLINE_STREAM trans #-}
-trans f (Stream step s n) = Stream (f . step) s n
+trans f (Stream (Unf step s) _ n) = simple (f . step) s n
 
 
-unbox :: Monad m => Stream m (Box a) -> Stream m a
+unbox :: Monad m => Stream m v (Box a) -> Stream m v a
 {-# INLINE_STREAM unbox #-}
 {-# INLINE_STREAM unbox #-}
-unbox (Stream step s n) = Stream step' s n
+unbox (Stream (Unf step s) _ n) = simple step' s n
   where
     {-# INLINE_INNER step' #-}
     step' s = do
   where
     {-# INLINE_INNER step' #-}
     step' s = do
@@ -444,9 +487,9 @@ unbox (Stream step s n) = Stream step' s n
 -- -------
 
 -- | Pair each element in a 'Stream' with its index
 -- -------
 
 -- | Pair each element in a 'Stream' with its index
-indexed :: Monad m => Stream m a -> Stream m (Int,a)
+indexed :: Monad m => Stream m v a -> Stream m v (Int,a)
 {-# INLINE_STREAM indexed #-}
 {-# INLINE_STREAM indexed #-}
-indexed (Stream step s n) = Stream step' (s,0) n
+indexed (Stream (Unf step s) _ n) = simple step' (s,0) n
   where
     {-# INLINE_INNER step' #-}
     step' (s,i) = i `seq`
   where
     {-# INLINE_INNER step' #-}
     step' (s,i) = i `seq`
@@ -459,9 +502,9 @@ indexed (Stream step s n) = Stream step' (s,0) n
 
 -- | Pair each element in a 'Stream' with its index, starting from the right
 -- and counting down
 
 -- | Pair each element in a 'Stream' with its index, starting from the right
 -- and counting down
-indexedR :: Monad m => Int -> Stream m a -> Stream m (Int,a)
+indexedR :: Monad m => Int -> Stream m v a -> Stream m v (Int,a)
 {-# INLINE_STREAM indexedR #-}
 {-# INLINE_STREAM indexedR #-}
-indexedR m (Stream step s n) = Stream step' (s,m) n
+indexedR m (Stream (Unf step s) _ n) = simple step' (s,m) n
   where
     {-# INLINE_INNER step' #-}
     step' (s,i) = i `seq`
   where
     {-# INLINE_INNER step' #-}
     step' (s,i) = i `seq`
@@ -475,10 +518,10 @@ indexedR m (Stream step s n) = Stream step' (s,m) n
                       Done       -> return Done
 
 -- | Zip two 'Stream's with the given monadic function
                       Done       -> return Done
 
 -- | Zip two 'Stream's with the given monadic function
-zipWithM :: Monad m => (a -> b -> m c) -> Stream m a -> Stream m b -> Stream m c
+zipWithM :: Monad m => (a -> b -> m c) -> Stream m v a -> Stream m v b -> Stream m v c
 {-# INLINE_STREAM zipWithM #-}
 {-# INLINE_STREAM zipWithM #-}
-zipWithM f (Stream stepa sa na) (Stream stepb sb nb)
-  = Stream step (sa, sb, Nothing) (smaller na nb)
+zipWithM f (Stream (Unf stepa sa) _ na) (Stream (Unf stepb sb) _ nb)
+  = simple step (sa, sb, Nothing) (smaller na nb)
   where
     {-# INLINE_INNER step #-}
     step (sa, sb, Nothing) = liftM (\r ->
   where
     {-# INLINE_INNER step #-}
     step (sa, sb, Nothing) = liftM (\r ->
@@ -506,14 +549,14 @@ zipWithM f (Stream stepa sa na) (Stream stepb sb nb)
 
   #-}
 
 
   #-}
 
-zipWithM_ :: Monad m => (a -> b -> m c) -> Stream m a -> Stream m b -> m ()
+zipWithM_ :: Monad m => (a -> b -> m c) -> Stream m v a -> Stream m v b -> m ()
 {-# INLINE zipWithM_ #-}
 zipWithM_ f sa sb = consume (zipWithM f sa sb)
 
 {-# INLINE zipWithM_ #-}
 zipWithM_ f sa sb = consume (zipWithM f sa sb)
 
-zipWith3M :: Monad m => (a -> b -> c -> m d) -> Stream m a -> Stream m b -> Stream m c -> Stream m d
+zipWith3M :: Monad m => (a -> b -> c -> m d) -> Stream m v a -> Stream m v b -> Stream m v c -> Stream m v d
 {-# INLINE_STREAM zipWith3M #-}
 {-# INLINE_STREAM zipWith3M #-}
-zipWith3M f (Stream stepa sa na) (Stream stepb sb nb) (Stream stepc sc nc)
-  = Stream step (sa, sb, sc, Nothing) (smaller na (smaller nb nc))
+zipWith3M f (Stream (Unf stepa sa) _ na) (Stream (Unf stepb sb) _ nb) (Stream (Unf stepc sc) _ nc)
+  = simple step (sa, sb, sc, Nothing) (smaller na (smaller nb nc))
   where
     {-# INLINE_INNER step #-}
     step (sa, sb, sc, Nothing) = do
   where
     {-# INLINE_INNER step #-}
     step (sa, sb, sc, Nothing) = do
@@ -538,74 +581,74 @@ zipWith3M f (Stream stepa sa na) (Stream stepb sb nb) (Stream stepc sc nc)
             Done        -> return $ Done
 
 zipWith4M :: Monad m => (a -> b -> c -> d -> m e)
             Done        -> return $ Done
 
 zipWith4M :: Monad m => (a -> b -> c -> d -> m e)
-                     -> Stream m a -> Stream m b -> Stream m c -> Stream m d
-                     -> Stream m e
+                     -> Stream m v a -> Stream m v b -> Stream m v c -> Stream m v d
+                     -> Stream m e
 {-# INLINE zipWith4M #-}
 zipWith4M f sa sb sc sd
   = zipWithM (\(a,b) (c,d) -> f a b c d) (zip sa sb) (zip sc sd)
 
 zipWith5M :: Monad m => (a -> b -> c -> d -> e -> m f)
 {-# INLINE zipWith4M #-}
 zipWith4M f sa sb sc sd
   = zipWithM (\(a,b) (c,d) -> f a b c d) (zip sa sb) (zip sc sd)
 
 zipWith5M :: Monad m => (a -> b -> c -> d -> e -> m f)
-                     -> Stream m a -> Stream m b -> Stream m c -> Stream m d
-                     -> Stream m e -> Stream m f
+                     -> Stream m v a -> Stream m v b -> Stream m v c -> Stream m v d
+                     -> Stream m v e -> Stream m v f
 {-# INLINE zipWith5M #-}
 zipWith5M f sa sb sc sd se
   = zipWithM (\(a,b,c) (d,e) -> f a b c d e) (zip3 sa sb sc) (zip sd se)
 
 zipWith6M :: Monad m => (a -> b -> c -> d -> e -> f -> m g)
 {-# INLINE zipWith5M #-}
 zipWith5M f sa sb sc sd se
   = zipWithM (\(a,b,c) (d,e) -> f a b c d e) (zip3 sa sb sc) (zip sd se)
 
 zipWith6M :: Monad m => (a -> b -> c -> d -> e -> f -> m g)
-                     -> Stream m a -> Stream m b -> Stream m c -> Stream m d
-                     -> Stream m e -> Stream m f -> Stream m g
+                     -> Stream m v a -> Stream m v b -> Stream m v c -> Stream m v d
+                     -> Stream m v e -> Stream m v f -> Stream m v g
 {-# INLINE zipWith6M #-}
 zipWith6M fn sa sb sc sd se sf
   = zipWithM (\(a,b,c) (d,e,f) -> fn a b c d e f) (zip3 sa sb sc)
                                                   (zip3 sd se sf)
 
 {-# INLINE zipWith6M #-}
 zipWith6M fn sa sb sc sd se sf
   = zipWithM (\(a,b,c) (d,e,f) -> fn a b c d e f) (zip3 sa sb sc)
                                                   (zip3 sd se sf)
 
-zipWith :: Monad m => (a -> b -> c) -> Stream m a -> Stream m b -> Stream m c
+zipWith :: Monad m => (a -> b -> c) -> Stream m v a -> Stream m v b -> Stream m v c
 {-# INLINE zipWith #-}
 zipWith f = zipWithM (\a b -> return (f a b))
 
 zipWith3 :: Monad m => (a -> b -> c -> d)
 {-# INLINE zipWith #-}
 zipWith f = zipWithM (\a b -> return (f a b))
 
 zipWith3 :: Monad m => (a -> b -> c -> d)
-                    -> Stream m a -> Stream m b -> Stream m c -> Stream m d
+                    -> Stream m v a -> Stream m v b -> Stream m v c -> Stream m v d
 {-# INLINE zipWith3 #-}
 zipWith3 f = zipWith3M (\a b c -> return (f a b c))
 
 zipWith4 :: Monad m => (a -> b -> c -> d -> e)
 {-# INLINE zipWith3 #-}
 zipWith3 f = zipWith3M (\a b c -> return (f a b c))
 
 zipWith4 :: Monad m => (a -> b -> c -> d -> e)
-                    -> Stream m a -> Stream m b -> Stream m c -> Stream m d
-                    -> Stream m e
+                    -> Stream m v a -> Stream m v b -> Stream m v c -> Stream m v d
+                    -> Stream m e
 {-# INLINE zipWith4 #-}
 zipWith4 f = zipWith4M (\a b c d -> return (f a b c d))
 
 zipWith5 :: Monad m => (a -> b -> c -> d -> e -> f)
 {-# INLINE zipWith4 #-}
 zipWith4 f = zipWith4M (\a b c d -> return (f a b c d))
 
 zipWith5 :: Monad m => (a -> b -> c -> d -> e -> f)
-                    -> Stream m a -> Stream m b -> Stream m c -> Stream m d
-                    -> Stream m e -> Stream m f
+                    -> Stream m v a -> Stream m v b -> Stream m v c -> Stream m v d
+                    -> Stream m v e -> Stream m v f
 {-# INLINE zipWith5 #-}
 zipWith5 f = zipWith5M (\a b c d e -> return (f a b c d e))
 
 zipWith6 :: Monad m => (a -> b -> c -> d -> e -> f -> g)
 {-# INLINE zipWith5 #-}
 zipWith5 f = zipWith5M (\a b c d e -> return (f a b c d e))
 
 zipWith6 :: Monad m => (a -> b -> c -> d -> e -> f -> g)
-                    -> Stream m a -> Stream m b -> Stream m c -> Stream m d
-                    -> Stream m e -> Stream m f -> Stream m g
+                    -> Stream m v a -> Stream m v b -> Stream m v c -> Stream m v d
+                    -> Stream m v e -> Stream m v f -> Stream m v g
 {-# INLINE zipWith6 #-}
 zipWith6 fn = zipWith6M (\a b c d e f -> return (fn a b c d e f))
 
 {-# INLINE zipWith6 #-}
 zipWith6 fn = zipWith6M (\a b c d e f -> return (fn a b c d e f))
 
-zip :: Monad m => Stream m a -> Stream m b -> Stream m (a,b)
+zip :: Monad m => Stream m v a -> Stream m v b -> Stream m v (a,b)
 {-# INLINE zip #-}
 zip = zipWith (,)
 
 {-# INLINE zip #-}
 zip = zipWith (,)
 
-zip3 :: Monad m => Stream m a -> Stream m b -> Stream m c -> Stream m (a,b,c)
+zip3 :: Monad m => Stream m v a -> Stream m v b -> Stream m v c -> Stream m v (a,b,c)
 {-# INLINE zip3 #-}
 zip3 = zipWith3 (,,)
 
 {-# INLINE zip3 #-}
 zip3 = zipWith3 (,,)
 
-zip4 :: Monad m => Stream m a -> Stream m b -> Stream m c -> Stream m d
-                -> Stream m (a,b,c,d)
+zip4 :: Monad m => Stream m v a -> Stream m v b -> Stream m v c -> Stream m v d
+                -> Stream m (a,b,c,d)
 {-# INLINE zip4 #-}
 zip4 = zipWith4 (,,,)
 
 {-# INLINE zip4 #-}
 zip4 = zipWith4 (,,,)
 
-zip5 :: Monad m => Stream m a -> Stream m b -> Stream m c -> Stream m d
-                -> Stream m e -> Stream m (a,b,c,d,e)
+zip5 :: Monad m => Stream m v a -> Stream m v b -> Stream m v c -> Stream m v d
+                -> Stream m v e -> Stream m v (a,b,c,d,e)
 {-# INLINE zip5 #-}
 zip5 = zipWith5 (,,,,)
 
 {-# INLINE zip5 #-}
 zip5 = zipWith5 (,,,,)
 
-zip6 :: Monad m => Stream m a -> Stream m b -> Stream m c -> Stream m d
-                -> Stream m e -> Stream m f -> Stream m (a,b,c,d,e,f)
+zip6 :: Monad m => Stream m v a -> Stream m v b -> Stream m v c -> Stream m v d
+                -> Stream m v e -> Stream m v f -> Stream m v (a,b,c,d,e,f)
 {-# INLINE zip6 #-}
 zip6 = zipWith6 (,,,,,)
 
 {-# INLINE zip6 #-}
 zip6 = zipWith6 (,,,,,)
 
@@ -613,14 +656,14 @@ zip6 = zipWith6 (,,,,,)
 -- ---------
 
 -- | Drop elements which do not satisfy the predicate
 -- ---------
 
 -- | Drop elements which do not satisfy the predicate
-filter :: Monad m => (a -> Bool) -> Stream m a -> Stream m a
+filter :: Monad m => (a -> Bool) -> Stream m v a -> Stream m v a
 {-# INLINE filter #-}
 filter f = filterM (return . f)
 
 -- | Drop elements which do not satisfy the monadic predicate
 {-# INLINE filter #-}
 filter f = filterM (return . f)
 
 -- | Drop elements which do not satisfy the monadic predicate
-filterM :: Monad m => (a -> m Bool) -> Stream m a -> Stream m a
+filterM :: Monad m => (a -> m Bool) -> Stream m v a -> Stream m v a
 {-# INLINE_STREAM filterM #-}
 {-# INLINE_STREAM filterM #-}
-filterM f (Stream step s n) = Stream step' s (toMax n)
+filterM f (Stream (Unf step s) _ n) = simple step' s (toMax n)
   where
     {-# INLINE_INNER step' #-}
     step' s = do
   where
     {-# INLINE_INNER step' #-}
     step' s = do
@@ -634,14 +677,14 @@ filterM f (Stream step s n) = Stream step' s (toMax n)
                   Done       -> return $ Done
 
 -- | Longest prefix of elements that satisfy the predicate
                   Done       -> return $ Done
 
 -- | Longest prefix of elements that satisfy the predicate
-takeWhile :: Monad m => (a -> Bool) -> Stream m a -> Stream m a
+takeWhile :: Monad m => (a -> Bool) -> Stream m v a -> Stream m v a
 {-# INLINE takeWhile #-}
 takeWhile f = takeWhileM (return . f)
 
 -- | Longest prefix of elements that satisfy the monadic predicate
 {-# INLINE takeWhile #-}
 takeWhile f = takeWhileM (return . f)
 
 -- | Longest prefix of elements that satisfy the monadic predicate
-takeWhileM :: Monad m => (a -> m Bool) -> Stream m a -> Stream m a
+takeWhileM :: Monad m => (a -> m Bool) -> Stream m v a -> Stream m v a
 {-# INLINE_STREAM takeWhileM #-}
 {-# INLINE_STREAM takeWhileM #-}
-takeWhileM f (Stream step s n) = Stream step' s (toMax n)
+takeWhileM f (Stream (Unf step s) _ n) = simple step' s (toMax n)
   where
     {-# INLINE_INNER step' #-}
     step' s = do
   where
     {-# INLINE_INNER step' #-}
     step' s = do
@@ -654,16 +697,16 @@ takeWhileM f (Stream step s n) = Stream step' s (toMax n)
                   Done       -> return $ Done
 
 -- | Drop the longest prefix of elements that satisfy the predicate
                   Done       -> return $ Done
 
 -- | Drop the longest prefix of elements that satisfy the predicate
-dropWhile :: Monad m => (a -> Bool) -> Stream m a -> Stream m a
+dropWhile :: Monad m => (a -> Bool) -> Stream m v a -> Stream m v a
 {-# INLINE dropWhile #-}
 dropWhile f = dropWhileM (return . f)
 
 data DropWhile s a = DropWhile_Drop s | DropWhile_Yield a s | DropWhile_Next s
 
 -- | Drop the longest prefix of elements that satisfy the monadic predicate
 {-# INLINE dropWhile #-}
 dropWhile f = dropWhileM (return . f)
 
 data DropWhile s a = DropWhile_Drop s | DropWhile_Yield a s | DropWhile_Next s
 
 -- | Drop the longest prefix of elements that satisfy the monadic predicate
-dropWhileM :: Monad m => (a -> m Bool) -> Stream m a -> Stream m a
+dropWhileM :: Monad m => (a -> m Bool) -> Stream m v a -> Stream m v a
 {-# INLINE_STREAM dropWhileM #-}
 {-# INLINE_STREAM dropWhileM #-}
-dropWhileM f (Stream step s n) = Stream step' (DropWhile_Drop s) (toMax n)
+dropWhileM f (Stream (Unf step s) _ n) = simple step' (DropWhile_Drop s) (toMax n)
   where
     -- NOTE: we jump through hoops here to have only one Yield; local data
     -- declarations would be nice!
   where
     -- NOTE: we jump through hoops here to have only one Yield; local data
     -- declarations would be nice!
@@ -695,9 +738,9 @@ dropWhileM f (Stream step s n) = Stream step' (DropWhile_Drop s) (toMax n)
 
 infix 4 `elem`
 -- | Check whether the 'Stream' contains an element
 
 infix 4 `elem`
 -- | Check whether the 'Stream' contains an element
-elem :: (Monad m, Eq a) => a -> Stream m a -> m Bool
+elem :: (Monad m, Eq a) => a -> Stream m a -> m Bool
 {-# INLINE_STREAM elem #-}
 {-# INLINE_STREAM elem #-}
-elem x (Stream step s _) = elem_loop SPEC s
+elem x (Stream (Unf step s) _ _) = elem_loop SPEC s
   where
     elem_loop !sPEC s
       = do
   where
     elem_loop !sPEC s
       = do
@@ -710,21 +753,21 @@ elem x (Stream step s _) = elem_loop SPEC s
 
 infix 4 `notElem`
 -- | Inverse of `elem`
 
 infix 4 `notElem`
 -- | Inverse of `elem`
-notElem :: (Monad m, Eq a) => a -> Stream m a -> m Bool
+notElem :: (Monad m, Eq a) => a -> Stream m a -> m Bool
 {-# INLINE notElem #-}
 notElem x s = liftM not (elem x s)
 
 -- | Yield 'Just' the first element that satisfies the predicate or 'Nothing'
 -- if no such element exists.
 {-# INLINE notElem #-}
 notElem x s = liftM not (elem x s)
 
 -- | Yield 'Just' the first element that satisfies the predicate or 'Nothing'
 -- if no such element exists.
-find :: Monad m => (a -> Bool) -> Stream m a -> m (Maybe a)
+find :: Monad m => (a -> Bool) -> Stream m a -> m (Maybe a)
 {-# INLINE find #-}
 find f = findM (return . f)
 
 -- | Yield 'Just' the first element that satisfies the monadic predicate or
 -- 'Nothing' if no such element exists.
 {-# INLINE find #-}
 find f = findM (return . f)
 
 -- | Yield 'Just' the first element that satisfies the monadic predicate or
 -- 'Nothing' if no such element exists.
-findM :: Monad m => (a -> m Bool) -> Stream m a -> m (Maybe a)
+findM :: Monad m => (a -> m Bool) -> Stream m a -> m (Maybe a)
 {-# INLINE_STREAM findM #-}
 {-# INLINE_STREAM findM #-}
-findM f (Stream step s _) = find_loop SPEC s
+findM f (Stream (Unf step s) _ _) = find_loop SPEC s
   where
     find_loop !sPEC s
       = do
   where
     find_loop !sPEC s
       = do
@@ -739,15 +782,15 @@ findM f (Stream step s _) = find_loop SPEC s
 
 -- | Yield 'Just' the index of the first element that satisfies the predicate
 -- or 'Nothing' if no such element exists.
 
 -- | Yield 'Just' the index of the first element that satisfies the predicate
 -- or 'Nothing' if no such element exists.
-findIndex :: Monad m => (a -> Bool) -> Stream m a -> m (Maybe Int)
+findIndex :: Monad m => (a -> Bool) -> Stream m a -> m (Maybe Int)
 {-# INLINE_STREAM findIndex #-}
 findIndex f = findIndexM (return . f)
 
 -- | Yield 'Just' the index of the first element that satisfies the monadic
 -- predicate or 'Nothing' if no such element exists.
 {-# INLINE_STREAM findIndex #-}
 findIndex f = findIndexM (return . f)
 
 -- | Yield 'Just' the index of the first element that satisfies the monadic
 -- predicate or 'Nothing' if no such element exists.
-findIndexM :: Monad m => (a -> m Bool) -> Stream m a -> m (Maybe Int)
+findIndexM :: Monad m => (a -> m Bool) -> Stream m a -> m (Maybe Int)
 {-# INLINE_STREAM findIndexM #-}
 {-# INLINE_STREAM findIndexM #-}
-findIndexM f (Stream step s _) = findIndex_loop SPEC s 0
+findIndexM f (Stream (Unf step s) _ _) = findIndex_loop SPEC s 0
   where
     findIndex_loop !sPEC s i
       = do
   where
     findIndex_loop !sPEC s i
       = do
@@ -764,14 +807,14 @@ findIndexM f (Stream step s _) = findIndex_loop SPEC s 0
 -- -------
 
 -- | Left fold
 -- -------
 
 -- | Left fold
-foldl :: Monad m => (a -> b -> a) -> a -> Stream m b -> m a
+foldl :: Monad m => (a -> b -> a) -> a -> Stream m b -> m a
 {-# INLINE foldl #-}
 foldl f = foldlM (\a b -> return (f a b))
 
 -- | Left fold with a monadic operator
 {-# INLINE foldl #-}
 foldl f = foldlM (\a b -> return (f a b))
 
 -- | Left fold with a monadic operator
-foldlM :: Monad m => (a -> b -> m a) -> a -> Stream m b -> m a
+foldlM :: Monad m => (a -> b -> m a) -> a -> Stream m b -> m a
 {-# INLINE_STREAM foldlM #-}
 {-# INLINE_STREAM foldlM #-}
-foldlM m z (Stream step s _) = foldlM_loop SPEC z s
+foldlM m z (Stream (Unf step s) _ _) = foldlM_loop SPEC z s
   where
     foldlM_loop !sPEC z s
       = do
   where
     foldlM_loop !sPEC z s
       = do
@@ -782,42 +825,55 @@ foldlM m z (Stream step s _) = foldlM_loop SPEC z s
             Done       -> return z
 
 -- | Same as 'foldlM'
             Done       -> return z
 
 -- | Same as 'foldlM'
-foldM :: Monad m => (a -> b -> m a) -> a -> Stream m b -> m a
+foldM :: Monad m => (a -> b -> m a) -> a -> Stream m b -> m a
 {-# INLINE foldM #-}
 foldM = foldlM
 
 {-# INLINE foldM #-}
 foldM = foldlM
 
+vfoldlM :: Monad m => (a -> b -> m a) -> (a -> v b -> m a) -> a -> Stream m v b -> m a
+{-# INLINE_STREAM vfoldlM #-}
+vfoldlM p q z (Stream _ (Unf step s) _) = vfoldlM_loop SPEC z s
+  where
+    vfoldlM_loop !sPEC z s
+      = do
+          r <- step s
+          case r of
+            Yield (Left  x) s' -> do { z' <- p z x; vfoldlM_loop SPEC z' s' }
+            Yield (Right v) s' -> do { z' <- q z v; vfoldlM_loop SPEC z' s' }
+            Skip            s' -> vfoldlM_loop SPEC z s'
+            Done               -> return z
+
 -- | Left fold over a non-empty 'Stream'
 -- | Left fold over a non-empty 'Stream'
-foldl1 :: Monad m => (a -> a -> a) -> Stream m a -> m a
+foldl1 :: Monad m => (a -> a -> a) -> Stream m a -> m a
 {-# INLINE foldl1 #-}
 foldl1 f = foldl1M (\a b -> return (f a b))
 
 -- | Left fold over a non-empty 'Stream' with a monadic operator
 {-# INLINE foldl1 #-}
 foldl1 f = foldl1M (\a b -> return (f a b))
 
 -- | Left fold over a non-empty 'Stream' with a monadic operator
-foldl1M :: Monad m => (a -> a -> m a) -> Stream m a -> m a
+foldl1M :: Monad m => (a -> a -> m a) -> Stream m a -> m a
 {-# INLINE_STREAM foldl1M #-}
 {-# INLINE_STREAM foldl1M #-}
-foldl1M f (Stream step s sz) = foldl1M_loop SPEC s
+foldl1M f (Stream (Unf step s) _ sz) = foldl1M_loop SPEC s
   where
     foldl1M_loop !sPEC s
       = do
           r <- step s
           case r of
   where
     foldl1M_loop !sPEC s
       = do
           r <- step s
           case r of
-            Yield x s' -> foldlM f x (Stream step s' (sz - 1))
+            Yield x s' -> foldlM f x (simple step s' (sz - 1))
             Skip    s' -> foldl1M_loop SPEC s'
             Done       -> EMPTY_STREAM "foldl1M"
 
 -- | Same as 'foldl1M'
             Skip    s' -> foldl1M_loop SPEC s'
             Done       -> EMPTY_STREAM "foldl1M"
 
 -- | Same as 'foldl1M'
-fold1M :: Monad m => (a -> a -> m a) -> Stream m a -> m a
+fold1M :: Monad m => (a -> a -> m a) -> Stream m a -> m a
 {-# INLINE fold1M #-}
 fold1M = foldl1M
 
 -- | Left fold with a strict accumulator
 {-# INLINE fold1M #-}
 fold1M = foldl1M
 
 -- | Left fold with a strict accumulator
-foldl' :: Monad m => (a -> b -> a) -> a -> Stream m b -> m a
+foldl' :: Monad m => (a -> b -> a) -> a -> Stream m b -> m a
 {-# INLINE foldl' #-}
 foldl' f = foldlM' (\a b -> return (f a b))
 
 -- | Left fold with a strict accumulator and a monadic operator
 {-# INLINE foldl' #-}
 foldl' f = foldlM' (\a b -> return (f a b))
 
 -- | Left fold with a strict accumulator and a monadic operator
-foldlM' :: Monad m => (a -> b -> m a) -> a -> Stream m b -> m a
+foldlM' :: Monad m => (a -> b -> m a) -> a -> Stream m b -> m a
 {-# INLINE_STREAM foldlM' #-}
 {-# INLINE_STREAM foldlM' #-}
-foldlM' m z (Stream step s _) = foldlM'_loop SPEC z s
+foldlM' m z (Stream (Unf step s) _ _) = foldlM'_loop SPEC z s
   where
     foldlM'_loop !sPEC z s
       = z `seq`
   where
     foldlM'_loop !sPEC z s
       = z `seq`
@@ -829,43 +885,56 @@ foldlM' m z (Stream step s _) = foldlM'_loop SPEC z s
             Done       -> return z
 
 -- | Same as 'foldlM''
             Done       -> return z
 
 -- | Same as 'foldlM''
-foldM' :: Monad m => (a -> b -> m a) -> a -> Stream m b -> m a
+foldM' :: Monad m => (a -> b -> m a) -> a -> Stream m b -> m a
 {-# INLINE foldM' #-}
 foldM' = foldlM'
 
 {-# INLINE foldM' #-}
 foldM' = foldlM'
 
+vfoldlM' :: Monad m => (a -> b -> m a) -> (a -> v b -> m a) -> a -> Stream m v b -> m a
+{-# INLINE_STREAM vfoldlM' #-}
+vfoldlM' p q z (Stream _ (Unf step s) _) = vfoldlM'_loop SPEC z s
+  where
+    vfoldlM'_loop !sPEC z s
+      = z `seq` do
+          r <- step s
+          case r of
+            Yield (Left  x) s' -> do { z' <- p z x; vfoldlM'_loop SPEC z' s' }
+            Yield (Right v) s' -> do { z' <- q z v; vfoldlM'_loop SPEC z' s' }
+            Skip            s' -> vfoldlM'_loop SPEC z s'
+            Done               -> return z
+
 -- | Left fold over a non-empty 'Stream' with a strict accumulator
 -- | Left fold over a non-empty 'Stream' with a strict accumulator
-foldl1' :: Monad m => (a -> a -> a) -> Stream m a -> m a
+foldl1' :: Monad m => (a -> a -> a) -> Stream m a -> m a
 {-# INLINE foldl1' #-}
 foldl1' f = foldl1M' (\a b -> return (f a b))
 
 -- | Left fold over a non-empty 'Stream' with a strict accumulator and a
 -- monadic operator
 {-# INLINE foldl1' #-}
 foldl1' f = foldl1M' (\a b -> return (f a b))
 
 -- | Left fold over a non-empty 'Stream' with a strict accumulator and a
 -- monadic operator
-foldl1M' :: Monad m => (a -> a -> m a) -> Stream m a -> m a
+foldl1M' :: Monad m => (a -> a -> m a) -> Stream m a -> m a
 {-# INLINE_STREAM foldl1M' #-}
 {-# INLINE_STREAM foldl1M' #-}
-foldl1M' f (Stream step s sz) = foldl1M'_loop SPEC s
+foldl1M' f (Stream (Unf step s) _ sz) = foldl1M'_loop SPEC s
   where
     foldl1M'_loop !sPEC s
       = do
           r <- step s
           case r of
   where
     foldl1M'_loop !sPEC s
       = do
           r <- step s
           case r of
-            Yield x s' -> foldlM' f x (Stream step s' (sz - 1))
+            Yield x s' -> foldlM' f x (simple step s' (sz - 1))
             Skip    s' -> foldl1M'_loop SPEC s'
             Done       -> EMPTY_STREAM "foldl1M'"
 
 -- | Same as 'foldl1M''
             Skip    s' -> foldl1M'_loop SPEC s'
             Done       -> EMPTY_STREAM "foldl1M'"
 
 -- | Same as 'foldl1M''
-fold1M' :: Monad m => (a -> a -> m a) -> Stream m a -> m a
+fold1M' :: Monad m => (a -> a -> m a) -> Stream m a -> m a
 {-# INLINE fold1M' #-}
 fold1M' = foldl1M'
 
 -- | Right fold
 {-# INLINE fold1M' #-}
 fold1M' = foldl1M'
 
 -- | Right fold
-foldr :: Monad m => (a -> b -> b) -> b -> Stream m a -> m b
+foldr :: Monad m => (a -> b -> b) -> b -> Stream m a -> m b
 {-# INLINE foldr #-}
 foldr f = foldrM (\a b -> return (f a b))
 
 -- | Right fold with a monadic operator
 {-# INLINE foldr #-}
 foldr f = foldrM (\a b -> return (f a b))
 
 -- | Right fold with a monadic operator
-foldrM :: Monad m => (a -> b -> m b) -> b -> Stream m a -> m b
+foldrM :: Monad m => (a -> b -> m b) -> b -> Stream m a -> m b
 {-# INLINE_STREAM foldrM #-}
 {-# INLINE_STREAM foldrM #-}
-foldrM f z (Stream step s _) = foldrM_loop SPEC s
+foldrM f z (Stream (Unf step s) _ _) = foldrM_loop SPEC s
   where
     foldrM_loop !sPEC s
       = do
   where
     foldrM_loop !sPEC s
       = do
@@ -876,14 +945,14 @@ foldrM f z (Stream step s _) = foldrM_loop SPEC s
             Done       -> return z
 
 -- | Right fold over a non-empty stream
             Done       -> return z
 
 -- | Right fold over a non-empty stream
-foldr1 :: Monad m => (a -> a -> a) -> Stream m a -> m a
+foldr1 :: Monad m => (a -> a -> a) -> Stream m a -> m a
 {-# INLINE foldr1 #-}
 foldr1 f = foldr1M (\a b -> return (f a b))
 
 -- | Right fold over a non-empty stream with a monadic operator
 {-# INLINE foldr1 #-}
 foldr1 f = foldr1M (\a b -> return (f a b))
 
 -- | Right fold over a non-empty stream with a monadic operator
-foldr1M :: Monad m => (a -> a -> m a) -> Stream m a -> m a
+foldr1M :: Monad m => (a -> a -> m a) -> Stream m a -> m a
 {-# INLINE_STREAM foldr1M #-}
 {-# INLINE_STREAM foldr1M #-}
-foldr1M f (Stream step s _) = foldr1M_loop0 SPEC s
+foldr1M f (Stream (Unf step s) _ _) = foldr1M_loop0 SPEC s
   where
     foldr1M_loop0 !sPEC s
       = do
   where
     foldr1M_loop0 !sPEC s
       = do
@@ -904,9 +973,9 @@ foldr1M f (Stream step s _) = foldr1M_loop0 SPEC s
 -- Specialised folds
 -- -----------------
 
 -- Specialised folds
 -- -----------------
 
-and :: Monad m => Stream m Bool -> m Bool
+and :: Monad m => Stream m Bool -> m Bool
 {-# INLINE_STREAM and #-}
 {-# INLINE_STREAM and #-}
-and (Stream step s _) = and_loop SPEC s
+and (Stream (Unf step s) _ _) = and_loop SPEC s
   where
     and_loop !sPEC s
       = do
   where
     and_loop !sPEC s
       = do
@@ -917,9 +986,9 @@ and (Stream step s _) = and_loop SPEC s
             Skip        s' -> and_loop SPEC s'
             Done           -> return True
 
             Skip        s' -> and_loop SPEC s'
             Done           -> return True
 
-or :: Monad m => Stream m Bool -> m Bool
+or :: Monad m => Stream m Bool -> m Bool
 {-# INLINE_STREAM or #-}
 {-# INLINE_STREAM or #-}
-or (Stream step s _) = or_loop SPEC s
+or (Stream (Unf step s) _ _) = or_loop SPEC s
   where
     or_loop !sPEC s
       = do
   where
     or_loop !sPEC s
       = do
@@ -930,13 +999,13 @@ or (Stream step s _) = or_loop SPEC s
             Skip        s' -> or_loop SPEC s'
             Done           -> return False
 
             Skip        s' -> or_loop SPEC s'
             Done           -> return False
 
-concatMap :: Monad m => (a -> Stream m b) -> Stream m a -> Stream m b
+concatMap :: Monad m => (a -> Stream m v b) -> Stream m v a -> Stream m v b
 {-# INLINE concatMap #-}
 concatMap f = concatMapM (return . f)
 
 {-# INLINE concatMap #-}
 concatMap f = concatMapM (return . f)
 
-concatMapM :: Monad m => (a -> m (Stream m b)) -> Stream m a -> Stream m b
+concatMapM :: Monad m => (a -> m (Stream m v b)) -> Stream m v a -> Stream m v b
 {-# INLINE_STREAM concatMapM #-}
 {-# INLINE_STREAM concatMapM #-}
-concatMapM f (Stream step s _) = Stream concatMap_go (Left s) Unknown
+concatMapM f (Stream (Unf step s) _ _) = simple concatMap_go (Left s) Unknown
   where
     concatMap_go (Left s) = do
         r <- step s
   where
     concatMap_go (Left s) = do
         r <- step s
@@ -946,18 +1015,18 @@ concatMapM f (Stream step s _) = Stream concatMap_go (Left s) Unknown
                 return $ Skip (Right (b_stream, s'))
             Skip    s' -> return $ Skip (Left s')
             Done       -> return Done
                 return $ Skip (Right (b_stream, s'))
             Skip    s' -> return $ Skip (Left s')
             Done       -> return Done
-    concatMap_go (Right (Stream inner_step inner_s sz, s)) = do
+    concatMap_go (Right (Stream (Unf inner_step inner_s) _ sz, s)) = do
         r <- inner_step inner_s
         case r of
         r <- inner_step inner_s
         case r of
-            Yield b inner_s' -> return $ Yield b (Right (Stream inner_step inner_s' sz, s))
-            Skip    inner_s' -> return $ Skip (Right (Stream inner_step inner_s' sz, s))
+            Yield b inner_s' -> return $ Yield b (Right (simple inner_step inner_s' sz, s))
+            Skip    inner_s' -> return $ Skip (Right (simple inner_step inner_s' sz, s))
             Done             -> return $ Skip (Left s)
 
 -- | Create a 'Stream' of values from a 'Stream' of streamable things
 flatten :: Monad m => (a -> m s) -> (s -> m (Step s b)) -> Size
             Done             -> return $ Skip (Left s)
 
 -- | Create a 'Stream' of values from a 'Stream' of streamable things
 flatten :: Monad m => (a -> m s) -> (s -> m (Step s b)) -> Size
-                   -> Stream m a -> Stream m b
+                   -> Stream m v a -> Stream m v b
 {-# INLINE_STREAM flatten #-}
 {-# INLINE_STREAM flatten #-}
-flatten mk istep sz (Stream ostep t _) = Stream step (Left t) sz
+flatten mk istep sz (Stream (Unf ostep t) _ _) = simple step (Left t) sz
   where
     {-# INLINE_INNER step #-}
     step (Left t) = do
   where
     {-# INLINE_INNER step #-}
     step (Left t) = do
@@ -981,14 +1050,14 @@ flatten mk istep sz (Stream ostep t _) = Stream step (Left t) sz
 -- ---------
 
 -- | Unfold
 -- ---------
 
 -- | Unfold
-unfoldr :: Monad m => (s -> Maybe (a, s)) -> s -> Stream m a
+unfoldr :: Monad m => (s -> Maybe (a, s)) -> s -> Stream m a
 {-# INLINE_STREAM unfoldr #-}
 unfoldr f = unfoldrM (return . f)
 
 -- | Unfold with a monadic function
 {-# INLINE_STREAM unfoldr #-}
 unfoldr f = unfoldrM (return . f)
 
 -- | Unfold with a monadic function
-unfoldrM :: Monad m => (s -> m (Maybe (a, s))) -> s -> Stream m a
+unfoldrM :: Monad m => (s -> m (Maybe (a, s))) -> s -> Stream m a
 {-# INLINE_STREAM unfoldrM #-}
 {-# INLINE_STREAM unfoldrM #-}
-unfoldrM f s = Stream step s Unknown
+unfoldrM f s = simple step s Unknown
   where
     {-# INLINE_INNER step #-}
     step s = liftM (\r ->
   where
     {-# INLINE_INNER step #-}
     step s = liftM (\r ->
@@ -998,14 +1067,14 @@ unfoldrM f s = Stream step s Unknown
              ) (f s)
 
 -- | Unfold at most @n@ elements
              ) (f s)
 
 -- | Unfold at most @n@ elements
-unfoldrN :: Monad m => Int -> (s -> Maybe (a, s)) -> s -> Stream m a
+unfoldrN :: Monad m => Int -> (s -> Maybe (a, s)) -> s -> Stream m a
 {-# INLINE_STREAM unfoldrN #-}
 unfoldrN n f = unfoldrNM n (return . f)
 
 -- | Unfold at most @n@ elements with a monadic functions
 {-# INLINE_STREAM unfoldrN #-}
 unfoldrN n f = unfoldrNM n (return . f)
 
 -- | Unfold at most @n@ elements with a monadic functions
-unfoldrNM :: Monad m => Int -> (s -> m (Maybe (a, s))) -> s -> Stream m a
+unfoldrNM :: Monad m => Int -> (s -> m (Maybe (a, s))) -> s -> Stream m a
 {-# INLINE_STREAM unfoldrNM #-}
 {-# INLINE_STREAM unfoldrNM #-}
-unfoldrNM n f s = Stream step (s,n) (Max (delay_inline max n 0))
+unfoldrNM n f s = simple step (s,n) (Max (delay_inline max n 0))
   where
     {-# INLINE_INNER step #-}
     step (s,n) | n <= 0    = return Done
   where
     {-# INLINE_INNER step #-}
     step (s,n) | n <= 0    = return Done
@@ -1016,9 +1085,9 @@ unfoldrNM n f s = Stream step (s,n) (Max (delay_inline max n 0))
                              ) (f s)
 
 -- | Apply monadic function n times to value. Zeroth element is original value.
                              ) (f s)
 
 -- | Apply monadic function n times to value. Zeroth element is original value.
-iterateNM :: Monad m => Int -> (a -> m a) -> a -> Stream m a
+iterateNM :: Monad m => Int -> (a -> m a) -> a -> Stream m a
 {-# INLINE_STREAM iterateNM #-}
 {-# INLINE_STREAM iterateNM #-}
-iterateNM n f x0 = Stream step (x0,n) (Exact (delay_inline max n 0))
+iterateNM n f x0 = simple step (x0,n) (Exact (delay_inline max n 0))
   where
     {-# INLINE_INNER step #-}
     step (x,i) | i <= 0    = return Done
   where
     {-# INLINE_INNER step #-}
     step (x,i) | i <= 0    = return Done
@@ -1027,7 +1096,7 @@ iterateNM n f x0 = Stream step (x0,n) (Exact (delay_inline max n 0))
                                 return $ Yield a (a,i-1)
 
 -- | Apply function n times to value. Zeroth element is original value.
                                 return $ Yield a (a,i-1)
 
 -- | Apply function n times to value. Zeroth element is original value.
-iterateN :: Monad m => Int -> (a -> a) -> a -> Stream m a
+iterateN :: Monad m => Int -> (a -> a) -> a -> Stream m a
 {-# INLINE_STREAM iterateN #-}
 iterateN n f x0 = iterateNM n (return . f) x0
 
 {-# INLINE_STREAM iterateN #-}
 iterateN n f x0 = iterateNM n (return . f) x0
 
@@ -1035,14 +1104,14 @@ iterateN n f x0 = iterateNM n (return . f) x0
 -- -----
 
 -- | Prefix scan
 -- -----
 
 -- | Prefix scan
-prescanl :: Monad m => (a -> b -> a) -> a -> Stream m b -> Stream m a
+prescanl :: Monad m => (a -> b -> a) -> a -> Stream m v b -> Stream m v a
 {-# INLINE prescanl #-}
 prescanl f = prescanlM (\a b -> return (f a b))
 
 -- | Prefix scan with a monadic operator
 {-# INLINE prescanl #-}
 prescanl f = prescanlM (\a b -> return (f a b))
 
 -- | Prefix scan with a monadic operator
-prescanlM :: Monad m => (a -> b -> m a) -> a -> Stream m b -> Stream m a
+prescanlM :: Monad m => (a -> b -> m a) -> a -> Stream m v b -> Stream m v a
 {-# INLINE_STREAM prescanlM #-}
 {-# INLINE_STREAM prescanlM #-}
-prescanlM f z (Stream step s sz) = Stream step' (s,z) sz
+prescanlM f z (Stream (Unf step s) _ sz) = simple step' (s,z) sz
   where
     {-# INLINE_INNER step' #-}
     step' (s,x) = do
   where
     {-# INLINE_INNER step' #-}
     step' (s,x) = do
@@ -1055,14 +1124,14 @@ prescanlM f z (Stream step s sz) = Stream step' (s,z) sz
                       Done       -> return Done
 
 -- | Prefix scan with strict accumulator
                       Done       -> return Done
 
 -- | Prefix scan with strict accumulator
-prescanl' :: Monad m => (a -> b -> a) -> a -> Stream m b -> Stream m a
+prescanl' :: Monad m => (a -> b -> a) -> a -> Stream m v b -> Stream m v a
 {-# INLINE prescanl' #-}
 prescanl' f = prescanlM' (\a b -> return (f a b))
 
 -- | Prefix scan with strict accumulator and a monadic operator
 {-# INLINE prescanl' #-}
 prescanl' f = prescanlM' (\a b -> return (f a b))
 
 -- | Prefix scan with strict accumulator and a monadic operator
-prescanlM' :: Monad m => (a -> b -> m a) -> a -> Stream m b -> Stream m a
+prescanlM' :: Monad m => (a -> b -> m a) -> a -> Stream m v b -> Stream m v a
 {-# INLINE_STREAM prescanlM' #-}
 {-# INLINE_STREAM prescanlM' #-}
-prescanlM' f z (Stream step s sz) = Stream step' (s,z) sz
+prescanlM' f z (Stream (Unf step s) _ sz) = simple step' (s,z) sz
   where
     {-# INLINE_INNER step' #-}
     step' (s,x) = x `seq`
   where
     {-# INLINE_INNER step' #-}
     step' (s,x) = x `seq`
@@ -1076,14 +1145,14 @@ prescanlM' f z (Stream step s sz) = Stream step' (s,z) sz
                       Done       -> return Done
 
 -- | Suffix scan
                       Done       -> return Done
 
 -- | Suffix scan
-postscanl :: Monad m => (a -> b -> a) -> a -> Stream m b -> Stream m a
+postscanl :: Monad m => (a -> b -> a) -> a -> Stream m v b -> Stream m v a
 {-# INLINE postscanl #-}
 postscanl f = postscanlM (\a b -> return (f a b))
 
 -- | Suffix scan with a monadic operator
 {-# INLINE postscanl #-}
 postscanl f = postscanlM (\a b -> return (f a b))
 
 -- | Suffix scan with a monadic operator
-postscanlM :: Monad m => (a -> b -> m a) -> a -> Stream m b -> Stream m a
+postscanlM :: Monad m => (a -> b -> m a) -> a -> Stream m v b -> Stream m v a
 {-# INLINE_STREAM postscanlM #-}
 {-# INLINE_STREAM postscanlM #-}
-postscanlM f z (Stream step s sz) = Stream step' (s,z) sz
+postscanlM f z (Stream (Unf step s) _ sz) = simple step' (s,z) sz
   where
     {-# INLINE_INNER step' #-}
     step' (s,x) = do
   where
     {-# INLINE_INNER step' #-}
     step' (s,x) = do
@@ -1096,14 +1165,14 @@ postscanlM f z (Stream step s sz) = Stream step' (s,z) sz
                       Done       -> return Done
 
 -- | Suffix scan with strict accumulator
                       Done       -> return Done
 
 -- | Suffix scan with strict accumulator
-postscanl' :: Monad m => (a -> b -> a) -> a -> Stream m b -> Stream m a
+postscanl' :: Monad m => (a -> b -> a) -> a -> Stream m v b -> Stream m v a
 {-# INLINE postscanl' #-}
 postscanl' f = postscanlM' (\a b -> return (f a b))
 
 -- | Suffix scan with strict acccumulator and a monadic operator
 {-# INLINE postscanl' #-}
 postscanl' f = postscanlM' (\a b -> return (f a b))
 
 -- | Suffix scan with strict acccumulator and a monadic operator
-postscanlM' :: Monad m => (a -> b -> m a) -> a -> Stream m b -> Stream m a
+postscanlM' :: Monad m => (a -> b -> m a) -> a -> Stream m v b -> Stream m v a
 {-# INLINE_STREAM postscanlM' #-}
 {-# INLINE_STREAM postscanlM' #-}
-postscanlM' f z (Stream step s sz) = z `seq` Stream step' (s,z) sz
+postscanlM' f z (Stream (Unf step s) _ sz) = z `seq` simple step' (s,z) sz
   where
     {-# INLINE_INNER step' #-}
     step' (s,x) = x `seq`
   where
     {-# INLINE_INNER step' #-}
     step' (s,x) = x `seq`
@@ -1117,34 +1186,34 @@ postscanlM' f z (Stream step s sz) = z `seq` Stream step' (s,z) sz
                       Done       -> return Done
 
 -- | Haskell-style scan
                       Done       -> return Done
 
 -- | Haskell-style scan
-scanl :: Monad m => (a -> b -> a) -> a -> Stream m b -> Stream m a
+scanl :: Monad m => (a -> b -> a) -> a -> Stream m v b -> Stream m v a
 {-# INLINE scanl #-}
 scanl f = scanlM (\a b -> return (f a b))
 
 -- | Haskell-style scan with a monadic operator
 {-# INLINE scanl #-}
 scanl f = scanlM (\a b -> return (f a b))
 
 -- | Haskell-style scan with a monadic operator
-scanlM :: Monad m => (a -> b -> m a) -> a -> Stream m b -> Stream m a
+scanlM :: Monad m => (a -> b -> m a) -> a -> Stream m v b -> Stream m v a
 {-# INLINE scanlM #-}
 scanlM f z s = z `cons` postscanlM f z s
 
 -- | Haskell-style scan with strict accumulator
 {-# INLINE scanlM #-}
 scanlM f z s = z `cons` postscanlM f z s
 
 -- | Haskell-style scan with strict accumulator
-scanl' :: Monad m => (a -> b -> a) -> a -> Stream m b -> Stream m a
+scanl' :: Monad m => (a -> b -> a) -> a -> Stream m v b -> Stream m v a
 {-# INLINE scanl' #-}
 scanl' f = scanlM' (\a b -> return (f a b))
 
 -- | Haskell-style scan with strict accumulator and a monadic operator
 {-# INLINE scanl' #-}
 scanl' f = scanlM' (\a b -> return (f a b))
 
 -- | Haskell-style scan with strict accumulator and a monadic operator
-scanlM' :: Monad m => (a -> b -> m a) -> a -> Stream m b -> Stream m a
+scanlM' :: Monad m => (a -> b -> m a) -> a -> Stream m v b -> Stream m v a
 {-# INLINE scanlM' #-}
 scanlM' f z s = z `seq` (z `cons` postscanlM f z s)
 
 -- | Scan over a non-empty 'Stream'
 {-# INLINE scanlM' #-}
 scanlM' f z s = z `seq` (z `cons` postscanlM f z s)
 
 -- | Scan over a non-empty 'Stream'
-scanl1 :: Monad m => (a -> a -> a) -> Stream m a -> Stream m a
+scanl1 :: Monad m => (a -> a -> a) -> Stream m v a -> Stream m v a
 {-# INLINE scanl1 #-}
 scanl1 f = scanl1M (\x y -> return (f x y))
 
 -- | Scan over a non-empty 'Stream' with a monadic operator
 {-# INLINE scanl1 #-}
 scanl1 f = scanl1M (\x y -> return (f x y))
 
 -- | Scan over a non-empty 'Stream' with a monadic operator
-scanl1M :: Monad m => (a -> a -> m a) -> Stream m a -> Stream m a
+scanl1M :: Monad m => (a -> a -> m a) -> Stream m v a -> Stream m v a
 {-# INLINE_STREAM scanl1M #-}
 {-# INLINE_STREAM scanl1M #-}
-scanl1M f (Stream step s sz) = Stream step' (s, Nothing) sz
+scanl1M f (Stream (Unf step s) _ sz) = simple step' (s, Nothing) sz
   where
     {-# INLINE_INNER step' #-}
     step' (s, Nothing) = do
   where
     {-# INLINE_INNER step' #-}
     step' (s, Nothing) = do
@@ -1164,15 +1233,15 @@ scanl1M f (Stream step s sz) = Stream step' (s, Nothing) sz
                             Done       -> return Done
 
 -- | Scan over a non-empty 'Stream' with a strict accumulator
                             Done       -> return Done
 
 -- | Scan over a non-empty 'Stream' with a strict accumulator
-scanl1' :: Monad m => (a -> a -> a) -> Stream m a -> Stream m a
+scanl1' :: Monad m => (a -> a -> a) -> Stream m v a -> Stream m v a
 {-# INLINE scanl1' #-}
 scanl1' f = scanl1M' (\x y -> return (f x y))
 
 -- | Scan over a non-empty 'Stream' with a strict accumulator and a monadic
 -- operator
 {-# INLINE scanl1' #-}
 scanl1' f = scanl1M' (\x y -> return (f x y))
 
 -- | Scan over a non-empty 'Stream' with a strict accumulator and a monadic
 -- operator
-scanl1M' :: Monad m => (a -> a -> m a) -> Stream m a -> Stream m a
+scanl1M' :: Monad m => (a -> a -> m a) -> Stream m v a -> Stream m v a
 {-# INLINE_STREAM scanl1M' #-}
 {-# INLINE_STREAM scanl1M' #-}
-scanl1M' f (Stream step s sz) = Stream step' (s, Nothing) sz
+scanl1M' f (Stream (Unf step s) _ sz) = simple step' (s, Nothing) sz
   where
     {-# INLINE_INNER step' #-}
     step' (s, Nothing) = do
   where
     {-# INLINE_INNER step' #-}
     step' (s, Nothing) = do
@@ -1201,10 +1270,10 @@ scanl1M' f (Stream step s sz) = Stream step' (s, Nothing) sz
 
 -- | Yield a 'Stream' of the given length containing the values @x@, @x+y@,
 -- @x+y+y@ etc.
 
 -- | Yield a 'Stream' of the given length containing the values @x@, @x+y@,
 -- @x+y+y@ etc.
-enumFromStepN :: (Num a, Monad m) => a -> a -> Int -> Stream m a
+enumFromStepN :: (Num a, Monad m) => a -> a -> Int -> Stream m a
 {-# INLINE_STREAM enumFromStepN #-}
 enumFromStepN x y n = x `seq` y `seq` n `seq`
 {-# INLINE_STREAM enumFromStepN #-}
 enumFromStepN x y n = x `seq` y `seq` n `seq`
-                      Stream step (x,n) (Exact (delay_inline max n 0))
+                      simple step (x,n) (Exact (delay_inline max n 0))
   where
     {-# INLINE_INNER step #-}
     step (x,n) | n > 0     = return $ Yield x (x+y,n-1)
   where
     {-# INLINE_INNER step #-}
     step (x,n) | n > 0     = return $ Yield x (x+y,n-1)
@@ -1214,7 +1283,7 @@ enumFromStepN x y n = x `seq` y `seq` n `seq`
 --
 -- /WARNING:/ This operation can be very inefficient. If at all possible, use
 -- 'enumFromStepN' instead.
 --
 -- /WARNING:/ This operation can be very inefficient. If at all possible, use
 -- 'enumFromStepN' instead.
-enumFromTo :: (Enum a, Monad m) => a -> a -> Stream m a
+enumFromTo :: (Enum a, Monad m) => a -> a -> Stream m a
 {-# INLINE_STREAM enumFromTo #-}
 enumFromTo x y = fromList [x .. y]
 
 {-# INLINE_STREAM enumFromTo #-}
 enumFromTo x y = fromList [x .. y]
 
@@ -1222,9 +1291,9 @@ enumFromTo x y = fromList [x .. y]
 -- overflow which can't happen here.
 
 -- FIXME: add "too large" test for Int
 -- overflow which can't happen here.
 
 -- FIXME: add "too large" test for Int
-enumFromTo_small :: (Integral a, Monad m) => a -> a -> Stream m a
+enumFromTo_small :: (Integral a, Monad m) => a -> a -> Stream m a
 {-# INLINE_STREAM enumFromTo_small #-}
 {-# INLINE_STREAM enumFromTo_small #-}
-enumFromTo_small x y = x `seq` y `seq` Stream step x (Exact n)
+enumFromTo_small x y = x `seq` y `seq` simple step x (Exact n)
   where
     n = delay_inline max (fromIntegral y - fromIntegral x + 1) 0
 
   where
     n = delay_inline max (fromIntegral y - fromIntegral x + 1) 0
 
@@ -1235,16 +1304,16 @@ enumFromTo_small x y = x `seq` y `seq` Stream step x (Exact n)
 {-# RULES
 
 "enumFromTo<Int8> [Stream]"
 {-# RULES
 
 "enumFromTo<Int8> [Stream]"
-  enumFromTo = enumFromTo_small :: Monad m => Int8 -> Int8 -> Stream m Int8
+  enumFromTo = enumFromTo_small :: Monad m => Int8 -> Int8 -> Stream m Int8
 
 "enumFromTo<Int16> [Stream]"
 
 "enumFromTo<Int16> [Stream]"
-  enumFromTo = enumFromTo_small :: Monad m => Int16 -> Int16 -> Stream m Int16
+  enumFromTo = enumFromTo_small :: Monad m => Int16 -> Int16 -> Stream m Int16
 
 "enumFromTo<Word8> [Stream]"
 
 "enumFromTo<Word8> [Stream]"
-  enumFromTo = enumFromTo_small :: Monad m => Word8 -> Word8 -> Stream m Word8
+  enumFromTo = enumFromTo_small :: Monad m => Word8 -> Word8 -> Stream m Word8
 
 "enumFromTo<Word16> [Stream]"
 
 "enumFromTo<Word16> [Stream]"
-  enumFromTo = enumFromTo_small :: Monad m => Word16 -> Word16 -> Stream m Word16
+  enumFromTo = enumFromTo_small :: Monad m => Word16 -> Word16 -> Stream m Word16
 
   #-}
 
 
   #-}
 
@@ -1253,10 +1322,10 @@ enumFromTo_small x y = x `seq` y `seq` Stream step x (Exact n)
 {-# RULES
 
 "enumFromTo<Int32> [Stream]"
 {-# RULES
 
 "enumFromTo<Int32> [Stream]"
-  enumFromTo = enumFromTo_small :: Monad m => Int32 -> Int32 -> Stream m Int32
+  enumFromTo = enumFromTo_small :: Monad m => Int32 -> Int32 -> Stream m Int32
 
 "enumFromTo<Word32> [Stream]"
 
 "enumFromTo<Word32> [Stream]"
-  enumFromTo = enumFromTo_small :: Monad m => Word32 -> Word32 -> Stream m Word32
+  enumFromTo = enumFromTo_small :: Monad m => Word32 -> Word32 -> Stream m Word32
 
   #-}
 
 
   #-}
 
@@ -1274,9 +1343,9 @@ enumFromTo_small x y = x `seq` y `seq` Stream step x (Exact n)
 -- unsigned types). See http://hackage.haskell.org/trac/ghc/ticket/3744
 --
 
 -- unsigned types). See http://hackage.haskell.org/trac/ghc/ticket/3744
 --
 
-enumFromTo_int :: (Integral a, Monad m) => a -> a -> Stream m a
+enumFromTo_int :: (Integral a, Monad m) => a -> a -> Stream m a
 {-# INLINE_STREAM enumFromTo_int #-}
 {-# INLINE_STREAM enumFromTo_int #-}
-enumFromTo_int x y = x `seq` y `seq` Stream step x (Exact (len x y))
+enumFromTo_int x y = x `seq` y `seq` simple step x (Exact (len x y))
   where
     {-# INLINE [0] len #-}
     len x y | x > y     = 0
   where
     {-# INLINE [0] len #-}
     len x y | x > y     = 0
@@ -1293,25 +1362,25 @@ enumFromTo_int x y = x `seq` y `seq` Stream step x (Exact (len x y))
 {-# RULES
 
 "enumFromTo<Int> [Stream]"
 {-# RULES
 
 "enumFromTo<Int> [Stream]"
-  enumFromTo = enumFromTo_int :: Monad m => Int -> Int -> Stream m Int
+  enumFromTo = enumFromTo_int :: Monad m => Int -> Int -> Stream m Int
 
 #if WORD_SIZE_IN_BITS > 32
 
 "enumFromTo<Int64> [Stream]"
 
 #if WORD_SIZE_IN_BITS > 32
 
 "enumFromTo<Int64> [Stream]"
-  enumFromTo = enumFromTo_int :: Monad m => Int64 -> Int64 -> Stream m Int64
+  enumFromTo = enumFromTo_int :: Monad m => Int64 -> Int64 -> Stream m Int64
 
 #else
 
 "enumFromTo<Int32> [Stream]"
 
 #else
 
 "enumFromTo<Int32> [Stream]"
-  enumFromTo = enumFromTo_int :: Monad m => Int32 -> Int32 -> Stream m Int32
+  enumFromTo = enumFromTo_int :: Monad m => Int32 -> Int32 -> Stream m Int32
 
 #endif
 
   #-}
 
 
 #endif
 
   #-}
 
-enumFromTo_big_word :: (Integral a, Monad m) => a -> a -> Stream m a
+enumFromTo_big_word :: (Integral a, Monad m) => a -> a -> Stream m a
 {-# INLINE_STREAM enumFromTo_big_word #-}
 {-# INLINE_STREAM enumFromTo_big_word #-}
-enumFromTo_big_word x y = x `seq` y `seq` Stream step x (Exact (len x y))
+enumFromTo_big_word x y = x `seq` y `seq` simple step x (Exact (len x y))
   where
     {-# INLINE [0] len #-}
     len x y | x > y     = 0
   where
     {-# INLINE [0] len #-}
     len x y | x > y     = 0
@@ -1328,30 +1397,30 @@ enumFromTo_big_word x y = x `seq` y `seq` Stream step x (Exact (len x y))
 {-# RULES
 
 "enumFromTo<Word> [Stream]"
 {-# RULES
 
 "enumFromTo<Word> [Stream]"
-  enumFromTo = enumFromTo_big_word :: Monad m => Word -> Word -> Stream m Word
+  enumFromTo = enumFromTo_big_word :: Monad m => Word -> Word -> Stream m Word
 
 "enumFromTo<Word64> [Stream]"
   enumFromTo = enumFromTo_big_word
 
 "enumFromTo<Word64> [Stream]"
   enumFromTo = enumFromTo_big_word
-                        :: Monad m => Word64 -> Word64 -> Stream m Word64
+                        :: Monad m => Word64 -> Word64 -> Stream m Word64
 
 #if WORD_SIZE_IN_BITS == 32
 
 "enumFromTo<Word32> [Stream]"
   enumFromTo = enumFromTo_big_word
 
 #if WORD_SIZE_IN_BITS == 32
 
 "enumFromTo<Word32> [Stream]"
   enumFromTo = enumFromTo_big_word
-                        :: Monad m => Word32 -> Word32 -> Stream m Word32
+                        :: Monad m => Word32 -> Word32 -> Stream m Word32
 
 #endif
 
 "enumFromTo<Integer> [Stream]"
   enumFromTo = enumFromTo_big_word
 
 #endif
 
 "enumFromTo<Integer> [Stream]"
   enumFromTo = enumFromTo_big_word
-                        :: Monad m => Integer -> Integer -> Stream m Integer
+                        :: Monad m => Integer -> Integer -> Stream m Integer
 
   #-}
 
 -- FIXME: the "too large" test is totally wrong
 
   #-}
 
 -- FIXME: the "too large" test is totally wrong
-enumFromTo_big_int :: (Integral a, Monad m) => a -> a -> Stream m a
+enumFromTo_big_int :: (Integral a, Monad m) => a -> a -> Stream m a
 {-# INLINE_STREAM enumFromTo_big_int #-}
 {-# INLINE_STREAM enumFromTo_big_int #-}
-enumFromTo_big_int x y = x `seq` y `seq` Stream step x (Exact (len x y))
+enumFromTo_big_int x y = x `seq` y `seq` simple step x (Exact (len x y))
   where
     {-# INLINE [0] len #-}
     len x y | x > y     = 0
   where
     {-# INLINE [0] len #-}
     len x y | x > y     = 0
@@ -1370,15 +1439,15 @@ enumFromTo_big_int x y = x `seq` y `seq` Stream step x (Exact (len x y))
 {-# RULES
 
 "enumFromTo<Int64> [Stream]"
 {-# RULES
 
 "enumFromTo<Int64> [Stream]"
-  enumFromTo = enumFromTo_big :: Monad m => Int64 -> Int64 -> Stream m Int64
+  enumFromTo = enumFromTo_big :: Monad m => Int64 -> Int64 -> Stream m Int64
 
   #-}
 
 #endif
 
 
   #-}
 
 #endif
 
-enumFromTo_char :: Monad m => Char -> Char -> Stream m Char
+enumFromTo_char :: Monad m => Char -> Char -> Stream m Char
 {-# INLINE_STREAM enumFromTo_char #-}
 {-# INLINE_STREAM enumFromTo_char #-}
-enumFromTo_char x y = x `seq` y `seq` Stream step xn (Exact n)
+enumFromTo_char x y = x `seq` y `seq` simple step xn (Exact n)
   where
     xn = ord x
     yn = ord y
   where
     xn = ord x
     yn = ord y
@@ -1401,9 +1470,9 @@ enumFromTo_char x y = x `seq` y `seq` Stream step xn (Exact n)
 -- Specialise enumFromTo for Float and Double.
 -- Also, try to do something about pairs?
 
 -- Specialise enumFromTo for Float and Double.
 -- Also, try to do something about pairs?
 
-enumFromTo_double :: (Monad m, Ord a, RealFrac a) => a -> a -> Stream m a
+enumFromTo_double :: (Monad m, Ord a, RealFrac a) => a -> a -> Stream m a
 {-# INLINE_STREAM enumFromTo_double #-}
 {-# INLINE_STREAM enumFromTo_double #-}
-enumFromTo_double n m = n `seq` m `seq` Stream step n (Max (len n m))
+enumFromTo_double n m = n `seq` m `seq` simple step n (Max (len n m))
   where
     lim = m + 1/2 -- important to float out
 
   where
     lim = m + 1/2 -- important to float out
 
@@ -1422,10 +1491,10 @@ enumFromTo_double n m = n `seq` m `seq` Stream step n (Max (len n m))
 {-# RULES
 
 "enumFromTo<Double> [Stream]"
 {-# RULES
 
 "enumFromTo<Double> [Stream]"
-  enumFromTo = enumFromTo_double :: Monad m => Double -> Double -> Stream m Double
+  enumFromTo = enumFromTo_double :: Monad m => Double -> Double -> Stream m Double
 
 "enumFromTo<Float> [Stream]"
 
 "enumFromTo<Float> [Stream]"
-  enumFromTo = enumFromTo_double :: Monad m => Float -> Float -> Stream m Float
+  enumFromTo = enumFromTo_double :: Monad m => Float -> Float -> Stream m Float
 
   #-}
 
 
   #-}
 
@@ -1435,7 +1504,7 @@ enumFromTo_double n m = n `seq` m `seq` Stream step n (Max (len n m))
 --
 -- /WARNING:/ This operation is very inefficient. If at all possible, use
 -- 'enumFromStepN' instead.
 --
 -- /WARNING:/ This operation is very inefficient. If at all possible, use
 -- 'enumFromStepN' instead.
-enumFromThenTo :: (Enum a, Monad m) => a -> a -> a -> Stream m a
+enumFromThenTo :: (Enum a, Monad m) => a -> a -> a -> Stream m a
 {-# INLINE_STREAM enumFromThenTo #-}
 enumFromThenTo x y z = fromList [x, y .. z]
 
 {-# INLINE_STREAM enumFromThenTo #-}
 enumFromThenTo x y z = fromList [x, y .. z]
 
@@ -1445,19 +1514,19 @@ enumFromThenTo x y z = fromList [x, y .. z]
 -- -----------
 
 -- | Convert a 'Stream' to a list
 -- -----------
 
 -- | Convert a 'Stream' to a list
-toList :: Monad m => Stream m a -> m [a]
+toList :: Monad m => Stream m a -> m [a]
 {-# INLINE toList #-}
 toList = foldr (:) []
 
 -- | Convert a list to a 'Stream'
 {-# INLINE toList #-}
 toList = foldr (:) []
 
 -- | Convert a list to a 'Stream'
-fromList :: Monad m => [a] -> Stream m a
+fromList :: Monad m => [a] -> Stream m a
 {-# INLINE fromList #-}
 fromList xs = unsafeFromList Unknown xs
 
 -- | Convert the first @n@ elements of a list to a 'Stream'
 {-# INLINE fromList #-}
 fromList xs = unsafeFromList Unknown xs
 
 -- | Convert the first @n@ elements of a list to a 'Stream'
-fromListN :: Monad m => Int -> [a] -> Stream m a
+fromListN :: Monad m => Int -> [a] -> Stream m a
 {-# INLINE_STREAM fromListN #-}
 {-# INLINE_STREAM fromListN #-}
-fromListN n xs = Stream step (xs,n) (Max (delay_inline max n 0))
+fromListN n xs = simple step (xs,n) (Max (delay_inline max n 0))
   where
     {-# INLINE_INNER step #-}
     step (xs,n) | n <= 0 = return Done
   where
     {-# INLINE_INNER step #-}
     step (xs,n) | n <= 0 = return Done
@@ -1465,10 +1534,41 @@ fromListN n xs = Stream step (xs,n) (Max (delay_inline max n 0))
     step ([],n)          = return Done
 
 -- | Convert a list to a 'Stream' with the given 'Size' hint. 
     step ([],n)          = return Done
 
 -- | Convert a list to a 'Stream' with the given 'Size' hint. 
-unsafeFromList :: Monad m => Size -> [a] -> Stream m a
+unsafeFromList :: Monad m => Size -> [a] -> Stream m a
 {-# INLINE_STREAM unsafeFromList #-}
 {-# INLINE_STREAM unsafeFromList #-}
-unsafeFromList sz xs = Stream step xs sz
+unsafeFromList sz xs = simple step xs sz
   where
     step (x:xs) = return (Yield x xs)
     step []     = return Done
 
   where
     step (x:xs) = return (Yield x xs)
     step []     = return Done
 
+fromVector :: (Monad m, Vector v a) => v a -> Stream m v a
+{-# INLINE_STREAM fromVector #-}
+fromVector v = v `seq` n `seq` Stream (Unf step 0) (Unf vstep True) (Exact n)
+  where
+    n = basicLength v
+
+    {-# INLINE step #-}
+    step i | i >= n = return Done
+           | otherwise = case basicUnsafeIndexM v i of
+                           Box x -> return $ Yield x (i+1)
+
+    
+    {-# INLINE vstep #-}
+    vstep True  = return (Yield (Right v) False)
+    vstep False = return Done
+
+reVector :: Monad m => Stream m u a -> Stream m v a
+{-# INLINE_STREAM reVector #-}
+reVector (Stream (Unf step s) _ n) = simple step s n
+
+{-# RULES
+
+"reVector [Vector]"
+  reVector = id
+
+"reVector/reVector [Vector]" forall s.
+  reVector (reVector s) = s
+
+  #-}
+
+    
index b8f2e81..263c4e3 100644 (file)
@@ -780,7 +780,7 @@ update_ :: (Vector v a, Vector v Int)
 {-# INLINE update_ #-}
 update_ v is w = update_stream v (Stream.zipWith (,) (stream is) (stream w))
 
 {-# INLINE update_ #-}
 update_ v is w = update_stream v (Stream.zipWith (,) (stream is) (stream w))
 
-update_stream :: Vector v a => v a -> Stream (Int,a) -> v a
+update_stream :: Vector v a => v a -> Stream (Int,a) -> v a
 {-# INLINE update_stream #-}
 update_stream = modifyWithStream M.update
 
 {-# INLINE update_stream #-}
 update_stream = modifyWithStream M.update
 
@@ -800,7 +800,7 @@ unsafeUpdate_ :: (Vector v a, Vector v Int) => v a -> v Int -> v a -> v a
 unsafeUpdate_ v is w
   = unsafeUpdate_stream v (Stream.zipWith (,) (stream is) (stream w))
 
 unsafeUpdate_ v is w
   = unsafeUpdate_stream v (Stream.zipWith (,) (stream is) (stream w))
 
-unsafeUpdate_stream :: Vector v a => v a -> Stream (Int,a) -> v a
+unsafeUpdate_stream :: Vector v a => v a -> Stream (Int,a) -> v a
 {-# INLINE unsafeUpdate_stream #-}
 unsafeUpdate_stream = modifyWithStream M.unsafeUpdate
 
 {-# INLINE unsafeUpdate_stream #-}
 unsafeUpdate_stream = modifyWithStream M.unsafeUpdate
 
@@ -855,7 +855,7 @@ accumulate_ f v is xs = accum_stream f v (Stream.zipWith (,) (stream is)
                                                              (stream xs))
                                         
 
                                                              (stream xs))
                                         
 
-accum_stream :: Vector v a => (a -> b -> a) -> v a -> Stream (Int,b) -> v a
+accum_stream :: Vector v a => (a -> b -> a) -> v a -> Stream (Int,b) -> v a
 {-# INLINE accum_stream #-}
 accum_stream f = modifyWithStream (M.accum f)
 
 {-# INLINE accum_stream #-}
 accum_stream f = modifyWithStream (M.accum f)
 
@@ -878,7 +878,7 @@ unsafeAccumulate_ f v is xs
   = unsafeAccum_stream f v (Stream.zipWith (,) (stream is) (stream xs))
 
 unsafeAccum_stream
   = unsafeAccum_stream f v (Stream.zipWith (,) (stream is) (stream xs))
 
 unsafeAccum_stream
-  :: Vector v a => (a -> b -> a) -> v a -> Stream (Int,b) -> v a
+  :: Vector v a => (a -> b -> a) -> v a -> Stream (Int,b) -> v a
 {-# INLINE unsafeAccum_stream #-}
 unsafeAccum_stream f = modifyWithStream (M.unsafeAccum f)
 
 {-# INLINE unsafeAccum_stream #-}
 unsafeAccum_stream f = modifyWithStream (M.unsafeAccum f)
 
@@ -954,8 +954,8 @@ modify p = new . New.modify p . clone
 -- We have to make sure that this is strict in the stream but we can't seq on
 -- it while fusion is happening. Hence this ugliness.
 modifyWithStream :: Vector v a
 -- We have to make sure that this is strict in the stream but we can't seq on
 -- it while fusion is happening. Hence this ugliness.
 modifyWithStream :: Vector v a
-                 => (forall s. Mutable v s a -> Stream b -> ST s ())
-                 -> v a -> Stream b -> v a
+                 => (forall s. Mutable v s a -> Stream b -> ST s ())
+                 -> v a -> Stream b -> v a
 {-# INLINE modifyWithStream #-}
 modifyWithStream p v s = new (New.modifyWithStream p (clone v) s)
 
 {-# INLINE modifyWithStream #-}
 modifyWithStream p v s = new (New.modifyWithStream p (clone v) s)
 
@@ -1275,7 +1275,7 @@ partition f = partition_stream f . stream
 -- FIXME: Make this inplace-fusible (look at how stable_partition is
 -- implemented in C++)
 
 -- FIXME: Make this inplace-fusible (look at how stable_partition is
 -- implemented in C++)
 
-partition_stream :: Vector v a => (a -> Bool) -> Stream a -> (v a, v a)
+partition_stream :: Vector v a => (a -> Bool) -> Stream a -> (v a, v a)
 {-# INLINE_STREAM partition_stream #-}
 partition_stream f s = s `seq` runST (
   do
 {-# INLINE_STREAM partition_stream #-}
 partition_stream f s = s `seq` runST (
   do
@@ -1293,7 +1293,7 @@ unstablePartition :: Vector v a => (a -> Bool) -> v a -> (v a, v a)
 unstablePartition f = unstablePartition_stream f . stream
 
 unstablePartition_stream
 unstablePartition f = unstablePartition_stream f . stream
 
 unstablePartition_stream
-  :: Vector v a => (a -> Bool) -> Stream a -> (v a, v a)
+  :: Vector v a => (a -> Bool) -> Stream a -> (v a, v a)
 {-# INLINE_STREAM unstablePartition_stream #-}
 unstablePartition_stream f s = s `seq` runST (
   do
 {-# INLINE_STREAM unstablePartition_stream #-}
 unstablePartition_stream f s = s `seq` runST (
   do
@@ -1757,7 +1757,7 @@ fromListN n = unstream . Stream.fromListN n
 -- | /O(n)/ Convert different vector types
 convert :: (Vector v a, Vector w a) => v a -> w a
 {-# INLINE convert #-}
 -- | /O(n)/ Convert different vector types
 convert :: (Vector v a, Vector w a) => v a -> w a
 {-# INLINE convert #-}
-convert = unstream . stream
+convert = unstream . Stream.reVector . stream
 
 -- Conversions - Mutable vectors
 -- -----------------------------
 
 -- Conversions - Mutable vectors
 -- -----------------------------
@@ -1843,8 +1843,11 @@ unsafeCopy dst src = UNSAFE_CHECK(check) "unsafeCopy" "length mismatch"
 -- ---------------------------
 
 -- | /O(1)/ Convert a vector to a 'Stream'
 -- ---------------------------
 
 -- | /O(1)/ Convert a vector to a 'Stream'
-stream :: Vector v a => v a -> Stream a
+stream :: Vector v a => v a -> Stream a
 {-# INLINE_STREAM stream #-}
 {-# INLINE_STREAM stream #-}
+stream v = Stream.fromVector v
+
+{-
 stream v = v `seq` n `seq` (Stream.unfoldr get 0 `Stream.sized` Exact n)
   where
     n = length v
 stream v = v `seq` n `seq` (Stream.unfoldr get 0 `Stream.sized` Exact n)
   where
     n = length v
@@ -1854,9 +1857,10 @@ stream v = v `seq` n `seq` (Stream.unfoldr get 0 `Stream.sized` Exact n)
     {-# INLINE get #-}
     get i | i >= n    = Nothing
           | otherwise = case basicUnsafeIndexM v i of Box x -> Just (x, i+1)
     {-# INLINE get #-}
     get i | i >= n    = Nothing
           | otherwise = case basicUnsafeIndexM v i of Box x -> Just (x, i+1)
+-}
 
 -- | /O(n)/ Construct a vector from a 'Stream'
 
 -- | /O(n)/ Construct a vector from a 'Stream'
-unstream :: Vector v a => Stream a -> v a
+unstream :: Vector v a => Stream a -> v a
 {-# INLINE unstream #-}
 unstream s = new (New.unstream s)
 
 {-# INLINE unstream #-}
 unstream s = new (New.unstream s)
 
@@ -1872,17 +1876,17 @@ unstream s = new (New.unstream s)
   clone (new p) = p
 
 "inplace [Vector]"
   clone (new p) = p
 
 "inplace [Vector]"
-  forall (f :: forall m. Monad m => MStream m a -> MStream m a) m.
+  forall (f :: forall m. Monad m => MStream m u a -> MStream m u a) m.
   New.unstream (inplace f (stream (new m))) = New.transform f m
 
 "uninplace [Vector]"
   New.unstream (inplace f (stream (new m))) = New.transform f m
 
 "uninplace [Vector]"
-  forall (f :: forall m. Monad m => MStream m a -> MStream m a) m.
+  forall (f :: forall m. Monad m => MStream m u a -> MStream m u a) m.
   stream (new (New.transform f m)) = inplace f (stream (new m))
 
  #-}
 
 -- | /O(1)/ Convert a vector to a 'Stream', proceeding from right to left
   stream (new (New.transform f m)) = inplace f (stream (new m))
 
  #-}
 
 -- | /O(1)/ Convert a vector to a 'Stream', proceeding from right to left
-streamR :: Vector v a => v a -> Stream a
+streamR :: Vector v a => v a -> Stream a
 {-# INLINE_STREAM streamR #-}
 streamR v = v `seq` n `seq` (Stream.unfoldr get n `Stream.sized` Exact n)
   where
 {-# INLINE_STREAM streamR #-}
 streamR v = v `seq` n `seq` (Stream.unfoldr get n `Stream.sized` Exact n)
   where
@@ -1895,7 +1899,7 @@ streamR v = v `seq` n `seq` (Stream.unfoldr get n `Stream.sized` Exact n)
             case basicUnsafeIndexM v i' of Box x -> Just (x, i')
 
 -- | /O(n)/ Construct a vector from a 'Stream', proceeding from right to left
             case basicUnsafeIndexM v i' of Box x -> Just (x, i')
 
 -- | /O(n)/ Construct a vector from a 'Stream', proceeding from right to left
-unstreamR :: Vector v a => Stream a -> v a
+unstreamR :: Vector v a => Stream a -> v a
 {-# INLINE unstreamR #-}
 unstreamR s = new (New.unstreamR s)
 
 {-# INLINE unstreamR #-}
 unstreamR s = new (New.unstreamR s)
 
@@ -1914,31 +1918,31 @@ unstreamR s = new (New.unstreamR s)
   New.unstreamR (stream (new p)) = New.modify M.reverse p
 
 "inplace right [Vector]"
   New.unstreamR (stream (new p)) = New.modify M.reverse p
 
 "inplace right [Vector]"
-  forall (f :: forall m. Monad m => MStream m a -> MStream m a) m.
+  forall (f :: forall m. Monad m => MStream m u a -> MStream m u a) m.
   New.unstreamR (inplace f (streamR (new m))) = New.transformR f m
 
 "uninplace right [Vector]"
   New.unstreamR (inplace f (streamR (new m))) = New.transformR f m
 
 "uninplace right [Vector]"
-  forall (f :: forall m. Monad m => MStream m a -> MStream m a) m.
+  forall (f :: forall m. Monad m => MStream m u a -> MStream m u a) m.
   streamR (new (New.transformR f m)) = inplace f (streamR (new m))
 
  #-}
 
   streamR (new (New.transformR f m)) = inplace f (streamR (new m))
 
  #-}
 
-unstreamM :: (Monad m, Vector v a) => MStream m a -> m (v a)
+unstreamM :: (Monad m, Vector v a) => MStream m a -> m (v a)
 {-# INLINE_STREAM unstreamM #-}
 unstreamM s = do
                 xs <- MStream.toList s
                 return $ unstream $ Stream.unsafeFromList (MStream.size s) xs
 
 {-# INLINE_STREAM unstreamM #-}
 unstreamM s = do
                 xs <- MStream.toList s
                 return $ unstream $ Stream.unsafeFromList (MStream.size s) xs
 
-unstreamPrimM :: (PrimMonad m, Vector v a) => MStream m a -> m (v a)
+unstreamPrimM :: (PrimMonad m, Vector v a) => MStream m a -> m (v a)
 {-# INLINE_STREAM unstreamPrimM #-}
 unstreamPrimM s = M.munstream s >>= unsafeFreeze
 
 -- FIXME: the next two functions are only necessary for the specialisations
 {-# INLINE_STREAM unstreamPrimM #-}
 unstreamPrimM s = M.munstream s >>= unsafeFreeze
 
 -- FIXME: the next two functions are only necessary for the specialisations
-unstreamPrimM_IO :: Vector v a => MStream IO a -> IO (v a)
+unstreamPrimM_IO :: Vector v a => MStream IO a -> IO (v a)
 {-# INLINE unstreamPrimM_IO #-}
 unstreamPrimM_IO = unstreamPrimM
 
 {-# INLINE unstreamPrimM_IO #-}
 unstreamPrimM_IO = unstreamPrimM
 
-unstreamPrimM_ST :: Vector v a => MStream (ST s) a -> ST s (v a)
+unstreamPrimM_ST :: Vector v a => MStream (ST s) a -> ST s (v a)
 {-# INLINE unstreamPrimM_ST #-}
 unstreamPrimM_ST = unstreamPrimM
 
 {-# INLINE unstreamPrimM_ST #-}
 unstreamPrimM_ST = unstreamPrimM
 
index 7b6ece3..28ec271 100644 (file)
@@ -18,8 +18,8 @@ module Data.Vector.Generic.Base (
   Vector(..), Mutable
 ) where
 
   Vector(..), Mutable
 ) where
 
-import           Data.Vector.Generic.Mutable ( MVector )
-import qualified Data.Vector.Generic.Mutable as M
+import           Data.Vector.Generic.Mutable.Base ( MVector )
+import qualified Data.Vector.Generic.Mutable.Base as M
 
 import Control.Monad.Primitive
 
 
 import Control.Monad.Primitive
 
index 91e7036..c6f716c 100644 (file)
@@ -1,4 +1,4 @@
-{-# LANGUAGE MultiParamTypeClasses, BangPatterns, ScopedTypeVariables #-}
+{-# LANGUAGE MultiParamTypeClasses, FlexibleContexts, BangPatterns, TypeFamilies, ScopedTypeVariables #-}
 -- |
 -- Module      : Data.Vector.Generic.Mutable
 -- Copyright   : (c) Roman Leshchinskiy 2008-2010
 -- |
 -- Module      : Data.Vector.Generic.Mutable
 -- Copyright   : (c) Roman Leshchinskiy 2008-2010
@@ -49,7 +49,7 @@ module Data.Vector.Generic.Mutable (
 
   -- * Internal operations
   mstream, mstreamR,
 
   -- * Internal operations
   mstream, mstreamR,
-  unstream, unstreamR,
+  unstream, unstreamR, vunstream,
   munstream, munstreamR,
   transform, transformR,
   fill, fillR,
   munstream, munstreamR,
   transform, transformR,
   fill, fillR,
@@ -57,6 +57,9 @@ module Data.Vector.Generic.Mutable (
   unstablePartition, unstablePartitionStream, partitionStream
 ) where
 
   unstablePartition, unstablePartitionStream, partitionStream
 ) where
 
+import           Data.Vector.Generic.Mutable.Base
+import qualified Data.Vector.Generic.Base as V
+
 import qualified Data.Vector.Fusion.Stream      as Stream
 import           Data.Vector.Fusion.Stream      ( Stream, MStream )
 import qualified Data.Vector.Fusion.Stream.Monadic as MStream
 import qualified Data.Vector.Fusion.Stream      as Stream
 import           Data.Vector.Fusion.Stream      ( Stream, MStream )
 import qualified Data.Vector.Fusion.Stream.Monadic as MStream
@@ -70,23 +73,12 @@ import Prelude hiding ( length, null, replicate, reverse, map, read,
 
 #include "vector.h"
 
 
 #include "vector.h"
 
+{-
+type family Immutable (v :: * -> * -> *) :: * -> *
+
 -- | Class of mutable vectors parametrised with a primitive state token.
 --
 -- | Class of mutable vectors parametrised with a primitive state token.
 --
--- Minimum complete implementation:
---
---   * 'basicLength'
---
---   * 'basicUnsafeSlice'
---
---   * 'basicOverlaps'
---
---   * 'basicUnsafeNew'
---
---   * 'basicUnsafeRead'
---
---   * 'basicUnsafeWrite'
---
-class MVector v a where
+class MStream.Pointer u a => MVector v a where
   -- | Length of the mutable vector. This method should not be
   -- called directly, use 'length' instead.
   basicLength       :: v s a -> Int
   -- | Length of the mutable vector. This method should not be
   -- called directly, use 'length' instead.
   basicLength       :: v s a -> Int
@@ -128,6 +120,10 @@ class MVector v a where
   -- not be called directly, use 'set' instead.
   basicSet         :: PrimMonad m => v (PrimState m) a -> a -> m ()
 
   -- not be called directly, use 'set' instead.
   basicSet         :: PrimMonad m => v (PrimState m) a -> a -> m ()
 
+  basicUnsafeCopyPointer :: PrimMonad m => v (PrimState m) a
+                                        -> Immutable v a
+                                        -> m ()
+
   -- | Copy a vector. The two vectors may not overlap. This method should not
   -- be called directly, use 'unsafeCopy' instead.
   basicUnsafeCopy  :: PrimMonad m => v (PrimState m) a   -- ^ target
   -- | Copy a vector. The two vectors may not overlap. This method should not
   -- be called directly, use 'unsafeCopy' instead.
   basicUnsafeCopy  :: PrimMonad m => v (PrimState m) a   -- ^ target
@@ -170,6 +166,14 @@ class MVector v a where
                | otherwise = basicUnsafeCopy (basicUnsafeSlice i (n-i) v)
                                              (basicUnsafeSlice 0 (n-i) v)
 
                | otherwise = basicUnsafeCopy (basicUnsafeSlice i (n-i) v)
                                              (basicUnsafeSlice 0 (n-i) v)
 
+  {-# INLINE basicUnsafeCopyPointer #-}
+  basicUnsafeCopyPointer !dst !src = do_copy 0 src
+    where
+      do_copy !i p | Just (x,q) <- MStream.pget p = do
+                                                      basicUnsafeWrite dst i x
+                                                      do_copy (i+1) q
+                   | otherwise = return ()
+
   {-# INLINE basicUnsafeCopy #-}
   basicUnsafeCopy !dst !src = do_copy 0
     where
   {-# INLINE basicUnsafeCopy #-}
   basicUnsafeCopy !dst !src = do_copy 0
     where
@@ -196,7 +200,8 @@ class MVector v a where
         return v'
     where
       n = basicLength v
         return v'
     where
       n = basicLength v
-
+-}
 -- ------------------
 -- Internal functions
 -- ------------------
 -- ------------------
 -- Internal functions
 -- ------------------
@@ -233,7 +238,7 @@ unsafePrepend1 v i x
                     $ unsafeWrite v' i' x
                   return (v', i')
 
                     $ unsafeWrite v' i' x
                   return (v', i')
 
-mstream :: (PrimMonad m, MVector v a) => v (PrimState m) a -> MStream m a
+mstream :: (PrimMonad m, MVector v a) => v (PrimState m) a -> MStream m a
 {-# INLINE mstream #-}
 mstream v = v `seq` n `seq` (MStream.unfoldrM get 0 `MStream.sized` Exact n)
   where
 {-# INLINE mstream #-}
 mstream v = v `seq` n `seq` (MStream.unfoldrM get 0 `MStream.sized` Exact n)
   where
@@ -245,7 +250,9 @@ mstream v = v `seq` n `seq` (MStream.unfoldrM get 0 `MStream.sized` Exact n)
           | otherwise = return $ Nothing
 
 fill :: (PrimMonad m, MVector v a)
           | otherwise = return $ Nothing
 
 fill :: (PrimMonad m, MVector v a)
-           => v (PrimState m) a -> MStream m a -> m (v (PrimState m) a)
+     => v (PrimState m) a
+     -> MStream m u a
+     -> m (v (PrimState m) a)
 {-# INLINE fill #-}
 fill v s = v `seq` do
                      n' <- MStream.foldM put 0 s
 {-# INLINE fill #-}
 fill v s = v `seq` do
                      n' <- MStream.foldM put 0 s
@@ -258,11 +265,15 @@ fill v s = v `seq` do
                 return (i+1)
 
 transform :: (PrimMonad m, MVector v a)
                 return (i+1)
 
 transform :: (PrimMonad m, MVector v a)
-  => (MStream m a -> MStream m a) -> v (PrimState m) a -> m (v (PrimState m) a)
+          => (MStream m u a -> MStream m u a)
+          -> v (PrimState m) a
+          -> m (v (PrimState m) a)
 {-# INLINE_STREAM transform #-}
 transform f v = fill v (f (mstream v))
 
 {-# INLINE_STREAM transform #-}
 transform f v = fill v (f (mstream v))
 
-mstreamR :: (PrimMonad m, MVector v a) => v (PrimState m) a -> MStream m a
+mstreamR :: (PrimMonad m, MVector v a)
+         => v (PrimState m) a
+         -> MStream m u a
 {-# INLINE mstreamR #-}
 mstreamR v = v `seq` n `seq` (MStream.unfoldrM get n `MStream.sized` Exact n)
   where
 {-# INLINE mstreamR #-}
 mstreamR v = v `seq` n `seq` (MStream.unfoldrM get n `MStream.sized` Exact n)
   where
@@ -276,7 +287,9 @@ mstreamR v = v `seq` n `seq` (MStream.unfoldrM get n `MStream.sized` Exact n)
         j = i-1
 
 fillR :: (PrimMonad m, MVector v a)
         j = i-1
 
 fillR :: (PrimMonad m, MVector v a)
-           => v (PrimState m) a -> MStream m a -> m (v (PrimState m) a)
+      => v (PrimState m) a
+      -> MStream m u a
+      -> m (v (PrimState m) a)
 {-# INLINE fillR #-}
 fillR v s = v `seq` do
                       i <- MStream.foldM put n s
 {-# INLINE fillR #-}
 fillR v s = v `seq` do
                       i <- MStream.foldM put n s
@@ -292,14 +305,17 @@ fillR v s = v `seq` do
         j = i-1
 
 transformR :: (PrimMonad m, MVector v a)
         j = i-1
 
 transformR :: (PrimMonad m, MVector v a)
-  => (MStream m a -> MStream m a) -> v (PrimState m) a -> m (v (PrimState m) a)
+           => (MStream m u a -> MStream m u a)
+           -> v (PrimState m) a
+           -> m (v (PrimState m) a)
 {-# INLINE_STREAM transformR #-}
 transformR f v = fillR v (f (mstreamR v))
 
 -- | Create a new mutable vector and fill it with elements from the 'Stream'.
 -- The vector will grow exponentially if the maximum size of the 'Stream' is
 -- unknown.
 {-# INLINE_STREAM transformR #-}
 transformR f v = fillR v (f (mstreamR v))
 
 -- | Create a new mutable vector and fill it with elements from the 'Stream'.
 -- The vector will grow exponentially if the maximum size of the 'Stream' is
 -- unknown.
-unstream :: (PrimMonad m, MVector v a) => Stream a -> m (v (PrimState m) a)
+unstream :: (PrimMonad m, MVector v a)
+         => Stream u a -> m (v (PrimState m) a)
 -- NOTE: replace INLINE_STREAM by INLINE? (also in unstreamR)
 {-# INLINE_STREAM unstream #-}
 unstream s = munstream (Stream.liftStream s)
 -- NOTE: replace INLINE_STREAM by INLINE? (also in unstreamR)
 {-# INLINE_STREAM unstream #-}
 unstream s = munstream (Stream.liftStream s)
@@ -307,7 +323,8 @@ unstream s = munstream (Stream.liftStream s)
 -- | Create a new mutable vector and fill it with elements from the monadic
 -- stream. The vector will grow exponentially if the maximum size of the stream
 -- is unknown.
 -- | Create a new mutable vector and fill it with elements from the monadic
 -- stream. The vector will grow exponentially if the maximum size of the stream
 -- is unknown.
-munstream :: (PrimMonad m, MVector v a) => MStream m a -> m (v (PrimState m) a)
+munstream :: (PrimMonad m, MVector v a)
+          => MStream m u a -> m (v (PrimState m) a)
 {-# INLINE_STREAM munstream #-}
 munstream s = case upperBound (MStream.size s) of
                Just n  -> munstreamMax     s n
 {-# INLINE_STREAM munstream #-}
 munstream s = case upperBound (MStream.size s) of
                Just n  -> munstreamMax     s n
@@ -323,8 +340,8 @@ munstream s = case upperBound (MStream.size s) of
 --
 -- I'm not sure this still applies (19/04/2010)
 
 --
 -- I'm not sure this still applies (19/04/2010)
 
-munstreamMax
-  :: (PrimMonad m, MVector v a) => MStream m a -> Int -> m (v (PrimState m) a)
+munstreamMax :: (PrimMonad m, MVector v a)
+             => MStream m u a -> Int -> m (v (PrimState m) a)
 {-# INLINE munstreamMax #-}
 munstreamMax s n
   = do
 {-# INLINE munstreamMax #-}
 munstreamMax s n
   = do
@@ -338,8 +355,8 @@ munstreamMax s n
       return $ INTERNAL_CHECK(checkSlice) "munstreamMax" 0 n' n
              $ unsafeSlice 0 n' v
 
       return $ INTERNAL_CHECK(checkSlice) "munstreamMax" 0 n' n
              $ unsafeSlice 0 n' v
 
-munstreamUnknown
-  :: (PrimMonad m, MVector v a) => MStream m a -> m (v (PrimState m) a)
+munstreamUnknown :: (PrimMonad m, MVector v a)
+                 => MStream m u a -> m (v (PrimState m) a)
 {-# INLINE munstreamUnknown #-}
 munstreamUnknown s
   = do
 {-# INLINE munstreamUnknown #-}
 munstreamUnknown s
   = do
@@ -353,10 +370,96 @@ munstreamUnknown s
                     v' <- unsafeAppend1 v i x
                     return (v',i+1)
 
                     v' <- unsafeAppend1 v i x
                     return (v',i+1)
 
+
+
+
+
+
+
+-- | Create a new mutable vector and fill it with elements from the 'Stream'.
+-- The vector will grow exponentially if the maximum size of the 'Stream' is
+-- unknown.
+vunstream :: (PrimMonad m, V.Vector v a)
+         => Stream v a -> m (V.Mutable v (PrimState m) a)
+-- NOTE: replace INLINE_STREAM by INLINE? (also in unstreamR)
+{-# INLINE_STREAM vunstream #-}
+vunstream s = vmunstream (Stream.liftStream s)
+
+-- | Create a new mutable vector and fill it with elements from the monadic
+-- stream. The vector will grow exponentially if the maximum size of the stream
+-- is unknown.
+vmunstream :: (PrimMonad m, V.Vector v a)
+           => MStream m v a -> m (V.Mutable v (PrimState m) a)
+{-# INLINE_STREAM vmunstream #-}
+vmunstream s = case upperBound (MStream.size s) of
+               Just n  -> vmunstreamMax     s n
+               Nothing -> vmunstreamUnknown s
+
+-- FIXME: I can't think of how to prevent GHC from floating out
+-- unstreamUnknown. That is bad because SpecConstr then generates two
+-- specialisations: one for when it is called from unstream (it doesn't know
+-- the shape of the vector) and one for when the vector has grown. To see the
+-- problem simply compile this:
+--
+-- fromList = Data.Vector.Unboxed.unstream . Stream.fromList
+--
+-- I'm not sure this still applies (19/04/2010)
+
+vmunstreamMax :: (PrimMonad m, V.Vector v a)
+              => MStream m v a -> Int -> m (V.Mutable v (PrimState m) a)
+{-# INLINE vmunstreamMax #-}
+vmunstreamMax s n
+  = do
+      v <- INTERNAL_CHECK(checkLength) "munstreamMax" n
+           $ unsafeNew n
+      let put i x = do
+                       INTERNAL_CHECK(checkIndex) "munstreamMax" i n
+                         $ unsafeWrite v i x
+                       return (i+1)
+
+          {-# INLINE_INNER copy #-}
+          copy i u = do
+                       let n = V.basicLength u
+                       V.basicUnsafeCopy (basicUnsafeSlice i n v) u
+                       return (i+n)
+
+      n' <- MStream.vfoldlM' put copy 0 s
+      return $ INTERNAL_CHECK(checkSlice) "munstreamMax" 0 n' n
+             $ unsafeSlice 0 n' v
+
+vmunstreamUnknown :: (PrimMonad m, V.Vector v a)
+                 => MStream m v a -> m (V.Mutable v (PrimState m) a)
+{-# INLINE vmunstreamUnknown #-}
+vmunstreamUnknown s
+  = do
+      v <- unsafeNew 0
+      (v', n) <- MStream.vfoldlM put copy (v, 0) s
+      return $ INTERNAL_CHECK(checkSlice) "munstreamUnknown" 0 n (length v')
+             $ unsafeSlice 0 n v'
+  where
+    {-# INLINE_INNER put #-}
+    put (v,i) x = do
+                    v' <- unsafeAppend1 v i x
+                    return (v',i+1)
+
+    {-# INLINE_INNER copy #-}
+    copy (v,i) u = do
+                     let n = V.basicLength u
+                         j = i+n
+                     v' <- if basicLength v < j
+                             then unsafeGrow v (delay_inline max (enlarge_delta v) (j - basicLength v))
+                             else return v
+                     V.basicUnsafeCopy (basicUnsafeSlice i n v') u
+                     return (v',j)
+
+
+
+
 -- | Create a new mutable vector and fill it with elements from the 'Stream'
 -- from right to left. The vector will grow exponentially if the maximum size
 -- of the 'Stream' is unknown.
 -- | Create a new mutable vector and fill it with elements from the 'Stream'
 -- from right to left. The vector will grow exponentially if the maximum size
 -- of the 'Stream' is unknown.
-unstreamR :: (PrimMonad m, MVector v a) => Stream a -> m (v (PrimState m) a)
+unstreamR :: (PrimMonad m, MVector v a)
+          => Stream u a -> m (v (PrimState m) a)
 -- NOTE: replace INLINE_STREAM by INLINE? (also in unstream)
 {-# INLINE_STREAM unstreamR #-}
 unstreamR s = munstreamR (Stream.liftStream s)
 -- NOTE: replace INLINE_STREAM by INLINE? (also in unstream)
 {-# INLINE_STREAM unstreamR #-}
 unstreamR s = munstreamR (Stream.liftStream s)
@@ -364,14 +467,15 @@ unstreamR s = munstreamR (Stream.liftStream s)
 -- | Create a new mutable vector and fill it with elements from the monadic
 -- stream from right to left. The vector will grow exponentially if the maximum
 -- size of the stream is unknown.
 -- | Create a new mutable vector and fill it with elements from the monadic
 -- stream from right to left. The vector will grow exponentially if the maximum
 -- size of the stream is unknown.
-munstreamR :: (PrimMonad m, MVector v a) => MStream m a -> m (v (PrimState m) a)
+munstreamR :: (PrimMonad m, MVector v a)
+           => MStream m u a -> m (v (PrimState m) a)
 {-# INLINE_STREAM munstreamR #-}
 munstreamR s = case upperBound (MStream.size s) of
                Just n  -> munstreamRMax     s n
                Nothing -> munstreamRUnknown s
 
 {-# INLINE_STREAM munstreamR #-}
 munstreamR s = case upperBound (MStream.size s) of
                Just n  -> munstreamRMax     s n
                Nothing -> munstreamRUnknown s
 
-munstreamRMax
-  :: (PrimMonad m, MVector v a) => MStream m a -> Int -> m (v (PrimState m) a)
+munstreamRMax :: (PrimMonad m, MVector v a)
+              => MStream m u a -> Int -> m (v (PrimState m) a)
 {-# INLINE munstreamRMax #-}
 munstreamRMax s n
   = do
 {-# INLINE munstreamRMax #-}
 munstreamRMax s n
   = do
@@ -386,8 +490,8 @@ munstreamRMax s n
       return $ INTERNAL_CHECK(checkSlice) "munstreamRMax" i (n-i) n
              $ unsafeSlice i (n-i) v
 
       return $ INTERNAL_CHECK(checkSlice) "munstreamRMax" i (n-i) n
              $ unsafeSlice i (n-i) v
 
-munstreamRUnknown
-  :: (PrimMonad m, MVector v a) => MStream m a -> m (v (PrimState m) a)
+munstreamRUnknown :: (PrimMonad m, MVector v a)
+                  => MStream m u a -> m (v (PrimState m) a)
 {-# INLINE munstreamRUnknown #-}
 munstreamRUnknown s
   = do
 {-# INLINE munstreamRUnknown #-}
 munstreamRUnknown s
   = do
@@ -709,7 +813,7 @@ unsafeMove dst src = UNSAFE_CHECK(check) "unsafeMove" "length mismatch"
 -- ------------
 
 accum :: (PrimMonad m, MVector v a)
 -- ------------
 
 accum :: (PrimMonad m, MVector v a)
-        => (a -> b -> a) -> v (PrimState m) a -> Stream (Int, b) -> m ()
+      => (a -> b -> a) -> v (PrimState m) a -> Stream u (Int, b) -> m ()
 {-# INLINE accum #-}
 accum f !v s = Stream.mapM_ upd s
   where
 {-# INLINE accum #-}
 accum f !v s = Stream.mapM_ upd s
   where
@@ -722,7 +826,7 @@ accum f !v s = Stream.mapM_ upd s
     !n = length v
 
 update :: (PrimMonad m, MVector v a)
     !n = length v
 
 update :: (PrimMonad m, MVector v a)
-                        => v (PrimState m) a -> Stream (Int, a) -> m ()
+                        => v (PrimState m) a -> Stream (Int, a) -> m ()
 {-# INLINE update #-}
 update !v s = Stream.mapM_ upd s
   where
 {-# INLINE update #-}
 update !v s = Stream.mapM_ upd s
   where
@@ -733,7 +837,7 @@ update !v s = Stream.mapM_ upd s
     !n = length v
 
 unsafeAccum :: (PrimMonad m, MVector v a)
     !n = length v
 
 unsafeAccum :: (PrimMonad m, MVector v a)
-            => (a -> b -> a) -> v (PrimState m) a -> Stream (Int, b) -> m ()
+            => (a -> b -> a) -> v (PrimState m) a -> Stream (Int, b) -> m ()
 {-# INLINE unsafeAccum #-}
 unsafeAccum f !v s = Stream.mapM_ upd s
   where
 {-# INLINE unsafeAccum #-}
 unsafeAccum f !v s = Stream.mapM_ upd s
   where
@@ -746,7 +850,7 @@ unsafeAccum f !v s = Stream.mapM_ upd s
     !n = length v
 
 unsafeUpdate :: (PrimMonad m, MVector v a)
     !n = length v
 
 unsafeUpdate :: (PrimMonad m, MVector v a)
-                        => v (PrimState m) a -> Stream (Int, a) -> m ()
+                        => v (PrimState m) a -> Stream (Int, a) -> m ()
 {-# INLINE unsafeUpdate #-}
 unsafeUpdate !v s = Stream.mapM_ upd s
   where
 {-# INLINE unsafeUpdate #-}
 unsafeUpdate !v s = Stream.mapM_ upd s
   where
@@ -795,7 +899,7 @@ unstablePartition f !v = from_left 0 (length v)
                         else from_right i (j-1)
 
 unstablePartitionStream :: (PrimMonad m, MVector v a)
                         else from_right i (j-1)
 
 unstablePartitionStream :: (PrimMonad m, MVector v a)
-        => (a -> Bool) -> Stream a -> m (v (PrimState m) a, v (PrimState m) a)
+        => (a -> Bool) -> Stream a -> m (v (PrimState m) a, v (PrimState m) a)
 {-# INLINE unstablePartitionStream #-}
 unstablePartitionStream f s
   = case upperBound (Stream.size s) of
 {-# INLINE unstablePartitionStream #-}
 unstablePartitionStream f s
   = case upperBound (Stream.size s) of
@@ -803,7 +907,7 @@ unstablePartitionStream f s
       Nothing -> partitionUnknown f s
 
 unstablePartitionMax :: (PrimMonad m, MVector v a)
       Nothing -> partitionUnknown f s
 
 unstablePartitionMax :: (PrimMonad m, MVector v a)
-        => (a -> Bool) -> Stream a -> Int
+        => (a -> Bool) -> Stream a -> Int
         -> m (v (PrimState m) a, v (PrimState m) a)
 {-# INLINE unstablePartitionMax #-}
 unstablePartitionMax f s n
         -> m (v (PrimState m) a, v (PrimState m) a)
 {-# INLINE unstablePartitionMax #-}
 unstablePartitionMax f s n
@@ -823,7 +927,7 @@ unstablePartitionMax f s n
       return (unsafeSlice 0 i v, unsafeSlice j (n-j) v)
 
 partitionStream :: (PrimMonad m, MVector v a)
       return (unsafeSlice 0 i v, unsafeSlice j (n-j) v)
 
 partitionStream :: (PrimMonad m, MVector v a)
-        => (a -> Bool) -> Stream a -> m (v (PrimState m) a, v (PrimState m) a)
+        => (a -> Bool) -> Stream a -> m (v (PrimState m) a, v (PrimState m) a)
 {-# INLINE partitionStream #-}
 partitionStream f s
   = case upperBound (Stream.size s) of
 {-# INLINE partitionStream #-}
 partitionStream f s
   = case upperBound (Stream.size s) of
@@ -831,7 +935,7 @@ partitionStream f s
       Nothing -> partitionUnknown f s
 
 partitionMax :: (PrimMonad m, MVector v a)
       Nothing -> partitionUnknown f s
 
 partitionMax :: (PrimMonad m, MVector v a)
-  => (a -> Bool) -> Stream a -> Int -> m (v (PrimState m) a, v (PrimState m) a)
+  => (a -> Bool) -> Stream a -> Int -> m (v (PrimState m) a, v (PrimState m) a)
 {-# INLINE partitionMax #-}
 partitionMax f s n
   = do
 {-# INLINE partitionMax #-}
 partitionMax f s n
   = do
@@ -858,7 +962,7 @@ partitionMax f s n
       return (l,r)
 
 partitionUnknown :: (PrimMonad m, MVector v a)
       return (l,r)
 
 partitionUnknown :: (PrimMonad m, MVector v a)
-        => (a -> Bool) -> Stream a -> m (v (PrimState m) a, v (PrimState m) a)
+        => (a -> Bool) -> Stream a -> m (v (PrimState m) a, v (PrimState m) a)
 {-# INLINE partitionUnknown #-}
 partitionUnknown f s
   = do
 {-# INLINE partitionUnknown #-}
 partitionUnknown f s
   = do
diff --git a/Data/Vector/Generic/Mutable/Base.hs b/Data/Vector/Generic/Mutable/Base.hs
new file mode 100644 (file)
index 0000000..d50c8c0
--- /dev/null
@@ -0,0 +1,135 @@
+{-# LANGUAGE MultiParamTypeClasses, BangPatterns #-}
+-- |
+-- Module      : Data.Vector.Generic.Mutable.Base
+-- Copyright   : (c) Roman Leshchinskiy 2008-2011
+-- License     : BSD-style
+--
+-- Maintainer  : Roman Leshchinskiy <rl@cse.unsw.edu.au>
+-- Stability   : experimental
+-- Portability : non-portable
+-- 
+-- Class of mutable vectors 
+--
+
+module Data.Vector.Generic.Mutable.Base (
+  MVector(..)
+) where
+
+import Control.Monad.Primitive ( PrimMonad, PrimState )
+
+#include "vector.h"
+
+-- | Class of mutable vectors parametrised with a primitive state token.
+--
+class MVector v a where
+  -- | Length of the mutable vector. This method should not be
+  -- called directly, use 'length' instead.
+  basicLength       :: v s a -> Int
+
+  -- | Yield a part of the mutable vector without copying it. This method
+  -- should not be called directly, use 'unsafeSlice' instead.
+  basicUnsafeSlice :: Int  -- ^ starting index
+                   -> Int  -- ^ length of the slice
+                   -> v s a
+                   -> v s a
+
+  -- Check whether two vectors overlap. This method should not be
+  -- called directly, use 'overlaps' instead.
+  basicOverlaps    :: v s a -> v s a -> Bool
+
+  -- | Create a mutable vector of the given length. This method should not be
+  -- called directly, use 'unsafeNew' instead.
+  basicUnsafeNew   :: PrimMonad m => Int -> m (v (PrimState m) a)
+
+  -- | Create a mutable vector of the given length and fill it with an
+  -- initial value. This method should not be called directly, use
+  -- 'replicate' instead.
+  basicUnsafeReplicate :: PrimMonad m => Int -> a -> m (v (PrimState m) a)
+
+  -- | Yield the element at the given position. This method should not be
+  -- called directly, use 'unsafeRead' instead.
+  basicUnsafeRead  :: PrimMonad m => v (PrimState m) a -> Int -> m a
+
+  -- | Replace the element at the given position. This method should not be
+  -- called directly, use 'unsafeWrite' instead.
+  basicUnsafeWrite :: PrimMonad m => v (PrimState m) a -> Int -> a -> m ()
+
+  -- | Reset all elements of the vector to some undefined value, clearing all
+  -- references to external objects. This is usually a noop for unboxed
+  -- vectors. This method should not be called directly, use 'clear' instead.
+  basicClear       :: PrimMonad m => v (PrimState m) a -> m ()
+
+  -- | Set all elements of the vector to the given value. This method should
+  -- not be called directly, use 'set' instead.
+  basicSet         :: PrimMonad m => v (PrimState m) a -> a -> m ()
+
+  -- | Copy a vector. The two vectors may not overlap. This method should not
+  -- be called directly, use 'unsafeCopy' instead.
+  basicUnsafeCopy  :: PrimMonad m => v (PrimState m) a   -- ^ target
+                                  -> v (PrimState m) a   -- ^ source
+                                  -> m ()
+
+  -- | Move the contents of a vector. The two vectors may overlap. This method
+  -- should not be called directly, use 'unsafeMove' instead.
+  basicUnsafeMove  :: PrimMonad m => v (PrimState m) a   -- ^ target
+                                  -> v (PrimState m) a   -- ^ source
+                                  -> m ()
+
+  -- | Grow a vector by the given number of elements. This method should not be
+  -- called directly, use 'unsafeGrow' instead.
+  basicUnsafeGrow  :: PrimMonad m => v (PrimState m) a -> Int
+                                                       -> m (v (PrimState m) a)
+
+  {-# INLINE basicUnsafeReplicate #-}
+  basicUnsafeReplicate n x
+    = do
+        v <- basicUnsafeNew n
+        basicSet v x
+        return v
+
+  {-# INLINE basicClear #-}
+  basicClear _ = return ()
+
+  {-# INLINE basicSet #-}
+  basicSet !v x
+    | n == 0    = return ()
+    | otherwise = do
+                    basicUnsafeWrite v 0 x
+                    do_set 1
+    where
+      !n = basicLength v
+
+      do_set i | 2*i < n = do basicUnsafeCopy (basicUnsafeSlice i i v)
+                                              (basicUnsafeSlice 0 i v)
+                              do_set (2*i)
+               | otherwise = basicUnsafeCopy (basicUnsafeSlice i (n-i) v)
+                                             (basicUnsafeSlice 0 (n-i) v)
+
+  {-# INLINE basicUnsafeCopy #-}
+  basicUnsafeCopy !dst !src = do_copy 0
+    where
+      !n = basicLength src
+
+      do_copy i | i < n = do
+                            x <- basicUnsafeRead src i
+                            basicUnsafeWrite dst i x
+                            do_copy (i+1)
+                | otherwise = return ()
+  
+  {-# INLINE basicUnsafeMove #-}
+  basicUnsafeMove !dst !src
+    | basicOverlaps dst src = do
+        srcCopy <- basicUnsafeNew (basicLength src)
+        basicUnsafeCopy srcCopy src
+        basicUnsafeCopy dst srcCopy
+    | otherwise = basicUnsafeCopy dst src
+
+  {-# INLINE basicUnsafeGrow #-}
+  basicUnsafeGrow v by
+    = do
+        v' <- basicUnsafeNew (n+by)
+        basicUnsafeCopy (basicUnsafeSlice 0 n v') v
+        return v'
+    where
+      n = basicLength v
+
index d5bb50c..32c1fe6 100644 (file)
@@ -56,55 +56,55 @@ modify :: (forall s. Mutable v s a -> ST s ()) -> New v a -> New v a
 {-# INLINE modify #-}
 modify f (New p) = New (do { v <- p; f v; return v })
 
 {-# INLINE modify #-}
 modify f (New p) = New (do { v <- p; f v; return v })
 
-modifyWithStream :: (forall s. Mutable v s a -> Stream b -> ST s ())
-                 -> New v a -> Stream b -> New v a
+modifyWithStream :: (forall s. Mutable v s a -> Stream b -> ST s ())
+                 -> New v a -> Stream b -> New v a
 {-# INLINE_STREAM modifyWithStream #-}
 modifyWithStream f (New p) s = s `seq` New (do { v <- p; f v s; return v })
 
 {-# INLINE_STREAM modifyWithStream #-}
 modifyWithStream f (New p) s = s `seq` New (do { v <- p; f v s; return v })
 
-unstream :: Vector v a => Stream a -> New v a
+unstream :: Vector v a => Stream a -> New v a
 {-# INLINE_STREAM unstream #-}
 {-# INLINE_STREAM unstream #-}
-unstream s = s `seq` New (MVector.unstream s)
+unstream s = s `seq` New (MVector.vunstream s)
 
 transform :: Vector v a =>
 
 transform :: Vector v a =>
-        (forall m. Monad m => MStream m a -> MStream m a) -> New v a -> New v a
+        (forall m. Monad m => MStream m u a -> MStream m u a) -> New v a -> New v a
 {-# INLINE_STREAM transform #-}
 transform f (New p) = New (MVector.transform f =<< p)
 
 {-# RULES
 
 "transform/transform [New]"
 {-# INLINE_STREAM transform #-}
 transform f (New p) = New (MVector.transform f =<< p)
 
 {-# RULES
 
 "transform/transform [New]"
-  forall (f :: forall m. Monad m => MStream m a -> MStream m a)
-         (g :: forall m. Monad m => MStream m a -> MStream m a)
+  forall (f :: forall m. Monad m => MStream m v a -> MStream m v a)
+         (g :: forall m. Monad m => MStream m v a -> MStream m v a)
          p .
   transform f (transform g p) = transform (f . g) p
 
 "transform/unstream [New]"
          p .
   transform f (transform g p) = transform (f . g) p
 
 "transform/unstream [New]"
-  forall (f :: forall m. Monad m => MStream m a -> MStream m a)
+  forall (f :: forall m. Monad m => MStream m v a -> MStream m v a)
          s.
   transform f (unstream s) = unstream (f s)
 
  #-}
 
 
          s.
   transform f (unstream s) = unstream (f s)
 
  #-}
 
 
-unstreamR :: Vector v a => Stream a -> New v a
+unstreamR :: Vector v a => Stream a -> New v a
 {-# INLINE_STREAM unstreamR #-}
 unstreamR s = s `seq` New (MVector.unstreamR s)
 
 transformR :: Vector v a =>
 {-# INLINE_STREAM unstreamR #-}
 unstreamR s = s `seq` New (MVector.unstreamR s)
 
 transformR :: Vector v a =>
-        (forall m. Monad m => MStream m a -> MStream m a) -> New v a -> New v a
+        (forall m. Monad m => MStream m u a -> MStream m u a) -> New v a -> New v a
 {-# INLINE_STREAM transformR #-}
 transformR f (New p) = New (MVector.transformR f =<< p)
 
 {-# RULES
 
 "transformR/transformR [New]"
 {-# INLINE_STREAM transformR #-}
 transformR f (New p) = New (MVector.transformR f =<< p)
 
 {-# RULES
 
 "transformR/transformR [New]"
-  forall (f :: forall m. Monad m => MStream m a -> MStream m a)
-         (g :: forall m. Monad m => MStream m a -> MStream m a)
+  forall (f :: forall m. Monad m => MStream m v a -> MStream m v a)
+         (g :: forall m. Monad m => MStream m v a -> MStream m v a)
          p .
   transformR f (transformR g p) = transformR (f . g) p
 
 "transformR/unstreamR [New]"
          p .
   transformR f (transformR g p) = transformR (f . g) p
 
 "transformR/unstreamR [New]"
-  forall (f :: forall m. Monad m => MStream m a -> MStream m a)
+  forall (f :: forall m. Monad m => MStream m v a -> MStream m v a)
          s.
   transformR f (unstreamR s) = unstreamR (f s)
 
          s.
   transformR f (unstreamR s) = unstreamR (f s)
 
index d7b63cf..939e4a4 100644 (file)
@@ -136,6 +136,7 @@ Library
         Data.Vector.Fusion.Stream
         Data.Vector.Fusion.Stream.Safe
 
         Data.Vector.Fusion.Stream
         Data.Vector.Fusion.Stream.Safe
 
+        Data.Vector.Generic.Mutable.Base
         Data.Vector.Generic.Mutable
         Data.Vector.Generic.Mutable.Safe
         Data.Vector.Generic.Base
         Data.Vector.Generic.Mutable
         Data.Vector.Generic.Mutable.Safe
         Data.Vector.Generic.Base