un_algebra 0.9.0

//!
//! Multiplicative groups.
//!
//! An algebraic _multiplicative_ _group_ is a _multiplicative_ _monoid_
//! `M`, where each _invertible_ group element `g` has a unique
//! multiplicative _inverse_ denoted `g^-1`. The inverse operation is
//! called _invert_.
//!
//! # Axioms
//!
//! ```text
//! ∀g, 1 ∈ M
//!
//! Inverse: ∃g^-1 ∈ M: g × g^-1 = g^-1 × g = 1.
//! ```
//!
//! # References
//!
//! See [references] for a formal definition of a multiplicative
//! group.
//!
#![doc(include = "../../doc/references.md")]

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


///
/// An algebraic _multiplicative group_.
///
pub trait MulGroup: MulMonoid {

  /// The unique _multiplicative_ _inverse_ of a group element.
  /// Inversion is only defined for _invertible_ group elements.
  fn invert(&self) -> Self;


  /// Test for an _invertible_ group element.
  fn is_invertible(&self) -> bool;


  /// The multiplicative "division" of two group elements.
  fn div(&self, other: &Self) -> Self {
    self.mul(&other.invert())
  }
}


///
/// Laws of multiplicative groups.
///
pub trait MulGroupLaws: MulGroup {

  /// The _left_ _multiplicative_ _inverse_ axiom.
  fn left_inverse(&self) -> bool {
    self.invert().mul(self) == Self::one()
  }


  /// The _right_ _multiplicative_ _inverse_ axiom.
  fn right_inverse(&self) -> bool {
    self.mul(&self.invert()) == Self::one()
  }


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


///
/// Blanket implementation of multiplicative group laws for
/// multiplicative group implementations.
///
impl<G: MulGroup> MulGroupLaws for G {}


///
/// Numeric laws of multiplicative groups.
///
pub trait NumMulGroupLaws: NumEq + MulGroup {

  /// The _left_ _numeric_ _multiplicative_ _inverse_ axiom.
  fn num_left_inverse(&self, eps: &Self::Eps) -> bool {
    self.invert().mul(self).num_eq(&Self::one(), eps)
  }


  /// The _right_ _numeric_ _multiplicative_ _inverse_ axiom.
  fn num_right_inverse(&self, eps: &Self::Eps) -> bool {
    self.mul(&self.invert()).num_eq(&Self::one(), eps)
  }


  /// The _two_-_sided_ _numeric_ _multiplicative_ _inverse_ axiom.
  fn num_inverses(&self, eps: &Self::Eps) -> bool {
    self.num_left_inverse(eps) && self.num_right_inverse(eps)
  }
}


///
/// Blanket implementation of multiplicative group laws for
/// multiplicative group implementations.
///
impl<G: NumEq + MulGroup> NumMulGroupLaws for G {}


///
/// Define `MulGroup` implementations for floating point types. Probably
/// not needed if Rust had a `Float` super-trait.
///
macro_rules! float_mul_group {
  ($type:ty) => {
    impl MulGroup for $type {

      /// Inversion is just floating point inversion.
      fn invert(&self) -> Self {
        1.0 / *self
      }

      /// Non-zero elements are invertible.
      fn is_invertible(&self) -> bool {
        *self != 0.0
      }
    }
  };

  ($type:ty, $($others:ty),+) => {
    float_mul_group! {$type}
    float_mul_group! {$($others),+}
  };
}


// Multiplicative group floating point types.
float_mul_group! {
  f32, f64
}


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

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

  /// The only value is invertible.
  fn is_invertible(&self) -> bool {
    true
  }
}


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

  /// Inversion is by matching element.
  fn invert(&self) -> Self {
    (self.0.invert(), )
  }


  /// Invertibility is across the tuple.
  fn is_invertible(&self) -> bool {
    self.0.is_invertible()
  }
}


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

  /// Inversion is by matching element.
  fn invert(&self) -> Self {
    (self.0.invert(), self.1.invert())
  }


  /// Invertibility is across the tuple.
  fn is_invertible(&self) -> bool {
    self.0.is_invertible() && self.1.is_invertible()
  }
}


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

  /// Inversion is by matching element.
  fn invert(&self) -> Self {
    let (a, b, c) = self;

    (a.invert(), b.invert(), c.invert())
  }


  /// Invertibility is across the tuple.
  fn is_invertible(&self) -> bool {
    let (a, b, c) = self;

    a.is_invertible() && b.is_invertible() && c.is_invertible()
  }
}


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

     // All array items must be invertible.
     fn is_invertible(&self) -> bool {
       self.into_iter().all(|&x| x.is_invertible())
     }


     // Invert all array items.
     fn invert(&self) -> Self {
       self.map(&|&x| x.invert())
     }
    }
  };

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


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


// Module unit tests are in a sub-module.
#[cfg(test)]
mod tests;