Module UnionFindSource

This module offers a union-find data structure based on disjoint set forests, with path compression and linking by rank.

A type of elements, also known as references.

Operations for creating a new reference, reading and writing a reference, and testing whether two references are equivalent. (Two references are considered equivalent after they have been merged by union.)

union x y does nothing if the references x and y are equal, and merges them if they are distinct. In the latter case, the content of the merged reference is arbitrarily chosen to be the previous content of x or y.

find x returns the representative element of x's equivalence class.

Instead of hard-coding the use of mutable state, we parameterize the module over an implementation S of stores, as described by the signature STORE. This allows the client to choose between many different representations of the store: e.g., based on primitive references, based on a (possibly extensible) primitive array, based on a persistent map, based on a persistent or semi-persistent array, based on transactional references, etc.

The signature provided by this module is also STORE, extended with an operation for merging two references.