Module `Union_Find.Functional`

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.

module GenericRelationalValued
  (Elt : Parameters.GENERIC_ELT)
  (Relation : Parameters.GENERIC_GROUP)
  (Value : 
    Parameters.GENERIC_VALUE with type ('a, 'b) relation = ('a, 'b) Relation.t) : 
  sig ... end

Functional union find

Module Union_Find.Functional

Module `Union_Find.Functional`