open_hypergraphs/finite_function/arrow.rs
1use crate::array::*;
2use crate::category::*;
3
4use core::fmt::Debug;
5use core::ops::{Add, BitOr, Shr};
6use num_traits::{One, Zero};
7
8/// A finite function is an array of indices in a range `{0..N}` for some `N ∈ Nat`
9#[derive(Eq)]
10pub struct FiniteFunction<K: ArrayKind> {
11 pub table: K::Index,
12 pub target: K::I,
13}
14
15// Can't use derived PartialEq because it introduces unwanted bound `K: PartialEq`.
16impl<K: ArrayKind> PartialEq for FiniteFunction<K> {
17 fn eq(&self, other: &Self) -> bool {
18 self.table == other.table && self.target == other.target
19 }
20}
21
22// Ad-hoc methods for finite functions
23impl<K: ArrayKind> FiniteFunction<K> {
24 /// Construct a FiniteFunction from a table of indices
25 pub fn new(table: K::Index, target: K::I) -> Option<FiniteFunction<K>> {
26 // If table was nonempty and had a value larger or equal to codomain, this is invalid.
27 // TODO: should check that table min is greater than zero!
28 if let Some(true) = table.max().map(|m| m >= target) {
29 return None;
30 }
31 Some(FiniteFunction { table, target })
32 }
33
34 /// The length-`a` array of zeroes `!_a : a → 1`.
35 /// TODO: doctest
36 pub fn terminal(a: K::I) -> Self {
37 let table = K::Index::fill(K::I::zero(), a);
38 let target = K::I::one();
39 FiniteFunction { table, target }
40 }
41
42 /// Construct the constant finite function `f : a → x + 1 + b`,
43 /// an array of length `a` mapping all elements to `x`.
44 ///
45 /// Note that the *target* of the finite function must be at least `x+1` to be valid.
46 /// This is equivalent to `!_a ; ι₁ ; ι₀`, where
47 ///
48 /// - `!_a : a → 1` is the terminal map
49 /// - `ι₁ : 1 → x+1` and `ι₀ : x+1 → x+1+b` are injections.
50 ///
51 /// ```rust
52 /// # use open_hypergraphs::category::*;
53 /// # use open_hypergraphs::array::vec::*;
54 /// # use open_hypergraphs::finite_function::*;
55 /// let (x, a, b) = (2, 3, 2);
56 ///
57 /// let actual = FiniteFunction::<VecKind>::constant(a, x, b);
58 /// let expected = FiniteFunction::new(VecArray(vec![2, 2, 2]), x + b + 1).unwrap();
59 /// assert_eq!(actual, expected);
60 ///
61 /// // Check equal to `!_a ; ι₁ ; ι₀`
62 /// let i1 = FiniteFunction::<VecKind>::inj1(x, 1);
63 /// let i0 = FiniteFunction::inj0(x + 1, b);
64 /// let f = FiniteFunction::terminal(a);
65 /// let h = f.compose(&i1).expect("b").compose(&i0).expect("c");
66 /// assert_eq!(actual, h);
67 /// ```
68 pub fn constant(a: K::I, x: K::I, b: K::I) -> Self {
69 let table = K::Index::fill(x.clone(), a);
70 let target = x + b + K::I::one(); // We need the +1 to ensure entries in range.
71 FiniteFunction { table, target }
72 }
73
74 /// Directly construct `f ; ι₀` instead of computing by composition.
75 ///
76 /// ```rust
77 /// # use open_hypergraphs::array::vec::*;
78 /// # use open_hypergraphs::category::*;
79 /// # use open_hypergraphs::finite_function::*;
80 /// # let f = FiniteFunction::<VecKind>::identity(5);
81 /// # let b = 3;
82 /// # let i0 = FiniteFunction::<VecKind>::inj0(f.target(), b);
83 /// assert_eq!(Some(f.inject0(b)), &f >> &i0);
84 /// ```
85 pub fn inject0(&self, b: K::I) -> FiniteFunction<K> {
86 FiniteFunction {
87 table: self.table.clone(),
88 target: b + self.target(),
89 }
90 }
91
92 /// Directly construct `f ; ι₁` instead of computing by composition.
93 ///
94 /// ```rust
95 /// # use open_hypergraphs::array::vec::*;
96 /// # use open_hypergraphs::category::*;
97 /// # use open_hypergraphs::finite_function::*;
98 /// # let f = FiniteFunction::<VecKind>::identity(5);
99 /// # let a = 3;
100 /// # let i1 = FiniteFunction::<VecKind>::inj1(a, f.target());
101 /// assert_eq!(Some(f.inject1(a)), &f >> &i1);
102 /// ```
103 pub fn inject1(&self, a: K::I) -> FiniteFunction<K> {
104 FiniteFunction {
105 table: a.clone() + &self.table,
106 target: a + self.target.clone(),
107 }
108 }
109
110 /// Given a finite function `f : A → B`, return the initial map `initial : 0 → B`.
111 pub fn to_initial(&self) -> FiniteFunction<K> {
112 Self::initial(self.target.clone())
113 }
114
115 pub fn coequalizer(&self, other: &Self) -> Option<FiniteFunction<K>> {
116 // if self is parallel to other
117 if self.source() != other.source() || self.target() != other.target() {
118 return None;
119 }
120
121 let (table, target) =
122 K::Index::connected_components(&self.table, &other.table, self.target());
123 Some(FiniteFunction { table, target })
124 }
125
126 pub fn coequalizer_universal(&self, f: &Self) -> Option<Self>
127 where
128 K::Type<K::I>: Array<K, K::I> + PartialEq,
129 {
130 let table = coequalizer_universal(self, f.table.as_ref())?.into();
131 let target = f.target();
132 Some(FiniteFunction { table, target })
133 }
134
135 /// `transpose(a, b)` is the "transposition permutation" for an `a → b` matrix stored in
136 /// row-major order.
137 ///
138 /// Let M be an `a*b`-dimensional input thought of as a matrix in row-major order -- having `b`
139 /// rows and `a` columns.
140 /// Then `transpose(a, b)` computes the "target indices" of the transpose.
141 /// So for matrices `M : a → b` and `N : b → a`, setting the indices `N[transpose(a, b)] = M`
142 /// is the same as writing `N = M.T`.
143 pub fn transpose(a: K::I, b: K::I) -> FiniteFunction<K> {
144 if a.is_zero() {
145 return Self::initial(a);
146 }
147
148 let n = b.clone() * a.clone();
149 let i = K::Index::arange(&K::I::zero(), &n);
150 let (q, r) = i.quot_rem(a);
151 FiniteFunction {
152 target: n,
153 // r * b + q
154 table: r.mul_constant_add(b, &q),
155 }
156 }
157
158 /// Given a finite function `s : N → K`
159 /// representing the objects of the finite coproduct
160 /// `Σ_{n ∈ N} s(n)`
161 /// whose injections have the type
162 /// `ι_x : s(x) → Σ_{n ∈ N} s(n)`,
163 /// and given a finite map
164 /// `a : A → N`,
165 /// compute the coproduct of injections
166 /// ```text
167 /// injections(s, a) : Σ_{x ∈ A} s(x) → Σ_{n ∈ N} s(n)
168 /// injections(s, a) = Σ_{x ∈ A} ι_a(x)
169 /// ```
170 /// So that `injections(s, id) == id`
171 ///
172 /// Note that when a is a permutation,
173 /// injections(s, a) is a "blockwise" version of that permutation with block
174 /// sizes equal to s.
175 /// """
176 pub fn injections(&self, a: &FiniteFunction<K>) -> Option<Self> {
177 let s = self;
178 let p = self.table.cumulative_sum();
179
180 // TODO: better errors!
181 let k = (a >> s)?;
182 let r = k.table.segmented_arange();
183
184 let repeats = k.table;
185 let values = p.gather(a.table.get_range(..));
186 let z = repeats.repeat(values.get_range(..));
187
188 Some(FiniteFunction {
189 table: r + z,
190 target: p.get(p.len() - K::I::one()),
191 })
192 }
193
194 /// Given a finite function `f : A → B`, compute the cumulative sum of `f`, a finite function
195 /// `cumulative_sum(f) : A → sum_i(f())`
196 ///
197 /// ```rust
198 /// # use open_hypergraphs::category::*;
199 /// # use open_hypergraphs::array::vec::*;
200 /// # use open_hypergraphs::finite_function::*;
201 /// let f = FiniteFunction::<VecKind>::new(VecArray(vec![3, 0, 1, 4]), 5).unwrap();
202 /// let c = f.cumulative_sum();
203 /// assert_eq!(c.table, VecArray(vec![0, 3, 3, 4]));
204 /// assert_eq!(c.target(), 8);
205 ///
206 /// let f = FiniteFunction::<VecKind>::new(VecArray(vec![]), 5).unwrap();
207 /// let c = f.cumulative_sum();
208 /// assert_eq!(c.table, VecArray(vec![]));
209 /// assert_eq!(c.target(), 0);
210 /// ```
211 pub fn cumulative_sum(&self) -> Self {
212 let extended_table = self.table.cumulative_sum();
213 let target = extended_table.get(self.source());
214 let table = Array::from_slice(extended_table.get_range(..self.source()));
215 FiniteFunction { table, target }
216 }
217}
218
219/// Compute the universal map for a coequalizer `q : B → Q` and arrow `f : B → T`, generalised to
220/// the case where `T` is an arbitrary set (i.e., `f` is an array of `T`)
221pub fn coequalizer_universal<K: ArrayKind, T>(
222 q: &FiniteFunction<K>,
223 f: &K::Type<T>,
224) -> Option<K::Type<T>>
225where
226 K::Type<T>: Array<K, T> + PartialEq,
227{
228 if q.source() != f.len() {
229 return None;
230 }
231
232 // Compute table by scattering
233 let table = f.scatter(q.table.get_range(..), q.target());
234
235 // TODO: FIXME: we only need SemifiniteFunction to check this is a coequalizer;
236 // we use the >> implementation to check, which is implemented for SemifiniteFunction
237 use crate::semifinite::SemifiniteFunction;
238 let u = SemifiniteFunction(table);
239
240 // NOTE: we expect() here because composition is *defined* for self and u by construction;
241 // if it panics, there is a library bug.
242 let f_prime = (q >> &u).expect("by construction");
243 if f_prime.0 == *f {
244 Some(u.0)
245 } else {
246 None
247 }
248}
249
250impl<K: ArrayKind> Arrow for FiniteFunction<K> {
251 type Object = K::I;
252
253 fn source(&self) -> Self::Object {
254 self.table.len()
255 }
256
257 fn target(&self) -> Self::Object {
258 self.target.clone()
259 }
260
261 fn identity(a: Self::Object) -> Self {
262 let table = K::Index::arange(&K::I::zero(), &a);
263 let target = a.clone();
264 FiniteFunction { table, target }
265 }
266
267 fn compose(&self, other: &Self) -> Option<Self> {
268 if self.target == other.source() {
269 let table = other.table.gather(self.table.get_range(..));
270 let target = other.target.clone();
271 Some(FiniteFunction { table, target })
272 } else {
273 None
274 }
275 }
276}
277
278impl<K: ArrayKind> Coproduct for FiniteFunction<K> {
279 fn initial_object() -> Self::Object {
280 K::I::zero()
281 }
282
283 fn initial(a: Self::Object) -> Self {
284 Self {
285 table: K::Index::empty(),
286 target: a.clone(),
287 }
288 }
289
290 fn coproduct(&self, other: &Self) -> Option<Self> {
291 if self.target != other.target {
292 return None;
293 }
294
295 Some(Self {
296 table: self.table.concatenate(&other.table),
297 target: self.target.clone(),
298 })
299 }
300
301 /// Coproduct injection 0.
302 ///
303 /// As an array, the indices `0..a`
304 fn inj0(a: Self::Object, b: Self::Object) -> Self {
305 let table = K::Index::arange(&K::I::zero(), &a);
306 let target = a.clone() + b.clone();
307 Self { table, target }
308 }
309
310 /// Coproduct injection 1.
311 ///
312 /// As an array, the indices `a..(a+b)`
313 ///
314 /// ```rust
315 /// # use open_hypergraphs::category::*;
316 /// # use open_hypergraphs::finite_function::*;
317 /// # use open_hypergraphs::array::vec::*;
318 /// assert_eq!(
319 /// FiniteFunction::<VecKind>::inj1(3, 5).table,
320 /// VecArray(vec![3,4,5,6,7]),
321 /// )
322 /// ```
323 fn inj1(a: Self::Object, b: Self::Object) -> Self {
324 let target = a.clone() + b.clone();
325 let table = K::Index::arange(&a, &target);
326 Self { table, target }
327 }
328}
329
330impl<K: ArrayKind> Monoidal for FiniteFunction<K> {
331 // the unit object
332 fn unit() -> Self::Object {
333 K::I::zero()
334 }
335
336 fn tensor(&self, other: &Self) -> Self {
337 // NOTE: this uses the `Add<&K::Index>` bound on `K::I` to compute offset piece without
338 // unnecessary cloning.
339 let table = self
340 .table
341 .concatenate(&(self.target.clone() + &other.table));
342 let target = self.target.clone() + other.target.clone();
343 Self { table, target }
344 }
345}
346
347impl<K: ArrayKind> SymmetricMonoidal for FiniteFunction<K> {
348 fn twist(a: K::I, b: K::I) -> Self {
349 // This is more efficiently expressed as arange + b `mod` target,
350 // but this would require adding an operation add_mod(a, b, n) to the array trait.
351 let target = a.clone() + b.clone();
352 let lhs = K::Index::arange(&b, &target);
353 let rhs = K::Index::arange(&K::I::zero(), &b);
354 let table = lhs.concatenate(&rhs);
355 Self { table, target }
356 }
357}
358
359// Syntactic sugar for finite function composition
360impl<K: ArrayKind> Shr<&FiniteFunction<K>> for &FiniteFunction<K> {
361 type Output = Option<FiniteFunction<K>>;
362
363 fn shr(self, rhs: &FiniteFunction<K>) -> Option<FiniteFunction<K>> {
364 self.compose(rhs)
365 }
366}
367
368// Sugar for coproduct
369impl<K: ArrayKind> Add<&FiniteFunction<K>> for &FiniteFunction<K> {
370 type Output = Option<FiniteFunction<K>>;
371
372 fn add(self, rhs: &FiniteFunction<K>) -> Option<FiniteFunction<K>> {
373 self.coproduct(rhs)
374 }
375}
376
377// Tensor product (parallel composition)
378impl<K: ArrayKind> BitOr<&FiniteFunction<K>> for &FiniteFunction<K> {
379 type Output = FiniteFunction<K>;
380 fn bitor(self, rhs: &FiniteFunction<K>) -> FiniteFunction<K> {
381 self.tensor(rhs)
382 }
383}
384
385impl<K: ArrayKind> Clone for FiniteFunction<K> {
386 fn clone(&self) -> Self {
387 Self {
388 table: self.table.clone(),
389 target: self.target.clone(),
390 }
391 }
392}
393
394impl<K: ArrayKind> Debug for FiniteFunction<K>
395where
396 K::Index: Debug,
397{
398 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
399 f.debug_struct("FiniteFunction")
400 .field("table", &self.table)
401 .field("target", &self.target)
402 .finish()
403 }
404}