sim_lib_discrete_algebra/
semiring.rs

1//! The [`Semiring`] trait: the algebraic core of the discrete-math family.
2//!
3//! A semiring is a set with two operations, `add` (combine alternatives) and
4//! `mul` (chain in sequence), each with an identity (`zero` and `one`). One
5//! generic matrix-closure engine over a semiring derives algebraic closures:
6//! boolean closure gives reachability, bounded min-plus closure gives tropical
7//! path costs under its documented saturation contract, and counting powers
8//! count walks. Checked integer graph shortest paths live in the graph crate.
9//! See the instance modules for the standard semirings.
10
11/// A semiring: `(add, zero)` is a commutative monoid, `(mul, one)` is a monoid,
12/// `mul` distributes over `add`, and `zero` annihilates under `mul`.
13///
14/// Implementations must uphold, for all `a`, `b`, `c`:
15/// - `zero + a == a` and `a + zero == a`
16/// - `a + b == b + a` and `(a + b) + c == a + (b + c)`
17/// - `one * a == a` and `a * one == a`
18/// - `(a * b) * c == a * (b * c)`
19/// - `a * (b + c) == a*b + a*c` and `(a + b) * c == a*c + b*c`
20/// - `zero * a == zero` and `a * zero == zero`
21///
22/// # Examples
23///
24/// The standard instances differ only in what `add` and `mul` mean. Over
25/// [`MinPlus`](crate::MinPlus), `add` is `min` and `mul` is `+`, so chaining a
26/// path costs the sum of its edges while combining alternatives keeps the
27/// cheaper one:
28///
29/// ```
30/// use sim_lib_discrete_algebra::{MinPlus, Semiring};
31///
32/// let zero = MinPlus::zero(); // Inf: "no path"
33/// let one = MinPlus::one(); //  Fin(0): the empty path
34/// assert_eq!(one, MinPlus::Fin(0));
35///
36/// // mul chains in sequence (sum of weights); add picks the cheaper route.
37/// assert_eq!(MinPlus::Fin(2).mul(&MinPlus::Fin(3)), MinPlus::Fin(5));
38/// assert_eq!(MinPlus::Fin(2).add(&MinPlus::Fin(3)), MinPlus::Fin(2));
39///
40/// // zero annihilates under mul and is the additive identity.
41/// assert_eq!(zero.mul(&MinPlus::Fin(7)), zero);
42/// assert_eq!(zero.add(&MinPlus::Fin(7)), MinPlus::Fin(7));
43/// ```
44pub trait Semiring: Clone + PartialEq + core::fmt::Debug {
45    /// The additive identity, also meaning "no value" / "no path".
46    fn zero() -> Self;
47    /// The multiplicative identity.
48    fn one() -> Self;
49    /// Combine two alternatives.
50    fn add(&self, other: &Self) -> Self;
51    /// Chain two values in sequence.
52    fn mul(&self, other: &Self) -> Self;
53    /// Whether this value is the additive identity.
54    fn is_zero(&self) -> bool {
55        *self == Self::zero()
56    }
57    /// The Kleene star `1 + a + a^2 + ...` when it converges, else `None`.
58    ///
59    /// Present only for closed semirings. The default is `None`.
60    fn star(&self) -> Option<Self> {
61        None
62    }
63}
64
65#[cfg(test)]
66pub(crate) mod laws {
67    use super::Semiring;
68
69    /// Assert the semiring laws on a small sample set (all triples).
70    ///
71    /// `samples` should include `zero` and `one` plus a few ordinary values.
72    /// For floating-point semirings, pick values that are exact in the format.
73    pub(crate) fn assert_semiring_laws<S: Semiring>(samples: &[S]) {
74        let zero = S::zero();
75        let one = S::one();
76        for a in samples {
77            assert_eq!(zero.add(a), *a, "zero + a == a");
78            assert_eq!(a.add(&zero), *a, "a + zero == a");
79            assert_eq!(one.mul(a), *a, "one * a == a");
80            assert_eq!(a.mul(&one), *a, "a * one == a");
81            assert_eq!(zero.mul(a), zero, "zero * a == zero");
82            assert_eq!(a.mul(&zero), zero, "a * zero == zero");
83            assert_eq!(a.is_zero(), *a == zero, "is_zero agrees with == zero");
84        }
85        for a in samples {
86            for b in samples {
87                assert_eq!(a.add(b), b.add(a), "add is commutative");
88                for c in samples {
89                    assert_eq!(a.add(b).add(c), a.add(&b.add(c)), "add is associative");
90                    assert_eq!(a.mul(b).mul(c), a.mul(&b.mul(c)), "mul is associative");
91                    assert_eq!(
92                        a.mul(&b.add(c)),
93                        a.mul(b).add(&a.mul(c)),
94                        "left distributive"
95                    );
96                    assert_eq!(
97                        a.add(b).mul(c),
98                        a.mul(c).add(&b.mul(c)),
99                        "right distributive"
100                    );
101                }
102            }
103        }
104    }
105}
sim_lib_discrete_algebra/semiring.rs

sim_lib_discrete_algebra/
semiring.rs
