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

//!
//! Algebraic _groups_.
//!
//! An algebraic _group_ is a _monoid_ `M`, where each group element `g`
//! has a unique _inverse_ element denoted `g^-1`.
//!
//! # Axioms
//!
//! ```notrust
//! ∀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())
  }
}


///
/// The _left_ _inverse_ axiom.
///
pub fn left_inverse<T: Group>(x: &T) -> bool {
  x.inverse().op(x) == T::id()
}


///
/// The _right_ _inverse_ axiom.
///
pub fn right_inverse<T: Group>(x: &T) -> bool {
  x.op(&x.inverse()) == T::id()
}


///
/// The _two_-_sided_ inverse axiom.
///
pub fn inverse<T: Group>(x: &T) -> bool {
  left_inverse(x) && right_inverse(x)
}


///
/// 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())
  }
}


///
/// A macro for `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
}