The persistent-vector package
This package provides persistent vectors based on array mapped tries. The implementation is based on the persistent vectors used in clojure, but in a Haskell-style API. The API is modeled after Data.Sequence from the containers library.
Technically, the element-wise operations are O(log(n)), but the underlying tree cannot be more than 7 or 8 levels deep so this is effectively constant time.
One change from the clojure implementation is that this version supports O(1) slicing, though it does cheat a little. Slices retain references to elements that cannot be indexed. These extra references (and the space they occupy) can be reclaimed by shrinking the slice. This seems like a reasonable tradeoff, and, I believe, mirrors the behavior of the vector library.
O(1) append element, indexing, updates, length, and slicing
Reasonably compact representation
[Skip to ReadMe]
|Versions||0.1.0.0, 0.1.0.1, 0.1.0.3, 0.1.1|
|Change log||None available|
|Dependencies||base (==4.*), deepseq [details]|
|Source repository||head: git clone git://github.com/travitch/persistent-vector.git|
|Uploaded||Wed Apr 22 03:37:26 UTC 2015 by TristanRavitch|
|Downloads||594 total (20 in last 30 days)|
|Status||Docs available [build log]|
Last success reported on 2015-04-22 [all 1 reports]
- persistent-vector-0.1.1.tar.gz [browse] (Cabal source package)
- Package description (included in the package)
For package maintainers and hackage trustees