catlog/one/
category.rs

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

catlog/one/
category.rs
