algebraeon_sets/structure/
morphism.rs

1use super::{CountableSetSignature, EqSignature, FiniteSetSignature, SetSignature, Signature};
2use itertools::Itertools;
3use std::borrow::Borrow;
4use std::fmt::Debug;
5use std::marker::PhantomData;
6
7pub trait Morphism<Domain: Signature, Range: Signature>: Debug + Clone + Send + Sync {
8    fn domain(&self) -> &Domain;
9    fn range(&self) -> &Range;
10}
11
12/// A morphism from an object to itself
13pub trait Endomorphism<X: Signature>: Morphism<X, X> {}
14impl<X: Signature, T: Morphism<X, X>> Endomorphism<X> for T {}
15
16pub trait Function<Domain: SetSignature, Range: SetSignature>: Morphism<Domain, Range> {
17    fn image(&self, x: &Domain::Set) -> Range::Set;
18}
19
20/// A function from a set into itself
21pub trait Endofunction<X: SetSignature + EqSignature>: Function<X, X> {
22    // TODO: remove EqSignature requirement and use specialization once it is stable.
23    /// check if an element is fixed
24    fn is_fixed_point(&self, x: X::Set) -> bool {
25        self.domain().equal(&self.image(&x), &x)
26    }
27}
28
29pub trait InjectiveFunction<Domain: SetSignature, Range: SetSignature>:
30    Function<Domain, Range>
31{
32    fn try_preimage(&self, y: &Range::Set) -> Option<Domain::Set>;
33}
34
35pub trait BijectiveFunction<Domain: SetSignature, Range: SetSignature>:
36    InjectiveFunction<Domain, Range>
37{
38    fn preimage(&self, y: &Range::Set) -> Domain::Set {
39        self.try_preimage(y).unwrap()
40    }
41}
42
43/// A permutation is a bijective function from a set to itself
44pub trait Permutation<X: SetSignature>: BijectiveFunction<X, X> {}
45
46impl<X: SetSignature, T: BijectiveFunction<X, X>> Permutation<X> for T {}
47
48/// The identity morphism X -> X
49#[derive(Debug, Clone, PartialEq, Eq)]
50pub struct IdentityMorphism<X: Signature> {
51    x: X,
52}
53
54impl<X: Signature> IdentityMorphism<X> {
55    pub fn new(x: X) -> Self {
56        Self { x }
57    }
58}
59
60impl<X: Signature> Morphism<X, X> for IdentityMorphism<X> {
61    fn domain(&self) -> &X {
62        &self.x
63    }
64
65    fn range(&self) -> &X {
66        &self.x
67    }
68}
69
70impl<X: SetSignature> Function<X, X> for IdentityMorphism<X> {
71    fn image(&self, x: &X::Set) -> X::Set {
72        x.clone()
73    }
74}
75
76impl<X: SetSignature> InjectiveFunction<X, X> for IdentityMorphism<X> {
77    fn try_preimage(&self, x: &X::Set) -> Option<X::Set> {
78        Some(x.clone())
79    }
80}
81
82impl<X: SetSignature> BijectiveFunction<X, X> for IdentityMorphism<X> {}
83
84/// The composition A -> B -> C of two morphisms A -> B and B -> C
85#[derive(Debug, Clone, PartialEq, Eq)]
86pub struct CompositionMorphism<
87    A: Signature,
88    B: Signature,
89    C: Signature,
90    AB: Morphism<A, B>,
91    BC: Morphism<B, C>,
92> {
93    a: PhantomData<A>,
94    b: PhantomData<B>,
95    c: PhantomData<C>,
96    // required to satisfy ab.range() == bc.domain()
97    a_to_b: AB,
98    b_to_c: BC,
99}
100
101impl<A: Signature, B: Signature, C: Signature, AB: Morphism<A, B>, BC: Morphism<B, C>>
102    CompositionMorphism<A, B, C, AB, BC>
103{
104    pub fn new(a_to_b: AB, b_to_c: BC) -> Self {
105        assert_eq!(a_to_b.range(), b_to_c.domain());
106        Self {
107            a: PhantomData,
108            b: PhantomData,
109            c: PhantomData,
110            a_to_b,
111            b_to_c,
112        }
113    }
114
115    pub fn a(&self) -> &A {
116        self.a_to_b.domain()
117    }
118
119    pub fn b(&self) -> &B {
120        let b = self.a_to_b.range();
121        debug_assert_eq!(b, self.b_to_c.domain());
122        b
123    }
124
125    pub fn c(&self) -> &C {
126        self.b_to_c.range()
127    }
128
129    pub fn a_to_b(&self) -> &AB {
130        &self.a_to_b
131    }
132
133    pub fn b_to_c(&self) -> &BC {
134        &self.b_to_c
135    }
136}
137
138impl<A: Signature, B: Signature, C: Signature, AB: Morphism<A, B>, BC: Morphism<B, C>>
139    Morphism<A, C> for CompositionMorphism<A, B, C, AB, BC>
140{
141    fn domain(&self) -> &A {
142        self.a()
143    }
144
145    fn range(&self) -> &C {
146        self.c()
147    }
148}
149
150impl<A: SetSignature, B: SetSignature, C: SetSignature, AB: Function<A, B>, BC: Function<B, C>>
151    Function<A, C> for CompositionMorphism<A, B, C, AB, BC>
152{
153    fn image(&self, x: &A::Set) -> C::Set {
154        self.b_to_c.image(&self.a_to_b.image(x))
155    }
156}
157
158impl<
159    A: SetSignature,
160    B: SetSignature,
161    C: SetSignature,
162    AB: InjectiveFunction<A, B>,
163    BC: InjectiveFunction<B, C>,
164> InjectiveFunction<A, C> for CompositionMorphism<A, B, C, AB, BC>
165{
166    fn try_preimage(&self, x: &C::Set) -> Option<A::Set> {
167        self.a_to_b.try_preimage(&self.b_to_c.try_preimage(x)?)
168    }
169}
170
171impl<
172    A: SetSignature,
173    B: SetSignature,
174    C: SetSignature,
175    AB: BijectiveFunction<A, B>,
176    BC: BijectiveFunction<B, C>,
177> BijectiveFunction<A, C> for CompositionMorphism<A, B, C, AB, BC>
178{
179    fn preimage(&self, x: &C::Set) -> A::Set {
180        self.a_to_b.preimage(&self.b_to_c.preimage(x))
181    }
182}
183
184/// Represent all functions from `domain` to `range`
185#[derive(Debug, Clone, PartialEq, Eq)]
186pub struct Functions<Domain: SetSignature, Range: SetSignature> {
187    domain: Domain,
188    range: Range,
189}
190
191impl<Domain: SetSignature, Range: SetSignature> Functions<Domain, Range> {
192    pub fn new(domain: Domain, range: Range) -> Self {
193        Self { domain, range }
194    }
195}
196
197impl<Domain: SetSignature, Range: SetSignature> Signature for Functions<Domain, Range> {}
198
199impl<Domain: FiniteSetSignature, Range: EqSignature> SetSignature for Functions<Domain, Range> {
200    type Set = Vec<Range::Set>;
201
202    fn is_element(&self, x: &Self::Set) -> Result<(), String> {
203        if x.len() != self.domain.size() {
204            return Err("Incorrect vector length".to_string());
205        }
206        for y in x {
207            self.range.is_element(y)?;
208        }
209        Ok(())
210    }
211}
212
213impl<Domain: FiniteSetSignature, Range: EqSignature + FiniteSetSignature> CountableSetSignature
214    for Functions<Domain, Range>
215{
216    fn generate_all_elements(&self) -> impl Iterator<Item = Self::Set> + Clone {
217        (0..self.domain.size())
218            .map(|_| self.range.list_all_elements())
219            .multi_cartesian_product()
220    }
221}
222
223impl<Domain: FiniteSetSignature, Range: EqSignature + FiniteSetSignature> FiniteSetSignature
224    for Functions<Domain, Range>
225{
226}
227
228/// The set of all endofunctions on a finite set X: functions X → X
229#[derive(Debug, Clone, PartialEq, Eq)]
230pub struct FiniteSetEndofunctions<X: FiniteSetSignature + EqSignature> {
231    set: X,
232}
233
234impl<X: FiniteSetSignature + EqSignature> FiniteSetEndofunctions<X> {
235    pub fn new(set: X) -> Self {
236        Self { set }
237    }
238}
239
240impl<X: FiniteSetSignature + EqSignature> Signature for FiniteSetEndofunctions<X> {}
241
242impl<X: FiniteSetSignature + EqSignature> SetSignature for FiniteSetEndofunctions<X> {
243    type Set = Vec<X::Set>;
244
245    fn is_element(&self, f: &Self::Set) -> Result<(), String> {
246        if f.len() != self.set.size() {
247            return Err("Function must have one value per element in the domain.".to_string());
248        }
249        for y in f {
250            self.set.is_element(y)?;
251        }
252        Ok(())
253    }
254}
255
256impl<X: FiniteSetSignature + EqSignature> CountableSetSignature for FiniteSetEndofunctions<X> {
257    fn generate_all_elements(&self) -> impl Iterator<Item = Self::Set> + Clone {
258        (0..self.set.size())
259            .map(|_| self.set.list_all_elements())
260            .multi_cartesian_product()
261    }
262}
263
264impl<X: FiniteSetSignature + EqSignature> FiniteSetSignature for FiniteSetEndofunctions<X> {}
265
266pub trait BorrowedMorphism<Domain: Signature, Range: Signature, M: Morphism<Domain, Range>>:
267    Borrow<M> + Clone + Debug + Send + Sync
268{
269}
270impl<
271    Domain: Signature,
272    Range: Signature,
273    M: Morphism<Domain, Range>,
274    BM: Borrow<M> + Clone + Debug + Send + Sync,
275> BorrowedMorphism<Domain, Range, M> for BM
276{
277}
algebraeon_sets/structure/morphism.rs

algebraeon_sets/structure/
morphism.rs
