Add constructN and constructrN
[darcs-mirrors/vector.git] / Data / Vector.hs
index 8f395e4..6b3cc98 100644 (file)
-{-# LANGUAGE MagicHash, UnboxedTuples, FlexibleInstances, MultiParamTypeClasses #-}
+{-# LANGUAGE FlexibleInstances, MultiParamTypeClasses, TypeFamilies, Rank2Types #-}
 
 -- |
 -- Module      : Data.Vector
--- Copyright   : (c) Roman Leshchinskiy 2008
+-- Copyright   : (c) Roman Leshchinskiy 2008-2010
 -- License     : BSD-style
 --
 -- Maintainer  : Roman Leshchinskiy <rl@cse.unsw.edu.au>
 -- Stability   : experimental
 -- Portability : non-portable
 -- 
--- Boxed vectors
+-- A library for boxed vectors (that is, polymorphic arrays capable of
+-- holding any Haskell value). The vectors come in two flavors:
+--
+--  * mutable
+--
+--  * immutable
+--
+-- and support a rich interface of both list-like operations, and bulk
+-- array operations.
+--
+-- For unboxed arrays, use the 'Data.Vector.Unboxed' interface.
 --
 
 module Data.Vector (
-  Vector,
+  -- * Boxed vectors
+  Vector, MVector,
 
-  -- * Length information
+  -- * 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
-  empty, singleton, cons, snoc, replicate, (++), copy,
 
-  -- * Accessing individual elements
-  (!), head, last, indexM, headM, lastM,
+  -- ** 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_,
 
-  -- * Subvectors
-  slice, init, tail, take, drop,
+  -- ** Accumulations
+  accum, accumulate, accumulate_,
+  unsafeAccum, unsafeAccumulate, unsafeAccumulate_,
 
-  -- * Permutations
-  accum, (//), update, backpermute, reverse,
+  -- ** Permutations 
+  reverse, backpermute, unsafeBackpermute,
 
-  -- * Mapping
-  map, concatMap,
+  -- ** Safe destructive updates
+  modify,
 
-  -- * Zipping and unzipping
-  zipWith, zipWith3, zip, zip3, unzip, unzip3,
+  -- * Elementwise operations
 
-  -- * Filtering
-  filter, takeWhile, dropWhile,
+  -- ** Indexing
+  indexed,
 
-  -- * Searching
-  elem, notElem, find, findIndex,
+  -- ** 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,
+  foldl, foldl1, foldl', foldl1', foldr, foldr1, foldr', foldr1',
+  ifoldl, ifoldl', ifoldr, ifoldr',
 
-  -- * Specialised folds
-  and, or, sum, product, maximum, minimum,
+  -- ** Specialised folds
+  all, any, and, or,
+  sum, product,
+  maximum, maximumBy, minimum, minimumBy,
+  minIndex, minIndexBy, maxIndex, maxIndexBy,
 
-  -- * Unfolding
-  unfoldr,
+  -- ** Monadic folds
+  foldM, foldM', fold1M, fold1M',
+  foldM_, foldM'_, fold1M_, fold1M'_,
 
-  -- * Scans
+  -- ** Monadic sequencing
+  sequence, sequence_,
+
+  -- * Prefix sums (scans)
   prescanl, prescanl',
   postscanl, postscanl',
   scanl, scanl', scanl1, scanl1',
+  prescanr, prescanr',
+  postscanr, postscanr',
+  scanr, scanr', scanr1, scanr1',
+
+  -- * Conversions
 
-  -- * Enumeration
-  enumFromTo, enumFromThenTo,
+  -- ** Lists
+  toList, fromList, fromListN,
 
-  -- * Conversion to/from lists
-  toList, fromList
+  -- ** Other vector types
+  G.convert,
+
+  -- ** Mutable vectors
+  freeze, thaw, copy, unsafeFreeze, unsafeThaw, unsafeCopy
 ) where
 
-import           Data.Vector.IVector ( IVector(..) )
-import qualified Data.Vector.IVector    as IV
-import qualified Data.Vector.Mutable    as Mut
+import qualified Data.Vector.Generic as G
+import           Data.Vector.Mutable  ( MVector(..) )
 import           Data.Primitive.Array
+import qualified Data.Vector.Fusion.Stream as Stream
 
-import Control.Monad.ST ( runST )
+import Control.Monad ( liftM, ap )
+import Control.Monad.ST ( ST )
+import Control.Monad.Primitive
 
 import Prelude hiding ( length, null,
-                        replicate, (++),
+                        replicate, (++), concat,
                         head, last,
-                        init, tail, take, drop, reverse,
+                        init, tail, take, drop, splitAt, reverse,
                         map, concatMap,
                         zipWith, zipWith3, zip, zip3, unzip, unzip3,
-                        filter, takeWhile, dropWhile,
+                        filter, takeWhile, dropWhile, span, break,
                         elem, notElem,
                         foldl, foldl1, foldr, foldr1,
-                        and, or, sum, product, minimum, maximum,
-                        scanl, scanl1,
-                        enumFromTo, enumFromThenTo )
+                        all, any, and, or, sum, product, minimum, maximum,
+                        scanl, scanl1, scanr, scanr1,
+                        enumFromTo, enumFromThenTo,
+                        mapM, mapM_, sequence, sequence_ )
 
 import qualified Prelude
 
+import Data.Typeable ( Typeable )
+import Data.Data     ( Data(..) )
+
+import Data.Monoid   ( Monoid(..) )
+import qualified Control.Applicative as Applicative
+import qualified Data.Foldable as Foldable
+import qualified Data.Traversable as Traversable
+
+-- | Boxed vectors, supporting efficient slicing.
 data Vector a = Vector {-# UNPACK #-} !Int
                        {-# UNPACK #-} !Int
                        {-# UNPACK #-} !(Array a)
+        deriving ( Typeable )
 
 instance Show a => Show (Vector a) where
     show = (Prelude.++ " :: Data.Vector.Vector") . ("fromList " Prelude.++) . show . toList
 
-instance IVector Vector a where
-  {-# INLINE vnew #-}
-  vnew init = runST (do
-                       Mut.Vector i n marr <- init
-                       arr <- unsafeFreezeArray marr
-                       return (Vector i n arr))
+instance Data a => Data (Vector a) where
+  gfoldl       = G.gfoldl
+  toConstr _   = error "toConstr"
+  gunfold _ _  = error "gunfold"
+  dataTypeOf _ = G.mkType "Data.Vector.Vector"
+  dataCast1    = G.dataCast
+
+type instance G.Mutable Vector = MVector
+
+instance G.Vector Vector a where
+  {-# INLINE basicUnsafeFreeze #-}
+  basicUnsafeFreeze (MVector i n marr)
+    = Vector i n `liftM` unsafeFreezeArray marr
 
-  {-# INLINE vlength #-}
-  vlength (Vector _ n _) = n
+  {-# INLINE basicUnsafeThaw #-}
+  basicUnsafeThaw (Vector i n arr)
+    = MVector i n `liftM` unsafeThawArray arr
 
-  {-# INLINE unsafeSlice #-}
-  unsafeSlice (Vector i _ arr) j n = Vector (i+j) n arr
+  {-# INLINE basicLength #-}
+  basicLength (Vector _ n _) = n
 
-  {-# INLINE unsafeIndexM #-}
-  unsafeIndexM (Vector i _ arr) j = indexArrayM arr (i+j)
+  {-# INLINE basicUnsafeSlice #-}
+  basicUnsafeSlice j n (Vector i _ arr) = Vector (i+j) n arr
 
+  {-# INLINE basicUnsafeIndexM #-}
+  basicUnsafeIndexM (Vector i _ arr) j = indexArrayM arr (i+j)
+
+  {-# INLINE basicUnsafeCopy #-}
+  basicUnsafeCopy (MVector i n dst) (Vector j _ src)
+    = copyArray src j dst i n
+
+-- See http://trac.haskell.org/vector/ticket/12
 instance Eq a => Eq (Vector a) where
   {-# INLINE (==) #-}
-  (==) = IV.eq
+  xs == ys = Stream.eq (G.stream xs) (G.stream ys)
 
+  {-# INLINE (/=) #-}
+  xs /= ys = not (Stream.eq (G.stream xs) (G.stream ys))
+
+-- See http://trac.haskell.org/vector/ticket/12
 instance Ord a => Ord (Vector a) where
   {-# INLINE compare #-}
-  compare = IV.cmp
+  compare xs ys = Stream.cmp (G.stream xs) (G.stream ys)
 
--- Length
--- ------
+  {-# INLINE (<) #-}
+  xs < ys = Stream.cmp (G.stream xs) (G.stream ys) == LT
 
-length :: Vector a -> Int
-{-# INLINE length #-}
-length = IV.length
+  {-# INLINE (<=) #-}
+  xs <= ys = Stream.cmp (G.stream xs) (G.stream ys) /= GT
 
-null :: Vector a -> Bool
-{-# INLINE null #-}
-null = IV.null
+  {-# INLINE (>) #-}
+  xs > ys = Stream.cmp (G.stream xs) (G.stream ys) == GT
 
--- Construction
--- ------------
+  {-# INLINE (>=) #-}
+  xs >= ys = Stream.cmp (G.stream xs) (G.stream ys) /= LT
 
--- | Empty vector
-empty :: Vector a
-{-# INLINE empty #-}
-empty = IV.empty
+instance Monoid (Vector a) where
+  {-# INLINE mempty #-}
+  mempty = empty
 
--- | Vector with exaclty one element
-singleton :: a -> Vector a
-{-# INLINE singleton #-}
-singleton = IV.singleton
+  {-# INLINE mappend #-}
+  mappend = (++)
 
--- | Vector of the given length with the given value in each position
-replicate :: Int -> a -> Vector a
-{-# INLINE replicate #-}
-replicate = IV.replicate
+  {-# INLINE mconcat #-}
+  mconcat = concat
 
--- | Prepend an element
-cons :: a -> Vector a -> Vector a
-{-# INLINE cons #-}
-cons = IV.cons
+instance Functor Vector where
+  {-# INLINE fmap #-}
+  fmap = map
 
--- | Append an element
-snoc :: Vector a -> a -> Vector a
-{-# INLINE snoc #-}
-snoc = IV.snoc
+instance Monad Vector where
+  {-# INLINE return #-}
+  return = singleton
 
-infixr 5 ++
--- | Concatenate two vectors
-(++) :: Vector a -> Vector a -> Vector a
-{-# INLINE (++) #-}
-(++) = (IV.++)
+  {-# INLINE (>>=) #-}
+  (>>=) = flip concatMap
 
--- | Create a copy of a vector. Useful when dealing with slices.
-copy :: Vector a -> Vector a
-{-# INLINE copy #-}
-copy = IV.copy
+instance Applicative.Applicative Vector where
+  {-# INLINE pure #-}
+  pure = singleton
 
--- Accessing individual elements
--- -----------------------------
+  {-# INLINE (<*>) #-}
+  (<*>) = ap
+
+instance Applicative.Alternative Vector where
+  {-# INLINE empty #-}
+  empty = empty
+
+  {-# INLINE (<|>) #-}
+  (<|>) = (++)
+
+instance Foldable.Foldable Vector where
+  {-# INLINE foldr #-}
+  foldr = foldr
+
+  {-# INLINE foldl #-}
+  foldl = foldl
+  
+  {-# INLINE foldr1 #-}
+  foldr1 = foldr1
+
+  {-# INLINE foldl1 #-}
+  foldl1 = foldl1
+
+instance Traversable.Traversable Vector where
+  {-# INLINE traverse #-}
+  traverse f xs = fromList Applicative.<$> Traversable.traverse f (toList xs)
+
+  {-# INLINE mapM #-}
+  mapM = mapM
 
--- | Indexing
+  {-# INLINE sequence #-}
+  sequence = sequence
+
+-- Length information
+-- ------------------
+
+-- | /O(1)/ Yield the length of the vector.
+length :: Vector a -> Int
+{-# INLINE length #-}
+length = G.length
+
+-- | /O(1)/ Test whether a vector if empty
+null :: Vector a -> Bool
+{-# INLINE null #-}
+null = G.null
+
+-- Indexing
+-- --------
+
+-- | O(1) Indexing
 (!) :: Vector a -> Int -> a
 {-# INLINE (!) #-}
-(!) = (IV.!)
+(!) = (G.!)
+
+-- | O(1) Safe indexing
+(!?) :: Vector a -> Int -> Maybe a
+{-# INLINE (!?) #-}
+(!?) = (G.!?)
 
--- | First element
+-- | /O(1)/ First element
 head :: Vector a -> a
 {-# INLINE head #-}
-head = IV.head
+head = G.head
 
--- | Last element
+-- | /O(1)/ Last element
 last :: Vector a -> a
 {-# INLINE last #-}
-last = IV.last
+last = G.last
+
+-- | /O(1)/ Unsafe indexing without bounds checking
+unsafeIndex :: Vector a -> Int -> a
+{-# INLINE unsafeIndex #-}
+unsafeIndex = G.unsafeIndex
+
+-- | /O(1)/ First element without checking if the vector is empty
+unsafeHead :: Vector a -> a
+{-# INLINE unsafeHead #-}
+unsafeHead = G.unsafeHead
 
--- | Monadic indexing which can be strict in the vector while remaining lazy in
--- the element
+-- | /O(1)/ Last element without checking if the vector is empty
+unsafeLast :: Vector a -> a
+{-# INLINE unsafeLast #-}
+unsafeLast = G.unsafeLast
+
+-- 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 :: Monad m => Vector a -> Int -> m a
 {-# INLINE indexM #-}
-indexM = IV.indexM
+indexM = G.indexM
 
+-- | /O(1)/ First element of a vector in a monad. See 'indexM' for an
+-- explanation of why this is useful.
 headM :: Monad m => Vector a -> m a
 {-# INLINE headM #-}
-headM = IV.headM
+headM = G.headM
 
+-- | /O(1)/ Last element of a vector in a monad. See 'indexM' for an
+-- explanation of why this is useful.
 lastM :: Monad m => Vector a -> m a
 {-# INLINE lastM #-}
-lastM = IV.lastM
-
--- Subarrays
--- ---------
-
--- | Yield a part of the vector without copying it. Safer version of
--- 'unsafeSlice'.
-slice :: Vector a -> Int   -- ^ starting index
-                  -> Int   -- ^ length
-                  -> Vector a
+lastM = G.lastM
+
+-- | /O(1)/ Indexing in a monad without bounds checks. See 'indexM' for an
+-- explanation of why this is useful.
+unsafeIndexM :: Monad m => Vector a -> Int -> m a
+{-# INLINE unsafeIndexM #-}
+unsafeIndexM = G.unsafeIndexM
+
+-- | /O(1)/ First element in a monad without checking for empty vectors.
+-- See 'indexM' for an explanation of why this is useful.
+unsafeHeadM :: Monad m => Vector a -> m a
+{-# INLINE unsafeHeadM #-}
+unsafeHeadM = G.unsafeHeadM
+
+-- | /O(1)/ Last element in a monad without checking for empty vectors.
+-- See 'indexM' for an explanation of why this is useful.
+unsafeLastM :: Monad m => Vector a -> m a
+{-# INLINE unsafeLastM #-}
+unsafeLastM = G.unsafeLastM
+
+-- Extracting subvectors (slicing)
+-- -------------------------------
+
+-- | /O(1)/ Yield a slice of the vector without copying it. The vector must
+-- contain at least @i+n@ elements.
+slice :: Int   -- ^ @i@ starting index
+                 -> Int   -- ^ @n@ length
+                 -> Vector a
+                 -> Vector a
 {-# INLINE slice #-}
-slice = IV.slice
+slice = G.slice
 
--- | Yield all but the last element without copying.
+-- | /O(1)/ Yield all but the last element without copying. The vector may not
+-- be empty.
 init :: Vector a -> Vector a
 {-# INLINE init #-}
-init = IV.init
+init = G.init
 
--- | 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 a -> Vector a
 {-# INLINE tail #-}
-tail = IV.tail
+tail = G.tail
 
--- | Yield the first @n@ elements without copying.
+-- | /O(1)/ Yield at the first @n@ elements without copying. The vector may
+-- contain less than @n@ elements in which case it is returned unchanged.
 take :: Int -> Vector a -> Vector a
 {-# INLINE take #-}
-take = IV.take
+take = G.take
 
--- | 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 :: Int -> Vector a -> Vector a
 {-# INLINE drop #-}
-drop = IV.drop
+drop = G.drop
 
--- Permutations
--- ------------
+-- | /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 splitAt #-}
+splitAt :: Int -> Vector a -> (Vector a, Vector a)
+splitAt = G.splitAt
+
+-- | /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 :: Int   -- ^ @i@ starting index
+                       -> Int   -- ^ @n@ length
+                       -> Vector a
+                       -> Vector a
+{-# INLINE unsafeSlice #-}
+unsafeSlice = G.unsafeSlice
+
+-- | /O(1)/ Yield all but the last element without copying. The vector may not
+-- be empty but this is not checked.
+unsafeInit :: Vector a -> Vector a
+{-# INLINE unsafeInit #-}
+unsafeInit = G.unsafeInit
+
+-- | /O(1)/ Yield all but the first element without copying. The vector may not
+-- be empty but this is not checked.
+unsafeTail :: Vector a -> Vector a
+{-# INLINE unsafeTail #-}
+unsafeTail = G.unsafeTail
+
+-- | /O(1)/ Yield the first @n@ elements without copying. The vector must
+-- contain at least @n@ elements but this is not checked.
+unsafeTake :: Int -> Vector a -> Vector a
+{-# INLINE unsafeTake #-}
+unsafeTake = G.unsafeTake
+
+-- | /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 :: Int -> Vector a -> Vector a
+{-# INLINE unsafeDrop #-}
+unsafeDrop = G.unsafeDrop
+
+-- Initialisation
+-- --------------
+
+-- | /O(1)/ Empty vector
+empty :: Vector a
+{-# INLINE empty #-}
+empty = G.empty
 
-accum :: (a -> b -> a) -> Vector a -> [(Int,b)] -> Vector a
-{-# INLINE accum #-}
-accum = IV.accum
+-- | /O(1)/ Vector with exactly one element
+singleton :: a -> Vector a
+{-# INLINE singleton #-}
+singleton = G.singleton
+
+-- | /O(n)/ Vector of the given length with the same value in each position
+replicate :: Int -> a -> Vector a
+{-# INLINE replicate #-}
+replicate = G.replicate
+
+-- | /O(n)/ Construct a vector of the given length by applying the function to
+-- each index
+generate :: Int -> (Int -> a) -> Vector a
+{-# INLINE generate #-}
+generate = G.generate
+
+-- | /O(n)/ Apply function n times to value. Zeroth element is original value.
+iterateN :: Int -> (a -> a) -> a -> Vector a
+{-# INLINE iterateN #-}
+iterateN = G.iterateN
+
+-- 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 :: (b -> Maybe (a, b)) -> b -> Vector a
+{-# INLINE unfoldr #-}
+unfoldr = G.unfoldr
+
+-- | /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 :: Int -> (b -> Maybe (a, b)) -> b -> Vector a
+{-# INLINE unfoldrN #-}
+unfoldrN = G.unfoldrN
+
+-- | /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 :: Int -> (Vector a -> a) -> Vector a
+{-# INLINE constructN #-}
+constructN = G.constructN
 
-(//) :: Vector a -> [(Int, a)] -> Vector a
+-- | /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 :: Int -> (Vector a -> a) -> Vector a
+{-# INLINE constructrN #-}
+constructrN = G.constructrN
+
+-- 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 :: Num a => a -> Int -> Vector a
+{-# INLINE enumFromN #-}
+enumFromN = G.enumFromN
+
+-- | /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 :: Num a => a -> a -> Int -> Vector a
+{-# INLINE enumFromStepN #-}
+enumFromStepN = G.enumFromStepN
+
+-- | /O(n)/ Enumerate values from @x@ to @y@.
+--
+-- /WARNING:/ This operation can be very inefficient. If at all possible, use
+-- 'enumFromN' instead.
+enumFromTo :: Enum a => a -> a -> Vector a
+{-# INLINE enumFromTo #-}
+enumFromTo = G.enumFromTo
+
+-- | /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 :: Enum a => a -> a -> a -> Vector a
+{-# INLINE enumFromThenTo #-}
+enumFromThenTo = G.enumFromThenTo
+
+-- Concatenation
+-- -------------
+
+-- | /O(n)/ Prepend an element
+cons :: a -> Vector a -> Vector a
+{-# INLINE cons #-}
+cons = G.cons
+
+-- | /O(n)/ Append an element
+snoc :: Vector a -> a -> Vector a
+{-# INLINE snoc #-}
+snoc = G.snoc
+
+infixr 5 ++
+-- | /O(m+n)/ Concatenate two vectors
+(++) :: Vector a -> Vector a -> Vector a
+{-# INLINE (++) #-}
+(++) = (G.++)
+
+-- | /O(n)/ Concatenate all vectors in the list
+concat :: [Vector a] -> Vector a
+{-# INLINE concat #-}
+concat = G.concat
+
+-- Monadic initialisation
+-- ----------------------
+
+-- | /O(n)/ Execute the monadic action the given number of times and store the
+-- results in a vector.
+replicateM :: Monad m => Int -> m a -> m (Vector a)
+{-# INLINE replicateM #-}
+replicateM = G.replicateM
+
+-- | /O(n)/ Construct a vector of the given length by applying the monadic
+-- action to each index
+generateM :: Monad m => Int -> (Int -> m a) -> m (Vector a)
+{-# INLINE generateM #-}
+generateM = G.generateM
+
+-- | Execute the monadic action and freeze the resulting vector.
+--
+-- @
+-- create (do { v \<- new 2; write v 0 \'a\'; write v 1 \'b\' }) = \<'a','b'\>
+-- @
+create :: (forall s. ST s (MVector s a)) -> Vector a
+{-# INLINE create #-}
+-- NOTE: eta-expanded due to http://hackage.haskell.org/trac/ghc/ticket/4120
+create p = G.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 a -> Vector a
+{-# INLINE force #-}
+force = G.force
+
+-- 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 a   -- ^ initial vector (of length @m@)
+                -> [(Int, a)] -- ^ list of index/value pairs (of length @n@) 
+                -> Vector a
 {-# INLINE (//) #-}
-(//) = (IV.//)
+(//) = (G.//)
 
-update :: Vector a -> Vector (Int, a) -> Vector 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 a        -- ^ initial vector (of length @m@)
+       -> Vector (Int, a) -- ^ vector of index/value pairs (of length @n@)
+       -> Vector a
 {-# INLINE update #-}
-update = IV.update
+update = G.update
 
-backpermute :: Vector a -> Vector Int -> Vector a
-{-# INLINE backpermute #-}
-backpermute = IV.backpermute
+-- | /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>
+--
+-- The function 'update' provides the same functionality and is usually more
+-- convenient.
+--
+-- @
+-- update_ xs is ys = 'update' xs ('zip' is ys)
+-- @
+update_ :: Vector a   -- ^ initial vector (of length @m@)
+        -> Vector Int -- ^ index vector (of length @n1@)
+        -> Vector a   -- ^ value vector (of length @n2@)
+        -> Vector a
+{-# INLINE update_ #-}
+update_ = G.update_
+
+-- | Same as ('//') but without bounds checking.
+unsafeUpd :: Vector a -> [(Int, a)] -> Vector a
+{-# INLINE unsafeUpd #-}
+unsafeUpd = G.unsafeUpd
+
+-- | Same as 'update' but without bounds checking.
+unsafeUpdate :: Vector a -> Vector (Int, a) -> Vector a
+{-# INLINE unsafeUpdate #-}
+unsafeUpdate = G.unsafeUpdate
+
+-- | Same as 'update_' but without bounds checking.
+unsafeUpdate_ :: Vector a -> Vector Int -> Vector a -> Vector a
+{-# INLINE unsafeUpdate_ #-}
+unsafeUpdate_ = G.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 :: (a -> b -> a) -- ^ accumulating function @f@
+      -> Vector a      -- ^ initial vector (of length @m@)
+      -> [(Int,b)]     -- ^ list of index/value pairs (of length @n@)
+      -> Vector a
+{-# INLINE accum #-}
+accum = G.accum
+
+-- | /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 :: (a -> b -> a)  -- ^ accumulating function @f@
+            -> Vector a       -- ^ initial vector (of length @m@)
+            -> Vector (Int,b) -- ^ vector of index/value pairs (of length @n@)
+            -> Vector a
+{-# INLINE accumulate #-}
+accumulate = G.accumulate
+
+-- | /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>
+--
+-- The function 'accumulate' provides the same functionality and is usually more
+-- convenient.
+--
+-- @
+-- accumulate_ f as is bs = 'accumulate' f as ('zip' is bs)
+-- @
+accumulate_ :: (a -> b -> a) -- ^ accumulating function @f@
+            -> Vector a      -- ^ initial vector (of length @m@)
+            -> Vector Int    -- ^ index vector (of length @n1@)
+            -> Vector b      -- ^ value vector (of length @n2@)
+            -> Vector a
+{-# INLINE accumulate_ #-}
+accumulate_ = G.accumulate_
+
+-- | Same as 'accum' but without bounds checking.
+unsafeAccum :: (a -> b -> a) -> Vector a -> [(Int,b)] -> Vector a
+{-# INLINE unsafeAccum #-}
+unsafeAccum = G.unsafeAccum
+
+-- | Same as 'accumulate' but without bounds checking.
+unsafeAccumulate :: (a -> b -> a) -> Vector a -> Vector (Int,b) -> Vector a
+{-# INLINE unsafeAccumulate #-}
+unsafeAccumulate = G.unsafeAccumulate
+
+-- | Same as 'accumulate_' but without bounds checking.
+unsafeAccumulate_
+  :: (a -> b -> a) -> Vector a -> Vector Int -> Vector b -> Vector a
+{-# INLINE unsafeAccumulate_ #-}
+unsafeAccumulate_ = G.unsafeAccumulate_
 
+-- Permutations
+-- ------------
+
+-- | /O(n)/ Reverse a vector
 reverse :: Vector a -> Vector a
 {-# INLINE reverse #-}
-reverse = IV.reverse
+reverse = G.reverse
+
+-- | /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 a -> Vector Int -> Vector a
+{-# INLINE backpermute #-}
+backpermute = G.backpermute
+
+-- | Same as 'backpermute' but without bounds checking.
+unsafeBackpermute :: Vector a -> Vector Int -> Vector a
+{-# INLINE unsafeBackpermute #-}
+unsafeBackpermute = G.unsafeBackpermute
+
+-- 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 -> write v 0 \'x\') ('replicate' 3 \'a\') = \<\'x\',\'a\',\'a\'\>
+-- @
+modify :: (forall s. MVector s a -> ST s ()) -> Vector a -> Vector a
+{-# INLINE modify #-}
+modify p = G.modify p
+
+-- Indexing
+-- --------
+
+-- | /O(n)/ Pair each element in a vector with its index
+indexed :: Vector a -> Vector (Int,a)
+{-# INLINE indexed #-}
+indexed = G.indexed
 
 -- Mapping
 -- -------
 
--- | Map a function over a vector
+-- | /O(n)/ Map a function over a vector
 map :: (a -> b) -> Vector a -> Vector b
 {-# INLINE map #-}
-map = IV.map
+map = G.map
+
+-- | /O(n)/ Apply a function to every element of a vector and its index
+imap :: (Int -> a -> b) -> Vector a -> Vector b
+{-# INLINE imap #-}
+imap = G.imap
 
+-- | Map a function over a vector and concatenate the results.
 concatMap :: (a -> Vector b) -> Vector a -> Vector b
 {-# INLINE concatMap #-}
-concatMap = IV.concatMap
-
--- Zipping/unzipping
--- -----------------
+concatMap = G.concatMap
+
+-- Monadic mapping
+-- ---------------
+
+-- | /O(n)/ Apply the monadic action to all elements of the vector, yielding a
+-- vector of results
+mapM :: Monad m => (a -> m b) -> Vector a -> m (Vector b)
+{-# INLINE mapM #-}
+mapM = G.mapM
+
+-- | /O(n)/ Apply the monadic action to all elements of a vector and ignore the
+-- results
+mapM_ :: Monad m => (a -> m b) -> Vector a -> m ()
+{-# INLINE mapM_ #-}
+mapM_ = G.mapM_
+
+-- | /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 a -> (a -> m b) -> m (Vector b)
+{-# INLINE forM #-}
+forM = G.forM
+
+-- | /O(n)/ Apply the monadic action to all elements of a vector and ignore the
+-- results. Equivalent to @flip 'mapM_'@.
+forM_ :: Monad m => Vector a -> (a -> m b) -> m ()
+{-# INLINE forM_ #-}
+forM_ = G.forM_
+
+-- Zipping
+-- -------
 
--- | Zip two vectors with the given function.
+-- | /O(min(m,n))/ Zip two vectors with the given function.
 zipWith :: (a -> b -> c) -> Vector a -> Vector b -> Vector c
 {-# INLINE zipWith #-}
-zipWith = IV.zipWith
+zipWith = G.zipWith
 
 -- | Zip three vectors with the given function.
 zipWith3 :: (a -> b -> c -> d) -> Vector a -> Vector b -> Vector c -> Vector d
 {-# INLINE zipWith3 #-}
-zipWith3 = IV.zipWith3
-
+zipWith3 = G.zipWith3
+
+zipWith4 :: (a -> b -> c -> d -> e)
+         -> Vector a -> Vector b -> Vector c -> Vector d -> Vector e
+{-# INLINE zipWith4 #-}
+zipWith4 = G.zipWith4
+
+zipWith5 :: (a -> b -> c -> d -> e -> f)
+         -> Vector a -> Vector b -> Vector c -> Vector d -> Vector e
+         -> Vector f
+{-# INLINE zipWith5 #-}
+zipWith5 = G.zipWith5
+
+zipWith6 :: (a -> b -> c -> d -> e -> f -> g)
+         -> Vector a -> Vector b -> Vector c -> Vector d -> Vector e
+         -> Vector f -> Vector g
+{-# INLINE zipWith6 #-}
+zipWith6 = G.zipWith6
+
+-- | /O(min(m,n))/ Zip two vectors with a function that also takes the
+-- elements' indices.
+izipWith :: (Int -> a -> b -> c) -> Vector a -> Vector b -> Vector c
+{-# INLINE izipWith #-}
+izipWith = G.izipWith
+
+-- | Zip three vectors and their indices with the given function.
+izipWith3 :: (Int -> a -> b -> c -> d)
+          -> Vector a -> Vector b -> Vector c -> Vector d
+{-# INLINE izipWith3 #-}
+izipWith3 = G.izipWith3
+
+izipWith4 :: (Int -> a -> b -> c -> d -> e)
+          -> Vector a -> Vector b -> Vector c -> Vector d -> Vector e
+{-# INLINE izipWith4 #-}
+izipWith4 = G.izipWith4
+
+izipWith5 :: (Int -> a -> b -> c -> d -> e -> f)
+          -> Vector a -> Vector b -> Vector c -> Vector d -> Vector e
+          -> Vector f
+{-# INLINE izipWith5 #-}
+izipWith5 = G.izipWith5
+
+izipWith6 :: (Int -> a -> b -> c -> d -> e -> f -> g)
+          -> Vector a -> Vector b -> Vector c -> Vector d -> Vector e
+          -> Vector f -> Vector g
+{-# INLINE izipWith6 #-}
+izipWith6 = G.izipWith6
+
+-- | Elementwise pairing of array elements. 
 zip :: Vector a -> Vector b -> Vector (a, b)
 {-# INLINE zip #-}
-zip = IV.zip
+zip = G.zip
 
+-- | zip together three vectors into a vector of triples
 zip3 :: Vector a -> Vector b -> Vector c -> Vector (a, b, c)
 {-# INLINE zip3 #-}
-zip3 = IV.zip3
+zip3 = G.zip3
 
+zip4 :: Vector a -> Vector b -> Vector c -> Vector d
+     -> Vector (a, b, c, d)
+{-# INLINE zip4 #-}
+zip4 = G.zip4
+
+zip5 :: Vector a -> Vector b -> Vector c -> Vector d -> Vector e
+     -> Vector (a, b, c, d, e)
+{-# INLINE zip5 #-}
+zip5 = G.zip5
+
+zip6 :: Vector a -> Vector b -> Vector c -> Vector d -> Vector e -> Vector f
+     -> Vector (a, b, c, d, e, f)
+{-# INLINE zip6 #-}
+zip6 = G.zip6
+
+-- Unzipping
+-- ---------
+
+-- | /O(min(m,n))/ Unzip a vector of pairs.
 unzip :: Vector (a, b) -> (Vector a, Vector b)
 {-# INLINE unzip #-}
-unzip = IV.unzip
+unzip = G.unzip
 
 unzip3 :: Vector (a, b, c) -> (Vector a, Vector b, Vector c)
 {-# INLINE unzip3 #-}
-unzip3 = IV.unzip3
+unzip3 = G.unzip3
+
+unzip4 :: Vector (a, b, c, d) -> (Vector a, Vector b, Vector c, Vector d)
+{-# INLINE unzip4 #-}
+unzip4 = G.unzip4
+
+unzip5 :: Vector (a, b, c, d, e)
+       -> (Vector a, Vector b, Vector c, Vector d, Vector e)
+{-# INLINE unzip5 #-}
+unzip5 = G.unzip5
+
+unzip6 :: Vector (a, b, c, d, e, f)
+       -> (Vector a, Vector b, Vector c, Vector d, Vector e, Vector f)
+{-# INLINE unzip6 #-}
+unzip6 = G.unzip6
+
+-- Monadic zipping
+-- ---------------
+
+-- | /O(min(m,n))/ Zip the two vectors with the monadic action and yield a
+-- vector of results
+zipWithM :: Monad m => (a -> b -> m c) -> Vector a -> Vector b -> m (Vector c)
+{-# INLINE zipWithM #-}
+zipWithM = G.zipWithM
+
+-- | /O(min(m,n))/ Zip the two vectors with the monadic action and ignore the
+-- results
+zipWithM_ :: Monad m => (a -> b -> m c) -> Vector a -> Vector b -> m ()
+{-# INLINE zipWithM_ #-}
+zipWithM_ = G.zipWithM_
 
 -- Filtering
 -- ---------
 
--- | Drop elements which do not satisfy the predicate
+-- | /O(n)/ Drop elements that do not satisfy the predicate
 filter :: (a -> Bool) -> Vector a -> Vector a
 {-# INLINE filter #-}
-filter = IV.filter
+filter = G.filter
 
--- | Yield the longest prefix of elements satisfying the predicate.
+-- | /O(n)/ Drop elements that do not satisfy the predicate which is applied to
+-- values and their indices
+ifilter :: (Int -> a -> Bool) -> Vector a -> Vector a
+{-# INLINE ifilter #-}
+ifilter = G.ifilter
+
+-- | /O(n)/ Drop elements that do not satisfy the monadic predicate
+filterM :: Monad m => (a -> m Bool) -> Vector a -> m (Vector a)
+{-# INLINE filterM #-}
+filterM = G.filterM
+
+-- | /O(n)/ Yield the longest prefix of elements satisfying the predicate
+-- without copying.
 takeWhile :: (a -> Bool) -> Vector a -> Vector a
 {-# INLINE takeWhile #-}
-takeWhile = IV.takeWhile
+takeWhile = G.takeWhile
 
--- | 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 :: (a -> Bool) -> Vector a -> Vector a
 {-# INLINE dropWhile #-}
-dropWhile = IV.dropWhile
+dropWhile = G.dropWhile
+
+-- 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 :: (a -> Bool) -> Vector a -> (Vector a, Vector a)
+{-# INLINE partition #-}
+partition = G.partition
+
+-- | /O(n)/ Split the vector in two parts, the first one containing those
+-- elements that satisfy the predicate and the second one those that don't.
+-- The order of the elements is not preserved but the operation is often
+-- faster than 'partition'.
+unstablePartition :: (a -> Bool) -> Vector a -> (Vector a, Vector a)
+{-# INLINE unstablePartition #-}
+unstablePartition = G.unstablePartition
+
+-- | /O(n)/ Split the vector into the longest prefix of elements that satisfy
+-- the predicate and the rest without copying.
+span :: (a -> Bool) -> Vector a -> (Vector a, Vector a)
+{-# INLINE span #-}
+span = G.span
+
+-- | /O(n)/ Split the vector into the longest prefix of elements that do not
+-- satisfy the predicate and the rest without copying.
+break :: (a -> Bool) -> Vector a -> (Vector a, Vector a)
+{-# INLINE break #-}
+break = G.break
 
 -- Searching
 -- ---------
 
 infix 4 `elem`
--- | Check whether the vector contains an element
+-- | /O(n)/ Check if the vector contains an element
 elem :: Eq a => a -> Vector a -> Bool
 {-# INLINE elem #-}
-elem = IV.elem
+elem = G.elem
 
 infix 4 `notElem`
--- | Inverse of `elem`
+-- | /O(n)/ Check if the vector does not contain an element (inverse of 'elem')
 notElem :: Eq a => a -> Vector a -> Bool
 {-# INLINE notElem #-}
-notElem = IV.notElem
+notElem = G.notElem
 
--- | 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 :: (a -> Bool) -> Vector a -> Maybe a
 {-# INLINE find #-}
-find = IV.find
+find = G.find
 
--- | 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 :: (a -> Bool) -> Vector a -> Maybe Int
 {-# INLINE findIndex #-}
-findIndex = IV.findIndex
+findIndex = G.findIndex
+
+-- | /O(n)/ Yield the indices of elements satisfying the predicate in ascending
+-- order.
+findIndices :: (a -> Bool) -> Vector a -> Vector Int
+{-# INLINE findIndices #-}
+findIndices = G.findIndices
+
+-- | /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 :: Eq a => a -> Vector a -> Maybe Int
+{-# INLINE elemIndex #-}
+elemIndex = G.elemIndex
+
+-- | /O(n)/ Yield the indices of all occurences of the given element in
+-- ascending order. This is a specialised version of 'findIndices'.
+elemIndices :: Eq a => a -> Vector a -> Vector Int
+{-# INLINE elemIndices #-}
+elemIndices = G.elemIndices
 
 -- Folding
 -- -------
 
--- | Left fold
+-- | /O(n)/ Left fold
 foldl :: (a -> b -> a) -> a -> Vector b -> a
 {-# INLINE foldl #-}
-foldl = IV.foldl
+foldl = G.foldl
 
--- | Lefgt fold on non-empty vectors
+-- | /O(n)/ Left fold on non-empty vectors
 foldl1 :: (a -> a -> a) -> Vector a -> a
 {-# INLINE foldl1 #-}
-foldl1 = IV.foldl1
+foldl1 = G.foldl1
 
--- | Left fold with strict accumulator
+-- | /O(n)/ Left fold with strict accumulator
 foldl' :: (a -> b -> a) -> a -> Vector b -> a
 {-# INLINE foldl' #-}
-foldl' = IV.foldl'
+foldl' = G.foldl'
 
--- | Left fold on non-empty vectors with strict accumulator
+-- | /O(n)/ Left fold on non-empty vectors with strict accumulator
 foldl1' :: (a -> a -> a) -> Vector a -> a
 {-# INLINE foldl1' #-}
-foldl1' = IV.foldl1'
+foldl1' = G.foldl1'
 
--- | Right fold
+-- | /O(n)/ Right fold
 foldr :: (a -> b -> b) -> b -> Vector a -> b
 {-# INLINE foldr #-}
-foldr = IV.foldr
+foldr = G.foldr
 
--- | Right fold on non-empty vectors
+-- | /O(n)/ Right fold on non-empty vectors
 foldr1 :: (a -> a -> a) -> Vector a -> a
 {-# INLINE foldr1 #-}
-foldr1 = IV.foldr1
+foldr1 = G.foldr1
+
+-- | /O(n)/ Right fold with a strict accumulator
+foldr' :: (a -> b -> b) -> b -> Vector a -> b
+{-# INLINE foldr' #-}
+foldr' = G.foldr'
+
+-- | /O(n)/ Right fold on non-empty vectors with strict accumulator
+foldr1' :: (a -> a -> a) -> Vector a -> a
+{-# INLINE foldr1' #-}
+foldr1' = G.foldr1'
+
+-- | /O(n)/ Left fold (function applied to each element and its index)
+ifoldl :: (a -> Int -> b -> a) -> a -> Vector b -> a
+{-# INLINE ifoldl #-}
+ifoldl = G.ifoldl
+
+-- | /O(n)/ Left fold with strict accumulator (function applied to each element
+-- and its index)
+ifoldl' :: (a -> Int -> b -> a) -> a -> Vector b -> a
+{-# INLINE ifoldl' #-}
+ifoldl' = G.ifoldl'
+
+-- | /O(n)/ Right fold (function applied to each element and its index)
+ifoldr :: (Int -> a -> b -> b) -> b -> Vector a -> b
+{-# INLINE ifoldr #-}
+ifoldr = G.ifoldr
+
+-- | /O(n)/ Right fold with strict accumulator (function applied to each
+-- element and its index)
+ifoldr' :: (Int -> a -> b -> b) -> b -> Vector a -> b
+{-# INLINE ifoldr' #-}
+ifoldr' = G.ifoldr'
 
 -- Specialised folds
 -- -----------------
 
+-- | /O(n)/ Check if all elements satisfy the predicate.
+all :: (a -> Bool) -> Vector a -> Bool
+{-# INLINE all #-}
+all = G.all
+
+-- | /O(n)/ Check if any element satisfies the predicate.
+any :: (a -> Bool) -> Vector a -> Bool
+{-# INLINE any #-}
+any = G.any
+
+-- | /O(n)/ Check if all elements are 'True'
 and :: Vector Bool -> Bool
 {-# INLINE and #-}
-and = IV.and
+and = G.and
 
+-- | /O(n)/ Check if any element is 'True'
 or :: Vector Bool -> Bool
 {-# INLINE or #-}
-or = IV.or
+or = G.or
 
+-- | /O(n)/ Compute the sum of the elements
 sum :: Num a => Vector a -> a
 {-# INLINE sum #-}
-sum = IV.sum
+sum = G.sum
 
+-- | /O(n)/ Compute the produce of the elements
 product :: Num a => Vector a -> a
 {-# INLINE product #-}
-product = IV.product
+product = G.product
 
+-- | /O(n)/ Yield the maximum element of the vector. The vector may not be
+-- empty.
 maximum :: Ord a => Vector a -> a
 {-# INLINE maximum #-}
-maximum = IV.maximum
+maximum = G.maximum
 
+-- | /O(n)/ Yield the maximum element of the vector according to the given
+-- comparison function. The vector may not be empty.
+maximumBy :: (a -> a -> Ordering) -> Vector a -> a
+{-# INLINE maximumBy #-}
+maximumBy = G.maximumBy
+
+-- | /O(n)/ Yield the minimum element of the vector. The vector may not be
+-- empty.
 minimum :: Ord a => Vector a -> a
 {-# INLINE minimum #-}
-minimum = IV.minimum
-
--- Unfolding
--- ---------
-
-unfoldr :: (b -> Maybe (a, b)) -> b -> Vector a
-{-# INLINE unfoldr #-}
-unfoldr = IV.unfoldr
-
--- Scans
--- -----
-
--- | Prefix scan
+minimum = G.minimum
+
+-- | /O(n)/ Yield the minimum element of the vector according to the given
+-- comparison function. The vector may not be empty.
+minimumBy :: (a -> a -> Ordering) -> Vector a -> a
+{-# INLINE minimumBy #-}
+minimumBy = G.minimumBy
+
+-- | /O(n)/ Yield the index of the maximum element of the vector. The vector
+-- may not be empty.
+maxIndex :: Ord a => Vector a -> Int
+{-# INLINE maxIndex #-}
+maxIndex = G.maxIndex
+
+-- | /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 :: (a -> a -> Ordering) -> Vector a -> Int
+{-# INLINE maxIndexBy #-}
+maxIndexBy = G.maxIndexBy
+
+-- | /O(n)/ Yield the index of the minimum element of the vector. The vector
+-- may not be empty.
+minIndex :: Ord a => Vector a -> Int
+{-# INLINE minIndex #-}
+minIndex = G.minIndex
+
+-- | /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 :: (a -> a -> Ordering) -> Vector a -> Int
+{-# INLINE minIndexBy #-}
+minIndexBy = G.minIndexBy
+
+-- Monadic folds
+-- -------------
+
+-- | /O(n)/ Monadic fold
+foldM :: Monad m => (a -> b -> m a) -> a -> Vector b -> m a
+{-# INLINE foldM #-}
+foldM = G.foldM
+
+-- | /O(n)/ Monadic fold over non-empty vectors
+fold1M :: Monad m => (a -> a -> m a) -> Vector a -> m a
+{-# INLINE fold1M #-}
+fold1M = G.fold1M
+
+-- | /O(n)/ Monadic fold with strict accumulator
+foldM' :: Monad m => (a -> b -> m a) -> a -> Vector b -> m a
+{-# INLINE foldM' #-}
+foldM' = G.foldM'
+
+-- | /O(n)/ Monadic fold over non-empty vectors with strict accumulator
+fold1M' :: Monad m => (a -> a -> m a) -> Vector a -> m a
+{-# INLINE fold1M' #-}
+fold1M' = G.fold1M'
+
+-- | /O(n)/ Monadic fold that discards the result
+foldM_ :: Monad m => (a -> b -> m a) -> a -> Vector b -> m ()
+{-# INLINE foldM_ #-}
+foldM_ = G.foldM_
+
+-- | /O(n)/ Monadic fold over non-empty vectors that discards the result
+fold1M_ :: Monad m => (a -> a -> m a) -> Vector a -> m ()
+{-# INLINE fold1M_ #-}
+fold1M_ = G.fold1M_
+
+-- | /O(n)/ Monadic fold with strict accumulator that discards the result
+foldM'_ :: Monad m => (a -> b -> m a) -> a -> Vector b -> m ()
+{-# INLINE foldM'_ #-}
+foldM'_ = G.foldM'_
+
+-- | /O(n)/ Monadic fold over non-empty vectors with strict accumulator
+-- that discards the result
+fold1M'_ :: Monad m => (a -> a -> m a) -> Vector a -> m ()
+{-# INLINE fold1M'_ #-}
+fold1M'_ = G.fold1M'_
+
+-- Monadic sequencing
+-- ------------------
+
+-- | Evaluate each action and collect the results
+sequence :: Monad m => Vector (m a) -> m (Vector a)
+{-# INLINE sequence #-}
+sequence = G.sequence
+
+-- | Evaluate each action and discard the results
+sequence_ :: Monad m => Vector (m a) -> m ()
+{-# INLINE sequence_ #-}
+sequence_ = G.sequence_
+
+-- 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 :: (a -> b -> a) -> a -> Vector b -> Vector a
 {-# INLINE prescanl #-}
-prescanl = IV.prescanl
+prescanl = G.prescanl
 
--- | Prefix scan with strict accumulator
+-- | /O(n)/ Prescan with strict accumulator
 prescanl' :: (a -> b -> a) -> a -> Vector b -> Vector a
 {-# INLINE prescanl' #-}
-prescanl' = IV.prescanl'
+prescanl' = G.prescanl'
 
--- | Suffix scan
+-- | /O(n)/ Scan
+--
+-- @
+-- postscanl f z = 'tail' . 'scanl' f z
+-- @
+--
+-- Example: @postscanl (+) 0 \<1,2,3,4\> = \<1,3,6,10\>@
+--
 postscanl :: (a -> b -> a) -> a -> Vector b -> Vector a
 {-# INLINE postscanl #-}
-postscanl = IV.postscanl
+postscanl = G.postscanl
 
--- | Suffix scan with strict accumulator
+-- | /O(n)/ Scan with strict accumulator
 postscanl' :: (a -> b -> a) -> a -> Vector b -> Vector a
 {-# INLINE postscanl' #-}
-postscanl' = IV.postscanl'
+postscanl' = G.postscanl'
 
--- | 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 :: (a -> b -> a) -> a -> Vector b -> Vector a
 {-# INLINE scanl #-}
-scanl = IV.scanl
+scanl = G.scanl
 
--- | Haskell-style scan with strict accumulator
+-- | /O(n)/ Haskell-style scan with strict accumulator
 scanl' :: (a -> b -> a) -> a -> Vector b -> Vector a
 {-# INLINE scanl' #-}
-scanl' = IV.scanl'
+scanl' = G.scanl'
 
--- | 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 :: (a -> a -> a) -> Vector a -> Vector a
 {-# INLINE scanl1 #-}
-scanl1 = IV.scanl1
+scanl1 = G.scanl1
 
--- | Scan over a non-empty 'Vector' with a strict accumulator
+-- | /O(n)/ Scan over a non-empty vector with a strict accumulator
 scanl1' :: (a -> a -> a) -> Vector a -> Vector a
 {-# INLINE scanl1' #-}
-scanl1' = IV.scanl1'
+scanl1' = G.scanl1'
 
--- Enumeration
--- -----------
-
-enumFromTo :: Enum a => a -> a -> Vector a
-{-# INLINE enumFromTo #-}
-enumFromTo = IV.enumFromTo
-
-enumFromThenTo :: Enum a => a -> a -> a -> Vector a
-{-# INLINE enumFromThenTo #-}
-enumFromThenTo = IV.enumFromThenTo
-
--- Conversion to/from lists
+-- | /O(n)/ Right-to-left prescan
+--
+-- @
+-- prescanr f z = 'reverse' . 'prescanl' (flip f) z . 'reverse'
+-- @
+--
+prescanr :: (a -> b -> b) -> b -> Vector a -> Vector b
+{-# INLINE prescanr #-}
+prescanr = G.prescanr
+
+-- | /O(n)/ Right-to-left prescan with strict accumulator
+prescanr' :: (a -> b -> b) -> b -> Vector a -> Vector b
+{-# INLINE prescanr' #-}
+prescanr' = G.prescanr'
+
+-- | /O(n)/ Right-to-left scan
+postscanr :: (a -> b -> b) -> b -> Vector a -> Vector b
+{-# INLINE postscanr #-}
+postscanr = G.postscanr
+
+-- | /O(n)/ Right-to-left scan with strict accumulator
+postscanr' :: (a -> b -> b) -> b -> Vector a -> Vector b
+{-# INLINE postscanr' #-}
+postscanr' = G.postscanr'
+
+-- | /O(n)/ Right-to-left Haskell-style scan
+scanr :: (a -> b -> b) -> b -> Vector a -> Vector b
+{-# INLINE scanr #-}
+scanr = G.scanr
+
+-- | /O(n)/ Right-to-left Haskell-style scan with strict accumulator
+scanr' :: (a -> b -> b) -> b -> Vector a -> Vector b
+{-# INLINE scanr' #-}
+scanr' = G.scanr'
+
+-- | /O(n)/ Right-to-left scan over a non-empty vector
+scanr1 :: (a -> a -> a) -> Vector a -> Vector a
+{-# INLINE scanr1 #-}
+scanr1 = G.scanr1
+
+-- | /O(n)/ Right-to-left scan over a non-empty vector with a strict
+-- accumulator
+scanr1' :: (a -> a -> a) -> Vector a -> Vector a
+{-# INLINE scanr1' #-}
+scanr1' = G.scanr1'
+
+-- Conversions - Lists
 -- ------------------------
 
--- | Convert a vector to a list
+-- | /O(n)/ Convert a vector to a list
 toList :: Vector a -> [a]
 {-# INLINE toList #-}
-toList = IV.toList
+toList = G.toList
 
--- | Convert a list to a vector
+-- | /O(n)/ Convert a list to a vector
 fromList :: [a] -> Vector a
 {-# INLINE fromList #-}
-fromList = IV.fromList
+fromList = G.fromList
+
+-- | /O(n)/ Convert the first @n@ elements of a list to a vector
+--
+-- @
+-- fromListN n xs = 'fromList' ('take' n xs)
+-- @
+fromListN :: Int -> [a] -> Vector a
+{-# INLINE fromListN #-}
+fromListN = G.fromListN
+
+-- 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 => MVector (PrimState m) a -> m (Vector a)
+{-# INLINE unsafeFreeze #-}
+unsafeFreeze = G.unsafeFreeze
+
+-- | /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 a -> m (MVector (PrimState m) a)
+{-# INLINE unsafeThaw #-}
+unsafeThaw = G.unsafeThaw
+
+-- | /O(n)/ Yield a mutable copy of the immutable vector.
+thaw :: PrimMonad m => Vector a -> m (MVector (PrimState m) a)
+{-# INLINE thaw #-}
+thaw = G.thaw
+
+-- | /O(n)/ Yield an immutable copy of the mutable vector.
+freeze :: PrimMonad m => MVector (PrimState m) a -> m (Vector a)
+{-# INLINE freeze #-}
+freeze = G.freeze
+
+-- | /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 => MVector (PrimState m) a -> Vector a -> m ()
+{-# INLINE unsafeCopy #-}
+unsafeCopy = G.unsafeCopy
+           
+-- | /O(n)/ Copy an immutable vector into a mutable one. The two vectors must
+-- have the same length.
+copy :: PrimMonad m => MVector (PrimState m) a -> Vector a -> m ()
+{-# INLINE copy #-}
+copy = G.copy