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

//!
//! Groups.
//!
//! An algebraic _group_ is a _monoid_ `M`, where each group element `g`
//! has a unique _inverse_ element denoted `g^-1`.
//!
//! # Axioms
//!
//! ```text
//! ∀g, e ∈ M
//!
//! Inverse: ∃g^-1 ∈ M: g ∘ g^-1 = g^-1 ∘ g = e.
//! ```
//!
//! # References
//!
//! See [references] for a formal definition of a group.
//!
#![doc(include = "../../doc/references.md")]

use crate::monoid::*;
use crate::helpers::*;


///
/// An algebraic _group_.
///
pub trait Group: Monoid {

  /// The unique _inverse_ of a group element.
  fn inverse(&self) -> Self;


  /// The cancellation of a group element.
  fn cancel(&self) -> Self {
    self.op(&self.inverse())
  }
}


///
/// Laws of groups.
///
pub trait GroupLaws: Group {

  /// The _left_ _inverse_ axiom.
  fn left_inverse(&self) -> bool {
    self.inverse().op(self) == Self::id()
  }


  /// The _right_ _inverse_ axiom.
  fn right_inverse(&self) -> bool {
    self.op(&self.inverse()) == Self::id()
  }


  /// The _two_-_sided_ _inverse_ axiom.
  fn inverses(&self) -> bool {
    self.left_inverse() && self.right_inverse()
  }
}


///
/// Blanket implementation of group laws for group implementations.
///
impl<S: Group> GroupLaws for S {}


///
/// 0-tuples form a group.
///
impl Group for () {

  /// Inverse value can only be `()`.
  fn inverse(&self) -> Self {}
}


///
/// 1-tuples form a group when their items do.
///
impl<A: Group> Group for (A,) {

  /// Inverse is by element type.
  fn inverse(&self) -> Self {
    (self.0.inverse(), )
  }
}


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

  /// Inverse is by element type.
  fn inverse(&self) -> Self {
    (self.0.inverse(), self.1.inverse())
  }
}


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

  /// Inverse is by element type.
  fn inverse(&self) -> Self {
    (self.0.inverse(), self.1.inverse(), self.2.inverse())
  }
}


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

     fn inverse(&self) -> Self {
       self.map(&|&x| x.inverse())
     }
    }
  };

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


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