content: {-# LANGUAGE Rank2Types, MultiParamTypeClasses, FlexibleContexts,
               TypeFamilies, ScopedTypeVariables, BangPatterns #-}
  -- |
  -- Module      : Data.Vector.Generic
  -- 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.
  --
  
  module Data.Vector.Generic (
    -- * Immutable vectors
    Vector(..), Mutable,
  
    -- * Accessors
  
    -- ** Length information
    length, null,
  
    -- ** Indexing
    (!), (!?), head, last,
    unsafeIndex, unsafeHead, unsafeLast,
  
    -- ** Monadic indexing
    indexM, headM, lastM,
    unsafeIndexM, unsafeHeadM, unsafeLastM,
  
    -- ** Extracting subvectors (slicing)
    slice, init, tail, take, drop, splitAt,
    unsafeSlice, unsafeInit, unsafeTail, unsafeTake, unsafeDrop,
  
    -- * 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_,
    unsafeUpd, unsafeUpdate, unsafeUpdate_,
  
    -- ** Accumulations
    accum, accumulate, accumulate_,
    unsafeAccum, unsafeAccumulate, unsafeAccumulate_,
  
    -- ** Permutations 
    reverse, backpermute, unsafeBackpermute,
  
    -- ** Safe destructive updates
    modify,
  
    -- * Elementwise operations
  
    -- ** Indexing
    indexed,
  
    -- ** Mapping
    map, imap, concatMap,
  
    -- ** Monadic mapping
    mapM, mapM_, forM, forM_,
  
    -- ** Zipping
    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,
  
    -- * Working with predicates
  
    -- ** Filtering
    filter, ifilter, filterM,
    takeWhile, dropWhile,
  
    -- ** Partitioning
    partition, unstablePartition, span, break,
  
    -- ** Searching
    elem, notElem, find, findIndex, findIndices, elemIndex, elemIndices,
  
    -- * 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,
  
    -- ** Monadic folds
    foldM, foldM', fold1M, fold1M',
    foldM_, foldM'_, fold1M_, fold1M'_,
  
    -- ** Monadic sequencing
    sequence, sequence_,
  
    -- * Prefix sums (scans)
    prescanl, prescanl',
    postscanl, postscanl',
    scanl, scanl', scanl1, scanl1',
    prescanr, prescanr',
    postscanr, postscanr',
    scanr, scanr', scanr1, scanr1',
  
    -- * Conversions
  
    -- ** Lists
    toList, fromList, fromListN,
  
    -- ** Different vector types
    convert,
  
    -- ** Mutable vectors
    freeze, thaw, copy, unsafeFreeze, unsafeThaw, unsafeCopy,
  
    -- * Fusion support
  
    -- ** Conversion to/from Streams
    stream, unstream, streamR, unstreamR,
  
    -- ** Recycling support
    new, clone,
  
    -- * Utilities
  
    -- ** Comparisons
    eq, cmp,
  
    -- ** Show and Read
    showsPrec, readPrec,
  
    -- ** @Data@ and @Typeable@
    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 qualified Data.Vector.Fusion.Stream as Stream
  import           Data.Vector.Fusion.Stream ( Stream, MStream, Step(..), inplace, liftStream )
  import qualified Data.Vector.Fusion.Stream.Monadic as MStream
  import           Data.Vector.Fusion.Stream.Size
  import           Data.Vector.Fusion.Util
  
  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
  
  #if __GLASGOW_HASKELL__ >= 707
  import Data.Typeable ( Typeable, gcast1 )
  #else
  import Data.Typeable ( Typeable1, gcast1 )
  #endif
  
  #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_STREAM length #-}
  length v = basicLength v
  
  {-# RULES
  
  "length/unstream [Vector]" forall s.
    length (new (New.unstream s)) = Stream.length s
  
    #-}
  
  -- | /O(1)/ Test whether a vector if empty
  null :: Vector v a => v a -> Bool
  {-# INLINE_STREAM null #-}
  null v = basicLength v == 0
  
  {-# RULES
  
  "null/unstream [Vector]" forall s.
    null (new (New.unstream s)) = Stream.null s
  
    #-}
  
  -- Indexing
  -- --------
  
  infixl 9 !
  -- | O(1) Indexing
  (!) :: Vector v a => v a -> Int -> a
  {-# INLINE_STREAM (!) #-}
  (!) 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_STREAM (!?) #-}
  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 #-}
  head v = v ! 0
  
  -- | /O(1)/ Last element
  last :: Vector v a => v a -> a
  {-# INLINE_STREAM last #-}
  last v = v ! (length v - 1)
  
  -- | /O(1)/ Unsafe indexing without bounds checking
  unsafeIndex :: Vector v a => v a -> Int -> a
  {-# INLINE_STREAM 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_STREAM 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_STREAM unsafeLast #-}
  unsafeLast v = unsafeIndex v (length v - 1)
  
  {-# RULES
  
  "(!)/unstream [Vector]" forall i s.
    new (New.unstream s) ! i = s Stream.!! i
  
  "(!?)/unstream [Vector]" forall i s.
    new (New.unstream s) !? i = s Stream.!? i
  
  "head/unstream [Vector]" forall s.
    head (new (New.unstream s)) = Stream.head s
  
  "last/unstream [Vector]" forall s.
    last (new (New.unstream s)) = Stream.last s
  
  "unsafeIndex/unstream [Vector]" forall i s.
    unsafeIndex (new (New.unstream s)) i = s Stream.!! i
  
  "unsafeHead/unstream [Vector]" forall s.
    unsafeHead (new (New.unstream s)) = Stream.head s
  
  "unsafeLast/unstream [Vector]" forall s.
    unsafeLast (new (New.unstream s)) = Stream.last s
  
   #-}
  
  -- 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 = 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 #-}
  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 #-}
  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_STREAM 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_STREAM 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_STREAM unsafeLastM #-}
  unsafeLastM v = unsafeIndexM v (length v - 1)
  
  {-# RULES
  
  "indexM/unstream [Vector]" forall s i.
    indexM (new (New.unstream s)) i = liftStream s MStream.!! i
  
  "headM/unstream [Vector]" forall s.
    headM (new (New.unstream s)) = MStream.head (liftStream s)
  
  "lastM/unstream [Vector]" forall s.
    lastM (new (New.unstream s)) = MStream.last (liftStream s)
  
  "unsafeIndexM/unstream [Vector]" forall s i.
    unsafeIndexM (new (New.unstream s)) i = liftStream s MStream.!! i
  
  "unsafeHeadM/unstream [Vector]" forall s.
    unsafeHeadM (new (New.unstream s)) = MStream.head (liftStream s)
  
  "unsafeLastM/unstream [Vector]" forall s.
    unsafeLastM (new (New.unstream s)) = MStream.last (liftStream s)
  
    #-}
  
  -- 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_STREAM 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 0 (length v - 1) v
  
  -- | /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 1 (length v - 1) v
  
  -- | /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 = unsafeSlice 0 (delay_inline min n' (length v)) v
    where n' = max n 0
  
  -- | /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 = 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_STREAM 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_STREAM 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_STREAM 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_STREAM 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 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)
  
  "take/new [Vector]" forall n p.
    take n (new p) = new (New.take 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 p) = new (New.unsafeSlice i 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)
  
    #-}
  
  -- Initialisation
  -- --------------
  
  -- | /O(1)/ Empty vector
  empty :: Vector v a => v a
  {-# INLINE empty #-}
  empty = unstream Stream.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 (Stream.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
                $ Stream.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 (Stream.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 (Stream.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 . Stream.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 . Stream.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
  
  
  -- 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
                      $ Stream.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 (Stream.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 (Stream.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
           $ Stream.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
           $ Stream.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 Stream.++ stream w)
  
  -- | /O(n)/ Concatenate all vectors in the list
  concat :: Vector v a => [v a] -> v a
  {-# INLINE concat #-}
  concat vs = unstream (Stream.flatten mk step (Exact n) (Stream.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 -> Stream.Yield x (v,i+1,k)
        | otherwise = Stream.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 (MStream.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 (MStream.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_STREAM 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 (Stream.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 (Stream.zipWith (,) (stream is) (stream w))
  
  update_stream :: Vector v a => v a -> Stream (Int,a) -> v a
  {-# INLINE update_stream #-}
  update_stream = modifyWithStream 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 (Stream.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 (Stream.zipWith (,) (stream is) (stream w))
  
  unsafeUpdate_stream :: Vector v a => v a -> Stream (Int,a) -> v a
  {-# INLINE unsafeUpdate_stream #-}
  unsafeUpdate_stream = modifyWithStream 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 (Stream.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@.
  --
  -- > 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 (Stream.zipWith (,) (stream is)
                                                               (stream xs))
                                          
  
  accum_stream :: Vector v a => (a -> b -> a) -> v a -> Stream (Int,b) -> v a
  {-# INLINE accum_stream #-}
  accum_stream f = modifyWithStream (M.accum f)
  
  -- | 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 (Stream.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 (Stream.zipWith (,) (stream is) (stream xs))
  
  unsafeAccum_stream
    :: Vector v a => (a -> b -> a) -> v a -> Stream (Int,b) -> v a
  {-# INLINE unsafeAccum_stream #-}
  unsafeAccum_stream f = modifyWithStream (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
                   $ Stream.unbox
                   $ Stream.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 = 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
                         $ Stream.unbox
                         $ Stream.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.
  modifyWithStream :: Vector v a
                   => (forall s. Mutable v s a -> Stream b -> ST s ())
                   -> v a -> Stream b -> v a
  {-# INLINE modifyWithStream #-}
  modifyWithStream p v s = new (New.modifyWithStream p (clone v) s)
  
  -- 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 . Stream.indexed . stream
  
  -- Mapping
  -- -------
  
  -- | /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
  
  -- | /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 (MStream.map (uncurry f) . MStream.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 #-}
  -- NOTE: We can't fuse concatMap anyway so don't pretend we do.
  -- This seems to be slightly slower
  -- concatMap f = concat . Stream.toList . Stream.map f . stream
  
  -- Slowest
  -- concatMap f = unstream . Stream.concatMap (stream . f) . stream
  
  -- Seems to be fastest
  concatMap f = unstream
              . Stream.flatten mk step Unknown
              . stream
    where
      {-# INLINE_INNER step #-}
      step (v,i,k)
        | i < k = case unsafeIndexM v i of
                    Box x -> Stream.Yield x (v,i+1,k)
        | otherwise = Stream.Done
  
      {-# INLINE mk #-}
      mk x = let v = f x
                 k = length v
             in
             k `seq` (v,0,k)
  
  -- 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 . Stream.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 = Stream.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
  -- -------
  
  -- | /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))
  
  -- | 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)
                                                    (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 (Stream.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 (Stream.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 (Stream.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
                    (Stream.zipWith (uncurry f) (Stream.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 (Stream.zipWith3 (uncurry f) (Stream.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 (Stream.zipWith4 (uncurry f) (Stream.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 (Stream.zipWith5 (uncurry f) (Stream.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 (Stream.zipWith6 (uncurry f) (Stream.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)
  {-# 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 $ Stream.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 = Stream.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)
  {-# INLINE unzip3 #-}
  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
  -- ---------
  
  -- | /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
  
  -- | /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 (MStream.map snd . MStream.filter (uncurry f)
                                       . MStream.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 . Stream.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
  
  -- | /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
  
  -- 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) -> Stream a -> (v a, v a)
  {-# INLINE_STREAM partition_stream #-}
  partition_stream f s = s `seq` runST (
    do
      (mv1,mv2) <- M.partitionStream 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) -> Stream a -> (v a, v a)
  {-# INLINE_STREAM unstablePartition_stream #-}
  unstablePartition_stream f s = s `seq` runST (
    do
      (mv1,mv2) <- M.unstablePartitionStream 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_STREAM 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`
  -- | /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
  
  infix 4 `notElem`
  -- | /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
  
  -- | /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
  
  -- | /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
  
  -- | /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 (MStream.map fst . MStream.filter (f . snd)
                                           . MStream.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
  -- -------
  
  -- | /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
  
  -- | /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
  
  -- | /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
  
  -- | /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
  
  -- | /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
  
  -- | /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
  
  -- | /O(n)/ Right fold with a strict accumulator
  foldr' :: Vector v a => (a -> b -> b) -> b -> v a -> b
  {-# INLINE foldr' #-}
  foldr' f z = Stream.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 = Stream.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 = Stream.foldl (uncurry . f) z . Stream.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 = Stream.foldl' (uncurry . f) z . Stream.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 = Stream.foldr (uncurry f) z . Stream.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 = Stream.foldl' (flip (uncurry f)) z
                 $ Stream.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 = Stream.and . Stream.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 = Stream.or . Stream.map f . stream
  
  -- | /O(n)/ Check if all elements are 'True'
  and :: Vector v Bool => v Bool -> Bool
  {-# INLINE and #-}
  and = Stream.and . stream
  
  -- | /O(n)/ Check if any element is 'True'
  or :: Vector v Bool => v Bool -> Bool
  {-# INLINE or #-}
  or = Stream.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
  
  -- | /O(n)/ Compute the produce of the elements
  product :: (Vector v a, Num a) => v a -> a
  {-# INLINE product #-}
  product = Stream.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
  
  -- | /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 = Stream.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
  
  -- | /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 = Stream.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 . Stream.foldl1' imax . Stream.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 . Stream.foldl1' imin . Stream.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 = Stream.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 = Stream.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 = Stream.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 = Stream.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 . Stream.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 . Stream.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 . Stream.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 . Stream.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
  
  -- | /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
  
  -- | /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
  
  -- | /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
  
  -- | /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
  
  -- | /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
  
  -- | /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
  
  -- | /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
  
  -- | /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 (MStream.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 (MStream.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 (MStream.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 (MStream.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 . Stream.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 . Stream.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 (MStream.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 (MStream.scanl1' (flip f)) . streamR
  
  -- Conversions - Lists
  -- ------------------------
  
  -- | /O(n)/ Convert a vector to a list
  toList :: Vector v a => v a -> [a]
  {-# INLINE toList #-}
  toList = Stream.toList . stream
  
  -- | /O(n)/ Convert a list to a vector
  fromList :: Vector v a => [a] -> v a
  {-# INLINE fromList #-}
  fromList = unstream . Stream.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 . Stream.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 . 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_STREAM 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_STREAM 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_STREAM 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 Streams
  -- ---------------------------
  
  -- | /O(1)/ Convert a vector to a 'Stream'
  stream :: Vector v a => v a -> Stream a
  {-# INLINE_STREAM stream #-}
  stream v = v `seq` n `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)
  
  -- | /O(n)/ Construct 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 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 => MStream m a -> MStream m a) m.
    New.unstream (inplace f (stream (new m))) = New.transform f m
  
  "uninplace [Vector]"
    forall (f :: forall m. Monad m => MStream m a -> MStream m a) m.
    stream (new (New.transform f m)) = inplace f (stream (new m))
  
   #-}
  
  -- | /O(1)/ Convert a vector to a 'Stream', proceeding from right to left
  streamR :: Vector v a => v a -> Stream a
  {-# INLINE_STREAM streamR #-}
  streamR v = v `seq` n `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')
  
  -- | /O(n)/ Construct a vector from a 'Stream', proceeding from right to left
  unstreamR :: Vector v a => Stream 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 => MStream m a -> MStream m a) m.
    New.unstreamR (inplace f (streamR (new m))) = New.transformR f m
  
  "uninplace right [Vector]"
    forall (f :: forall m. Monad m => MStream m a -> MStream m a) m.
    streamR (new (New.transformR f m)) = inplace f (streamR (new m))
  
   #-}
  
  unstreamM :: (Monad m, Vector v a) => MStream m a -> m (v a)
  {-# INLINE_STREAM unstreamM #-}
  unstreamM s = do
                  xs <- MStream.toList s
                  return $ unstream $ Stream.unsafeFromList (MStream.size s) xs
  
  unstreamPrimM :: (PrimMonad m, Vector v a) => MStream m a -> m (v a)
  {-# INLINE_STREAM unstreamPrimM #-}
  unstreamPrimM s = M.munstream s >>= unsafeFreeze
  
  -- FIXME: the next two functions are only necessary for the specialisations
  unstreamPrimM_IO :: Vector v a => MStream IO a -> IO (v a)
  {-# INLINE unstreamPrimM_IO #-}
  unstreamPrimM_IO = unstreamPrimM
  
  unstreamPrimM_ST :: Vector v a => MStream (ST s) 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_STREAM 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_STREAM 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
  
  #if __GLASGOW_HASKELL__ >= 707
  dataCast :: (Vector v a, Data a, Typeable v, Typeable t)
  #else
  dataCast :: (Vector v a, Data a, Typeable1 v, Typeable1 t)
  #endif
           => (forall d. Data  d => c (t d)) -> Maybe  (c (v a))
  {-# INLINE dataCast #-}
  dataCast f = gcast1 f
  
  