Finish Stream -> Bundle renaming
[darcs-mirrors/vector.git] / Data / Vector / Generic.hs
index 82c6ed7..9483020 100644 (file)
 {-# LANGUAGE Rank2Types, MultiParamTypeClasses, FlexibleContexts,
-             ScopedTypeVariables #-}
+             TypeFamilies, ScopedTypeVariables, BangPatterns #-}
 -- |
 -- 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
 -- 
--- Generic interface to pure vectors
+-- Generic interface to pure vectors.
 --
 
-#include "phases.h"
-
 module Data.Vector.Generic (
   -- * Immutable vectors
-  Vector(..),
+  Vector(..), Mutable,
+
+  -- * Accessors
 
-  -- * Length information
+  -- ** Length information
   length, null,
 
-  -- * Construction
-  empty, singleton, cons, snoc, replicate, (++), copy,
+  -- ** Indexing
+  (!), (!?), head, last,
+  unsafeIndex, unsafeHead, unsafeLast,
 
-  -- * Accessing individual elements
-  (!), head, last, indexM, headM, lastM,
+  -- ** Monadic indexing
+  indexM, headM, lastM,
+  unsafeIndexM, unsafeHeadM, unsafeLastM,
 
-  -- * Subvectors
-  slice, init, tail, take, drop,
+  -- ** Extracting subvectors (slicing)
+  slice, init, tail, take, drop, splitAt,
+  unsafeSlice, unsafeInit, unsafeTail, unsafeTake, unsafeDrop,
 
-  -- * Permutations
-  accum, (//), update, backpermute, reverse,
+  -- * Construction
 
-  -- * Mapping
-  map, concatMap,
+  -- ** Initialisation
+  empty, singleton, replicate, generate, iterateN,
 
-  -- * Zipping and unzipping
-  zipWith, zipWith3, zip, zip3, unzip, unzip3,
+  -- ** Monadic initialisation
+  replicateM, generateM, create,
 
-  -- * Comparisons
-  eq, cmp,
+  -- ** Unfolding
+  unfoldr, unfoldrN,
+  constructN, constructrN,
 
-  -- * Filtering
-  filter, takeWhile, dropWhile,
+  -- ** Enumeration
+  enumFromN, enumFromStepN, enumFromTo, enumFromThenTo,
 
-  -- * Searching
-  elem, notElem, find, findIndex,
+  -- ** Concatenation
+  cons, snoc, (++), concat,
 
-  -- * Folding
-  foldl, foldl1, foldl', foldl1', foldr, foldr1,
-  -- * Specialised folds
-  and, or, sum, product, maximum, minimum,
+  -- ** Restricting memory usage
+  force,
 
-  -- * Unfolding
-  unfoldr,
+  -- * Modifying vectors
 
-  -- * Scans
-  prescanl, prescanl',
-  postscanl, postscanl',
-  scanl, scanl', scanl1, scanl1',
+  -- ** Bulk updates
+  (//), update, update_,
+  unsafeUpd, unsafeUpdate, unsafeUpdate_,
 
-  -- * Enumeration
-  enumFromTo, enumFromThenTo,
+  -- ** Accumulations
+  accum, accumulate, accumulate_,
+  unsafeAccum, unsafeAccumulate, unsafeAccumulate_,
 
-  -- * Conversion to/from lists
-  toList, fromList,
+  -- ** Permutations 
+  reverse, backpermute, unsafeBackpermute,
 
-  -- * Conversion to/from Streams
-  stream, unstream,
+  -- ** Safe destructive updates
+  modify,
 
-  -- * MVector-based initialisation
-  new
-) where
+  -- * Elementwise operations
 
-import qualified Data.Vector.Generic.Mutable as Mut
-import           Data.Vector.Generic.Mutable ( MVector )
+  -- ** Indexing
+  indexed,
 
-import qualified Data.Vector.Generic.New as New
-import           Data.Vector.Generic.New ( New )
+  -- ** Mapping
+  map, imap, concatMap,
 
-import qualified Data.Vector.Fusion.Stream as Stream
-import           Data.Vector.Fusion.Stream ( Stream, MStream, inplace, inplace' )
-import qualified Data.Vector.Fusion.Stream.Monadic as MStream
-import           Data.Vector.Fusion.Stream.Size
-import           Data.Vector.Fusion.Util
+  -- ** Monadic mapping
+  mapM, mapM_, forM, forM_,
 
-import Control.Exception ( assert )
+  -- ** Zipping
+  zipWith, zipWith3, zipWith4, zipWith5, zipWith6,
+  izipWith, izipWith3, izipWith4, izipWith5, izipWith6,
+  zip, zip3, zip4, zip5, zip6,
 
-import Prelude hiding ( length, null,
-                        replicate, (++),
-                        head, last,
-                        init, tail, take, drop, reverse,
-                        map, concatMap,
-                        zipWith, zipWith3, zip, zip3, unzip, unzip3,
-                        filter, takeWhile, dropWhile,
-                        elem, notElem,
-                        foldl, foldl1, foldr, foldr1,
-                        and, or, sum, product, maximum, minimum,
-                        scanl, scanl1,
-                        enumFromTo, enumFromThenTo )
-
--- | Class of immutable vectors.
---
-class Vector v a where
-  -- | Construct a pure vector from a monadic initialiser (not fusible!)
-  vnew         :: (forall mv m. MVector mv m a => m (mv a)) -> v a
-
-  -- | Length of the vector (not fusible!)
-  vlength      :: v a -> Int
-
-  -- | Yield a part of the vector without copying it. No range checks!
-  unsafeSlice  :: v a -> Int -> Int -> 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 'unsafeIndexM', we can do
-  --
-  -- > copy mv v ... = ... case unsafeIndexM 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.
-  --
-  unsafeIndexM  :: Monad m => v a -> Int -> m a
-
--- 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 = vnew (New.run m)
-
--- | 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
+  -- ** Monadic zipping
+  zipWithM, zipWithM_,
 
-    {-# INLINE get #-}
-    get i | i < n     = case unsafeIndexM v i of Box x -> Just (x, i+1)
-          | otherwise = Nothing
-
--- | Create a vector from a 'Stream'
-unstream :: Vector v a => Stream a -> v a
-{-# INLINE unstream #-}
-unstream s = new (New.unstream s)
-
-{-# RULES
+  -- ** Unzipping
+  unzip, unzip3, unzip4, unzip5, unzip6,
 
-"stream/unstream [Vector]" forall v s.
-  stream (new' v (New.unstream s)) = s
+  -- * Working with predicates
 
-"New.unstream/stream/new [Vector]" forall v p.
-  New.unstream (stream (new' v p)) = p
+  -- ** Filtering
+  filter, ifilter, filterM,
+  takeWhile, dropWhile,
 
- #-}
+  -- ** Partitioning
+  partition, unstablePartition, span, break,
 
-{-# 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
+  -- ** Searching
+  elem, notElem, find, findIndex, findIndices, elemIndex, elemIndices,
 
-"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))
+  -- * Folding
+  foldl, foldl1, foldl', foldl1', foldr, foldr1, foldr', foldr1',
+  ifoldl, ifoldl', ifoldr, ifoldr',
 
- #-}
+  -- ** Specialised folds
+  all, any, and, or,
+  sum, product,
+  maximum, maximumBy, minimum, minimumBy,
+  minIndex, minIndexBy, maxIndex, maxIndexBy,
 
--- Length
--- ------
+  -- ** Monadic folds
+  foldM, foldM', fold1M, fold1M',
+  foldM_, foldM'_, fold1M_, fold1M'_,
 
-length :: Vector v a => v a -> Int
-{-# INLINE_STREAM length #-}
-length v = vlength v
+  -- ** Monadic sequencing
+  sequence, sequence_,
 
-{-# RULES
+  -- * Prefix sums (scans)
+  prescanl, prescanl',
+  postscanl, postscanl',
+  scanl, scanl', scanl1, scanl1',
+  prescanr, prescanr',
+  postscanr, postscanr',
+  scanr, scanr', scanr1, scanr1',
 
-"length/unstream [Vector]" forall v s.
-  length (new' v (New.unstream s)) = Stream.length s
+  -- * Conversions
 
-  #-}
+  -- ** Lists
+  toList, fromList, fromListN,
 
-null :: Vector v a => v a -> Bool
-{-# INLINE_STREAM null #-}
-null v = vlength v == 0
+  -- ** Different vector types
+  convert,
 
-{-# RULES
+  -- ** Mutable vectors
+  freeze, thaw, copy, unsafeFreeze, unsafeThaw, unsafeCopy,
 
-"null/unstream [Vector]" forall v s.
-  null (new' v (New.unstream s)) = Stream.null s
+  -- * Fusion support
 
-  #-}
+  -- ** Conversion to/from Bundles
+  stream, unstream, streamR, unstreamR,
 
--- Construction
--- ------------
+  -- ** Recycling support
+  new, clone,
 
--- | Empty vector
-empty :: Vector v a => v a
-{-# INLINE empty #-}
-empty = unstream Stream.empty
+  -- * Utilities
 
--- | Vector with exaclty one element
-singleton :: Vector v a => a -> v a
-{-# INLINE singleton #-}
-singleton x = unstream (Stream.singleton x)
+  -- ** Comparisons
+  eq, cmp,
 
--- | Vector of the given length with the given value in each position
-replicate :: Vector v a => Int -> a -> v a
-{-# INLINE replicate #-}
-replicate n = unstream . Stream.replicate n
+  -- ** Show and Read
+  showsPrec, readPrec,
 
--- | Prepend an element
-cons :: Vector v a => a -> v a -> v a
-{-# INLINE cons #-}
-cons x = unstream . Stream.cons x . stream
+  -- ** @Data@ and @Typeable@
+  gfoldl, dataCast, mkType
+) where
 
--- | Append an element
-snoc :: Vector v a => v a -> a -> v a
-{-# INLINE snoc #-}
-snoc v = unstream . Stream.snoc (stream v)
+import           Data.Vector.Generic.Base
 
-infixr 5 ++
--- | Concatenate two vectors
-(++) :: Vector v a => v a -> v a -> v a
-{-# INLINE (++) #-}
-v ++ w = unstream (stream v Stream.++ stream w)
+import           Data.Vector.Generic.Mutable ( MVector )
+import qualified Data.Vector.Generic.Mutable as M
 
--- | 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
+import qualified Data.Vector.Generic.New as New
+import           Data.Vector.Generic.New ( New )
 
-{-# RULES
+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
 
-"copy/unstream [Vector]" forall v s.
-  copy (new' v (New.unstream s)) = new' v (New.unstream s)
+import Control.Monad.ST ( ST, runST )
+import Control.Monad.Primitive
+import qualified Control.Monad as Monad
+import qualified Data.List as List
+import Prelude hiding ( length, null,
+                        replicate, (++), concat,
+                        head, last,
+                        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,
+                        enumFromTo, enumFromThenTo,
+                        mapM, mapM_, sequence, sequence_,
+                        showsPrec )
+
+import qualified Text.Read as Read
+import Data.Typeable ( Typeable1, gcast1 )
+
+#include "vector.h"
+
+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
+
+-- Length information
+-- ------------------
+
+-- | /O(1)/ Yield the length of the vector.
+length :: Vector v a => v a -> Int
+{-# INLINE length #-}
+length = Bundle.length . stream
 
- #-}
+-- | /O(1)/ Test whether a vector if empty
+null :: Vector v a => v a -> Bool
+{-# INLINE null #-}
+null = Bundle.null . stream
 
--- Accessing individual elements
--- -----------------------------
+-- Indexing
+-- --------
 
--- | Indexing
+infixl 9 !
+-- | O(1) Indexing
 (!) :: Vector v a => v a -> Int -> a
-{-# INLINE_STREAM (!) #-}
-v ! i = assert (i >= 0 && i < length v)
-      $ unId (unsafeIndexM 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
-{-# INLINE_STREAM head #-}
+{-# INLINE_FUSED head #-}
 head v = v ! 0
 
--- | Last element
+-- | /O(1)/ Last element
 last :: Vector v a => v a -> a
-{-# INLINE_STREAM last #-}
+{-# INLINE_FUSED last #-}
 last v = v ! (length v - 1)
 
+-- | /O(1)/ Unsafe indexing without bounds checking
+unsafeIndex :: Vector v a => v a -> Int -> a
+{-# INLINE_FUSED unsafeIndex #-}
+unsafeIndex v i = UNSAFE_CHECK(checkIndex) "unsafeIndex" i (length v)
+                $ unId (basicUnsafeIndexM v i)
+
+-- | /O(1)/ First element without checking if the vector is empty
+unsafeHead :: Vector v a => v a -> a
+{-# INLINE_FUSED unsafeHead #-}
+unsafeHead v = unsafeIndex v 0
+
+-- | /O(1)/ Last element without checking if the vector is empty
+unsafeLast :: Vector v a => v a -> a
+{-# INLINE_FUSED unsafeLast #-}
+unsafeLast v = unsafeIndex v (length v - 1)
+
 {-# RULES
 
-"(!)/unstream [Vector]" forall v i s.
-  new' v (New.unstream s) ! i = s Stream.!! i
+"(!)/unstream [Vector]" forall i s.
+  new (New.unstream s) ! i = s Bundle.!! i
+
+"(!?)/unstream [Vector]" forall i s.
+  new (New.unstream s) !? i = s Bundle.!? i
+
+"head/unstream [Vector]" forall s.
+  head (new (New.unstream s)) = Bundle.head s
+
+"last/unstream [Vector]" forall s.
+  last (new (New.unstream s)) = Bundle.last s
+
+"unsafeIndex/unstream [Vector]" forall i s.
+  unsafeIndex (new (New.unstream s)) i = s Bundle.!! i
 
-"head/unstream [Vector]" forall v s.
-  head (new' v (New.unstream s)) = Stream.head s
+"unsafeHead/unstream [Vector]" forall s.
+  unsafeHead (new (New.unstream s)) = Bundle.head s
 
-"last/unstream [Vector]" forall v s.
-  last (new' v (New.unstream s)) = Stream.last 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
-{-# INLINE_STREAM indexM #-}
-indexM v i = assert (i >= 0 && i < length v)
-           $ unsafeIndexM v i
+{-# INLINE_FUSED indexM #-}
+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
-{-# INLINE_STREAM headM #-}
+{-# INLINE_FUSED headM #-}
 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
-{-# INLINE_STREAM lastM #-}
+{-# INLINE_FUSED lastM #-}
 lastM v = indexM v (length v - 1)
 
+-- | /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
+{-# INLINE_FUSED unsafeIndexM #-}
+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
+{-# INLINE_FUSED unsafeHeadM #-}
+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
+{-# INLINE_FUSED unsafeLastM #-}
+unsafeLastM v = unsafeIndexM v (length v - 1)
+
 {-# 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. Safer version of
--- 'unsafeSlice'.
-slice :: Vector v a => v a -> Int   -- ^ starting index
-                            -> Int   -- ^ length
-                            -> v a
-{-# INLINE_STREAM slice #-}
-slice v i n = assert (i >= 0 && n >= 0  && i+n <= length v)
-            $ unsafeSlice v i n
+  #-}
 
--- | Yield all but the last element without copying.
+-- 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
+{-# INLINE_FUSED slice #-}
+slice i n v = BOUNDS_CHECK(checkSlice) "slice" i n (length v)
+            $ basicUnsafeSlice i n v
+
+-- | /O(1)/ Yield all but the last element without copying. The vector may not
+-- be empty.
 init :: Vector v a => v a -> v a
-{-# INLINE_STREAM init #-}
-init v = slice v 0 (length v - 1)
+{-# INLINE_FUSED init #-}
+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
-{-# INLINE_STREAM tail #-}
-tail v = slice v 1 (length v - 1)
+{-# INLINE_FUSED tail #-}
+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
-{-# INLINE_STREAM take #-}
-take n v = slice v 0 (min n' (length v))
+{-# INLINE_FUSED take #-}
+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
-{-# INLINE_STREAM drop #-}
-drop n v = slice v (min n' len) (max 0 (len - n'))
+{-# 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
 
+-- | /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
+{-# INLINE_FUSED unsafeSlice #-}
+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
+{-# INLINE_FUSED unsafeInit #-}
+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
+{-# INLINE_FUSED unsafeTail #-}
+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
+
+-- | /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
 
-"slice/new [Vector]" forall v p i n.
-  slice (new' v p) i n = new' v (New.slice p i n)
+"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 p) = new (New.init p)
+
+"tail/new [Vector]" forall p.
+  tail (new p) = new (New.tail p)
 
-"init/new [Vector]" forall v p.
-  init (new' v p) = new' v (New.init p)
+"take/new [Vector]" forall n p.
+  take n (new p) = new (New.take n p)
 
-"tail/new [Vector]" forall v p.
-  tail (new' v p) = new' v (New.tail p)
+"drop/new [Vector]" forall n p.
+  drop n (new p) = new (New.drop n p)
 
-"take/new [Vector]" forall n v p.
-  take n (new' v p) = new' v (New.take n p)
+"unsafeSlice/new [Vector]" forall i n p.
+  unsafeSlice i n (new p) = new (New.unsafeSlice i n p)
 
-"drop/new [Vector]" forall n v p.
-  drop n (new' v p) = new' v (New.drop n p)
+"unsafeInit/new [Vector]" forall p.
+  unsafeInit (new p) = new (New.unsafeInit p)
+
+"unsafeTail/new [Vector]" forall p.
+  unsafeTail (new p) = new (New.unsafeTail p)
 
   #-}
 
--- Permutations
--- ------------
+-- Initialisation
+-- --------------
+
+-- | /O(1)/ Empty vector
+empty :: Vector v a => v a
+{-# INLINE empty #-}
+empty = unstream Bundle.empty
+
+-- | /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)
+
+-- | /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
+
+-- | /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)
+
+-- | /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)
+
+-- Unfolding
+-- ---------
+
+-- | /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
+
+-- | /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
+
+-- | /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
 
-accum :: Vector v a => (a -> b -> a) -> v a -> [(Int,b)] -> v a
-{-# INLINE accum #-}
-accum f v us = new (New.accum f (New.unstream (stream v))
-                                (Stream.fromList us))
 
-(//) :: Vector v a => v a -> [(Int, a)] -> v a
+-- 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 = new (New.update (New.unstream (stream v))
-                          (Stream.fromList us))
+v // us = update_stream v (Bundle.fromList us)
 
-update :: (Vector v a, Vector v (Int, a)) => v a -> v (Int, a) -> v a
+-- | /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 = new (New.update (New.unstream (stream v)) (stream w))
+update v w = update_stream v (stream w)
 
--- 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 @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 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)
+
+-- | 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_stream v (Bundle.zipWith (,) (stream is) (stream w))
+
+unsafeUpdate_stream :: Vector v a => v a -> Bundle u (Int,a) -> v a
+{-# INLINE unsafeUpdate_stream #-}
+unsafeUpdate_stream = modifyWithBundle M.unsafeUpdate
+
+-- Accumulations
+-- -------------
+
+-- | /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)
+
+-- | /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@.
 --
--- backpermute v is = map (v!) is
-backpermute :: (Vector v a, Vector v Int) => v a -> v Int -> v a
+-- > 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)
+
+-- | /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>
+--
+-- 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 #-}
+-- 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
+                 $ seq n
                  $ unstream
-                 $ MStream.trans (Id . unBox)
-                 $ MStream.mapM (indexM v)
-                 $ MStream.trans (Box . unId)
+                 $ Bundle.unbox
+                 $ Bundle.map index
                  $ stream is
+  where
+    n = length v
 
-reverse :: (Vector v a) => v a -> v a
-{-# INLINE reverse #-}
-reverse = new . New.reverse . New.unstream . stream
+    {-# 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
+                       $ seq n
+                       $ unstream
+                       $ Bundle.unbox
+                       $ Bundle.map index
+                       $ 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 = 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
 -- -------
 
--- | 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 f = unstream . inplace' (MStream.map f) . stream
+map f = unstream . inplace (MBundle.map f) . stream
+
+-- | /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 f = unstream . inplace (MBundle.map (uncurry f) . MBundle.indexed)
+                  . 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 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.
-zipWith :: (Vector v a, Vector v b, Vector v c) => (a -> b -> c) -> v a -> v b -> v c
+-- | /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 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
+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 xs ys zs = unstream (Stream.zipWith3 f (stream xs) (stream ys) (stream zs))
-
+zipWith3 f as bs cs = unstream (Bundle.zipWith3 f (stream as)
+                                                  (stream bs)
+                                                  (stream cs))
+
+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
+  = unstream (Bundle.zipWith4 f (stream as)
+                                (stream bs)
+                                (stream cs)
+                                (stream ds))
+
+zipWith5 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e,
+             Vector v f)
+         => (a -> b -> c -> d -> e -> f) -> v a -> v b -> v c -> v d -> v e
+                                         -> v f
+{-# INLINE zipWith5 #-}
+zipWith5 f as bs cs ds es
+  = unstream (Bundle.zipWith5 f (stream as)
+                                (stream bs)
+                                (stream cs)
+                                (stream ds)
+                                (stream es))
+
+zipWith6 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e,
+             Vector v f, Vector v g)
+         => (a -> b -> c -> d -> e -> f -> g)
+         -> 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 (Bundle.zipWith6 f (stream as)
+                                (stream bs)
+                                (stream cs)
+                                (stream ds)
+                                (stream es)
+                                (stream fs))
+
+-- | /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
+                  (Bundle.zipWith (uncurry f) (Bundle.indexed (stream xs))
+                                                              (stream ys))
+
+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 (Bundle.zipWith3 (uncurry f) (Bundle.indexed (stream as))
+                                                          (stream bs)
+                                                          (stream cs))
+
+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
+  = unstream (Bundle.zipWith4 (uncurry f) (Bundle.indexed (stream as))
+                                                          (stream bs)
+                                                          (stream cs)
+                                                          (stream ds))
+
+izipWith5 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e,
+             Vector v f)
+         => (Int -> a -> b -> c -> d -> e -> f) -> v a -> v b -> v c -> v d
+                                                -> v e -> v f
+{-# INLINE izipWith5 #-}
+izipWith5 f as bs cs ds es
+  = unstream (Bundle.zipWith5 (uncurry f) (Bundle.indexed (stream as))
+                                                          (stream bs)
+                                                          (stream cs)
+                                                          (stream ds)
+                                                          (stream es))
+
+izipWith6 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e,
+             Vector v f, Vector v g)
+         => (Int -> a -> b -> c -> d -> e -> f -> g)
+         -> 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 (Bundle.zipWith6 (uncurry f) (Bundle.indexed (stream as))
+                                                          (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 (,)
 
-zip3 :: (Vector v a, Vector v b, Vector v c, Vector v (a, b, c)) => v a -> v b -> v c -> v (a, b, c)
+zip3 :: (Vector v a, Vector v b, Vector v c, Vector v (a, b, c))
+     => v a -> v b -> v c -> v (a, b, c)
 {-# INLINE zip3 #-}
 zip3 = zipWith3 (,,)
 
+zip4 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v (a, b, c, d))
+     => v a -> v b -> v c -> v d -> v (a, b, c, d)
+{-# INLINE zip4 #-}
+zip4 = zipWith4 (,,,)
+
+zip5 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e,
+         Vector v (a, b, c, d, e))
+     => v a -> v b -> v c -> v d -> v e -> v (a, b, c, d, e)
+{-# INLINE zip5 #-}
+zip5 = zipWith5 (,,,,)
+
+zip6 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e,
+         Vector v f, Vector v (a, b, c, d, e, f))
+     => v a -> v b -> v c -> v d -> v e -> v f -> v (a, b, c, d, e, f)
+{-# 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)
 
-unzip3 :: (Vector v a, Vector v b, Vector v c, Vector v (a, b, c)) => v (a, b, c) -> (v a, v b, v c)
+unzip3 :: (Vector v a, Vector v b, Vector v c, Vector v (a, b, c))
+       => v (a, b, c) -> (v a, v b, v c)
 {-# INLINE unzip3 #-}
-unzip3 xs = (map (\(a, b, c) -> a) xs, map (\(a, b, c) -> b) xs, map (\(a, b, c) -> c) 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)
+unzip3 xs = (map (\(a, b, c) -> a) xs,
+             map (\(a, b, c) -> b) xs,
+             map (\(a, b, c) -> c) xs)
+
+unzip4 :: (Vector v a, Vector v b, Vector v c, Vector v d,
+           Vector v (a, b, c, d))
+       => v (a, b, c, d) -> (v a, v b, v c, v d)
+{-# INLINE unzip4 #-}
+unzip4 xs = (map (\(a, b, c, d) -> a) xs,
+             map (\(a, b, c, d) -> b) xs,
+             map (\(a, b, c, d) -> c) xs,
+             map (\(a, b, c, d) -> d) xs)
+
+unzip5 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e,
+           Vector v (a, b, c, d, e))
+       => v (a, b, c, d, e) -> (v a, v b, v c, v d, v e)
+{-# INLINE unzip5 #-}
+unzip5 xs = (map (\(a, b, c, d, e) -> a) xs,
+             map (\(a, b, c, d, e) -> b) xs,
+             map (\(a, b, c, d, e) -> c) xs,
+             map (\(a, b, c, d, e) -> d) xs,
+             map (\(a, b, c, d, e) -> e) xs)
+
+unzip6 :: (Vector v a, Vector v b, Vector v c, Vector v d, Vector v e,
+           Vector v f, Vector v (a, b, c, d, e, f))
+       => v (a, b, c, d, e, f) -> (v a, v b, v c, v d, v e, v f)
+{-# INLINE unzip6 #-}
+unzip6 xs = (map (\(a, b, c, d, e, f) -> a) xs,
+             map (\(a, b, c, d, e, f) -> b) xs,
+             map (\(a, b, c, d, e, f) -> c) xs,
+             map (\(a, b, c, d, e, f) -> d) xs,
+             map (\(a, b, c, d, e, f) -> e) xs,
+             map (\(a, b, c, d, e, f) -> f) xs)
 
 -- Filtering
 -- ---------
 
--- | Drop elements which 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 f = unstream . inplace (MStream.filter f) . stream
-
--- | Yield the longest prefix of elements satisfying the predicate.
+filter f = unstream . inplace (MBundle.filter f) . stream
+
+-- | /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
+          . inplace (MBundle.map snd . MBundle.filter (uncurry f)
+                                     . MBundle.indexed)
+          . stream
+
+-- | /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 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 f = unstream . Stream.dropWhile f . stream
+dropWhile f = unstream . Bundle.dropWhile f . stream
+
+-- Parititioning
+-- -------------
+
+-- | /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 #-}
+partition f = partition_stream f . stream
+
+-- FIXME: Make this inplace-fusible (look at how stable_partition is
+-- implemented in C++)
+
+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
+    (mv1,mv2) <- M.partitionBundle f s
+    v1 <- unsafeFreeze mv1
+    v2 <- unsafeFreeze mv2
+    return (v1,v2))
+
+-- | /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
+  :: Vector v a => (a -> Bool) -> Bundle u a -> (v a, v a)
+{-# INLINE_FUSED unstablePartition_stream #-}
+unstablePartition_stream f s = s `seq` runST (
+  do
+    (mv1,mv2) <- M.unstablePartitionBundle f s
+    v1 <- unsafeFreeze mv1
+    v2 <- unsafeFreeze mv2
+    return (v1,v2))
+
+unstablePartition_new :: Vector v a => (a -> Bool) -> New v a -> (v a, v a)
+{-# INLINE_FUSED unstablePartition_new #-}
+unstablePartition_new f (New.New p) = runST (
+  do
+    mv <- p
+    i <- M.unstablePartition f mv
+    v <- unsafeFreeze mv
+    return (unsafeTake i v, unsafeDrop i v))
+
+{-# RULES
+
+"unstablePartition" forall f p.
+  unstablePartition_stream f (stream (new p))
+    = unstablePartition_new f p
+
+  #-}
+
+
+-- FIXME: make span and break fusible
+
+-- | /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)
+
+-- | /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
+               Just i  -> (unsafeSlice 0 i xs, unsafeSlice i (length xs - i) xs)
+               Nothing -> (xs, empty)
+    
 
 -- Searching
 -- ---------
 
 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 x = Stream.elem x . stream
+elem x = Bundle.elem x . stream
 
 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 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 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 f = Stream.findIndex f . stream
+findIndex f = Bundle.findIndex f . stream
+
+-- | /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
+              . inplace (MBundle.map fst . MBundle.filter (f . snd)
+                                         . MBundle.indexed)
+              . stream
+
+-- | /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==)
+
+-- | /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==)
 
 -- Folding
 -- -------
 
--- | Left fold
+-- | /O(n)/ Left fold
 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
 
--- | Lefgt 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 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' 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' 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 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 f = Stream.foldr1 f . stream
+foldr1 f = Bundle.foldr1 f . stream
+
+-- | /O(n)/ Right fold with a strict accumulator
+foldr' :: Vector v a => (a -> b -> b) -> b -> v a -> b
+{-# INLINE foldr' #-}
+foldr' f z = Bundle.foldl' (flip f) z . streamR
+
+-- | /O(n)/ Right fold on non-empty vectors with strict accumulator
+foldr1' :: Vector v a => (a -> a -> a) -> v a -> a
+{-# INLINE foldr1' #-}
+foldr1' f = Bundle.foldl1' (flip f) . streamR
+
+-- | /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 f z = Bundle.foldl (uncurry . f) z . Bundle.indexed . stream
+
+-- | /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' f z = Bundle.foldl' (uncurry . f) z . Bundle.indexed . stream
+
+-- | /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 f z = Bundle.foldr (uncurry f) z . Bundle.indexed . stream
+
+-- | /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' f z xs = Bundle.foldl' (flip (uncurry f)) z
+               $ Bundle.indexedR (length xs) $ streamR xs
 
 -- Specialised folds
 -- -----------------
 
+-- | /O(n)/ Check if all elements satisfy the predicate.
+all :: Vector v a => (a -> Bool) -> v a -> Bool
+{-# INLINE all #-}
+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 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 = 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 = 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 = 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 = 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 = 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 cmp = Bundle.foldl1' maxBy . stream
+  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 = Stream.foldl1' min . stream
-
--- Unfolding
--- ---------
-
-unfoldr :: Vector v a => (b -> Maybe (a, b)) -> b -> v a
-{-# INLINE unfoldr #-}
-unfoldr f = unstream . Stream.unfoldr f
+minimum = Bundle.foldl1' min . stream
 
--- Scans
--- -----
-
--- | Prefix scan
+-- | /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 cmp = Bundle.foldl1' minBy . stream
+  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
+
+-- | /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 cmp = fst . Bundle.foldl1' imax . Bundle.indexed . stream
+  where
+    imax (i,x) (j,y) = i `seq` j `seq`
+                       case cmp x y of
+                         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
+
+-- | /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 cmp = fst . Bundle.foldl1' imin . Bundle.indexed . stream
+  where
+    imin (i,x) (j,y) = i `seq` j `seq`
+                       case cmp x y of
+                         GT -> (j,y)
+                         _  -> (i,x)
+
+-- 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 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' 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 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' 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 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' 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 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' f = unstream . inplace (MStream.scanl1' f) . stream
+scanl1' f = unstream . inplace (MBundle.scanl1' f) . stream
 
--- Enumeration
--- -----------
+-- | /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 f z = unstreamR . inplace (MBundle.prescanl (flip f) z) . streamR
+
+-- | /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' f z = unstreamR . inplace (MBundle.prescanl' (flip f) z) . streamR
+
+-- | /O(n)/ Right-to-left scan
+postscanr :: (Vector v a, Vector v b) => (a -> b -> b) -> b -> v a -> v b
+{-# INLINE postscanr #-}
+postscanr f z = unstreamR . inplace (MBundle.postscanl (flip f) z) . streamR
+
+-- | /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' f z = unstreamR . inplace (MBundle.postscanl' (flip f) z) . streamR
+
+-- | /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 f z = unstreamR . Bundle.scanl (flip f) z . streamR
+
+-- | /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' f z = unstreamR . Bundle.scanl' (flip f) z . streamR
+
+-- | /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 f = unstreamR . inplace (MBundle.scanl1 (flip f)) . streamR
+
+-- | /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' f = unstreamR . inplace (MBundle.scanl1' (flip f)) . streamR
+
+-- Conversions - Lists
+-- ------------------------
+
+-- | /O(n)/ Convert a vector to a list
+toList :: Vector v a => v a -> [a]
+{-# INLINE toList #-}
+toList = Bundle.toList . stream
 
-enumFromTo :: (Vector v a, Enum a) => a -> a -> v a
-{-# INLINE enumFromTo #-}
-enumFromTo from to = from `seq` to `seq` unfoldr enumFromTo_go (fromEnum from)
+-- | /O(n)/ Convert a list to a vector
+fromList :: Vector v a => [a] -> v a
+{-# INLINE fromList #-}
+fromList = unstream . Bundle.fromList
+
+-- | /O(n)/ Convert the first @n@ elements of a list to a vector
+--
+-- @
+-- fromListN n xs = 'fromList' ('take' n xs)
+-- @
+fromListN :: Vector v a => Int -> [a] -> v a
+{-# INLINE fromListN #-}
+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
-    to_i = fromEnum to
-    enumFromTo_go i | i <= to_i = Just (toEnum i, i + 1)
-                    | otherwise = Nothing
+    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
 
-enumFromThenTo :: (Vector v a, Enum a) => a -> a -> a -> v a
-{-# INLINE enumFromThenTo #-}
-enumFromThenTo from next to = from `seq` next `seq` to `seq` unfoldr enumFromThenTo_go from_i
+    -- 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
-    from_i = fromEnum from
-    to_i = fromEnum to
-    step_i = fromEnum next - from_i
-    enumFromThenTo_go i | i <= to_i = Just (toEnum i, i + step_i)
-                        | otherwise = Nothing
+    n = length v
 
--- | Convert a vector to a list
-toList :: Vector v a => v a -> [a]
-{-# INLINE toList #-}
-toList = Stream.toList . stream
+    {-# INLINE get #-}
+    get 0 = Nothing
+    get i = let i' = i-1
+            in
+            case basicUnsafeIndexM v i' of Box x -> Just (x, i')
 
--- | Convert a list to a vector
-fromList :: Vector v a => [a] -> v a
-{-# INLINE fromList #-}
-fromList = unstream . Stream.fromList
+-- | /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)
+
+-- 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.
+gfoldl :: (Vector v a, Data a)
+       => (forall d b. Data d => c (d -> b) -> d -> c b)
+       -> (forall g. g -> c g)
+       -> v a
+       -> c (v a)
+{-# INLINE gfoldl #-}
+gfoldl f z v = z fromList `f` toList v
+
+mkType :: String -> DataType
+{-# INLINE mkType #-}
+mkType = mkNoRepType
+
+dataCast :: (Vector v a, Data a, Typeable1 v, Typeable1 t)
+         => (forall d. Data  d => c (t d)) -> Maybe  (c (v a))
+{-# INLINE dataCast #-}
+dataCast f = gcast1 f