Copyright  (c) Dong Han 20172019 (c) Tao He 20182019 

License  BSD 
Maintainer  winterland1989@gmail.com 
Stability  experimental 
Portability  nonportable 
Safe Haskell  None 
Language  Haskell2010 
This module provides unified vector interface. Conceptually a vector is simply a slice of an array, for example this is the definition of boxed vector:
data Vector a = Vector !(SmallArray a) !Int !Int  payload offset length
The Vec
class unified different type of vectors, and this module provide operation over Vec
instances, with all the internal structures. Be careful on modifying internal slices, otherwise segmentation fault await.
Synopsis
 class Arr (IArray v) a => Vec v a where
 pattern Vec :: Vec v a => IArray v a > Int > Int > v a
 arrVec :: (Vec v a, Vec u a, IArray v ~ IArray u) => v a > u a
 indexMaybe :: Vec v a => v a > Int > Maybe a
 data Vector a = Vector !(SmallArray a) !Int !Int
 data PrimVector a = PrimVector !(PrimArray a) !Int !Int
 type Bytes = PrimVector Word8
 packASCII :: String > Bytes
 create :: Vec v a => Int > (forall s. MArr (IArray v) s a > ST s ()) > v a
 create' :: Vec v a => Int > (forall s. MArr (IArray v) s a > ST s (IPair (MArr (IArray v) s a))) > v a
 creating :: Vec v a => Int > (forall s. MArr (IArray v) s a > ST s b) > (b, v a)
 creating' :: Vec v a => Int > (forall s. MArr (IArray v) s a > ST s (b, IPair (MArr (IArray v) s a))) > (b, v a)
 createN :: (Vec v a, HasCallStack) => Int > (forall s. MArr (IArray v) s a > ST s Int) > v a
 createN2 :: (Vec v a, Vec u b, HasCallStack) => Int > Int > (forall s. MArr (IArray v) s a > MArr (IArray u) s b > ST s (Int, Int)) > (v a, u b)
 empty :: Vec v a => v a
 singleton :: Vec v a => a > v a
 copy :: Vec v a => v a > v a
 pack :: Vec v a => [a] > v a
 packN :: forall v a. Vec v a => Int > [a] > v a
 packN' :: forall v a. Vec v a => Int > [a] > v a
 packR :: Vec v a => [a] > v a
 packRN :: forall v a. Vec v a => Int > [a] > v a
 packRN' :: forall v a. Vec v a => Int > [a] > v a
 unpack :: Vec v a => v a > [a]
 unpackR :: Vec v a => v a > [a]
 null :: Vec v a => v a > Bool
 length :: Vec v a => v a > Int
 append :: Vec v a => v a > v a > v a
 map :: forall u v a b. (Vec u a, Vec v b) => (a > b) > u a > v b
 map' :: forall u v a b. (Vec u a, Vec v b) => (a > b) > u a > v b
 imap' :: forall u v a b. (Vec u a, Vec v b) => (Int > a > b) > u a > v b
 traverseVec :: (Vec v a, Vec u b, Applicative f) => (a > f b) > v a > f (u b)
 traverseWithIndex :: (Vec v a, Vec u b, Applicative f) => (Int > a > f b) > v a > f (u b)
 traverseVec_ :: (Vec v a, Applicative f) => (a > f b) > v a > f ()
 traverseWithIndex_ :: (Vec v a, Applicative f) => (Int > a > f b) > v a > f ()
 foldl' :: Vec v a => (b > a > b) > b > v a > b
 ifoldl' :: Vec v a => (b > Int > a > b) > b > v a > b
 foldl1' :: forall v a. (Vec v a, HasCallStack) => (a > a > a) > v a > a
 foldl1Maybe' :: forall v a. Vec v a => (a > a > a) > v a > Maybe a
 foldr' :: Vec v a => (a > b > b) > b > v a > b
 ifoldr' :: Vec v a => (Int > a > b > b) > b > v a > b
 foldr1' :: forall v a. (Vec v a, HasCallStack) => (a > a > a) > v a > a
 foldr1Maybe' :: forall v a. Vec v a => (a > a > a) > v a > Maybe a
 concat :: forall v a. Vec v a => [v a] > v a
 concatMap :: Vec v a => (a > v a) > v a > v a
 maximum :: (Vec v a, Ord a, HasCallStack) => v a > a
 minimum :: (Vec v a, Ord a, HasCallStack) => v a > a
 maximumMaybe :: (Vec v a, Ord a) => v a > Maybe a
 minimumMaybe :: (Vec v a, Ord a) => v a > Maybe a
 sum :: (Vec v a, Num a) => v a > a
 count :: (Vec v a, Eq a) => a > v a > Int
 countBytes :: Word8 > Bytes > Int
 product :: (Vec v a, Num a) => v a > a
 product' :: (Vec v a, Num a, Eq a) => v a > a
 all :: Vec v a => (a > Bool) > v a > Bool
 any :: Vec v a => (a > Bool) > v a > Bool
 mapAccumL :: forall u v a b c. (Vec u b, Vec v c) => (a > b > (a, c)) > a > u b > (a, v c)
 mapAccumR :: forall u v a b c. (Vec u b, Vec v c) => (a > b > (a, c)) > a > u b > (a, v c)
 replicate :: Vec v a => Int > a > v a
 cycleN :: forall v a. Vec v a => Int > v a > v a
 unfoldr :: Vec u b => (a > Maybe (b, a)) > a > u b
 unfoldrN :: forall v a b. Vec v b => Int > (a > Maybe (b, a)) > a > (v b, Maybe a)
 elem :: (Vec v a, Eq a) => a > v a > Bool
 notElem :: (Vec v a, Eq a) => a > v a > Bool
 elemIndex :: (Vec v a, Eq a) => a > v a > Maybe Int
 data IPair a = IPair {}
 mapIPair' :: (a > b) > IPair a > IPair b
 fromIPair :: IPair a > (Int, a)
 toIPair :: (Int, a) > IPair a
 defaultInitSize :: Int
 chunkOverhead :: Int
 defaultChunkSize :: Int
 smallChunkSize :: Int
 data VectorException
 errorEmptyVector :: HasCallStack => a
 errorOutRange :: HasCallStack => Int > a
 castVector :: (Vec v a, Cast a b) => v a > v b
 c_strcmp :: Addr# > Addr# > IO CInt
 c_memchr :: ByteArray# > Int > Word8 > Int > Int
 c_memrchr :: ByteArray# > Int > Word8 > Int > Int
 c_strlen :: Addr# > IO CSize
 c_ascii_validate_addr :: Addr# > Int > IO Int
 c_fnv_hash_addr :: Addr# > Int > Int > IO Int
 c_fnv_hash_ba :: ByteArray# > Int > Int > Int > IO Int
