### 1 unstable release

0.1.0 | Nov 9, 2019 |
---|

#**1561** in Math

**MIT**license

64KB

717 lines

Types for constructing free algebras over sets in the Rust programming language.

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

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.`T`

As abstract as that sounds, there is actually a prime example of this already in the standard
library, the

! If we start with some type `Vec``<`T`>`

, assert that multiplication be associative,
and start multiplying elements like variables, the result is exactly the same as if we took
`T`

and implemented multiplication as concatenation. In fact, this is `Vec``<`T`>`*precisely*
what the

type in this crate is.`FreeMonoid <T>`

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

: Results from freely adding elements of`FreeModule``<`R,T`>`

in an associative and commutative manner and allowing distributive multiplication by elements from`T``R`

: The same as with`FreeAlgebra``<`R,T`>`

, except that we allow for free multiplication of elements distributively (like with`FreeModule`

)`FreeMonoid`- Polynomials: A

, but where multiplication between`FreeAlgebra`

's is commutative and associative`T` - Clifford algebra: A

, but where multiplication is associative and an element times itself results in a scalars`FreeAlgebra` - Complex numbers: Results from when

is either`T`

and`1`

and multiplies accordingly`i` - 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 structure

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:

constructs free-multiplying structures over a type`MonoidalString`

using an order-dependent internal representation with a`T`

that determines its multiplication rule using an implementor of the trait`Vec``<`T`>`

. Aliases of this struct include`MonoidRule`

and`FreeMonoid`

.`FreeGroup`

constructs types consisting of terms of type`ModuleString`

with scalars from some additive type`T`

stored with an order independent`R`

. This grants all`HashMap`

's an addition operation by adding the coefficients of like terms, and a free-multiplication can be included using an optional`ModuleString`

parameter. Aliases of this struct include`AlgebraRule`

and`FreeModule`

.`FreeAlgebra`

For more information, see the respective structs in the docs

#### Dependencies

~2MB

~50K SLoC