persistent-equivalence: Persistent equivalence relations (aka union-find)
|Versions||0.1, 0.1.1, 0.2, 0.3|
|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||by ChrisSmith at Mon Jun 6 21:24:33 UTC 2011|
|Downloads||1442 total (12 in the last 30 days)|
|Rating||(no votes yet) [estimated by rule of succession]|
|Status||Docs uploaded by user
Build status unknown [no reports yet]
Hackage Matrix CI
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.
For package maintainers and hackage trustees