From 0dd3cff5244d414f8779b2e4fc053bb5a0a3ec87 Mon Sep 17 00:00:00 2001
From: Don Stewart
Date: Tue, 16 Feb 2010 04:25:38 +0000
Subject: [PATCH] Documentation only (for Data.Vector module)

Data/Vector.hs  207 ++++++++++++++++++++++++++++++++++++++++++++
vector.cabal  4 +
2 files changed, 161 insertions(+), 50 deletions()
diff git a/Data/Vector.hs b/Data/Vector.hs
index bf0b80e..bf0a573 100644
 a/Data/Vector.hs
+++ b/Data/Vector.hs
@@ 9,25 +9,60 @@
 Stability : experimental
 Portability : nonportable

 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 listlike operations, and bulk
+ array operations.
+
+ For unboxed arrays, use the 'Data.Vector.Unboxed' interface.

module Data.Vector (
+
+  * The pure and mutable array types
Vector, MVector,
  * Length information
 length, null,
+  * Constructing vectors
+ empty,
+ singleton,
+ cons,
+ snoc,
+ (++),
+ replicate,
+ generate,
+ copy,
  * Construction
 empty, singleton, cons, snoc, replicate, generate, (++), copy,
+  * Operations based on length information
+ length,
+ null,
 * Accessing individual elements
 (!), head, last, indexM, headM, lastM,
+ (!),
+ head,
+ last,
+
+  ** Accessors in a monad
+ indexM,
+ headM,
+ lastM,
+
+  ** Accessor functions with no bounds checking
unsafeIndex, unsafeHead, unsafeLast,
unsafeIndexM, unsafeHeadM, unsafeLastM,
 * Subvectors
 slice, init, tail, take, drop,
+ init,
+ tail,
+ take,
+ drop,
+ slice,
+
+  * Subvector construction without bounds checks
unsafeSlice, unsafeInit, unsafeTail, unsafeTake, unsafeDrop,
 * Permutations
@@ 103,6 +138,7 @@ import Prelude hiding ( length, null,
import qualified Prelude
+  Boxed vectors, supporting efficient slicing.
data Vector a = Vector {# UNPACK #} !Int
{# UNPACK #} !Int
{# UNPACK #} !(Array a)
@@ 137,10 +173,12 @@ instance Ord a => Ord (Vector a) where
 Length
 
+ /O(1)/. Yield the length of a vector as an 'Int'
length :: Vector a > Int
{# INLINE length #}
length = G.length
+ /O(1)/. 'null' tests whether the given array is empty.
null :: Vector a > Bool
{# INLINE null #}
null = G.null
@@ 148,44 +186,48 @@ null = G.null
 Construction
 
  Empty vector
+ /O(1)/. 'empty' builds a vector of size zero.
empty :: Vector a
{# INLINE empty #}
empty = G.empty
  Vector with exaclty one element
+ /O(1)/, Vector with exactly one element
singleton :: a > Vector a
{# INLINE singleton #}
singleton = G.singleton
  Vector of the given length with the given value in each position
+ /O(n)/. @'replicate' n e@ yields a vector of length @n@ storing @e@ at each position
replicate :: Int > a > Vector a
{# INLINE replicate #}
replicate = G.replicate
  Generate a vector of the given length by applying the function to each
 index
+ /O(n)/, Generate a vector of the given length by applying a (pure)
+ generator function to each index
generate :: Int > (Int > a) > Vector a
{# INLINE generate #}
generate = G.generate
  Prepend an element
+ /O(n)/, Prepend an element to an array.
cons :: a > Vector a > Vector a
{# INLINE cons #}
cons = G.cons
  Append an element
+ /O(n)/, Append an element to an array.
snoc :: Vector a > a > Vector a
{# INLINE snoc #}
snoc = G.snoc
infixr 5 ++
  Concatenate two vectors
+
+ /O(n)/, Concatenate two vectors
(++) :: Vector a > Vector a > Vector a
{# INLINE (++) #}
(++) = (G.++)
  Create a copy of a vector. Useful when dealing with slices.
+ /O(n)/, Create a copy of a vector.
+ @copy@ is useful when dealing with slices, as the garbage collector
+ may be able to free the original vector if no further references are held.
+
copy :: Vector a > Vector a
{# INLINE copy #}
copy = G.copy
@@ 193,48 +235,57 @@ copy = G.copy
 Accessing individual elements
 
  Indexing
+ /O(1)/. Read the element in the vector at the given index.
(!) :: Vector a > Int > a
{# INLINE (!) #}
(!) = (G.!)
  First element
+ /O(1)/. 'head' returns the first element of the vector
head :: Vector a > a
{# INLINE head #}
head = G.head
  Last element
+ /O(n)/. 'last' yields the last element of an array.
last :: Vector a > a
{# INLINE last #}
last = G.last
  Unsafe indexing without bounds checking
+ /O(1)/, Unsafe indexing without bounds checking
+
+ By not performing bounds checks, this function may be faster when
+ this function is used in an inner loop)
+
unsafeIndex :: 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)/, Yield the first element of a vector without checking if the vector is empty
+
+ By not performing bounds checks, this function may be faster when
+ this function is used in an inner loop)
unsafeHead :: Vector a > a
{# INLINE unsafeHead #}
unsafeHead = G.unsafeHead
  Yield the last element of a vector without checking if the vector is
 empty
+  Yield the last element of a vector without checking if the vector is empty
+
+ By not performing bounds checks, this function may be faster when
+ this function is used in an inner loop)
unsafeLast :: 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 which can be strict in the vector while remaining lazy in the element
indexM :: Monad m => Vector a > Int > m a
{# INLINE indexM #}
indexM = G.indexM
+  Monadic head which can be strict in the vector while remaining lazy in the element
headM :: Monad m => Vector a > m a
{# INLINE headM #}
headM = G.headM
+  Monadic last which can be strict in the vector while remaining lazy in the element
lastM :: Monad m => Vector a > m a
{# INLINE lastM #}
lastM = G.lastM
@@ 244,10 +295,12 @@ unsafeIndexM :: Monad m => Vector a > Int > m a
{# INLINE unsafeIndexM #}
unsafeIndexM = G.unsafeIndexM
+  Unsafe monadic head (access the first element) without bounds checks
unsafeHeadM :: Monad m => Vector a > m a
{# INLINE unsafeHeadM #}
unsafeHeadM = G.unsafeHeadM
+  Unsafe monadic last (access the last element) without bounds checks
unsafeLastM :: Monad m => Vector a > m a
{# INLINE unsafeLastM #}
unsafeLastM = G.unsafeLastM
@@ 255,8 +308,8 @@ unsafeLastM = G.unsafeLastM
 Subarrays
 
  Yield a part of the vector without copying it. Safer version of
 'basicUnsafeSlice'.
+  /O(1)/, Yield a part of the vector without copying it.
+
slice :: Int  ^ starting index
> Int  ^ length
> Vector a
@@ 264,27 +317,27 @@ slice :: Int  ^ starting index
{# INLINE slice #}
slice = G.slice
  Yield all but the last element without copying.
+ /O(1)/, Yield all but the last element without copying.
init :: 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).
tail :: Vector a > Vector a
{# INLINE tail #}
tail = G.tail
  Yield the first @n@ elements without copying.
+ /O(1)/, Yield the first @n@ elements without copying.
take :: 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.
drop :: Int > Vector a > Vector a
{# INLINE drop #}
drop = G.drop
  Unsafely yield a part of the vector without copying it and without
+ /O(1)/, Unsafely yield a part of the vector without copying it and without
 performing bounds checks.
unsafeSlice :: Int  ^ starting index
> Int  ^ length
@@ 293,18 +346,22 @@ unsafeSlice :: Int  ^ starting index
{# INLINE unsafeSlice #}
unsafeSlice = G.unsafeSlice
+ /O(1)/, Zerocopying 'init' without bounds checks.
unsafeInit :: Vector a > Vector a
{# INLINE unsafeInit #}
unsafeInit = G.unsafeInit
+ /O(1)/, Zerocopying 'tail' without bounds checks.
unsafeTail :: Vector a > Vector a
{# INLINE unsafeTail #}
unsafeTail = G.unsafeTail
+ /O(1)/, Zerocopying 'take' without bounds checks.
unsafeTake :: Int > Vector a > Vector a
{# INLINE unsafeTake #}
unsafeTake = G.unsafeTake
+ /O(1)/, Zerocopying 'drop' without bounds checks.
unsafeDrop :: Int > Vector a > Vector a
{# INLINE unsafeDrop #}
unsafeDrop = G.unsafeDrop
@@ 312,63 +369,80 @@ unsafeDrop = G.unsafeDrop
 Permutations
 
+ TODO there is no documentation for the accum* family of functions
+
+  TODO unsafeAccum.
unsafeAccum :: (a > b > a) > Vector a > [(Int,b)] > Vector a
{# INLINE unsafeAccum #}
unsafeAccum = G.unsafeAccum
+  TODO unsafeAccumulate
unsafeAccumulate :: (a > b > a) > Vector a > Vector (Int,b) > Vector a
{# INLINE unsafeAccumulate #}
unsafeAccumulate = G.unsafeAccumulate
+  TODO unsafeAccumulate_
unsafeAccumulate_
:: (a > b > a) > Vector a > Vector Int > Vector b > Vector a
{# INLINE unsafeAccumulate_ #}
unsafeAccumulate_ = G.unsafeAccumulate_
+  TODO accum
accum :: (a > b > a) > Vector a > [(Int,b)] > Vector a
{# INLINE accum #}
accum = G.accum
+  TODO accumulate
accumulate :: (a > b > a) > Vector a > Vector (Int,b) > Vector a
{# INLINE accumulate #}
accumulate = G.accumulate
+  TODO accumulate_
accumulate_ :: (a > b > a) > Vector a > Vector Int > Vector b > Vector a
{# INLINE accumulate_ #}
accumulate_ = G.accumulate_
+  TODO unsafeUpd
unsafeUpd :: Vector a > [(Int, a)] > Vector a
{# INLINE unsafeUpd #}
unsafeUpd = G.unsafeUpd
+  TODO unsafeUpdate
unsafeUpdate :: Vector a > Vector (Int, a) > Vector a
{# INLINE unsafeUpdate #}
unsafeUpdate = G.unsafeUpdate
+  TODO unsafeUpdate_
unsafeUpdate_ :: Vector a > Vector Int > Vector a > Vector a
{# INLINE unsafeUpdate_ #}
unsafeUpdate_ = G.unsafeUpdate_
+  TODO (//)
(//) :: Vector a > [(Int, a)] > Vector a
{# INLINE (//) #}
(//) = (G.//)
+  TODO update
update :: Vector a > Vector (Int, a) > Vector a
{# INLINE update #}
update = G.update
+  TODO update_
update_ :: Vector a > Vector Int > Vector a > Vector a
{# INLINE update_ #}
update_ = G.update_
+  backpermute, courtesy Blelloch. The backpermute is a gather\/get operation.
backpermute :: Vector a > Vector Int > Vector a
{# INLINE backpermute #}
backpermute = G.backpermute
+  TODO unsafeBackpermute
unsafeBackpermute :: Vector a > Vector Int > Vector a
{# INLINE unsafeBackpermute #}
unsafeBackpermute = G.unsafeBackpermute
+  /O(n)/, reverse the elements of the given vector.
reverse :: Vector a > Vector a
{# INLINE reverse #}
reverse = G.reverse
@@ 376,16 +450,17 @@ reverse = G.reverse
 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 = G.map
  Apply a function to every index/value pair
+  /O(n)/, Apply a function to every index/value pair yielding a new vector
imap :: (Int > a > b) > Vector a > Vector b
{# INLINE imap #}
imap = G.imap
+  /O(n)/, generate a vector from each element of the input vector, then join the results.
concatMap :: (a > Vector b) > Vector a > Vector b
{# INLINE concatMap #}
concatMap = G.concatMap
@@ 393,65 +468,73 @@ concatMap = G.concatMap
 Zipping/unzipping
 
  Zip two vectors with the given function.
+ /O(n)/, Zip two vectors with the given function.
zipWith :: (a > b > c) > Vector a > Vector b > Vector c
{# INLINE zipWith #}
zipWith = G.zipWith
  Zip three vectors with the given function.
+ /O(n)/, Zip three vectors with the given function.
zipWith3 :: (a > b > c > d) > Vector a > Vector b > Vector c > Vector d
{# INLINE zipWith3 #}
zipWith3 = G.zipWith3
+ /O(n)/, Zip four vectors with the given function.
zipWith4 :: (a > b > c > d > e)
> Vector a > Vector b > Vector c > Vector d > Vector e
{# INLINE zipWith4 #}
zipWith4 = G.zipWith4
+ /O(n)/, Zip five vectors with the given function.
zipWith5 :: (a > b > c > d > e > f)
> Vector a > Vector b > Vector c > Vector d > Vector e
> Vector f
{# INLINE zipWith5 #}
zipWith5 = G.zipWith5
+ /O(n)/, Zip six vectors with the given function.
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
  Zip two vectors and their indices with the given function.
+ /O(n)/, Zip two vectors and their indices with the given function.
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.
+ /O(n)/, 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
+ /O(n)/, Zip four vectors and their indices with the given function.
izipWith4 :: (Int > a > b > c > d > e)
> Vector a > Vector b > Vector c > Vector d > Vector e
{# INLINE izipWith4 #}
izipWith4 = G.izipWith4
+ /O(n)/, Zip five vectors and their indices with the given function.
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
+ /O(n)/, Zip six vectors and their indices with the given function.
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 = 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 = G.zip3
@@ 471,6 +554,7 @@ zip6 :: Vector a > Vector b > Vector c > Vector d > Vector e > Vector f
{# INLINE zip6 #}
zip6 = G.zip6
+  Elementwise unpairing of array elements.
unzip :: Vector (a, b) > (Vector a, Vector b)
{# INLINE unzip #}
unzip = G.unzip
@@ 496,23 +580,23 @@ unzip6 = G.unzip6
 Filtering
 
  Drop elements which do not satisfy the predicate
+ /O(n)/, Remove elements from the vector which do not satisfy the predicate
filter :: (a > Bool) > Vector a > Vector a
{# INLINE filter #}
filter = G.filter
  Drop elements that do not satisfy the predicate (applied to values and
+ /O(n)/, Drop elements that do not satisfy the predicate (applied to values and
 their indices)
ifilter :: (Int > a > Bool) > Vector a > Vector a
{# INLINE ifilter #}
ifilter = G.ifilter
  Yield the longest prefix of elements satisfying the predicate.
+ /O(n)/, Yield the longest prefix of elements satisfying the predicate.
takeWhile :: (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.
dropWhile :: (a > Bool) > Vector a > Vector a
{# INLINE dropWhile #}
dropWhile = G.dropWhile
@@ 525,14 +609,14 @@ partition :: (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
+ /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.
unstablePartition :: (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
+ /O(n)/, Split the vector into the longest prefix of elements that satisfy the
 predicate and the rest.
span :: (a > Bool) > Vector a > (Vector a, Vector a)
{# INLINE span #}
@@ 595,7 +679,7 @@ foldl :: (a > b > a) > a > Vector b > a
{# INLINE foldl #}
foldl = G.foldl
  Lefgt fold on nonempty vectors
+  Left fold on nonempty vectors
foldl1 :: (a > a > a) > Vector a > a
{# INLINE foldl1 #}
foldl1 = G.foldl1
@@ 655,58 +739,74 @@ ifoldr' = G.ifoldr'
 Specialised folds
 
+ /O(n)/. @'all' p u@ determines whether all elements in array @u@ satisfy
+ predicate @p@.
all :: (a > Bool) > Vector a > Bool
{# INLINE all #}
all = G.all
+ /O(n)/. @'any' p u@ determines whether any element in array @u@ satisfies
+ predicate @p@.
any :: (a > Bool) > Vector a > Bool
{# INLINE any #}
any = G.any
+ /O(n)/. 'and' yields the conjunction of a boolean array.
and :: Vector Bool > Bool
{# INLINE and #}
and = G.and
+ /O(n)/. 'or' yields the disjunction of a boolean array.
or :: Vector Bool > Bool
{# INLINE or #}
or = G.or
+ /O(n)/. 'sum' computes the sum (with @(+)@) of an array of elements.
sum :: Num a => Vector a > a
{# INLINE sum #}
sum = G.sum
+ /O(n)/. 'sum' computes the product (with @(*)@) of an array of elements.
product :: Num a => Vector a > a
{# INLINE product #}
product = G.product
+ /O(n)/. 'maximum' finds the maximum element in an array of orderable elements.
maximum :: Ord a => Vector a > a
{# INLINE maximum #}
maximum = G.maximum
+ /O(n)/. 'maximumBy' finds the maximum element in an array under the given ordering.
maximumBy :: (a > a > Ordering) > Vector a > a
{# INLINE maximumBy #}
maximumBy = G.maximumBy
+ /O(n)/. 'minimum' finds the minimum element in an array of orderable elements.
minimum :: Ord a => Vector a > a
{# INLINE minimum #}
minimum = G.minimum
+ /O(n)/. 'minimumBy' finds the minimum element in an array under the given ordering.
minimumBy :: (a > a > Ordering) > Vector a > a
{# INLINE minimumBy #}
minimumBy = G.minimumBy
+  TODO maxIndex
maxIndex :: Ord a => Vector a > Int
{# INLINE maxIndex #}
maxIndex = G.maxIndex
+  TODO maxIndexBy
maxIndexBy :: (a > a > Ordering) > Vector a > Int
{# INLINE maxIndexBy #}
maxIndexBy = G.maxIndexBy
+  TODO minIndex
minIndex :: Ord a => Vector a > Int
{# INLINE minIndex #}
minIndex = G.minIndex
+  TODO minIndexBy
minIndexBy :: (a > a > Ordering) > Vector a > Int
{# INLINE minIndexBy #}
minIndexBy = G.minIndexBy
@@ 714,6 +814,18 @@ minIndexBy = G.minIndexBy
 Unfolding
 
+  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, b1)) 10
+ > [10,9,8,7,6,5,4,3,2,1]
+
unfoldr :: (b > Maybe (a, b)) > b > Vector a
{# INLINE unfoldr #}
unfoldr = G.unfoldr
@@ 741,7 +853,7 @@ postscanl' :: (a > b > a) > a > Vector b > Vector a
{# INLINE postscanl' #}
postscanl' = G.postscanl'
  Haskellstyle scan
+  Haskellstyle scan function.
scanl :: (a > b > a) > a > Vector b > Vector a
{# INLINE scanl #}
scanl = G.scanl
@@ 761,7 +873,6 @@ scanl1' :: (a > a > a) > Vector a > Vector a
{# INLINE scanl1' #}
scanl1' = G.scanl1'

  Prefix righttoleft scan
prescanr :: (a > b > b) > b > Vector a > Vector b
{# INLINE prescanr #}
diff git a/vector.cabal b/vector.cabal
index c6c6551..03676a4 100644
 a/vector.cabal
+++ b/vector.cabal
@@ 10,8 +10,8 @@ Category: Data, Data Structures
Synopsis: Efficient Arrays
Description:
.
 An efficient implementation of Intindexed arrays with a powerful loop
 fusion framework.
+ An efficient implementation of Intindexed arrays (both mutable
+ and immutable), with a powerful loop fusion optimization framework .
.
It is structured as follows:
.

1.9.1