[−][src]Crate free_algebra
Types for constructing free algebras over sets.
What even is a "Free Algebra"?
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 T
and
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
library, the 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
what the 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 ofT
in an associative and commutative manner and allowing distributive multiplication by elements fromR
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
T
is either1
andi
and multiplies accordingly - Quaternions: Same as for Complex numbers, but with more imaginary units
Use cases
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.
Crate structures
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
Specifically:
- MonoidalString constructs free-multiplying structures over a type
T
using an order-dependent internal representation with aVec<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
T
with scalars from some additive typeR
stored 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
Re-exports
pub use self::monoid::*; |
pub use self::module::*; |
Modules
module | Contains ModuleString and the types and traits relevant to its system |
monoid | Contains MonoidalString and the types and traits relevant to its system |
Structs
AddRule | Multiplication of terms using a type's intrinsic addition operation |
FreePow | Represents a free symbol raised to some power |
InvRule | Multiplication of FreeInv elements using concatenation with inverse cancellation |
MulRule | Multiplication of terms using a type's intrinsic multiplication operation |
PowRule | Multiplication between FreePow elements using addition of exponents on equal bases |
Enums
FreeInv | Wraps a type |
Type Definitions
FreeAlgebra | A module over a ring constructed from free multiplication and addition of elements of a set |
FreeGroup | A FreeMonoid, but where each letter can be inverted |
FreeModule | A module over a ring constructed from free addition scalar-multiplication of elements of a set |
FreeMonoid | A monoid constructed from free multiplication of elements of a set |
FreePowMonoid | The free multiplication of members of type |
MonoidRing | A FreeModule over some monoid, but with a multiplication between elements given using the monoid operation |