Crate un_algebra

Simple implementations of selected abstract algebraic structures.

Rationale

Mathematical abstract algebra is built on a rich collection of algebraic structures. Learning about these structures can give non-mathematicians insights into the mathematical entities they need to work with--for example, real numbers, complex numbers, vectors, matrices, and permutations. By definition, these structures must comply with sets of axioms and properties, which are in turn a rich source of properties for generative testing.

un_algebra ("understanding algebra") is a simple implementation of selected algebraic structures in Rust. I hope it is useful to developers learning abstract algebra concepts for the first time. Currently this crate provides magma, semigroup, quasigroup, monoid, group, ring and field implementations.

Stability

un_algebra is still under pre-version 1.0 development, with a number of outstanding design and implementation issues. Breaking changes are likely to the crate API.

Production use

un_algebra is intended to support self-study of abstract algebraic structures--it is not optimized for use in a production environment. For production environments I recommend using a more sophisticated library like alga.

Compatibility

un_algebra uses 2018 edition features but unfortunately requires Rust nightly as it uses the (experimental) external documentation feature.

Errors

I'm not a mathematician so my implementation of the various structures and their respective axioms in un_algebra may not be strictly correct. Please let me know of any errors.

Please refer to the references document for more background on each structure and its associated axioms and properties.

Glossary

The names of the un_algebra structures and their respective axioms can be long and unwieldy, for example, a "commutative multiplicative group". To keep the exported names workable I use these abbreviations in trait and function names:

• Num for "numeric"
• Add for "additive"
• Com for "commutative"
• Mul for "multiplicative"
• "Rel" for "relation"
• eps for "epsilon"
• prop for "property"

Organization

Each algebraic structure implemented in un_algebra is bundled as a module of structure traits and unit tests of the trait axioms. For example, the modules group, ring, or field.

All structures have an abstract version of the structure trait (for example group::Group), and, where they are commonly used, additive and multiplicative versions of the structure trait (for example add_group::AddGroup and mul_group::MulGroup). These traits are defined using the terminology of addition and multiplication rather than as abstract binary operations.

Each algebraic structure module has sub-modules for its abstract, additive and multiplicative variations, so the group module for example has group, add_group, mul_group, sub-modules.

Axioms and properties

All un_algebra structure traits have associated predicate functions that implement the structure axioms. Some structures also have associated predicate functions that implement derived properties of the structure. These properties are not strictly necessary since they can be derived from the axioms, but they do allow richer generative testing of trait implementations, especially those using floating point numbers.

Axiom and property functions are bundled into "laws" traits, with a blanket implementation for each axiom or property associated trait, e.g. add_group::AddGroupLaws for the add_group::AddGroup trait.

Macros

User defined traits that are implementable by Rust's built-in numeric types seem to quickly lead to a lot of tedious, repeated impl code, or to using tricky self-referential macros. This could be due to missing abstractions in Rust's numeric type hierarchy or (more likely) my lack of Rust experience.

Where a trait's impl code is only repeated a couple of times modules use the boilerplate code approach and in other cases they rely on a macro to create the impl items.

Unit tests

Where un_algebra traits provide unit tests they are generally generative tests built on the proptest generative testing crate. These generative tests test a selection of built-in numeric type with every structure.

Generating test values and test functions seems to require a surprising amount of repetitive, boilerplate code items. Reducing the repeated items is possible via code generation using complex self-referential macros, but I'm not sure this is easier to maintain than the repeated items.

To avoid cluttering up module source files, the unit tests for most modules are defined in separate files. The module source files use the path = attribute to link the source and test files.

Integer types

Rust's built-in integer types (for example i32) are finite subsets of the natural numbers (ℕ). This means they can only satisfy abstract structure axioms with modulo, or "wrapping" addition and multiplication.

Floating point types

Many application data types that in theory conform to modern algebraic structures make heavy use of IEEE floating point numbers. Unfortunately, these numbers are only a finite subset of the real numbers (ℝ) and they do not reliably satisfy even the simplest real number axioms (IEEE).

For working with IEEE floating point types un_algebra provides "numeric" structure axioms and properties that are handy when working with IEEE floating point types, which often require "numeric" comparisons using an "epsilon" or error term.

Examples

un_algebra implements the relevant structure traits for all the Rust standard library integer and floating point numeric types, for example, an additive group for integer types i8, i16, i32, etc. It also provides rational number (ℚ) and complex number (ℂ) examples, based on the num crate.

In addition, the crate examples directory contains abstract structure implementations of selected concepts, for example, finite fields.

Modules

com_group	Commutative group modules.
com_ring	Commutative ring modules.
field	Field modules.
group	Group modules.
helpers	Helper methods for un_algebra modules.
magma	Magma modules.
monoid	Monoid modules.
numeric	Numeric support module for floating point types.
prelude	Re-exports of un-algebra public modules.
quasigroup	Quasigroup modules.
relation	Relation modules.
ring	Algebraic ring modules.
semigroup	Semigroup modules.
tests	Generative testing support for un_algebra axioms and properties.