Module Union_Find_Lattice.Sig

The common signatures of union-finds. Each implementation should have the same interface, among one of those below.

Union-find lattice signatures

module type UNION_FIND_LATTICE = sig ... end

The simplest union-find lattice.

module type VALUED_UNION_FIND_LATTICE = sig ... end

Extend UNION_FIND_LATTICE with values attached to each equivalence class.

module type LABELED_UNION_FIND_LATTICE = sig ... end

Signature for a labeled union-find lattice. Its parent edges are annotated by relations, which form a Group.

module type LABELED_VALUED_UNION_FIND_LATTICE = sig ... end

Extension of LABELED_UNION_FIND_LATTICE which can store an optional value on each relational class.

module type POLYMORPHIC_LABELED_UNION_FIND_LATTICE = sig ... end

Polymorphic version of LABELED_UNION_FIND_LATTICE, here the type of nodes has a parameter: 'a node and the type of relations has two: ('a,'b) relation. This allows type-checking of relation composition/inversion, at the cost of using GADTs and existential types.

Extension of POLYMORPHIC_LABELED_UNION_FIND_LATTICE which can store an optional 'a value on each relational class.