un_algebra 0.9.0

//!
//! Algebraic quasigroups.
//!
//! An algebraic _quasigroup_ is a _multiplicative_ _magma_ `M`,
//! equipped with _left_ and _right_ _division_ operators `\` and `/`.
//! The magma multiplication operator is *not* required to be
//! associative. Both division operators must obey _cancellation_
//! axioms.
//!
//! Quasigroups can be defined in terms of one binary operation with the
//! _latin_ _square_ property, but in `un_algebra` quasigroups are
//! defined with separate left and right division operators and axioms.
//!
//! # Axioms
//!
//! ```text
//! ∀x, y ∈ M
//!
//! Left cancellation:  x \ (x × y) = y = x × (x \ y).
//! Right cancellation: (x / y) × y = x = (x × y) / y.
//! ```
//!
//! # References
//!
//! See [references] for a formal definition of a quasigroup.
//!
#![doc(include = "../../doc/references.md")]

use crate::magma::*;
use crate::helpers::*;
use crate::numeric::*;


///
/// An algebraic _quasigroup_.
///
pub trait Quasigroup: MulMagma {

  /// Test for a known divisor quasigroup element.
  fn is_divisor(&self) -> bool;


  /// _Left_-_division_ (`a \ b`) of quasigroup elements.
  fn ldiv(&self, other: &Self) -> Self;


  /// _Right_-_division_ (`a / b`) of quasigroup elements.
  fn rdiv(&self, other: &Self) -> Self;
}


///
/// Laws of quasigroups.
///
pub trait QuasigroupLaws: Quasigroup {

  /// The left axiom of _left-cancellation_.
  fn left_lcancellation(&self, x: &Self) -> bool {
    self.ldiv(&self.mul(x)) == *x
  }


  /// The right axiom of _left-cancellation_.
  fn right_lcancellation(&self, x: &Self) -> bool {
    self.mul(&self.ldiv(x)) == *x
  }


  /// The left axiom of _right-cancellation_.
  fn left_rcancellation(&self, x: &Self) -> bool {
    self.rdiv(x).mul(x) == *self
  }


  /// The right axiom of _right-cancellation_.
  fn right_rcancellation(&self, x: &Self) -> bool {
    self.mul(x).rdiv(x) == *self
  }
}


///
/// Blanket implementation of quasigroup laws for quasigroup
/// implementations.
///
impl<Q: Quasigroup> QuasigroupLaws for Q {}


///
/// Numeric laws of quasigroups.
///
pub trait NumQuasigroupLaws: NumEq + Quasigroup {

  /// The numeric left axiom of _left-cancellation_.
  fn num_left_lcancellation(&self, x: &Self, eps: &Self::Eps) -> bool {
    self.ldiv(&self.mul(x)).num_eq(&x, eps)
  }


  /// The numeric right axiom of _left-cancellation_.
  fn num_right_lcancellation(&self, x: &Self, eps: &Self::Eps) -> bool {
    self.mul(&self.ldiv(x)).num_eq(&x, eps)
  }


  /// The numeric left axiom of _right-cancellation_.
  fn num_left_rcancellation(&self, x: &Self, eps: &Self::Eps) -> bool {
    self.rdiv(x).mul(x).num_eq(&self, eps)
  }


  /// The numeric right axiom of _right-cancellation_.
  fn num_right_rcancellation(&self, x: &Self, eps: &Self::Eps) -> bool {
    self.mul(x).rdiv(x).num_eq(&self, eps)
  }
}


///
/// Blanket implementation of numeric quasigroup laws for quasigroup
/// implementations.
///
impl<Q: NumEq + Quasigroup> NumQuasigroupLaws for Q {}


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

      /// Divisors must be non-zero.
      fn is_divisor(&self) -> bool {
        *self != 0.0
      }


      /// Left division is just floating point division.
      fn ldiv(&self, other: &Self) -> Self {
        other / self
      }


      /// Right division is just floating point division.
      fn rdiv(&self, other: &Self) -> Self {
        self / other
      }
    }
  };

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


// Floating point quasigroups.
float_quasigroup! {
  f32, f64
}


///
/// 0-tuples form a quasigroup.
///
impl Quasigroup for () {

  /// `()` is always a known divisor.
  fn is_divisor(&self) -> bool {
    true
  }


  /// Left-division can only be `()`.
  fn ldiv(&self, _: &Self) -> Self {}


  /// Right-division can only be `()`.
  fn rdiv(&self, _: &Self) -> Self {}
}


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

  /// Known divisor tests are by tuple element.
  fn is_divisor(&self) -> bool {
    self.0.is_divisor()
  }


  /// Left-division is by matching element
  fn ldiv(&self, other: &Self) -> Self {
    (self.0.ldiv(&other.0),)
  }


  /// Right-division is by matching element
  fn rdiv(&self, other: &Self) -> Self {
    (self.0.rdiv(&other.0),)
  }
}


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

  /// Known divisor tests are by tuple element.
  fn is_divisor(&self) -> bool {
    self.0.is_divisor() && self.1.is_divisor()
  }


  /// Left-division is by matching element
  fn ldiv(&self, other: &Self) -> Self {
    (self.0.ldiv(&other.0), self.1.ldiv(&other.1))
  }


  /// Right-division is by matching element
  fn rdiv(&self, other: &Self) -> Self {
    (self.0.rdiv(&other.0), self.1.rdiv(&other.1))
  }
}


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

  /// Known divisor tests are by tuple element.
  fn is_divisor(&self) -> bool {
    let (a, b, c) = self;

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


  /// Left-division is by matching element
  fn ldiv(&self, other: &Self) -> Self {
    (self.0.ldiv(&other.0), self.1.ldiv(&other.1), self.2.ldiv(&other.2))
  }


  /// Right-division is by matching element
  fn rdiv(&self, other: &Self) -> Self {
    (self.0.rdiv(&other.0), self.1.rdiv(&other.1), self.2.rdiv(&other.2))
  }
}


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

      // Delegate to iterator function.
      fn is_divisor(&self) -> bool {
        self.all(&|&x| x.is_divisor())
      }


      // Delegate to `Sequence` trait map_with function.
      fn ldiv(&self, other: &Self) -> Self {
        self.map_with(other, &|&x, &y| x.ldiv(&y))
      }


      // Delegate to `Sequence` trait map_with function.
      fn rdiv(&self, other: &Self) -> Self {
        self.map_with(other, &|&x, &y| x.rdiv(&y))
      }
    }
  };

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


// Array quasigroup types.
array_quasigroup! {
  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;