persistent-vector
Version 0.1.0.3 revision 0 uploaded by TristanRavitch.
Package meta
- Synopsis
- A persistent sequence based on array mapped tries
- Description
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.
Highlights:
O(1) append element, indexing, updates, length, and slicing
Reasonably compact representation
- Author
- Tristan Ravitch
- Bug reports
- https://github.com/travitch/persistent-vector/issues
- Category
- Data
- Copyright
- n/a
- Homepage
- https://github.com/travitch/persistent-vector
- Maintainer
- tristan@nochair.net
- Package URL
- n/a
- Stability
- n/a