algae_rs/
mapping.rs

1fn permutations<T: Clone>(collection: &[T], group_size: usize) -> Vec<Vec<T>> {
2    let mut groupings: Vec<Vec<T>> = vec![];
3    for chunk in collection.chunks(group_size) {
4        if chunk.len() != group_size {
5            continue;
6        }
7        groupings.push(chunk.to_vec());
8    }
9    let mut reversed_collection = collection.to_vec();
10    reversed_collection.reverse();
11    for chunk in reversed_collection.chunks(group_size) {
12        if chunk.len() != group_size {
13            continue;
14        }
15        groupings.push(chunk.to_vec());
16    }
17    groupings
18}
19
20fn cayley_product<T: Copy>(collection: &Vec<T>) -> Vec<Vec<T>> {
21    let mut pairs: Vec<Vec<T>> = vec![];
22    for x in collection {
23        for y in collection {
24            pairs.push(vec![*x, *y]);
25        }
26    }
27    pairs
28}
29
30#[derive(Debug)]
31pub enum PropertyError {
32    CommutativityError,
33    AssociativityError,
34    CancellativityError,
35    IdentityError,
36    InvertibilityError,
37    Other(String),
38}
39
40impl std::fmt::Display for PropertyError {
41    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> Result<(), std::fmt::Error> {
42        let msg = match self {
43            PropertyError::CommutativityError => "Operation is not commutative!",
44            PropertyError::AssociativityError => "Operation is not associative!",
45            PropertyError::CancellativityError => "Operation is not cancellative!",
46            PropertyError::IdentityError => "Operation has no valid identity!",
47            PropertyError::InvertibilityError => "Operation is not invertible!",
48            PropertyError::Other(error) => error,
49        };
50        write!(f, "{msg}")
51    }
52}
53
54pub enum PropertyType<'a, T> {
55    Commutative,
56    Abelian,
57    Associative,
58    Cancellative,
59    WithIdentity(T),
60    Invertible(T, &'a dyn Fn(T, T) -> T),
61}
62
63impl<'a, T: Copy + PartialEq> PropertyType<'a, T> {
64    pub fn holds_over(&self, op: &dyn Fn(T, T) -> T, domain_sample: &Vec<T>) -> bool {
65        match self {
66            Self::Commutative | Self::Abelian => Self::commutativity_holds_over(op, domain_sample),
67            Self::Associative => Self::associativity_holds_over(op, domain_sample),
68            Self::Cancellative => Self::cancellative_holds_over(op, domain_sample),
69            Self::WithIdentity(identity) => Self::identity_holds_over(op, domain_sample, *identity),
70            Self::Invertible(identity, inv) => {
71                Self::invertibility_holds_over(op, inv, domain_sample, *identity)
72            }
73        }
74    }
75
76    fn commutativity_holds_over(op: &dyn Fn(T, T) -> T, domain_sample: &Vec<T>) -> bool {
77        if domain_sample.len() < 2 {
78            return true;
79        }
80        return permutations(domain_sample, 2).iter().all(|pair| {
81            let left = (op)(pair[0], pair[1]);
82            let right = (op)(pair[1], pair[0]);
83            left == right
84        });
85    }
86
87    fn associativity_holds_over(op: &dyn Fn(T, T) -> T, domain_sample: &Vec<T>) -> bool {
88        if domain_sample.len() < 3 {
89            return true;
90        }
91        return permutations(domain_sample, 3).iter().all(|triple| {
92            let left_first = (op)((op)(triple[0], triple[1]), triple[2]);
93            let right_first = (op)(triple[0], (op)(triple[1], triple[2]));
94            left_first == right_first
95        });
96    }
97
98    fn identity_holds_over(op: &dyn Fn(T, T) -> T, domain_sample: &[T], identity: T) -> bool {
99        return domain_sample.iter().all(|e| {
100            let from_left = (op)(identity, *e);
101            let from_right = (op)(*e, identity);
102            (*e == from_left) && (*e == from_right)
103        });
104    }
105
106    fn cancellative_holds_over(op: &dyn Fn(T, T) -> T, domain_sample: &Vec<T>) -> bool {
107        if domain_sample.len() < 3 {
108            return true;
109        }
110        let left_cancellative = permutations(domain_sample, 3).iter().all(|triple| {
111            if (op)(triple[0], triple[1]) == (op)(triple[0], triple[2]) {
112                return triple[1] == triple[2];
113            }
114            true
115        });
116        let right_cancellative = permutations(domain_sample, 3).iter().all(|triple| {
117            if (op)(triple[1], triple[0]) == (op)(triple[2], triple[0]) {
118                return triple[1] == triple[2];
119            }
120            true
121        });
122        left_cancellative && right_cancellative
123    }
124
125    fn invertibility_holds_over(
126        op: &dyn Fn(T, T) -> T,
127        inv: &dyn Fn(T, T) -> T,
128        domain_sample: &Vec<T>,
129        identity: T,
130    ) -> bool {
131        if domain_sample.len() < 2 {
132            return true;
133        }
134        return permutations(domain_sample, 2).iter().all(|pair| {
135            let inverse_works = (inv)(pair[0], pair[0]) == identity;
136            let left_composition_works = (inv)((op)(pair[0], pair[1]), pair[1]) == pair[0];
137            let right_composition_works = (inv)((op)(pair[1], pair[0]), pair[1]) == pair[0];
138            inverse_works && left_composition_works && right_composition_works
139        });
140    }
141}
142
143impl<'a, T> PartialEq for PropertyType<'a, T> {
144    fn eq(&self, other: &PropertyType<'a, T>) -> bool {
145        match self {
146            Self::Commutative | Self::Abelian => {
147                matches!(other, Self::Commutative) | matches!(other, Self::Abelian)
148            }
149            Self::Associative => matches!(other, Self::Associative),
150            Self::Cancellative => matches!(other, Self::Cancellative),
151            Self::WithIdentity(_) => matches!(other, Self::WithIdentity(_)),
152            Self::Invertible(_, _) => matches!(other, Self::Invertible(_, _)),
153        }
154    }
155}
156
157/// Common interface for all Algae operations.
158///
159/// All operations in Algae implement AlgaeOperation. This trait's key feature
160/// is the provided `with` method, which provides a common interface both for
161/// retrieving the results of binary operations in Algae and for enforcing
162/// their specified properties.
163///
164/// Property enforcement is done by keeping a history of all the inputs given
165/// to the operation. The property is enforced among all combinations of
166/// previous inputs every time the operation is called. The existence of the
167/// input history is required by `input_history`, and the caching mechanism is
168/// given by `cache`. The operation itself is given by a reference to a
169/// function via `operation`.
170pub trait BinaryOperation<T: Copy + PartialEq> {
171    /// Returns a reference to the function underlying the operation
172    fn operation(&self) -> &dyn Fn(T, T) -> T;
173
174    /// Vec of all enforced properties
175    fn properties(&self) -> Vec<PropertyType<'_, T>>;
176
177    /// Returns whether or not `property` is enforced by the given operation
178    fn is(&self, property: PropertyType<'_, T>) -> bool {
179        self.properties().contains(&property)
180    }
181
182    /// Returns a reference to a Vec of all previous inputs to the operation
183    fn input_history(&self) -> &Vec<T>;
184
185    /// Caches the given `input` to the operation's input history
186    fn cache(&mut self, input: T);
187
188    /// Returns the result of performing the given operation.
189    ///
190    /// If the operation is found not to obey all of its stated properties,
191    /// an appropriate Err will be returned; if else, an Ok wrapping the
192    /// proper result of the operation with the given inputs will be returned.
193    fn with(&mut self, left: T, right: T) -> Result<T, PropertyError> {
194        self.cache(left);
195        self.cache(right);
196        for property in self.properties() {
197            if property.holds_over(self.operation(), self.input_history()) {
198                continue;
199            }
200            match property {
201                PropertyType::Commutative | PropertyType::Abelian => {
202                    return Err(PropertyError::CommutativityError);
203                }
204                PropertyType::Associative => {
205                    return Err(PropertyError::AssociativityError);
206                }
207                PropertyType::Cancellative => {
208                    return Err(PropertyError::CancellativityError);
209                }
210                PropertyType::WithIdentity(_) => {
211                    return Err(PropertyError::IdentityError);
212                }
213                PropertyType::Invertible(_, _) => {
214                    return Err(PropertyError::InvertibilityError);
215                }
216            }
217        }
218        return Ok((self.operation())(left, right));
219    }
220}
221
222/// A function wrapper enforcing commutativity.
223///
224/// # Examples
225///
226/// ```
227/// # use algae_rs::mapping::AbelianOperation;
228/// # use algae_rs::mapping::BinaryOperation;
229/// let mut add = AbelianOperation::new(&|a, b| {
230///     a + b
231/// });
232///
233/// let sum = add.with(1, 2);
234/// assert!(sum.is_ok());
235/// assert!(sum.unwrap() == 3);
236///
237/// let mut sub = AbelianOperation::new(&|a, b| {
238///     a - b
239/// });
240///
241/// let pos_difference = sub.with(4, 3);
242/// assert!(pos_difference.is_err());
243///
244/// let neg_difference = sub.with(1, 2);
245/// assert!(neg_difference.is_err());
246/// ```
247pub struct AbelianOperation<'a, T> {
248    op: &'a dyn Fn(T, T) -> T,
249    history: Vec<T>,
250}
251
252impl<'a, T> AbelianOperation<'a, T> {
253    pub fn new(op: &'a dyn Fn(T, T) -> T) -> Self {
254        Self {
255            op,
256            history: vec![],
257        }
258    }
259}
260
261impl<'a, T: Copy + PartialEq> BinaryOperation<T> for AbelianOperation<'a, T> {
262    fn operation(&self) -> &dyn Fn(T, T) -> T {
263        self.op
264    }
265
266    fn properties(&self) -> Vec<PropertyType<'_, T>> {
267        vec![PropertyType::Commutative, PropertyType::Abelian]
268    }
269
270    fn input_history(&self) -> &Vec<T> {
271        &self.history
272    }
273
274    fn cache(&mut self, input: T) {
275        self.history.push(input);
276    }
277}
278
279/// A function wrapper enforcing associativity.
280///
281/// # Examples
282///
283/// ```
284/// # use algae_rs::mapping::AssociativeOperation;
285/// # use algae_rs::mapping::BinaryOperation;
286/// let mut mul = AssociativeOperation::new(&|a, b| {
287///     a * b
288/// });
289///
290/// let six = mul.with(2, 3);
291/// let twenty = mul.with(4, 5);
292/// assert!(six.is_ok());
293/// assert!(six.unwrap() == 6);
294/// assert!(twenty.is_ok());
295/// assert!(twenty.unwrap() == 20);
296///
297/// let mut div = AssociativeOperation::new(&|a, b| {
298///     a / b
299/// });
300///
301/// let whole_dividend = div.with(4.0, 2.0);
302/// assert!(whole_dividend.is_ok());
303/// assert!(whole_dividend.unwrap() == 2.0);
304/// let fractional_dividend = div.with(3.0, 1.0);
305/// assert!(fractional_dividend.is_err());
306/// ```
307pub struct AssociativeOperation<'a, T> {
308    op: &'a dyn Fn(T, T) -> T,
309    history: Vec<T>,
310}
311
312impl<'a, T> AssociativeOperation<'a, T> {
313    pub fn new(op: &'a dyn Fn(T, T) -> T) -> Self {
314        Self {
315            op,
316            history: vec![],
317        }
318    }
319}
320
321impl<'a, T: Copy + PartialEq> BinaryOperation<T> for AssociativeOperation<'a, T> {
322    fn operation(&self) -> &dyn Fn(T, T) -> T {
323        self.op
324    }
325
326    fn properties(&self) -> Vec<PropertyType<'_, T>> {
327        vec![PropertyType::Associative]
328    }
329
330    fn input_history(&self) -> &Vec<T> {
331        &self.history
332    }
333
334    fn cache(&mut self, input: T) {
335        self.history.push(input);
336    }
337}
338
339/// A function wrapper enforcing cancellativity.
340///
341/// # Examples
342///
343/// ```
344/// use algae_rs::mapping::{CancellativeOperation, BinaryOperation};
345///
346/// let mut mul = CancellativeOperation::new(&|a, b| a * b);
347///
348/// let six = mul.with(2, 3);
349/// assert!(six.is_ok());
350/// assert!(six.unwrap() == 6);
351/// ```
352pub struct CancellativeOperation<'a, T> {
353    op: &'a dyn Fn(T, T) -> T,
354    history: Vec<T>,
355}
356
357impl<'a, T> CancellativeOperation<'a, T> {
358    pub fn new(op: &'a dyn Fn(T, T) -> T) -> Self {
359        Self {
360            op,
361            history: vec![],
362        }
363    }
364}
365
366impl<'a, T: Copy + PartialEq> BinaryOperation<T> for CancellativeOperation<'a, T> {
367    fn operation(&self) -> &dyn Fn(T, T) -> T {
368        self.op
369    }
370
371    fn properties(&self) -> Vec<PropertyType<'_, T>> {
372        vec![PropertyType::Cancellative]
373    }
374
375    fn input_history(&self) -> &Vec<T> {
376        &self.history
377    }
378
379    fn cache(&mut self, input: T) {
380        self.history.push(input);
381    }
382}
383
384/// A function wrapper enforcing identity existence.
385///
386/// # Examples
387///
388/// ```
389/// use algae_rs::mapping::{IdentityOperation, BinaryOperation};
390///
391/// let mut mul = IdentityOperation::new(&|a, b| {
392///     a * b
393/// }, 1);
394///
395/// let six = mul.with(2, 3);
396/// assert!(six.is_ok());
397/// assert!(six.unwrap() == 6);
398///
399/// let mut add = IdentityOperation::new(&|a, b| {
400///     a + b
401/// }, 3);
402///
403/// let sum = add.with(4, 2);
404/// assert!(sum.is_err());
405/// ```
406pub struct IdentityOperation<'a, T> {
407    op: &'a dyn Fn(T, T) -> T,
408    identity: T,
409    history: Vec<T>,
410}
411
412impl<'a, T> IdentityOperation<'a, T> {
413    pub fn new(op: &'a dyn Fn(T, T) -> T, identity: T) -> Self {
414        Self {
415            op,
416            identity,
417            history: vec![],
418        }
419    }
420}
421
422impl<'a, T: Copy + PartialEq> BinaryOperation<T> for IdentityOperation<'a, T> {
423    fn operation(&self) -> &dyn Fn(T, T) -> T {
424        self.op
425    }
426
427    fn properties(&self) -> Vec<PropertyType<'_, T>> {
428        vec![PropertyType::WithIdentity(self.identity)]
429    }
430
431    fn input_history(&self) -> &Vec<T> {
432        &self.history
433    }
434
435    fn cache(&mut self, input: T) {
436        self.history.push(input);
437    }
438}
439
440/// A function wrapper enforcing identity existence and associativity.
441///
442/// # Examples
443///
444/// ```
445/// use algae_rs::mapping::{MonoidOperation, BinaryOperation};
446///
447/// let mut mul = MonoidOperation::new(&|a, b| a * b, 1);
448///
449/// let six = mul.with(2, 3);
450/// assert!(six.is_ok());
451/// assert!(six.unwrap() == 6);
452///
453/// let mut add = MonoidOperation::new(&|a, b| a + b, 3);
454///
455/// let sum = add.with(4, 2);
456/// assert!(sum.is_err());
457/// ```
458pub struct MonoidOperation<'a, T> {
459    op: &'a dyn Fn(T, T) -> T,
460    identity: T,
461    history: Vec<T>,
462}
463
464impl<'a, T> MonoidOperation<'a, T> {
465    pub fn new(op: &'a dyn Fn(T, T) -> T, identity: T) -> Self {
466        Self {
467            op,
468            identity,
469            history: vec![],
470        }
471    }
472}
473
474impl<'a, T: Copy + PartialEq> BinaryOperation<T> for MonoidOperation<'a, T> {
475    fn operation(&self) -> &dyn Fn(T, T) -> T {
476        self.op
477    }
478
479    fn properties(&self) -> Vec<PropertyType<'_, T>> {
480        vec![
481            PropertyType::Associative,
482            PropertyType::WithIdentity(self.identity),
483        ]
484    }
485
486    fn input_history(&self) -> &Vec<T> {
487        &self.history
488    }
489
490    fn cache(&mut self, input: T) {
491        self.history.push(input);
492    }
493}
494
495/// A function wrapper enforcing identity existence and cancellativity.
496///
497/// # Examples
498///
499/// ```
500/// use algae_rs::mapping::{LoopOperation, BinaryOperation};
501///
502/// let mut mul = LoopOperation::new(&|a, b| a * b, 1);
503///
504/// let six = mul.with(2, 3);
505/// assert!(six.is_ok());
506/// assert!(six.unwrap() == 6);
507///
508/// let mut add = LoopOperation::new(&|a, b| a + b, 3);
509///
510/// let sum = add.with(4, 2);
511/// assert!(sum.is_err());
512/// ```
513pub struct LoopOperation<'a, T> {
514    op: &'a dyn Fn(T, T) -> T,
515    identity: T,
516    history: Vec<T>,
517}
518
519impl<'a, T> LoopOperation<'a, T> {
520    pub fn new(op: &'a dyn Fn(T, T) -> T, identity: T) -> Self {
521        Self {
522            op,
523            identity,
524            history: vec![],
525        }
526    }
527}
528
529impl<'a, T: Copy + PartialEq> BinaryOperation<T> for LoopOperation<'a, T> {
530    fn operation(&self) -> &dyn Fn(T, T) -> T {
531        self.op
532    }
533
534    fn properties(&self) -> Vec<PropertyType<'_, T>> {
535        vec![
536            PropertyType::Cancellative,
537            PropertyType::WithIdentity(self.identity),
538        ]
539    }
540
541    fn input_history(&self) -> &Vec<T> {
542        &self.history
543    }
544
545    fn cache(&mut self, input: T) {
546        self.history.push(input);
547    }
548}
549
550/// A function wrapper enforcing identity existence and invertibility.
551///
552/// # Examples
553///
554/// ```
555/// use algae_rs::mapping::{InvertibleOperation, BinaryOperation};
556///
557/// let mut add = InvertibleOperation::new(&|a, b| a + b, &|a, b| a - b, 0);
558///
559/// let seven = add.with(4, 3);
560/// assert!(seven.is_ok());
561/// assert!(seven.unwrap() == 7);
562///
563/// let mut bad_add = InvertibleOperation::new(&|a, b| a + b, &|a, b| a * b, 0);
564///
565/// let sum = bad_add.with(4, 2);
566/// assert!(sum.is_err());
567/// ```
568pub struct InvertibleOperation<'a, T> {
569    op: &'a dyn Fn(T, T) -> T,
570    inv: &'a dyn Fn(T, T) -> T,
571    identity: T,
572    history: Vec<T>,
573}
574
575impl<'a, T> InvertibleOperation<'a, T> {
576    pub fn new(op: &'a dyn Fn(T, T) -> T, inv: &'a dyn Fn(T, T) -> T, identity: T) -> Self {
577        Self {
578            op,
579            inv,
580            identity,
581            history: vec![],
582        }
583    }
584}
585
586impl<'a, T: Copy + PartialEq> BinaryOperation<T> for InvertibleOperation<'a, T> {
587    fn operation(&self) -> &dyn Fn(T, T) -> T {
588        self.op
589    }
590
591    fn properties(&self) -> Vec<PropertyType<'_, T>> {
592        vec![
593            PropertyType::WithIdentity(self.identity),
594            PropertyType::Invertible(self.identity, self.inv),
595        ]
596    }
597
598    fn input_history(&self) -> &Vec<T> {
599        &self.history
600    }
601
602    fn cache(&mut self, input: T) {
603        self.history.push(input);
604    }
605}
606
607/// A function wrapper enforcing identity existence, invertibility, and associativity.
608///
609/// # Examples
610///
611/// ```
612/// use algae_rs::mapping::{GroupOperation, BinaryOperation};
613///
614/// let mut add = GroupOperation::new(&|a, b| a + b, &|a, b| a - b, 0);
615///
616/// let seven = add.with(4, 3);
617/// assert!(seven.is_ok());
618/// assert!(seven.unwrap() == 7);
619///
620/// let mut bad_add = GroupOperation::new(&|a, b| a + b, &|a, b| a * b, 0);
621///
622/// let sum = bad_add.with(4, 2);
623/// assert!(sum.is_err());
624/// ```
625pub struct GroupOperation<'a, T> {
626    op: &'a dyn Fn(T, T) -> T,
627    inv: &'a dyn Fn(T, T) -> T,
628    identity: T,
629    history: Vec<T>,
630}
631
632impl<'a, T> GroupOperation<'a, T> {
633    pub fn new(op: &'a dyn Fn(T, T) -> T, inv: &'a dyn Fn(T, T) -> T, identity: T) -> Self {
634        Self {
635            op,
636            inv,
637            identity,
638            history: vec![],
639        }
640    }
641}
642
643impl<'a, T: Copy + PartialEq> BinaryOperation<T> for GroupOperation<'a, T> {
644    fn operation(&self) -> &dyn Fn(T, T) -> T {
645        self.op
646    }
647
648    fn properties(&self) -> Vec<PropertyType<'_, T>> {
649        vec![
650            PropertyType::Associative,
651            PropertyType::WithIdentity(self.identity),
652            PropertyType::Invertible(self.identity, self.inv),
653        ]
654    }
655
656    fn input_history(&self) -> &Vec<T> {
657        &self.history
658    }
659
660    fn cache(&mut self, input: T) {
661        self.history.push(input);
662    }
663}
664
665/// Returns whether or not the given [`BinaryOperation`] has the [`PropertyType::Invertible`] property.
666///
667/// # Examples
668///
669/// ```
670/// # use algae_rs::mapping::{BinaryOperation};
671/// use algae_rs::mapping::{InvertibleOperation, AssociativeOperation, binop_is_invertible};
672///
673/// let add = InvertibleOperation::new(&|a: i32, b: i32| a + b, &|a: i32, b: i32| a - b, 0);
674/// assert!(binop_is_invertible(&add));
675///
676/// let bad_add = AssociativeOperation::new(&|a: i32, b: i32| a * b);
677/// assert!(!binop_is_invertible(&bad_add));
678/// ```
679pub fn binop_is_invertible<T: Copy + PartialEq>(binop: &dyn BinaryOperation<T>) -> bool {
680    for property in binop.properties() {
681        if let PropertyType::Invertible(_, _) = property {
682            return true;
683        }
684    }
685    false
686}
687
688/// Returns whether or not the given invertible [`BinaryOperation`] has the given `identity`.
689///
690/// # Examples
691///
692/// ```
693/// # use algae_rs::mapping::{BinaryOperation};
694/// use algae_rs::mapping::{InvertibleOperation, AssociativeOperation, binop_has_invertible_identity};
695///
696/// let add = InvertibleOperation::new(&|a: i32, b: i32| a + b, &|a: i32, b: i32| a - b, 0);
697/// assert!(binop_has_invertible_identity(&add, 0));
698///
699/// let bad_add = InvertibleOperation::new(&|a: i32, b: i32| a + b, &|a: i32, b: i32| a - b, 123);
700/// assert!(!binop_has_invertible_identity(&bad_add, 0));
701/// ```
702pub fn binop_has_invertible_identity<T: Copy + PartialEq>(
703    binop: &dyn BinaryOperation<T>,
704    identity: T,
705) -> bool {
706    assert!(binop_is_invertible(binop));
707    for property in binop.properties() {
708        if let PropertyType::Invertible(binop_identity, _) = property {
709            return binop_identity == identity;
710        }
711    }
712    false
713}
714
715#[cfg(test)]
716mod tests {
717
718    use super::{cayley_product, permutations};
719
720    #[test]
721    fn pair_permutations() {
722        let v = &[1, 2, 3];
723        let pairs = permutations(v, 2);
724        assert!(pairs.contains(&vec![1, 2]));
725        assert!(pairs.contains(&vec![3, 2]));
726    }
727
728    #[test]
729    fn cayley_product_works() {
730        let v = vec![1, 2, 3];
731        let product = cayley_product(&v);
732        assert!(
733            product
734                == vec![
735                    vec![1, 1],
736                    vec![1, 2],
737                    vec![1, 3],
738                    vec![2, 1],
739                    vec![2, 2],
740                    vec![2, 3],
741                    vec![3, 1],
742                    vec![3, 2],
743                    vec![3, 3]
744                ]
745        );
746    }
747}
algae_rs/mapping.rs

algae_rs/
mapping.rs
