catlog/one/
category.rs

1//! Categories: interfaces and basic constructions.
2
3use derive_more::From;
4use ref_cast::RefCast;
5
6use super::graph::{FinGraph, Graph, ReflexiveGraph};
7use super::path::Path;
8use crate::zero::{FinSet, Set};
9
10/// A category.
11///
12/// We take the unbiased view of categories, meaning that composition is an
13/// operation on [paths](Path) of arbitrary finite length. This has several
14/// advantages. First, it takes as primitive the natural data structure for
15/// morphisms in a free category, or more generally in a presentation of a category.
16/// It also enables more intelligent strategies for evaluating composites in
17/// specific categories. For instance, when composing (multiplying) a sequence of
18/// matrices, it can be very inefficient to just fold from the left or right,
19/// compared to multiplying in the [optimal
20/// order](https://en.wikipedia.org/wiki/Matrix_chain_multiplication).
21pub trait Category {
22    /// Type of objects in category.
23    type Ob: Eq + Clone;
24
25    /// Type of morphisms in category.
26    type Mor: Eq + Clone;
27
28    /// Does the category contain the value as an object?
29    fn has_ob(&self, x: &Self::Ob) -> bool;
30
31    /// Does the category contain the value as a morphism?
32    fn has_mor(&self, f: &Self::Mor) -> bool;
33
34    /// Gets the domain of a morphism in the category.
35    fn dom(&self, f: &Self::Mor) -> Self::Ob;
36
37    /// Gets the codomain of a morphism in the category.
38    fn cod(&self, f: &Self::Mor) -> Self::Ob;
39
40    /// Composes a path of morphisms in the category.
41    fn compose(&self, path: Path<Self::Ob, Self::Mor>) -> Self::Mor;
42
43    /// Composes a pair of morphisms with compatible (co)domains.
44    fn compose2(&self, f: Self::Mor, g: Self::Mor) -> Self::Mor {
45        self.compose(Path::pair(f, g))
46    }
47
48    /// Constructs the identity morphism at an object.
49    fn id(&self, x: Self::Ob) -> Self::Mor {
50        self.compose(Path::empty(x))
51    }
52
53    /// Are the two morphisms in the category equal?
54    ///
55    /// The default implementation compares the morphisms with `==`. In some
56    /// categories, equality is defined by a weaker equivalence relation.
57    fn morphisms_are_equal(&self, f: Self::Mor, g: Self::Mor) -> bool {
58        f == g
59    }
60}
61
62/// The set of objects of a category.
63#[derive(From, RefCast)]
64#[repr(transparent)]
65pub struct ObSet<Cat>(Cat);
66
67impl<Cat: Category> Set for ObSet<Cat> {
68    type Elem = Cat::Ob;
69
70    fn contains(&self, x: &Cat::Ob) -> bool {
71        self.0.has_ob(x)
72    }
73}
74
75/// The discrete category on a set.
76///
77/// The objects of the category are the elements of the set, and the only morphisms
78/// are the identities, which can thus be identified with the objects.
79#[derive(From, RefCast)]
80#[repr(transparent)]
81pub struct DiscreteCategory<S>(S);
82
83impl<S: Set> Category for DiscreteCategory<S> {
84    type Ob = S::Elem;
85    type Mor = S::Elem;
86
87    fn has_ob(&self, x: &S::Elem) -> bool {
88        self.0.contains(x)
89    }
90    fn has_mor(&self, f: &S::Elem) -> bool {
91        self.0.contains(f)
92    }
93    fn dom(&self, x: &S::Elem) -> S::Elem {
94        x.clone()
95    }
96    fn cod(&self, x: &S::Elem) -> S::Elem {
97        x.clone()
98    }
99
100    fn compose(&self, path: Path<S::Elem, S::Elem>) -> S::Elem {
101        match path {
102            Path::Id(x) => x,
103            Path::Seq(xs) => {
104                let x = xs.head;
105                assert!(
106                    xs.tail.into_iter().all(|y| x == y),
107                    "Cannot compose identities on different objects"
108                );
109                x
110            }
111        }
112    }
113}
114
115/// The underlying graph of a category.
116///
117/// The vertices and edges of the graph are the objects and morphisms of the
118/// category, respectively.
119#[derive(From, RefCast)]
120#[repr(transparent)]
121pub struct UnderlyingGraph<Cat: Category>(Cat);
122
123impl<Cat: Category> Graph for UnderlyingGraph<Cat> {
124    type V = Cat::Ob;
125    type E = Cat::Mor;
126
127    fn has_vertex(&self, x: &Self::V) -> bool {
128        self.0.has_ob(x)
129    }
130    fn has_edge(&self, f: &Self::E) -> bool {
131        self.0.has_mor(f)
132    }
133    fn src(&self, f: &Self::E) -> Self::V {
134        self.0.dom(f)
135    }
136    fn tgt(&self, f: &Self::E) -> Self::V {
137        self.0.cod(f)
138    }
139}
140
141impl<Cat: Category> ReflexiveGraph for UnderlyingGraph<Cat> {
142    fn refl(&self, x: Self::V) -> Self::E {
143        self.0.id(x)
144    }
145}
146
147/// The free category on a graph.
148///
149/// The objects and morphisms of the free category are the vertices and *paths* in
150/// the graph, respectively. Paths compose by concatenation.
151#[derive(From, RefCast)]
152#[repr(transparent)]
153pub struct FreeCategory<G: Graph>(G);
154
155impl<G: Graph> Category for FreeCategory<G> {
156    type Ob = G::V;
157    type Mor = Path<G::V, G::E>;
158
159    fn has_ob(&self, x: &G::V) -> bool {
160        self.0.has_vertex(x)
161    }
162    fn has_mor(&self, path: &Path<G::V, G::E>) -> bool {
163        path.contained_in(&self.0)
164    }
165    fn dom(&self, path: &Path<G::V, G::E>) -> G::V {
166        path.src(&self.0)
167    }
168    fn cod(&self, path: &Path<G::V, G::E>) -> G::V {
169        path.tgt(&self.0)
170    }
171
172    fn compose(&self, path: Path<G::V, Path<G::V, G::E>>) -> Path<G::V, G::E> {
173        path.flatten_in(&self.0).expect("Paths should be composable")
174    }
175    fn compose2(&self, path1: Path<G::V, G::E>, path2: Path<G::V, G::E>) -> Path<G::V, G::E> {
176        path1
177            .concat_in(&self.0, path2)
178            .expect("Target of first path should equal source of second path")
179    }
180}
181
182/// A finitely generated category with specified object and morphism generators.
183///
184/// Unless the category has extra structure like a monoidal product, a finitely
185/// generated (f.g.) category has finitely many objects. Moreover, the objects will
186/// coincide with the object generators in the typical case that there are no
187/// equations between objects. On the other hand, a f.g. category can have
188/// infinitely many morphisms and often does.
189pub trait FgCategory: Category {
190    /// Type of an object generator.
191    ///
192    /// In simple cases, `Ob = ObGen`.
193    type ObGen: Eq + Clone + Into<Self::Ob>;
194
195    /// Type of a morphism generator
196    ///
197    /// Often `Mor = Path<Ob, MorGen>`.
198    type MorGen: Eq + Clone + Into<Self::Mor>;
199
200    /// Iterates over object generators.
201    fn ob_generators(&self) -> impl Iterator<Item = Self::ObGen>;
202
203    /// Iterates over morphism generators.
204    fn mor_generators(&self) -> impl Iterator<Item = Self::MorGen>;
205
206    /// The domain of a morphism generator
207    fn mor_generator_dom(&self, f: &Self::MorGen) -> Self::Ob;
208
209    /// The codomain of a morphism generator
210    fn mor_generator_cod(&self, f: &Self::MorGen) -> Self::Ob;
211
212    /// Iterates over basic objects.
213    fn objects(&self) -> impl Iterator<Item = Self::Ob> {
214        self.ob_generators().map(|ob_gen| ob_gen.into())
215    }
216
217    /// Iterates over basic morphisms.
218    fn morphisms(&self) -> impl Iterator<Item = Self::Mor> {
219        self.mor_generators().map(|mor_gen| mor_gen.into())
220    }
221}
222
223impl<S: FinSet> FgCategory for DiscreteCategory<S> {
224    type ObGen = S::Elem;
225    type MorGen = S::Elem;
226
227    fn ob_generators(&self) -> impl Iterator<Item = Self::ObGen> {
228        self.0.iter()
229    }
230
231    fn mor_generators(&self) -> impl Iterator<Item = Self::MorGen> {
232        self.0.iter()
233    }
234
235    fn mor_generator_dom(&self, f: &Self::MorGen) -> Self::Ob {
236        f.clone()
237    }
238
239    fn mor_generator_cod(&self, f: &Self::MorGen) -> Self::Ob {
240        f.clone()
241    }
242}
243
244impl<G: FinGraph> FgCategory for FreeCategory<G> {
245    type ObGen = G::V;
246    type MorGen = G::E;
247
248    fn ob_generators(&self) -> impl Iterator<Item = Self::ObGen> {
249        self.0.vertices()
250    }
251
252    fn mor_generators(&self) -> impl Iterator<Item = Self::MorGen> {
253        self.0.edges()
254    }
255
256    fn mor_generator_dom(&self, f: &Self::MorGen) -> Self::Ob {
257        self.0.src(f)
258    }
259
260    fn mor_generator_cod(&self, f: &Self::MorGen) -> Self::Ob {
261        self.0.tgt(f)
262    }
263}
264
265#[cfg(test)]
266mod tests {
267    use nonempty::nonempty;
268
269    use super::super::graph::SkelGraph;
270    use super::*;
271    use crate::zero::SkelFinSet;
272
273    #[test]
274    fn discrete_category() {
275        let cat = DiscreteCategory::from(SkelFinSet::from(3));
276        assert!(cat.has_ob(&2));
277        assert!(cat.has_mor(&2));
278        assert!(!cat.has_mor(&3));
279        assert_eq!(cat.dom(&1), 1);
280        assert_eq!(cat.cod(&1), 1);
281        assert_eq!(cat.compose(Path::Seq(nonempty![1, 1, 1])), 1);
282    }
283
284    #[test]
285    fn free_category() {
286        let cat = FreeCategory::from(SkelGraph::triangle());
287        assert!(cat.has_ob(&2));
288        assert_eq!(cat.ob_generators().count(), 3);
289        assert_eq!(cat.mor_generators().count(), 3);
290
291        let id = Path::Id(1);
292        assert!(cat.has_mor(&id));
293        assert_eq!(cat.dom(&id), 1);
294        assert_eq!(cat.cod(&id), 1);
295
296        let path = Path::pair(0, 1);
297        assert!(cat.has_mor(&path));
298        assert!(!cat.has_mor(&Path::pair(0, 2)));
299        assert_eq!(cat.dom(&path), 0);
300        assert_eq!(cat.cod(&path), 2);
301
302        let cat = FreeCategory::from(SkelGraph::path(5));
303        let path = Path::Seq(nonempty![
304            Path::Id(0),
305            Path::pair(0, 1),
306            Path::Id(2),
307            Path::pair(2, 3),
308            Path::Id(4),
309        ]);
310        let result = Path::Seq(nonempty![0, 1, 2, 3]);
311        assert_eq!(cat.compose(path), result);
312        assert_eq!(cat.compose2(Path::pair(0, 1), Path::pair(2, 3)), result);
313    }
314}
catlog/one/category.rs

catlog/one/
category.rs
