1pub trait BinaryOp {
2 type Set;
3 fn op(&self, lhs: &Self::Set, rhs: &Self::Set) -> Self::Set;
4}
5
6pub trait Identity: BinaryOp {
7 fn id(&self) -> Self::Set;
8}
9
10pub trait Associative {}
11
12pub trait Recip: BinaryOp {
13 fn recip(&self, elt: &Self::Set) -> Self::Set;
14}
15
16pub trait Commutative {}
17
18pub trait Magma: BinaryOp {}
19pub trait Semigroup: BinaryOp + Associative {}
20pub trait Monoid: BinaryOp + Associative + Identity {}
21pub trait CommutativeMonoid:
22 BinaryOp + Associative + Identity + Commutative
23{
24}
25pub trait Group: BinaryOp + Associative + Identity + Recip {}
26pub trait CommutativeGroup:
27 BinaryOp + Associative + Identity + Recip + Commutative
28{
29}
30
31impl<T: BinaryOp> Magma for T {}
32impl<T: BinaryOp + Associative> Semigroup for T {}
33impl<T: BinaryOp + Associative + Identity> Monoid for T {}
34impl<T: BinaryOp + Associative + Identity + Commutative> CommutativeMonoid
35 for T
36{
37}
38impl<T: BinaryOp + Associative + Identity + Recip> Group for T {}
39impl<T: BinaryOp + Associative + Identity + Recip + Commutative>
40 CommutativeGroup for T
41{
42}
43
44#[macro_export]
45macro_rules! impl_monoid_generics {
46 (
47 $name:ident[$($gen:tt)*] where [$($where:tt)*] =
48 ([$ty:ty, $op:expr, $id:expr] [])
49 ) => {
50 impl<$($gen)*> $name<$($gen)*>
51 where $($where)*
52 {
53 fn new() -> Self { Self(std::marker::PhantomData) }
54 }
55 impl<$($gen)*> $crate::BinaryOp for $name<$($gen)*>
56 where $($where)*
57 {
58 type Set = $ty;
59 fn op(&self, lhs: &Self::Set, rhs: &Self::Set) -> Self::Set {
60 ($op)(lhs, rhs)
61 }
62 }
63 impl<$($gen)*> $crate::Identity for $name<$($gen)*>
64 where $($where)*
65 {
66 fn id(&self) -> Self::Set { ($id)() }
67 }
68 impl<$($gen)*> $crate::Associative for $name<$($gen)*>
69 where $($where)*
70 {}
71 impl<$($gen)*> Default for $name<$($gen)*>
72 where $($where)*
73 {
74 fn default() -> Self { Self::new() }
75 }
76 };
77 (
78 $name:ident[$($gen:tt)*] where [$($where:tt)*] =
79 ([$ty:ty, $op:expr, $id:expr] [$marker:ident])
80 ) => {
81 impl_monoid_generics! {
82 $name[$($gen)*] where [$($where)*] = ([$ty, $op, $id] [])
83 }
84 impl<$($gen)*> $crate::$marker for $name<$($gen)*>
85 where $($where)*
86 {}
87 };
88}
89
90#[macro_export]
91macro_rules! def_monoid_generics {
92 (
93 $(#[$attr:meta])*
94 $name:ident[$($gen:tt)*] where [$($where:tt)*] =
95 ($ty:ty, $op:expr, $id:expr $(, $marker:ident)? $(,)?) $(,)?
96 ) => {
97 $(#[$attr])*
98 #[allow(unused_parens)]
99 struct $name<$($gen)*>(std::marker::PhantomData<fn() -> ($($gen)*)>)
100 where $($where)*;
101 $crate::impl_monoid_generics! {
102 $name[$($gen)*] where [$($where)*] = ([$ty, $op, $id] [$($marker)?])
103 }
104 };
105 (
106 $(#[$attr:meta])*
107 pub $name:ident[$($gen:tt)*] where [$($where:tt)*] =
108 ($ty:ty, $op:expr, $id:expr $(, $marker:ident)? $(,)?) $(,)?
109 ) => {
110 $(#[$attr])*
111 #[allow(unused_parens)]
112 pub struct $name<$($gen)*>(std::marker::PhantomData<fn() -> ($($gen)*)>)
113 where $($where)*;
114 $crate::impl_monoid_generics! {
115 $name[$($gen)*] where [$($where)*] = ([$ty, $op, $id] [$($marker)?])
116 }
117 };
118 (
119 $(#[$attr:meta])*
120 pub($($vis:tt)+) $name:ident[$($gen:tt)*] where [$($where:tt)*] =
121 ($ty:ty, $op:expr, $id:expr $(, $marker:ident)? $(,)?) $(,)?
122 ) => {
123 $(#[$attr])*
124 #[allow(unused_parens)]
125 pub($($vis)+) struct $name<$($gen)*>(std::marker::PhantomData<fn() -> ($($gen)*)>)
126 where $($where)*;
127 $crate::impl_monoid_generics! {
128 $name[$($gen)*] where [$($where)*] = ([$ty, $op, $id] [$($marker)?])
129 }
130 };
131}
132
133#[macro_export]
134macro_rules! impl_group_generics {
135 (
136 $name:ident[$($gen:tt)*] where [$($where:tt)*] =
137 ([$ty:ty, $op:expr, $id:expr, $recip:expr] [])
138 ) => {
139 impl_monoid_generics! {
140 $name[$($gen)*] where [$($where)*] = ([$ty, $op, $id] [])
141 }
142 impl<$($gen)*> $crate::Recip for $name<$($gen)*>
143 where $($where)*
144 {
145 fn recip(&self, lhs: &Self::Set) -> Self::Set { ($recip)(lhs) }
146 }
147 };
148 (
149 $name:ident[$($gen:tt)*] where [$($where:tt)*] =
150 ([$ty:ty, $op:expr, $id:expr, $recip:expr] [$marker:ident])
151 ) => {
152 impl_group_generics! {
153 $name[$($gen)*] where [$($where)*] = ([$ty, $op, $id, $recip] [])
154 }
155 impl<$($gen)*> $crate::$marker for $name<$($gen)*>
156 where $($where)*
157 {}
158 };
159}
160
161#[macro_export]
162macro_rules! def_group_generics {
163 (
164 $(#[$attr:meta])*
165 $name:ident[$($gen:tt)*] where [$($where:tt)*] =
166 ($ty:ty, $op:expr, $id:expr, $recip:expr $(, $marker:ident)? $(,)?) $(,)?
167 ) => {
168 $(#[$attr])*
169 #[allow(unused_parens)]
170 struct $name<$($gen)*>(std::marker::PhantomData<fn() -> ($($gen)*)>)
171 where $($where)*;
172 $crate::impl_group_generics! {
173 $name[$($gen)*] where [$($where)*] = ([$ty, $op, $id, $recip] [$($marker)?])
174 }
175 };
176 (
177 $(#[$attr:meta])*
178 pub $name:ident[$($gen:tt)*] where [$($where:tt)*] =
179 ($ty:ty, $op:expr, $id:expr, $recip:expr $(, $marker:ident)? $(,)?) $(,)?
180 ) => {
181 $(#[$attr])*
182 #[allow(unused_parens)]
183 pub struct $name<$($gen)*>(std::marker::PhantomData<fn() -> ($($gen)*)>)
184 where $($where)*;
185 $crate::impl_group_generics! {
186 $name[$($gen)*] where [$($where)*] = ([$ty, $op, $id, $recip] [$($marker)?])
187 }
188 };
189 (
190 $(#[$attr:meta])*
191 pub($($vis:tt)+) $name:ident[$($gen:tt)*] where [$($where:tt)*] =
192 ($ty:ty, $op:expr, $id:expr, $recip:expr $(, $marker:ident)? $(,)?) $(,)?
193 ) => {
194 $(#[$attr])*
195 #[allow(unused_parens)]
196 pub($($vis)+) struct $name<$($gen)*>(std::marker::PhantomData<fn() -> ($($gen)*)>)
197 where $($where)*;
198 $crate::impl_group_generics! {
199 $name[$($gen)*] where [$($where)*] = ([$ty, $op, $id, $recip] [$($marker)?])
200 }
201 };
202}
203
204#[macro_export]
205macro_rules! def_monoid {
206 (
207 $(#[$attr:meta])*
208 $name:ident = ($ty:ty, $op:expr, $id:expr $(, $marker:ident)? $(,)?)
209 ) => {
210 $crate::def_monoid_generics! {
211 $(#[$attr])* $name[] where [] = ($ty, $op, $id $(, $marker)?)
212 }
213 };
214 (
215 $(#[$attr:meta])*
216 pub $name:ident = ($ty:ty, $op:expr, $id:expr $(, $marker:ident)? $(,)?)
217 ) => {
218 $crate::def_monoid_generics! {
219 $(#[$attr])* pub $name[] where [] = ($ty, $op, $id $(, $marker)?)
220 }
221 };
222 (
223 $(#[$attr:meta])*
224 pub($(vis:tt)+) $name:ident = ($ty:ty, $op:expr, $id:expr $(, $marker:ident)? $(,)?)
225 ) => {
226 $crate::def_monoid_generics! {
227 $(#[$attr])* pub($(vis)+) $name[] where [] = ($ty, $op, $id $(, $marker)?)
228 }
229 };
230}
231
232#[macro_export]
233macro_rules! def_group {
234 (
235 $(#[$attr:meta])*
236 $name:ident = ($ty:ty, $op:expr, $id:expr, $recip:expr $(, $marker:ident)? $(,)?) ) => {
237 $crate::def_group_generics! {
238 $(#[$attr])* $name[] where [] = ($ty, $op, $id, $recip $(, $marker)?)
239 }
240 };
241 (
242 $(#[$attr:meta])*
243 pub $name:ident = ($ty:ty, $op:expr, $id:expr, $recip:expr $(, $marker:ident)? $(,)?) ) => {
244 $crate::def_group_generics! {
245 $(#[$attr])* pub $name[] where [] = ($ty, $op, $id, $recip $(, $marker)?)
246 }
247 };
248 (
249 $(#[$attr:meta])*
250 pub($($vis:tt)+) $name:ident = ($ty:ty, $op:expr, $id:expr, $recip:expr $(, $marker:ident)? $(,)?) ) => {
251 $crate::def_group_generics! {
252 $(#[$attr])* pub($(vis)+) $name[] where [] = ($ty, $op, $id, $recip $(, $marker)?)
253 }
254 };
255}
256
257#[cfg(test)]
258mod tests {
259 use std::{
260 iter::Sum,
261 ops::{Add, BitXor, Neg},
262 };
263
264 use super::*;
265
266 #[test]
267 fn simple_monoid() {
268 def_monoid! { OpXor = (u32, |x, y| x ^ y, || 0) }
269 def_monoid! { OpAdd = (i32, |x, y| x + y, || 0) }
270
271 let xor = OpXor::new();
272 assert_eq!(xor.id(), 0);
273 assert_eq!(xor.op(&2, &3), 1);
274
275 let add = OpAdd::new();
276 assert_eq!(add.id(), 0);
277 assert_eq!(add.op(&2, &3), 5);
278 }
279
280 #[test]
281 fn simple_group() {
282 def_group! { OpXor = (u32, |x, y| x ^ y, || 0, |&x: &u32| x) }
283 def_group! { OpAdd = (i32, |x, y| x + y, || 0, |&x: &i32| -x, Commutative) }
284
285 let xor = OpXor::new();
286 assert_eq!(xor.id(), 0);
287 assert_eq!(xor.op(&2, &3), 1);
288
289 let add = OpAdd::new();
290 assert_eq!(add.id(), 0);
291 assert_eq!(add.op(&2, &3), 5);
292 }
293
294 #[test]
295 fn generics_monoid() {
296 def_monoid_generics! {
297 #[allow(non_camel_case_types)]
298 Op_Xor[T] where [
299 for<'a> &'a T: BitXor<Output = T>,
300 T: for<'a> Sum<&'a T>,
301 ] = (T, |x, y| x ^ y, || None.into_iter().sum(), Commutative),
302 }
303
304 let xor = Op_Xor::<u64>::new();
305 assert_eq!(xor.id(), 0);
306 assert_eq!(xor.op(&2, &3), 1);
307 }
308
309 #[test]
310 fn generics_group() {
311 def_group_generics! {
312 OpXor[T] where [
313 for<'a> &'a T: BitXor<Output = T>,
314 T: for<'a> Sum<&'a T>,
315 ] = (T, |x, y| x ^ y, || None.into_iter().sum(), |x| &(x ^ x) ^ x, Commutative),
316 }
317 def_group_generics! {
318 OpAdd[T] where [
319 for<'a> &'a T: Add<Output = T> + Neg<Output = T>,
320 T: for<'a> Sum<&'a T>,
321 ] = (T, |x, y| x + y, || None.into_iter().sum(), |x: &T| -x, Commutative),
322 }
323
324 let xor = OpXor::<u64>::new();
325 assert_eq!(xor.id(), 0);
326 assert_eq!(xor.op(&2, &3), 1);
327 assert_eq!(xor.recip(&1), 1);
328
329 let add = OpAdd::<i32>::new();
330 assert_eq!(add.id(), 0);
331 assert_eq!(add.op(&-1, &2), 1);
332 assert_eq!(add.recip(&2), -2);
333 }
334}