Struct FpCategory

pub struct FpCategory<V, E, S = RandomState> { /* private fields */ }

A finitely presented category backed by an e-graph.

A data structure for a f.p. category in which the congruence relation generated by the path equations is maintained by an e-graph. The question of whether paths in the presented category are equivalent is referred to the e-graph.

Interior mutability

Checking equivalence of paths requires mutating the underlying e-graph. However, we do not want to regard this check as mutating, for the theoretical reason that the check does not change the category presented and the practical reason that it would cause mutable references to be aggressively propagated throughout the codebase. Thus, we use the interior mutability pattern to encapsulate the mutability of the e-graph and perform borrow checking at runtime. The current implementation allows only single-threaded usage.

Implementations

impl<V, E, S> FpCategory<V, E, S>

where S: Default,

pub fn new() -> Self

Creates a default value for this type.

impl<V, E, S> FpCategory<V, E, S>

where V: Eq + Clone + Hash, E: Eq + Clone + Hash, S: BuildHasher,

pub fn generators(&self) -> &(impl FinGraph<V = V, E = E> + use<V, E, S>)

Gets the generating graph of the category presentation.

pub fn equations(&self) -> impl Iterator<Item = &PathEq<V, E>>

Gets the path equations of the category presentation.

pub fn is_free(&self) -> bool

Is the category freely generated?

pub fn add_ob_generator(&mut self, v: V)

Adds an object generator.

pub fn add_ob_generators(&mut self, iter: impl IntoIterator<Item = V>)

Adds several object generators at once.

pub fn add_mor_generator(&mut self, e: E, dom: V, cod: V)

Adds a morphism generator.

pub fn make_mor_generator(&mut self, e: E)

Adds a morphism generator without declaring its (co)domain.

pub fn get_dom(&self, e: &E) -> Option<&V>

Gets the domain of a morphism generator.

pub fn get_cod(&self, e: &E) -> Option<&V>

Gets the codomain of a morphism generator.

pub fn set_dom(&mut self, e: E, v: V)

Sets the domain of a morphism generator.

pub fn set_cod(&mut self, e: E, v: V)

Sets the codomain of a morphism generator.

pub fn add_equation(&mut self, eq: PathEq<V, E>)

Adds a path equation to the presentation.

pub fn equate(&mut self, lhs: Path<V, E>, rhs: Path<V, E>)

Equates two path in the presentation.

pub fn iter_invalid(&self) -> impl Iterator<Item = InvalidFpCategory<E>> + '_

Iterates over failures to be a well-defined presentation of a category.

Trait Implementations

impl<V, E, S> Category for FpCategory<V, E, S>

where V: Eq + Clone + Hash, E: Eq + Clone + Hash, S: BuildHasher,

type Ob = V

Type of objects in category.

type Mor = Path<V, E>

Type of morphisms in category.

fn has_ob(&self, x: &Self::Ob) -> bool

Does the category contain the value as an object?

fn has_mor(&self, path: &Self::Mor) -> bool

Does the category contain the value as a morphism?

fn dom(&self, path: &Self::Mor) -> Self::Ob

Gets the domain of a morphism in the category.

fn cod(&self, path: &Self::Mor) -> Self::Ob

Gets the codomain of a morphism in the category.

fn compose(&self, path: Path<Self::Ob, Self::Mor>) -> Self::Mor

Composes a path of morphisms in the category.

fn compose2(&self, path1: Self::Mor, path2: Self::Mor) -> Self::Mor

Composes a pair of morphisms with compatible (co)domains.

fn morphisms_are_equal(&self, path1: Self::Mor, path2: Self::Mor) -> bool

Are the two morphisms in the category equal?

fn id(&self, x: Self::Ob) -> Self::Mor

Constructs the identity morphism at an object.

impl<V: Clone, E: Clone, S: Clone> Clone for FpCategory<V, E, S>

fn clone(&self) -> FpCategory<V, E, S>

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<V, E, S> Debug for FpCategory<V, E, S>

where V: Debug, E: Debug, S: Debug,

fn fmt(&self, __f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<V, E, S> Default for FpCategory<V, E, S>

where S: Default,

fn default() -> Self

Returns the “default value” for a type.

impl<V, E, S> FgCategory for FpCategory<V, E, S>

where V: Eq + Clone + Hash, E: Eq + Clone + Hash, S: BuildHasher,

type ObGen = V

Type of an object generator.

type MorGen = E

Type of a morphism generator

fn ob_generators(&self) -> impl Iterator<Item = Self::ObGen>

Iterates over object generators.

fn mor_generators(&self) -> impl Iterator<Item = Self::MorGen>

Iterates over morphism generators.

fn mor_generator_dom(&self, f: &Self::MorGen) -> Self::Ob

The domain of a morphism generator

fn mor_generator_cod(&self, f: &Self::MorGen) -> Self::Ob

The codomain of a morphism generator

fn objects(&self) -> impl Iterator<Item = Self::Ob>

Iterates over basic objects.

fn morphisms(&self) -> impl Iterator<Item = Self::Mor>

Iterates over basic morphisms.

impl<V, E, S> PartialEq for FpCategory<V, E, S>

where V: Eq + Hash, E: Eq + Hash, S: BuildHasher,

fn eq(&self, other: &Self) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<V, E, S> Validate for FpCategory<V, E, S>

where V: Eq + Clone + Hash, E: Eq + Clone + Hash, S: BuildHasher,

type ValidationError = InvalidFpCategory<E>

The type of a validation error.

fn validate(&self) -> Result<(), NonEmpty<Self::ValidationError>>

Validates the object.

impl<V, E, S> Eq for FpCategory<V, E, S>

where V: Eq + Hash, E: Eq + Hash, S: BuildHasher,