haar_lib/algebra/
traits.rs

1//! 代数的構造に関するトレイトを定義する。
2use crate::trait_alias;
3
4/// 集合
5pub trait Set: Sized {
6    /// 集合の元
7    type Element;
8}
9
10/// 二項演算をもつ
11pub trait BinaryOp: Set {
12    /// 二項演算
13    fn op(&self, a: Self::Element, b: Self::Element) -> Self::Element;
14
15    /// 二項演算$\circ$で(右側から)代入操作($a \leftarrow a \circ b$)をする。
16    fn op_assign_r(&self, a: &mut Self::Element, b: Self::Element)
17    where
18        Self::Element: Clone,
19    {
20        *a = self.op(a.clone(), b);
21    }
22
23    /// 二項演算$\circ$で(左側から)代入操作($a \leftarrow b \circ a$)をする。
24    fn op_assign_l(&self, a: &mut Self::Element, b: Self::Element)
25    where
26        Self::Element: Clone,
27    {
28        *a = self.op(b, a.clone());
29    }
30}
31
32/// 単位元をもつ
33pub trait Identity: Set {
34    /// 単位元
35    fn id(&self) -> Self::Element;
36    /// 単位元の判定
37    fn is_id(&self, a: &Self::Element) -> bool
38    where
39        Self::Element: PartialEq,
40    {
41        a == &self.id()
42    }
43}
44
45/// 逆元をもつ
46pub trait Inverse: Set {
47    /// 逆元
48    fn inv(&self, a: Self::Element) -> Self::Element;
49}
50
51/// 可換性をもつ
52pub trait Commutative {}
53/// 結合性をもつ
54pub trait Associative {}
55/// 冪等性をもつ
56pub trait Idempotence {}
57
58/// 二項演算が加法的
59pub trait Additive: BinaryOp {
60    fn times(&self, a: Self::Element, n: u64) -> Self::Element;
61}
62
63/// 二項演算が乗法的
64pub trait Multiplicative: BinaryOp {}
65
66/// 二項演算で順序が変化しない。
67///
68/// $a < b \implies a \circ m < b \circ m$
69pub trait Ordered: BinaryOp<Element: Ord> {}
70
71/// 半群
72pub trait Semigroup: BinaryOp + Associative {
73    /// `iter`が空のとき、`None`を返す。
74    /// そうでないとき、`iter`の中身を二項演算で畳み込んで`Some`で返す。
75    fn reduce<I>(&self, iter: I) -> Option<Self::Element>
76    where
77        I: IntoIterator<Item = Self::Element>,
78    {
79        iter.into_iter().reduce(|a, b| self.op(a, b))
80    }
81}
82impl<T: BinaryOp + Associative> Semigroup for T {}
83
84/// モノイド
85pub trait Monoid: Semigroup + Identity {
86    /// `iter`が空のとき、モノイドの単位元を返す。
87    /// そうでないとき、`iter`の中身を二項演算で畳み込んで返す。
88    fn fold_m<I>(&self, iter: I) -> Self::Element
89    where
90        I: IntoIterator<Item = Self::Element>,
91    {
92        self.reduce(iter).unwrap_or(self.id())
93    }
94
95    /// $\underbrace{a \circ a \circ \dots \circ a \circ a}_{n}$を計算する。
96    fn times(&self, mut a: Self::Element, mut n: u64) -> Self::Element
97    where
98        Self::Element: Clone,
99    {
100        let mut ret = self.id();
101
102        while n > 0 {
103            if n & 1 == 1 {
104                ret = self.op(ret, a.clone());
105            }
106            a = self.op(a.clone(), a);
107            n >>= 1;
108        }
109
110        ret
111    }
112}
113impl<T: Semigroup + Identity> Monoid for T {}
114
115trait_alias!(#[doc = "可換モノイド"] AbelianMonoid: Monoid + Commutative);
116trait_alias!(#[doc = "群"] Group: Monoid + Inverse);
117trait_alias!(#[doc = "可換群"] AbelianGroup: Group + Commutative);
118
119trait_alias!(#[doc = "半束"] Semilattice: Semigroup + Commutative + Idempotence);
120
121/// `fold_m`を提供する。
122pub trait FoldM: Iterator {
123    /// モノイドで畳み込んだ結果を返す。
124    fn fold_m<M>(self, monoid: &M) -> Self::Item
125    where
126        Self: Sized,
127        M: Monoid<Element = Self::Item>,
128    {
129        monoid.fold_m(self)
130    }
131}
132
133impl<I> FoldM for I where I: Iterator + ?Sized {}
haar_lib/algebra/traits.rs

haar_lib/algebra/
traits.rs
