cp_library_rs/algebraic_structure/
monoid.rs

1//! ## モノイド
2//!
3//! - [`Monoid::Val`] ： データの型 $`S`$
4//! - [`Monoid::e`] ： 単位元を返す関数 $`\varnothing \to S`$
5//! - [`Monoid::op`] ： 演算 $`S\times S \to S`$
6
7use crate::algebraic_structure::operation::{Add, Max, Min, MinMax, Mul, WrappingAdd, Xor, GCD};
8
9use num::Zero;
10use num_traits::{Bounded, One};
11
12/// モノイド
13///
14/// - [`Monoid::Val`] ： データの型 $`S`$
15/// - [`Monoid::e`] ： 単位元を返す関数 $`\varnothing \to S`$
16/// - [`Monoid::op`] ： 演算 $`S\times S \to S`$
17pub trait Monoid {
18    /// データの型 （$`S`$）
19    type Val: Clone;
20    /// 単位元 （$`\varnothing \to S`$）
21    fn e() -> Self::Val;
22    /// 演算 （$`S \times S \to S`$）
23    fn op(left: &Self::Val, right: &Self::Val) -> Self::Val;
24}
25
26// ========== 実装 ==========
27impl Monoid for () {
28    type Val = ();
29    fn e() -> Self::Val {}
30    fn op(_: &Self::Val, _: &Self::Val) -> Self::Val {}
31}
32
33impl<T: Ord + Bounded + Clone> Monoid for Min<T> {
34    type Val = T;
35    fn e() -> Self::Val {
36        Self::Val::max_value()
37    }
38    fn op(left: &Self::Val, right: &Self::Val) -> Self::Val {
39        left.min(right).clone()
40    }
41}
42
43impl<T: Ord + Bounded + Clone> Monoid for Max<T> {
44    type Val = T;
45    fn e() -> Self::Val {
46        Self::Val::min_value()
47    }
48    fn op(left: &Self::Val, right: &Self::Val) -> Self::Val {
49        left.max(right).clone()
50    }
51}
52
53impl<T: Ord + Bounded + Clone> Monoid for MinMax<T> {
54    type Val = (T, T);
55    fn e() -> Self::Val {
56        (Min::e(), Max::e())
57    }
58    fn op(left: &Self::Val, right: &Self::Val) -> Self::Val {
59        (Min::op(&left.0, &right.0), Max::op(&left.1, &right.1))
60    }
61}
62
63impl<T: Zero + Clone> Monoid for Add<T> {
64    type Val = T;
65    fn e() -> Self::Val {
66        T::zero()
67    }
68    fn op(left: &Self::Val, right: &Self::Val) -> Self::Val {
69        left.clone() + right.clone()
70    }
71}
72
73impl Monoid for WrappingAdd {
74    type Val = usize;
75    fn e() -> Self::Val {
76        0
77    }
78    fn op(left: &Self::Val, right: &Self::Val) -> Self::Val {
79        left.wrapping_add(*right)
80    }
81}
82
83impl<T: One + Clone> Monoid for Mul<T> {
84    type Val = T;
85    fn e() -> Self::Val {
86        T::one()
87    }
88    fn op(left: &Self::Val, right: &Self::Val) -> Self::Val {
89        left.clone() * right.clone()
90    }
91}
92
93impl Monoid for Xor {
94    type Val = usize;
95    fn e() -> Self::Val {
96        0
97    }
98    fn op(left: &Self::Val, right: &Self::Val) -> Self::Val {
99        left ^ right
100    }
101}
102
103impl<T> Monoid for GCD<T> {
104    type Val = usize;
105    fn e() -> Self::Val {
106        0
107    }
108    fn op(left: &Self::Val, right: &Self::Val) -> Self::Val {
109        GCD::gcd(left, right)
110    }
111}
cp_library_rs/algebraic_structure/monoid.rs

cp_library_rs/algebraic_structure/
monoid.rs
