algebraeon_sets/structure/
structure.rs

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

algebraeon_sets/structure/
structure.rs
