semigroup/
semigroup.rs

1use crate::Annotated;
2
3/// [`Semigroup`] represents a binary operation that satisfies the following properties
4/// 1. *Closure*: `op: T × T → T`
5/// 2. *Associativity*: `op(op(a, b), c) = op(a, op(b, c))`
6///
7/// # Deriving
8/// When fields do not implement [`Semigroup`], use `with` attribute.
9/// ```
10/// use semigroup::Semigroup;
11/// #[derive(Debug, Clone, PartialEq, Semigroup)]
12/// #[semigroup(with = "semigroup::op::Coalesce")]
13/// pub struct ExampleStruct<'a> {
14///     pub str: Option<&'a str>,
15///     #[semigroup(with = "semigroup::op::Overwrite")]
16///     pub boolean: bool,
17///     #[semigroup(with = "semigroup::op::Sum")]
18///     pub sum: u32,
19/// }
20///
21/// let a = ExampleStruct { str: None, boolean: true, sum: 1 };
22/// let b = ExampleStruct { str: Some("ten"), boolean: false, sum: 10 };
23/// let c = ExampleStruct { str: None, boolean: false, sum: 100 };
24///
25/// // #[test]
26/// semigroup::assert_semigroup!(&a, &b, &c);
27/// assert_eq!(a.semigroup(b).semigroup(c), ExampleStruct { str: Some("ten"), boolean: false, sum: 111 });
28/// ```
29///
30/// # Construction
31/// [`Semigroup`] can be constructed by [`crate::Construction`].
32///
33/// Some operations are already provided by [`crate::op`].
34/// ```
35/// use semigroup::{Construction, Semigroup};
36///
37/// #[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Default, Hash, Construction)]
38/// #[construction(monoid, commutative)]
39/// pub struct Sum(u64);
40/// impl Semigroup for Sum {
41///     fn op(base: Self, other: Self) -> Self {
42///         Self(base.0 + other.0)
43///     }
44/// }
45///
46/// let (a, b, c) = (Sum(1), Sum(2), Sum(3));
47/// // #[test]
48/// semigroup::assert_semigroup!(&a, &b, &c);
49/// assert_eq!(a.semigroup(b).semigroup(c), Sum(6));
50/// ```
51///
52/// # Testing
53/// Use [`crate::assert_semigroup!`] macro.
54///
55/// The *closure* property is guaranteed by Rust’s type system,
56/// but *associativity* must be verified manually using [`crate::assert_semigroup!`].
57pub trait Semigroup {
58    fn op(base: Self, other: Self) -> Self;
59    fn semigroup(self, other: Self) -> Self
60    where
61        Self: Sized,
62    {
63        Semigroup::op(self, other)
64    }
65}
66
67/// [`AnnotatedSemigroup`] is a [`Semigroup`] that has an annotation.
68pub trait AnnotatedSemigroup<A>: Sized + Semigroup {
69    fn annotated_op(base: Annotated<Self, A>, other: Annotated<Self, A>) -> Annotated<Self, A>;
70}
71
72#[cfg(any(test, feature = "test"))]
73pub mod test_semigroup {
74    use std::fmt::Debug;
75
76    use rand::seq::IndexedRandom;
77
78    use crate::{
79        commutative::test_commutative::{assert_reverse_associative_law, assert_reverse_reverse},
80        iter::test_iter::assert_lazy_evaluation_iter,
81    };
82
83    use super::*;
84
85    /// Assert that the given type satisfies the *semigroup* property.
86    ///
87    /// # Usage
88    /// - 1 argument: iterator of more than 3 items that implements [`Semigroup`].
89    /// - More than 3 arguments: items that implements [`Semigroup`].
90    ///
91    /// # Examples
92    /// ```
93    /// use semigroup::{assert_semigroup, op::Coalesce};
94    ///
95    /// let a = Coalesce(Some(1));
96    /// let b = Coalesce(None);
97    /// let c = Coalesce(Some(3));
98    /// assert_semigroup!(a, b, c);
99    ///
100    /// let v = vec![a, b, c];
101    /// assert_semigroup!(&v);
102    /// ```
103    ///
104    /// # Panics
105    /// - If the given function does not satisfy the *semigroup* property.
106    /// - The input iterator has less than 3 items.
107    ///
108    /// ```compile_fail
109    /// use semigroup::{assert_semigroup, op::Coalesce};
110    /// let a = Coalesce(Some(1));
111    /// let b = Coalesce(None);
112    /// assert_semigroup!(a, b);
113    /// ```
114    #[macro_export]
115    macro_rules! assert_semigroup {
116        ($a:expr, $b: expr, $($tail: expr),*) => {
117            {
118                let v = vec![$a, $b, $($tail),*];
119                $crate::assert_semigroup!(&v)
120            }
121        };
122        ($v:expr) => {
123            {
124                let (a, b, c) = $crate::test_semigroup::pick3($v);
125                $crate::test_semigroup::assert_semigroup_impl(a.clone(), b.clone(), c.clone());
126                $crate::test_monoid::assert_option_monoid(a.clone(), b.clone(), c.clone());
127            }
128        };
129    }
130
131    pub fn pick3<T: Clone>(data: &[T]) -> (T, T, T) {
132        data.choose_multiple_array(&mut rand::rng())
133            .map(|[a, b, c]| (a, b, c))
134            .expect("failed to pick 3 items")
135    }
136
137    pub fn assert_semigroup_impl<T: Semigroup + Clone + PartialEq + Debug>(a: T, b: T, c: T) {
138        assert_associative_law(a.clone(), b.clone(), c.clone());
139        assert_reverse_reverse(a.clone(), b.clone(), c.clone());
140        assert_reverse_associative_law(a.clone(), b.clone(), c.clone());
141        assert_lazy_evaluation_iter(a.clone(), b.clone(), c.clone());
142    }
143
144    pub fn assert_associative_law<T: Semigroup + Clone + PartialEq + Debug>(a: T, b: T, c: T) {
145        let ab_c = T::op(T::op(a.clone(), b.clone()), c.clone());
146        let a_bc = T::op(a.clone(), T::op(b.clone(), c.clone()));
147        assert_eq!(ab_c, a_bc);
148    }
149}
semigroup/semigroup.rs

semigroup/
semigroup.rs
