# Persistent Vector

A library providing persistent (purely functional) vectors for Haskell
based on array mapped tries.

## Description

These persistent vectors are modeled on the persistent vector used by
clojure, with an API modeled after Data.Sequence from the containers
library.  This data structure is *spine strict* and is not useful for
incremental consumption.  If you need that, stick to lists.  It is
still lazy in the elements.

While per-element operations are O(log(n)), the internal tree can
never be more than 7 or 8 deep.  Thus, they are effectively constant
time.

This implementation adds O(1) slicing support for vectors that I do
not believe clojure supports.  The implementation cheats, though, and
slices can retain references to objects that cannot be indexed.

## Performance

Performance is an important consideration for a data structure like
this.  The package contains a criterion benchmark suite that attempts
to compare the performance of persistent vectors against a variety of
existing persistent data structures.  As an overview of the results I
have observed:

 * Traversing and building lists is faster than the same operations
   with persistent vectors.

 * (Strict) left folds over persistent vectors are faster than left
   folds over Sequences.  Right folds over Sequences are faster than
   right folds over vectors.

 * Indexing persistent vectors is faster than indexing sequences and
   IntMaps (and, of course, lists).

 * Appending to vectors is slightly faster than appending to a Sequence.
   It is much faster than appending to an IntMap.

 * Updating an element at an index in a vector is *slower* than
   updating an index in a Sequence (but still faster than an IntMap).

Overall, it seems like persistent vectors are efficient at most tasks.
If you only need a (strict) left fold, they are efficient for
traversal.  Indexing and construction are very fast, but Sequences are
superior for element-wise updates.

## Implementation

## TODO

 * More of the Data.Sequence API

 * More efficient Eq and Ord instances.  This is tricky in the
   presence of slicing.  There are faster implementations for unsliced
   inputs.

 * Implement something to make parallel reductions simple (maybe
   something like vector-strategies)

 * Implement cons.  Cons can use the space that is hidden by the
   offset cheaply.  It can also make a variant of pushTail
   (pushHead) that allocates fragments of preceeding sub-trees.
   Each cons call will modify the offset of its result vector.