persistent-vector- A persistent sequence based on array mapped tries

Safe HaskellSafe-Infered




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.



data Vector a Source

Persistent vectors based on array mapped tries



empty :: Vector aSource

O(1) The empty vector

singleton :: a -> Vector aSource

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

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

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

fromList :: [a] -> Vector aSource

O(n) Construct a vector from a list.


null :: Vector a -> BoolSource

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

length :: Vector a -> IntSource

O(1) Get the length of the vector.


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

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

unsafeIndex :: Vector a -> Int -> aSource

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 aSource

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 aSource

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)Source

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


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

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 aSource

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

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


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

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

 update ix elt v

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

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


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

O(n) Right fold over the vector

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

O(n) Strict left fold over the vector


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

O(n) Map over the vector

reverse :: Vector a -> Vector aSource

O(n) Reverse a vector


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

O(n) Filter according to the predicate

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

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