Safe Haskell | None |
---|---|

Language | Haskell2010 |

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)
- takeWhile :: (a -> Bool) -> Vector a -> Vector a
- dropWhile :: (a -> Bool) -> Vector a -> Vector a

# Documentation

Persistent vectors based on array mapped tries

# Construction

# Queries

# Indexing

unsafeIndex :: Vector a -> Int -> a Source

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 Source

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 Source

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

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 Source

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 Source

O(1) Update a single element at `ix`

with new value `elt`

in
`v`

.

update ix elt v

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

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

# Folds

# Transformations

# Searches

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

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