Safe Haskell | Safe-Inferred |
---|---|

Language | Haskell2010 |

The

type is an persistent vector of elements of type `Vector`

a`a`

.

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

Many operations have a average-case complexity of *O(log n)*. The
implementation uses a large base (i.e. 32) so in practice these
operations are constant time.

# Comparison with Data.RRBVector and Data.Sequence

- Persistent vectors generally have less operations than sequences or RRBVectors but those operations can be faster.
- Persistent vectors have the fastest indexing.
- Persistent vectors are faster than RRBVectors at snocing because of tail optimization. Snocing is a near constant time operation. Snocing is still slower than sequences.
- RRBVectors are faster than persistent vectors at splitting and merging, but still slower than sequences.
- RRBVectors are faster than Sequences at indexing but slower than persistent vectors.
- Sequences have the fastest consing, snocing, and merging, but the slowest indexing.

## Synopsis

- foldr :: (a -> b -> b) -> b -> Vector a -> b
- foldr' :: (a -> b -> b) -> b -> Vector a -> b
- foldl :: (b -> a -> b) -> b -> Vector a -> b
- foldl' :: (b -> a -> b) -> b -> Vector a -> b
- data Vector a where
- (|>) :: Vector a -> a -> Vector a
- empty :: Vector a
- length :: Vector a -> Int
- lookup :: Int -> Vector a -> Maybe a
- index :: HasCallStack => Int -> Vector a -> a
- (!?) :: Vector a -> Int -> Maybe a
- (!) :: HasCallStack => Vector a -> Int -> a
- update :: Int -> a -> Vector a -> Vector a
- adjust :: (a -> a) -> Int -> Vector a -> Vector a
- adjustF :: Applicative f => (a -> f a) -> Int -> Vector a -> f (Vector a)
- snoc :: Vector a -> a -> Vector a
- singleton :: a -> Vector a
- null :: Vector a -> Bool
- (//) :: Vector a -> [(Int, a)] -> Vector a
- (><) :: Vector a -> Vector a -> Vector a
- map :: (a -> b) -> Vector a -> Vector b
- traverse :: Applicative f => (a -> f b) -> Vector a -> f (Vector b)
- toList :: Vector a -> [a]
- fromList :: [a] -> Vector a
- unsnoc :: Vector a -> Maybe (Vector a, a)

# Documentation

A vector.

The instances are based on those of `Seq`

s, which are in turn based on those of lists.

pattern (:|>) :: Vector a -> a -> Vector a infixl 5 | \(O(\log n)\). A bidirectional pattern synonym viewing the rear of a non-empty sequence. |

pattern Empty :: Vector a | \(O(1)\). A bidirectional pattern synonym matching an empty sequence. |

#### Instances

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

\(O(\log n)\). An alias for `snoc`

Mnemonic: a triangle with the single element at the pointy end.

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 :: HasCallStack => 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)\). Replace the element at the specified position. If the position is out of range, the original sequence is returned.

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

\(O(\log n)\). Adjust the element at the index by applying the function to it. If the index is out of range, the original vector is returned.

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

\(O(\log n)\). Same as `adjust`

but can have effects through `Applicative`

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

\(O(n)\). For each pair `(i,a)`

from the vector of index/value pairs,
replace the vector element at position `i`

by `a`

.

update <5,9,2,7> <(2,1),(0,3),(2,8)> = <3,9,8,7>