Parameter Make.Relation

include Union_Find.Parameters.GENERIC_MONOID

type ('a, 'b) t

The type of elements of the monoid. Since these are used to represent relation between our generic union-find elements GENERIC_ELT.t, they have two type parameters, so an ('a, 'b) t represents a relation between 'a GENERIC_ELT.t and 'b GENERIC_ELT.t

val equal : ('a, 'b) t -> ('a, 'b) t -> bool

Equality of relations

val pretty : Stdlib.Format.formatter -> ('a, 'b) t -> unit

Pretty printer for relations

val pretty_with_terms : (Stdlib.Format.formatter -> 'tl -> unit) -> 'tl -> (Stdlib.Format.formatter -> 'tr -> unit) -> 'tr -> Stdlib.Format.formatter -> ('a, 'b) t -> unit

pretty_with_terms pp_x x pp_y y rel pretty-prints the relation rel between terms x and y (respectively printed with pp_x and pp_y).

For placeholder variables, use pretty

val identity : ('a, 'a) t

The identity relation

val compose : ('b, 'c) t -> ('a, 'b) t -> ('a, 'c) t

Monoid composition, written using the functional convention compose f g is f \circ g. Should be associative, and compatible with identity:

• For all x, G.compose x G.identity = G.compose G.identity x = x
• For all x y z, G.compose x (G.compose y z) = G.compose (G.compose x y) z

val inverse : ('a, 'b) t -> ('b, 'a) t

Group inversion, should verify for all x: G.compose x (G.inverse x) = G.compose (G.inverse x) x = G.identity