Module maths_traits::algebra::group_like

Traits for sets with a single binary operation and various properties of that operation

Currently, the group operation is interpreted as being either the Add or Mul operation, and each of the group properties in this module have both an additive and multiplicative variant.

As it stands currently, there is no real difference between the two, so it is ultimately up to the implementor's preference which one (or both) to use. However, obviously, addition and multiplication carry difference connotations in different contexts, so for clarity and consistency it is suggested to try to follow the general mathematical or programming conventions whenever possible. In particular:

• Try to use multiplication for single operation structures except when convention dictates otherwise (such as the case of string concatenation).
• While the option does exist, avoid implementing a non-commutative or especially a non-associative addition operation unless convention dictates otherwise.
• Avoid implementing both an addition and multiplication where the multiplication doesn't distrubute or where the addition distributes instead.

Implementation

The inclusion of a particular struct into a group-like trait will depend on its implementation of the following properties:

• An additive or multiplicative binary operation:
  • Has some function taking any pair of elements from Self and outputing any other member of Self
  • Represented with either Add and AddAssign or Mul and MulAssign from std::ops
  • (Note that for the auto-implementing categorization traits to work, the corresponding "Assign" traits must be implemented.)
• An identity element:
  • Contains a unique element 0 or 1 such that 0+x=x and x+0=x or 1*x=x,x*1=x for all x
  • Represented with either Zero or One from num_traits
• Invertibility:
  • For every x in the set, there exists some other y in the struct such that x*y=1 and y*x=1 (or x+y=0 and y+x=0 if additive), and there exists a corresponding inverse operation.
  • Represented with either Neg, Sub, and SubAssign or Inv, Div, and DivAssign from std::ops and num_traits
  • Note, again, that the "Assign" variants are required
• Commutative:
  • If the operation is order invariant, ie x+y=y+x or x*y=y*x for all x and y.
  • Represented with AddCommutative or MulCommutative
• Associative:
  • If operation sequences are evaluation order invariant, ie x+(y+z)=(x+y)+z or x*(y*z)=(x*y)*z for all x, y, and z.
  • Represented with AddAssociative or MulAssociative

Exponentiation

In addition to these traits, it may be desirable to implement a multiplication or exponentiation operation with particular integers or naturals. See MulN, MulZ, PowN, and PowZ for more details.

Usage

Structs with these properties implemented will be automatically added to a number of categorization traits for various mathematical sets. These traits all have additive and multiplicative variants and fit into a heirarchy of mathematical structures as such:

    ---Magma---
    |         |
    |     Semigroup
   Loop       |
    |      Monoid
    |         |
    ---Group---
         |
   Abelian Group

where:

• A Magma is a set with any binary operation
• A Semigroup is an associative Magma
• A Monoid is a Semigroup with an identity element
• A Loop is a Magma with an identity element and inverses
• A Group is a Monoid with inverses, or alternatively, an associative Loop
• An Abelian Group is a commutative Group

Re-exports

pub use self::additive::*;

pub use self::multiplicative::*;

Modules

additive	Traits for group-like structures using addition
multiplicative	Traits for group-like structures using Multiplication

Functions

repeated_doubling	Multiplies a monoid by a positive integer using repeated doublings
repeated_doubling_neg	Multiplies a monoid by a positive integer using negation and repeated doublings
repeated_squaring	Raises a monoid element to a positive integer power using the repeated squaring algorithm
repeated_squaring_inv	Raises a monoid element to a integral power using inversion and repeated squaring