Module Union_Find.FunctionalSource

Functional Union Find structures. These are immutable and can grow or shrink (add/remove equalities). Represented with PatriciaTree (binary tree maps) and eager compression.

However, their performance isn't as good as imperative union-find's:

• Imperative UF uses union-by-size and path compression, so the amortized complexity of its operations is O(inv_ackermann(n)) (also known as O(1) for any n that can be physically represented).
• Functional UF performs eager compression, and maintains a set of back pointers (from representative to class elements), so its complexities are:
• find is O(log n) (single map lookup)
• union is O(c + log(n)) where c is the max of cardinals of the class being united.