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}