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. Obviously though, 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 structures with a single operation 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

To implement a struct as a group-like structure, the various group-like trait aliases will be usable according to which and how the following properties are implemented:

• 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 core::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 core::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 integer or natural type. See MulN, MulZ, PowN, and PowZ for more details.

Usage

Structs with the above properties implemented will be automatically usable under a number of trait aliases for particular group-like structures. These structures follow standard mathematical convention and roughly correspond to a heirarchy varying levels of "niceness" of each binary operation.

These structures can be diagrammed as follows:

    ---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

For more information, see Wikipedia's article on algebraic structures

Additional Notes

It is worth noting that this particular system is certainly non-exhaustive and is missing a number of group-like structures. In particular, it is missing the Category-like structures and Quasigroups

In the case of categories, this is because as it stands currently, there are few uses for partial operations while including them would add noticeable complexity.

In the case of quasigroups however, the reason is because with the way the primitive types are designed, the only way to determine if an addition or subtraction operation is truely invertible is to check against the Neg or Inv traits, as the unsigned integers implement both division and subtraction even though technically those operations are not valid on all natural numbers. So seeing as quasigroups aren't particularly useful anyway, the decision was made to omit them.

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