The persistent-equivalence package
This is a semi-persistent data structure for equivalence relations (known in the imperative world as union-find or disjoint set union). It exhibits optimal performance when used in a linear pattern, but degrades when other access patterns are used.
The basic idea is as given by Conchon and Filliatre in their 2007 paper A persistent union-find data structure. Unlike the implementation given in the paper, this version is safe with multiple threads, but does not optimize for backtracking.
Properties
| Versions | 0.1, 0.1.1, 0.2, 0.3 |
|---|---|
| Dependencies | array (0.3.*), base (≥3 & <5), diffarray (0.1.*) |
| License | BSD3 |
| Author | Chris Smith <cdsmith@gmail.com> |
| Maintainer | Chris Smith <cdsmith@gmail.com> |
| Category | Data |
| Upload date | Mon Jun 6 21:24:33 UTC 2011 |
| Uploaded by | ChrisSmith |
| Built on | ghc-7.0 |
Modules
- Data
- Equivalence
Downloads
- persistent-equivalence-0.1.tar.gz (Cabal source package)
- package description (included in the package)