Types for constructing free algebras over sets.
In the context of this crate, the term "Algebra" refers to a range of mathematical constructions involving arithmetic operations, and the term "Free" refers to the nature of those operations. In particular, a "free" operation is one that is made with as little restriction as possible with respect to the desired set of rules.
So, in general, the procedure for such a "free" construction is to start with some type
some set of algebraic rules, and then operated on the elements of
T as if they were a variable
or symbol, applying the rules as necessary.
As abstract as that sounds, there is actually a prime example of this already in the standard
Vec<T>! If we start with some type
T, assert that multiplication be associative,
and start multiplying elements like variables, the result is exactly the same as if we took
Vec<T> and implemented multiplication as concatenation. In fact, this is precisely
FreeMonoid<T> type in this crate is.
use maths_traits::algebra::One; use free_algebra::FreeMonoid; let x: FreeMonoid<char> = FreeMonoid::one(); let y = FreeMonoid::one() * 'a' * 'b'; let z = FreeMonoid::one() * 'c' * 'd'; assert_eq!(x, vec!); assert_eq!(y, vec!['a', 'b']); assert_eq!(z, vec!['c', 'd']); assert_eq!(&y * &z, vec!['a', 'b', 'c', 'd']); assert_eq!(&z * &y, vec!['c', 'd', 'a', 'b']);
In addition to this, moreover, a number of other constructions can be achieved by changing which types are used, which operations are considered, and what rules are followed. Examples include:
FreeModule<R,T>: Results from freely adding elements of
Tin an associative and commutative manner and allowing distributive multiplication by elements from
FreeAlgebra<R,T>: The same as with FreeModule, except that we allow for free multiplication of elements distributively (like with FreeMonoid)
- Polynomials: A FreeAlgebra, but where multiplication between
T's is commutative and associative
- Clifford algebra: A FreeAlgebra, but where multiplication is associative and an element times itself results in a scalars
- Complex numbers: Results from when
iand multiplies accordingly
- Quaternions: Same as for Complex numbers, but with more imaginary units
The primary purposes for this crate fall into two general categories:
- Use as an abstract foundation to create more specific systems like polynomials or Clifford algebras.
- Utilization as a tool for lazily storing costly arithmetic operations for future evaluation.
This crate consists of the following:
- Two main structures for doing the free-arithmetic over some type
- Traits for specifying the rules for arithmetic
- Type aliases for particular combinations of construction and rules
- MonoidalString constructs free-multiplying structures over a type
Tusing an order-dependent internal representation with a
Vec<T>that determines its multiplication rule using an implementor of the trait MonoidRule. Aliases of this struct include FreeMonoid and FreeGroup.
- ModuleString constructs types consisting of terms of type
Twith scalars from some additive type
Rstored with an order independent HashMap. This grants all ModuleString's an addition operation by adding the coeffients of like terms, and a free-multiplication can be included using an optional AlgebraRule parameter. Aliases of this struct include FreeModule and FreeAlgebra.
For more information, see the respective structs
Contains ModuleString and the types and traits relevant to its system
Contains MonoidalString and the types and traits relevant to its system
Multiplication of terms using a type's intrinsic addition operation
Represents a free symbol raised to some power
Multiplication of FreeInv elements using concatenation with inverse cancellation
Multiplication of terms using a type's intrinsic multiplication operation
Multiplication between FreePow elements using addition of exponents on equal bases
Wraps a type
A module over a ring constructed from free multiplication and addition of elements of a set
A FreeMonoid, but where each letter can be inverted
A module over a ring constructed from free addition scalar-multiplication of elements of a set
A monoid constructed from free multiplication of elements of a set
The free multiplication of members of type
A FreeModule over some monoid, but with a multiplication between elements given using the monoid operation