Docs + rearrange code
authorRoman Leshchinskiy <rl@cse.unsw.edu.au>
Tue, 27 Apr 2010 04:17:28 +0000 (04:17 +0000)
committerRoman Leshchinskiy <rl@cse.unsw.edu.au>
Tue, 27 Apr 2010 04:17:28 +0000 (04:17 +0000)
Data/Vector/Storable.hs

index b383997..4b88abe 100644 (file)
 --
 
 module Data.Vector.Storable (
+  -- * Storable vectors
   Vector, MVector(..), Storable,
 
-  -- * Length information
-  length, null,
+  -- * Accessors
 
-  -- * Construction
-  empty, singleton, cons, snoc, replicate, generate, (++), force,
+  -- ** Length information
+  length, null,
 
-  -- * Accessing individual elements
-  (!), head, last, indexM, headM, lastM,
+  -- ** Indexing
+  (!), head, last,
   unsafeIndex, unsafeHead, unsafeLast,
+
+  -- ** Monadic indexing
+  indexM, headM, lastM,
   unsafeIndexM, unsafeHeadM, unsafeLastM,
 
-  -- * Subvectors
+  -- ** Extracting subvectors (slicing)
   slice, init, tail, take, drop,
   unsafeSlice, unsafeInit, unsafeTail, unsafeTake, unsafeDrop,
 
-  -- * Permutations
-  accum, accumulate_, (//), update_, backpermute, reverse,
-  unsafeAccum, unsafeAccumulate_,
+  -- * Construction
+
+  -- ** Initialisation
+  empty, singleton, replicate, generate,
+
+  -- ** Monadic initialisation
+  replicateM, create,
+
+  -- ** Unfolding
+  unfoldr, unfoldrN,
+
+  -- ** Enumeration
+  enumFromN, enumFromStepN, enumFromTo, enumFromThenTo,
+
+  -- ** Concatenation
+  cons, snoc, (++),
+
+  -- ** Restricting memory usage
+  force,
+
+  -- * Modifying vectors
+
+  -- ** Bulk updates
+  (//), update_,
   unsafeUpd, unsafeUpdate_,
-  unsafeBackpermute,
 
-  -- * Mapping
+  -- ** Accumulations
+  accum, accumulate_,
+  unsafeAccum, unsafeAccumulate_,
+
+  -- ** Permutations 
+  reverse, backpermute, unsafeBackpermute,
+
+  -- ** Safe destructive updates
+  modify,
+
+  -- * Elementwise operations
+
+  -- ** Mapping
   map, imap, concatMap,
 
-  -- * Zipping and unzipping
+  -- ** Monadic mapping
+  mapM, mapM_, forM, forM_,
+
+  -- ** Zipping
   zipWith, zipWith3, zipWith4, zipWith5, zipWith6,
   izipWith, izipWith3, izipWith4, izipWith5, izipWith6,
 
-  -- * Filtering
-  filter, ifilter, takeWhile, dropWhile,
+  -- ** Monadic zipping
+  zipWithM, zipWithM_,
+
+  -- * Working with predicates
+
+  -- ** Filtering
+  filter, ifilter, filterM,
+  takeWhile, dropWhile,
+
+  -- ** Partitioning
   partition, unstablePartition, span, break,
 
-  -- * Searching
+  -- ** Searching
   elem, notElem, find, findIndex, findIndices, elemIndex, elemIndices,
 
   -- * Folding
   foldl, foldl1, foldl', foldl1', foldr, foldr1, foldr', foldr1',
   ifoldl, ifoldl', ifoldr, ifoldr',
 
-  -- * Specialised folds
+  -- ** Specialised folds
   all, any, and, or,
   sum, product,
   maximum, maximumBy, minimum, minimumBy,
   minIndex, minIndexBy, maxIndex, maxIndexBy,
 
-  -- * Unfolding
-  unfoldr, unfoldrN,
+  -- ** Monadic folds
+  foldM, foldM', fold1M, fold1M',
 
-  -- * Scans
+  -- * Prefix sums (scans)
   prescanl, prescanl',
   postscanl, postscanl',
   scanl, scanl', scanl1, scanl1',
@@ -71,20 +117,15 @@ module Data.Vector.Storable (
   postscanr, postscanr',
   scanr, scanr', scanr1, scanr1',
 
-  -- * Enumeration
-  enumFromN, enumFromStepN, enumFromTo, enumFromThenTo,
+  -- * Conversions
 
-  -- * Conversion to/from lists
+  -- ** Lists
   toList, fromList, fromListN,
 
-  -- * Monadic operations
-  replicateM, mapM, mapM_, forM, forM_, zipWithM, zipWithM_, filterM,
-  foldM, foldM', fold1M, fold1M',
-
-  -- * Destructive operations
-  create, modify, copy, unsafeCopy,
+  -- ** Mutable vectors
+  copy, unsafeCopy,
 
-  -- * Accessing the underlying memory
+  -- * Raw pointers
   unsafeFromForeignPtr, unsafeToForeignPtr, unsafeWith
 ) where
 
@@ -219,248 +260,475 @@ foreign import ccall unsafe "string.h memcmp" memcmp
 -- Length
 -- ------
 
+-- | /O(1)/ Yield the length of the vector.
 length :: Storable a => Vector a -> Int
 {-# INLINE length #-}
 length = G.length
 
+-- | /O(1)/ Test whether a vector if empty
 null :: Storable a => Vector a -> Bool
 {-# INLINE null #-}
 null = G.null
 
--- Construction
--- ------------
-
--- | Empty vector
-empty :: Storable a => Vector a
-{-# INLINE empty #-}
-empty = G.empty
-
--- | Vector with exaclty one element
-singleton :: Storable a => a -> Vector a
-{-# INLINE singleton #-}
-singleton = G.singleton
-
--- | Vector of the given length with the given value in each position
-replicate :: Storable a => Int -> a -> Vector a
-{-# INLINE replicate #-}
-replicate = G.replicate
-
--- | Generate a vector of the given length by applying the function to each
--- index
-generate :: Storable a => Int -> (Int -> a) -> Vector a
-{-# INLINE generate #-}
-generate = G.generate
-
--- | Prepend an element
-cons :: Storable a => a -> Vector a -> Vector a
-{-# INLINE cons #-}
-cons = G.cons
-
--- | Append an element
-snoc :: Storable a => Vector a -> a -> Vector a
-{-# INLINE snoc #-}
-snoc = G.snoc
+-- Indexing
+-- --------
 
-infixr 5 ++
--- | Concatenate two vectors
-(++) :: Storable a => Vector a -> Vector a -> Vector a
-{-# INLINE (++) #-}
-(++) = (G.++)
-
--- | Create a copy of a vector. Useful when dealing with slices.
-force :: Storable a => Vector a -> Vector a
-{-# INLINE force #-}
-force = G.force
-
--- Accessing individual elements
--- -----------------------------
-
--- | Indexing
+-- | O(1) Indexing
 (!) :: Storable a => Vector a -> Int -> a
 {-# INLINE (!) #-}
 (!) = (G.!)
 
--- | First element
+-- | /O(1)/ First element
 head :: Storable a => Vector a -> a
 {-# INLINE head #-}
 head = G.head
 
--- | Last element
+-- | /O(1)/ Last element
 last :: Storable a => Vector a -> a
 {-# INLINE last #-}
 last = G.last
 
--- | Unsafe indexing without bounds checking
+-- | /O(1)/ Unsafe indexing without bounds checking
 unsafeIndex :: Storable a => Vector a -> Int -> a
 {-# INLINE unsafeIndex #-}
 unsafeIndex = G.unsafeIndex
 
--- | Yield the first element of a vector without checking if the vector is
--- empty
+-- | /O(1)/ First element without checking if the vector is empty
 unsafeHead :: Storable a => Vector a -> a
 {-# INLINE unsafeHead #-}
 unsafeHead = G.unsafeHead
 
--- | Yield the last element of a vector without checking if the vector is
--- empty
+-- | /O(1)/ Last element without checking if the vector is empty
 unsafeLast :: Storable a => Vector a -> a
 {-# INLINE unsafeLast #-}
 unsafeLast = G.unsafeLast
 
--- | Monadic indexing which can be strict in the vector while remaining lazy in
--- the element
+-- Monadic indexing
+-- ----------------
+
+-- | /O(1)/ Indexing in a monad.
+--
+-- The monad allows operations to be strict in the vector when necessary.
+-- Suppose vector copying is implemented like this:
+--
+-- > copy mv v = ... write mv i (v ! i) ...
+--
+-- For lazy vectors, @v ! i@ would not be evaluated which means that @mv@
+-- would unnecessarily retain a reference to @v@ in each element written.
+--
+-- With 'indexM', copying can be implemented like this instead:
+--
+-- > copy mv v = ... do
+-- >                   x <- indexM v i
+-- >                   write mv i x
+--
+-- Here, no references to @v@ are retained because indexing (but /not/ the
+-- elements) is evaluated eagerly.
+--
 indexM :: (Storable a, Monad m) => Vector a -> Int -> m a
 {-# INLINE 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 :: (Storable a, Monad m) => Vector a -> m a
 {-# INLINE 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 :: (Storable a, Monad m) => Vector a -> m a
 {-# INLINE lastM #-}
 lastM = G.lastM
 
--- | Unsafe monadic indexing without bounds checks
+-- | /O(1)/ Indexing in a monad without bounds checks. See 'indexM' for an
+-- explanation of why this is useful.
 unsafeIndexM :: (Storable a, 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 :: (Storable a, 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 :: (Storable a, Monad m) => Vector a -> m a
 {-# INLINE unsafeLastM #-}
 unsafeLastM = G.unsafeLastM
 
--- Subarrays
--- ---------
+-- Extracting subvectors (slicing)
+-- -------------------------------
 
--- | Yield a part of the vector without copying it. Safer version of
--- 'basicUnsafeSlice'.
-slice :: Storable a => Int   -- ^ starting index
-                    -> Int   -- ^ length
-                    -> Vector a
-                    -> Vector a
+-- | /O(1)/ Yield a slice of the vector without copying it. The vector must
+-- contain at least @i+n@ elements.
+slice :: Storable a
+      => Int   -- ^ @i@ starting index
+      -> Int   -- ^ @n@ length
+      -> Vector a
+      -> Vector a
 {-# INLINE 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 :: Storable a => Vector a -> Vector a
 {-# INLINE 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 :: Storable a => Vector a -> Vector a
 {-# INLINE 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 :: Storable a => Int -> Vector a -> Vector a
 {-# INLINE 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 :: Storable a => Int -> Vector a -> Vector a
 {-# INLINE drop #-}
 drop = G.drop
 
--- | Unsafely yield a part of the vector without copying it and without
--- performing bounds checks.
-unsafeSlice :: Storable a => Int   -- ^ starting index
-                          -> Int   -- ^ length
-                          -> Vector a
-                          -> Vector a
+-- | /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 :: Storable a => 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 :: Storable a => 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 :: Storable a => 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 :: Storable a => 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 :: Storable a => Int -> Vector a -> Vector a
 {-# INLINE unsafeDrop #-}
 unsafeDrop = G.unsafeDrop
 
--- Permutations
--- ------------
+-- Initialisation
+-- --------------
 
-unsafeAccum :: Storable a => (a -> b -> a) -> Vector a -> [(Int,b)] -> Vector a
-{-# INLINE unsafeAccum #-}
-unsafeAccum = G.unsafeAccum
+-- | /O(1)/ Empty vector
+empty :: Storable a => Vector a
+{-# INLINE empty #-}
+empty = G.empty
 
-unsafeAccumulate_ :: (Storable a, Storable b) =>
-               (a -> b -> a) -> Vector a -> Vector Int -> Vector b -> Vector a
-{-# INLINE unsafeAccumulate_ #-}
-unsafeAccumulate_ = G.unsafeAccumulate_
+-- | /O(1)/ Vector with exactly one element
+singleton :: Storable a => a -> Vector a
+{-# INLINE singleton #-}
+singleton = G.singleton
 
-accum :: Storable a => (a -> b -> a) -> Vector a -> [(Int,b)] -> Vector a
-{-# INLINE accum #-}
-accum = G.accum
+-- | /O(n)/ Vector of the given length with the same value in each position
+replicate :: Storable a => Int -> a -> Vector a
+{-# INLINE replicate #-}
+replicate = G.replicate
 
-accumulate_ :: (Storable a, Storable b) =>
-               (a -> b -> a) -> Vector a -> Vector Int -> Vector b -> Vector a
-{-# INLINE accumulate_ #-}
-accumulate_ = G.accumulate_
+-- | /O(n)/ Construct a vector of the given length by applying the function to
+-- each index
+generate :: Storable a => Int -> (Int -> a) -> Vector a
+{-# INLINE generate #-}
+generate = G.generate
+
+-- 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 :: Storable a => (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 :: Storable a => Int -> (b -> Maybe (a, b)) -> b -> Vector a
+{-# INLINE unfoldrN #-}
+unfoldrN = G.unfoldrN
+
+-- 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 :: (Storable a, 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 :: (Storable a, 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 :: (Storable a, 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 :: (Storable a, Enum a) => a -> a -> a -> Vector a
+{-# INLINE enumFromThenTo #-}
+enumFromThenTo = G.enumFromThenTo
+
+-- Concatenation
+-- -------------
+
+-- | /O(n)/ Prepend an element
+cons :: Storable a => a -> Vector a -> Vector a
+{-# INLINE cons #-}
+cons = G.cons
 
+-- | /O(n)/ Append an element
+snoc :: Storable a => Vector a -> a -> Vector a
+{-# INLINE snoc #-}
+snoc = G.snoc
+
+infixr 5 ++
+-- | /O(m+n)/ Concatenate two vectors
+(++) :: Storable a => Vector a -> Vector a -> Vector a
+{-# INLINE (++) #-}
+(++) = (G.++)
+
+-- Monadic initialisation
+-- ----------------------
+
+-- | /O(n)/ Execute the monadic action the given number of times and store the
+-- results in a vector.
+replicateM :: (Monad m, Storable a) => Int -> m a -> m (Vector a)
+{-# INLINE replicateM #-}
+replicateM = G.replicateM
+
+-- | 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 :: Storable a => (forall s. ST s (MVector s a)) -> Vector a
+{-# INLINE create #-}
+create = G.create
+
+-- 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 :: Storable a => 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>
+--
+(//) :: Storable a => Vector a   -- ^ initial vector (of length @m@)
+                -> [(Int, a)] -- ^ list of index/value pairs (of length @n@) 
+                -> Vector a
+{-# INLINE (//) #-}
+(//) = (G.//)
+
+-- | /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>
+--
+update_ :: Storable a
+        => 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 :: Storable a => Vector a -> [(Int, a)] -> Vector a
 {-# INLINE unsafeUpd #-}
 unsafeUpd = G.unsafeUpd
 
+-- | Same as 'update_' but without bounds checking.
 unsafeUpdate_ :: Storable a => Vector a -> Vector Int -> Vector a -> Vector a
 {-# INLINE unsafeUpdate_ #-}
 unsafeUpdate_ = G.unsafeUpdate_
 
-(//) :: Storable a => Vector a -> [(Int, a)] -> Vector a
-{-# INLINE (//) #-}
-(//) = (G.//)
+-- Accumulations
+-- -------------
 
-update_ :: Storable a => Vector a -> Vector Int -> Vector a -> Vector a
-{-# INLINE update_ #-}
-update_ = G.update_
+-- | /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 :: Storable a
+      => (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+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>
+--
+accumulate_ :: (Storable a, Storable b)
+            => (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 :: Storable a => (a -> b -> a) -> Vector a -> [(Int,b)] -> Vector a
+{-# INLINE unsafeAccum #-}
+unsafeAccum = G.unsafeAccum
+
+-- | Same as 'accumulate_' but without bounds checking.
+unsafeAccumulate_ :: (Storable a, Storable b) =>
+               (a -> b -> a) -> Vector a -> Vector Int -> Vector b -> Vector a
+{-# INLINE unsafeAccumulate_ #-}
+unsafeAccumulate_ = G.unsafeAccumulate_
+
+-- Permutations
+-- ------------
+
+-- | /O(n)/ Reverse a vector
+reverse :: Storable a => Vector a -> Vector a
+{-# INLINE 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 :: Storable a => Vector a -> Vector Int -> Vector a
 {-# INLINE backpermute #-}
 backpermute = G.backpermute
 
+-- | Same as 'backpermute' but without bounds checking.
 unsafeBackpermute :: Storable a => Vector a -> Vector Int -> Vector a
 {-# INLINE unsafeBackpermute #-}
 unsafeBackpermute = G.unsafeBackpermute
 
-reverse :: Storable a => Vector a -> Vector a
-{-# INLINE reverse #-}
-reverse = G.reverse
+-- 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 :: Storable a => (forall s. MVector s a -> ST s ()) -> Vector a -> Vector a
+{-# INLINE modify #-}
+modify = G.modify
 
 -- Mapping
 -- -------
 
--- | Map a function over a vector
+-- | /O(n)/ Map a function over a vector
 map :: (Storable a, Storable b) => (a -> b) -> Vector a -> Vector b
 {-# INLINE map #-}
 map = G.map
 
--- | Apply a function to every index/value pair
+-- | /O(n)/ Apply a function to every element of a vector and its index
 imap :: (Storable a, Storable b) => (Int -> a -> b) -> Vector a -> Vector b
 {-# INLINE imap #-}
 imap = G.imap
 
+-- | Map a function over a vector and concatenate the results.
 concatMap :: (Storable a, Storable b) => (a -> Vector b) -> Vector a -> Vector b
 {-# INLINE concatMap #-}
 concatMap = G.concatMap
 
--- Zipping/unzipping
--- -----------------
+-- Monadic mapping
+-- ---------------
+
+-- | /O(n)/ Apply the monadic action to all elements of the vector, yielding a
+-- vector of results
+mapM :: (Monad m, Storable a, Storable b) => (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, Storable a) => (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, Storable a, Storable b) => 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, Storable a) => 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 :: (Storable a, Storable b, Storable c)
         => (a -> b -> c) -> Vector a -> Vector b -> Vector c
 {-# INLINE zipWith #-}
@@ -494,7 +762,8 @@ zipWith6 :: (Storable a, Storable b, Storable c, Storable d, Storable e,
 {-# INLINE zipWith6 #-}
 zipWith6 = G.zipWith6
 
--- | Zip two vectors and their indices with the given function.
+-- | /O(min(m,n))/ Zip two vectors with a function that also takes the
+-- elements' indices.
 izipWith :: (Storable a, Storable b, Storable c)
          => (Int -> a -> b -> c) -> Vector a -> Vector b -> Vector c
 {-# INLINE izipWith #-}
@@ -529,54 +798,81 @@ izipWith6 :: (Storable a, Storable b, Storable c, Storable d, Storable e,
 {-# INLINE izipWith6 #-}
 izipWith6 = G.izipWith6
 
+-- Monadic zipping
+-- ---------------
+
+-- | /O(min(m,n))/ Zip the two vectors with the monadic action and yield a
+-- vector of results
+zipWithM :: (Monad m, Storable a, Storable b, Storable c)
+         => (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, Storable a, Storable b)
+          => (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 :: Storable a => (a -> Bool) -> Vector a -> Vector a
 {-# INLINE filter #-}
 filter = G.filter
 
--- | Drop elements that do not satisfy the predicate (applied to values and
--- their indices)
+-- | /O(n)/ Drop elements that do not satisfy the predicate which is applied to
+-- values and their indices
 ifilter :: Storable a => (Int -> a -> Bool) -> Vector a -> Vector a
 {-# INLINE ifilter #-}
 ifilter = G.ifilter
 
--- | Yield the longest prefix of elements satisfying the predicate.
+-- | /O(n)/ Drop elements that do not satisfy the monadic predicate
+filterM :: (Monad m, Storable a) => (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 :: Storable a => (a -> Bool) -> Vector a -> Vector a
 {-# INLINE 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 :: Storable a => (a -> Bool) -> Vector a -> Vector a
 {-# INLINE dropWhile #-}
 dropWhile = G.dropWhile
 
--- | 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)
+-- 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 :: Storable a => (a -> Bool) -> Vector a -> (Vector a, Vector a)
 {-# INLINE partition #-}
 partition = G.partition
 
--- | 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.
-unstablePartition
-        :: Storable a => (a -> Bool) -> Vector a -> (Vector a, Vector a)
+-- | /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 :: Storable a => (a -> Bool) -> Vector a -> (Vector a, Vector a)
 {-# INLINE unstablePartition #-}
 unstablePartition = G.unstablePartition
 
--- | Split the vector into the longest prefix of elements that satisfy the
--- predicate and the rest.
+-- | /O(n)/ Split the vector into the longest prefix of elements that satisfy
+-- the predicate and the rest without copying.
 span :: Storable a => (a -> Bool) -> Vector a -> (Vector a, Vector a)
 {-# INLINE span #-}
 span = G.span
 
--- | Split the vector into the longest prefix of elements that do not satisfy
--- the predicate and the rest.
+-- | /O(n)/ Split the vector into the longest prefix of elements that do not
+-- satisfy the predicate and the rest without copying.
 break :: Storable a => (a -> Bool) -> Vector a -> (Vector a, Vector a)
 {-# INLINE break #-}
 break = G.break
@@ -585,41 +881,44 @@ break = G.break
 -- ---------
 
 infix 4 `elem`
--- | Check whether the vector contains an element
+-- | /O(n)/ Check if the vector contains an element
 elem :: (Storable a, Eq a) => a -> Vector a -> Bool
 {-# INLINE 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 :: (Storable a, Eq a) => a -> Vector a -> Bool
 {-# INLINE 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 :: Storable a => (a -> Bool) -> Vector a -> Maybe a
 {-# INLINE 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 :: Storable a => (a -> Bool) -> Vector a -> Maybe Int
 {-# INLINE findIndex #-}
 findIndex = G.findIndex
 
--- | Yield the indices of elements satisfying the predicate
+-- | /O(n)/ Yield the indices of elements satisfying the predicate in ascending
+-- order.
 findIndices :: Storable a => (a -> Bool) -> Vector a -> Vector Int
 {-# INLINE findIndices #-}
 findIndices = G.findIndices
 
--- | Yield 'Just' the index of the first occurence of the given element or
--- 'Nothing' if the vector does not contain the element
+-- | /O(n)/ Yield 'Just' the index of the first occurence of the given element or
+-- 'Nothing' if the vector does not contain the element. This is a specialised
+-- version of 'findIndex'.
 elemIndex :: (Storable a, Eq a) => a -> Vector a -> Maybe Int
 {-# INLINE elemIndex #-}
 elemIndex = G.elemIndex
 
--- | Yield the indices of all occurences of the given element
+-- | /O(n)/ Yield the indices of all occurences of the given element in
+-- ascending order. This is a specialised version of 'findIndices'.
 elemIndices :: (Storable a, Eq a) => a -> Vector a -> Vector Int
 {-# INLINE elemIndices #-}
 elemIndices = G.elemIndices
@@ -627,64 +926,64 @@ elemIndices = G.elemIndices
 -- Folding
 -- -------
 
--- | Left fold
+-- | /O(n)/ Left fold
 foldl :: Storable b => (a -> b -> a) -> a -> Vector b -> a
 {-# INLINE foldl #-}
 foldl = G.foldl
 
--- | Lefgt fold on non-empty vectors
+-- | /O(n)/ Left fold on non-empty vectors
 foldl1 :: Storable a => (a -> a -> a) -> Vector a -> a
 {-# INLINE foldl1 #-}
 foldl1 = G.foldl1
 
--- | Left fold with strict accumulator
+-- | /O(n)/ Left fold with strict accumulator
 foldl' :: Storable b => (a -> b -> a) -> a -> Vector b -> a
 {-# INLINE 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' :: Storable a => (a -> a -> a) -> Vector a -> a
 {-# INLINE foldl1' #-}
 foldl1' = G.foldl1'
 
--- | Right fold
+-- | /O(n)/ Right fold
 foldr :: Storable a => (a -> b -> b) -> b -> Vector a -> b
 {-# INLINE foldr #-}
 foldr = G.foldr
 
--- | Right fold on non-empty vectors
+-- | /O(n)/ Right fold on non-empty vectors
 foldr1 :: Storable a => (a -> a -> a) -> Vector a -> a
 {-# INLINE foldr1 #-}
 foldr1 = G.foldr1
 
--- | Right fold with a strict accumulator
+-- | /O(n)/ Right fold with a strict accumulator
 foldr' :: Storable a => (a -> b -> b) -> b -> Vector a -> b
 {-# INLINE foldr' #-}
 foldr' = G.foldr'
 
--- | Right fold on non-empty vectors with strict accumulator
+-- | /O(n)/ Right fold on non-empty vectors with strict accumulator
 foldr1' :: Storable a => (a -> a -> a) -> Vector a -> a
 {-# INLINE foldr1' #-}
 foldr1' = G.foldr1'
 
--- | Left fold (function applied to each element and its index)
+-- | /O(n)/ Left fold (function applied to each element and its index)
 ifoldl :: Storable b => (a -> Int -> b -> a) -> a -> Vector b -> a
 {-# INLINE ifoldl #-}
 ifoldl = G.ifoldl
 
--- | Left fold with strict accumulator (function applied to each element and
--- its index)
+-- | /O(n)/ Left fold with strict accumulator (function applied to each element
+-- and its index)
 ifoldl' :: Storable b => (a -> Int -> b -> a) -> a -> Vector b -> a
 {-# INLINE ifoldl' #-}
 ifoldl' = G.ifoldl'
 
--- | Right fold (function applied to each element and its index)
+-- | /O(n)/ Right fold (function applied to each element and its index)
 ifoldr :: Storable a => (Int -> a -> b -> b) -> b -> Vector a -> b
 {-# INLINE ifoldr #-}
 ifoldr = G.ifoldr
 
--- | Right fold with strict accumulator (function applied to each element and
--- its index)
+-- | /O(n)/ Right fold with strict accumulator (function applied to each
+-- element and its index)
 ifoldr' :: Storable a => (Int -> a -> b -> b) -> b -> Vector a -> b
 {-# INLINE ifoldr' #-}
 ifoldr' = G.ifoldr'
@@ -692,329 +991,265 @@ ifoldr' = G.ifoldr'
 -- Specialised folds
 -- -----------------
 
+-- | /O(n)/ Check if all elements satisfy the predicate.
 all :: Storable a => (a -> Bool) -> Vector a -> Bool
 {-# INLINE all #-}
 all = G.all
 
+-- | /O(n)/ Check if any element satisfies the predicate.
 any :: Storable a => (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 = G.and
 
+-- | /O(n)/ Check if any element is 'True'
 or :: Vector Bool -> Bool
 {-# INLINE or #-}
 or = G.or
 
+-- | /O(n)/ Compute the sum of the elements
 sum :: (Storable a, Num a) => Vector a -> a
 {-# INLINE sum #-}
 sum = G.sum
 
+-- | /O(n)/ Compute the produce of the elements
 product :: (Storable a, Num a) => Vector a -> a
 {-# INLINE product #-}
 product = G.product
 
+-- | /O(n)/ Yield the maximum element of the vector. The vector may not be
+-- empty.
 maximum :: (Storable a, Ord a) => Vector a -> a
 {-# INLINE 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 :: Storable a => (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 :: (Storable a, Ord a) => Vector a -> a
 {-# INLINE minimum #-}
 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 :: Storable a => (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 :: (Storable a, 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 :: Storable a => (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 :: (Storable a, 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 :: Storable a => (a -> a -> Ordering) -> Vector a -> Int
 {-# INLINE minIndexBy #-}
 minIndexBy = G.minIndexBy
 
--- Unfolding
--- ---------
+-- Monadic folds
+-- -------------
 
--- | The 'unfoldr' function is a \`dual\' to 'foldr': while 'foldr'
--- reduces a vector to a summary value, 'unfoldr' builds a list from
--- a seed value.  The function takes the element and returns 'Nothing'
--- if it is done generating the vector or returns 'Just' @(a,b)@, in which
--- case, @a@ is a prepended to the vector and @b@ is used as the next
--- element in a recursive call.
---
--- A simple use of unfoldr:
---
--- > unfoldr (\b -> if b == 0 then Nothing else Just (b, b-1)) 10
--- >  [10,9,8,7,6,5,4,3,2,1]
---
-unfoldr :: Storable a => (b -> Maybe (a, b)) -> b -> Vector a
-{-# INLINE unfoldr #-}
-unfoldr = G.unfoldr
+-- | /O(n)/ Monadic fold
+foldM :: (Monad m, Storable b) => (a -> b -> m a) -> a -> Vector b -> m a
+{-# INLINE foldM #-}
+foldM = G.foldM
 
--- | Unfold at most @n@ elements
-unfoldrN :: Storable a => Int -> (b -> Maybe (a, b)) -> b -> Vector a
-{-# INLINE unfoldrN #-}
-unfoldrN = G.unfoldrN
+-- | /O(n)/ Monadic fold over non-empty vectors
+fold1M :: (Monad m, Storable a) => (a -> a -> m a) -> Vector a -> m a
+{-# INLINE fold1M #-}
+fold1M = G.fold1M
+
+-- | /O(n)/ Monadic fold with strict accumulator
+foldM' :: (Monad m, Storable b) => (a -> b -> m a) -> a -> Vector b -> m a
+{-# INLINE foldM' #-}
+foldM' = G.foldM'
+
+-- | /O(n)/ Monad fold over non-empty vectors with strict accumulator
+fold1M' :: (Monad m, Storable a) => (a -> a -> m a) -> Vector a -> m a
+{-# INLINE fold1M' #-}
+fold1M' = G.fold1M'
 
--- Scans
--- -----
+-- Prefix sums (scans)
+-- -------------------
 
--- | Prefix scan
+-- | /O(n)/ Prescan
+--
+-- @
+-- prescanl f z = 'init' . 'scanl' f z
+-- @
+--
+-- Example: @prescanl (+) 0 \<1,2,3,4\> = \<0,1,3,6\>@
+--
 prescanl :: (Storable a, Storable b) => (a -> b -> a) -> a -> Vector b -> Vector a
 {-# INLINE prescanl #-}
 prescanl = G.prescanl
 
--- | Prefix scan with strict accumulator
+-- | /O(n)/ Prescan with strict accumulator
 prescanl' :: (Storable a, Storable b) => (a -> b -> a) -> a -> Vector b -> Vector a
 {-# INLINE 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 :: (Storable a, Storable b) => (a -> b -> a) -> a -> Vector b -> Vector a
 {-# INLINE postscanl #-}
 postscanl = G.postscanl
 
--- | Suffix scan with strict accumulator
+-- | /O(n)/ Scan with strict accumulator
 postscanl' :: (Storable a, Storable b) => (a -> b -> a) -> a -> Vector b -> Vector a
 {-# INLINE 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 :: (Storable a, Storable b) => (a -> b -> a) -> a -> Vector b -> Vector a
 {-# INLINE scanl #-}
 scanl = G.scanl
 
--- | Haskell-style scan with strict accumulator
+-- | /O(n)/ Haskell-style scan with strict accumulator
 scanl' :: (Storable a, Storable b) => (a -> b -> a) -> a -> Vector b -> Vector a
 {-# INLINE 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 :: Storable a => (a -> a -> a) -> Vector a -> Vector a
 {-# INLINE 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' :: Storable a => (a -> a -> a) -> Vector a -> Vector a
 {-# INLINE scanl1' #-}
 scanl1' = G.scanl1'
 
-
--- | Prefix right-to-left scan
-prescanr
-  :: (Storable a, Storable b) => (a -> b -> b) -> b -> Vector a -> Vector b
+-- | /O(n)/ Right-to-left prescan
+--
+-- @
+-- prescanr f z = 'reverse' . 'prescanl' (flip f) z . 'reverse'
+-- @
+--
+prescanr :: (Storable a, Storable b) => (a -> b -> b) -> b -> Vector a -> Vector b
 {-# INLINE prescanr #-}
 prescanr = G.prescanr
 
--- | Prefix right-to-left scan with strict accumulator
-prescanr'
-  :: (Storable a, Storable b) => (a -> b -> b) -> b -> Vector a -> Vector b
+-- | /O(n)/ Right-to-left prescan with strict accumulator
+prescanr' :: (Storable a, Storable b) => (a -> b -> b) -> b -> Vector a -> Vector b
 {-# INLINE prescanr' #-}
 prescanr' = G.prescanr'
 
--- | Suffix right-to-left scan
-postscanr
-  :: (Storable a, Storable b) => (a -> b -> b) -> b -> Vector a -> Vector b
+-- | /O(n)/ Right-to-left scan
+postscanr :: (Storable a, Storable b) => (a -> b -> b) -> b -> Vector a -> Vector b
 {-# INLINE postscanr #-}
 postscanr = G.postscanr
 
--- | Suffix right-to-left scan with strict accumulator
-postscanr'
-  :: (Storable a, Storable b) => (a -> b -> b) -> b -> Vector a -> Vector b
+-- | /O(n)/ Right-to-left scan with strict accumulator
+postscanr' :: (Storable a, Storable b) => (a -> b -> b) -> b -> Vector a -> Vector b
 {-# INLINE postscanr' #-}
 postscanr' = G.postscanr'
 
--- | Haskell-style right-to-left scan
+-- | /O(n)/ Right-to-left Haskell-style scan
 scanr :: (Storable a, Storable b) => (a -> b -> b) -> b -> Vector a -> Vector b
 {-# INLINE scanr #-}
 scanr = G.scanr
 
--- | Haskell-style right-to-left scan with strict accumulator
+-- | /O(n)/ Right-to-left Haskell-style scan with strict accumulator
 scanr' :: (Storable a, Storable b) => (a -> b -> b) -> b -> Vector a -> Vector b
 {-# INLINE scanr' #-}
 scanr' = G.scanr'
 
--- | Right-to-left scan over a non-empty vector
+-- | /O(n)/ Right-to-left scan over a non-empty vector
 scanr1 :: Storable a => (a -> a -> a) -> Vector a -> Vector a
 {-# INLINE scanr1 #-}
 scanr1 = G.scanr1
 
--- | Right-to-left scan over a non-empty vector with a strict accumulator
+-- | /O(n)/ Right-to-left scan over a non-empty vector with a strict
+-- accumulator
 scanr1' :: Storable a => (a -> a -> a) -> Vector a -> Vector a
 {-# INLINE scanr1' #-}
 scanr1' = G.scanr1'
 
--- Enumeration
--- -----------
-
--- | Yield a vector of the given length containing the values @x@, @x+1@ etc.
--- This operation is usually more efficient than 'enumFromTo'.
-enumFromN :: (Storable a, Num a) => a -> Int -> Vector a
-{-# INLINE enumFromN #-}
-enumFromN = G.enumFromN
-
--- | 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 :: (Storable a, Num a) => a -> a -> Int -> Vector a
-{-# INLINE enumFromStepN #-}
-enumFromStepN = G.enumFromStepN
-
--- | Enumerate values from @x@ to @y@.
---
--- /WARNING:/ This operation can be very inefficient. If at all possible, use
--- 'enumFromN' instead.
-enumFromTo :: (Storable a, Enum a) => a -> a -> Vector a
-{-# INLINE enumFromTo #-}
-enumFromTo = G.enumFromTo
-
--- | 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 :: (Storable a, Enum a) => a -> a -> a -> Vector a
-{-# INLINE enumFromThenTo #-}
-enumFromThenTo = G.enumFromThenTo
-
--- Conversion to/from lists
+-- Conversions - Lists
 -- ------------------------
 
--- | Convert a vector to a list
+-- | /O(n)/ Convert a vector to a list
 toList :: Storable a => Vector a -> [a]
 {-# INLINE toList #-}
 toList = G.toList
 
--- | Convert a list to a vector
+-- | /O(n)/ Convert a list to a vector
 fromList :: Storable a => [a] -> Vector a
 {-# INLINE fromList #-}
 fromList = G.fromList
 
--- | Convert the first @n@ elements of a list to a vector
+-- | /O(n)/ Convert the first @n@ elements of a list to a vector
 --
--- > fromListN n xs = fromList (take n xs)
+-- @
+-- fromListN n xs = 'fromList' ('take' n xs)
+-- @
 fromListN :: Storable a => Int -> [a] -> Vector a
 {-# INLINE fromListN #-}
 fromListN = G.fromListN
 
--- Monadic operations
--- ------------------
-
--- | Perform the monadic action the given number of times and store the
--- results in a vector.
-replicateM :: (Monad m, Storable a) => Int -> m a -> m (Vector a)
-{-# INLINE replicateM #-}
-replicateM = G.replicateM
-
--- | Apply the monadic action to all elements of the vector, yielding a vector
--- of results
-mapM :: (Monad m, Storable a, Storable b) => (a -> m b) -> Vector a -> m (Vector b)
-{-# INLINE mapM #-}
-mapM = G.mapM
-
--- | Apply the monadic action to all elements of a vector and ignore the
--- results
-mapM_ :: (Monad m, Storable a) => (a -> m b) -> Vector a -> m ()
-{-# INLINE mapM_ #-}
-mapM_ = G.mapM_
-
--- | Apply the monadic action to all elements of the vector, yielding a vector
--- of results
-forM :: (Monad m, Storable a, Storable b) => Vector a -> (a -> m b) -> m (Vector b)
-{-# INLINE forM #-}
-forM = G.forM
-
--- | Apply the monadic action to all elements of a vector and ignore the
--- results
-forM_ :: (Monad m, Storable a) => Vector a -> (a -> m b) -> m ()
-{-# INLINE forM_ #-}
-forM_ = G.forM_
-
--- | Zip the two vectors with the monadic action and yield a vector of results
-zipWithM :: (Monad m, Storable a, Storable b, Storable c)
-         => (a -> b -> m c) -> Vector a -> Vector b -> m (Vector c)
-{-# INLINE zipWithM #-}
-zipWithM = G.zipWithM
-
--- | Zip the two vectors with the monadic action and ignore the results
-zipWithM_ :: (Monad m, Storable a, Storable b)
-          => (a -> b -> m c) -> Vector a -> Vector b -> m ()
-{-# INLINE zipWithM_ #-}
-zipWithM_ = G.zipWithM_
-
--- | Drop elements that do not satisfy the monadic predicate
-filterM :: (Monad m, Storable a) => (a -> m Bool) -> Vector a -> m (Vector a)
-{-# INLINE filterM #-}
-filterM = G.filterM
-
--- | Monadic fold
-foldM :: (Monad m, Storable b) => (a -> b -> m a) -> a -> Vector b -> m a
-{-# INLINE foldM #-}
-foldM = G.foldM
-
--- | Monadic fold over non-empty vectors
-fold1M :: (Monad m, Storable a) => (a -> a -> m a) -> Vector a -> m a
-{-# INLINE fold1M #-}
-fold1M = G.fold1M
-
--- | Monadic fold with strict accumulator
-foldM' :: (Monad m, Storable b) => (a -> b -> m a) -> a -> Vector b -> m a
-{-# INLINE foldM' #-}
-foldM' = G.foldM'
-
--- | Monad fold over non-empty vectors with strict accumulator
-fold1M' :: (Monad m, Storable a) => (a -> a -> m a) -> Vector a -> m a
-{-# INLINE fold1M' #-}
-fold1M' = G.fold1M'
-
--- Destructive operations
--- ----------------------
-
--- | Destructively initialise a vector.
-create :: Storable a => (forall s. ST s (MVector s a)) -> Vector a
-{-# INLINE create #-}
-create = G.create
-
--- | Apply a destructive operation to a vector. The operation is applied to a
--- copy of the vector unless it can be safely performed in place.
-modify
-  :: Storable a => (forall s. MVector s a -> ST s ()) -> Vector a -> Vector a
-{-# INLINE modify #-}
-modify = G.modify
+-- Conversions - Mutable vectors
+-- -----------------------------
 
--- | Copy an immutable vector into a mutable one. The two vectors must have
--- the same length. This is not checked.
+-- | /O(n)/ Copy an immutable vector into a mutable one. The two vectors must
+-- have the same length.
 unsafeCopy
   :: (Storable a, PrimMonad m) => MVector (PrimState m) a -> Vector a -> m ()
 {-# INLINE unsafeCopy #-}
 unsafeCopy = G.unsafeCopy
            
--- | Copy an immutable vector into a mutable one. The two vectors must have the
--- same length.
+-- | /O(n)/ Copy an immutable vector into a mutable one. The two vectors must
+-- have the same length. This is not checked.
 copy :: (Storable a, PrimMonad m) => MVector (PrimState m) a -> Vector a -> m ()
 {-# INLINE copy #-}
 copy = G.copy
 
--- Accessing the underlying memory
--- -------------------------------
+-- Conversions - Raw pointers
+-- --------------------------
 
--- | Create a vector from a 'ForeignPtr' with an offset and a length. The data
--- may not be modified through the 'ForeignPtr' afterwards.
+-- | /O(1)/ Create a vector from a 'ForeignPtr' with an offset and a length.
+-- The data may not be modified through the 'ForeignPtr' afterwards.
 unsafeFromForeignPtr :: Storable a
                      => ForeignPtr a    -- ^ pointer
                      -> Int             -- ^ offset
@@ -1023,8 +1258,8 @@ unsafeFromForeignPtr :: Storable a
 {-# INLINE unsafeFromForeignPtr #-}
 unsafeFromForeignPtr fp i n = Vector (offsetToPtr fp i) n fp
 
--- | Yield the underlying 'ForeignPtr' together with the offset to the data
--- and its length. The data may not be modified through the 'ForeignPtr'.
+-- | /O(1)/ Yield the underlying 'ForeignPtr' together with the offset to the
+-- data and its length. The data may not be modified through the 'ForeignPtr'.
 unsafeToForeignPtr :: Storable a => Vector a -> (ForeignPtr a, Int, Int)
 {-# INLINE unsafeToForeignPtr #-}
 unsafeToForeignPtr (Vector p n fp) = (fp, ptrToOffset fp p, n)