Module Bigraph.Fun

Implementation of finite functions over integers.

type t

Type of finite functions over integers.

val pp : Ppx_deriving_runtime.Format.formatter -> t -> Ppx_deriving_runtime.unit
val show : t -> Ppx_deriving_runtime.string
val to_yojson : t -> Yojson.Safe.t
val of_yojson : Yojson.Safe.t -> t Ppx_deriving_yojson_runtime.error_or

Standard map operations

These follow the standard Map module conventions.

val add : int -> int -> t -> t

add i j f adds a new pair (i, j) to function f. Both i and j must be non negative.

val compare : t -> t -> int
val empty : t
val equal : t -> t -> bool
val fold : (int -> int -> 'b -> 'b) -> t -> 'b -> 'b
val iter : (int -> int -> unit) -> t -> unit

Additional functions

val dom : t -> IntSet.t

Return the domain of a function.

val codom : t -> IntSet.t

Return the codomain of a function.

val inverse : t -> Rel.t

Return the inverse of a function. Note that the inverse of a function is, in the general case, a binary relation.

val to_list : t -> (int * int) list

Return the list of pairs defined by a function.

val of_list : (int * int) list -> t

Inverse of Fun.to_list. Note that in case of clashing pairs only the right-most is used.

val parse : int list -> t

parse l returns a function in which the numbers from 0 to n - 1 (with n the length of l) are mapped to the elements of l, in the given order. Example:

parse [0; 0; 3; 1; 2] = [(0, 0); (1, 0); (2, 3); (3, 1); (4, 2)].

val apply : t -> int -> int option

apply f x returns f x.

val transform : iso_dom:Iso.t -> iso_codom:Iso.t -> t -> t

transform ~iso_dom ~iso_codom f returns the function obtained by applying iso_dom and iso_codom to the domain and codomain of f, respectively.

val is_total : int -> t -> bool

is_total n f returns true if function f is total over domain 0, ..., n - 1, false otherwise. n must be non negative.

val is_surj : int -> t -> bool

is_surj n f returns true if function f is surjective over codomain 0, ..., n - 1, false otherwise. n must be non negative.

val is_id : t -> bool

is_id f returns true if f i = i for each i, false otherwise.

val check_codom : int -> t -> bool

check_codom n f returns true if the codomain of f is in the range [0, n - 1]. n must be non negative.