The persistent-vector package

[Tags: bsd3, library]

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:


[Skip to ReadMe]

Properties

Versions0.1.0.0, 0.1.0.1, 0.1.0.3, 0.1.1
Change logNone available
Dependenciesbase (==4.*), deepseq [details]
LicenseBSD3
AuthorTristan Ravitch
Maintainertristan@nochair.net
CategoryData
Home pagehttps://github.com/travitch/persistent-vector
Bug trackerhttps://github.com/travitch/persistent-vector/issues
Source repositoryhead: git clone git://github.com/travitch/persistent-vector.git
UploadedWed Apr 22 03:37:26 UTC 2015 by TristanRavitch
DistributionsNixOS:0.1.1
Downloads456 total (28 in last 30 days)
Votes
0 []
StatusDocs available [build log]
Last success reported on 2015-04-22 [all 1 reports]

Modules

[Index]

Downloads

Maintainers' corner

For package maintainers and hackage trustees

Readme for persistent-vector-0.1.1

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:

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