haar_lib/algebra/semiring/
mod.rs

1//! 半環
2
3pub mod add_mul;
4pub mod add_mul_mod;
5pub mod max_add;
6pub mod min_add;
7pub mod xor_and;
8
9/// 半環
10pub trait Semiring {
11    /// 集合の元
12    type Element;
13    /// 加法の単位元
14    fn zero(&self) -> Self::Element;
15    /// 乗法の単位元
16    fn one(&self) -> Self::Element;
17    /// 加法$\oplus$
18    fn add(&self, a: Self::Element, b: Self::Element) -> Self::Element;
19    /// 乗法$\otimes$
20    fn mul(&self, a: Self::Element, b: Self::Element) -> Self::Element;
21    /// $\underbrace{a \oplus a \oplus  \dots \oplus a \oplus a}_{n}$を計算する。
22    fn times(&self, a: Self::Element, n: u64) -> Self::Element;
23}
24
25/// 環
26pub trait Ring: Semiring {
27    /// 加法の逆元 $-a$
28    fn neg(&self, a: Self::Element) -> Self::Element;
29    /// $a \oplus (-b)$
30    fn sub(&self, a: Self::Element, b: Self::Element) -> Self::Element {
31        self.add(a, self.neg(b))
32    }
33}
34
35/// 体
36pub trait Field: Ring {
37    /// 乗法の逆元 $a^{-1}$
38    fn inv(&self, a: Self::Element) -> Self::Element;
39    /// $a \otimes b^{-1}$
40    fn div(&self, a: Self::Element, b: Self::Element) -> Self::Element {
41        self.mul(a, self.inv(b))
42    }
43}
haar_lib/algebra/semiring/mod.rs

haar_lib/algebra/semiring/
mod.rs
