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

catlog/one/
category.rs
