haar_lib/algebra/
traits.rs

1//! 代数的構造に関するトレイトを定義する。
2use crate::trait_alias;
3
4/// 集合
5pub trait Set {}
6
7/// 二項演算をもつ
8pub trait BinaryOp: Set {
9    /// 二項演算
10    fn op(self, other: Self) -> Self;
11
12    /// 二項演算$\circ$で(右側から)代入操作($a \leftarrow a \circ b$)をする。
13    fn op_assign_r(&mut self, b: Self)
14    where
15        Self: Clone,
16    {
17        *self = Self::op(self.clone(), b);
18    }
19
20    /// 二項演算$\circ$で(左側から)代入操作($a \leftarrow b \circ a$)をする。
21    fn op_assign_l(&mut self, b: Self)
22    where
23        Self: Clone,
24    {
25        *self = Self::op(b, self.clone());
26    }
27}
28
29/// 単位元をもつ
30pub trait Identity: Set {
31    /// 単位元
32    fn id() -> Self;
33}
34
35/// 逆元をもつ
36pub trait Inverse: Set {
37    /// 逆元
38    fn inv(self) -> Self;
39}
40
41/// 可換性をもつ
42pub trait Commutative {}
43/// 結合性をもつ
44pub trait Associative {}
45/// 冪等性をもつ
46pub trait Idempotence {}
47
48trait_alias!(#[doc = "半群"] Semigroup: BinaryOp + Associative);
49trait_alias!(#[doc = "モノイド"] Monoid: Semigroup + Identity);
50trait_alias!(#[doc = "可換モノイド"] AbelianMonoid: Monoid + Commutative);
51trait_alias!(#[doc = "群"] Group: Monoid + Inverse);
52trait_alias!(#[doc = "可換群"] AbelianGroup: Group + Commutative);
53
54/// 値に二項演算を複数回適用する。
55pub trait Times: BinaryOp + Identity + Clone {
56    /// $\underbrace{a \circ a \circ \dots \circ a \circ a}_{n}$を計算する。
57    ///
58    /// **Time complexity** $O(\log n)$
59    fn times(self, mut n: u64) -> Self {
60        let mut ret = Self::id();
61        let mut a = self;
62
63        while n > 0 {
64            if n & 1 == 1 {
65                ret = Self::op(ret, a.clone());
66            }
67            a = Self::op(a.clone(), a);
68            n >>= 1;
69        }
70
71        ret
72    }
73}
74impl<A: BinaryOp + Identity + Clone> Times for A {}
75
76/// `fold_m`を提供する。
77pub trait FoldM: Iterator {
78    /// モノイドで畳み込んだ結果を返す。
79    fn fold_m(self) -> Self::Item
80    where
81        Self: Sized,
82        Self::Item: Monoid,
83    {
84        self.fold(Self::Item::id(), Self::Item::op)
85    }
86}
87
88impl<I> FoldM for I where I: Iterator + ?Sized {}
haar_lib/algebra/traits.rs

haar_lib/algebra/
traits.rs
