Implementations of the union-find data structure


  • Strengthen the specification of merge. It is now guaranteed that,
    if the user function f raises an exception, then the union-find
    data structure is unaffected.


  • In UnionFind and UnionFind.Make, introduce a new operation merge,
    a variant of union that is parameterized with a join function f.
    The function f is not allowed to perform reentrant accesses to the
    union-find data structure.

  • In UnionFind only, introduce an optimization that reduces the amount
    of memory allocation. This leads to a speed improvement of about 10%
    in the micro-benchmark.


  • Incompatible changes in the signature STORE, which appears in the type of
    the functor UnionFind.Make.

    • Instead of having every operation return a possibly-updated store, we
      assume that stores are updated in place. A new copy operation is
      introduced, so a persistent store is now simulated by a mutable store that
      can be copied in constant time. The main motivation for this change is
      that it makes UnionFind.Make much more pleasant to use in practice.

    • The operation union is no longer parameterized with a join function f.
      This API was flawed and could lead to meaningless behavior if the function
      f provided by the user performed reentrant calls to the union-find

    • The operation union now returns a reference of type 'a rref instead
      of a unit value. This makes UnionFind.Make analogous to UnionFind,
      which it was not.

  • Expose find among the operations offered by UnionFind.Make.

  • Add is_representative to the operations offered by UnionFind
    and by UnionFind.Make.

  • Add a micro-benchmark, which is executed by make test.


  • Improved documentation.


  • Add a fast path (an optimization) in the find and eq functions, both in
    the basic union-find (UnionFind) and the one that is parameterized over a
    store (UnionFind.Make).


  • Initial release of the package.