The Vec typeclass
class Arr (IArray v) a => Vec v a where Source #
Typeclass for box and unboxed vectors, which are created by slicing arrays.
Instead of providing a generalized vector with polymorphric array field, we use this typeclass so that instances use concrete array type can unpack their array payload.
Vector types, e.g. Vector
,PrimVector
... are obivious instances, with O(1) toArr
and
fromArr
, which convert slices to (array, offset, length) tuple back and forth.
Array types can also be instances of this class, e.g. Array
, PrimArray
..., in this case
toArr
will always return offset 0 and whole array length, and fromArr
is O(n) copyArr
.
toArr :: v a > (IArray v a, Int, Int) Source #
Get underline array and slice range(offset and length).
fromArr :: IArray v a > Int > Int > v a Source #
Create a vector by slicing an array(with offset and length).
Instances
Prim a => Vec PrimArray a Source #  
Vec SmallArray a Source #  
Defined in Z.Data.Vector.Base toArr :: SmallArray a > (IArray SmallArray a, Int, Int) Source # fromArr :: IArray SmallArray a > Int > Int > SmallArray a Source #  
Vec Array a Source #  
Prim a => Vec PrimVector a Source #  
Defined in Z.Data.Vector.Base toArr :: PrimVector a > (IArray PrimVector a, Int, Int) Source # fromArr :: IArray PrimVector a > Int > Int > PrimVector a Source #  
Vec Vector a Source #  
PrimUnlifted a => Vec (UnliftedArray :: Type > Type) a Source #  
Defined in Z.Data.Vector.Base toArr :: UnliftedArray a > (IArray UnliftedArray a, Int, Int) Source # fromArr :: IArray UnliftedArray a > Int > Int > UnliftedArray a Source # 
pattern Vec :: Vec v a => IArray v a > Int > Int > v a Source #
A pattern synonyms for matching the underline array, offset and length.
This is a bidirectional pattern synonyms, but very unsafe if not use properly. Make sure your slice is within array's bounds!
arrVec :: (Vec v a, Vec u a, IArray v ~ IArray u) => v a > u a Source #
Change vector types based on same array type, e.g. construct an array from a slice, or viceversa.
indexMaybe :: Vec v a => v a > Int > Maybe a Source #
O(1) Index vector's element.
Return Nothing
if index is out of bounds.
Boxed and unboxed vector type
Boxed vector
Vector  

