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

Versions 0.1, 0.1.1, 0.2, 0.3
Dependencies array (==0.3.*), base (>=3 && <5), diffarray (==0.1.*) [details]
License BSD3
Author Chris Smith <cdsmith@gmail.com>
Maintainer Chris Smith <cdsmith@gmail.com>
Stability Unknown
Category Data
Uploaded Mon Jun 6 21:24:33 UTC 2011 by ChrisSmith
Distributions NixOS:0.3
Downloads 798 total (21 in the last 30 days)
Votes
0 []
Status Docs uploaded by user
Build status unknown [no reports yet]

Modules

[Index]

Downloads

Maintainer's Corner

For package maintainers and hackage trustees