# [−][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 of `T` in an associative and commutative manner and allowing distributive multiplication by elements from `R`
• `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 either `1` and `i` 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 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 `T` with scalars from some additive type `R` 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.

## 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 `T` and symbolically inverts elements.

## 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 `C` raised to some power MonoidRing A FreeModule over some monoid, but with a multiplication between elements given using the monoid operation