catlog/one/
fin_category.rs

1//! Data structures for finite and finitely presented categories.
2
3use std::hash::{BuildHasher, BuildHasherDefault, Hash, RandomState};
4
5use derivative::Derivative;
6use nonempty::NonEmpty;
7use thiserror::Error;
8use ustr::{IdentityHasher, Ustr};
9
10use super::category::*;
11use super::graph::*;
12use super::path::*;
13use crate::validate::{self, Validate};
14use crate::zero::{Column, HashColumn, Mapping, MutMapping};
15
16/// Morphism in a finite category.
17#[derive(Clone, Debug, PartialEq, Eq, Hash)]
18pub enum FinMor<V, E> {
19    /// Identity morphism on an object.
20    Id(V),
21
22    /// Generating morphism of the finite category.
23    Generator(E),
24}
25
26impl<V, E> From<E> for FinMor<V, E> {
27    fn from(value: E) -> Self {
28        FinMor::Generator(value)
29    }
30}
31
32/** A finite category with explicitly defined composition law.
33
34Such a category is not just finitely presented, but actually finite. The
35composition law is defined by a hash map on pairs of morphism generators. While
36very special, finite categories show up surprisingly often as schemas or
37theories. For example, the schemas for graphs, symmetric graphs, reflexive
38graphs, and symmetric reflexive graphs are all finite.
39 */
40#[derive(Clone, Derivative, Debug)]
41#[derivative(Default(bound = "S: Default"))]
42#[derivative(PartialEq(bound = "V: Eq + Hash, E: Eq + Hash, S: BuildHasher"))]
43#[derivative(Eq(bound = "V: Eq + Hash, E: Eq + Hash, S: BuildHasher"))]
44pub struct FinCategory<V, E, S = RandomState> {
45    generators: HashGraph<V, E, S>,
46    compose_map: HashColumn<(E, E), FinMor<V, E>>,
47}
48
49/// A finite category with objects and morphisms of type `Ustr`.
50pub type UstrFinCategory = FinCategory<Ustr, Ustr, BuildHasherDefault<IdentityHasher>>;
51
52impl<V, E, S> FinCategory<V, E, S>
53where
54    V: Eq + Hash + Clone,
55    E: Eq + Hash + Clone,
56    S: BuildHasher,
57{
58    /// Graph of generators of the finite category.
59    pub fn generators(&self) -> &(impl FinGraph<V = V, E = E> + use<V, E, S>) {
60        &self.generators
61    }
62
63    /// Adds an object generator, returning whether it is new.
64    pub fn add_ob_generator(&mut self, v: V) -> bool {
65        self.generators.add_vertex(v)
66    }
67
68    /// Adds multiple object generators.
69    pub fn add_ob_generators<T>(&mut self, iter: T)
70    where
71        T: IntoIterator<Item = V>,
72    {
73        self.generators.add_vertices(iter)
74    }
75
76    /// Adds a morphism generator, returning whether it is new.
77    pub fn add_mor_generator(&mut self, e: E, dom: V, cod: V) -> bool {
78        self.generators.add_edge(e, dom, cod)
79    }
80
81    /// Sets the value of a binary composite.
82    pub fn set_composite(&mut self, d: E, e: E, f: FinMor<V, E>) {
83        self.compose_map.set((d, e), f);
84    }
85
86    /// Iterates over failures to be a well-defined finite category.
87    pub fn iter_invalid(&self) -> impl Iterator<Item = InvalidFinCategory<E>> + '_ {
88        let generator_errors = self.generators.iter_invalid().map(|err| match err {
89            InvalidGraphData::Src(e) => InvalidFinCategory::Dom(e),
90            InvalidGraphData::Tgt(e) => InvalidFinCategory::Cod(e),
91        });
92        let compose_errors = self.generators.edges().flat_map(move |e1| {
93            self.generators.edges().flat_map(move |e2| {
94                let mut errs = Vec::new();
95                if self.generators.tgt(&e1) != self.generators.src(&e2) {
96                    return errs;
97                }
98                let pair = (e1.clone(), e2.clone());
99                if let Some(composite) = self.compose_map.get(&pair) {
100                    if self.dom(composite) != self.generators.src(&e1) {
101                        errs.push(InvalidFinCategory::CompositeDom(e1.clone(), e2.clone()));
102                    }
103                    if self.cod(composite) != self.generators.tgt(&e2) {
104                        errs.push(InvalidFinCategory::CompositeCod(pair.0, pair.1));
105                    }
106                } else {
107                    errs.push(InvalidFinCategory::Composite(pair.0, pair.1));
108                }
109                errs
110            })
111        });
112        generator_errors.chain(compose_errors)
113    }
114}
115
116impl<V, E, S> Validate for FinCategory<V, E, S>
117where
118    V: Eq + Hash + Clone,
119    E: Eq + Hash + Clone,
120    S: BuildHasher,
121{
122    type ValidationError = InvalidFinCategory<E>;
123
124    fn validate(&self) -> Result<(), NonEmpty<Self::ValidationError>> {
125        validate::wrap_errors(self.iter_invalid())
126    }
127}
128
129impl<V, E, S> Category for FinCategory<V, E, S>
130where
131    V: Eq + Hash + Clone,
132    E: Eq + Hash + Clone,
133    S: BuildHasher,
134{
135    type Ob = V;
136    type Mor = FinMor<V, E>;
137
138    fn has_ob(&self, x: &V) -> bool {
139        self.generators.has_vertex(x)
140    }
141
142    fn has_mor(&self, f: &FinMor<V, E>) -> bool {
143        match f {
144            FinMor::Id(v) => self.generators.has_vertex(v),
145            FinMor::Generator(e) => self.generators.has_edge(e),
146        }
147    }
148
149    fn dom(&self, f: &FinMor<V, E>) -> V {
150        match f {
151            FinMor::Id(v) => v.clone(),
152            FinMor::Generator(e) => self.generators.src(e),
153        }
154    }
155
156    fn cod(&self, f: &FinMor<V, E>) -> V {
157        match f {
158            FinMor::Id(v) => v.clone(),
159            FinMor::Generator(e) => self.generators.tgt(e),
160        }
161    }
162
163    fn compose(&self, path: Path<V, FinMor<V, E>>) -> FinMor<V, E> {
164        path.reduce(|x| self.id(x), |f, g| self.compose2(f, g))
165    }
166
167    fn compose2(&self, f: FinMor<V, E>, g: FinMor<V, E>) -> FinMor<V, E> {
168        match (f, g) {
169            (FinMor::Id(_), g) => g,
170            (f, FinMor::Id(_)) => f,
171            (FinMor::Generator(d), FinMor::Generator(e)) => {
172                assert!(
173                    self.generators.tgt(&d) == self.generators.src(&e),
174                    "(Co)domains should be equal"
175                );
176                self.compose_map.apply(&(d, e)).expect("Composition should be defined")
177            }
178        }
179    }
180
181    fn id(&self, x: V) -> FinMor<V, E> {
182        FinMor::Id(x)
183    }
184}
185
186impl<V, E, S> FgCategory for FinCategory<V, E, S>
187where
188    V: Eq + Hash + Clone,
189    E: Eq + Hash + Clone,
190    S: BuildHasher,
191{
192    type ObGen = V;
193    type MorGen = E;
194
195    fn ob_generators(&self) -> impl Iterator<Item = Self::ObGen> {
196        self.generators.vertices()
197    }
198
199    fn mor_generators(&self) -> impl Iterator<Item = Self::MorGen> {
200        self.generators.edges()
201    }
202
203    fn mor_generator_dom(&self, f: &Self::MorGen) -> Self::Ob {
204        self.generators.src(f)
205    }
206
207    fn mor_generator_cod(&self, f: &Self::MorGen) -> Self::Ob {
208        self.generators.tgt(f)
209    }
210}
211
212/// A failure of a finite category to be well defined.
213#[derive(Debug, Error)]
214pub enum InvalidFinCategory<E> {
215    /// Morphism assigned a domain not contained in the category.
216    #[error("Domain of morphism `{0}` is not in the category")]
217    Dom(E),
218
219    /// Morphism assigned a codomain not contained in the category.
220    #[error("Codomain of morphism `{0}` is not in the category")]
221    Cod(E),
222
223    /// Composite of a pair of morphisms is not defined.
224    #[error("Composite of morphisms `{0}` and `{1}` is not defined")]
225    Composite(E, E),
226
227    /// Composite of a pair of morphisms has incompatible domain.
228    #[error("Composite of morphisms `{0}` and `{1}` has incompatible domain")]
229    CompositeDom(E, E),
230
231    /// Composite of a pair of morphisms has incompatible codomain.
232    #[error("Composite of morphisms `{0}` and `{1}` has incompatible codomain")]
233    CompositeCod(E, E),
234}
235
236/** A finitely presented category.
237
238Such a presentation is defined by a finite graph together with a set of path
239equations. A morphism in the presented category is an *equivalence class* of
240paths in the graph, so strictly speaking we work with morphism representatives
241rather than morphism themselves.
242
243Like the object and morphism generators, the equations are identified by keys.
244Depending on the application, these could be axiom names or meaningless IDs.
245 */
246#[derive(Clone, Derivative, Debug)]
247#[derivative(Default(bound = "S: Default"))]
248#[derivative(PartialEq(bound = "V: Eq + Hash, E: Eq + Hash, EqKey: Eq + Hash, S: BuildHasher"))]
249#[derivative(Eq(bound = "V: Eq + Hash, E: Eq + Hash, EqKey: Eq + Hash, S: BuildHasher"))]
250pub struct FpCategory<V, E, EqKey, S = RandomState> {
251    generators: HashGraph<V, E, S>,
252    equations: HashColumn<EqKey, PathEq<V, E>, S>,
253}
254
255/// A finitely presented category with generators and equation keys of type
256/// `Ustr`.
257pub type UstrFpCategory = FpCategory<Ustr, Ustr, Ustr, BuildHasherDefault<IdentityHasher>>;
258
259impl<V, E, EqKey, S> FpCategory<V, E, EqKey, S>
260where
261    V: Eq + Clone + Hash,
262    E: Eq + Clone + Hash,
263    EqKey: Eq + Clone + Hash,
264    S: BuildHasher,
265{
266    /// Graph of generators of the finitely presented category.
267    pub fn generators(&self) -> &(impl FinGraph<V = V, E = E> + use<V, E, EqKey, S>) {
268        &self.generators
269    }
270
271    /// Get a path equation by key.
272    pub fn get_equation(&self, key: &EqKey) -> Option<&PathEq<V, E>> {
273        self.equations.get(key)
274    }
275
276    /// Iterates over path equations in the presentation.
277    pub fn equations(&self) -> impl Iterator<Item = &PathEq<V, E>> {
278        self.equations.values()
279    }
280
281    /// Adds an object generator, returning whether it is new.
282    pub fn add_ob_generator(&mut self, v: V) -> bool {
283        self.generators.add_vertex(v)
284    }
285
286    /// Adds multiple object generators.
287    pub fn add_ob_generators<Iter>(&mut self, iter: Iter)
288    where
289        Iter: IntoIterator<Item = V>,
290    {
291        self.generators.add_vertices(iter)
292    }
293
294    /// Adds a morphism generator, returning whether it is new.
295    pub fn add_mor_generator(&mut self, e: E, dom: V, cod: V) -> bool {
296        self.generators.add_edge(e, dom, cod)
297    }
298
299    /// Adds a morphism generator without initializing its (co)domain.
300    pub fn make_mor_generator(&mut self, e: E) -> bool {
301        self.generators.make_edge(e)
302    }
303
304    /// Gets the domain of a morphism generator.
305    pub fn get_dom(&self, e: &E) -> Option<&V> {
306        self.generators.get_src(e)
307    }
308
309    /// Gets the codomain of a morphism generator.
310    pub fn get_cod(&self, e: &E) -> Option<&V> {
311        self.generators.get_tgt(e)
312    }
313
314    /// Sets the domain of a morphism generator.
315    pub fn set_dom(&mut self, e: E, v: V) -> Option<V> {
316        self.generators.set_src(e, v)
317    }
318
319    /// Sets the codomain of a morphism generator.
320    pub fn set_cod(&mut self, e: E, v: V) -> Option<V> {
321        self.generators.set_tgt(e, v)
322    }
323
324    /// Adds a path equation to the presentation.
325    pub fn add_equation(&mut self, key: EqKey, eq: PathEq<V, E>) {
326        self.equations.set(key, eq);
327    }
328
329    /// Is the category freely generated?
330    pub fn is_free(&self) -> bool {
331        self.equations.is_empty()
332    }
333
334    /// Iterates over failures to be a well-defined presentation of a category.
335    pub fn iter_invalid(&self) -> impl Iterator<Item = InvalidFpCategory<E, EqKey>> + '_ {
336        let generator_errors = self.generators.iter_invalid().map(|err| match err {
337            InvalidGraphData::Src(e) => InvalidFpCategory::Dom(e),
338            InvalidGraphData::Tgt(e) => InvalidFpCategory::Cod(e),
339        });
340        let equation_errors = self.equations.iter().flat_map(|(key, eq)| {
341            eq.iter_invalid_in(&self.generators).map(move |err| match err {
342                InvalidPathEq::Lhs() => InvalidFpCategory::EqLhs(key.clone()),
343                InvalidPathEq::Rhs() => InvalidFpCategory::EqRhs(key.clone()),
344                InvalidPathEq::Src() => InvalidFpCategory::EqSrc(key.clone()),
345                InvalidPathEq::Tgt() => InvalidFpCategory::EqTgt(key.clone()),
346            })
347        });
348        generator_errors.chain(equation_errors)
349    }
350}
351
352impl<V, E, EqKey, S> Validate for FpCategory<V, E, EqKey, S>
353where
354    V: Eq + Clone + Hash,
355    E: Eq + Clone + Hash,
356    EqKey: Eq + Clone + Hash,
357    S: BuildHasher,
358{
359    type ValidationError = InvalidFpCategory<E, EqKey>;
360
361    fn validate(&self) -> Result<(), NonEmpty<Self::ValidationError>> {
362        validate::wrap_errors(self.iter_invalid())
363    }
364}
365
366impl<V, E, EqKey, S> Category for FpCategory<V, E, EqKey, S>
367where
368    V: Eq + Clone + Hash,
369    E: Eq + Clone + Hash,
370    EqKey: Eq + Clone + Hash,
371    S: BuildHasher,
372{
373    type Ob = V;
374    type Mor = Path<V, E>;
375
376    fn has_ob(&self, x: &V) -> bool {
377        self.generators.has_vertex(x)
378    }
379    fn has_mor(&self, path: &Path<V, E>) -> bool {
380        path.contained_in(&self.generators)
381    }
382    fn dom(&self, path: &Path<V, E>) -> V {
383        path.src(&self.generators)
384    }
385    fn cod(&self, path: &Path<V, E>) -> V {
386        path.tgt(&self.generators)
387    }
388
389    fn compose(&self, path: Path<V, Path<V, E>>) -> Path<V, E> {
390        path.flatten_in(&self.generators).expect("Paths should be composable")
391    }
392    fn compose2(&self, path1: Path<V, E>, path2: Path<V, E>) -> Path<V, E> {
393        path1
394            .concat_in(&self.generators, path2)
395            .expect("Target of first path should equal source of second path")
396    }
397}
398
399impl<V, E, EqKey, S> FgCategory for FpCategory<V, E, EqKey, S>
400where
401    V: Eq + Clone + Hash,
402    E: Eq + Clone + Hash,
403    EqKey: Eq + Clone + Hash,
404    S: BuildHasher,
405{
406    type ObGen = V;
407    type MorGen = E;
408
409    fn ob_generators(&self) -> impl Iterator<Item = Self::ObGen> {
410        self.generators.vertices()
411    }
412
413    fn mor_generators(&self) -> impl Iterator<Item = Self::MorGen> {
414        self.generators.edges()
415    }
416
417    fn mor_generator_dom(&self, f: &Self::MorGen) -> Self::Ob {
418        self.generators.src(f)
419    }
420
421    fn mor_generator_cod(&self, f: &Self::MorGen) -> Self::Ob {
422        self.generators.tgt(f)
423    }
424}
425
426/// A failure of a finite presentation of a category to be well defined.
427#[derive(Debug, Error)]
428pub enum InvalidFpCategory<E, EqKey> {
429    /// Morphism generator assigned a domain not contained in the category.
430    #[error("Domain of morphism generator `{0}` is not in the category")]
431    Dom(E),
432
433    /// Morphism generator assigned a codomain not contained in the category.
434    #[error("Codomain of morphism generator `{0}` is not in the category")]
435    Cod(E),
436
437    /// Path in left hand side of equation not contained in the category.
438    #[error("LHS of path equation `{0}` is not in the category")]
439    EqLhs(EqKey),
440
441    /// Path in right hand side of equation not contained in the category.
442    #[error("RHS of path equation `{0}` is not in the category")]
443    EqRhs(EqKey),
444
445    /// Sources of left and right hand sides of path equation are not equal.
446    #[error("Path equation `{0}` has sources that are not equal")]
447    EqSrc(EqKey),
448
449    /// Targets of left and right hand sides of path equation are not equal.
450    #[error("Path equation `{0}` has targets that are not equal")]
451    EqTgt(EqKey),
452}
453
454#[cfg(test)]
455mod tests {
456    use super::*;
457    use nonempty::nonempty;
458
459    #[test]
460    fn fin_category() {
461        type Mor<V, E> = FinMor<V, E>;
462
463        let mut sch_sgraph: FinCategory<char, char> = Default::default();
464        sch_sgraph.add_ob_generators(['V', 'E']);
465        sch_sgraph.add_mor_generator('s', 'E', 'V');
466        sch_sgraph.add_mor_generator('t', 'E', 'V');
467        sch_sgraph.add_mor_generator('i', 'E', 'E');
468        assert_eq!(sch_sgraph.ob_generators().count(), 2);
469        assert_eq!(sch_sgraph.mor_generators().count(), 3);
470        assert_eq!(sch_sgraph.dom(&Mor::Generator('t')), 'E');
471        assert_eq!(sch_sgraph.cod(&Mor::Generator('t')), 'V');
472        assert_eq!(sch_sgraph.validate().unwrap_err().len(), 3);
473
474        sch_sgraph.set_composite('i', 'i', Mor::Id('E'));
475        sch_sgraph.set_composite('i', 's', Mor::Generator('t'));
476        sch_sgraph.set_composite('i', 't', Mor::Generator('s'));
477        assert!(sch_sgraph.validate().is_ok());
478        assert_eq!(sch_sgraph.compose2(Mor::Generator('i'), Mor::Generator('i')), Mor::Id('E'));
479        let path = Path::Seq(nonempty![
480            Mor::Generator('i'),
481            Mor::Id('E'),
482            Mor::Generator('i'),
483            Mor::Generator('i'),
484            Mor::Generator('s'),
485        ]);
486        assert_eq!(sch_sgraph.compose(path), Mor::Generator('t'));
487    }
488
489    #[test]
490    fn fp_category() {
491        let mut sch_sgraph: FpCategory<_, _, _> = Default::default();
492        sch_sgraph.add_ob_generators(['V', 'E']);
493        sch_sgraph.add_mor_generator('s', 'E', 'V');
494        sch_sgraph.add_mor_generator('t', 'E', 'V');
495        sch_sgraph.add_mor_generator('i', 'E', 'E');
496        assert!(sch_sgraph.is_free());
497        assert_eq!(sch_sgraph.ob_generators().count(), 2);
498        assert_eq!(sch_sgraph.mor_generators().count(), 3);
499        assert_eq!(sch_sgraph.dom(&Path::single('t')), 'E');
500        assert_eq!(sch_sgraph.cod(&Path::single('t')), 'V');
501        assert!(sch_sgraph.validate().is_ok());
502
503        sch_sgraph.add_equation("inv", PathEq::new(Path::pair('i', 'i'), Path::empty('E')));
504        sch_sgraph.add_equation("rev_src", PathEq::new(Path::pair('i', 's'), Path::single('t')));
505        sch_sgraph.add_equation("rev_tgt", PathEq::new(Path::pair('i', 't'), Path::single('s')));
506        assert!(!sch_sgraph.is_free());
507        assert_eq!(sch_sgraph.equations().count(), 3);
508        assert!(sch_sgraph.validate().is_ok());
509
510        let mut sch_bad: FpCategory<_, _, _> = Default::default();
511        sch_bad.add_ob_generators(['x', 'y']);
512        sch_bad.make_mor_generator('f');
513        assert_eq!(sch_bad.validate().unwrap_err().len(), 2);
514        sch_bad.set_dom('f', 'x');
515        sch_bad.set_cod('f', 'y');
516        assert!(sch_bad.validate().is_ok());
517        sch_bad.add_mor_generator('g', 'y', 'x');
518        sch_bad.add_equation('α', PathEq::new(Path::single('f'), Path::single('g')));
519        assert_eq!(sch_bad.validate().unwrap_err().len(), 2);
520    }
521}
catlog/one/fin_category.rs

catlog/one/
fin_category.rs
