[−][src]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:
- An identity element:
- Contains a unique element
0
or1
such that0+x=x
andx+0=x
or1*x=x
,x*1=x
for allx
- Represented with either
Zero
orOne
fromnum_traits
- Contains a unique element
- Invertibility:
- For every
x
in the set, there exists some othery
in the struct such thatx*y=1
andy*x=1
(orx+y=0
andy+x=0
if additive), and there exists a corresponding inverse operation. - Represented with either
Neg
,Sub
, andSubAssign
orInv
,Div
, andDivAssign
fromstd::ops
andnum_traits
- Note, again, that the "Assign" variants are required
- For every
- Commutative:
- If the operation is order invariant, ie
x+y=y+x
orx*y=y*x
for allx
andy
. - Represented with
AddCommutative
orMulCommutative
- If the operation is order invariant, ie
- Associative:
- If operation sequences are evaluation order invariant, ie
x+(y+z)=(x+y)+z
orx*(y*z)=(x*y)*z
for allx
,y
, andz
. - Represented with
AddAssociative
orMulAssociative
- If operation sequences are evaluation order invariant, ie
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 |