Finish Stream -> Bundle renaming
[darcs-mirrors/vector.git] / Data / Vector / Generic.hs
index c768d66..9483020 100644 (file)
 {-# LANGUAGE Rank2Types, MultiParamTypeClasses, FlexibleContexts,
 {-# LANGUAGE Rank2Types, MultiParamTypeClasses, FlexibleContexts,
-             TypeFamilies, ScopedTypeVariables #-}
+             TypeFamilies, ScopedTypeVariables, BangPatterns #-}
 -- |
 -- Module      : Data.Vector.Generic
 -- |
 -- Module      : Data.Vector.Generic
--- Copyright   : (c) Roman Leshchinskiy 2008-2009
+-- Copyright   : (c) Roman Leshchinskiy 2008-2010
 -- License     : BSD-style
 --
 -- Maintainer  : Roman Leshchinskiy <rl@cse.unsw.edu.au>
 -- Stability   : experimental
 -- Portability : non-portable
 -- 
 -- License     : BSD-style
 --
 -- Maintainer  : Roman Leshchinskiy <rl@cse.unsw.edu.au>
 -- Stability   : experimental
 -- Portability : non-portable
 -- 
--- Generic interface to pure vectors
+-- Generic interface to pure vectors.
 --
 
 module Data.Vector.Generic (
   -- * Immutable vectors
   Vector(..), Mutable,
 
 --
 
 module Data.Vector.Generic (
   -- * Immutable vectors
   Vector(..), Mutable,
 
-  -- * Length information
-  length, null,
+  -- * Accessors
 
 
-  -- * Construction
-  empty, singleton, cons, snoc, replicate, generate, (++), copy,
+  -- ** Length information
+  length, null,
 
 
-  -- * Accessing individual elements
-  (!), head, last, indexM, headM, lastM,
+  -- ** Indexing
+  (!), (!?), head, last,
   unsafeIndex, unsafeHead, unsafeLast,
   unsafeIndex, unsafeHead, unsafeLast,
+
+  -- ** Monadic indexing
+  indexM, headM, lastM,
   unsafeIndexM, unsafeHeadM, unsafeLastM,
 
   unsafeIndexM, unsafeHeadM, unsafeLastM,
 
-  -- * Subvectors
-  slice, init, tail, take, drop,
+  -- ** Extracting subvectors (slicing)
+  slice, init, tail, take, drop, splitAt,
   unsafeSlice, unsafeInit, unsafeTail, unsafeTake, unsafeDrop,
 
   unsafeSlice, unsafeInit, unsafeTail, unsafeTake, unsafeDrop,
 
-  -- * Permutations
-  accum, accumulate, accumulate_,
+  -- * Construction
+
+  -- ** Initialisation
+  empty, singleton, replicate, generate, iterateN,
+
+  -- ** Monadic initialisation
+  replicateM, generateM, create,
+
+  -- ** Unfolding
+  unfoldr, unfoldrN,
+  constructN, constructrN,
+
+  -- ** Enumeration
+  enumFromN, enumFromStepN, enumFromTo, enumFromThenTo,
+
+  -- ** Concatenation
+  cons, snoc, (++), concat,
+
+  -- ** Restricting memory usage
+  force,
+
+  -- * Modifying vectors
+
+  -- ** Bulk updates
   (//), update, update_,
   (//), update, update_,
-  backpermute, reverse,
-  unsafeAccum, unsafeAccumulate, unsafeAccumulate_,
   unsafeUpd, unsafeUpdate, unsafeUpdate_,
   unsafeUpd, unsafeUpdate, unsafeUpdate_,
-  unsafeBackpermute,
 
 
-  -- * Mapping
+  -- ** Accumulations
+  accum, accumulate, accumulate_,
+  unsafeAccum, unsafeAccumulate, unsafeAccumulate_,
+
+  -- ** Permutations 
+  reverse, backpermute, unsafeBackpermute,
+
+  -- ** Safe destructive updates
+  modify,
+
+  -- * Elementwise operations
+
+  -- ** Indexing
+  indexed,
+
+  -- ** Mapping
   map, imap, concatMap,
 
   map, imap, concatMap,
 
-  -- * Zipping and unzipping
+  -- ** Monadic mapping
+  mapM, mapM_, forM, forM_,
+
+  -- ** Zipping
   zipWith, zipWith3, zipWith4, zipWith5, zipWith6,
   izipWith, izipWith3, izipWith4, izipWith5, izipWith6,
   zip, zip3, zip4, zip5, zip6,
   zipWith, zipWith3, zipWith4, zipWith5, zipWith6,
   izipWith, izipWith3, izipWith4, izipWith5, izipWith6,
   zip, zip3, zip4, zip5, zip6,
+
+  -- ** Monadic zipping
+  zipWithM, zipWithM_,
+
+  -- ** Unzipping
   unzip, unzip3, unzip4, unzip5, unzip6,
 
   unzip, unzip3, unzip4, unzip5, unzip6,
 
-  -- * Comparisons
-  eq, cmp,
+  -- * Working with predicates
 
 
-  -- * Filtering
-  filter, ifilter, takeWhile, dropWhile,
+  -- ** Filtering
+  filter, ifilter, filterM,
+  takeWhile, dropWhile,
+
+  -- ** Partitioning
   partition, unstablePartition, span, break,
 
   partition, unstablePartition, span, break,
 
-  -- * Searching
+  -- ** Searching
   elem, notElem, find, findIndex, findIndices, elemIndex, elemIndices,
 
   -- * Folding
   foldl, foldl1, foldl', foldl1', foldr, foldr1, foldr', foldr1',
   ifoldl, ifoldl', ifoldr, ifoldr',
   elem, notElem, find, findIndex, findIndices, elemIndex, elemIndices,
 
   -- * Folding
   foldl, foldl1, foldl', foldl1', foldr, foldr1, foldr', foldr1',
   ifoldl, ifoldl', ifoldr, ifoldr',
-  -- * Specialised folds
+
+  -- ** Specialised folds
   all, any, and, or,
   sum, product,
   maximum, maximumBy, minimum, minimumBy,
   minIndex, minIndexBy, maxIndex, maxIndexBy,
 
   all, any, and, or,
   sum, product,
   maximum, maximumBy, minimum, minimumBy,
   minIndex, minIndexBy, maxIndex, maxIndexBy,
 
-  -- * Unfolding
-  unfoldr, unfoldrN,
+  -- ** Monadic folds
+  foldM, foldM', fold1M, fold1M',
+  foldM_, foldM'_, fold1M_, fold1M'_,
+
+  -- ** Monadic sequencing
+  sequence, sequence_,
 
 
-  -- * Scans
+  -- * Prefix sums (scans)
   prescanl, prescanl',
   postscanl, postscanl',
   scanl, scanl', scanl1, scanl1',
   prescanl, prescanl',
   postscanl, postscanl',
   scanl, scanl', scanl1, scanl1',
@@ -79,609 +129,923 @@ module Data.Vector.Generic (
   postscanr, postscanr',
   scanr, scanr', scanr1, scanr1',
 
   postscanr, postscanr',
   scanr, scanr', scanr1, scanr1',
 
-  -- * Enumeration
-  enumFromN, enumFromStepN, enumFromTo, enumFromThenTo,
+  -- * Conversions
 
 
-  -- * Conversion to/from lists
+  -- ** Lists
   toList, fromList, fromListN,
 
   toList, fromList, fromListN,
 
-  -- * Conversion to/from Streams
+  -- ** Different vector types
+  convert,
+
+  -- ** Mutable vectors
+  freeze, thaw, copy, unsafeFreeze, unsafeThaw, unsafeCopy,
+
+  -- * Fusion support
+
+  -- ** Conversion to/from Bundles
   stream, unstream, streamR, unstreamR,
 
   stream, unstream, streamR, unstreamR,
 
-  -- * MVector-based initialisation
-  new,
+  -- ** Recycling support
+  new, clone,
+
+  -- * Utilities
+
+  -- ** Comparisons
+  eq, cmp,
+
+  -- ** Show and Read
+  showsPrec, readPrec,
 
 
-  -- * Utilities for defining Data instances
+  -- ** @Data@ and @Typeable@
   gfoldl, dataCast, mkType
 ) where
 
   gfoldl, dataCast, mkType
 ) where
 
+import           Data.Vector.Generic.Base
+
 import           Data.Vector.Generic.Mutable ( MVector )
 import qualified Data.Vector.Generic.Mutable as M
 
 import qualified Data.Vector.Generic.New as New
 import           Data.Vector.Generic.New ( New )
 
 import           Data.Vector.Generic.Mutable ( MVector )
 import qualified Data.Vector.Generic.Mutable as M
 
 import qualified Data.Vector.Generic.New as New
 import           Data.Vector.Generic.New ( New )
 
-import qualified Data.Vector.Fusion.Stream as Stream
-import           Data.Vector.Fusion.Stream ( Stream, MStream, inplace )
-import qualified Data.Vector.Fusion.Stream.Monadic as MStream
-import           Data.Vector.Fusion.Stream.Size
+import qualified Data.Vector.Fusion.Bundle as Bundle
+import           Data.Vector.Fusion.Bundle ( Bundle, MBundle, Step(..), inplace, lift )
+import qualified Data.Vector.Fusion.Bundle.Monadic as MBundle
+import           Data.Vector.Fusion.Bundle.Size
 import           Data.Vector.Fusion.Util
 
 import           Data.Vector.Fusion.Util
 
-import Control.Monad.ST ( runST )
+import Control.Monad.ST ( ST, runST )
 import Control.Monad.Primitive
 import Control.Monad.Primitive
+import qualified Control.Monad as Monad
+import qualified Data.List as List
 import Prelude hiding ( length, null,
 import Prelude hiding ( length, null,
-                        replicate, (++),
+                        replicate, (++), concat,
                         head, last,
                         head, last,
-                        init, tail, take, drop, reverse,
-                        map, concatMap,
+                        init, tail, take, drop, splitAt, reverse,
+                        map, concat, concatMap,
                         zipWith, zipWith3, zip, zip3, unzip, unzip3,
                         filter, takeWhile, dropWhile, span, break,
                         elem, notElem,
                         foldl, foldl1, foldr, foldr1,
                         all, any, and, or, sum, product, maximum, minimum,
                         scanl, scanl1, scanr, scanr1,
                         zipWith, zipWith3, zip, zip3, unzip, unzip3,
                         filter, takeWhile, dropWhile, span, break,
                         elem, notElem,
                         foldl, foldl1, foldr, foldr1,
                         all, any, and, or, sum, product, maximum, minimum,
                         scanl, scanl1, scanr, scanr1,
-                        enumFromTo, enumFromThenTo )
+                        enumFromTo, enumFromThenTo,
+                        mapM, mapM_, sequence, sequence_,
+                        showsPrec )
 
 
+import qualified Text.Read as Read
 import Data.Typeable ( Typeable1, gcast1 )
 import Data.Typeable ( Typeable1, gcast1 )
-import Data.Data ( Data, DataType, mkNorepType )
 
 #include "vector.h"
 
 
 #include "vector.h"
 
-type family Mutable (v :: * -> *) :: * -> * -> *
+import Data.Data ( Data, DataType )
+#if MIN_VERSION_base(4,2,0)
+import Data.Data ( mkNoRepType )
+#else
+import Data.Data ( mkNorepType )
+mkNoRepType :: String -> DataType
+mkNoRepType = mkNorepType
+#endif
 
 
--- | Class of immutable vectors.
---
-class MVector (Mutable v) a => Vector v a where
-  -- | Unsafely convert a mutable vector to its immutable version
-  -- without copying. The mutable vector may not be used after
-  -- this operation.
-  unsafeFreeze :: PrimMonad m => Mutable v (PrimState m) a -> m (v a)
-
-  -- | Length of the vector (not fusible!)
-  basicLength      :: v a -> Int
-
-  -- | Yield a part of the vector without copying it. No range checks!
-  basicUnsafeSlice  :: Int -> Int -> v a -> v a
-
-  -- | Yield the element at the given position in a monad. The monad allows us
-  -- to be strict in the vector if we want. Suppose we had
-  --
-  -- > unsafeIndex :: v a -> Int -> a
-  --
-  -- instead. Now, if we wanted to copy a vector, we'd do something like
-  --
-  -- > copy mv v ... = ... unsafeWrite mv i (unsafeIndex v i) ...
-  --
-  -- For lazy vectors, the indexing would not be evaluated which means that we
-  -- would retain a reference to the original vector in each element we write.
-  -- This is not what we want!
-  --
-  -- With 'basicUnsafeIndexM', we can do
-  --
-  -- > copy mv v ... = ... case basicUnsafeIndexM v i of
-  -- >                       Box x -> unsafeWrite mv i x ...
-  --
-  -- which does not have this problem because indexing (but not the returned
-  -- element!) is evaluated immediately.
-  --
-  basicUnsafeIndexM  :: Monad m => v a -> Int -> m a
-
-  elemseq :: v a -> a -> b -> b
-
-  {-# INLINE elemseq #-}
-  elemseq _ = \_ x -> x
-
--- Fusion
--- ------
-
--- | Construct a pure vector from a monadic initialiser 
-new :: Vector v a => New a -> v a
-{-# INLINE new #-}
-new m = new' undefined m
-
--- | Same as 'new' but with a dummy argument necessary for correctly typing
--- the rule @uninplace@.
---
--- See http://hackage.haskell.org/trac/ghc/ticket/2600
-new' :: Vector v a => v a -> New a -> v a
-{-# INLINE_STREAM new' #-}
-new' _ m = m `seq` runST (do
-                            mv <- New.run m
-                            unsafeFreeze mv)
-
--- | Convert a vector to a 'Stream'
-stream :: Vector v a => v a -> Stream a
-{-# INLINE_STREAM stream #-}
-stream v = v `seq` (Stream.unfoldr get 0 `Stream.sized` Exact n)
-  where
-    n = length v
-
-    -- NOTE: the False case comes first in Core so making it the recursive one
-    -- makes the code easier to read
-    {-# INLINE get #-}
-    get i | i >= n    = Nothing
-          | otherwise = case basicUnsafeIndexM v i of Box x -> Just (x, i+1)
-
--- | Create a vector from a 'Stream'
-unstream :: Vector v a => Stream a -> v a
-{-# INLINE unstream #-}
-unstream s = new (New.unstream s)
-
-{-# RULES
-
-"stream/unstream [Vector]" forall v s.
-  stream (new' v (New.unstream s)) = s
-
-"New.unstream/stream/new [Vector]" forall v p.
-  New.unstream (stream (new' v p)) = p
-
- #-}
-
-{-# RULES
-
-"inplace [Vector]"
-  forall (f :: forall m. Monad m => MStream m a -> MStream m a) v m.
-  New.unstream (inplace f (stream (new' v m))) = New.transform f m
-
-"uninplace [Vector]"
-  forall (f :: forall m. Monad m => MStream m a -> MStream m a) v m.
-  stream (new' v (New.transform f m)) = inplace f (stream (new' v m))
-
- #-}
-
--- | Convert a vector to a 'Stream'
-streamR :: Vector v a => v a -> Stream a
-{-# INLINE_STREAM streamR #-}
-streamR v = v `seq` (Stream.unfoldr get n `Stream.sized` Exact n)
-  where
-    n = length v
-
-    {-# INLINE get #-}
-    get 0 = Nothing
-    get i = let i' = i-1
-            in
-            case basicUnsafeIndexM v i' of Box x -> Just (x, i')
-
--- | Create a vector from a 'Stream'
-unstreamR :: Vector v a => Stream a -> v a
-{-# INLINE unstreamR #-}
-unstreamR s = new (New.unstreamR s)
-
-{-# RULES
-
-"streamR/unstreamR [Vector]" forall v s.
-  streamR (new' v (New.unstreamR s)) = s
-
-"New.unstreamR/streamR/new [Vector]" forall v p.
-  New.unstreamR (streamR (new' v p)) = p
-
- #-}
-
-{-# RULES
-
-"inplace [Vector]"
-  forall (f :: forall m. Monad m => MStream m a -> MStream m a) v m.
-  New.unstreamR (inplace f (streamR (new' v m))) = New.transformR f m
-
-"uninplace [Vector]"
-  forall (f :: forall m. Monad m => MStream m a -> MStream m a) v m.
-  streamR (new' v (New.transformR f m)) = inplace f (streamR (new' v m))
-
- #-}
-
--- Length
--- ------
+-- Length information
+-- ------------------
 
 
+-- | /O(1)/ Yield the length of the vector.
 length :: Vector v a => v a -> Int
 length :: Vector v a => v a -> Int
-{-# INLINE_STREAM length #-}
-length v = basicLength v
-
-{-# RULES
-
-"length/unstream [Vector]" forall v s.
-  length (new' v (New.unstream s)) = Stream.length s
-
-  #-}
+{-# INLINE length #-}
+length = Bundle.length . stream
 
 
+-- | /O(1)/ Test whether a vector if empty
 null :: Vector v a => v a -> Bool
 null :: Vector v a => v a -> Bool
-{-# INLINE_STREAM null #-}
-null v = basicLength v == 0
-
-{-# RULES
+{-# INLINE null #-}
+null = Bundle.null . stream
 
 
-"null/unstream [Vector]" forall v s.
-  null (new' v (New.unstream s)) = Stream.null s
+-- Indexing
+-- --------
 
 
-  #-}
-
--- Construction
--- ------------
-
--- | Empty vector
-empty :: Vector v a => v a
-{-# INLINE empty #-}
-empty = unstream Stream.empty
-
--- | Vector with exaclty one element
-singleton :: forall v a. Vector v a => a -> v a
-{-# INLINE singleton #-}
-singleton x = elemseq (undefined :: v a) x
-            $ unstream (Stream.singleton x)
-
--- | Vector of the given length with the given value in each position
-replicate :: forall v a. Vector v a => Int -> a -> v a
-{-# INLINE replicate #-}
-replicate n x = elemseq (undefined :: v a) x
-              $ unstream
-              $ Stream.replicate n x
-
--- | Generate a vector of the given length by applying the function to each
--- index
-generate :: Vector v a => Int -> (Int -> a) -> v a
-{-# INLINE generate #-}
-generate n f = unstream (Stream.generate n f)
-
--- | Prepend an element
-cons :: forall v a. Vector v a => a -> v a -> v a
-{-# INLINE cons #-}
-cons x v = elemseq (undefined :: v a) x
-         $ unstream
-         $ Stream.cons x
-         $ stream v
-
--- | Append an element
-snoc :: forall v a. Vector v a => v a -> a -> v a
-{-# INLINE snoc #-}
-snoc v x = elemseq (undefined :: v a) x
-         $ unstream
-         $ Stream.snoc (stream v) x
-
-infixr 5 ++
--- | Concatenate two vectors
-(++) :: Vector v a => v a -> v a -> v a
-{-# INLINE (++) #-}
-v ++ w = unstream (stream v Stream.++ stream w)
-
--- | Create a copy of a vector. Useful when dealing with slices.
-copy :: Vector v a => v a -> v a
-{-# INLINE_STREAM copy #-}
-copy = unstream . stream
-
-{-# RULES
-
-"copy/unstream [Vector]" forall v s.
-  copy (new' v (New.unstream s)) = new' v (New.unstream s)
-
- #-}
-
--- Accessing individual elements
--- -----------------------------
-
--- | Indexing
+infixl 9 !
+-- | O(1) Indexing
 (!) :: Vector v a => v a -> Int -> a
 (!) :: Vector v a => v a -> Int -> a
-{-# INLINE_STREAM (!) #-}
-v ! i = BOUNDS_CHECK(checkIndex) "(!)" i (length v)
-      $ unId (basicUnsafeIndexM v i)
-
--- | First element
+{-# INLINE_FUSED (!) #-}
+(!) v i = BOUNDS_CHECK(checkIndex) "(!)" i (length v)
+        $ unId (basicUnsafeIndexM v i)
+
+infixl 9 !?
+-- | O(1) Safe indexing
+(!?) :: Vector v a => v a -> Int -> Maybe a
+{-# INLINE_FUSED (!?) #-}
+v !? i | i < 0 || i >= length v = Nothing
+       | otherwise              = Just $ unsafeIndex v i
+
+-- | /O(1)/ First element
 head :: Vector v a => v a -> a
 head :: Vector v a => v a -> a
-{-# INLINE_STREAM head #-}
+{-# INLINE_FUSED head #-}
 head v = v ! 0
 
 head v = v ! 0
 
--- | Last element
+-- | /O(1)/ Last element
 last :: Vector v a => v a -> a
 last :: Vector v a => v a -> a
-{-# INLINE_STREAM last #-}
+{-# INLINE_FUSED last #-}
 last v = v ! (length v - 1)
 
 last v = v ! (length v - 1)
 
--- | Unsafe indexing without bounds checking
+-- | /O(1)/ Unsafe indexing without bounds checking
 unsafeIndex :: Vector v a => v a -> Int -> a
 unsafeIndex :: Vector v a => v a -> Int -> a
-{-# INLINE_STREAM unsafeIndex #-}
+{-# INLINE_FUSED unsafeIndex #-}
 unsafeIndex v i = UNSAFE_CHECK(checkIndex) "unsafeIndex" i (length v)
                 $ unId (basicUnsafeIndexM v i)
 
 unsafeIndex v i = UNSAFE_CHECK(checkIndex) "unsafeIndex" i (length v)
                 $ unId (basicUnsafeIndexM v i)
 
--- | Yield the first element of a vector without checking if the vector is
--- empty
+-- | /O(1)/ First element without checking if the vector is empty
 unsafeHead :: Vector v a => v a -> a
 unsafeHead :: Vector v a => v a -> a
-{-# INLINE_STREAM unsafeHead #-}
+{-# INLINE_FUSED unsafeHead #-}
 unsafeHead v = unsafeIndex v 0
 
 unsafeHead v = unsafeIndex v 0
 
--- | Yield the last element of a vector without checking if the vector is
--- empty
+-- | /O(1)/ Last element without checking if the vector is empty
 unsafeLast :: Vector v a => v a -> a
 unsafeLast :: Vector v a => v a -> a
-{-# INLINE_STREAM unsafeLast #-}
+{-# INLINE_FUSED unsafeLast #-}
 unsafeLast v = unsafeIndex v (length v - 1)
 
 {-# RULES
 
 unsafeLast v = unsafeIndex v (length v - 1)
 
 {-# RULES
 
-"(!)/unstream [Vector]" forall i s.
-  new' v (New.unstream s) ! i = s Stream.!! i
+"(!)/unstream [Vector]" forall i s.
+  new (New.unstream s) ! i = s Bundle.!! i
 
 
-"head/unstream [Vector]" forall v s.
-  head (new' v (New.unstream s)) = Stream.head s
+"(!?)/unstream [Vector]" forall i s.
+  new (New.unstream s) !? i = s Bundle.!? i
 
 
-"last/unstream [Vector]" forall v s.
-  last (new' v (New.unstream s)) = Stream.last s
+"head/unstream [Vector]" forall s.
+  head (new (New.unstream s)) = Bundle.head s
 
 
-"unsafeIndex/unstream [Vector]" forall v i s.
-  unsafeIndex (new' v (New.unstream s)) i = s Stream.!! i
+"last/unstream [Vector]" forall s.
+  last (new (New.unstream s)) = Bundle.last s
 
 
-"unsafeHead/unstream [Vector]" forall v s.
-  unsafeHead (new' v (New.unstream s)) = Stream.head s
+"unsafeIndex/unstream [Vector]" forall i s.
+  unsafeIndex (new (New.unstream s)) i = s Bundle.!! i
 
 
-"unsafeLast/unstream [Vector]" forall v s.
-  unsafeLast (new' v (New.unstream s)) = Stream.last s
+"unsafeHead/unstream [Vector]" forall s.
+  unsafeHead (new (New.unstream s)) = Bundle.head s
+
+"unsafeLast/unstream [Vector]" forall s.
+  unsafeLast (new (New.unstream s)) = Bundle.last s
 
  #-}
 
 
  #-}
 
--- | Monadic indexing which can be strict in the vector while remaining lazy in
--- the element.
+-- Monadic indexing
+-- ----------------
+
+-- | /O(1)/ Indexing in a monad.
+--
+-- The monad allows operations to be strict in the vector when necessary.
+-- Suppose vector copying is implemented like this:
+--
+-- > copy mv v = ... write mv i (v ! i) ...
+--
+-- For lazy vectors, @v ! i@ would not be evaluated which means that @mv@
+-- would unnecessarily retain a reference to @v@ in each element written.
+--
+-- With 'indexM', copying can be implemented like this instead:
+--
+-- > copy mv v = ... do
+-- >                   x <- indexM v i
+-- >                   write mv i x
+--
+-- Here, no references to @v@ are retained because indexing (but /not/ the
+-- elements) is evaluated eagerly.
+--
 indexM :: (Vector v a, Monad m) => v a -> Int -> m a
 indexM :: (Vector v a, Monad m) => v a -> Int -> m a
-{-# INLINE_STREAM indexM #-}
+{-# INLINE_FUSED indexM #-}
 indexM v i = BOUNDS_CHECK(checkIndex) "indexM" i (length v)
            $ basicUnsafeIndexM v i
 
 indexM v i = BOUNDS_CHECK(checkIndex) "indexM" i (length v)
            $ basicUnsafeIndexM v i
 
+-- | /O(1)/ First element of a vector in a monad. See 'indexM' for an
+-- explanation of why this is useful.
 headM :: (Vector v a, Monad m) => v a -> m a
 headM :: (Vector v a, Monad m) => v a -> m a
-{-# INLINE_STREAM headM #-}
+{-# INLINE_FUSED headM #-}
 headM v = indexM v 0
 
 headM v = indexM v 0
 
+-- | /O(1)/ Last element of a vector in a monad. See 'indexM' for an
+-- explanation of why this is useful.
 lastM :: (Vector v a, Monad m) => v a -> m a
 lastM :: (Vector v a, Monad m) => v a -> m a
-{-# INLINE_STREAM lastM #-}
+{-# INLINE_FUSED lastM #-}
 lastM v = indexM v (length v - 1)
 
 lastM v = indexM v (length v - 1)
 
--- | Unsafe monadic indexing without bounds checks
+-- | /O(1)/ Indexing in a monad without bounds checks. See 'indexM' for an
+-- explanation of why this is useful.
 unsafeIndexM :: (Vector v a, Monad m) => v a -> Int -> m a
 unsafeIndexM :: (Vector v a, Monad m) => v a -> Int -> m a
-{-# INLINE_STREAM unsafeIndexM #-}
+{-# INLINE_FUSED unsafeIndexM #-}
 unsafeIndexM v i = UNSAFE_CHECK(checkIndex) "unsafeIndexM" i (length v)
                  $ basicUnsafeIndexM v i
 
 unsafeIndexM v i = UNSAFE_CHECK(checkIndex) "unsafeIndexM" i (length v)
                  $ basicUnsafeIndexM v i
 
+-- | /O(1)/ First element in a monad without checking for empty vectors.
+-- See 'indexM' for an explanation of why this is useful.
 unsafeHeadM :: (Vector v a, Monad m) => v a -> m a
 unsafeHeadM :: (Vector v a, Monad m) => v a -> m a
-{-# INLINE_STREAM unsafeHeadM #-}
+{-# INLINE_FUSED unsafeHeadM #-}
 unsafeHeadM v = unsafeIndexM v 0
 
 unsafeHeadM v = unsafeIndexM v 0
 
+-- | /O(1)/ Last element in a monad without checking for empty vectors.
+-- See 'indexM' for an explanation of why this is useful.
 unsafeLastM :: (Vector v a, Monad m) => v a -> m a
 unsafeLastM :: (Vector v a, Monad m) => v a -> m a
-{-# INLINE_STREAM unsafeLastM #-}
+{-# INLINE_FUSED unsafeLastM #-}
 unsafeLastM v = unsafeIndexM v (length v - 1)
 
 unsafeLastM v = unsafeIndexM v (length v - 1)
 
--- FIXME: the rhs of these rules are lazy in the stream which is WRONG
-{- RULES
+{-# RULES
 
 
-"indexM/unstream [Vector]" forall v i s.
-  indexM (new' v (New.unstream s)) i = return (s Stream.!! i)
+"indexM/unstream [Vector]" forall s i.
+  indexM (new (New.unstream s)) i = lift s MBundle.!! i
 
 
-"headM/unstream [Vector]" forall s.
-  headM (new' v (New.unstream s)) = return (Stream.head s)
+"headM/unstream [Vector]" forall s.
+  headM (new (New.unstream s)) = MBundle.head (lift s)
 
 
-"lastM/unstream [Vector]" forall s.
-  lastM (new' v (New.unstream s)) = return (Stream.last s)
+"lastM/unstream [Vector]" forall s.
+  lastM (new (New.unstream s)) = MBundle.last (lift s)
 
 
- -}
+"unsafeIndexM/unstream [Vector]" forall s i.
+  unsafeIndexM (new (New.unstream s)) i = lift s MBundle.!! i
 
 
--- Subarrays
--- ---------
+"unsafeHeadM/unstream [Vector]" forall s.
+  unsafeHeadM (new (New.unstream s)) = MBundle.head (lift s)
 
 
--- FIXME: slicing doesn't work with the inplace stuff at the moment
+"unsafeLastM/unstream [Vector]" forall s.
+  unsafeLastM (new (New.unstream s)) = MBundle.last (lift s)
 
 
--- | Yield a part of the vector without copying it.
-slice :: Vector v a => Int   -- ^ starting index
-                    -> Int   -- ^ length
+  #-}
+
+-- Extracting subvectors (slicing)
+-- -------------------------------
+
+-- | /O(1)/ Yield a slice of the vector without copying it. The vector must
+-- contain at least @i+n@ elements.
+slice :: Vector v a => Int   -- ^ @i@ starting index
+                    -> Int   -- ^ @n@ length
                     -> v a
                     -> v a
                     -> v a
                     -> v a
-{-# INLINE_STREAM slice #-}
+{-# INLINE_FUSED slice #-}
 slice i n v = BOUNDS_CHECK(checkSlice) "slice" i n (length v)
             $ basicUnsafeSlice i n v
 
 slice i n v = BOUNDS_CHECK(checkSlice) "slice" i n (length v)
             $ basicUnsafeSlice i n v
 
--- | Yield all but the last element without copying.
+-- | /O(1)/ Yield all but the last element without copying. The vector may not
+-- be empty.
 init :: Vector v a => v a -> v a
 init :: Vector v a => v a -> v a
-{-# INLINE_STREAM init #-}
+{-# INLINE_FUSED init #-}
 init v = slice 0 (length v - 1) v
 
 init v = slice 0 (length v - 1) v
 
--- | All but the first element (without copying).
+-- | /O(1)/ Yield all but the first element without copying. The vector may not
+-- be empty.
 tail :: Vector v a => v a -> v a
 tail :: Vector v a => v a -> v a
-{-# INLINE_STREAM tail #-}
+{-# INLINE_FUSED tail #-}
 tail v = slice 1 (length v - 1) v
 
 tail v = slice 1 (length v - 1) v
 
--- | Yield the first @n@ elements without copying.
+-- | /O(1)/ Yield the first @n@ elements without copying. The vector may
+-- contain less than @n@ elements in which case it is returned unchanged.
 take :: Vector v a => Int -> v a -> v a
 take :: Vector v a => Int -> v a -> v a
-{-# INLINE_STREAM take #-}
+{-# INLINE_FUSED take #-}
 take n v = unsafeSlice 0 (delay_inline min n' (length v)) v
   where n' = max n 0
 
 take n v = unsafeSlice 0 (delay_inline min n' (length v)) v
   where n' = max n 0
 
--- | Yield all but the first @n@ elements without copying.
+-- | /O(1)/ Yield all but the first @n@ elements without copying. The vector may
+-- contain less than @n@ elements in which case an empty vector is returned.
 drop :: Vector v a => Int -> v a -> v a
 drop :: Vector v a => Int -> v a -> v a
-{-# INLINE_STREAM drop #-}
+{-# INLINE_FUSED drop #-}
 drop n v = unsafeSlice (delay_inline min n' len)
                        (delay_inline max 0 (len - n')) v
   where n' = max n 0
         len = length v
 
 drop n v = unsafeSlice (delay_inline min n' len)
                        (delay_inline max 0 (len - n')) v
   where n' = max n 0
         len = length v
 
--- | Unsafely yield a part of the vector without copying it and without
--- performing bounds checks.
-unsafeSlice :: Vector v a => Int   -- ^ starting index
-                          -> Int   -- ^ length
+-- | /O(1)/ Yield the first @n@ elements paired with the remainder without copying.
+--
+-- Note that @'splitAt' n v@ is equivalent to @('take' n v, 'drop' n v)@
+-- but slightly more efficient.
+{-# INLINE_FUSED splitAt #-}
+splitAt :: Vector v a => Int -> v a -> (v a, v a)
+splitAt n v = ( unsafeSlice 0 m v
+              , unsafeSlice m (delay_inline max 0 (len - n')) v
+              )
+    where
+      m   = delay_inline min n' len
+      n'  = max n 0
+      len = length v
+
+-- | /O(1)/ Yield a slice of the vector without copying. The vector must
+-- contain at least @i+n@ elements but this is not checked.
+unsafeSlice :: Vector v a => Int   -- ^ @i@ starting index
+                          -> Int   -- ^ @n@ length
                           -> v a
                           -> v a
                           -> v a
                           -> v a
-{-# INLINE_STREAM unsafeSlice #-}
+{-# INLINE_FUSED unsafeSlice #-}
 unsafeSlice i n v = UNSAFE_CHECK(checkSlice) "unsafeSlice" i n (length v)
                   $ basicUnsafeSlice i n v
 
 unsafeSlice i n v = UNSAFE_CHECK(checkSlice) "unsafeSlice" i n (length v)
                   $ basicUnsafeSlice i n v
 
+-- | /O(1)/ Yield all but the last element without copying. The vector may not
+-- be empty but this is not checked.
 unsafeInit :: Vector v a => v a -> v a
 unsafeInit :: Vector v a => v a -> v a
-{-# INLINE_STREAM unsafeInit #-}
+{-# INLINE_FUSED unsafeInit #-}
 unsafeInit v = unsafeSlice 0 (length v - 1) v
 
 unsafeInit v = unsafeSlice 0 (length v - 1) v
 
+-- | /O(1)/ Yield all but the first element without copying. The vector may not
+-- be empty but this is not checked.
 unsafeTail :: Vector v a => v a -> v a
 unsafeTail :: Vector v a => v a -> v a
-{-# INLINE_STREAM unsafeTail #-}
+{-# INLINE_FUSED unsafeTail #-}
 unsafeTail v = unsafeSlice 1 (length v - 1) v
 
 unsafeTail v = unsafeSlice 1 (length v - 1) v
 
+-- | /O(1)/ Yield the first @n@ elements without copying. The vector must
+-- contain at least @n@ elements but this is not checked.
 unsafeTake :: Vector v a => Int -> v a -> v a
 {-# INLINE unsafeTake #-}
 unsafeTake n v = unsafeSlice 0 n v
 
 unsafeTake :: Vector v a => Int -> v a -> v a
 {-# INLINE unsafeTake #-}
 unsafeTake n v = unsafeSlice 0 n v
 
+-- | /O(1)/ Yield all but the first @n@ elements without copying. The vector
+-- must contain at least @n@ elements but this is not checked.
 unsafeDrop :: Vector v a => Int -> v a -> v a
 {-# INLINE unsafeDrop #-}
 unsafeDrop n v = unsafeSlice n (length v - n) v
 
 {-# RULES
 
 unsafeDrop :: Vector v a => Int -> v a -> v a
 {-# INLINE unsafeDrop #-}
 unsafeDrop n v = unsafeSlice n (length v - n) v
 
 {-# RULES
 
-"slice/new [Vector]" forall i n p.
-  slice i n (new' v p) = new' v (New.slice i n p)
+"slice/new [Vector]" forall i n p.
+  slice i n (new p) = new (New.slice i n p)
 
 
-"init/new [Vector]" forall p.
-  init (new' v p) = new' v (New.init p)
+"init/new [Vector]" forall p.
+  init (new p) = new (New.init p)
 
 
-"tail/new [Vector]" forall p.
-  tail (new' v p) = new' v (New.tail p)
+"tail/new [Vector]" forall p.
+  tail (new p) = new (New.tail p)
 
 
-"take/new [Vector]" forall n p.
-  take n (new' v p) = new' v (New.take n p)
+"take/new [Vector]" forall n p.
+  take n (new p) = new (New.take n p)
 
 
-"drop/new [Vector]" forall n p.
-  drop n (new' v p) = new' v (New.drop n p)
+"drop/new [Vector]" forall n p.
+  drop n (new p) = new (New.drop n p)
 
 
-"unsafeSlice/new [Vector]" forall i n p.
-  unsafeSlice i n (new' v p) = new' v (New.unsafeSlice i n p)
+"unsafeSlice/new [Vector]" forall i n p.
+  unsafeSlice i n (new p) = new (New.unsafeSlice i n p)
 
 
-"unsafeInit/new [Vector]" forall p.
-  unsafeInit (new' v p) = new' v (New.unsafeInit p)
+"unsafeInit/new [Vector]" forall p.
+  unsafeInit (new p) = new (New.unsafeInit p)
 
 
-"unsafeTail/new [Vector]" forall p.
-  unsafeTail (new' v p) = new' v (New.unsafeTail p)
+"unsafeTail/new [Vector]" forall p.
+  unsafeTail (new p) = new (New.unsafeTail p)
 
   #-}
 
 
   #-}
 
--- Permutations
--- ------------
+-- Initialisation
+-- --------------
 
 
-unsafeAccum_stream
-  :: Vector v a => (a -> b -> a) -> v a -> Stream (Int,b) -> v a
-{-# INLINE unsafeAccum_stream #-}
-unsafeAccum_stream f v s = new (New.accum f (New.unstream (stream v)) s)
+-- | /O(1)/ Empty vector
+empty :: Vector v a => v a
+{-# INLINE empty #-}
+empty = unstream Bundle.empty
 
 
-unsafeAccum :: Vector v a => (a -> b -> a) -> v a -> [(Int,b)] -> v a
-{-# INLINE unsafeAccum #-}
-unsafeAccum f v us = unsafeAccum_stream f v (Stream.fromList us)
+-- | /O(1)/ Vector with exactly one element
+singleton :: forall v a. Vector v a => a -> v a
+{-# INLINE singleton #-}
+singleton x = elemseq (undefined :: v a) x
+            $ unstream (Bundle.singleton x)
 
 
-unsafeAccumulate :: (Vector v a, Vector v (Int, b))
-                => (a -> b -> a) -> v a -> v (Int,b) -> v a
-{-# INLINE unsafeAccumulate #-}
-unsafeAccumulate f v us = unsafeAccum_stream f v (stream us)
+-- | /O(n)/ Vector of the given length with the same value in each position
+replicate :: forall v a. Vector v a => Int -> a -> v a
+{-# INLINE replicate #-}
+replicate n x = elemseq (undefined :: v a) x
+              $ unstream
+              $ Bundle.replicate n x
 
 
-unsafeAccumulate_ :: (Vector v a, Vector v Int, Vector v b)
-                => (a -> b -> a) -> v a -> v Int -> v b -> v a
-{-# INLINE unsafeAccumulate_ #-}
-unsafeAccumulate_ f v is xs
-  = unsafeAccum_stream f v (Stream.zipWith (,) (stream is) (stream xs))
+-- | /O(n)/ Construct a vector of the given length by applying the function to
+-- each index
+generate :: Vector v a => Int -> (Int -> a) -> v a
+{-# INLINE generate #-}
+generate n f = unstream (Bundle.generate n f)
 
 
-accum_stream :: Vector v a => (a -> b -> a) -> v a -> Stream (Int,b) -> v a
-{-# INLINE accum_stream #-}
-accum_stream f v s = new (New.accum f (New.unstream (stream v)) s)
+-- | /O(n)/ Apply function n times to value. Zeroth element is original value.
+iterateN :: Vector v a => Int -> (a -> a) -> a -> v a
+{-# INLINE iterateN #-}
+iterateN n f x = unstream (Bundle.iterateN n f x)
 
 
-accum :: Vector v a => (a -> b -> a) -> v a -> [(Int,b)] -> v a
-{-# INLINE accum #-}
-accum f v us = accum_stream f v (Stream.fromList us)
+-- Unfolding
+-- ---------
 
 
-accumulate :: (Vector v a, Vector v (Int, b))
-                => (a -> b -> a) -> v a -> v (Int,b) -> v a
-{-# INLINE accumulate #-}
-accumulate f v us = accum_stream f v (stream us)
+-- | /O(n)/ Construct a vector by repeatedly applying the generator function
+-- to a seed. The generator function yields 'Just' the next element and the
+-- new seed or 'Nothing' if there are no more elements.
+--
+-- > unfoldr (\n -> if n == 0 then Nothing else Just (n,n-1)) 10
+-- >  = <10,9,8,7,6,5,4,3,2,1>
+unfoldr :: Vector v a => (b -> Maybe (a, b)) -> b -> v a
+{-# INLINE unfoldr #-}
+unfoldr f = unstream . Bundle.unfoldr f
 
 
-accumulate_ :: (Vector v a, Vector v Int, Vector v b)
-                => (a -> b -> a) -> v a -> v Int -> v b -> v a
-{-# INLINE accumulate_ #-}
-accumulate_ f v is xs = accum_stream f v (Stream.zipWith (,) (stream is)
-                                                             (stream xs))
-                                        
+-- | /O(n)/ Construct a vector with at most @n@ by repeatedly applying the
+-- generator function to the a seed. The generator function yields 'Just' the
+-- next element and the new seed or 'Nothing' if there are no more elements.
+--
+-- > unfoldrN 3 (\n -> Just (n,n-1)) 10 = <10,9,8>
+unfoldrN  :: Vector v a => Int -> (b -> Maybe (a, b)) -> b -> v a
+{-# INLINE unfoldrN #-}
+unfoldrN n f = unstream . Bundle.unfoldrN n f
 
 
-unsafeUpdate_stream :: Vector v a => v a -> Stream (Int,a) -> v a
-{-# INLINE unsafeUpdate_stream #-}
-unsafeUpdate_stream v s = new (New.unsafeUpdate (New.unstream (stream v)) s)
+-- | /O(n)/ Construct a vector with @n@ elements by repeatedly applying the
+-- generator function to the already constructed part of the vector.
+--
+-- > constructN 3 f = let a = f <> ; b = f <a> ; c = f <a,b> in f <a,b,c>
+--
+constructN :: forall v a. Vector v a => Int -> (v a -> a) -> v a
+{-# INLINE constructN #-}
+-- NOTE: We *CANNOT* wrap this in New and then fuse because the elements
+-- might contain references to the immutable vector!
+constructN !n f = runST (
+  do
+    v  <- M.new n
+    v' <- unsafeFreeze v
+    fill v' 0
+  )
+  where
+    fill :: forall s. v a -> Int -> ST s (v a)
+    fill !v i | i < n = let x = f (unsafeTake i v)
+                        in
+                        elemseq v x $
+                        do
+                          v'  <- unsafeThaw v
+                          M.unsafeWrite v' i x
+                          v'' <- unsafeFreeze v'
+                          fill v'' (i+1)
+
+    fill v i = return v
+
+-- | /O(n)/ Construct a vector with @n@ elements from right to left by
+-- repeatedly applying the generator function to the already constructed part
+-- of the vector.
+--
+-- > constructrN 3 f = let a = f <> ; b = f<a> ; c = f <b,a> in f <c,b,a>
+--
+constructrN :: forall v a. Vector v a => Int -> (v a -> a) -> v a
+{-# INLINE constructrN #-}
+-- NOTE: We *CANNOT* wrap this in New and then fuse because the elements
+-- might contain references to the immutable vector!
+constructrN !n f = runST (
+  do
+    v  <- n `seq` M.new n
+    v' <- unsafeFreeze v
+    fill v' 0
+  )
+  where
+    fill :: forall s. v a -> Int -> ST s (v a)
+    fill !v i | i < n = let x = f (unsafeSlice (n-i) i v)
+                        in
+                        elemseq v x $
+                        do
+                          v'  <- unsafeThaw v
+                          M.unsafeWrite v' (n-i-1) x
+                          v'' <- unsafeFreeze v'
+                          fill v'' (i+1)
+
+    fill v i = return v
+
+
+-- Enumeration
+-- -----------
+
+-- | /O(n)/ Yield a vector of the given length containing the values @x@, @x+1@
+-- etc. This operation is usually more efficient than 'enumFromTo'.
+--
+-- > enumFromN 5 3 = <5,6,7>
+enumFromN :: (Vector v a, Num a) => a -> Int -> v a
+{-# INLINE enumFromN #-}
+enumFromN x n = enumFromStepN x 1 n
+
+-- | /O(n)/ Yield a vector of the given length containing the values @x@, @x+y@,
+-- @x+y+y@ etc. This operations is usually more efficient than 'enumFromThenTo'.
+--
+-- > enumFromStepN 1 0.1 5 = <1,1.1,1.2,1.3,1.4>
+enumFromStepN :: forall v a. (Vector v a, Num a) => a -> a -> Int -> v a
+{-# INLINE enumFromStepN #-}
+enumFromStepN x y n = elemseq (undefined :: v a) x
+                    $ elemseq (undefined :: v a) y
+                    $ unstream
+                    $ Bundle.enumFromStepN  x y n
+
+-- | /O(n)/ Enumerate values from @x@ to @y@.
+--
+-- /WARNING:/ This operation can be very inefficient. If at all possible, use
+-- 'enumFromN' instead.
+enumFromTo :: (Vector v a, Enum a) => a -> a -> v a
+{-# INLINE enumFromTo #-}
+enumFromTo x y = unstream (Bundle.enumFromTo x y)
+
+-- | /O(n)/ Enumerate values from @x@ to @y@ with a specific step @z@.
+--
+-- /WARNING:/ This operation can be very inefficient. If at all possible, use
+-- 'enumFromStepN' instead.
+enumFromThenTo :: (Vector v a, Enum a) => a -> a -> a -> v a
+{-# INLINE enumFromThenTo #-}
+enumFromThenTo x y z = unstream (Bundle.enumFromThenTo x y z)
+
+-- Concatenation
+-- -------------
+
+-- | /O(n)/ Prepend an element
+cons :: forall v a. Vector v a => a -> v a -> v a
+{-# INLINE cons #-}
+cons x v = elemseq (undefined :: v a) x
+         $ unstream
+         $ Bundle.cons x
+         $ stream v
 
 
+-- | /O(n)/ Append an element
+snoc :: forall v a. Vector v a => v a -> a -> v a
+{-# INLINE snoc #-}
+snoc v x = elemseq (undefined :: v a) x
+         $ unstream
+         $ Bundle.snoc (stream v) x
+
+infixr 5 ++
+-- | /O(m+n)/ Concatenate two vectors
+(++) :: Vector v a => v a -> v a -> v a
+{-# INLINE (++) #-}
+v ++ w = unstream (stream v Bundle.++ stream w)
+
+-- | /O(n)/ Concatenate all vectors in the list
+concat :: Vector v a => [v a] -> v a
+{-# INLINE concat #-}
+concat = unstream . Bundle.fromVectors
+{-
+concat vs = unstream (Bundle.flatten mk step (Exact n) (Bundle.fromList vs))
+  where
+    n = List.foldl' (\k v -> k + length v) 0 vs
+
+    {-# INLINE_INNER step #-}
+    step (v,i,k)
+      | i < k = case unsafeIndexM v i of
+                  Box x -> Bundle.Yield x (v,i+1,k)
+      | otherwise = Bundle.Done
+
+    {-# INLINE mk #-}
+    mk v = let k = length v
+           in
+           k `seq` (v,0,k)
+-}
+
+-- Monadic initialisation
+-- ----------------------
+
+-- | /O(n)/ Execute the monadic action the given number of times and store the
+-- results in a vector.
+replicateM :: (Monad m, Vector v a) => Int -> m a -> m (v a)
+{-# INLINE replicateM #-}
+replicateM n m = unstreamM (MBundle.replicateM n m)
+
+-- | /O(n)/ Construct a vector of the given length by applying the monadic
+-- action to each index
+generateM :: (Monad m, Vector v a) => Int -> (Int -> m a) -> m (v a)
+{-# INLINE generateM #-}
+generateM n f = unstreamM (MBundle.generateM n f)
+
+-- | Execute the monadic action and freeze the resulting vector.
+--
+-- @
+-- create (do { v \<- 'M.new' 2; 'M.write' v 0 \'a\'; 'M.write' v 1 \'b\'; return v }) = \<'a','b'\>
+-- @
+create :: Vector v a => (forall s. ST s (Mutable v s a)) -> v a
+{-# INLINE create #-}
+create p = new (New.create p)
+
+-- Restricting memory usage
+-- ------------------------
+
+-- | /O(n)/ Yield the argument but force it not to retain any extra memory,
+-- possibly by copying it.
+--
+-- This is especially useful when dealing with slices. For example:
+--
+-- > force (slice 0 2 <huge vector>)
+--
+-- Here, the slice retains a reference to the huge vector. Forcing it creates
+-- a copy of just the elements that belong to the slice and allows the huge
+-- vector to be garbage collected.
+force :: Vector v a => v a -> v a
+-- FIXME: we probably ought to inline this later as the rules still might fire
+-- otherwise
+{-# INLINE_FUSED force #-}
+force v = new (clone v)
+
+-- Bulk updates
+-- ------------
+
+-- | /O(m+n)/ For each pair @(i,a)@ from the list, replace the vector
+-- element at position @i@ by @a@.
+--
+-- > <5,9,2,7> // [(2,1),(0,3),(2,8)] = <3,9,8,7>
+--
+(//) :: Vector v a => v a        -- ^ initial vector (of length @m@)
+                   -> [(Int, a)] -- ^ list of index/value pairs (of length @n@)
+                   -> v a
+{-# INLINE (//) #-}
+v // us = update_stream v (Bundle.fromList us)
+
+-- | /O(m+n)/ For each pair @(i,a)@ from the vector of index/value pairs,
+-- replace the vector element at position @i@ by @a@.
+--
+-- > update <5,9,2,7> <(2,1),(0,3),(2,8)> = <3,9,8,7>
+--
+update :: (Vector v a, Vector v (Int, a))
+        => v a        -- ^ initial vector (of length @m@)
+        -> v (Int, a) -- ^ vector of index/value pairs (of length @n@)
+        -> v a
+{-# INLINE update #-}
+update v w = update_stream v (stream w)
+
+-- | /O(m+min(n1,n2))/ For each index @i@ from the index vector and the
+-- corresponding value @a@ from the value vector, replace the element of the
+-- initial vector at position @i@ by @a@.
+--
+-- > update_ <5,9,2,7>  <2,0,2> <1,3,8> = <3,9,8,7>
+--
+-- This function is useful for instances of 'Vector' that cannot store pairs.
+-- Otherwise, 'update' is probably more convenient.
+--
+-- @
+-- update_ xs is ys = 'update' xs ('zip' is ys)
+-- @
+update_ :: (Vector v a, Vector v Int)
+        => v a   -- ^ initial vector (of length @m@)
+        -> v Int -- ^ index vector (of length @n1@)
+        -> v a   -- ^ value vector (of length @n2@)
+        -> v a
+{-# INLINE update_ #-}
+update_ v is w = update_stream v (Bundle.zipWith (,) (stream is) (stream w))
+
+update_stream :: Vector v a => v a -> Bundle u (Int,a) -> v a
+{-# INLINE update_stream #-}
+update_stream = modifyWithBundle M.update
+
+-- | Same as ('//') but without bounds checking.
 unsafeUpd :: Vector v a => v a -> [(Int, a)] -> v a
 {-# INLINE unsafeUpd #-}
 unsafeUpd :: Vector v a => v a -> [(Int, a)] -> v a
 {-# INLINE unsafeUpd #-}
-unsafeUpd v us = unsafeUpdate_stream v (Stream.fromList us)
+unsafeUpd v us = unsafeUpdate_stream v (Bundle.fromList us)
 
 
+-- | Same as 'update' but without bounds checking.
 unsafeUpdate :: (Vector v a, Vector v (Int, a)) => v a -> v (Int, a) -> v a
 {-# INLINE unsafeUpdate #-}
 unsafeUpdate v w = unsafeUpdate_stream v (stream w)
 
 unsafeUpdate :: (Vector v a, Vector v (Int, a)) => v a -> v (Int, a) -> v a
 {-# INLINE unsafeUpdate #-}
 unsafeUpdate v w = unsafeUpdate_stream v (stream w)
 
+-- | Same as 'update_' but without bounds checking.
 unsafeUpdate_ :: (Vector v a, Vector v Int) => v a -> v Int -> v a -> v a
 {-# INLINE unsafeUpdate_ #-}
 unsafeUpdate_ v is w
 unsafeUpdate_ :: (Vector v a, Vector v Int) => v a -> v Int -> v a -> v a
 {-# INLINE unsafeUpdate_ #-}
 unsafeUpdate_ v is w
-  = unsafeUpdate_stream v (Stream.zipWith (,) (stream is) (stream w))
+  = unsafeUpdate_stream v (Bundle.zipWith (,) (stream is) (stream w))
 
 
-update_stream :: Vector v a => v a -> Stream (Int,a) -> v a
-{-# INLINE update_stream #-}
-update_stream v s = new (New.update (New.unstream (stream v)) s)
+unsafeUpdate_stream :: Vector v a => v a -> Bundle u (Int,a) -> v a
+{-# INLINE unsafeUpdate_stream #-}
+unsafeUpdate_stream = modifyWithBundle M.unsafeUpdate
 
 
-(//) :: Vector v a => v a -> [(Int, a)] -> v a
-{-# INLINE (//) #-}
-v // us = update_stream v (Stream.fromList us)
+-- Accumulations
+-- -------------
 
 
-update :: (Vector v a, Vector v (Int, a)) => v a -> v (Int, a) -> v a
-{-# INLINE update #-}
-update v w = update_stream v (stream w)
+-- | /O(m+n)/ For each pair @(i,b)@ from the list, replace the vector element
+-- @a@ at position @i@ by @f a b@.
+--
+-- > accum (+) <5,9,2> [(2,4),(1,6),(0,3),(1,7)] = <5+3, 9+6+7, 2+4>
+accum :: Vector v a
+      => (a -> b -> a) -- ^ accumulating function @f@
+      -> v a           -- ^ initial vector (of length @m@)
+      -> [(Int,b)]     -- ^ list of index/value pairs (of length @n@)
+      -> v a
+{-# INLINE accum #-}
+accum f v us = accum_stream f v (Bundle.fromList us)
 
 
-update_ :: (Vector v a, Vector v Int) => v a -> v Int -> v a -> v a
-{-# INLINE update_ #-}
-update_ v is w = update_stream v (Stream.zipWith (,) (stream is) (stream w))
+-- | /O(m+n)/ For each pair @(i,b)@ from the vector of pairs, replace the vector
+-- element @a@ at position @i@ by @f a b@.
+--
+-- > accumulate (+) <5,9,2> <(2,4),(1,6),(0,3),(1,7)> = <5+3, 9+6+7, 2+4>
+accumulate :: (Vector v a, Vector v (Int, b))
+           => (a -> b -> a) -- ^ accumulating function @f@
+           -> v a           -- ^ initial vector (of length @m@)
+           -> v (Int,b)     -- ^ vector of index/value pairs (of length @n@)
+           -> v a
+{-# INLINE accumulate #-}
+accumulate f v us = accum_stream f v (stream us)
 
 
--- This somewhat non-intuitive definition ensures that the resulting vector
--- does not retain references to the original one even if it is lazy in its
--- elements. This would not be the case if we simply used
+-- | /O(m+min(n1,n2))/ For each index @i@ from the index vector and the
+-- corresponding value @b@ from the the value vector,
+-- replace the element of the initial vector at
+-- position @i@ by @f a b@.
+--
+-- > accumulate_ (+) <5,9,2> <2,1,0,1> <4,6,3,7> = <5+3, 9+6+7, 2+4>
 --
 --
--- backpermute v is = map (v!) is
-backpermute :: (Vector v a, Vector v Int) => v a -> v Int -> v a
+-- This function is useful for instances of 'Vector' that cannot store pairs.
+-- Otherwise, 'accumulate' is probably more convenient:
+--
+-- @
+-- accumulate_ f as is bs = 'accumulate' f as ('zip' is bs)
+-- @
+accumulate_ :: (Vector v a, Vector v Int, Vector v b)
+                => (a -> b -> a) -- ^ accumulating function @f@
+                -> v a           -- ^ initial vector (of length @m@)
+                -> v Int         -- ^ index vector (of length @n1@)
+                -> v b           -- ^ value vector (of length @n2@)
+                -> v a
+{-# INLINE accumulate_ #-}
+accumulate_ f v is xs = accum_stream f v (Bundle.zipWith (,) (stream is)
+                                                             (stream xs))
+                                        
+
+accum_stream :: Vector v a => (a -> b -> a) -> v a -> Bundle u (Int,b) -> v a
+{-# INLINE accum_stream #-}
+accum_stream f = modifyWithBundle (M.accum f)
+
+-- | Same as 'accum' but without bounds checking.
+unsafeAccum :: Vector v a => (a -> b -> a) -> v a -> [(Int,b)] -> v a
+{-# INLINE unsafeAccum #-}
+unsafeAccum f v us = unsafeAccum_stream f v (Bundle.fromList us)
+
+-- | Same as 'accumulate' but without bounds checking.
+unsafeAccumulate :: (Vector v a, Vector v (Int, b))
+                => (a -> b -> a) -> v a -> v (Int,b) -> v a
+{-# INLINE unsafeAccumulate #-}
+unsafeAccumulate f v us = unsafeAccum_stream f v (stream us)
+
+-- | Same as 'accumulate_' but without bounds checking.
+unsafeAccumulate_ :: (Vector v a, Vector v Int, Vector v b)
+                => (a -> b -> a) -> v a -> v Int -> v b -> v a
+{-# INLINE unsafeAccumulate_ #-}
+unsafeAccumulate_ f v is xs
+  = unsafeAccum_stream f v (Bundle.zipWith (,) (stream is) (stream xs))
+
+unsafeAccum_stream
+  :: Vector v a => (a -> b -> a) -> v a -> Bundle u (Int,b) -> v a
+{-# INLINE unsafeAccum_stream #-}
+unsafeAccum_stream f = modifyWithBundle (M.unsafeAccum f)
+
+-- Permutations
+-- ------------
+
+-- | /O(n)/ Reverse a vector
+reverse :: (Vector v a) => v a -> v a
+{-# INLINE reverse #-}
+-- FIXME: make this fuse better, add support for recycling
+reverse = unstream . streamR
+
+-- | /O(n)/ Yield the vector obtained by replacing each element @i@ of the
+-- index vector by @xs'!'i@. This is equivalent to @'map' (xs'!') is@ but is
+-- often much more efficient.
+--
+-- > backpermute <a,b,c,d> <0,3,2,3,1,0> = <a,d,c,d,b,a>
+backpermute :: (Vector v a, Vector v Int)
+            => v a   -- ^ @xs@ value vector
+            -> v Int -- ^ @is@ index vector (of length @n@)
+            -> v a
 {-# INLINE backpermute #-}
 {-# INLINE backpermute #-}
+-- This somewhat non-intuitive definition ensures that the resulting vector
+-- does not retain references to the original one even if it is lazy in its
+-- elements. This would not be the case if we simply used map (v!)
 backpermute v is = seq v
 backpermute v is = seq v
+                 $ seq n
                  $ unstream
                  $ unstream
-                 $ Stream.unbox
-                 $ Stream.map (indexM v)
+                 $ Bundle.unbox
+                 $ Bundle.map index
                  $ stream is
                  $ stream is
+  where
+    n = length v
 
 
+    {-# INLINE index #-}
+    -- NOTE: we do it this way to avoid triggering LiberateCase on n in
+    -- polymorphic code
+    index i = BOUNDS_CHECK(checkIndex) "backpermute" i n
+            $ basicUnsafeIndexM v i
+
+-- | Same as 'backpermute' but without bounds checking.
 unsafeBackpermute :: (Vector v a, Vector v Int) => v a -> v Int -> v a
 {-# INLINE unsafeBackpermute #-}
 unsafeBackpermute v is = seq v
 unsafeBackpermute :: (Vector v a, Vector v Int) => v a -> v Int -> v a
 {-# INLINE unsafeBackpermute #-}
 unsafeBackpermute v is = seq v
+                       $ seq n
                        $ unstream
                        $ unstream
-                       $ Stream.unbox
-                       $ Stream.map (unsafeIndexM v)
+                       $ Bundle.unbox
+                       $ Bundle.map index
                        $ stream is
                        $ stream is
+  where
+    n = length v
 
 
--- FIXME: make this fuse better, add support for recycling
-reverse :: (Vector v a) => v a -> v a
-{-# INLINE reverse #-}
-reverse = unstream . streamR
+    {-# INLINE index #-}
+    -- NOTE: we do it this way to avoid triggering LiberateCase on n in
+    -- polymorphic code
+    index i = UNSAFE_CHECK(checkIndex) "unsafeBackpermute" i n
+            $ basicUnsafeIndexM v i
+
+-- Safe destructive updates
+-- ------------------------
+
+-- | Apply a destructive operation to a vector. The operation will be
+-- performed in place if it is safe to do so and will modify a copy of the
+-- vector otherwise.
+--
+-- @
+-- modify (\\v -> 'M.write' v 0 \'x\') ('replicate' 3 \'a\') = \<\'x\',\'a\',\'a\'\>
+-- @
+modify :: Vector v a => (forall s. Mutable v s a -> ST s ()) -> v a -> v a
+{-# INLINE modify #-}
+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.
+modifyWithBundle :: Vector v a
+                 => (forall s. Mutable v s a -> Bundle u b -> ST s ())
+                 -> v a -> Bundle u b -> v a
+{-# INLINE modifyWithBundle #-}
+modifyWithBundle p v s = new (New.modifyWithBundle p (clone v) s)
+
+-- Indexing
+-- --------
+
+-- | /O(n)/ Pair each element in a vector with its index
+indexed :: (Vector v a, Vector v (Int,a)) => v a -> v (Int,a)
+{-# INLINE indexed #-}
+indexed = unstream . Bundle.indexed . stream
 
 -- Mapping
 -- -------
 
 
 -- Mapping
 -- -------
 
--- | Map a function over a vector
+-- | /O(n)/ Map a function over a vector
 map :: (Vector v a, Vector v b) => (a -> b) -> v a -> v b
 {-# INLINE map #-}
 map :: (Vector v a, Vector v b) => (a -> b) -> v a -> v b
 {-# INLINE map #-}
-map f = unstream . inplace (MStream.map f) . stream
+map f = unstream . inplace (MBundle.map f) . stream
 
 
--- | Apply a function to every index/value pair
+-- | /O(n)/ Apply a function to every element of a vector and its index
 imap :: (Vector v a, Vector v b) => (Int -> a -> b) -> v a -> v b
 {-# INLINE imap #-}
 imap :: (Vector v a, Vector v b) => (Int -> a -> b) -> v a -> v b
 {-# INLINE imap #-}
-imap f = unstream . inplace (MStream.map (uncurry f) . MStream.indexed)
+imap f = unstream . inplace (MBundle.map (uncurry f) . MBundle.indexed)
                   . stream
 
                   . stream
 
+-- | Map a function over a vector and concatenate the results.
 concatMap :: (Vector v a, Vector v b) => (a -> v b) -> v a -> v b
 {-# INLINE concatMap #-}
 concatMap :: (Vector v a, Vector v b) => (a -> v b) -> v a -> v b
 {-# INLINE concatMap #-}
-concatMap f = unstream . Stream.concatMap (stream . f) . stream
-
--- Zipping/unzipping
--- -----------------
+-- NOTE: We can't fuse concatMap anyway so don't pretend we do.
+-- This seems to be slightly slower
+-- concatMap f = concat . Bundle.toList . Bundle.map f . stream
+
+-- Slowest
+-- concatMap f = unstream . Bundle.concatMap (stream . f) . stream
+
+-- Used to be fastest
+{-
+concatMap f = unstream
+            . Bundle.flatten mk step Unknown
+            . stream
+  where
+    {-# INLINE_INNER step #-}
+    step (v,i,k)
+      | i < k = case unsafeIndexM v i of
+                  Box x -> Bundle.Yield x (v,i+1,k)
+      | otherwise = Bundle.Done
+
+    {-# INLINE mk #-}
+    mk x = let v = f x
+               k = length v
+           in
+           k `seq` (v,0,k)
+-}
+
+-- This seems to be fastest now
+concatMap f = unstream
+            . Bundle.concatVectors
+            . Bundle.map f
+            . stream
+
+-- Monadic mapping
+-- ---------------
+
+-- | /O(n)/ Apply the monadic action to all elements of the vector, yielding a
+-- vector of results
+mapM :: (Monad m, Vector v a, Vector v b) => (a -> m b) -> v a -> m (v b)
+{-# INLINE mapM #-}
+mapM f = unstreamM . Bundle.mapM f . stream
+
+-- | /O(n)/ Apply the monadic action to all elements of a vector and ignore the
+-- results
+mapM_ :: (Monad m, Vector v a) => (a -> m b) -> v a -> m ()
+{-# INLINE mapM_ #-}
+mapM_ f = Bundle.mapM_ f . stream
+
+-- | /O(n)/ Apply the monadic action to all elements of the vector, yielding a
+-- vector of results. Equvalent to @flip 'mapM'@.
+forM :: (Monad m, Vector v a, Vector v b) => v a -> (a -> m b) -> m (v b)
+{-# INLINE forM #-}
+forM as f = mapM f as
+
+-- | /O(n)/ Apply the monadic action to all elements of a vector and ignore the
+-- results. Equivalent to @flip 'mapM_'@.
+forM_ :: (Monad m, Vector v a) => v a -> (a -> m b) -> m ()
+{-# INLINE forM_ #-}
+forM_ as f = mapM_ f as
+
+-- Zipping
+-- -------
 
 
--- | Zip two vectors with the given function.
+-- | /O(min(m,n))/ Zip two vectors with the given function.
 zipWith :: (Vector v a, Vector v b, Vector v c)
         => (a -> b -> c) -> v a -> v b -> v c
 {-# INLINE zipWith #-}
 zipWith :: (Vector v a, Vector v b, Vector v c)
         => (a -> b -> c) -> v a -> v b -> v c
 {-# INLINE zipWith #-}
-zipWith f xs ys = unstream (Stream.zipWith f (stream xs) (stream ys))
+zipWith f xs ys = unstream (Bundle.zipWith f (stream xs) (stream ys))
 
 -- | Zip three vectors with the given function.
 zipWith3 :: (Vector v a, Vector v b, Vector v c, Vector v d)
          => (a -> b -> c -> d) -> v a -> v b -> v c -> v d
 {-# INLINE zipWith3 #-}
 
 -- | Zip three vectors with the given function.
 zipWith3 :: (Vector v a, Vector v b, Vector v c, Vector v d)
          => (a -> b -> c -> d) -> v a -> v b -> v c -> v d
 {-# INLINE zipWith3 #-}
-zipWith3 f as bs cs = unstream (Stream.zipWith3 f (stream as)
+zipWith3 f as bs cs = unstream (Bundle.zipWith3 f (stream as)
                                                   (stream bs)
                                                   (stream cs))
 
                                                   (stream bs)
                                                   (stream cs))
 
@@ -689,7 +1053,7 @@ zipWith4 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e)
          => (a -> b -> c -> d -> e) -> v a -> v b -> v c -> v d -> v e
 {-# INLINE zipWith4 #-}
 zipWith4 f as bs cs ds
          => (a -> b -> c -> d -> e) -> v a -> v b -> v c -> v d -> v e
 {-# INLINE zipWith4 #-}
 zipWith4 f as bs cs ds
-  = unstream (Stream.zipWith4 f (stream as)
+  = unstream (Bundle.zipWith4 f (stream as)
                                 (stream bs)
                                 (stream cs)
                                 (stream ds))
                                 (stream bs)
                                 (stream cs)
                                 (stream ds))
@@ -700,7 +1064,7 @@ zipWith5 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e,
                                          -> v f
 {-# INLINE zipWith5 #-}
 zipWith5 f as bs cs ds es
                                          -> v f
 {-# INLINE zipWith5 #-}
 zipWith5 f as bs cs ds es
-  = unstream (Stream.zipWith5 f (stream as)
+  = unstream (Bundle.zipWith5 f (stream as)
                                 (stream bs)
                                 (stream cs)
                                 (stream ds)
                                 (stream bs)
                                 (stream cs)
                                 (stream ds)
@@ -712,27 +1076,27 @@ zipWith6 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e,
          -> v a -> v b -> v c -> v d -> v e -> v f -> v g
 {-# INLINE zipWith6 #-}
 zipWith6 f as bs cs ds es fs
          -> v a -> v b -> v c -> v d -> v e -> v f -> v g
 {-# INLINE zipWith6 #-}
 zipWith6 f as bs cs ds es fs
-  = unstream (Stream.zipWith6 f (stream as)
+  = unstream (Bundle.zipWith6 f (stream as)
                                 (stream bs)
                                 (stream cs)
                                 (stream ds)
                                 (stream es)
                                 (stream fs))
 
                                 (stream bs)
                                 (stream cs)
                                 (stream ds)
                                 (stream es)
                                 (stream fs))
 
--- | Zip two vectors and their indices with the given function.
+-- | /O(min(m,n))/ Zip two vectors with a function that also takes the
+-- elements' indices.
 izipWith :: (Vector v a, Vector v b, Vector v c)
         => (Int -> a -> b -> c) -> v a -> v b -> v c
 {-# INLINE izipWith #-}
 izipWith f xs ys = unstream
 izipWith :: (Vector v a, Vector v b, Vector v c)
         => (Int -> a -> b -> c) -> v a -> v b -> v c
 {-# INLINE izipWith #-}
 izipWith f xs ys = unstream
-                  (Stream.zipWith (uncurry f) (Stream.indexed (stream xs))
+                  (Bundle.zipWith (uncurry f) (Bundle.indexed (stream xs))
                                                               (stream ys))
 
                                                               (stream ys))
 
--- | Zip three vectors and their indices with the given function.
 izipWith3 :: (Vector v a, Vector v b, Vector v c, Vector v d)
          => (Int -> a -> b -> c -> d) -> v a -> v b -> v c -> v d
 {-# INLINE izipWith3 #-}
 izipWith3 f as bs cs
 izipWith3 :: (Vector v a, Vector v b, Vector v c, Vector v d)
          => (Int -> a -> b -> c -> d) -> v a -> v b -> v c -> v d
 {-# INLINE izipWith3 #-}
 izipWith3 f as bs cs
-  = unstream (Stream.zipWith3 (uncurry f) (Stream.indexed (stream as))
+  = unstream (Bundle.zipWith3 (uncurry f) (Bundle.indexed (stream as))
                                                           (stream bs)
                                                           (stream cs))
 
                                                           (stream bs)
                                                           (stream cs))
 
@@ -740,7 +1104,7 @@ izipWith4 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e)
          => (Int -> a -> b -> c -> d -> e) -> v a -> v b -> v c -> v d -> v e
 {-# INLINE izipWith4 #-}
 izipWith4 f as bs cs ds
          => (Int -> a -> b -> c -> d -> e) -> v a -> v b -> v c -> v d -> v e
 {-# INLINE izipWith4 #-}
 izipWith4 f as bs cs ds
-  = unstream (Stream.zipWith4 (uncurry f) (Stream.indexed (stream as))
+  = unstream (Bundle.zipWith4 (uncurry f) (Bundle.indexed (stream as))
                                                           (stream bs)
                                                           (stream cs)
                                                           (stream ds))
                                                           (stream bs)
                                                           (stream cs)
                                                           (stream ds))
@@ -751,7 +1115,7 @@ izipWith5 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e,
                                                 -> v e -> v f
 {-# INLINE izipWith5 #-}
 izipWith5 f as bs cs ds es
                                                 -> v e -> v f
 {-# INLINE izipWith5 #-}
 izipWith5 f as bs cs ds es
-  = unstream (Stream.zipWith5 (uncurry f) (Stream.indexed (stream as))
+  = unstream (Bundle.zipWith5 (uncurry f) (Bundle.indexed (stream as))
                                                           (stream bs)
                                                           (stream cs)
                                                           (stream ds)
                                                           (stream bs)
                                                           (stream cs)
                                                           (stream ds)
@@ -763,13 +1127,14 @@ izipWith6 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e,
          -> v a -> v b -> v c -> v d -> v e -> v f -> v g
 {-# INLINE izipWith6 #-}
 izipWith6 f as bs cs ds es fs
          -> v a -> v b -> v c -> v d -> v e -> v f -> v g
 {-# INLINE izipWith6 #-}
 izipWith6 f as bs cs ds es fs
-  = unstream (Stream.zipWith6 (uncurry f) (Stream.indexed (stream as))
+  = unstream (Bundle.zipWith6 (uncurry f) (Bundle.indexed (stream as))
                                                           (stream bs)
                                                           (stream cs)
                                                           (stream ds)
                                                           (stream es)
                                                           (stream fs))
 
                                                           (stream bs)
                                                           (stream cs)
                                                           (stream ds)
                                                           (stream es)
                                                           (stream fs))
 
+-- | /O(min(m,n))/ Zip two vectors
 zip :: (Vector v a, Vector v b, Vector v (a,b)) => v a -> v b -> v (a, b)
 {-# INLINE zip #-}
 zip = zipWith (,)
 zip :: (Vector v a, Vector v b, Vector v (a,b)) => v a -> v b -> v (a, b)
 {-# INLINE zip #-}
 zip = zipWith (,)
@@ -796,6 +1161,28 @@ zip6 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e,
 {-# INLINE zip6 #-}
 zip6 = zipWith6 (,,,,,)
 
 {-# INLINE zip6 #-}
 zip6 = zipWith6 (,,,,,)
 
+-- Monadic zipping
+-- ---------------
+
+-- | /O(min(m,n))/ Zip the two vectors with the monadic action and yield a
+-- vector of results
+zipWithM :: (Monad m, Vector v a, Vector v b, Vector v c)
+         => (a -> b -> m c) -> v a -> v b -> m (v c)
+-- FIXME: specialise for ST and IO?
+{-# INLINE zipWithM #-}
+zipWithM f as bs = unstreamM $ Bundle.zipWithM f (stream as) (stream bs)
+
+-- | /O(min(m,n))/ Zip the two vectors with the monadic action and ignore the
+-- results
+zipWithM_ :: (Monad m, Vector v a, Vector v b)
+          => (a -> b -> m c) -> v a -> v b -> m ()
+{-# INLINE zipWithM_ #-}
+zipWithM_ f as bs = Bundle.zipWithM_ f (stream as) (stream bs)
+
+-- Unzipping
+-- ---------
+
+-- | /O(min(m,n))/ Unzip a vector of pairs.
 unzip :: (Vector v a, Vector v b, Vector v (a,b)) => v (a, b) -> (v a, v b)
 {-# INLINE unzip #-}
 unzip xs = (map fst xs, map snd xs)
 unzip :: (Vector v a, Vector v b, Vector v (a,b)) => v (a, b) -> (v a, v b)
 {-# INLINE unzip #-}
 unzip xs = (map fst xs, map snd xs)
@@ -837,47 +1224,46 @@ unzip6 xs = (map (\(a, b, c, d, e, f) -> a) xs,
              map (\(a, b, c, d, e, f) -> e) xs,
              map (\(a, b, c, d, e, f) -> f) xs)
 
              map (\(a, b, c, d, e, f) -> e) xs,
              map (\(a, b, c, d, e, f) -> f) xs)
 
--- Comparisons
--- -----------
-
-eq :: (Vector v a, Eq a) => v a -> v a -> Bool
-{-# INLINE eq #-}
-xs `eq` ys = stream xs == stream ys
-
-cmp :: (Vector v a, Ord a) => v a -> v a -> Ordering
-{-# INLINE cmp #-}
-cmp xs ys = compare (stream xs) (stream ys)
-
 -- Filtering
 -- ---------
 
 -- Filtering
 -- ---------
 
--- | Drop elements that do not satisfy the predicate
+-- | /O(n)/ Drop elements that do not satisfy the predicate
 filter :: Vector v a => (a -> Bool) -> v a -> v a
 {-# INLINE filter #-}
 filter :: Vector v a => (a -> Bool) -> v a -> v a
 {-# INLINE filter #-}
-filter f = unstream . inplace (MStream.filter f) . stream
+filter f = unstream . inplace (MBundle.filter f) . stream
 
 
--- | Drop elements that do not satisfy the predicate (applied to values and
--- their indices)
+-- | /O(n)/ Drop elements that do not satisfy the predicate which is applied to
+-- values and their indices
 ifilter :: Vector v a => (Int -> a -> Bool) -> v a -> v a
 {-# INLINE ifilter #-}
 ifilter f = unstream
 ifilter :: Vector v a => (Int -> a -> Bool) -> v a -> v a
 {-# INLINE ifilter #-}
 ifilter f = unstream
-          . inplace (MStream.map snd . MStream.filter (uncurry f)
-                                     . MStream.indexed)
+          . inplace (MBundle.map snd . MBundle.filter (uncurry f)
+                                     . MBundle.indexed)
           . stream
 
           . stream
 
--- | Yield the longest prefix of elements satisfying the predicate.
+-- | /O(n)/ Drop elements that do not satisfy the monadic predicate
+filterM :: (Monad m, Vector v a) => (a -> m Bool) -> v a -> m (v a)
+{-# INLINE filterM #-}
+filterM f = unstreamM . Bundle.filterM f . stream
+
+-- | /O(n)/ Yield the longest prefix of elements satisfying the predicate
+-- without copying.
 takeWhile :: Vector v a => (a -> Bool) -> v a -> v a
 {-# INLINE takeWhile #-}
 takeWhile :: Vector v a => (a -> Bool) -> v a -> v a
 {-# INLINE takeWhile #-}
-takeWhile f = unstream . Stream.takeWhile f . stream
+takeWhile f = unstream . Bundle.takeWhile f . stream
 
 
--- | Drop the longest prefix of elements that satisfy the predicate.
+-- | /O(n)/ Drop the longest prefix of elements that satisfy the predicate
+-- without copying.
 dropWhile :: Vector v a => (a -> Bool) -> v a -> v a
 {-# INLINE dropWhile #-}
 dropWhile :: Vector v a => (a -> Bool) -> v a -> v a
 {-# INLINE dropWhile #-}
-dropWhile f = unstream . Stream.dropWhile f . stream
+dropWhile f = unstream . Bundle.dropWhile f . stream
+
+-- Parititioning
+-- -------------
 
 
--- | Split the vector in two parts, the first one containing those elements
--- that satisfy the predicate and the second one those that don't. The
--- relative order of the elements is preserved at the cost of a (sometimes)
+-- | /O(n)/ Split the vector in two parts, the first one containing those
+-- elements that satisfy the predicate and the second one those that don't. The
+-- relative order of the elements is preserved at the cost of a sometimes
 -- reduced performance compared to 'unstablePartition'.
 partition :: Vector v a => (a -> Bool) -> v a -> (v a, v a)
 {-# INLINE partition #-}
 -- reduced performance compared to 'unstablePartition'.
 partition :: Vector v a => (a -> Bool) -> v a -> (v a, v a)
 {-# INLINE partition #-}
@@ -886,35 +1272,35 @@ 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)
-{-# INLINE_STREAM partition_stream #-}
+partition_stream :: Vector v a => (a -> Bool) -> Bundle u a -> (v a, v a)
+{-# INLINE_FUSED partition_stream #-}
 partition_stream f s = s `seq` runST (
   do
 partition_stream f s = s `seq` runST (
   do
-    (mv1,mv2) <- M.partitionStream f s
+    (mv1,mv2) <- M.partitionBundle f s
     v1 <- unsafeFreeze mv1
     v2 <- unsafeFreeze mv2
     return (v1,v2))
 
     v1 <- unsafeFreeze mv1
     v2 <- unsafeFreeze mv2
     return (v1,v2))
 
--- | Split the vector in two parts, the first one containing those elements
--- that satisfy the predicate and the second one those that don't. The order
--- of the elements is not preserved but the operation is often faster than
--- 'partition'.
+-- | /O(n)/ Split the vector in two parts, the first one containing those
+-- elements that satisfy the predicate and the second one those that don't.
+-- The order of the elements is not preserved but the operation is often
+-- faster than 'partition'.
 unstablePartition :: Vector v a => (a -> Bool) -> v a -> (v a, v a)
 {-# INLINE unstablePartition #-}
 unstablePartition f = unstablePartition_stream f . stream
 
 unstablePartition_stream
 unstablePartition :: Vector v a => (a -> Bool) -> v a -> (v a, v a)
 {-# INLINE unstablePartition #-}
 unstablePartition f = unstablePartition_stream f . stream
 
 unstablePartition_stream
-  :: Vector v a => (a -> Bool) -> Stream a -> (v a, v a)
-{-# INLINE_STREAM unstablePartition_stream #-}
+  :: Vector v a => (a -> Bool) -> Bundle u a -> (v a, v a)
+{-# INLINE_FUSED unstablePartition_stream #-}
 unstablePartition_stream f s = s `seq` runST (
   do
 unstablePartition_stream f s = s `seq` runST (
   do
-    (mv1,mv2) <- M.unstablePartitionStream f s
+    (mv1,mv2) <- M.unstablePartitionBundle f s
     v1 <- unsafeFreeze mv1
     v2 <- unsafeFreeze mv2
     return (v1,v2))
 
     v1 <- unsafeFreeze mv1
     v2 <- unsafeFreeze mv2
     return (v1,v2))
 
-unstablePartition_new :: Vector v a => (a -> Bool) -> New a -> (v a, v a)
-{-# INLINE_STREAM unstablePartition_new #-}
+unstablePartition_new :: Vector v a => (a -> Bool) -> New a -> (v a, v a)
+{-# INLINE_FUSED unstablePartition_new #-}
 unstablePartition_new f (New.New p) = runST (
   do
     mv <- p
 unstablePartition_new f (New.New p) = runST (
   do
     mv <- p
@@ -924,8 +1310,8 @@ unstablePartition_new f (New.New p) = runST (
 
 {-# RULES
 
 
 {-# RULES
 
-"unstablePartition" forall f p.
-  unstablePartition_stream f (stream (new' v p))
+"unstablePartition" forall f p.
+  unstablePartition_stream f (stream (new p))
     = unstablePartition_new f p
 
   #-}
     = unstablePartition_new f p
 
   #-}
@@ -933,14 +1319,14 @@ unstablePartition_new f (New.New p) = runST (
 
 -- FIXME: make span and break fusible
 
 
 -- FIXME: make span and break fusible
 
--- | Split the vector into the longest prefix of elements that satisfy the
--- predicate and the rest.
+-- | /O(n)/ Split the vector into the longest prefix of elements that satisfy
+-- the predicate and the rest without copying.
 span :: Vector v a => (a -> Bool) -> v a -> (v a, v a)
 {-# INLINE span #-}
 span f = break (not . f)
 
 span :: Vector v a => (a -> Bool) -> v a -> (v a, v a)
 {-# INLINE span #-}
 span f = break (not . f)
 
--- | Split the vector into the longest prefix of elements that do not satisfy
--- the predicate and the rest.
+-- | /O(n)/ Split the vector into the longest prefix of elements that do not
+-- satisfy the predicate and the rest without copying.
 break :: Vector v a => (a -> Bool) -> v a -> (v a, v a)
 {-# INLINE break #-}
 break f xs = case findIndex f xs of
 break :: Vector v a => (a -> Bool) -> v a -> (v a, v a)
 {-# INLINE break #-}
 break f xs = case findIndex f xs of
@@ -952,44 +1338,47 @@ break f xs = case findIndex f xs of
 -- ---------
 
 infix 4 `elem`
 -- ---------
 
 infix 4 `elem`
--- | Check whether the vector contains an element
+-- | /O(n)/ Check if the vector contains an element
 elem :: (Vector v a, Eq a) => a -> v a -> Bool
 {-# INLINE elem #-}
 elem :: (Vector v a, Eq a) => a -> v a -> Bool
 {-# INLINE elem #-}
-elem x = Stream.elem x . stream
+elem x = Bundle.elem x . stream
 
 infix 4 `notElem`
 
 infix 4 `notElem`
--- | Inverse of `elem`
+-- | /O(n)/ Check if the vector does not contain an element (inverse of 'elem')
 notElem :: (Vector v a, Eq a) => a -> v a -> Bool
 {-# INLINE notElem #-}
 notElem :: (Vector v a, Eq a) => a -> v a -> Bool
 {-# INLINE notElem #-}
-notElem x = Stream.notElem x . stream
+notElem x = Bundle.notElem x . stream
 
 
--- | Yield 'Just' the first element matching the predicate or 'Nothing' if no
--- such element exists.
+-- | /O(n)/ Yield 'Just' the first element matching the predicate or 'Nothing'
+-- if no such element exists.
 find :: Vector v a => (a -> Bool) -> v a -> Maybe a
 {-# INLINE find #-}
 find :: Vector v a => (a -> Bool) -> v a -> Maybe a
 {-# INLINE find #-}
-find f = Stream.find f . stream
+find f = Bundle.find f . stream
 
 
--- | Yield 'Just' the index of the first element matching the predicate or
--- 'Nothing' if no such element exists.
+-- | /O(n)/ Yield 'Just' the index of the first element matching the predicate
+-- or 'Nothing' if no such element exists.
 findIndex :: Vector v a => (a -> Bool) -> v a -> Maybe Int
 {-# INLINE findIndex #-}
 findIndex :: Vector v a => (a -> Bool) -> v a -> Maybe Int
 {-# INLINE findIndex #-}
-findIndex f = Stream.findIndex f . stream
+findIndex f = Bundle.findIndex f . stream
 
 
--- | Yield the indices of elements satisfying the predicate
+-- | /O(n)/ Yield the indices of elements satisfying the predicate in ascending
+-- order.
 findIndices :: (Vector v a, Vector v Int) => (a -> Bool) -> v a -> v Int
 {-# INLINE findIndices #-}
 findIndices f = unstream
 findIndices :: (Vector v a, Vector v Int) => (a -> Bool) -> v a -> v Int
 {-# INLINE findIndices #-}
 findIndices f = unstream
-              . inplace (MStream.map fst . MStream.filter (f . snd)
-                                         . MStream.indexed)
+              . inplace (MBundle.map fst . MBundle.filter (f . snd)
+                                         . MBundle.indexed)
               . stream
 
               . stream
 
--- | Yield 'Just' the index of the first occurence of the given element or
--- 'Nothing' if the vector does not contain the element
+-- | /O(n)/ Yield 'Just' the index of the first occurence of the given element or
+-- 'Nothing' if the vector does not contain the element. This is a specialised
+-- version of 'findIndex'.
 elemIndex :: (Vector v a, Eq a) => a -> v a -> Maybe Int
 {-# INLINE elemIndex #-}
 elemIndex x = findIndex (x==)
 
 elemIndex :: (Vector v a, Eq a) => a -> v a -> Maybe Int
 {-# INLINE elemIndex #-}
 elemIndex x = findIndex (x==)
 
--- | Yield the indices of all occurences of the given element
+-- | /O(n)/ Yield the indices of all occurences of the given element in
+-- ascending order. This is a specialised version of 'findIndices'.
 elemIndices :: (Vector v a, Vector v Int, Eq a) => a -> v a -> v Int
 {-# INLINE elemIndices #-}
 elemIndices x = findIndices (x==)
 elemIndices :: (Vector v a, Vector v Int, Eq a) => a -> v a -> v Int
 {-# INLINE elemIndices #-}
 elemIndices x = findIndices (x==)
@@ -997,298 +1386,626 @@ elemIndices x = findIndices (x==)
 -- Folding
 -- -------
 
 -- Folding
 -- -------
 
--- | Left fold
+-- | /O(n)/ Left fold
 foldl :: Vector v b => (a -> b -> a) -> a -> v b -> a
 {-# INLINE foldl #-}
 foldl :: Vector v b => (a -> b -> a) -> a -> v b -> a
 {-# INLINE foldl #-}
-foldl f z = Stream.foldl f z . stream
+foldl f z = Bundle.foldl f z . stream
 
 
--- | Left fold on non-empty vectors
+-- | /O(n)/ Left fold on non-empty vectors
 foldl1 :: Vector v a => (a -> a -> a) -> v a -> a
 {-# INLINE foldl1 #-}
 foldl1 :: Vector v a => (a -> a -> a) -> v a -> a
 {-# INLINE foldl1 #-}
-foldl1 f = Stream.foldl1 f . stream
+foldl1 f = Bundle.foldl1 f . stream
 
 
--- | Left fold with strict accumulator
+-- | /O(n)/ Left fold with strict accumulator
 foldl' :: Vector v b => (a -> b -> a) -> a -> v b -> a
 {-# INLINE foldl' #-}
 foldl' :: Vector v b => (a -> b -> a) -> a -> v b -> a
 {-# INLINE foldl' #-}
-foldl' f z = Stream.foldl' f z . stream
+foldl' f z = Bundle.foldl' f z . stream
 
 
--- | Left fold on non-empty vectors with strict accumulator
+-- | /O(n)/ Left fold on non-empty vectors with strict accumulator
 foldl1' :: Vector v a => (a -> a -> a) -> v a -> a
 {-# INLINE foldl1' #-}
 foldl1' :: Vector v a => (a -> a -> a) -> v a -> a
 {-# INLINE foldl1' #-}
-foldl1' f = Stream.foldl1' f . stream
+foldl1' f = Bundle.foldl1' f . stream
 
 
--- | Right fold
+-- | /O(n)/ Right fold
 foldr :: Vector v a => (a -> b -> b) -> b -> v a -> b
 {-# INLINE foldr #-}
 foldr :: Vector v a => (a -> b -> b) -> b -> v a -> b
 {-# INLINE foldr #-}
-foldr f z = Stream.foldr f z . stream
+foldr f z = Bundle.foldr f z . stream
 
 
--- | Right fold on non-empty vectors
+-- | /O(n)/ Right fold on non-empty vectors
 foldr1 :: Vector v a => (a -> a -> a) -> v a -> a
 {-# INLINE foldr1 #-}
 foldr1 :: Vector v a => (a -> a -> a) -> v a -> a
 {-# INLINE foldr1 #-}
-foldr1 f = Stream.foldr1 f . stream
+foldr1 f = Bundle.foldr1 f . stream
 
 
--- | Right fold with a strict accumulator
+-- | /O(n)/ Right fold with a strict accumulator
 foldr' :: Vector v a => (a -> b -> b) -> b -> v a -> b
 {-# INLINE foldr' #-}
 foldr' :: Vector v a => (a -> b -> b) -> b -> v a -> b
 {-# INLINE foldr' #-}
-foldr' f z = Stream.foldl' (flip f) z . streamR
+foldr' f z = Bundle.foldl' (flip f) z . streamR
 
 
--- | Right fold on non-empty vectors with strict accumulator
+-- | /O(n)/ Right fold on non-empty vectors with strict accumulator
 foldr1' :: Vector v a => (a -> a -> a) -> v a -> a
 {-# INLINE foldr1' #-}
 foldr1' :: Vector v a => (a -> a -> a) -> v a -> a
 {-# INLINE foldr1' #-}
-foldr1' f = Stream.foldl1' (flip f) . streamR
+foldr1' f = Bundle.foldl1' (flip f) . streamR
 
 
--- | Left fold (function applied to each element and its index)
+-- | /O(n)/ Left fold (function applied to each element and its index)
 ifoldl :: Vector v b => (a -> Int -> b -> a) -> a -> v b -> a
 {-# INLINE ifoldl #-}
 ifoldl :: Vector v b => (a -> Int -> b -> a) -> a -> v b -> a
 {-# INLINE ifoldl #-}
-ifoldl f z = Stream.foldl (uncurry . f) z . Stream.indexed . stream
+ifoldl f z = Bundle.foldl (uncurry . f) z . Bundle.indexed . stream
 
 
--- | Left fold with strict accumulator (function applied to each element and
--- its index)
+-- | /O(n)/ Left fold with strict accumulator (function applied to each element
+-- and its index)
 ifoldl' :: Vector v b => (a -> Int -> b -> a) -> a -> v b -> a
 {-# INLINE ifoldl' #-}
 ifoldl' :: Vector v b => (a -> Int -> b -> a) -> a -> v b -> a
 {-# INLINE ifoldl' #-}
-ifoldl' f z = Stream.foldl' (uncurry . f) z . Stream.indexed . stream
+ifoldl' f z = Bundle.foldl' (uncurry . f) z . Bundle.indexed . stream
 
 
--- | Right fold (function applied to each element and its index)
+-- | /O(n)/ Right fold (function applied to each element and its index)
 ifoldr :: Vector v a => (Int -> a -> b -> b) -> b -> v a -> b
 {-# INLINE ifoldr #-}
 ifoldr :: Vector v a => (Int -> a -> b -> b) -> b -> v a -> b
 {-# INLINE ifoldr #-}
-ifoldr f z = Stream.foldr (uncurry f) z . Stream.indexed . stream
+ifoldr f z = Bundle.foldr (uncurry f) z . Bundle.indexed . stream
 
 
--- | Right fold with strict accumulator (function applied to each element and
--- its index)
+-- | /O(n)/ Right fold with strict accumulator (function applied to each
+-- element and its index)
 ifoldr' :: Vector v a => (Int -> a -> b -> b) -> b -> v a -> b
 {-# INLINE ifoldr' #-}
 ifoldr' :: Vector v a => (Int -> a -> b -> b) -> b -> v a -> b
 {-# INLINE ifoldr' #-}
-ifoldr' f z xs = Stream.foldl' (flip (uncurry f)) z
-               $ Stream.indexedR (length xs) $ streamR xs
+ifoldr' f z xs = Bundle.foldl' (flip (uncurry f)) z
+               $ Bundle.indexedR (length xs) $ streamR xs
 
 -- Specialised folds
 -- -----------------
 
 
 -- Specialised folds
 -- -----------------
 
+-- | /O(n)/ Check if all elements satisfy the predicate.
 all :: Vector v a => (a -> Bool) -> v a -> Bool
 {-# INLINE all #-}
 all :: Vector v a => (a -> Bool) -> v a -> Bool
 {-# INLINE all #-}
-all f = Stream.and . Stream.map f . stream
+all f = Bundle.and . Bundle.map f . stream
 
 
+-- | /O(n)/ Check if any element satisfies the predicate.
 any :: Vector v a => (a -> Bool) -> v a -> Bool
 {-# INLINE any #-}
 any :: Vector v a => (a -> Bool) -> v a -> Bool
 {-# INLINE any #-}
-any f = Stream.or . Stream.map f . stream
+any f = Bundle.or . Bundle.map f . stream
 
 
+-- | /O(n)/ Check if all elements are 'True'
 and :: Vector v Bool => v Bool -> Bool
 {-# INLINE and #-}
 and :: Vector v Bool => v Bool -> Bool
 {-# INLINE and #-}
-and = Stream.and . stream
+and = Bundle.and . stream
 
 
+-- | /O(n)/ Check if any element is 'True'
 or :: Vector v Bool => v Bool -> Bool
 {-# INLINE or #-}
 or :: Vector v Bool => v Bool -> Bool
 {-# INLINE or #-}
-or = Stream.or . stream
+or = Bundle.or . stream
 
 
+-- | /O(n)/ Compute the sum of the elements
 sum :: (Vector v a, Num a) => v a -> a
 {-# INLINE sum #-}
 sum :: (Vector v a, Num a) => v a -> a
 {-# INLINE sum #-}
-sum = Stream.foldl' (+) 0 . stream
+sum = Bundle.foldl' (+) 0 . stream
 
 
+-- | /O(n)/ Compute the produce of the elements
 product :: (Vector v a, Num a) => v a -> a
 {-# INLINE product #-}
 product :: (Vector v a, Num a) => v a -> a
 {-# INLINE product #-}
-product = Stream.foldl' (*) 1 . stream
+product = Bundle.foldl' (*) 1 . stream
 
 
+-- | /O(n)/ Yield the maximum element of the vector. The vector may not be
+-- empty.
 maximum :: (Vector v a, Ord a) => v a -> a
 {-# INLINE maximum #-}
 maximum :: (Vector v a, Ord a) => v a -> a
 {-# INLINE maximum #-}
-maximum = Stream.foldl1' max . stream
+maximum = Bundle.foldl1' max . stream
 
 
+-- | /O(n)/ Yield the maximum element of the vector according to the given
+-- comparison function. The vector may not be empty.
 maximumBy :: Vector v a => (a -> a -> Ordering) -> v a -> a
 {-# INLINE maximumBy #-}
 maximumBy :: Vector v a => (a -> a -> Ordering) -> v a -> a
 {-# INLINE maximumBy #-}
-maximumBy cmp = Stream.foldl1' maxBy . stream
+maximumBy cmp = Bundle.foldl1' maxBy . stream
   where
     {-# INLINE maxBy #-}
     maxBy x y = case cmp x y of
                   LT -> y
                   _  -> x
 
   where
     {-# INLINE maxBy #-}
     maxBy x y = case cmp x y of
                   LT -> y
                   _  -> x
 
+-- | /O(n)/ Yield the minimum element of the vector. The vector may not be
+-- empty.
 minimum :: (Vector v a, Ord a) => v a -> a
 {-# INLINE minimum #-}
 minimum :: (Vector v a, Ord a) => v a -> a
 {-# INLINE minimum #-}
-minimum = Stream.foldl1' min . stream
+minimum = Bundle.foldl1' min . stream
 
 
+-- | /O(n)/ Yield the minimum element of the vector according to the given
+-- comparison function. The vector may not be empty.
 minimumBy :: Vector v a => (a -> a -> Ordering) -> v a -> a
 {-# INLINE minimumBy #-}
 minimumBy :: Vector v a => (a -> a -> Ordering) -> v a -> a
 {-# INLINE minimumBy #-}
-minimumBy cmp = Stream.foldl1' minBy . stream
+minimumBy cmp = Bundle.foldl1' minBy . stream
   where
     {-# INLINE minBy #-}
     minBy x y = case cmp x y of
                   GT -> y
                   _  -> x
 
   where
     {-# INLINE minBy #-}
     minBy x y = case cmp x y of
                   GT -> y
                   _  -> x
 
+-- | /O(n)/ Yield the index of the maximum element of the vector. The vector
+-- may not be empty.
 maxIndex :: (Vector v a, Ord a) => v a -> Int
 {-# INLINE maxIndex #-}
 maxIndex = maxIndexBy compare
 
 maxIndex :: (Vector v a, Ord a) => v a -> Int
 {-# INLINE maxIndex #-}
 maxIndex = maxIndexBy compare
 
+-- | /O(n)/ Yield the index of the maximum element of the vector according to
+-- the given comparison function. The vector may not be empty.
 maxIndexBy :: Vector v a => (a -> a -> Ordering) -> v a -> Int
 {-# INLINE maxIndexBy #-}
 maxIndexBy :: Vector v a => (a -> a -> Ordering) -> v a -> Int
 {-# INLINE maxIndexBy #-}
-maxIndexBy cmp = fst . Stream.foldl1' imax . Stream.indexed . stream
+maxIndexBy cmp = fst . Bundle.foldl1' imax . Bundle.indexed . stream
   where
   where
-    imax (i,x) (j,y) = case cmp x y of
+    imax (i,x) (j,y) = i `seq` j `seq`
+                       case cmp x y of
                          LT -> (j,y)
                          _  -> (i,x)
 
                          LT -> (j,y)
                          _  -> (i,x)
 
+-- | /O(n)/ Yield the index of the minimum element of the vector. The vector
+-- may not be empty.
 minIndex :: (Vector v a, Ord a) => v a -> Int
 {-# INLINE minIndex #-}
 minIndex = minIndexBy compare
 
 minIndex :: (Vector v a, Ord a) => v a -> Int
 {-# INLINE minIndex #-}
 minIndex = minIndexBy compare
 
+-- | /O(n)/ Yield the index of the minimum element of the vector according to
+-- the given comparison function. The vector may not be empty.
 minIndexBy :: Vector v a => (a -> a -> Ordering) -> v a -> Int
 {-# INLINE minIndexBy #-}
 minIndexBy :: Vector v a => (a -> a -> Ordering) -> v a -> Int
 {-# INLINE minIndexBy #-}
-minIndexBy cmp = fst . Stream.foldl1' imin . Stream.indexed . stream
+minIndexBy cmp = fst . Bundle.foldl1' imin . Bundle.indexed . stream
   where
   where
-    imin (i,x) (j,y) = case cmp x y of
+    imin (i,x) (j,y) = i `seq` j `seq`
+                       case cmp x y of
                          GT -> (j,y)
                          _  -> (i,x)
 
                          GT -> (j,y)
                          _  -> (i,x)
 
-
--- Unfolding
--- ---------
-
--- | Unfold
-unfoldr :: Vector v a => (b -> Maybe (a, b)) -> b -> v a
-{-# INLINE unfoldr #-}
-unfoldr f = unstream . Stream.unfoldr f
-
--- | Unfoldr at most @n@ elements.
-unfoldrN  :: Vector v a => Int -> (b -> Maybe (a, b)) -> b -> v a
-{-# INLINE unfoldrN #-}
-unfoldrN n f = unstream . Stream.unfoldrN n f
-
--- Scans
--- -----
-
--- | Prefix scan
+-- Monadic folds
+-- -------------
+
+-- | /O(n)/ Monadic fold
+foldM :: (Monad m, Vector v b) => (a -> b -> m a) -> a -> v b -> m a
+{-# INLINE foldM #-}
+foldM m z = Bundle.foldM m z . stream
+
+-- | /O(n)/ Monadic fold over non-empty vectors
+fold1M :: (Monad m, Vector v a) => (a -> a -> m a) -> v a -> m a
+{-# INLINE fold1M #-}
+fold1M m = Bundle.fold1M m . stream
+
+-- | /O(n)/ Monadic fold with strict accumulator
+foldM' :: (Monad m, Vector v b) => (a -> b -> m a) -> a -> v b -> m a
+{-# INLINE foldM' #-}
+foldM' m z = Bundle.foldM' m z . stream
+
+-- | /O(n)/ Monadic fold over non-empty vectors with strict accumulator
+fold1M' :: (Monad m, Vector v a) => (a -> a -> m a) -> v a -> m a
+{-# INLINE fold1M' #-}
+fold1M' m = Bundle.fold1M' m . stream
+
+discard :: Monad m => m a -> m ()
+{-# INLINE discard #-}
+discard m = m >> return ()
+
+-- | /O(n)/ Monadic fold that discards the result
+foldM_ :: (Monad m, Vector v b) => (a -> b -> m a) -> a -> v b -> m ()
+{-# INLINE foldM_ #-}
+foldM_ m z = discard . Bundle.foldM m z . stream
+
+-- | /O(n)/ Monadic fold over non-empty vectors that discards the result
+fold1M_ :: (Monad m, Vector v a) => (a -> a -> m a) -> v a -> m ()
+{-# INLINE fold1M_ #-}
+fold1M_ m = discard . Bundle.fold1M m . stream
+
+-- | /O(n)/ Monadic fold with strict accumulator that discards the result
+foldM'_ :: (Monad m, Vector v b) => (a -> b -> m a) -> a -> v b -> m ()
+{-# INLINE foldM'_ #-}
+foldM'_ m z = discard . Bundle.foldM' m z . stream
+
+-- | /O(n)/ Monad fold over non-empty vectors with strict accumulator
+-- that discards the result
+fold1M'_ :: (Monad m, Vector v a) => (a -> a -> m a) -> v a -> m ()
+{-# INLINE fold1M'_ #-}
+fold1M'_ m = discard . Bundle.fold1M' m . stream
+
+-- Monadic sequencing
+-- ------------------
+
+-- | Evaluate each action and collect the results
+sequence :: (Monad m, Vector v a, Vector v (m a)) => v (m a) -> m (v a)
+{-# INLINE sequence #-}
+sequence = mapM id
+
+-- | Evaluate each action and discard the results
+sequence_ :: (Monad m, Vector v (m a)) => v (m a) -> m ()
+{-# INLINE sequence_ #-}
+sequence_ = mapM_ id
+
+-- Prefix sums (scans)
+-- -------------------
+
+-- | /O(n)/ Prescan
+--
+-- @
+-- prescanl f z = 'init' . 'scanl' f z
+-- @
+--
+-- Example: @prescanl (+) 0 \<1,2,3,4\> = \<0,1,3,6\>@
+--
 prescanl :: (Vector v a, Vector v b) => (a -> b -> a) -> a -> v b -> v a
 {-# INLINE prescanl #-}
 prescanl :: (Vector v a, Vector v b) => (a -> b -> a) -> a -> v b -> v a
 {-# INLINE prescanl #-}
-prescanl f z = unstream . inplace (MStream.prescanl f z) . stream
+prescanl f z = unstream . inplace (MBundle.prescanl f z) . stream
 
 
--- | Prefix scan with strict accumulator
+-- | /O(n)/ Prescan with strict accumulator
 prescanl' :: (Vector v a, Vector v b) => (a -> b -> a) -> a -> v b -> v a
 {-# INLINE prescanl' #-}
 prescanl' :: (Vector v a, Vector v b) => (a -> b -> a) -> a -> v b -> v a
 {-# INLINE prescanl' #-}
-prescanl' f z = unstream . inplace (MStream.prescanl' f z) . stream
+prescanl' f z = unstream . inplace (MBundle.prescanl' f z) . stream
 
 
--- | Suffix scan
+-- | /O(n)/ Scan
+--
+-- @
+-- postscanl f z = 'tail' . 'scanl' f z
+-- @
+--
+-- Example: @postscanl (+) 0 \<1,2,3,4\> = \<1,3,6,10\>@
+--
 postscanl :: (Vector v a, Vector v b) => (a -> b -> a) -> a -> v b -> v a
 {-# INLINE postscanl #-}
 postscanl :: (Vector v a, Vector v b) => (a -> b -> a) -> a -> v b -> v a
 {-# INLINE postscanl #-}
-postscanl f z = unstream . inplace (MStream.postscanl f z) . stream
+postscanl f z = unstream . inplace (MBundle.postscanl f z) . stream
 
 
--- | Suffix scan with strict accumulator
+-- | /O(n)/ Scan with strict accumulator
 postscanl' :: (Vector v a, Vector v b) => (a -> b -> a) -> a -> v b -> v a
 {-# INLINE postscanl' #-}
 postscanl' :: (Vector v a, Vector v b) => (a -> b -> a) -> a -> v b -> v a
 {-# INLINE postscanl' #-}
-postscanl' f z = unstream . inplace (MStream.postscanl' f z) . stream
+postscanl' f z = unstream . inplace (MBundle.postscanl' f z) . stream
 
 
--- | Haskell-style scan
+-- | /O(n)/ Haskell-style scan
+--
+-- > scanl f z <x1,...,xn> = <y1,...,y(n+1)>
+-- >   where y1 = z
+-- >         yi = f y(i-1) x(i-1)
+--
+-- Example: @scanl (+) 0 \<1,2,3,4\> = \<0,1,3,6,10\>@
+-- 
 scanl :: (Vector v a, Vector v b) => (a -> b -> a) -> a -> v b -> v a
 {-# INLINE scanl #-}
 scanl :: (Vector v a, Vector v b) => (a -> b -> a) -> a -> v b -> v a
 {-# INLINE scanl #-}
-scanl f z = unstream . Stream.scanl f z . stream
+scanl f z = unstream . Bundle.scanl f z . stream
 
 
--- | Haskell-style scan with strict accumulator
+-- | /O(n)/ Haskell-style scan with strict accumulator
 scanl' :: (Vector v a, Vector v b) => (a -> b -> a) -> a -> v b -> v a
 {-# INLINE scanl' #-}
 scanl' :: (Vector v a, Vector v b) => (a -> b -> a) -> a -> v b -> v a
 {-# INLINE scanl' #-}
-scanl' f z = unstream . Stream.scanl' f z . stream
+scanl' f z = unstream . Bundle.scanl' f z . stream
 
 
--- | Scan over a non-empty vector
+-- | /O(n)/ Scan over a non-empty vector
+--
+-- > scanl f <x1,...,xn> = <y1,...,yn>
+-- >   where y1 = x1
+-- >         yi = f y(i-1) xi
+--
 scanl1 :: Vector v a => (a -> a -> a) -> v a -> v a
 {-# INLINE scanl1 #-}
 scanl1 :: Vector v a => (a -> a -> a) -> v a -> v a
 {-# INLINE scanl1 #-}
-scanl1 f = unstream . inplace (MStream.scanl1 f) . stream
+scanl1 f = unstream . inplace (MBundle.scanl1 f) . stream
 
 
--- | Scan over a non-empty vector with a strict accumulator
+-- | /O(n)/ Scan over a non-empty vector with a strict accumulator
 scanl1' :: Vector v a => (a -> a -> a) -> v a -> v a
 {-# INLINE scanl1' #-}
 scanl1' :: Vector v a => (a -> a -> a) -> v a -> v a
 {-# INLINE scanl1' #-}
-scanl1' f = unstream . inplace (MStream.scanl1' f) . stream
-
+scanl1' f = unstream . inplace (MBundle.scanl1' f) . stream
 
 
--- | Prefix right-to-left scan
+-- | /O(n)/ Right-to-left prescan
+--
+-- @
+-- prescanr f z = 'reverse' . 'prescanl' (flip f) z . 'reverse'
+-- @
+--
 prescanr :: (Vector v a, Vector v b) => (a -> b -> b) -> b -> v a -> v b
 {-# INLINE prescanr #-}
 prescanr :: (Vector v a, Vector v b) => (a -> b -> b) -> b -> v a -> v b
 {-# INLINE prescanr #-}
-prescanr f z = unstreamR . inplace (MStream.prescanl (flip f) z) . streamR
+prescanr f z = unstreamR . inplace (MBundle.prescanl (flip f) z) . streamR
 
 
--- | Prefix right-to-left scan with strict accumulator
+-- | /O(n)/ Right-to-left prescan with strict accumulator
 prescanr' :: (Vector v a, Vector v b) => (a -> b -> b) -> b -> v a -> v b
 {-# INLINE prescanr' #-}
 prescanr' :: (Vector v a, Vector v b) => (a -> b -> b) -> b -> v a -> v b
 {-# INLINE prescanr' #-}
-prescanr' f z = unstreamR . inplace (MStream.prescanl' (flip f) z) . streamR
+prescanr' f z = unstreamR . inplace (MBundle.prescanl' (flip f) z) . streamR
 
 
--- | Suffix right-to-left scan
+-- | /O(n)/ Right-to-left scan
 postscanr :: (Vector v a, Vector v b) => (a -> b -> b) -> b -> v a -> v b
 {-# INLINE postscanr #-}
 postscanr :: (Vector v a, Vector v b) => (a -> b -> b) -> b -> v a -> v b
 {-# INLINE postscanr #-}
-postscanr f z = unstreamR . inplace (MStream.postscanl (flip f) z) . streamR
+postscanr f z = unstreamR . inplace (MBundle.postscanl (flip f) z) . streamR
 
 
--- | Suffix right-to-left scan with strict accumulator
+-- | /O(n)/ Right-to-left scan with strict accumulator
 postscanr' :: (Vector v a, Vector v b) => (a -> b -> b) -> b -> v a -> v b
 {-# INLINE postscanr' #-}
 postscanr' :: (Vector v a, Vector v b) => (a -> b -> b) -> b -> v a -> v b
 {-# INLINE postscanr' #-}
-postscanr' f z = unstreamR . inplace (MStream.postscanl' (flip f) z) . streamR
+postscanr' f z = unstreamR . inplace (MBundle.postscanl' (flip f) z) . streamR
 
 
--- | Haskell-style right-to-left scan
+-- | /O(n)/ Right-to-left Haskell-style scan
 scanr :: (Vector v a, Vector v b) => (a -> b -> b) -> b -> v a -> v b
 {-# INLINE scanr #-}
 scanr :: (Vector v a, Vector v b) => (a -> b -> b) -> b -> v a -> v b
 {-# INLINE scanr #-}
-scanr f z = unstreamR . Stream.scanl (flip f) z . streamR
+scanr f z = unstreamR . Bundle.scanl (flip f) z . streamR
 
 
--- | Haskell-style right-to-left scan with strict accumulator
+-- | /O(n)/ Right-to-left Haskell-style scan with strict accumulator
 scanr' :: (Vector v a, Vector v b) => (a -> b -> b) -> b -> v a -> v b
 {-# INLINE scanr' #-}
 scanr' :: (Vector v a, Vector v b) => (a -> b -> b) -> b -> v a -> v b
 {-# INLINE scanr' #-}
-scanr' f z = unstreamR . Stream.scanl' (flip f) z . streamR
+scanr' f z = unstreamR . Bundle.scanl' (flip f) z . streamR
 
 
--- | Right-to-left scan over a non-empty vector
+-- | /O(n)/ Right-to-left scan over a non-empty vector
 scanr1 :: Vector v a => (a -> a -> a) -> v a -> v a
 {-# INLINE scanr1 #-}
 scanr1 :: Vector v a => (a -> a -> a) -> v a -> v a
 {-# INLINE scanr1 #-}
-scanr1 f = unstreamR . inplace (MStream.scanl1 (flip f)) . streamR
+scanr1 f = unstreamR . inplace (MBundle.scanl1 (flip f)) . streamR
 
 
--- | Right-to-left scan over a non-empty vector with a strict accumulator
+-- | /O(n)/ Right-to-left scan over a non-empty vector with a strict
+-- accumulator
 scanr1' :: Vector v a => (a -> a -> a) -> v a -> v a
 {-# INLINE scanr1' #-}
 scanr1' :: Vector v a => (a -> a -> a) -> v a -> v a
 {-# INLINE scanr1' #-}
-scanr1' f = unstreamR . inplace (MStream.scanl1' (flip f)) . streamR
-
--- Enumeration
--- -----------
-
--- | Yield a vector of the given length containing the values @x@, @x+1@ etc.
--- This operation is usually more efficient than 'enumFromTo'.
-enumFromN :: (Vector v a, Num a) => a -> Int -> v a
-{-# INLINE enumFromN #-}
-enumFromN x n = enumFromStepN x 1 n
-
--- | Yield a vector of the given length containing the values @x@, @x+y@,
--- @x+y+y@ etc. This operations is usually more efficient than
--- 'enumFromThenTo'.
-enumFromStepN :: forall v a. (Vector v a, Num a) => a -> a -> Int -> v a
-{-# INLINE enumFromStepN #-}
-enumFromStepN x y n = elemseq (undefined :: v a) x
-                    $ elemseq (undefined :: v a) y
-                    $ unstream
-                    $ Stream.enumFromStepN  x y n
-
--- | Enumerate values from @x@ to @y@.
---
--- /WARNING:/ This operation can be very inefficient. If at all possible, use
--- 'enumFromN' instead.
-enumFromTo :: (Vector v a, Enum a) => a -> a -> v a
-{-# INLINE enumFromTo #-}
-enumFromTo x y = unstream (Stream.enumFromTo x y)
+scanr1' f = unstreamR . inplace (MBundle.scanl1' (flip f)) . streamR
 
 
--- | Enumerate values from @x@ to @y@ with a specific step @z@.
---
--- /WARNING:/ This operation can be very inefficient. If at all possible, use
--- 'enumFromStepN' instead.
-enumFromThenTo :: (Vector v a, Enum a) => a -> a -> a -> v a
-{-# INLINE enumFromThenTo #-}
-enumFromThenTo x y z = unstream (Stream.enumFromThenTo x y z)
+-- Conversions - Lists
+-- ------------------------
 
 
--- | Convert a vector to a list
+-- | /O(n)/ Convert a vector to a list
 toList :: Vector v a => v a -> [a]
 {-# INLINE toList #-}
 toList :: Vector v a => v a -> [a]
 {-# INLINE toList #-}
-toList = Stream.toList . stream
+toList = Bundle.toList . stream
 
 
--- | Convert a list to a vector
+-- | /O(n)/ Convert a list to a vector
 fromList :: Vector v a => [a] -> v a
 {-# INLINE fromList #-}
 fromList :: Vector v a => [a] -> v a
 {-# INLINE fromList #-}
-fromList = unstream . Stream.fromList
+fromList = unstream . Bundle.fromList
 
 
--- | Convert the first @n@ elements of a list to a vector
+-- | /O(n)/ Convert the first @n@ elements of a list to a vector
 --
 --
--- > fromListN n xs = fromList (take n xs)
+-- @
+-- fromListN n xs = 'fromList' ('take' n xs)
+-- @
 fromListN :: Vector v a => Int -> [a] -> v a
 {-# INLINE fromListN #-}
 fromListN :: Vector v a => Int -> [a] -> v a
 {-# INLINE fromListN #-}
-fromListN n = unstream . Stream.fromListN n
+fromListN n = unstream . Bundle.fromListN n
+
+-- Conversions - Immutable vectors
+-- -------------------------------
+
+-- | /O(n)/ Convert different vector types
+convert :: (Vector v a, Vector w a) => v a -> w a
+{-# INLINE convert #-}
+convert = unstream . Bundle.reVector . stream
+
+-- Conversions - Mutable vectors
+-- -----------------------------
+
+-- | /O(1)/ Unsafe convert a mutable vector to an immutable one without
+-- copying. The mutable vector may not be used after this operation.
+unsafeFreeze
+  :: (PrimMonad m, Vector v a) => Mutable v (PrimState m) a -> m (v a)
+{-# INLINE unsafeFreeze #-}
+unsafeFreeze = basicUnsafeFreeze
+
+-- | /O(n)/ Yield an immutable copy of the mutable vector.
+freeze :: (PrimMonad m, Vector v a) => Mutable v (PrimState m) a -> m (v a)
+{-# INLINE freeze #-}
+freeze mv = unsafeFreeze =<< M.clone mv
+
+-- | /O(1)/ Unsafely convert an immutable vector to a mutable one without
+-- copying. The immutable vector may not be used after this operation.
+unsafeThaw :: (PrimMonad m, Vector v a) => v a -> m (Mutable v (PrimState m) a)
+{-# INLINE_FUSED unsafeThaw #-}
+unsafeThaw = basicUnsafeThaw
+
+-- | /O(n)/ Yield a mutable copy of the immutable vector.
+thaw :: (PrimMonad m, Vector v a) => v a -> m (Mutable v (PrimState m) a)
+{-# INLINE_FUSED thaw #-}
+thaw v = do
+           mv <- M.unsafeNew (length v)
+           unsafeCopy mv v
+           return mv
+
+{-# RULES
+
+"unsafeThaw/new [Vector]" forall p.
+  unsafeThaw (new p) = New.runPrim p
+
+"thaw/new [Vector]" forall p.
+  thaw (new p) = New.runPrim p
+
+  #-}
+
+{-
+-- | /O(n)/ Yield a mutable vector containing copies of each vector in the
+-- list.
+thawMany :: (PrimMonad m, Vector v a) => [v a] -> m (Mutable v (PrimState m) a)
+{-# INLINE_FUSED thawMany #-}
+-- FIXME: add rule for (stream (new (New.create (thawMany vs))))
+-- NOTE: We don't try to consume the list lazily as this wouldn't significantly
+-- change the space requirements anyway.
+thawMany vs = do
+                mv <- M.new n
+                thaw_loop mv vs
+                return mv
+  where
+    n = List.foldl' (\k v -> k + length v) 0 vs
+
+    thaw_loop mv [] = mv `seq` return ()
+    thaw_loop mv (v:vs)
+      = do
+          let n = length v
+          unsafeCopy (M.unsafeTake n mv) v
+          thaw_loop (M.unsafeDrop n mv) vs
+-}
+
+-- | /O(n)/ Copy an immutable vector into a mutable one. The two vectors must
+-- have the same length.
+copy
+  :: (PrimMonad m, Vector v a) => Mutable v (PrimState m) a -> v a -> m ()
+{-# INLINE copy #-}
+copy dst src = BOUNDS_CHECK(check) "copy" "length mismatch"
+                                          (M.length dst == length src)
+             $ unsafeCopy dst src
+
+-- | /O(n)/ Copy an immutable vector into a mutable one. The two vectors must
+-- have the same length. This is not checked.
+unsafeCopy
+  :: (PrimMonad m, Vector v a) => Mutable v (PrimState m) a -> v a -> m ()
+{-# INLINE unsafeCopy #-}
+unsafeCopy dst src = UNSAFE_CHECK(check) "unsafeCopy" "length mismatch"
+                                         (M.length dst == length src)
+                   $ (dst `seq` src `seq` basicUnsafeCopy dst src)
+
+-- Conversions to/from Bundles
+-- ---------------------------
+
+-- | /O(1)/ Convert a vector to a 'Bundle'
+stream :: Vector v a => v a -> Bundle v a
+{-# INLINE_FUSED stream #-}
+stream v = Bundle.fromVector v
+
+{-
+stream v = v `seq` n `seq` (Bundle.unfoldr get 0 `Bundle.sized` Exact n)
+  where
+    n = length v
+
+    -- NOTE: the False case comes first in Core so making it the recursive one
+    -- makes the code easier to read
+    {-# 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 'Bundle'
+unstream :: Vector v a => Bundle v a -> v a
+{-# INLINE unstream #-}
+unstream s = new (New.unstream s)
+
+{-# RULES
+
+"stream/unstream [Vector]" forall s.
+  stream (new (New.unstream s)) = s
+
+"New.unstream/stream [Vector]" forall v.
+  New.unstream (stream v) = clone v
+
+"clone/new [Vector]" forall p.
+  clone (new p) = p
+
+"inplace [Vector]"
+  forall (f :: forall m. Monad m => MBundle m u a -> MBundle m u a) m.
+  New.unstream (inplace f (stream (new m))) = New.transform f m
+
+"uninplace [Vector]"
+  forall (f :: forall m. Monad m => MBundle m u a -> MBundle m u a) m.
+  stream (new (New.transform f m)) = inplace f (stream (new m))
+
+ #-}
+
+-- | /O(1)/ Convert a vector to a 'Bundle', proceeding from right to left
+streamR :: Vector v a => v a -> Bundle u a
+{-# INLINE_FUSED streamR #-}
+streamR v = v `seq` n `seq` (Bundle.unfoldr get n `Bundle.sized` Exact n)
+  where
+    n = length v
+
+    {-# INLINE get #-}
+    get 0 = Nothing
+    get i = let i' = i-1
+            in
+            case basicUnsafeIndexM v i' of Box x -> Just (x, i')
+
+-- | /O(n)/ Construct a vector from a 'Bundle', proceeding from right to left
+unstreamR :: Vector v a => Bundle v a -> v a
+{-# INLINE unstreamR #-}
+unstreamR s = new (New.unstreamR s)
+
+{-# RULES
+
+"streamR/unstreamR [Vector]" forall s.
+  streamR (new (New.unstreamR s)) = s
+
+"New.unstreamR/streamR/new [Vector]" forall p.
+  New.unstreamR (streamR (new p)) = p
+
+"New.unstream/streamR/new [Vector]" forall p.
+  New.unstream (streamR (new p)) = New.modify M.reverse p
+
+"New.unstreamR/stream/new [Vector]" forall p.
+  New.unstreamR (stream (new p)) = New.modify M.reverse p
+
+"inplace right [Vector]"
+  forall (f :: forall m. Monad m => MBundle m u a -> MBundle m u a) m.
+  New.unstreamR (inplace f (streamR (new m))) = New.transformR f m
+
+"uninplace right [Vector]"
+  forall (f :: forall m. Monad m => MBundle m u a -> MBundle m u a) m.
+  streamR (new (New.transformR f m)) = inplace f (streamR (new m))
+
+ #-}
+
+unstreamM :: (Monad m, Vector v a) => MBundle m u a -> m (v a)
+{-# INLINE_FUSED unstreamM #-}
+unstreamM s = do
+                xs <- MBundle.toList s
+                return $ unstream $ Bundle.unsafeFromList (MBundle.size s) xs
+
+unstreamPrimM :: (PrimMonad m, Vector v a) => MBundle m u a -> m (v a)
+{-# INLINE_FUSED unstreamPrimM #-}
+unstreamPrimM s = M.munstream s >>= unsafeFreeze
+
+-- FIXME: the next two functions are only necessary for the specialisations
+unstreamPrimM_IO :: Vector v a => MBundle IO u a -> IO (v a)
+{-# INLINE unstreamPrimM_IO #-}
+unstreamPrimM_IO = unstreamPrimM
+
+unstreamPrimM_ST :: Vector v a => MBundle (ST s) u a -> ST s (v a)
+{-# INLINE unstreamPrimM_ST #-}
+unstreamPrimM_ST = unstreamPrimM
+
+{-# RULES
+
+"unstreamM[IO]" unstreamM = unstreamPrimM_IO
+"unstreamM[ST]" unstreamM = unstreamPrimM_ST
+
+ #-}
+
+
+-- Recycling support
+-- -----------------
+
+-- | Construct a vector from a monadic initialiser.
+new :: Vector v a => New v a -> v a
+{-# INLINE_FUSED new #-}
+new m = m `seq` runST (unsafeFreeze =<< New.run m)
+
+-- | Convert a vector to an initialiser which, when run, produces a copy of
+-- the vector.
+clone :: Vector v a => v a -> New v a
+{-# INLINE_FUSED clone #-}
+clone v = v `seq` New.create (
+  do
+    mv <- M.new (length v)
+    unsafeCopy mv v
+    return mv)
 
 
--- Utilities for defining Data instances
--- -------------------------------------
+-- Comparisons
+-- -----------
+
+-- | /O(n)/ Check if two vectors are equal. All 'Vector' instances are also
+-- instances of 'Eq' and it is usually more appropriate to use those. This
+-- function is primarily intended for implementing 'Eq' instances for new
+-- vector types.
+eq :: (Vector v a, Eq a) => v a -> v a -> Bool
+{-# INLINE eq #-}
+xs `eq` ys = stream xs == stream ys
+
+-- | /O(n)/ Compare two vectors lexicographically. All 'Vector' instances are
+-- also instances of 'Ord' and it is usually more appropriate to use those. This
+-- function is primarily intended for implementing 'Ord' instances for new
+-- vector types.
+cmp :: (Vector v a, Ord a) => v a -> v a -> Ordering
+{-# INLINE cmp #-}
+cmp xs ys = compare (stream xs) (stream ys)
+
+-- Show
+-- ----
+
+-- | Generic definition of 'Prelude.showsPrec'
+showsPrec :: (Vector v a, Show a) => Int -> v a -> ShowS
+{-# INLINE showsPrec #-}
+showsPrec p v = showParen (p > 10) $ showString "fromList " . shows (toList v)
+
+-- | Generic definition of 'Text.Read.readPrec'
+readPrec :: (Vector v a, Read a) => Read.ReadPrec (v a)
+{-# INLINE readPrec #-}
+readPrec = Read.parens $ Read.prec 10 $ do
+  Read.Ident "fromList" <- Read.lexP
+  xs <- Read.readPrec
+  return (fromList xs)
+
+-- Data and Typeable
+-- -----------------
 
 -- | Generic definion of 'Data.Data.gfoldl' that views a 'Vector' as a
 -- list.
 
 -- | Generic definion of 'Data.Data.gfoldl' that views a 'Vector' as a
 -- list.
@@ -1302,7 +2019,7 @@ gfoldl f z v = z fromList `f` toList v
 
 mkType :: String -> DataType
 {-# INLINE mkType #-}
 
 mkType :: String -> DataType
 {-# INLINE mkType #-}
-mkType = mkNorepType
+mkType = mkNoRepType
 
 dataCast :: (Vector v a, Data a, Typeable1 v, Typeable1 t)
          => (forall d. Data  d => c (t d)) -> Maybe  (c (v a))
 
 dataCast :: (Vector v a, Data a, Typeable1 v, Typeable1 t)
          => (forall d. Data  d => c (t d)) -> Maybe  (c (v a))