open_hypergraphs/functor/
spider.rs

1//! Symmetric Monoidal Hypergraph Functors on Open Hypergraphs
2use crate::array::*;
3use crate::category::*;
4use crate::finite_function::*;
5use crate::indexed_coproduct::*;
6use crate::open_hypergraph::*;
7use crate::operations::*;
8use crate::semifinite::*;
9
10/// Strict symmetric monoidal hypergraph functors
11pub trait Functor<K: ArrayKind, O1, A1, O2, A2> {
12    /// Action on objects
13    fn map_object(a: &SemifiniteFunction<K, O1>) -> IndexedCoproduct<K, SemifiniteFunction<K, O2>>;
14
15    /// Action on arrows
16    fn map_arrow(a: &OpenHypergraph<K, O1, A1>) -> OpenHypergraph<K, O2, A2>;
17}
18
19/// The identity functor, which implements [`Functor`] for any signature.
20pub struct Identity;
21
22impl<K: ArrayKind, O, A> Functor<K, O, A, O, A> for Identity
23where
24    K::Type<K::I>: NaturalArray<K>,
25    K::Type<O>: Array<K, O>,
26    K::Type<A>: Array<K, A>,
27{
28    fn map_object(a: &SemifiniteFunction<K, O>) -> IndexedCoproduct<K, SemifiniteFunction<K, O>> {
29        IndexedCoproduct::elements(a.clone())
30    }
31
32    fn map_arrow(f: &OpenHypergraph<K, O, A>) -> OpenHypergraph<K, O, A> {
33        f.clone()
34    }
35}
36
37////////////////////////////////////////////////////////////////////////////////
38// Spider Functors
39
40pub fn to_operations<K: ArrayKind, O, A>(f: &OpenHypergraph<K, O, A>) -> Operations<K, O, A>
41where
42    K::Type<K::I>: NaturalArray<K>,
43    K::Type<O>: Array<K, O>,
44    K::Type<A>: Array<K, A>,
45{
46    Operations {
47        x: f.h.x.clone(),
48        a: f.h.s.map_semifinite(&f.h.w).unwrap(),
49        b: f.h.t.map_semifinite(&f.h.w).unwrap(),
50    }
51}
52
53fn map_half_spider<K: ArrayKind, O>(
54    w: &IndexedCoproduct<K, SemifiniteFunction<K, O>>,
55    f: &FiniteFunction<K>,
56) -> FiniteFunction<K> {
57    w.sources.injections(f).unwrap()
58}
59
60/// A [`SpiderFunctor`] is a [`Functor`] implemented in terms of its action on a tensoring of
61/// [`Operations`].
62/// This is (generally) easier to implement than [`Functor`] directly.
63///
64// NOTE: [`SpiderFunctor`] does not imply Functor because of the orphan instances rule.
65pub trait SpiderFunctor<K: ArrayKind, O1, A1, O2, A2>: Sized
66where
67    K::Type<K::I>: NaturalArray<K>,
68
69    K::Type<O1>: Array<K, O1>,
70    K::Type<A1>: Array<K, A1>,
71
72    K::Type<O2>: Array<K, O2>,
73    K::Type<A2>: Array<K, A2>,
74{
75    /// Action on objects
76    fn map_object(a: &SemifiniteFunction<K, O1>) -> IndexedCoproduct<K, SemifiniteFunction<K, O2>>;
77
78    /// Often, it's easier to map a list of operations f, g, h into their tensoring F(f) ● F(g) ●
79    /// F(h).
80    /// This efficiently generalises to the implementation of map_arrow.
81    fn map_operations(ops: Operations<K, O1, A1>) -> OpenHypergraph<K, O2, A2>;
82
83    fn map_arrow(f: &OpenHypergraph<K, O1, A1>) -> OpenHypergraph<K, O2, A2> {
84        // Compute the tensoring of operations
85        // Fx = F(x₀) ● F(x₁) ● ... ● F(x_n)
86        let fx = Self::map_operations(to_operations(f));
87
88        // Compute the tensoring of objects
89        // Fw = F(w₀) ● F(w₁) ● ... ● ... F(w_n)
90        let fw = Self::map_object(&f.h.w);
91
92        spider_map_arrow::<K, O1, A1, O2, A2>(f, fw, fx)
93    }
94}
95
96// NOTE: this implementation is factored outside the trait impl so we can use it in the Optic
97// functor implementation as well.
98pub(crate) fn spider_map_arrow<K: ArrayKind, O1, A1, O2, A2>(
99    f: &OpenHypergraph<K, O1, A1>,
100    fw: IndexedCoproduct<K, SemifiniteFunction<K, O2>>,
101    fx: OpenHypergraph<K, O2, A2>,
102) -> OpenHypergraph<K, O2, A2>
103where
104    K::Type<K::I>: NaturalArray<K>,
105
106    K::Type<O1>: Array<K, O1>,
107    K::Type<A1>: Array<K, A1>,
108
109    K::Type<O2>: Array<K, O2>,
110    K::Type<A2>: Array<K, A2>,
111{
112    // Construct the identity map on the wires of F(w)
113    let i = OpenHypergraph::<K, O2, A2>::identity(fw.values.clone());
114
115    let sx = {
116        let fs = map_half_spider(&fw, &f.s);
117        let e_s = map_half_spider(&fw, &f.h.s.values);
118        OpenHypergraph::<K, O2, A2>::spider(fs, i.t.coproduct(&e_s).unwrap(), i.h.w.clone())
119            .unwrap()
120    };
121
122    let yt = {
123        let ft = map_half_spider(&fw, &f.t);
124        let fe_t = map_half_spider(&fw, &f.h.t.values);
125        OpenHypergraph::<K, O2, A2>::spider(i.s.coproduct(&fe_t).unwrap(), ft, i.h.w.clone())
126            .unwrap()
127    };
128
129    // Construct the diagram
130    //
131    //          sx
132    //   _______|___________
133    //   |                 |
134    //
135    //
136    //           /-----------------------------\
137    //  -- F(s)--                               --- F(t) ---
138    //           \---F(e_s)---F(x)----F(e_t)---/
139    //
140    //
141    //                               |_______________________|
142    //                                           |
143    //                                           yt
144
145    sx.compose(&i.tensor(&fx)).unwrap().compose(&yt).unwrap()
146}
147
148impl<K: ArrayKind, O, A> SpiderFunctor<K, O, A, O, A> for Identity
149where
150    K::Type<K::I>: NaturalArray<K>,
151    K::Type<O>: Array<K, O>,
152    K::Type<A>: Array<K, A>,
153{
154    fn map_object(a: &SemifiniteFunction<K, O>) -> IndexedCoproduct<K, SemifiniteFunction<K, O>> {
155        // same action on objects
156        <Self as Functor<K, O, A, O, A>>::map_object(a)
157    }
158
159    fn map_operations(ops: Operations<K, O, A>) -> OpenHypergraph<K, O, A> {
160        OpenHypergraph::tensor_operations(ops)
161    }
162}
open_hypergraphs/functor/spider.rs

open_hypergraphs/functor/
spider.rs
