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.
|Versions||0.1, 0.1.1, 0.2, 0.3|
|Dependencies||array (0.3.*), base (≥3 & <5), diffarray (0.1.*)|
|Author||Chris Smith <firstname.lastname@example.org>|
|Maintainer||Chris Smith <email@example.com>|
|Upload date||Mon Jun 6 21:24:33 UTC 2011|