un_algebra 0.9.0

Simple implementations of selected abstract algebraic structures--including groups, rings, and fields. Intended for self-study of abstract algebra concepts and not for production use.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143

//!
//! Monoids.
//!
//! An algebraic _monoid_ is a _semigroup_ `S`, with a unique _identity_
//! element denoted `e`.
//!
//! # Axioms
//!
//! ```text
//! ∀x ∈ S
//!
//! Identity: ∃e ∈ S: e ∘ x = x ∘ e = x.
//! ```
//!
//! # References
//!
//! See [references] for a formal definition of a monoid.
//!
#![doc(include = "../../doc/references.md")]

use crate::semigroup::*;


///
/// An algebraic _monoid_.
///
pub trait Monoid: Semigroup {

  /// The unique monoid _identity_ _element_.
  fn id() -> Self;


  /// Test for the identity value.
  fn is_id(&self) -> bool {
    *self == Self::id()
  }
}


///
/// Laws of monoids.
///
pub trait MonoidLaws: Monoid {

  /// The _left_ _identity_ axiom.
  fn left_identity(&self) -> bool {
    Self::id().op(self) == *self
  }


  /// The _right_ _identity_ axiom.
  fn right_identity(&self) -> bool {
    self.op(&Self::id()) == *self
  }


  /// The _two_ _sided_ _identity_ axiom.
  fn identity(&self) -> bool {
    self.left_identity() && self.right_identity()
  }
}


///
/// Blanket implementation of monoid laws for monoid implementations.
///
impl<S: Monoid> MonoidLaws for S {}



///
/// 0-tuples form a monoid.
///
impl Monoid for () {

  /// Identity value can only be `()`.
  fn id() -> Self {}
}


///
/// 1-tuples form a monoid when items do.
///
impl<T: Monoid> Monoid for (T,) {

  /// Identity is by element type.
  fn id() -> Self {
    (T::id(), )
  }
}


///
/// 2-tuples form a monoid when items do.
///
impl<A: Monoid, B: Monoid> Monoid for (A, B) {

  /// Identity is by element type.
  fn id() -> Self {
    (A::id(), B::id())
  }
}


///
/// 3-tuples form a monoid when items do.
///
impl<A: Monoid, B: Monoid, C: Monoid> Monoid for (A, B, C) {

  /// Identity is by element type.
  fn id() -> Self {
    (A::id(), B::id(), C::id())
  }
}


///
/// Define `Monoid` implementations for arrays. Maybe not needed if Rust
/// had _const_ _generics_.
///
macro_rules! array_monoid {
  ($size:expr) => {
    impl<T: Copy + Monoid> Monoid for [T; $size] {

      // Create array of identity values.
      fn id() -> Self {
        [T::id(); $size]
      }
    }
  };

  ($size:expr, $($others:expr),+) => {
    array_monoid! {$size}
    array_monoid! {$($others),+}
  };
}


// Array monoid types.
array_monoid! {
  0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16
}