persistent-equivalence: Persistent equivalence relations (aka union-find)

[ bsd3, data, library ] [ Propose Tags ]

This is a 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.3 contains some performance improvements for concurrent applications, and removes the repr function, which was poorly defined and had no good uses.

Modules

[Index]

Downloads

Maintainer's Corner

Package maintainers

For package maintainers and hackage trustees

Candidates

  • No Candidates
Versions [RSS] 0.1, 0.1.1, 0.2, 0.3
Dependencies array (>=0.3 && <0.4), base (>=3 && <5), diffarray (>=0.1 && <0.2) [details]
License BSD-3-Clause
Author Chris Smith <cdsmith@gmail.com>
Maintainer Chris Smith <cdsmith@gmail.com>
Category Data
Uploaded by ChrisSmith at 2011-10-01T05:17:52Z
Distributions
Reverse Dependencies 1 direct, 0 indirect [details]
Downloads 3106 total (14 in the last 30 days)
Rating (no votes yet) [estimated by Bayesian average]
Your Rating
  • λ
  • λ
  • λ
Status Docs uploaded by user
Build status unknown [no reports yet]