storablevector-0.2.7: Fast, packed, strict storable arrays with a list interface like ByteString

Data.StorableVector

Contents

Description

A time and space-efficient implementation of vectors using packed arrays, suitable for high performance use, both in terms of large data quantities, or high speed requirements. Vectors are encoded as strict arrays, held in a `ForeignPtr`, and can be passed between C and Haskell with little effort.

This module is intended to be imported `qualified`, to avoid name clashes with Prelude functions. eg.

``` import qualified Data.StorableVector as V
```

Original GHC implementation by Bryan O'Sullivan. Rewritten to use UArray by Simon Marlow. Rewritten to support slices and use ForeignPtr by David Roundy. Polished and extended by Don Stewart. Generalized to any Storable value by Spencer Janssen. Chunky lazy stream, also with chunk pattern control, mutable access in ST monad, Builder monoid by Henning Thieleman.

Synopsis

# The `Vector` type

data Vector a Source

A space-efficient representation of a vector, supporting many efficient operations.

Instances of Eq, Ord, Read, Show, Data, Typeable

Instances

 Typeable1 Vector (Storable a, Eq a) => Eq (Vector a) Data a => Data (Vector a) (Storable a, Show a) => Show (Vector a) Storable a => Monoid (Vector a)

# Introducing and eliminating `Vector`s

empty :: Storable a => Vector aSource

O(1) The empty `Vector`

singleton :: Storable a => a -> Vector aSource

O(1) Construct a `Vector` containing a single element

pack :: Storable a => [a] -> Vector aSource

O(n) Convert a '[a]' into a 'Vector a'.

unpack :: Storable a => Vector a -> [a]Source

O(n) Converts a 'Vector a' to a '[a]'.

packN :: Storable a => Int -> [a] -> (Vector a, [a])Source

O(n) Convert first `n` elements of a '[a]' into a 'Vector a'.

packWith :: Storable b => (a -> b) -> [a] -> Vector bSource

O(n) Convert a list into a `Vector` using a conversion function

unpackWith :: Storable a => (a -> b) -> Vector a -> [b]Source

O(n) Convert a `Vector` into a list using a conversion function

# Basic interface

cons :: Storable a => a -> Vector a -> Vector aSource

O(n) `cons` is analogous to (:) for lists, but of different complexity, as it requires a memcpy.

snoc :: Storable a => Vector a -> a -> Vector aSource

O(n) Append an element to the end of a `Vector`

append :: Storable a => Vector a -> Vector a -> Vector aSource

O(n) Append two Vectors

head :: Storable a => Vector a -> aSource

O(1) Extract the first element of a `Vector`, which must be non-empty. An exception will be thrown in the case of an empty `Vector`.

last :: Storable a => Vector a -> aSource

O(1) Extract the last element of a `Vector`, which must be finite and non-empty. An exception will be thrown in the case of an empty `Vector`.

tail :: Storable a => Vector a -> Vector aSource

O(1) Extract the elements after the head of a `Vector`, which must be non-empty. An exception will be thrown in the case of an empty `Vector`.

init :: Vector a -> Vector aSource

O(1) Return all the elements of a `Vector` except the last one. An exception will be thrown in the case of an empty `Vector`.

null :: Vector a -> BoolSource

O(1) Test whether a `Vector` is empty.

length :: Vector a -> IntSource

O(1) `length` returns the length of a `Vector` as an `Int`.

viewL :: Storable a => Vector a -> Maybe (a, Vector a)Source

viewR :: Storable a => Vector a -> Maybe (Vector a, a)Source

switchL :: Storable a => b -> (a -> Vector a -> b) -> Vector a -> bSource

switchR :: Storable a => b -> (Vector a -> a -> b) -> Vector a -> bSource

# Transforming `Vector`s

map :: (Storable a, Storable b) => (a -> b) -> Vector a -> Vector bSource

O(n) `map` `f xs` is the `Vector` obtained by applying `f` to each element of `xs`.

reverse :: Storable a => Vector a -> Vector aSource

O(n) `reverse` `xs` efficiently returns the elements of `xs` in reverse order.

intersperse :: Storable a => a -> Vector a -> Vector aSource

