Persistent vectors based on array mapped tries

\( O(1) \) The empty vector.

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

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

\( O(n) \) Construct a vector from a list

\( O(m) \) Append two Vector instances

append v1 v2

This operation is linear in the length of v2 (where length v1 == n and length v2 == m).

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

\( O(1) \) Get the length of the vector.

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

\( O(1) \) Unchecked indexing into a vector.

Out-of-bounds indexing might not even crash—it will usually just return nonsense values.

Note: the actual lookup is not performed until the result is forced. This can cause a memory leak if the result of indexing is stored, unforced, after the rest of the vector becomes garbage. To avoid this, use unsafeIndexA or unsafeIndex# instead.

\( O(1) \) Unchecked indexing into a vector in the context of an arbitrary Applicative functor. If the Applicative is "strict" (such as IO, (strict) ST s, (strict) StateT, or Maybe, but not Identity, ReaderT, etc.), then the lookup is performed before the next action. This avoids space leaks that can result from lazy uses of unsafeIndex. See the documentation for unsafeIndex# for a custom Applicative that can be especially useful in conjunction with this function.

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

\( O(1) \) Unchecked indexing into a vector.

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

This function exists mostly because there is not, as yet, a well-known, canonical, and convenient lifted unary tuple. So we instead offer an eager indexing function returning an unlifted unary tuple. Users who prefer to avoid such "low-level" features can do something like this:

data Solo a = Solo a deriving Functor
instance Applicative Solo where
  pure = Solo
  liftA2 f (Solo a) (Solo b) = Solo (f a b)

Now

unsafeIndexA :: Vector a -> Int -> Solo a

\( O(n) \) Take n elements starting from the start of the Vector

\( O(n) \) Drop n elements starting from the start of the Vector

\( O(n) \) Split the vector into two at the given index

Note that this function strictly computes both result vectors (once the tuple itself is reduced to whnf)

\( O(n) \) 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

\( O(1) \) Drop any unused space in the vector

NOTE: This is currently the identity

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

update ix elt v

\( 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. The updates are applied in order, so the last one at each index takes effegct.

\( O(n) \) Right fold over the vector

\( O(n) \) Strict right fold over the vector.

Note: Strict in the initial accumulator value.

\( O(n) \) Left fold over the vector.

\( O(n) \) Strict left fold over the vector.

Note: Strict in the initial accumulator value.

\( O(n) \) Map over the vector

\( O(n) \) Reverse a vector

\( O(n) \) Apply a predicate p to the vector, returning the longest prefix of elements that satisfy p.

\( O(n) \) Returns the longest suffix after takeWhile p v.

\( O(n) \) Filter according to the predicate.

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