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
- empty :: Vector a
- singleton :: a -> Vector a
- snoc :: Vector a -> a -> Vector a
- fromList :: [a] -> Vector a
- null :: Vector a -> Bool
- length :: Vector a -> Int
- index :: Vector a -> Int -> Maybe a
- unsafeIndex :: Vector a -> Int -> a
- take :: Int -> Vector a -> Vector a
- drop :: Int -> Vector a -> Vector a
- splitAt :: Int -> Vector a -> (Vector a, Vector a)
- slice :: Int -> Int -> Vector a -> Vector a
- shrink :: Vector a -> Vector a
- update :: Int -> a -> Vector a -> Vector a
- (//) :: Vector a -> [(Int, a)] -> Vector a
- foldr :: (a -> b -> b) -> b -> Vector a -> b
- foldl' :: (b -> a -> b) -> b -> Vector a -> b
- map :: (a -> b) -> Vector a -> Vector b
- reverse :: Vector a -> Vector a
- filter :: (a -> Bool) -> Vector a -> Vector a
- partition :: (a -> Bool) -> Vector a -> (Vector a, Vector a)
Persistent vectors based on array mapped tries
O(1) Unchecked indexing into a vector.
Note that out-of-bounds indexing might not even crash - it will usually just return nonsense values.
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
this is undesirable.
i elements from the front of the vector.
Note that this is just a wrapper around slice.
O(1) Split the vector at the given position.
O(1) Return a slice of
v of length
length starting at index
start. The returned vector may have fewer than
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
shrink on the return value of
slice to drop unused
space and references.
O(n) Force a sliced vector to drop any unneeded space and references.
This is a no-op for an un-sliced vector.
O(1) Update a single element at
ix with new value
update ix elt v
O(n) Bulk update.
v // updates
For each (index, element) pair in
v such that
indexth position of
updates that are not in
v are ignored