Safe Haskell | None |
---|---|

Language | Haskell2010 |

# Finite vectors

The

type represents a finite vector (or dynamic array) of elements of type `Vector`

a`a`

.
A `Vector`

is strict in its spine.

The class instances are based on those for lists.

This module should be imported qualified, to avoid name clashes with the `Prelude`

.

import qualified Data.AMT as Vector

## Performance

The worst case running time complexities are given, with *n* referring the the number of elements in the vector.
A `Vector`

is particularly efficient for applications that require a lot of indexing and updates.
All logarithms are base 16, which means that *O(log n)* behaves like *O(1)* in practice.

## Warning

The length of a `Vector`

must not exceed

.
Violation of this condition is not detected and if the length limit is exceeded, the behaviour of the vector is undefined.`maxBound`

:: `Int`

## Implementation

The implementation of `Vector`

uses array mapped tries.

## Synopsis

- data Vector a
- empty :: Vector a
- singleton :: a -> Vector a
- fromList :: [a] -> Vector a
- fromFunction :: Int -> (Int -> a) -> Vector a
- replicate :: Int -> a -> Vector a
- replicateA :: Applicative f => Int -> f a -> f (Vector a)
- unfoldr :: (b -> Maybe (a, b)) -> b -> Vector a
- unfoldl :: (b -> Maybe (b, a)) -> b -> Vector a
- iterateN :: Int -> (a -> a) -> a -> Vector a
- (<|) :: a -> Vector a -> Vector a
- (|>) :: Vector a -> a -> Vector a
- (><) :: Vector a -> Vector a -> Vector a
- viewl :: Vector a -> Maybe (a, Vector a)
- viewr :: Vector a -> Maybe (Vector a, a)
- last :: Vector a -> Maybe a
- take :: Int -> Vector a -> Vector a
- lookup :: Int -> Vector a -> Maybe a
- index :: Int -> Vector a -> a
- (!?) :: Vector a -> Int -> Maybe a
- (!) :: Vector a -> Int -> a
- update :: Int -> a -> Vector a -> Vector a
- adjust :: Int -> (a -> a) -> Vector a -> Vector a
- map :: (a -> b) -> Vector a -> Vector b
- mapWithIndex :: (Int -> a -> b) -> Vector a -> Vector b
- traverseWithIndex :: Applicative f => (Int -> a -> f b) -> Vector a -> f (Vector b)
- indexed :: Vector a -> Vector (Int, a)
- foldMapWithIndex :: Monoid m => (Int -> a -> m) -> Vector a -> m
- foldlWithIndex :: (b -> Int -> a -> b) -> b -> Vector a -> b
- foldrWithIndex :: (Int -> a -> b -> b) -> b -> Vector a -> b
- foldlWithIndex' :: (b -> Int -> a -> b) -> b -> Vector a -> b
- foldrWithIndex' :: (Int -> a -> b -> b) -> b -> Vector a -> b
- zip :: Vector a -> Vector b -> Vector (a, b)
- zipWith :: (a -> b -> c) -> Vector a -> Vector b -> Vector c
- zip3 :: Vector a -> Vector b -> Vector c -> Vector (a, b, c)
- zipWith3 :: (a -> b -> c -> d) -> Vector a -> Vector b -> Vector c -> Vector d
- unzip :: Vector (a, b) -> (Vector a, Vector b)
- unzip3 :: Vector (a, b, c) -> (Vector a, Vector b, Vector c)
- toIndexedList :: Vector a -> [(Int, a)]

# Documentation

An array mapped trie.

## Instances

# Construction

fromFunction :: Int -> (Int -> a) -> Vector a Source #

Create a new vector of the given length from a function.

replicate :: Int -> a -> Vector a Source #

*O(n * log n)*. `replicate n x`

is a vector consisting of n copies of x.

replicateA :: Applicative f => Int -> f a -> f (Vector a) Source #

`replicateA`

is an `Applicative`

version of `replicate`

.

unfoldr :: (b -> Maybe (a, b)) -> b -> Vector a Source #

*O(n * log n)*. Build a vector from left to right by repeatedly applying a function to a seed value.

unfoldl :: (b -> Maybe (b, a)) -> b -> Vector a Source #

*O(n * log n)*. Build a vector from right to left by repeatedly applying a function to a seed value.