O(n) The `intersperse` function takes a element and a `Vector` and `intersperses' that element between the elements of the `Vector`. It is analogous to the intersperse function on Lists.

transpose :: Storable a => [Vector a] -> [Vector a]Source

The `transpose` function transposes the rows and columns of its `Vector` argument.

# Reducing `Vector`s (folds)

foldl :: Storable a => (b -> a -> b) -> b -> Vector a -> bSource

`foldl`, applied to a binary operator, a starting value (typically the left-identity of the operator), and a Vector, reduces the `Vector` using the binary operator, from left to right. This function is subject to array fusion.

foldl' :: Storable a => (b -> a -> b) -> b -> Vector a -> bSource

'foldl\'' is like `foldl`, but strict in the accumulator.

foldl1 :: Storable a => (a -> a -> a) -> Vector a -> aSource

`foldl1` is a variant of `foldl` that has no starting value argument, and thus must be applied to non-empty `Vector`s. This function is subject to array fusion. An exception will be thrown in the case of an empty `Vector`.

foldl1' :: Storable a => (a -> a -> a) -> Vector a -> aSource

'foldl1\'' is like `foldl1`, but strict in the accumulator. An exception will be thrown in the case of an empty `Vector`.

foldr :: Storable a => (a -> b -> b) -> b -> Vector a -> bSource

`foldr`, applied to a binary operator, a starting value (typically the right-identity of the operator), and a `Vector`, reduces the `Vector` using the binary operator, from right to left. However, it is not the same as `foldl` applied to the reversed vector. Actually `foldr` starts processing with the first element, and thus can be used for efficiently building a singly linked list by `foldr (:) [] vec`. Unfortunately `foldr` is quite slow for low-level loops, since GHC (up to 6.12.1) cannot detect the loop.

foldr1 :: Storable a => (a -> a -> a) -> Vector a -> aSource

`foldr1` is a variant of `foldr` that has no starting value argument, and thus must be applied to non-empty `Vector`s An exception will be thrown in the case of an empty `Vector`.

## Special folds

concat :: Storable a => [Vector a] -> Vector aSource

O(n) Concatenate a list of `Vector`s.

concatMap :: (Storable a, Storable b) => (a -> Vector b) -> Vector a -> Vector bSource

Map a function over a `Vector` and concatenate the results

monoidConcatMap :: (Storable a, Monoid m) => (a -> m) -> Vector a -> mSource

This is like `mconcat . map f`, but in many cases the result of `f` will not be storable.

any :: Storable a => (a -> Bool) -> Vector a -> BoolSource

O(n) Applied to a predicate and a `Vector`, `any` determines if any element of the `Vector` satisfies the predicate.

all :: Storable a => (a -> Bool) -> Vector a -> BoolSource

O(n) Applied to a predicate and a `Vector`, `all` determines if all elements of the `Vector` satisfy the predicate.

maximum :: (Storable a, Ord a) => Vector a -> aSource

O(n) `maximum` returns the maximum value from a `Vector` This function will fuse. An exception will be thrown in the case of an empty `Vector`.

minimum :: (Storable a, Ord a) => Vector a -> aSource

O(n) `minimum` returns the minimum value from a `Vector` This function will fuse. An exception will be thrown in the case of an empty `Vector`.

# Building `Vector`s

## Scans

scanl :: (Storable a, Storable b) => (a -> b -> a) -> a -> Vector b -> Vector aSource

`scanl` is similar to `foldl`, but returns a list of successive reduced values from the left. This function will fuse.

``` scanl f z [x1, x2, ...] == [z, z `f` x1, (z `f` x1) `f` x2, ...]
```

Note that

``` last (scanl f z xs) == foldl f z xs.
```

scanl1 :: Storable a => (a -> a -> a) -> Vector a -> Vector aSource

`scanl1` is a variant of `scanl` that has no starting value argument. This function will fuse.

``` scanl1 f [x1, x2, ...] == [x1, x1 `f` x2, ...]
```

scanr :: (Storable a, Storable b) => (a -> b -> b) -> b -> Vector a -> Vector bSource

scanr is the right-to-left dual of scanl.

scanr1 :: Storable a => (a -> a -> a) -> Vector a -> Vector aSource

`scanr1` is a variant of `scanr` that has no starting value argument.

## Accumulating maps

mapAccumL :: (Storable a, Storable b) => (acc -> a -> (acc, b)) -> acc -> Vector a -> (acc, Vector b)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.

mapAccumR :: (Storable a, Storable b) => (acc -> a -> (acc, b)) -> acc -> Vector a -> (acc, Vector b)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`.

