@hackage persistent-equivalence0.1

Persistent equivalence relations (aka union-find)

  • Categories

    • License

      BSD-3-Clause

    • Maintainer

      Chris Smith <cdsmith@gmail.com>

    • Links

    • Versions

      • 0.3 Sat, 1 Oct 2011
      • 0.2 Wed, 8 Jun 2011
      • 0.1.1 Tue, 7 Jun 2011
      • 0.1 Mon, 6 Jun 2011

    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.