[Haskell-cafe] ANNOUNCE: persistent-vector-

Tristan Ravitch travitch at cs.wisc.edu
Wed Aug 29 18:46:21 CEST 2012

I uploaded a package implementing persistent vectors using array
mapped tries (based on the implementation in clojure).  Version was broken, so I am starting off with


Persistent vectors are a sequence container offering efficient and
purely functional append (snoc), indexing, and updates.  This is
similar to Data.Sequence from containers.  The array mapped trie
is closely related to the data structure used in the
unordered-containers package.

Comparison to Sequence:

 * Faster indexing and append

 * Slightly slower updates to existing elements

 * O(1) slicing

 * Sequence offers efficient prepend and concatenate
   (persistent-vector does not implement prepend, while concatenate is

I tried to model the API after Sequence as much as was reasonable, but
a few functions are still missing.  Some are reasonable to implement
and some would be difficult to make efficient.  The results from
criterion (mostly comparing against Sequence and IntMap) are posted


The *Vec* runs are the vectors from this package and IM and Seq are
IntMap and Sequence from containers.

Hopefully someone will find this useful.  Comments and suggestions are
definitely welcome for anything: API, implementation, test suite, or
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: not available
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20120829/5e1a6182/attachment.pgp>

More information about the Haskell-Cafe mailing list