nekolib/traits/binop.rs
1//! 代数的構造に関するトレイトたちです。
2//!
3//! データ構造を実装する際に使うことを目的とします。
4
5/// マグマ。
6///
7/// 集合 $M$ と二項演算 $\\circ$ のペア $(M, \\circ)$ であり、次の性質を満たす。
8/// $$ x, y \\in M \\implies x \\circ y \\in M. $$
9///
10/// # Examples
11/// ```
12/// use nekolib::traits::Magma;
13/// use nekolib::utils::OpMin;
14///
15/// let op_min = OpMin::default();
16/// assert_eq!(3, op_min.op(3, 4));
17/// ```
18pub trait Magma {
19 /// 集合 $M$ に対応する型。
20 type Set: Eq;
21 /// $x \\circ y$ を返す。
22 fn op(&self, x: Self::Set, y: Self::Set) -> Self::Set;
23}
24
25/// 結合法則を満たす。
26///
27/// 二項演算 $\\circ: M \\times M \\to M$ が結合法則を満たすことを示す。
28/// $$ x, y, z \\in M \\implies (x \\circ y) \\circ z = x \\circ (y \\circ z). $$
29/// # Examples
30/// ```
31/// use nekolib::traits::{Associative, Magma};
32/// use nekolib::utils::OpMin;
33///
34/// let (x, y, z) = (2, 3, 4);
35/// let op_min = OpMin::default();
36/// assert_eq!(
37/// op_min.op(op_min.op(x, y), z),
38/// op_min.op(x, op_min.op(y, z)),
39/// );
40/// ```
41pub trait Associative: Magma {}
42
43/// 単位元を持つ。
44///
45/// 二項演算 $\\circ: M \\times M \\to M$ が単位元を持つことを示す。
46/// $$ x \\in M \\implies x \\circ e = e \\circ x = e. $$
47///
48/// # Examples
49/// ```
50/// use nekolib::traits::{Identity, Magma};
51/// use nekolib::utils::OpMin;
52///
53/// let op_min = OpMin::default();
54/// let x = 3;
55/// assert_eq!(op_min.id(), std::i32::MAX);
56/// assert_eq!(op_min.op(x, op_min.id()), x);
57/// ```
58pub trait Identity: Magma {
59 /// 単位元を返す。
60 fn id(&self) -> Self::Set;
61}
62
63/// 交換法則を満たす。
64///
65/// 二項演算 $\\circ: M \\times M \\to M$ が交換法則を満たすことを示す。
66/// $$ x, y \\in M \\implies x \\circ y = y \\circ x. $$
67/// 交換法則を満たさない演算の例としては、文字列結合や線形関数の合成、行列積などが挙げられる。
68///
69/// # Examples
70/// ```
71/// use nekolib::traits::{Commutative, Magma};
72/// use nekolib::utils::OpMin;
73///
74/// let op_min = OpMin::default();
75/// let (x, y) = (3, 4);
76/// assert_eq!(op_min.op(x, y), op_min.op(y, x));
77/// ```
78pub trait Commutative: Magma {}
79
80/// 逆元を持つ要素が存在する。
81///
82/// 二項演算 $\\circ: M \\times M \\to M$ が、一部の要素を除いて逆元を持つことを示す。
83///
84/// 体の乗法においては $0$ を除いて逆元を持つことが要請されるため必要かなと思った。
85/// もっといい設計はある気がする。
86pub trait PartialRecip: Magma {
87 fn partial_recip(&self, x: Self::Set) -> Option<Self::Set>;
88}
89
90/// 逆元が常に存在する。
91///
92/// 二項演算 $\\circ: M \\times M \\to M$ が、常に逆元を持つことを示す。
93/// $$ x \\in M \\implies {}^\\exists a \\in M: x \\circ a = a \\circ x = e. $$
94/// この $a$ を $x^{-1}$ と書く。
95///
96/// # Examples
97/// ```
98/// use nekolib::traits::{Magma, Monoid, Recip};
99/// use nekolib::utils::OpAdd;
100///
101/// let op_add = OpAdd::default();
102/// let x = 3;
103/// let y = op_add.recip(x);
104/// assert_eq!(op_add.op(x, y), 0);
105/// ```
106pub trait Recip: PartialRecip {
107 fn recip(&self, x: Self::Set) -> Self::Set {
108 self.partial_recip(x).unwrap()
109 }
110}
111
112/// 分配法則を満たす。
113///
114/// 乗法 $\\ast: M \\times M \\to M$ は、加法 $\\circ: M \\times M \\to M$ について
115/// 分配法則を満たすことを示す。
116/// $$ \\begin{aligned}
117/// x, y, z \\in R &\\implies x \\ast (y \\circ z) = (x \\ast y) \\circ (x \\ast z), \\\\
118/// x, y, z \\in R &\\implies (y \\circ z) \\ast x = (y \\ast x) \\circ (z \\ast x).
119/// \\end{aligned} $$
120/// 加法は型引数 `A` として指定される。
121///
122/// # Examples
123/// ```
124/// use nekolib::traits::{Commutative, Magma};
125/// use nekolib::utils::{OpAdd, OpMul};
126///
127/// let op_add = OpAdd::default();
128/// let op_mul = OpMul::default();
129/// let (x, y, z) = (3, 4, 5);
130/// assert_eq!(
131/// op_mul.op(x, op_add.op(y, z)),
132/// op_add.op(op_mul.op(x, y), op_mul.op(x, z))
133/// );
134/// ```
135pub trait Distributive<A: Magma> {}
136
137/// 半群。
138///
139/// マグマ $(M, \\circ)$ であり、結合法則を満たす。
140pub trait Semigroup: Associative + Magma {}
141impl<G: Associative + Magma> Semigroup for G {}
142
143/// モノイド。
144///
145/// 半群 $(M, \\circ)$ であり、単位元 $e \\in M$ を持つ。
146pub trait Monoid: Identity + Semigroup {}
147impl<G: Identity + Semigroup> Monoid for G {}
148
149/// 可換モノイド。
150///
151/// モノイド $(M, \\circ, e)$ であり、交換法則を満たす。
152pub trait CommutativeMonoid: Commutative + Monoid {}
153impl<G: Commutative + Monoid> CommutativeMonoid for G {}
154
155/// 群。
156///
157/// モノイド $(M, \\circ, e)$ であり、逆元を持つ。
158pub trait Group: Monoid + Recip {}
159impl<G: Monoid + Recip> Group for G {}
160
161/// 可換群。
162///
163/// 群 $(M, \\circ, e)$ であり、交換法則を満たす。
164pub trait CommutativeGroup: Commutative + Monoid + Recip {}
165impl<G: Commutative + Monoid + Recip> CommutativeGroup for G {}
166
167/// 環。
168///
169/// 集合 $R$ と二つの二項演算 $\\circ$, $\\ast$ の組 $(R, \\circ, \\ast)$ であり、次の性質を満たす。
170/// - $(R, \\circ, 0)$ は可換群をなす。
171/// - $(R, \\ast, 1)$ はモノイドをなす。
172/// - 乗法 $\\ast$ は加法 $\\circ$ について分配法則を満たす。
173pub trait Ring {
174 /// 集合 $R$ に対応する型。
175 type Set: Eq;
176 /// 可換群 $(R, \\circ, 0)$ に対応する型。
177 type Additive: CommutativeGroup<Set = Self::Set>;
178 /// モノイド $(R, \\ast, 1)$ に対応する型。
179 type Multiplicative: Monoid<Set = Self::Set> + Distributive<Self::Additive>;
180
181 fn additive(&self) -> &Self::Additive;
182 fn multiplicative(&self) -> &Self::Multiplicative;
183
184 /// 和 $x \\circ y$ を返す。
185 fn add(&self, x: Self::Set, y: Self::Set) -> Self::Set {
186 self.additive().op(x, y)
187 }
188 /// 加法 $\\circ$ の単位元 $0$ を返す。
189 #[must_use]
190 fn zero(&self) -> Self::Set { self.additive().id() }
191 /// 加法 $\\circ$ に関する $x$ の逆元 $-x$ を返す。
192 fn neg(&self, x: Self::Set) -> Self::Set { self.additive().recip(x) }
193 /// 積 $x \\ast y$ を返す。
194 fn mul(&self, x: Self::Set, y: Self::Set) -> Self::Set {
195 self.multiplicative().op(x, y)
196 }
197 /// 乗法 $\\ast$ の単位元 $1$ を返す。
198 #[must_use]
199 fn one(&self) -> Self::Set { self.multiplicative().id() }
200}
201
202/// 可換環。
203///
204/// 環 $(R, \\circ, \\ast, 0, 1)$ であり、$(R, \\ast, 1)$ は可換モノイドをなす。
205pub trait CommutativeRing: Ring
206where
207 Self::Multiplicative: Commutative,
208{
209}
210
211/// 体。
212///
213/// 環 $(R, \\circ, \\ast, 0, 1)$ であり、$(R \\setminus \\{0\\}, \\ast, 1)$ は群をなす。
214pub trait Field: Ring
215where
216 Self::Multiplicative: PartialRecip,
217{
218 /// 乗法 $\\ast$ における関する $x$ の逆元 $x^{-1}$ を返す。
219 fn recip(&self, x: Self::Set) -> Self::Set {
220 if x == self.additive().id() {
221 panic!("zero element does not have multiplicative inverse");
222 } else {
223 self.multiplicative().partial_recip(x).unwrap()
224 }
225 }
226}
227
228#[macro_export]
229macro_rules! new_monoid {
230 ( $ident:ident = ($ty:ty, $op:expr, $id:expr) ) => {
231 struct $ident;
232 impl Magma for $ident {
233 type Set = $ty;
234 fn op(&self, x: $ty, y: $ty) -> $ty { ($op)(x, y) }
235 }
236 impl Associative for $ident {}
237 impl Identity for $ident {
238 fn id(&self) -> $ty { $id }
239 }
240 impl Default for $ident {
241 fn default() -> Self { Self }
242 }
243 };
244 ( $ident:ident = ($ty:ty, $op:expr, $id:expr, +commutative) ) => {
245 struct $ident;
246 impl Magma for $ident {
247 type Set = $ty;
248 fn op(&self, x: $ty, y: $ty) -> $ty { ($op)(x, y) }
249 }
250 impl Associative for $ident {}
251 impl Identity for $ident {
252 fn id(&self) -> $ty { $id }
253 }
254 impl Commutative for $ident {}
255 impl Default for $ident {
256 fn default() -> Self { Self }
257 }
258 };
259 ( $ident:ident = ($ty:ty, $op:expr, $id:expr, $recip:expr) ) => {
260 struct $ident;
261 impl Magma for $ident {
262 type Set = $ty;
263 fn op(&self, x: $ty, y: $ty) -> $ty { ($op)(x, y) }
264 }
265 impl Associative for $ident {}
266 impl Identity for $ident {
267 fn id(&self) -> $ty { $id }
268 }
269 impl Recip for $ident {
270 fn recip(&self, x: $ty) -> $ty { ($recip)($x) }
271 }
272 impl PartialRecip for $ident {
273 fn partial_recip(&self, x: $ty) -> Option<$ty> {
274 Some(self.recip(x))
275 }
276 }
277 impl Default for $ident {
278 fn default() -> Self { Self }
279 }
280 };
281 ( $ident:ident = ($ty:ty, $op:expr, $id:expr, $recip:expr, +commutative) ) => {
282 struct $ident;
283 impl Magma for $ident {
284 type Set = $ty;
285 fn op(&self, x: $ty, y: $ty) -> $ty { ($op)(x, y) }
286 }
287 impl Associative for $ident {}
288 impl Identity for $ident {
289 fn id(&self) -> $ty { $id }
290 }
291 impl Recip for $ident {
292 fn recip(&self, x: $ty) -> $ty { ($recip)(x) }
293 }
294 impl PartialRecip for $ident {
295 fn partial_recip(&self, x: $ty) -> Option<$ty> {
296 Some(self.recip(x))
297 }
298 }
299 impl Commutative for $ident {}
300 impl Default for $ident {
301 fn default() -> Self { Self }
302 }
303 };
304}
305
306#[test]
307fn sanity_check() {
308 new_monoid! { OpXor1 = (u32, |x, y| x ^ y, 0, |x| x, +commutative) }
309
310 let monoid = OpXor1::default();
311 assert_eq!(monoid.id(), 0);
312 assert_eq!(monoid.op(2, 3), 1);
313 assert_eq!(monoid.recip(4), 4);
314}