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};
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: Category>(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: Set>(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
145/** The free category on a graph.
146
147The objects and morphisms of the free category are the vertices and *paths* in
148the graph, respectively. Paths compose by concatenation.
149 */
150#[derive(From, RefCast)]
151#[repr(transparent)]
152pub struct FreeCategory<G: Graph>(G);
153
154impl<G: Graph> Category for FreeCategory<G> {
155    type Ob = G::V;
156    type Mor = Path<G::V, G::E>;
157
158    fn has_ob(&self, x: &G::V) -> bool {
159        self.0.has_vertex(x)
160    }
161    fn has_mor(&self, path: &Path<G::V, G::E>) -> bool {
162        path.contained_in(&self.0)
163    }
164    fn dom(&self, path: &Path<G::V, G::E>) -> G::V {
165        path.src(&self.0)
166    }
167    fn cod(&self, path: &Path<G::V, G::E>) -> G::V {
168        path.tgt(&self.0)
169    }
170
171    fn compose(&self, path: Path<G::V, Path<G::V, G::E>>) -> Path<G::V, G::E> {
172        path.flatten_in(&self.0).expect("Paths should be composable")
173    }
174    fn compose2(&self, path1: Path<G::V, G::E>, path2: Path<G::V, G::E>) -> Path<G::V, G::E> {
175        path1
176            .concat_in(&self.0, path2)
177            .expect("Target of first path should equal source of second path")
178    }
179}
180
181/** A finitely generated category with specified object and morphism generators.
182
183Unless the category has extra structure like a monoidal product, a finitely
184generated (f.g.) category has finitely many objects. Moreover, the objects will
185coincide with the object generators in the typical case that there are no
186equations between objects. On the other hand, a f.g. category can have
187infinitely many morphisms and often does.
188 */
189pub trait FgCategory: Category {
190    /** Type of an object generator.
191
192    In simple cases, `Ob = ObGen`.
193     */
194    type ObGen: Eq + Clone + Into<Self::Ob>;
195
196    /** Type of a morphism generator
197
198    Often `Mor = Path<Ob, MorGen>`.
199     */
200    type MorGen: Eq + Clone + Into<Self::Mor>;
201
202    /// Iterates over object generators.
203    fn ob_generators(&self) -> impl Iterator<Item = Self::ObGen>;
204
205    /// Iterates over morphism generators.
206    fn mor_generators(&self) -> impl Iterator<Item = Self::MorGen>;
207
208    /// The domain of a morphism generator
209    fn mor_generator_dom(&self, f: &Self::MorGen) -> Self::Ob;
210
211    /// The codomain of a morphism generator
212    fn mor_generator_cod(&self, f: &Self::MorGen) -> Self::Ob;
213
214    /// Iterates over basic objects.
215    fn objects(&self) -> impl Iterator<Item = Self::Ob> {
216        self.ob_generators().map(|ob_gen| ob_gen.into())
217    }
218
219    /// Iterates over basic morphisms.
220    fn morphisms(&self) -> impl Iterator<Item = Self::Mor> {
221        self.mor_generators().map(|mor_gen| mor_gen.into())
222    }
223}
224
225impl<S: FinSet> FgCategory for DiscreteCategory<S> {
226    type ObGen = S::Elem;
227    type MorGen = S::Elem;
228
229    fn ob_generators(&self) -> impl Iterator<Item = Self::ObGen> {
230        self.0.iter()
231    }
232
233    fn mor_generators(&self) -> impl Iterator<Item = Self::MorGen> {
234        self.0.iter()
235    }
236
237    fn mor_generator_dom(&self, f: &Self::MorGen) -> Self::Ob {
238        f.clone()
239    }
240
241    fn mor_generator_cod(&self, f: &Self::MorGen) -> Self::Ob {
242        f.clone()
243    }
244}
245
246impl<G: FinGraph> FgCategory for FreeCategory<G> {
247    type ObGen = G::V;
248    type MorGen = G::E;
249
250    fn ob_generators(&self) -> impl Iterator<Item = Self::ObGen> {
251        self.0.vertices()
252    }
253
254    fn mor_generators(&self) -> impl Iterator<Item = Self::MorGen> {
255        self.0.edges()
256    }
257
258    fn mor_generator_dom(&self, f: &Self::MorGen) -> Self::Ob {
259        self.0.src(f)
260    }
261
262    fn mor_generator_cod(&self, f: &Self::MorGen) -> Self::Ob {
263        self.0.tgt(f)
264    }
265}
266
267#[cfg(test)]
268mod tests {
269    use nonempty::nonempty;
270
271    use super::super::graph::SkelGraph;
272    use super::*;
273    use crate::zero::SkelFinSet;
274
275    #[test]
276    fn discrete_category() {
277        let cat = DiscreteCategory::from(SkelFinSet::from(3));
278        assert!(cat.has_ob(&2));
279        assert!(cat.has_mor(&2));
280        assert!(!cat.has_mor(&3));
281        assert_eq!(cat.dom(&1), 1);
282        assert_eq!(cat.cod(&1), 1);
283        assert_eq!(cat.compose(Path::Seq(nonempty![1, 1, 1])), 1);
284    }
285
286    #[test]
287    fn free_category() {
288        let cat = FreeCategory::from(SkelGraph::triangle());
289        assert!(cat.has_ob(&2));
290        assert_eq!(cat.ob_generators().count(), 3);
291        assert_eq!(cat.mor_generators().count(), 3);
292
293        let id = Path::Id(1);
294        assert!(cat.has_mor(&id));
295        assert_eq!(cat.dom(&id), 1);
296        assert_eq!(cat.cod(&id), 1);
297
298        let path = Path::pair(0, 1);
299        assert!(cat.has_mor(&path));
300        assert!(!cat.has_mor(&Path::pair(0, 2)));
301        assert_eq!(cat.dom(&path), 0);
302        assert_eq!(cat.cod(&path), 2);
303
304        let cat = FreeCategory::from(SkelGraph::path(5));
305        let path = Path::Seq(nonempty![
306            Path::Id(0),
307            Path::pair(0, 1),
308            Path::Id(2),
309            Path::pair(2, 3),
310            Path::Id(4),
311        ]);
312        let result = Path::Seq(nonempty![0, 1, 2, 3]);
313        assert_eq!(cat.compose(path), result);
314        assert_eq!(cat.compose2(Path::pair(0, 1), Path::pair(2, 3)), result);
315    }
316}
catlog/one/category.rs

catlog/one/
category.rs
