Module Union_Find.Parameters

Common module types for Imperative and Functional parameters. Defines the types of the functor parameters.

Some vocabulary conventions:

  • An elt or element is the type of elements of the union-find. Here it is a generic type 'a GENERIC_ELT.t (often a GADT/a type where 'a is phantom)
  • A node is an element plus its parent pointers.
  • A relation is a type ('a,'b) GENERIC_GROUP.t modeling mathematical relation between elements. The set of relations has a monoid or group structure. Classical union-find only has a single relation: type ('a, 'b) t = Equiv : ('a,'a) t)
  • A value is a type 'a GENERIC_VALUE.t of values associated with each class (or more precisely, to the representative element of each class). Values and relations interact via a group action GENERIC_VALUE.apply.

Elements

module type SIMPLE_GENERIC_ELT = sig ... end

A type for generic elements stored in our Imperative union-find structures.

module type GENERIC_ELT = sig ... end

A type for generic elements stored in our Functional union-find structures. This should be a super-type of PatriciaTree.HETEROGENEOUS_KEY.

Relations

Relations between elements. Classical union find has a single equivalence relation, which can be mimicked with type ('a, 'b) t = Equiv : ('a,'a) t) However, we can have more complex relation (any group structure) fairly easily

module type GENERIC_MONOID = sig ... end

A (possibly non-commutative) monoid structure, used to represent relations.

module type GENERIC_GROUP = sig ... end

A (possibly non-commutative) group structure, used to represent relations.

Values

Values associated with each class. Values and relation interact via a group action apply

module type SIMPLE_GENERIC_VALUE = sig ... end

The values associated with each equivalence class in the imperative union-find

module type GENERIC_VALUE = sig ... end

The values associated with each equivalence class in the functional union-find

Imperative nodes

Node representative for imperative union-find. Nodes contain both the elements in the union find and the parent pointer. Nodes can be built on top of an element type (see Imperative.MakeNode and its variants). However, it is sometimes better to define the type of elements that contains the pointer (avoids having to keep track of two types: the uf-node and the element, as going back and forth can be costly).

module type UF_NODE = sig ... end

Simple union-find node, without values

module type UF_NODE_WITH_VALUE = sig ... end

union-find node with values