iterateN :: Int -> (a -> a) -> a -> Vector a Source #

Constructs a vector by repeatedly applying a function to a seed value.

(<|) :: a -> Vector a -> Vector a infixr 5 Source #

*O(n * log n)*. Add an element to the left end of the vector.

(|>) :: Vector a -> a -> Vector a infixl 5 Source #

*O(log n)*. Add an element to the right end of the vector.

# Deconstruction/Subranges

viewl :: Vector a -> Maybe (a, Vector a) Source #

*O(n * log n)*. The first element and the vector without the first element or `Nothing`

if the vector is empty.

viewr :: Vector a -> Maybe (Vector a, a) Source #

*O(log n)*. The vector without the last element and the last element or `Nothing`

if the vector is empty.

last :: Vector a -> Maybe a Source #

*O(1)*. The last element in the vector or `Nothing`

if the vector is empty.

take :: Int -> Vector a -> Vector a Source #

*O(log n)*. Take the first n elements of the vector or the vector if n is larger than the length of the vector.
Returns the empty vector if n is negative.

# Indexing

lookup :: Int -> Vector a -> Maybe a Source #

*O(log n)*. The element at the index or `Nothing`

if the index is out of range.

index :: Int -> Vector a -> a Source #

*O(log n)*. The element at the index. Calls `error`

if the index is out of range.

update :: Int -> a -> Vector a -> Vector a Source #

*O(log n)*. Update the element at the index with a new element.
Returns the original vector if the index is out of range.

adjust :: Int -> (a -> a) -> Vector a -> Vector a Source #

*O(log n)*. Adjust the element at the index by applying the function to it.
Returns the original vector if the index is out of range.

# Transformations

mapWithIndex :: (Int -> a -> b) -> Vector a -> Vector b Source #

*O(n)*. Map a function that has access to the index of an element over the vector.

traverseWithIndex :: Applicative f => (Int -> a -> f b) -> Vector a -> f (Vector b) Source #

*O(n)*. Traverse the vector with a function that has access to the index of an element.

indexed :: Vector a -> Vector (Int, a) Source #

*O(n)*. Pair each element in the vector with its index.

# Folds

foldMapWithIndex :: Monoid m => (Int -> a -> m) -> Vector a -> m Source #

*O(n)*. Fold the values in the vector, using the given monoid.

foldlWithIndex :: (b -> Int -> a -> b) -> b -> Vector a -> b Source #

*O(n)*. Fold using the given left-associative function that has access to the index of an element.

foldrWithIndex :: (Int -> a -> b -> b) -> b -> Vector a -> b Source #

*O(n)*. Fold using the given right-associative function that has access to the index of an element.

foldlWithIndex' :: (b -> Int -> a -> b) -> b -> Vector a -> b Source #

*O(n)*. A strict version of `foldlWithIndex`

.
Each application of the function is evaluated before using the result in the next application.

foldrWithIndex' :: (Int -> a -> b -> b) -> b -> Vector a -> b Source #

*O(n)*. A strict version of `foldrWithIndex`

.
Each application of the function is evaluated before using the result in the next application.

# Zipping/Unzipping

zip :: Vector a -> Vector b -> Vector (a, b) Source #

*O(n)*. Takes two vectors and returns a vector of corresponding pairs.

zipWith :: (a -> b -> c) -> Vector a -> Vector b -> Vector c Source #

*O(n)*. A generalized `zip`

zipping with a function.

zip3 :: Vector a -> Vector b -> Vector c -> Vector (a, b, c) Source #

*O(n)*. Takes three vectors and returns a vector of corresponding triples.

zipWith3 :: (a -> b -> c -> d) -> Vector a -> Vector b -> Vector c -> Vector d Source #

*O(n)*. A generalized `zip3`

zipping with a function.

unzip :: Vector (a, b) -> (Vector a, Vector b) Source #

*O(n)*. Transforms a vector of pairs into a vector of first components and a vector of second components.

unzip3 :: Vector (a, b, c) -> (Vector a, Vector b, Vector c) Source #

*O(n)*. Takes a vector of triples and returns three vectors, analogous to `unzip`

.

# To Lists

toIndexedList :: Vector a -> [(Int, a)] Source #

*O(n)*. Create a list of index-value pairs from the vector.