Data.Vector.Persistent

This is a port of the persistent vector from clojure to Haskell. It is spine-strict and lazy in the elements.

The implementation is based on array mapped tries. The complexity bounds given are mostly O(1), but only if you are willing to accept that the tree cannot have height greater than 7 on 32 bit systems and maybe 8 on 64 bit systems.

Documentation

data Vector a

Persistent vectors based on array mapped tries

Instances

Functor Vector

Foldable Vector

Traversable Vector

Eq a => Eq (Vector a)

Ord a => Ord (Vector a)

Show a => Show (Vector a)

Monoid (Vector a)

NFData a => NFData (Vector a)

Construction

empty :: Vector a

O(1) The empty vector

singleton :: a -> Vector a

O(1) Construct a vector with a single element.

snoc :: Vector a -> a -> Vector a

O(1) Append an element to the end of the vector.

fromList :: [a] -> Vector a

O(n) Construct a vector from a list.

Queries

null :: Vector a -> Bool

O(1) Test to see if the vector is empty.

length :: Vector a -> Int

O(1) Get the length of the vector.

Indexing

index :: Vector a -> Int -> Maybe a

O(1) Bounds-checked indexing into a vector.

unsafeIndex :: Vector a -> Int -> a

O(1) Unchecked indexing into a vector.

Note that out-of-bounds indexing might not even crash - it will usually just return nonsense values.

take :: Int -> Vector a -> Vector a

O(1) Take the first i elements of the vector.

Note that this is just a wrapper around slice and the resulting slice retains references that are inaccessible. Use shrink if this is undesirable.

drop :: Int -> Vector a -> Vector a

O(1) Drop i elements from the front of the vector.

Note that this is just a wrapper around slice.

splitAt :: Int -> Vector a -> (Vector a, Vector a)

O(1) Split the vector at the given position.

Slicing

slice :: Int -> Int -> Vector a -> Vector a

O(1) Return a slice of v of length length starting at index start. The returned vector may have fewer than length elements if the bounds are off on either side (the start is negative or length takes it past the end).

A slice of negative or zero length is the empty vector.

 slice start length v

Note that a slice retains all of the references that the vector it is derived from has. They are not reachable via any traversals and are not counted towards its size, but this may lead to references living longer than intended. If is important to you that this not happen, call shrink on the return value of slice to drop unused space and references.

shrink :: Vector a -> Vector a

O(n) Force a sliced vector to drop any unneeded space and references.

This is a no-op for an un-sliced vector.

Modification

update :: Int -> a -> Vector a -> Vector a

O(1) Update a single element at ix with new value elt in v.

 update ix elt v

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

O(n) Bulk update.

 v // updates

For each (index, element) pair in updates, modify v such that the indexth position of v is element. Indices in updates that are not in v are ignored

Folds

foldr :: (a -> b -> b) -> b -> Vector a -> b

O(n) Right fold over the vector

foldl' :: (b -> a -> b) -> b -> Vector a -> b

O(n) Strict left fold over the vector

Transformations

map :: (a -> b) -> Vector a -> Vector b

O(n) Map over the vector

reverse :: Vector a -> Vector a

O(n) Reverse a vector

Searches

filter :: (a -> Bool) -> Vector a -> Vector a

O(n) Filter according to the predicate

partition :: (a -> Bool) -> Vector a -> (Vector a, Vector a)

O(n) Return the elements that do and do not obey the predicate