algebraeon_sets/structure/
structure.rs

1use paste::paste;
2use rand::{Rng, RngExt, SeedableRng, rngs::StdRng};
3use std::{borrow::Borrow, fmt::Debug};
4
5macro_rules! make_maybe_trait {
6    ($name:ident) => {
7        paste! {
8            pub trait [<Maybe $name Signature>]: SetSignature {
9                type [<$name Structure>]: [<$name Signature>] <Set = Self::Set>;
10
11                #[allow(clippy::result_unit_err)]
12                fn [<$name:snake _structure>](
13                    &self
14                ) -> Result<Self::[<$name Structure>], ()>;
15            }
16        }
17    };
18}
19
20pub trait Signature: Clone + Debug + Eq + Send + Sync {}
21
22/// Instances of a type implementing this trait represent
23/// a set of elements of type `Self::Set` with some
24/// structure, for example, the structure of a ring.
25pub trait SetSignature: Signature {
26    type Set: Clone + Debug + Send + Sync;
27
28    /// Some instances of `Self::Set` may not be valid to represent elements of this set.
29    /// Return `Ok(())` if `x` is a valid element and an `Err` explaining why if not.
30    fn validate_element(&self, x: &Self::Set) -> Result<(), String>;
31
32    /// Some instances of `Self::Set` may not be valid to represent elements of this set.
33    /// Return `true` if `x` is a valid element and an `false` if not.
34    fn is_element(&self, x: &Self::Set) -> bool {
35        self.validate_element(x).is_ok()
36    }
37}
38
39pub trait MetaType: Clone + Debug {
40    type Signature: SetSignature<Set = Self>;
41    fn structure() -> Self::Signature;
42}
43
44pub trait ToStringSignature: SetSignature {
45    fn to_string(&self, elem: &Self::Set) -> String;
46}
47
48pub trait EqSignature: SetSignature {
49    fn equal(&self, a: &Self::Set, b: &Self::Set) -> bool;
50}
51
52pub trait CountableSetSignature: SetSignature {
53    /// Yield distinct elements of the set such that every element eventually appears.
54    /// Always yields elements in the same order.
55    fn generate_all_elements(&self) -> impl Iterator<Item = Self::Set> + Clone;
56}
57
58pub trait FiniteSetSignature: CountableSetSignature {
59    /// A list of all elements in the set.
60    /// Always returns elements in the same order.
61    fn list_all_elements(&self) -> Vec<Self::Set> {
62        self.generate_all_elements().collect()
63    }
64    fn size(&self) -> usize {
65        self.list_all_elements().len()
66    }
67    fn generate_random_elements(&self, seed: u64) -> impl Iterator<Item = Self::Set> {
68        let rng = StdRng::seed_from_u64(seed);
69        FiniteSetRandomElementGenerator::<Self, StdRng> {
70            all_elements: self.list_all_elements(),
71            rng,
72        }
73    }
74}
75make_maybe_trait!(FiniteSet);
76
77#[derive(Debug, Clone)]
78pub struct FiniteSetRandomElementGenerator<S: FiniteSetSignature, R: Rng> {
79    all_elements: Vec<S::Set>,
80    rng: R,
81}
82
83impl<S: FiniteSetSignature, R: Rng> Iterator for FiniteSetRandomElementGenerator<S, R> {
84    type Item = S::Set;
85
86    fn next(&mut self) -> Option<Self::Item> {
87        if self.all_elements.is_empty() {
88            None
89        } else {
90            let idx = self.rng.random_range(0..self.all_elements.len());
91            Some(self.all_elements[idx].clone())
92        }
93    }
94}
95
96pub trait BorrowedSet<S>: Borrow<S> + Clone + Debug + Send + Sync {}
97impl<S, BS: Borrow<S> + Clone + Debug + Send + Sync> BorrowedSet<S> for BS {}
98
99pub trait BorrowedStructure<S: Signature>: Borrow<S> + Clone + Debug + Eq + Send + Sync {}
100impl<S: Signature, BS: Borrow<S> + Clone + Debug + Eq + Send + Sync> BorrowedStructure<S> for BS {}
101
102#[cfg(test)]
103mod tests {
104    use super::*;
105    use algebraeon_macros::CanonicalStructure;
106
107    #[test]
108    fn canonical_structure() {
109        #[derive(Debug, Clone, PartialEq, Eq, CanonicalStructure)]
110        #[canonical_structure(eq)]
111        pub struct A {
112            x: i32,
113        }
114
115        impl ToString for A {
116            fn to_string(&self) -> String {
117                self.x.to_string()
118            }
119        }
120
121        impl ToStringSignature for ACanonicalStructure {
122            fn to_string(&self, elem: &Self::Set) -> String {
123                elem.to_string()
124            }
125        }
126
127        let a = A { x: 3 };
128        let b = A { x: 4 };
129        let v = A::structure().equal(&a, &b);
130        assert!(!v);
131        println!("{}", A::structure().to_string(&a));
132    }
133
134    #[test]
135    fn to_string_structure_impl() {
136        #[allow(dead_code)]
137        #[derive(Debug, Clone, PartialEq, Eq)]
138        struct A {
139            t: usize,
140        }
141
142        impl Signature for A {}
143
144        impl SetSignature for A {
145            type Set = usize;
146
147            fn validate_element(&self, _x: &Self::Set) -> Result<(), String> {
148                Ok(())
149            }
150        }
151
152        impl ToStringSignature for A {
153            fn to_string(&self, elem: &Self::Set) -> String {
154                elem.to_string()
155            }
156        }
157    }
158}
algebraeon_sets/structure/structure.rs

algebraeon_sets/structure/
structure.rs
