rsdd/util/semirings/
semiring_traits.rs

1//! A semiring is a set R equipped with two binary operations (+) and (*) such that:
2//! 1. (R, +) is a commutative monoid with identity 0
3//! 2. (R, *) is a monoid with identity 1
4//! 3. Multiplication distributes over addition
5//! 4. Multiplication by 0 annihilates R
6//! Compared with a ring, a semiring omits an inverse for addition
7//!
8use std::fmt::{Debug, Display};
9use std::ops;
10
11pub trait Semiring:
12    Debug + Clone + Copy + Display + ops::Add<Self, Output = Self> + ops::Mul<Self, Output = Self>
13{
14    fn one() -> Self;
15    fn zero() -> Self;
16}
17
18// A ring is a semiring with additive inverses, which is equivalent to a notion of subtraction.
19pub trait Ring: Semiring + ops::Sub<Self, Output = Self> {}
20
21// A join-semilattice is a set equipped with a partial order
22// that also admits a least upper bound (called join) for any two elements.
23pub trait JoinSemilattice: PartialOrd {
24    fn join(&self, arg: &Self) -> Self;
25}
26
27// A branch-and-bound semiring is a semiring join-semilattice with a
28// compatible total order `choose`.
29pub trait BBSemiring: Semiring + JoinSemilattice {
30    fn choose(&self, arg: &Self) -> Self;
31}
32
33pub trait BBRing: Ring + JoinSemilattice {
34    fn choose(&self, arg: &Self) -> Self;
35}
36
37// A meet-semilattice is a set equipped with a partial order
38// that also admits a least upper bound (called join) for any two elements.
39pub trait MeetSemilattice: PartialOrd {
40    fn meet(&self, arg: &Self) -> Self;
41}
42
43pub trait Lattice: JoinSemilattice + MeetSemilattice {}
44
45pub trait EdgeboundingRing: Lattice + BBRing {}
rsdd/util/semirings/semiring_traits.rs

rsdd/util/semirings/
semiring_traits.rs
