Safe Haskell | Safe-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
- 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)
Documentation
Persistent vectors based on array mapped tries
Construction
Queries
Indexing
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.
Slicing
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.
Modification
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 index
th position of v
is element
.
Indices in updates
that are not in v
are ignored