The persistent-equivalence package

[Tags: bsd3, library]

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

Versions0.1, 0.1.1, 0.2, 0.3
Dependenciesarray (==0.3.*), base (>=3 && <5), diffarray (==0.1.*)
LicenseBSD3
AuthorChris Smith <cdsmith@gmail.com>
MaintainerChris Smith <cdsmith@gmail.com>
CategoryData
Upload dateMon Jun 6 21:24:33 UTC 2011
Uploaded byChrisSmith
Downloads341 total (41 in last 30 days)

Modules

[Index]

Downloads

Maintainers' corner

For package maintainers and hackage trustees