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.
Version 0.2 removes unnecessary atomic operations when doing updates that are never semantically meaningful, hopefully leading to better scalability in a parallel setting.
|Versions||0.1, 0.1.1, 0.2, 0.3|
|Change log||None available|
|Dependencies||array (==0.3.*), base (>=3 && <5), diffarray (==0.1.*) [details]|
|Author||Chris Smith <email@example.com>|
|Maintainer||Chris Smith <firstname.lastname@example.org>|
|Uploaded||Wed Jun 8 16:17:41 UTC 2011 by ChrisSmith|
|Downloads||759 total (9 in last 30 days)|
|Status||Docs uploaded by user|
Build status unknown [no reports yet]
- persistent-equivalence-0.2.tar.gz [browse] (Cabal source package)
- Package description (included in the package)
For package maintainers and hackage trustees