catlog/one/
functor.rs

1//! Functors between categories.
2//!
3//! Abstractly, a functor between categories is a just graph morphism between the
4//! underlying graphs that respects composition. In our applications, we are most
5//! interested in functors out of *finitely generated* categories, whose action on
6//! arbitrary morphisms is uniquely determined by that on the morphism generators.
7//! Thus, in contrast to mappings between [sets](crate::zero::Mapping) and
8//! [graphs](crate::one::GraphMapping), we generally cannot separate *evaluation*
9//! from *validation*: to evaluate a [map](FgCategoryMap) on a finitely generated
10//! category, we might need access to the domain category, in order to decompose
11//! general morphisms into composites of generators, and also to the codomain
12//! category, in order to compose images of generating morphisms. The upshot is that
13//! you must carry around (references to) more data to evaluate functors than to
14//! evaluate functions or graph morphisms.
15
16use std::hash::Hash;
17
18use derive_more::Constructor;
19use nonempty::NonEmpty;
20use ref_cast::RefCast;
21use thiserror::Error;
22
23use super::{
24    Category, FpCategory, GraphMapping, GraphMorphism, InvalidGraphMorphism, Path, UnderlyingGraph,
25};
26use crate::zero::{Column, Mapping};
27
28/// A mapping between categories.
29///
30/// Analogous to a mapping between [sets](crate::zero::Mapping) or
31/// [graphs](crate::one::GraphMapping), a category mapping is a functor without
32/// specified domain or codomain categories.
33pub trait CategoryMap {
34    /// Type of objects in domain category.
35    type DomOb: Eq + Clone;
36
37    /// Type of morphisms in domain category.
38    type DomMor: Eq + Clone;
39
40    /// Type of objects in codomain category.
41    type CodOb: Eq + Clone;
42
43    /// Type of morphisms in codomain category.
44    type CodMor: Eq + Clone;
45
46    /// Type of underlying mapping on objects.
47    type ObMap: Mapping<Dom = Self::DomOb, Cod = Self::CodOb>;
48
49    /// Type of underlying mapping on morphisms.
50    type MorMap: Mapping<Dom = Self::DomMor, Cod = Self::CodMor>;
51
52    /// Gets the underlying mapping on objects.
53    fn ob_map(&self) -> &Self::ObMap;
54
55    /// Gets the underlying mapping on morphisms.
56    fn mor_map(&self) -> &Self::MorMap;
57
58    /// Applies the mapping to an object.
59    fn apply_ob(&self, x: Self::DomOb) -> Option<Self::CodOb> {
60        self.ob_map().apply(x)
61    }
62
63    /// Applies the mapping to a morphism.
64    fn apply_mor(&self, m: Self::DomMor) -> Option<Self::CodMor> {
65        self.mor_map().apply(m)
66    }
67
68    /// Is the mapping defined at an object?
69    fn is_ob_assigned(&self, x: &Self::DomOb) -> bool {
70        self.ob_map().is_set(x)
71    }
72
73    /// Is the mapping defined at a morphism?
74    fn is_mor_assigned(&self, m: &Self::DomMor) -> bool {
75        self.mor_map().is_set(m)
76    }
77}
78
79/// A mapping out of a finitely generated category.
80///
81/// Such a mapping is determined by where it sends generating objects and morphisms.
82/// The codomain category is arbitrary.
83pub trait FgCategoryMap: CategoryMap {
84    /// Type of object generators in domain category.
85    type ObGen: Eq + Clone;
86
87    /// Type of morphism generators in domain category.
88    type MorGen: Eq + Clone;
89
90    /// Type of underlying mapping from object generators to objects.
91    type ObGenMap: Column<Dom = Self::ObGen, Cod = Self::CodOb>;
92
93    /// Type of underlying mapping from morphism generators to morphisms.
94    type MorGenMap: Column<Dom = Self::MorGen, Cod = Self::CodMor>;
95
96    /// Gets the underlying mapping from object generators to objects.
97    fn ob_generator_map(&self) -> &Self::ObGenMap;
98
99    /// Gets the underlying mapping from morphism generators to morphisms.
100    fn mor_generator_map(&self) -> &Self::MorGenMap;
101
102    /// Applies the mapping at a generating object.
103    fn apply_ob_generator(&self, x: Self::ObGen) -> Option<Self::CodOb> {
104        self.ob_generator_map().apply(x)
105    }
106
107    /// Applies the mapping at a generating morphism.
108    fn apply_mor_generator(&self, m: Self::MorGen) -> Option<Self::CodMor> {
109        self.mor_generator_map().apply(m)
110    }
111}
112
113/// The data of a functor out of a finitely presented (f.p.) category.
114///
115/// This struct consists of a pair of mappings on the object and morphism generators
116/// of the domain category, assumed to be finitely presented. This data defines a
117/// [graph mapping](GraphMapping) from the domain category's generating graph to the
118/// codomain category's underlying graph.
119///
120/// You can't do much with this data until it is [interpreted as a
121/// functor](Self::functor_into) into a specific category.
122#[derive(Clone, Debug, Default, PartialEq, Eq, Constructor)]
123pub struct FpFunctorData<ObGenMap, MorGenMap> {
124    /// Mapping on object generators.
125    pub ob_generator_map: ObGenMap,
126
127    /// Mapping on morphism generators.
128    pub mor_generator_map: MorGenMap,
129}
130
131impl<ObGenMap, MorGenMap> FpFunctorData<ObGenMap, MorGenMap> {
132    /// Interprets the data as a functor into the given category.
133    pub fn functor_into<'a, Cod>(&'a self, cod: &'a Cod) -> FpFunctor<'a, Self, Cod> {
134        FpFunctor::new(self, cod)
135    }
136}
137
138impl<ObGenMap, MorGenMap> GraphMapping for FpFunctorData<ObGenMap, MorGenMap>
139where
140    ObGenMap: Mapping,
141    MorGenMap: Mapping,
142{
143    type DomV = ObGenMap::Dom;
144    type DomE = MorGenMap::Dom;
145    type CodV = ObGenMap::Cod;
146    type CodE = MorGenMap::Cod;
147    type VertexMap = ObGenMap;
148    type EdgeMap = MorGenMap;
149
150    fn vertex_map(&self) -> &Self::VertexMap {
151        &self.ob_generator_map
152    }
153    fn edge_map(&self) -> &Self::EdgeMap {
154        &self.mor_generator_map
155    }
156}
157
158/// A functor out of a finitely presented (f.p.) category.
159///
160/// Like a [`Function`](crate::zero::Function), this struct borrows its data. Unlike
161/// a [`Mapping`] between sets, a codomain is needed not just for validation but to
162/// even evaluate the functor on morphisms, hence is required as extra data. The
163/// domain category is needed only for validation.
164#[derive(Constructor)]
165pub struct FpFunctor<'a, Map, Cod> {
166    map: &'a Map,
167    cod: &'a Cod,
168}
169
170impl<'a, Ob, Mor, Map, Cod> CategoryMap for FpFunctor<'a, Map, Cod>
171where
172    Ob: Eq + Clone,
173    Mor: Eq + Clone,
174    Map: GraphMapping<CodV = Ob, CodE = Mor>,
175    Cod: Category<Ob = Ob, Mor = Mor>,
176{
177    type DomOb = Map::DomV;
178    type DomMor = Path<Map::DomV, Map::DomE>;
179    type CodOb = Ob;
180    type CodMor = Mor;
181    type ObMap = Map::VertexMap;
182    type MorMap = FpFunctorMorMap<'a, Map, Cod>;
183
184    fn ob_map(&self) -> &Self::ObMap {
185        self.map.vertex_map()
186    }
187    fn mor_map(&self) -> &Self::MorMap {
188        RefCast::ref_cast(self)
189    }
190}
191
192impl<'a, Ob, Mor, Map, Cod> FgCategoryMap for FpFunctor<'a, Map, Cod>
193where
194    Ob: Eq + Clone,
195    Mor: Eq + Clone,
196    Map: GraphMapping<CodV = Ob, CodE = Mor>,
197    Map::VertexMap: Column,
198    Map::EdgeMap: Column,
199    Cod: Category<Ob = Ob, Mor = Mor>,
200{
201    type ObGen = Map::DomV;
202    type MorGen = Map::DomE;
203    type ObGenMap = Map::VertexMap;
204    type MorGenMap = Map::EdgeMap;
205
206    fn ob_generator_map(&self) -> &Self::ObGenMap {
207        self.map.vertex_map()
208    }
209    fn mor_generator_map(&self) -> &Self::MorGenMap {
210        self.map.edge_map()
211    }
212}
213
214/// Auxiliary struct for the morphism map of a functor out of an f.p. category.
215#[derive(RefCast)]
216#[repr(transparent)]
217pub struct FpFunctorMorMap<'a, Map, Cod>(FpFunctor<'a, Map, Cod>);
218
219impl<'a, V, E, Ob, Mor, Map, Cod> Mapping for FpFunctorMorMap<'a, Map, Cod>
220where
221    V: Eq + Clone,
222    E: Eq + Clone,
223    Mor: Eq + Clone,
224    Map: GraphMapping<DomV = V, DomE = E, CodV = Ob, CodE = Mor>,
225    Cod: Category<Ob = Ob, Mor = Mor>,
226{
227    type Dom = Path<V, E>;
228    type Cod = Mor;
229
230    fn apply(&self, path: Path<V, E>) -> Option<Mor> {
231        path.partial_map(|v| self.0.map.apply_vertex(v), |e| self.0.map.apply_edge(e))
232            .map(|path| self.0.cod.compose(path))
233    }
234
235    fn is_set(&self, path: &Path<V, E>) -> bool {
236        match path {
237            Path::Id(v) => self.0.map.is_vertex_assigned(v),
238            Path::Seq(edges) => edges.iter().all(|e| self.0.map.is_edge_assigned(e)),
239        }
240    }
241}
242
243impl<'a, V, E, Ob, Mor, Map, Cod> FpFunctor<'a, Map, Cod>
244where
245    V: Eq + Clone + Hash,
246    E: Eq + Clone + Hash,
247    Ob: Eq + Clone,
248    Mor: Eq + Clone,
249    Map: GraphMapping<DomV = V, DomE = E, CodV = Ob, CodE = Mor>,
250    Cod: Category<Ob = Ob, Mor = Mor>,
251{
252    /// Validates that the functor is well-defined on the given f.p. category.
253    pub fn validate_on(
254        &self,
255        dom: &FpCategory<V, E>,
256    ) -> Result<(), NonEmpty<InvalidFpFunctor<V, E>>> {
257        crate::validate::wrap_errors(self.iter_invalid_on(dom))
258    }
259
260    /// Iterates over failures to be functorial on the given f.p. category.
261    pub fn iter_invalid_on<'b>(
262        &'b self,
263        dom: &'b FpCategory<V, E>,
264    ) -> impl Iterator<Item = InvalidFpFunctor<V, E>> + 'b {
265        let generator_errors =
266            GraphMorphism(self.map, dom.generators(), UnderlyingGraph::ref_cast(self.cod))
267                .iter_invalid()
268                .map(|err| match err {
269                    InvalidGraphMorphism::Vertex(v) => InvalidFpFunctor::ObGen(v),
270                    InvalidGraphMorphism::Edge(e) => InvalidFpFunctor::MorGen(e),
271                    InvalidGraphMorphism::Src(e) => InvalidFpFunctor::Dom(e),
272                    InvalidGraphMorphism::Tgt(e) => InvalidFpFunctor::Cod(e),
273                });
274        let equation_errors = dom.equations().enumerate().filter_map(|(id, eq)| {
275            let map = self.mor_map();
276            if let (Some(lhs), Some(rhs)) = (map.apply_to_ref(&eq.lhs), map.apply_to_ref(&eq.rhs))
277                && !self.cod.morphisms_are_equal(lhs, rhs)
278            {
279                Some(InvalidFpFunctor::Eq(id))
280            } else {
281                None
282            }
283        });
284        generator_errors.chain(equation_errors)
285    }
286}
287
288/// A failure of a map out of an f.p. category to be functorial.
289#[derive(Debug, Error, PartialEq, Eq)]
290pub enum InvalidFpFunctor<V, E> {
291    /// An object generator not mapped to an object in the codomain category.
292    #[error("Object generator `{0}` is not mapped to an object in the codomain")]
293    ObGen(V),
294
295    /// A morphism generator not mapped to a morphism in the codomain category.
296    #[error("Morphism generator `{0}` is not mapped to a morphism in the codomain")]
297    MorGen(E),
298
299    /// A morphism generator whose domain is not preserved.
300    #[error("Domain of morphism generator `{0}` is not preserved")]
301    Dom(E),
302
303    /// A morphism generator whose codomain is not preserved.
304    #[error("Codomain of morphism generator `{0}` is not preserved")]
305    Cod(E),
306
307    /// A path equation in domain presentation that is not respected.
308    #[error("Path equation `{0}` is not respected")]
309    Eq(usize),
310}
311
312#[cfg(test)]
313mod tests {
314    use super::*;
315    use crate::one::fp_category::{sch_graph, sch_hgraph, sch_sgraph};
316    use crate::zero::{HashColumn, name};
317
318    /// Isomorphism b/w the schemas for half-edge graphs and symmetric graphs.
319    ///
320    /// Reference: <https://blog.algebraicjulia.org/post/2020/09/cset-graphs-2/>.
321    #[test]
322    fn sch_sgraph_to_hgraph() {
323        let (sch_hgraph, sch_sgraph) = (sch_hgraph(), sch_sgraph());
324        let ob_map = HashColumn::from_iter([(name("V"), name("V")), (name("E"), name("H"))]);
325        let mor_map = HashColumn::from_iter([
326            (name("src"), Path::single(name("vert"))),
327            (name("tgt"), Path::pair(name("inv"), name("vert"))),
328            (name("inv"), Path::single(name("inv"))),
329        ]);
330        let data = FpFunctorData::new(ob_map, mor_map);
331        let functor = data.functor_into(&sch_hgraph);
332        assert_eq!(functor.apply_ob(name("E")), Some(name("H")));
333        assert_eq!(
334            functor.apply_mor(Path::pair(name("inv"), name("src"))),
335            Some(Path::pair(name("inv"), name("vert")))
336        );
337        assert!(functor.validate_on(&sch_sgraph).is_ok());
338    }
339
340    /// Non-functor from schema for symmetric graphs to schema for graphs.
341    #[test]
342    fn sch_sgraph_to_graph() {
343        let (sch_graph, sch_sgraph) = (sch_graph(), sch_sgraph());
344        let ob_map = HashColumn::from_iter([(name("V"), name("V")), (name("E"), name("E"))]);
345        let mor_map = HashColumn::from_iter([
346            (name("src"), Path::single(name("src"))),
347            (name("tgt"), Path::single(name("tgt"))),
348            (name("inv"), Path::empty(name("E"))),
349        ]);
350        let data = FpFunctorData::new(ob_map, mor_map);
351        let functor = data.functor_into(&sch_graph);
352        // Two equations fail, namely that `inv` swaps `src` and `tgt`.
353        assert_eq!(functor.validate_on(&sch_sgraph).map_err(|errs| errs.len()), Err(2));
354    }
355}
catlog/one/functor.rs

catlog/one/
functor.rs
