The Union-Find Data Structure in Several Guises

The OCaml library unionFind offers two implementations of the union-find data structure. Both implementations are based on disjoint sets forests, with path compression and linking-by-rank, so as to guarantee good asymptotic complexity: every operation requires a quasi-constant number of accesses to the store.

Over Primitive Mutable State

The first implementation uses heap-allocated mutable state. It is provided by the type elem and the operations make, get, set, eq, union, find in the module UnionFind.

Over a User-Provided Store

The second implementation is parameterized over an implementation of stores. Its operations explicitly take a store as a parameter, and update it in place. It is provided by the functor UnionFind.Make. This functor is parameterized over an implementation of stores, described by the signature UnionFind.STORE. Its result signature is also UnionFind.STORE, extended with a union operation that merges two references.


The functor UnionFind.Make can be applied to many different implementations of stores, such as persistent stores, mutable stores backed by mutable arrays, and more. The following modules provide several different implementations of stores.