Data.UnionFind

A persistent union-find (disjoint-set) over an ordered key type.

A set is named by its canonical root, and uf_union always keeps the smaller key (by Ord) as the root, so a set’s representative is a pure function of its members, never of the order unions ran in. There is no path compression (that needs mutation); uf_find walks parent links to the root on each call. A key absent from the map is its own singleton root, so uf_empty needs no pre-population. The occurs check an HM unifier layers on top is type-specific and lives with the unifier, not here. Opt-in: not in Base.

Types

UnionFind

newtype UnionFind(k) = UnionFind(Map(k, k))

A forest of parent links. The wrapper is opaque so callers cannot create cycles or install a non-canonical parent; only uf_union can add links.

Functions and Values

uf_empty

uf_empty : forall a. Data.UnionFind.UnionFind(a)

The empty forest: every key is its own singleton root.

uf_find

uf_find : forall a. (Data.UnionFind.UnionFind(a), a) -> a given Ord(a)

The canonical root of x’s set.

uf_find(uf_union(uf_union(uf_empty, 3, 2), 2, 1), 3)

1

uf_union

uf_union : forall a. (Data.UnionFind.UnionFind(a), a, a) -> Data.UnionFind.UnionFind(a) given Ord(a)

Merge the sets of x and y, keeping the smaller root; a no-op when they are already joined.

uf_equiv(uf_union(uf_union(uf_empty, 1, 2), 2, 3), 1, 3)

true

uf_equiv

uf_equiv : forall a. (Data.UnionFind.UnionFind(a), a, a) -> Bool given Ord(a)

True when x and y belong to the same set.