acls_rs/algebra/
monoid.rs

1//! Monoid algebraic structure.
2//!
3//! A monoid is a semigroup with an identity element.
4//!
5//! # Algebraic Laws
6//!
7//! For a type to implement `Monoid`, it must satisfy:
8//!
9//! - **Associativity**: `(a ∘ b) ∘ c = a ∘ (b ∘ c)` (inherited from Semigroup)
10//! - **Left Identity**: `e ∘ a = a` for all `a`
11//! - **Right Identity**: `a ∘ e = a` for all `a`
12//!
13//! where `e` is the identity element.
14
15use super::Semigroup;
16use std::collections::BTreeSet;
17
18/// A monoid: a semigroup with an identity element.
19///
20/// # Laws
21///
22/// Implementations must satisfy (in addition to semigroup laws):
23/// - **Left Identity**: `Monoid::identity().combine(a) == a`
24/// - **Right Identity**: `a.combine(Monoid::identity()) == a`
25pub trait Monoid: Semigroup {
26    /// Return the identity element.
27    ///
28    /// The identity element must satisfy:
29    /// - `identity().combine(a) == a` (left identity)
30    /// - `a.combine(identity()) == a` (right identity)
31    ///
32    /// # Examples
33    ///
34    /// ```
35    /// use acls_rs::algebra::Monoid;
36    /// use acls_rs::permission::PermissionSet;
37    ///
38    /// let empty = PermissionSet::identity();
39    /// assert!(empty.is_empty());
40    /// ```
41    fn identity() -> Self;
42
43    /// Combine all elements from an iterator, using identity for empty iterators.
44    ///
45    /// Unlike `Semigroup::combine_all`, this always returns a value, using the
46    /// identity element when the iterator is empty.
47    ///
48    /// # Examples
49    ///
50    /// ```
51    /// use acls_rs::algebra::Monoid;
52    /// use acls_rs::permission::PermissionSet;
53    ///
54    /// let empty: Vec<PermissionSet> = vec![];
55    /// let result = PermissionSet::combine_all_with_identity(empty);
56    /// assert_eq!(result, PermissionSet::identity());
57    /// ```
58    fn combine_all_with_identity<I: IntoIterator<Item = Self>>(iter: I) -> Self {
59        Self::combine_all(iter).unwrap_or_else(Self::identity)
60    }
61}
62
63// Blanket implementation for BTreeSet
64impl<T: Ord + Clone> Monoid for BTreeSet<T> {
65    #[inline]
66    fn identity() -> Self {
67        BTreeSet::new()
68    }
69}
70
71#[cfg(test)]
72mod tests {
73    use super::*;
74    use crate::algebra::Semigroup;
75
76    #[test]
77    fn test_btreeset_left_identity() {
78        let a: BTreeSet<i32> = [1, 2, 3].iter().cloned().collect();
79        let e = BTreeSet::identity();
80
81        assert_eq!(e.combine(a.clone()), a);
82    }
83
84    #[test]
85    fn test_btreeset_right_identity() {
86        let a: BTreeSet<i32> = [1, 2, 3].iter().cloned().collect();
87        let e = BTreeSet::identity();
88
89        assert_eq!(a.clone().combine(e), a);
90    }
91
92    #[test]
93    fn test_combine_all_with_identity_empty() {
94        let empty: Vec<BTreeSet<i32>> = vec![];
95        let result = BTreeSet::combine_all_with_identity(empty);
96
97        assert_eq!(result, BTreeSet::identity());
98    }
99
100    #[test]
101    fn test_combine_all_with_identity_nonempty() {
102        let sets = vec![
103            [1, 2].iter().cloned().collect::<BTreeSet<_>>(),
104            [3, 4].iter().cloned().collect::<BTreeSet<_>>(),
105        ];
106
107        let result = BTreeSet::combine_all_with_identity(sets);
108        assert_eq!(result, [1, 2, 3, 4].iter().cloned().collect());
109    }
110}
acls_rs/algebra/monoid.rs

acls_rs/algebra/
monoid.rs