mapIndexed :: (Storable a, Storable b) => (Int -> a -> b) -> Vector a -> Vector bSource

O(n) map functions, provided with the index at each position

## Unfolding `Vector`s

replicate :: Storable a => Int -> a -> Vector aSource

O(n) `replicate` `n x` is a `Vector` of length `n` with `x` the value of every element.

iterateN :: Storable a => Int -> (a -> a) -> a -> Vector aSource

O(n) `iterateN` `n f x` is a `Vector` of length `n` where the elements of `x` are generated by repeated application of `f`.

unfoldr :: Storable b => (a -> Maybe (b, a)) -> a -> Vector bSource

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 element in the `Vector`, 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 :: Storable b => Int -> (a -> Maybe (b, a)) -> a -> (Vector 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)
```

unfoldrResultN :: Storable b => Int -> (a -> c) -> (a -> Either c (b, a)) -> a -> (Vector b, c)Source

O(n) Like `unfoldrN` this function builds a `Vector` from a seed value with limited size. Additionally it returns a value, that depends on the state, but is not necessarily the state itself. If end of vector and end of the generator coincide, then the result is as if only the end of vector is reached.

Example:

``` unfoldrResultN 30 Char.ord (\c -> if c>'z' then Left 1000 else Right (c, succ c)) 'a'
```

The following equation relates `unfoldrN` and `unfoldrResultN`:

``` unfoldrN n f s ==
unfoldrResultN n Just
(maybe (Left Nothing) Right . f) s
```

It is not possible to express `unfoldrResultN` in terms of `unfoldrN`.

sample :: Storable a => Int -> (Int -> a) -> Vector aSource

O(n), where n is the length of the result. This function constructs a vector by evaluating a function that depends on the element index. It is a special case of `unfoldrN` and can in principle be parallelized.

Examples:

```    sample 26 (\x -> chr(ord 'a'+x))
== pack "abcdefghijklmnopqrstuvwxyz"
```

# Substrings

## Breaking strings

take :: Storable a => Int -> Vector a -> Vector aSource

O(1) `take` `n`, applied to a `Vector` `xs`, returns the prefix of `xs` of length `n`, or `xs` itself if `n > length xs`.

drop :: Storable a => Int -> Vector a -> Vector aSource

O(1) `drop` `n xs` returns the suffix of `xs` after the first `n` elements, or `[]` if `n > length xs`.

splitAt :: Storable a => Int -> Vector a -> (Vector a, Vector a)Source

O(1) `splitAt` `n xs` is equivalent to `(take n xs, drop n xs)`.

takeWhile :: Storable a => (a -> Bool) -> Vector a -> Vector aSource

`takeWhile`, applied to a predicate `p` and a `Vector` `xs`, returns the longest prefix (possibly empty) of `xs` of elements that satisfy `p`.

dropWhile :: Storable a => (a -> Bool) -> Vector a -> Vector aSource

`dropWhile` `p xs` returns the suffix remaining after `takeWhile` `p xs`.

span :: Storable a => (a -> Bool) -> Vector a -> (Vector a, Vector a)Source

`span` `p xs` breaks the `Vector` into two segments. It is equivalent to `(takeWhile p xs, dropWhile p xs)`

spanEnd :: Storable a => (a -> Bool) -> Vector a -> (Vector a, Vector a)Source

`spanEnd` behaves like `span` but from the end of the `Vector`. We have

``` spanEnd (not.isSpace) "x y z" == ("x y ","z")
```

and

``` spanEnd (not . isSpace) ps
==
let (x,y) = span (not.isSpace) (reverse ps) in (reverse y, reverse x)
```

break :: Storable a => (a -> Bool) -> Vector a -> (Vector a, Vector a)Source

`break` `p` is equivalent to `span (not . p)`.

breakEnd :: Storable a => (a -> Bool) -> Vector a -> (Vector a, Vector a)Source

`breakEnd` behaves like `break` but from the end of the `Vector`

breakEnd p == spanEnd (not.p)

group :: (Storable a, Eq a) => Vector a -> [Vector a]Source

The `group` function takes a `Vector` and returns a list of `Vector`s such that the concatenation of the result is equal to the argument. Moreover, each sublist in the result contains only equal elements. For example,

``` group "Mississippi" = ["M","i","ss","i","ss","i","pp","i"]
```

It is a special case of `groupBy`, which allows the programmer to supply their own equality test. It is about 40% faster than groupBy (==)

groupBy :: Storable a => (a -> a -> Bool) -> Vector a -> [Vector a]Source

The `groupBy` function is the non-overloaded version of `group`.

inits :: Storable a => Vector a -> [Vector a]Source

O(n) Return all initial segments of the given `Vector`, shortest first.

tails :: Storable a => Vector a -> [Vector a]Source

O(n) Return all final segments of the given `Vector`, longest first.

## Breaking into many substrings

split :: (Storable a, Eq a) => a -> Vector a -> [Vector a]Source

O(n) Break a `Vector` into pieces separated by the argument, consuming the delimiter. I.e.

``` split '\n' "a\nb\nd\ne" == ["a","b","d","e"]
split 'a'  "aXaXaXa"    == ["","X","X","X"]
split 'x'  "x"          == ["",""]
```

and

``` join [c] . split c == id
split == splitWith . (==)
```

As for all splitting functions in this library, this function does not copy the substrings, it just constructs new `Vector`s that are slices of the original.

splitWith :: Storable a => (a -> Bool) -> Vector a -> [Vector a]Source

O(n) Splits a `Vector` into components delimited by separators, where the predicate returns True for a separator element. The resulting components do not contain the separators. Two adjacent separators result in an empty component in the output. eg.

``` splitWith (=='a') "aabbaca" == ["","","bb","c",""]
splitWith (=='a') []        == []
```

tokens :: Storable a => (a -> Bool) -> Vector a -> [Vector a]Source

Like `splitWith`, except that sequences of adjacent separators are treated as a single separator. eg.

``` tokens (=='a') "aabbaca" == ["bb","c"]
```

## Joining strings

join :: Storable a => Vector a -> [Vector a] -> Vector aSource

O(n) The `join` function takes a `Vector` and a list of `Vector`s and concatenates the list after interspersing the first argument between each element of the list.

# Predicates

isPrefixOf :: (Storable a, Eq a) => Vector a -> Vector a -> BoolSource

O(n) The `isPrefixOf` function takes two `Vector` and returns `True` iff the first is a prefix of the second.

isSuffixOf :: (Storable a, Eq a) => Vector a -> Vector a -> BoolSource

O(n) The `isSuffixOf` function takes two `Vector`s and returns `True` iff the first is a suffix of the second.

The following holds:

``` isSuffixOf x y == reverse x `isPrefixOf` reverse y
```

# Searching `Vector`s

## Searching by equality

elem :: (Storable a, Eq a) => a -> Vector a -> BoolSource

O(n) `elem` is the `Vector` membership predicate.

notElem :: (Storable a, Eq a) => a -> Vector a -> BoolSource

O(n) `notElem` is the inverse of `elem`

## Searching with a predicate

find :: Storable a => (a -> Bool) -> Vector a -> Maybe aSource

O(n) The `find` function takes a predicate and a `Vector`, and returns the first element in matching the predicate, or `Nothing` if there is no such element.

``` find f p = case findIndex f p of Just n -> Just (p ! n) ; _ -> Nothing
```

filter :: Storable a => (a -> Bool) -> Vector a -> Vector aSource

O(n) `filter`, applied to a predicate and a `Vector`, returns a `Vector` containing those elements that satisfy the predicate. This function is subject to array fusion.

# Indexing `Vector`s

index :: Storable a => Vector a -> Int -> aSource

O(1) `Vector` index (subscript) operator, starting from 0.

elemIndex :: (Storable a, Eq a) => a -> Vector a -> Maybe IntSource

O(n) The `elemIndex` function returns the index of the first element in the given `Vector` which is equal to the query element, or `Nothing` if there is no such element.

elemIndices :: (Storable a, Eq a) => a -> Vector a -> [Int]Source

O(n) The `elemIndices` function extends `elemIndex`, by returning the indices of all elements equal to the query element, in ascending order.

elemIndexEnd :: (Storable a, Eq a) => a -> Vector a -> Maybe IntSource

O(n) The `elemIndexEnd` function returns the last index of the element in the given `Vector` which is equal to the query element, or `Nothing` if there is no such element. The following holds:

``` elemIndexEnd c xs ==
(-) (length xs - 1) `fmap` elemIndex c (reverse xs)
```

findIndex :: Storable a => (a -> Bool) -> Vector a -> Maybe IntSource

The `findIndex` function takes a predicate and a `Vector` and returns the index of the first element in the `Vector` satisfying the predicate.

findIndices :: Storable a => (a -> Bool) -> Vector a -> [Int]Source

The `findIndices` function extends `findIndex`, by returning the indices of all elements satisfying the predicate, in ascending order.

count :: (Storable a, Eq a) => a -> Vector a -> IntSource

count returns the number of times its argument appears in the `Vector`

``` count = length . elemIndices
```

But more efficiently than using length on the intermediate list.

findIndexOrEnd :: Storable a => (a -> Bool) -> Vector a -> IntSource

`findIndexOrEnd` is a variant of findIndex, that returns the length of the string if no element is found, rather than Nothing.

# Zipping and unzipping `Vector`s

zip :: (Storable a, Storable b) => Vector a -> Vector b -> [(a, b)]Source

O(n) `zip` takes two `Vector`s and returns a list of corresponding pairs of elements. If one input `Vector` is short, excess elements of the longer `Vector` are discarded. This is equivalent to a pair of `unpack` operations.

zipWith :: (Storable a, Storable b, Storable c) => (a -> b -> c) -> Vector a -> Vector b -> Vector cSource

`zipWith` generalises `zip` by zipping with the function given as the first argument, instead of a tupling function. For example, `zipWith (+)` is applied to two `Vector`s to produce the list of corresponding sums.

zipWith3 :: (Storable a, Storable b, Storable c, Storable d) => (a -> b -> c -> d) -> Vector a -> Vector b -> Vector c -> Vector dSource

Like `zipWith` but for three input vectors

zipWith4 :: (Storable a, Storable b, Storable c, Storable d, Storable e) => (a -> b -> c -> d -> e) -> Vector a -> Vector b -> Vector c -> Vector d -> Vector eSource

Like `zipWith` but for four input vectors If you need even more input vectors, you might write a function yourselve using unfoldrN and viewL.

unzip :: (Storable a, Storable b) => [(a, b)] -> (Vector a, Vector b)Source

O(n) `unzip` transforms a list of pairs of elements into a pair of `Vector`s. Note that this performs two `pack` operations.

copy :: Storable a => Vector a -> Vector aSource

O(n) Make a copy of the `Vector` with its own storage. This is mainly useful to allow the rest of the data pointed to by the `Vector` to be garbage collected, for example if a large string has been read in, and only a small part of it is needed in the rest of the program.

# IO

hGet :: Storable a => Handle -> Int -> IO (Vector a)Source

Read a `Vector` directly from the specified `Handle`. This is far more efficient than reading the characters into a list and then using `pack`.

hPut :: Storable a => Handle -> Vector a -> IO ()Source

Outputs a `Vector` to the specified `Handle`.

readFile :: Storable a => FilePath -> IO (Vector a)Source

Read an entire file strictly into a `Vector`. This is far more efficient than reading the characters into a `String` and then using `pack`. It also may be more efficient than opening the file and reading it using hGet. Files are read using 'binary mode' on Windows.

writeFile :: Storable a => FilePath -> Vector a -> IO ()Source

Write a `Vector` to a file.

appendFile :: Storable a => FilePath -> Vector a -> IO ()Source

Append a `Vector` to a file.