Instances
data PrimVector a Source #
Primitive vector
Instances
Word8 vector
Creating utilities
:: Vec v a  
=> Int  length in elements of type 
> (forall s. MArr (IArray v) s a > ST s ())  initialization function 
> v a 
Create a vector with size N.
:: Vec v a  
=> Int  length in elements of type 
> (forall s. MArr (IArray v) s a > ST s (IPair (MArr (IArray v) s a)))  initialization function return a result size and array, the result must start from index 0 
> v a 
Create a vector with a initial size N array (which may not be the final array).
Create a vector with a initial size N array, return both the vector and the monadic result during creating.
The result is not demanded strictly while the returned vector will be in normal form.
It this is not desired, use return $!
idiom in your initialization function.
:: Vec v a  
=> Int  
> (forall s. MArr (IArray v) s a > ST s (b, IPair (MArr (IArray v) s a)))  initialization function 
> (b, v a) 
Create a vector with a initial size N array (which may not be the final array), return both the vector and the monadic result during creating.
The result is not demanded strictly while the returned vector will be in normal form.
It this is not desired, use return $!
idiom in your initialization function.
:: (Vec v a, HasCallStack)  
=> Int  length's upper bound 
> (forall s. MArr (IArray v) s a > ST s Int)  initialization function which return the actual length 
> v a 
Create a vector up to a specific length.
If the initialization function return a length larger than initial size,
an IndexOutOfVectorRange
will be raised.
createN2 :: (Vec v a, Vec u b, HasCallStack) => Int > Int > (forall s. MArr (IArray v) s a > MArr (IArray u) s b > ST s (Int, Int)) > (v a, u b) Source #
Create two vector up to a specific length.
If the initialization function return lengths larger than initial sizes,
an IndexOutOfVectorRange
will be raised.
Conversion between list
pack :: Vec v a => [a] > v a Source #
O(n) Convert a list into a vector
Alias for
.packN
defaultInitSize
packN :: forall v a. Vec v a => Int > [a] > v a Source #
O(n) Convert a list into a vector with an approximate size.
If the list's length is large than the size given, we simply double the buffer size and continue building.
This function is a good consumer in the sense of build/foldr fusion.
packN' :: forall v a. Vec v a => Int > [a] > v a Source #
O(n) Convert a list into a vector with given size.
If the list's length is large than the size given, we drop the rest elements.
This function is a good consumer in the sense of build/foldr fusion.
packRN :: forall v a. Vec v a => Int > [a] > v a Source #
O(n) packN
in reverse order.
This function is a good consumer in the sense of build/foldr fusion.
packRN' :: forall v a. Vec v a => Int > [a] > v a Source #
O(n) packN'
in reverse order.
>>>
packRN' 3 [1,2,3,4,5]
>>>
[3,2,1]
This function is a good consumer in the sense of build/foldr fusion.
unpack :: Vec v a => v a > [a] Source #
O(n) Convert vector to a list.
Unpacking is done lazily. i.e. we will retain reference to the array until all element are consumed.
This function is a good producer in the sense of build/foldr fusion.
unpackR :: Vec v a => v a > [a] Source #
O(n) Convert vector to a list in reverse order.
This function is a good producer in the sense of build/foldr fusion.
Basic interface
append :: Vec v a => v a > v a > v a Source #
O(m+n)
There's no need to guard empty vector because we guard them for you, so appending empty vectors are noops.
map :: forall u v a b. (Vec u a, Vec v b) => (a > b) > u a > v b Source #
Mapping between vectors (possiblely with two different vector types).
NOTE, the result vector contain thunks in lifted Vector
case, use map'
if that's not desired.
For PrimVector
, map
and map'
are same, since PrimVector
s never
store thunks.
imap' :: forall u v a b. (Vec u a, Vec v b) => (Int > a > b) > u a > v b Source #
Strict mapping with index.
traverseVec :: (Vec v a, Vec u b, Applicative f) => (a > f b) > v a > f (u b) Source #
Traverse vector and gather result in another vector,
traverseWithIndex :: (Vec v a, Vec u b, Applicative f) => (Int > a > f b) > v a > f (u b) Source #
Traverse vector and gather result in another vector,
traverseVec_ :: (Vec v a, Applicative f) => (a > f b) > v a > f () Source #
Traverse vector without gathering result.
traverseWithIndex_ :: (Vec v a, Applicative f) => (Int > a > f b) > v a > f () Source #
Traverse vector with index.
ifoldl' :: Vec v a => (b > Int > a > b) > b > v a > b Source #
Strict left to right fold with index.
foldl1' :: forall v a. (Vec v a, HasCallStack) => (a > a > a) > v a > a Source #
Strict left to right fold using first element as the initial value.
Throw EmptyVector
if vector is empty.
foldl1Maybe' :: forall v a. Vec v a => (a > a > a) > v a > Maybe a Source #
Strict left to right fold using first element as the initial value.
return Nothing
when vector is empty.
ifoldr' :: Vec v a => (Int > a > b > b) > b > v a > b Source #
Strict right to left fold with index
NOTE: the index is counting from 0, not backwards
foldr1' :: forall v a. (Vec v a, HasCallStack) => (a > a > a) > v a > a Source #
Strict right to left fold using last element as the initial value.
Throw EmptyVector
if vector is empty.
foldr1Maybe' :: forall v a. Vec v a => (a > a > a) > v a > Maybe a Source #
Strict right to left fold using last element as the initial value,
return Nothing
when vector is empty.
Special folds
concat :: forall v a. Vec v a => [v a] > v a Source #
O(n) Concatenate a list of vector.
Note: concat
have to force the entire list to filter out empty vector and calculate
the length for allocation.
concatMap :: Vec v a => (a > v a) > v a > v a Source #
Map a function over a vector and concatenate the results
maximum :: (Vec v a, Ord a, HasCallStack) => v a > a Source #
O(n) maximum
returns the maximum value from a vector
It's defined with foldl1'
, an EmptyVector
exception will be thrown
in the case of an empty vector.
minimum :: (Vec v a, Ord a, HasCallStack) => v a > a Source #
O(n) minimum
returns the minimum value from a vector
An EmptyVector
exception will be thrown in the case of an empty vector.
count :: (Vec v a, Eq a) => a > v a > Int Source #
O(n) count
returns count of an element from a vector
product :: (Vec v a, Num a) => v a > a Source #
O(n) product
returns the product value from a vector
product' :: (Vec v a, Num a, Eq a) => v a > a Source #
O(n) product
returns the product value from a vector
This function will shortcut on zero. Note this behavior change the semantics
for lifted vector: product [1,0,undefined] /= product' [1,0,undefined]
.
all :: Vec v a => (a > Bool) > v a > Bool Source #
O(n) Applied to a predicate and a vector, all
determines
if all elements of the vector satisfy the predicate.
any :: Vec v a => (a > Bool) > v a > Bool Source #
O(n) Applied to a predicate and a vector, any
determines
if any elements of the vector satisfy the predicate.
Building vector
Accumulating maps
mapAccumL :: forall u v a b c. (Vec u b, Vec v c) => (a > b > (a, c)) > a > u b > (a, v c) Source #
The mapAccumL
function behaves like a combination of map
and
foldl
; it applies a function to each element of a vector,
passing an accumulating parameter from left to right, and returning a
final value of this accumulator together with the new list.
Note, this function will only force the result tuple, not the elements inside,
to prevent creating thunks during mapAccumL
, seq
your accumulator and result
with the result tuple.
mapAccumR :: forall u v a b c. (Vec u b, Vec v c) => (a > b > (a, c)) > a > u b > (a, v c) Source #
The mapAccumR
function behaves like a combination of map
and
foldr
; it applies a function to each element of a vector,
passing an accumulating parameter from right to left, and returning a
final value of this accumulator together with the new vector.
The same strictness property with mapAccumL
applys to mapAccumR
too.
Generating and unfolding vector
unfoldr :: Vec u b => (a > Maybe (b, a)) > a > u b Source #
O(n), where n is the length of the result. The unfoldr
function is analogous to the List 'unfoldr'. unfoldr
builds a
vector from a seed value. The function takes the element and
returns Nothing
if it is done producing the vector or returns
Just
(a,b)
, in which case, a
is the next byte in the string,
and b
is the seed value for further production.
Examples:
unfoldr (\x > if x <= 5 then Just (x, x + 1) else Nothing) 0 == pack [0, 1, 2, 3, 4, 5]
unfoldrN :: forall v a b. Vec v b => Int > (a > Maybe (b, a)) > a > (v b, Maybe a) Source #
O(n) Like unfoldr
, unfoldrN
builds a vector from a seed
value. However, the length of the result is limited by the first
argument to unfoldrN
. This function is more efficient than unfoldr
when the maximum length of the result is known.
The following equation relates unfoldrN
and unfoldr
:
fst (unfoldrN n f s) == take n (unfoldr f s)
Searching by equality
elem :: (Vec v a, Eq a) => a > v a > Bool Source #
O(n) elem
test if given element is in given vector.
Misc
Pair type to help GHC unpack in some loops, useful when write fast folds.
Instances
Functor IPair Source #  
Eq a => Eq (IPair a) Source #  
Ord a => Ord (IPair a) Source #  
Show a => Show (IPair a) Source #  
Arbitrary v => Arbitrary (IPair v) Source #  
CoArbitrary v => CoArbitrary (IPair v) Source #  
Defined in Z.Data.Vector.Base coarbitrary :: IPair v > Gen b > Gen b #  
NFData a => NFData (IPair a) Source #  
Defined in Z.Data.Vector.Base 
defaultInitSize :: Int Source #
defaultInitSize = 30
, used as initialize size when packing list of unknown size.
chunkOverhead :: Int Source #
The memory management overhead. Currently this is tuned for GHC only.
defaultChunkSize :: Int Source #
The chunk size used for I/O. Currently set to 16k  chunkOverhead
smallChunkSize :: Int Source #
The recommended chunk size. Currently set to 4k  chunkOverhead
.
data VectorException Source #
All exception can be throw by using Vec
.
Instances
Show VectorException Source #  
Defined in Z.Data.Vector.Base showsPrec :: Int > VectorException > ShowS # show :: VectorException > String # showList :: [VectorException] > ShowS #  
Exception VectorException Source #  
Defined in Z.Data.Vector.Base 
errorEmptyVector :: HasCallStack => a Source #
errorOutRange :: HasCallStack => Int > a Source #
castVector :: (Vec v a, Cast a b) => v a > v b Source #
Cast between vectors
C FFI
c_fnv_hash_ba :: ByteArray# > Int > Int > Int > IO Int Source #