persistent-vector: A persistent sequence based on array mapped tries
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 shrink
ing 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
[Skip to Readme]
Downloads
- persistent-vector-0.2.0.tar.gz [browse] (Cabal source package)
- Package description (as included in the package)
Maintainer's Corner
For package maintainers and hackage trustees
Candidates
Versions [RSS] | 0.1.0.0, 0.1.0.1, 0.1.0.3, 0.1.1, 0.2.0 |
---|---|
Change log | ChangeLog.md |
Dependencies | base (>=4 && <5), deepseq (>=1 && <1.5), semigroups (>=0.18 && <0.19), transformers (>=0.3 && <0.6) [details] |
License | BSD-3-Clause |
Author | Tristan Ravitch |
Maintainer | tristan@ravit.ch |
Category | Data |
Home page | https://github.com/travitch/persistent-vector |
Bug tracker | https://github.com/travitch/persistent-vector/issues |
Source repo | head: git clone git://github.com/travitch/persistent-vector.git |
Uploaded | by TristanRavitch at 2020-10-29T06:21:47Z |
Distributions | |
Reverse Dependencies | 3 direct, 47 indirect [details] |
Downloads | 3533 total (24 in the last 30 days) |
Rating | 2.0 (votes: 1) [estimated by Bayesian average] |
Your Rating | |
Status | Docs available [build log] Last success reported on 2020-10-29 [all 1 reports] |