un_algebra 0.9.0

//!
//! Additive groups.
//!
//! An algebraic _additive_ _group_ is an _additive_ _monoid_ `M`, where
//! each group element `g` has a unique additive _inverse_ element
//! denoted `-g`. The inverse operation is called _negation_.
//!
//! # Axioms
//!
//! ```text
//! ∀g, 0 ∈ M
//!
//! Inverse: ∃-g ∈ M: g + -g = -g + g = 0.
//! ```
//!
//! # References
//!
//! See [references] for a formal definition of an additive group.
//!
#![doc(include = "../../doc/references.md")]

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


///
/// An algebraic _additive group_.
///
pub trait AddGroup: AddMonoid {

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


  /// The additive "subtraction" of two group elements.
  fn sub(&self, other: &Self) -> Self {
    self.add(&other.negate())
  }
}


///
/// Laws of additive groups.
///
pub trait AddGroupLaws: AddGroup {

  /// The _left_ _additive_ _inverse_ axiom.
  fn left_inverse(&self) -> bool {
    self.negate().add(self) == Self::zero()
  }


  /// The _right_ _additive_ _inverse_ axiom.
  fn right_inverse(&self) -> bool {
    self.add(&self.negate()) == Self::zero()
  }


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


///
/// Blanket implementation of additive group laws for additive group
/// implementations.
///
impl<G: AddGroup> AddGroupLaws for G {}


///
/// Numeric laws of additive groups.
///
pub trait NumAddGroupLaws: NumEq + AddGroup {

  /// The _left_ _numeric_ _additive_ _inverse_ axiom.
  fn num_left_inverse(&self, eps: &Self::Eps) -> bool {
    self.negate().add(self).num_eq(&Self::zero(), eps)
  }


  /// The _right_ _numeric_ _additive_ _inverse_ axiom.
  fn num_right_inverse(&self, eps: &Self::Eps) -> bool {
    self.add(&self.negate()).num_eq(&Self::zero(), eps)
  }


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


///
/// Blanket implementation of additive group laws for additive group
/// implementations.
///
impl<G: NumEq + AddGroup> NumAddGroupLaws for G {}


///
/// Define `AddGroup` implementations for signed integer types. Probably
/// not needed if Rust had a signed `Integer` super-trait.
///
macro_rules! integer_add_group {
  ($type:ty) => {
    impl AddGroup for $type {

      /// Additive group negation uses "wrapping" negate to avoid
      /// overflow and guarantee the closure axiom.
      fn negate(&self) -> Self {
        self.wrapping_neg()
      }
    }
  };

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


// Only signed integers form an additive group.
integer_add_group! {
  i8, i16, i32, i64, i128, isize
}


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

      // Negation is just floating point negation.
      fn negate(&self) -> Self {
        -*self
      }
    }
  };

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


// Additive group floating point types.
float_add_group! {
  f32, f64
}


///
/// 0-tuples form an additive group.
///
impl AddGroup for () {

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


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

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


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

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


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

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


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

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

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


// Array additive group types.
array_add_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;