catlog/dbl/
category.rs

1//! Virtual double categories.
2//!
3//! # Background
4//!
5//! A [*virtual double
6//! category*](https://ncatlab.org/nlab/show/virtual+double+category) (VDC) is like
7//! a double category, except that there is no external composition operation on
8//! proarrows or cells. Rather, a cell has a domain that is a path of proarrows (a
9//! "virtual" composite). The name "virtual double category" was introduced by
10//! [Cruttwell and Shulman](crate::refs::GeneralizedMulticategories) but the concept
11//! has gone by many other names, notably *fc-multicategory* ([Leinster
12//! 2004](crate::refs::HigherOperads)).
13//!
14//! Composites* of proarrows in a VDC, if they exist, are represented by cells
15//! satsifying a universal property ([Cruttwell-Shulman
16//! 2008](crate::refs::GeneralizedMulticategories), Section 5). In our usage of
17//! virtual double categories as double theories, we will assume that *units*
18//! (nullary composites) exist. We will not assume that any other composites exist,
19//! though often they do.
20//!
21//! Virtual double categories have pros and cons compared with ordinary double
22//! categories. We prefer VDCs in `catlog` because pastings of cells are much
23//! simpler in a VDC than in a double category: a pasting diagram in VDC is a
24//! well-typed [tree](super::tree) of cells, rather than a kind of planar string
25//! diagram, and the notorious
26//! [pinwheel](https://ncatlab.org/nlab/show/double+category#Unbiased) obstruction
27//! to composition in a double category does not arise in VDCs.
28//!
29//! # Examples
30//!
31//! A [double theory](super::theory) is "just" a unital virtual double category, so
32//! any double theory in the standard library is an example of a VDC. For testing
33//! purposes, this module directly implements several minimal examples of VDCs,
34//! namely ["walking"](https://ncatlab.org/nlab/show/walking+structure) categorical
35//! structures that can be interpreted in any VDC:
36//!
37//! - the [walking category](WalkingCategory)
38//! - the [walking functor](WalkingFunctor)
39//! - the [walking bimodule](WalkingBimodule) or profunctor
40//!
41//! The walking category and bimodule can be seen as discrete double theories, while
42//! the walking functor is a simple double theory, but here they are implemented at
43//! the type level rather than as instances of general data structures.
44
45use derive_more::From;
46use ref_cast::RefCast;
47use std::ops::Range;
48
49use super::graph::{EdgeGraph, VDblGraph};
50use super::tree::DblTree;
51use crate::dbl::DblNode;
52use crate::one::{Category, Path, tree};
53
54/// A virtual double category (VDC).
55///
56/// See the [module-level docs](super::category) for background on VDCs.
57pub trait VDblCategory {
58    /// Type of objects in the VDC.
59    type Ob: Eq + Clone;
60
61    /// Type of arrows (tight morphisms) in the VDC.
62    type Arr: Eq + Clone;
63
64    /// Type of proarrows (loose morphisms) in the VDC.
65    type Pro: Eq + Clone;
66
67    /// Type of cells in the VDC.
68    type Cell: Eq + Clone;
69
70    /// Does the object belong to the VDC?
71    fn has_ob(&self, ob: &Self::Ob) -> bool;
72
73    /// Does the arrow belong to the VDC?
74    fn has_arrow(&self, arr: &Self::Arr) -> bool;
75
76    /// Does the proarrow belong to the VDC?
77    fn has_proarrow(&self, pro: &Self::Pro) -> bool;
78
79    /// Does the cell belong to the VDC?
80    fn has_cell(&self, cell: &Self::Cell) -> bool;
81
82    /// Gets the domain of an arrow.
83    fn dom(&self, f: &Self::Arr) -> Self::Ob;
84
85    /// Gets the codomain of an arrow.
86    fn cod(&self, f: &Self::Arr) -> Self::Ob;
87
88    /// Gets the source of a proarrow.
89    fn src(&self, m: &Self::Pro) -> Self::Ob;
90
91    /// Gets the target of a proarrow.
92    fn tgt(&self, m: &Self::Pro) -> Self::Ob;
93
94    /// Gets the domain of a cell, a path of proarrows.
95    fn cell_dom(&self, cell: &Self::Cell) -> Path<Self::Ob, Self::Pro>;
96
97    /// Gets the codomain of a cell, a single proarrow.
98    fn cell_cod(&self, cell: &Self::Cell) -> Self::Pro;
99
100    /// Gets the source of a cell, an arrow.
101    fn cell_src(&self, cell: &Self::Cell) -> Self::Arr;
102
103    /// Gets the target of a cell, an edge.
104    fn cell_tgt(&self, cell: &Self::Cell) -> Self::Arr;
105
106    /// Gets the arity of a cell.
107    ///
108    /// The default implementation returns the length of the cell's domain.
109    fn arity(&self, cell: &Self::Cell) -> usize {
110        self.cell_dom(cell).len()
111    }
112
113    /// Composes a path of arrows in the VDC.
114    fn compose(&self, path: Path<Self::Ob, Self::Arr>) -> Self::Arr;
115
116    /// Composes a pair of arrows with compatible (co)domains.
117    fn compose2(&self, f: Self::Arr, g: Self::Arr) -> Self::Arr {
118        self.compose(Path::pair(f, g))
119    }
120
121    /// Constructs the identity arrow at an object.
122    fn id(&self, x: Self::Ob) -> Self::Arr {
123        self.compose(Path::empty(x))
124    }
125
126    /// Composes a tree of cells in the VDC.
127    fn compose_cells(&self, tree: DblTree<Self::Arr, Self::Pro, Self::Cell>) -> Self::Cell;
128
129    /// Composes a two-layer pasting of cells.
130    fn compose_cells2(
131        &self, αs: impl IntoIterator<Item = Self::Cell>, β: Self::Cell
132    ) -> Self::Cell
133    where
134        Self: Sized,
135    {
136        let graph = UnderlyingDblGraph::ref_cast(self);
137        self.compose_cells(DblTree::two_level(αs, β, graph))
138    }
139
140    /// Constructs the identity cell on a proarrow.
141    fn id_cell(&self, m: Self::Pro) -> Self::Cell {
142        self.compose_cells(DblTree::empty(m))
143    }
144}
145
146/// A virtual double category with some or all chosen composites.
147///
148/// Like anything defined by a universal property, composites in a VDC are not
149/// strictly unique if they exist but they *are* unique up to unique isomorphism. As
150/// often when working with (co)limits, this trait assumes that a *choice* of
151/// composites has been made whenever they are exist. We do not attempt to
152/// "recognize" whether an arbitrary cell has the relevant universal property.
153pub trait VDCWithComposites: VDblCategory {
154    /// Does the path of proarrows have a chosen composite?
155    ///
156    /// The default implementation checks whether [`composite`](Self::composite)
157    /// returns something.
158    fn has_composite(&self, path: &Path<Self::Ob, Self::Pro>) -> bool {
159        self.composite(path.clone()).is_some()
160    }
161
162    /// Does the object have a chosen unit?
163    ///
164    /// The default implementation checks whether [`unit`](Self::unit) returns
165    /// something.
166    fn has_unit(&self, x: &Self::Ob) -> bool {
167        self.unit(x.clone()).is_some()
168    }
169
170    /// Gets the chosen cell witnessing a composite of proarrows, if there is one.
171    ///
172    /// Such a cell is called an **extension or **opcartesian** cell.
173    fn composite_ext(&self, path: Path<Self::Ob, Self::Pro>) -> Option<Self::Cell>;
174
175    /// Gets the chosen cell witnessing a composite of two proarrows, if there is one.
176    fn composite2_ext(&self, m: Self::Pro, n: Self::Pro) -> Option<Self::Cell> {
177        self.composite_ext(Path::pair(m, n))
178    }
179
180    /// Gets the chosen composite for a path of proarrows, if there is one.
181    ///
182    /// The default implementation returns the codomain of the extension cell from
183    /// [`composite_ext`](Self::composite_ext).
184    fn composite(&self, path: Path<Self::Ob, Self::Pro>) -> Option<Self::Pro> {
185        self.composite_ext(path).map(|α| self.cell_cod(&α))
186    }
187
188    /// Gets the chosen composite for a pair of consecutive proarrows, if there is one.
189    fn composite2(&self, m: Self::Pro, n: Self::Pro) -> Option<Self::Pro> {
190        self.composite(Path::pair(m, n))
191    }
192
193    /// Gets the chosen extension cell for an object, if there is one.
194    ///
195    /// Such a cell is an [extension](Self::composite_ext) or opcartesian cell
196    /// in the nullary case.
197    fn unit_ext(&self, x: Self::Ob) -> Option<Self::Cell> {
198        self.composite_ext(Path::empty(x))
199    }
200
201    /// Gets the chosen unit for an object, if there is one.
202    ///
203    /// The default implementation returns the codomain of the extension cell from
204    /// [`unit_ext`](Self::unit_ext).
205    fn unit(&self, x: Self::Ob) -> Option<Self::Pro> {
206        self.unit_ext(x).map(|α| self.cell_cod(&α))
207    }
208
209    /// Constructs the unit cell on an arrow, if there is one.
210    ///
211    /// The default implementation constructs the unit cell for an arrow by
212    /// using the unit extension (if it exists) on the codomain to form a cell
213    /// with the original arrow and factorising that cell through the unit.
214    fn unit_arrow(&self, f: Self::Arr) -> Option<Self::Cell> {
215        let y = self.cod(&f);
216        let y_ext = self.unit_ext(y)?;
217        let cell = self.compose_cells(DblTree(
218            tree::OpenTree::linear(vec![DblNode::Spine(f), DblNode::Cell(y_ext)]).unwrap(),
219        ));
220        self.through_unit(cell, 0)
221    }
222
223    /// Factorizes a cell through a composite of proarrows.
224    ///
225    /// The subpath of the domain path at the given range is replaced with the
226    /// composite of that subpath, if the composite exists. This is the universal
227    /// property of the composite.
228    fn through_composite(&self, cell: Self::Cell, range: Range<usize>) -> Option<Self::Cell>;
229
230    /// Factorizes a cell through the unit proarrow for an object.
231    ///
232    /// A unit proarrow is inserted into the domain path at the given index, if the
233    /// unit exists. This is the universal property of the unit.
234    fn through_unit(&self, cell: Self::Cell, index: usize) -> Option<Self::Cell> {
235        self.through_composite(cell, index..index)
236    }
237}
238
239/// The underlying category of objects and arrows in a VDC.
240#[derive(From, RefCast)]
241#[repr(transparent)]
242pub struct UnderlyingCategory<VDC>(pub VDC);
243
244impl<VDC: VDblCategory> Category for UnderlyingCategory<VDC> {
245    type Ob = VDC::Ob;
246    type Mor = VDC::Arr;
247
248    fn has_ob(&self, x: &Self::Ob) -> bool {
249        self.0.has_ob(x)
250    }
251    fn has_mor(&self, f: &Self::Mor) -> bool {
252        self.0.has_arrow(f)
253    }
254    fn dom(&self, f: &Self::Mor) -> Self::Ob {
255        self.0.dom(f)
256    }
257    fn cod(&self, f: &Self::Mor) -> Self::Ob {
258        self.0.cod(f)
259    }
260    fn compose(&self, path: Path<Self::Ob, Self::Mor>) -> Self::Mor {
261        self.0.compose(path)
262    }
263    fn compose2(&self, f: Self::Mor, g: Self::Mor) -> Self::Mor {
264        self.0.compose2(f, g)
265    }
266    fn id(&self, x: Self::Ob) -> Self::Mor {
267        self.0.id(x)
268    }
269}
270
271/// The underlying [virtual double graph](VDblGraph) of a VDC.
272#[derive(From, RefCast)]
273#[repr(transparent)]
274pub struct UnderlyingDblGraph<VDC>(pub VDC);
275
276impl<VDC: VDblCategory> VDblGraph for UnderlyingDblGraph<VDC> {
277    type V = VDC::Ob;
278    type E = VDC::Arr;
279    type ProE = VDC::Pro;
280    type Sq = VDC::Cell;
281
282    fn has_vertex(&self, v: &Self::V) -> bool {
283        self.0.has_ob(v)
284    }
285    fn has_edge(&self, e: &Self::E) -> bool {
286        self.0.has_arrow(e)
287    }
288    fn has_proedge(&self, p: &Self::ProE) -> bool {
289        self.0.has_proarrow(p)
290    }
291    fn has_square(&self, sq: &Self::Sq) -> bool {
292        self.0.has_cell(sq)
293    }
294
295    fn dom(&self, e: &Self::E) -> Self::V {
296        self.0.dom(e)
297    }
298    fn cod(&self, e: &Self::E) -> Self::V {
299        self.0.cod(e)
300    }
301    fn src(&self, p: &Self::ProE) -> Self::V {
302        self.0.src(p)
303    }
304    fn tgt(&self, p: &Self::ProE) -> Self::V {
305        self.0.tgt(p)
306    }
307
308    fn square_dom(&self, sq: &Self::Sq) -> Path<Self::V, Self::ProE> {
309        self.0.cell_dom(sq)
310    }
311    fn square_cod(&self, sq: &Self::Sq) -> Self::ProE {
312        self.0.cell_cod(sq)
313    }
314    fn square_src(&self, sq: &Self::Sq) -> Self::E {
315        self.0.cell_src(sq)
316    }
317    fn square_tgt(&self, sq: &Self::Sq) -> Self::E {
318        self.0.cell_tgt(sq)
319    }
320    fn arity(&self, sq: &Self::Sq) -> usize {
321        self.0.arity(sq)
322    }
323}
324
325/// The VDC freely generated by a virtual double graph.
326///
327/// A virtual double graph freely generated a virtual double category, generalizing
328/// how a graph [freely generates](crate::one::category::FreeCategory) a category.
329/// This is not, however, the most general way to freely generate a VDC. A "virtual
330/// double computad" freely generates a VDC but allows the generating cells to have
331/// sources and targets that are *paths* of generating arrows.
332#[derive(From, RefCast)]
333#[repr(transparent)]
334pub struct FreeVDblCategory<G: VDblGraph>(pub G);
335
336impl<G: VDblGraph> VDblCategory for FreeVDblCategory<G>
337where
338    G::ProE: std::fmt::Debug,
339{
340    type Ob = G::V;
341    type Arr = Path<G::V, G::E>;
342    type Pro = G::ProE;
343    type Cell = DblTree<G::E, G::ProE, G::Sq>;
344
345    fn has_ob(&self, ob: &Self::Ob) -> bool {
346        self.0.has_vertex(ob)
347    }
348    fn has_arrow(&self, path: &Self::Arr) -> bool {
349        path.contained_in(EdgeGraph::ref_cast(&self.0))
350    }
351    fn has_proarrow(&self, pro: &Self::Pro) -> bool {
352        self.0.has_proedge(pro)
353    }
354    fn has_cell(&self, tree: &Self::Cell) -> bool {
355        tree.contained_in(&self.0)
356    }
357
358    fn dom(&self, path: &Self::Arr) -> Self::Ob {
359        path.src(EdgeGraph::ref_cast(&self.0))
360    }
361    fn cod(&self, path: &Self::Arr) -> Self::Ob {
362        path.tgt(EdgeGraph::ref_cast(&self.0))
363    }
364    fn src(&self, m: &Self::Pro) -> Self::Ob {
365        self.0.src(m)
366    }
367    fn tgt(&self, m: &Self::Pro) -> Self::Ob {
368        self.0.tgt(m)
369    }
370
371    fn cell_dom(&self, tree: &Self::Cell) -> Path<Self::Ob, Self::Pro> {
372        tree.dom(&self.0)
373    }
374    fn cell_cod(&self, tree: &Self::Cell) -> Self::Pro {
375        tree.cod(&self.0)
376    }
377    fn cell_src(&self, tree: &Self::Cell) -> Self::Arr {
378        tree.src(&self.0)
379    }
380    fn cell_tgt(&self, tree: &Self::Cell) -> Self::Arr {
381        tree.tgt(&self.0)
382    }
383    fn arity(&self, tree: &Self::Cell) -> usize {
384        tree.arity(&self.0)
385    }
386
387    fn compose(&self, path: Path<Self::Ob, Self::Arr>) -> Self::Arr {
388        path.flatten_in(EdgeGraph::ref_cast(&self.0))
389            .expect("Path of paths should be valid before flattening")
390    }
391    fn compose_cells(&self, tree: DblTree<Self::Arr, Self::Pro, Self::Cell>) -> Self::Cell {
392        tree.flatten()
393    }
394}
395
396/// The walking category as a VDC.
397///
398/// The walking category is the simplest example of a virtual double category that
399/// has units (and in fact all composites). Specifically, the **walking category**
400/// is the unital VDC freely generated by a single object, here called `()`.
401///
402/// The concept of a category can be interpreted in any virtual double category: a
403/// category object** in a VDC is a functor from the walking category into that
404/// VDC. In particular, a category object in spans is a category in the ordinary
405/// sense.
406pub struct WalkingCategory();
407
408impl VDblCategory for WalkingCategory {
409    type Ob = ();
410    type Arr = ();
411    type Pro = ();
412    type Cell = usize;
413
414    fn has_ob(&self, _: &Self::Ob) -> bool {
415        true
416    }
417    fn has_arrow(&self, _: &Self::Arr) -> bool {
418        true
419    }
420    fn has_proarrow(&self, _: &Self::Pro) -> bool {
421        true
422    }
423    fn has_cell(&self, _: &Self::Cell) -> bool {
424        true
425    }
426
427    fn dom(&self, _: &Self::Arr) -> Self::Ob {}
428    fn cod(&self, _: &Self::Arr) -> Self::Ob {}
429    fn src(&self, _: &Self::Pro) -> Self::Ob {}
430    fn tgt(&self, _: &Self::Pro) -> Self::Ob {}
431
432    fn cell_dom(&self, n: &Self::Cell) -> Path<Self::Ob, Self::Pro> {
433        Path::repeat_n((), (), *n)
434    }
435    fn cell_cod(&self, _: &Self::Cell) -> Self::Pro {}
436    fn cell_src(&self, _: &Self::Cell) -> Self::Arr {}
437    fn cell_tgt(&self, _: &Self::Cell) -> Self::Arr {}
438
439    fn compose(&self, _: Path<Self::Ob, Self::Arr>) -> Self::Arr {}
440    fn compose_cells(&self, tree: DblTree<Self::Arr, Self::Pro, Self::Cell>) -> Self::Cell {
441        tree.dom(UnderlyingDblGraph::ref_cast(self)).len()
442    }
443}
444
445impl VDCWithComposites for WalkingCategory {
446    /// In the walking category, every cell is an extension.
447    fn composite_ext(&self, path: Path<Self::Ob, Self::Pro>) -> Option<Self::Cell> {
448        Some(path.len())
449    }
450
451    fn through_composite(&self, n: Self::Cell, range: Range<usize>) -> Option<Self::Cell> {
452        Some(n + 1 - range.len())
453    }
454}
455
456#[allow(non_snake_case)]
457pub mod WalkingBimodule {
458    //! The walking bimodule as a VDC.
459    //!
460    //! The **walking bimodule**, also known as the **walking profunctor**, is the
461    //! unital virtual double category freely generated by a pair of objects, here
462    //! called [`Left`](Ob::Left) and [`Right`](Ob::Right), and a single proarrow
463    //! between them, here called [`Middle`](Pro::Middle). In fact, this VDC has all
464    //! composites.
465    use super::super::graph::ProedgeGraph;
466    use super::*;
467
468    /// Struct representing the walking bimodule.
469    pub struct Main();
470
471    /// Type of objects in the walking bimodule.
472    #[derive(Clone, Copy, Debug, PartialEq, Eq)]
473    pub enum Ob {
474        /// Object representing the source of the bimodule.
475        Left,
476        /// Object representing the target of the bimodule.
477        Right,
478    }
479
480    /// Type of proarrows in the walking bimodule.
481    #[derive(Clone, Copy, Debug, PartialEq, Eq)]
482    pub enum Pro {
483        /// Unit proarrow on the object [`Left`](Ob::Left).
484        Left,
485        /// Generating proarrow from [`Left`](Ob::Left) to [`Right`](Ob::Right).
486        Middle,
487        /// Unit proarrow on the object [`Right`](Ob::Right).
488        Right,
489    }
490
491    impl Pro {
492        fn src(self) -> Ob {
493            match self {
494                Pro::Left => Ob::Left,
495                Pro::Middle => Ob::Left,
496                Pro::Right => Ob::Right,
497            }
498        }
499
500        fn tgt(self) -> Ob {
501            match self {
502                Pro::Left => Ob::Left,
503                Pro::Middle => Ob::Right,
504                Pro::Right => Ob::Right,
505            }
506        }
507    }
508
509    impl VDblCategory for Main {
510        type Ob = Ob;
511        type Arr = Ob;
512        type Pro = Pro;
513        type Cell = Path<Ob, Pro>;
514
515        fn has_ob(&self, _: &Self::Ob) -> bool {
516            true
517        }
518        fn has_arrow(&self, _: &Self::Arr) -> bool {
519            true
520        }
521        fn has_proarrow(&self, _: &Self::Pro) -> bool {
522            true
523        }
524        fn has_cell(&self, path: &Path<Ob, Pro>) -> bool {
525            path.contained_in(ProedgeGraph::ref_cast(UnderlyingDblGraph::ref_cast(self)))
526        }
527
528        fn dom(&self, f: &Self::Arr) -> Self::Ob {
529            *f
530        }
531        fn cod(&self, f: &Self::Arr) -> Self::Ob {
532            *f
533        }
534        fn src(&self, m: &Self::Pro) -> Self::Ob {
535            m.src()
536        }
537        fn tgt(&self, m: &Self::Pro) -> Self::Ob {
538            m.tgt()
539        }
540
541        fn cell_dom(&self, path: &Path<Ob, Pro>) -> Path<Self::Ob, Self::Pro> {
542            path.clone()
543        }
544        fn cell_cod(&self, path: &Path<Ob, Pro>) -> Self::Pro {
545            assert!(self.has_cell(path));
546            match path {
547                Path::Id(Ob::Left) => Pro::Left,
548                Path::Id(Ob::Right) => Pro::Right,
549                Path::Seq(pros) => {
550                    *pros.iter().find(|m| **m == Pro::Middle).unwrap_or_else(|| pros.first())
551                }
552            }
553        }
554        fn cell_src(&self, path: &Path<Ob, Pro>) -> Self::Arr {
555            path.src(ProedgeGraph::ref_cast(UnderlyingDblGraph::ref_cast(self)))
556        }
557        fn cell_tgt(&self, path: &Path<Ob, Pro>) -> Self::Arr {
558            path.tgt(ProedgeGraph::ref_cast(UnderlyingDblGraph::ref_cast(self)))
559        }
560
561        fn compose(&self, path: Path<Self::Ob, Self::Arr>) -> Self::Arr {
562            match path {
563                Path::Id(x) => x,
564                Path::Seq(arrows) => *arrows.first(),
565            }
566        }
567        fn compose_cells(&self, tree: DblTree<Self::Arr, Self::Pro, Self::Cell>) -> Self::Cell {
568            let path = tree.dom(UnderlyingDblGraph::ref_cast(self));
569            assert!(self.has_cell(&path));
570            path
571        }
572    }
573
574    impl VDCWithComposites for Main {
575        /// In the walking bimodule, every cell is an extension.
576        fn composite_ext(&self, path: Path<Self::Ob, Self::Pro>) -> Option<Self::Cell> {
577            Some(path)
578        }
579
580        fn through_composite(&self, path: Self::Cell, range: Range<usize>) -> Option<Self::Cell> {
581            let graph = ProedgeGraph::ref_cast(UnderlyingDblGraph::ref_cast(self));
582            Some(path.replace_subpath(graph, range, |subpath| self.cell_cod(&subpath).into()))
583        }
584    }
585}
586
587#[allow(non_snake_case)]
588pub mod WalkingFunctor {
589    //! The walking functor as a VDC.
590    //!
591    //! The **walking functor** is the unital virtual double category freely
592    //! generated by a pair of objects, here called [`Zero`](Ob::Zero) and
593    //! [`One`](Ob::One), and a single arrow between them.
594    use super::super::graph::{EdgeGraph, ProedgeGraph};
595    use super::*;
596
597    /// Struct representing the walking functor.
598    pub struct Main();
599
600    /// Type of objects in the walking functor.
601    #[derive(Clone, Copy, Debug, PartialEq, Eq)]
602    pub enum Ob {
603        /// Object representing the domain of the functor.
604        Zero,
605        /// Object representing the codomain of the functor.
606        One,
607    }
608
609    /// Type of arrows in the walking functor.
610    #[derive(Clone, Copy, Debug, PartialEq, Eq)]
611    pub enum Arr {
612        /// Identity arrow on the object [`Zero`](Ob::Zero).
613        Zero,
614        /// Identity arrow on the object [`One`](Ob::One).
615        One,
616        /// Generating arrow from [`Zero`](Ob::Zero) to [`One`](Ob::One).
617        Arrow,
618    }
619
620    impl Arr {
621        fn dom(self) -> Ob {
622            match self {
623                Arr::Zero => Ob::Zero,
624                Arr::Arrow => Ob::Zero,
625                Arr::One => Ob::One,
626            }
627        }
628
629        fn cod(self) -> Ob {
630            match self {
631                Arr::Zero => Ob::Zero,
632                Arr::Arrow => Ob::One,
633                Arr::One => Ob::One,
634            }
635        }
636    }
637
638    /// Type of cells in the walking functor.
639    #[derive(Clone, Copy, Debug, PartialEq, Eq)]
640    pub enum Cell {
641        /// Cell bounded by identity arrows on the object [`Zero`](Ob::Zero).
642        Zero(usize),
643        /// Cell bounded by identity arrows on the object [`One`](Ob::One).
644        One(usize),
645        /// Cell bounded by the generating arrow.
646        Arrow(usize),
647    }
648
649    impl Cell {
650        fn with_src_and_tgt(f: Arr, n: usize) -> Self {
651            match f {
652                Arr::Zero => Cell::Zero(n),
653                Arr::Arrow => Cell::Arrow(n),
654                Arr::One => Cell::One(n),
655            }
656        }
657
658        fn dom(self) -> Path<Ob, Ob> {
659            let (ob, n) = match self {
660                Cell::Zero(n) => (Ob::Zero, n),
661                Cell::Arrow(n) => (Ob::Zero, n),
662                Cell::One(n) => (Ob::One, n),
663            };
664            Path::repeat_n(ob, ob, n)
665        }
666
667        fn cod(self) -> Ob {
668            match self {
669                Cell::Zero(_) => Ob::Zero,
670                Cell::Arrow(_) => Ob::One,
671                Cell::One(_) => Ob::One,
672            }
673        }
674
675        fn src(self) -> Arr {
676            match self {
677                Cell::Zero(_) => Arr::Zero,
678                Cell::Arrow(_) => Arr::Arrow,
679                Cell::One(_) => Arr::One,
680            }
681        }
682
683        fn tgt(self) -> Arr {
684            self.src()
685        }
686
687        fn map<F>(self, f: F) -> Self
688        where
689            F: FnOnce(usize) -> usize,
690        {
691            match self {
692                Cell::Zero(n) => Cell::Zero(f(n)),
693                Cell::Arrow(n) => Cell::Arrow(f(n)),
694                Cell::One(n) => Cell::One(f(n)),
695            }
696        }
697    }
698
699    impl VDblCategory for Main {
700        type Ob = Ob;
701        type Arr = Arr;
702        type Pro = Ob;
703        type Cell = Cell;
704
705        fn has_ob(&self, _: &Self::Ob) -> bool {
706            true
707        }
708        fn has_arrow(&self, _: &Self::Arr) -> bool {
709            true
710        }
711        fn has_proarrow(&self, _: &Self::Pro) -> bool {
712            true
713        }
714        fn has_cell(&self, _: &Self::Cell) -> bool {
715            true
716        }
717
718        fn dom(&self, f: &Self::Arr) -> Self::Ob {
719            f.dom()
720        }
721        fn cod(&self, f: &Self::Arr) -> Self::Ob {
722            f.cod()
723        }
724        fn src(&self, m: &Self::Pro) -> Self::Ob {
725            *m
726        }
727        fn tgt(&self, m: &Self::Pro) -> Self::Ob {
728            *m
729        }
730
731        fn cell_dom(&self, cell: &Self::Cell) -> Path<Self::Ob, Self::Pro> {
732            cell.dom()
733        }
734        fn cell_cod(&self, cell: &Self::Cell) -> Self::Pro {
735            cell.cod()
736        }
737        fn cell_src(&self, cell: &Self::Cell) -> Self::Arr {
738            cell.src()
739        }
740        fn cell_tgt(&self, cell: &Self::Cell) -> Self::Arr {
741            cell.tgt()
742        }
743
744        fn compose(&self, path: Path<Self::Ob, Self::Arr>) -> Self::Arr {
745            assert!(path.contained_in(EdgeGraph::ref_cast(UnderlyingDblGraph::ref_cast(self))));
746            match path {
747                Path::Id(Ob::Zero) => Arr::Zero,
748                Path::Id(Ob::One) => Arr::One,
749                Path::Seq(arrows) => {
750                    *arrows.iter().find(|f| **f == Arr::Arrow).unwrap_or_else(|| arrows.first())
751                }
752            }
753        }
754        fn compose_cells(&self, tree: DblTree<Self::Arr, Self::Pro, Self::Cell>) -> Self::Cell {
755            let graph = UnderlyingDblGraph::ref_cast(self);
756            let (f, g) = (self.compose(tree.src(graph)), self.compose(tree.tgt(graph)));
757            assert_eq!(f, g, "Cells in walking functor have the same source and target");
758            Cell::with_src_and_tgt(f, tree.arity(graph))
759        }
760    }
761
762    impl VDCWithComposites for Main {
763        fn composite_ext(&self, path: Path<Self::Ob, Self::Pro>) -> Option<Self::Cell> {
764            let graph = ProedgeGraph::ref_cast(UnderlyingDblGraph::ref_cast(self));
765            let (x, y) = (path.src(graph), path.tgt(graph));
766            assert_eq!(x, y, "Paths in walking functor have the same source and target");
767            Some(Cell::with_src_and_tgt(self.id(x), path.len()))
768        }
769
770        fn through_composite(&self, cell: Self::Cell, range: Range<usize>) -> Option<Self::Cell> {
771            Some(cell.map(|n| n + 1 - range.len()))
772        }
773    }
774}
775
776#[cfg(test)]
777mod tests {
778    use super::*;
779
780    #[test]
781    fn walking_category() {
782        let vdc = WalkingCategory();
783        assert!(vdc.has_unit(&()));
784        assert_eq!(vdc.unit(()), Some(()));
785        assert_eq!(vdc.unit_ext(()), Some(0));
786        assert_eq!(vdc.through_unit(2, 1), Some(3));
787        assert_eq!(vdc.cell_dom(&0), Path::empty(()));
788        assert_eq!(vdc.cell_dom(&2), Path::pair((), ()));
789    }
790
791    #[test]
792    fn walking_bimodule() {
793        use WalkingBimodule::{Ob, Pro};
794
795        let vdc = WalkingBimodule::Main();
796        assert!(vdc.has_unit(&Ob::Left));
797        assert_eq!(vdc.unit(Ob::Left), Some(Pro::Left));
798        let ext = vdc.unit_ext(Ob::Left).unwrap();
799        assert_eq!(vdc.cell_dom(&ext), Path::empty(Ob::Left));
800        assert_eq!(vdc.cell_cod(&ext), Pro::Left);
801
802        let path = Path::from_vec(vec![Pro::Left, Pro::Middle, Pro::Right]).unwrap();
803        assert!(vdc.has_cell(&Path::single(Pro::Middle)));
804        assert!(vdc.has_cell(&path));
805        assert!(!vdc.has_cell(&Path::pair(Pro::Left, Pro::Right)));
806        assert_eq!(vdc.composite(Path::empty(Ob::Left)), Some(Pro::Left));
807        assert_eq!(vdc.composite(Path::empty(Ob::Right)), Some(Pro::Right));
808        assert_eq!(vdc.composite(path), Some(Pro::Middle));
809
810        assert_eq!(
811            vdc.through_unit(Pro::Middle.into(), 0),
812            Some(Path::pair(Pro::Left, Pro::Middle))
813        );
814        assert_eq!(
815            vdc.through_unit(Pro::Middle.into(), 1),
816            Some(Path::pair(Pro::Middle, Pro::Right))
817        );
818    }
819
820    #[test]
821    fn walking_functor() {
822        use WalkingFunctor::{Arr, Cell, Ob};
823
824        let vdc = WalkingFunctor::Main();
825        let cell = Cell::Arrow(2);
826        assert_eq!(vdc.cell_dom(&cell), Path::pair(Ob::Zero, Ob::Zero));
827        assert_eq!(vdc.cell_cod(&cell), Ob::One);
828        assert_eq!(vdc.cell_src(&cell), Arr::Arrow);
829        assert_eq!(vdc.cell_tgt(&cell), Arr::Arrow);
830
831        let ext = vdc.composite_ext(Path::pair(Ob::Zero, Ob::Zero)).unwrap();
832        assert_eq!(vdc.cell_src(&ext), Arr::Zero);
833        assert_eq!(vdc.cell_tgt(&ext), Arr::Zero);
834        let new_cell = vdc.compose_cells2(vec![ext, ext], cell);
835        assert_eq!(vdc.cell_dom(&new_cell).len(), 4);
836
837        assert_eq!(vdc.through_unit(Cell::Arrow(2), 1), Some(Cell::Arrow(3)));
838    }
839}
catlog/dbl/category.rs

catlog/dbl/
category.rs
