package term-indexing

  1. Overview
  2. Docs

Substitutions.

type term = Term.t

The type of terms

type var := int
type t

The type of substitutions

val of_seq : (var * term) Seq.t -> t
val to_seq : t -> (var * term) Seq.t
val to_seq_keys : t -> var Seq.t
val pp : Format.formatter -> t -> unit
val empty : unit -> t

empty () is the empty substitution.

val is_empty : t -> bool

is_empty subst checks whether equal subst empty

val equal : t -> t -> bool
val ub : t -> Int_option.t

ub subst is an upper bound on the absolute value of variables appearing in subst (either in the domain or the range of the substitution).

val eval : var -> t -> term option

eval v subst returns Some t if v is mapped to the term t in subst or None if v is not in the domain of subst.

val eval_exn : var -> t -> term

Exception-raising variant of eval. Raises Not_found if v is not in the domain of subst.

val add : var -> term -> t -> t

add v t subst adds a mapping from v to t in subst. If v is already in the domain of subst, the previous mapping is replaced.

Raises Invalid_argument if t is a variable equal to v

val unsafe_add : var -> term -> t -> t

unsafe_add does as add but doen't check for validity of the mapping.

val lift : t -> term -> term

lift subst term applies the substitution subst to term. Note that lift does not perform an occur check: do not use with substitutions that are not well-founded.

val union : t -> t -> t

union s1 s2 computes the union of s1 and s2.

Raises Invalid_argument if s1 and s2 have overlapping domains.

module Unification : sig ... end

Unification contains facilities to perform first-order term unification

OCaml

Innovation. Community. Security.