1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145
//! //!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>`](Vec)! 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>`](Vec) and implemented [multiplication](Mul) as concatenation. In fact, this is *precisely* //!what the [`FreeMonoid<T>`](FreeMonoid) 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>`](FreeModule): Results from freely adding elements of `T` in an associative //! and commutative manner and allowing distributive multiplication by elements from `R` //! * [`FreeAlgebra<R,T>`](FreeAlgebra): 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>`](Vec) 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]. //! //!For more information, see the respective structs //! //! #![feature(specialization)] #![feature(marker_trait_attr)] #![feature(never_type)] #[macro_use] extern crate derivative; extern crate num_traits; extern crate maths_traits; pub use self::monoid::*; pub use self::module::*; use maths_traits::algebra::*; use num_traits::Pow; use std::marker::PhantomData; use std::borrow::Borrow; use std::collections::HashMap; use std::hash::Hash; use std::fmt::{Display, Formatter}; use std::iter::*; macro_rules! impl_arith { (impl<$($T:ident),*> $Trait:ident.$fun:ident with $TraitAssign:ident.$fun_assign:ident for $ty:ty where $($where:tt)*) => { //impl of an op using its assign variant impl<RHS, $($T),*> $Trait<RHS> for $ty where $($where)*, Self:$TraitAssign<RHS> { type Output = Self; #[inline] fn $fun(mut self, rhs:RHS) -> Self {self.$fun_assign(rhs); self} } //impl of an op on a reference impl<'a, RHS, $($T),*> $Trait<RHS> for &'a $ty where $($where)*, $ty:Clone+$Trait<RHS> { type Output = <$ty as $Trait<RHS>>::Output; #[inline] fn $fun(self, rhs:RHS) -> Self::Output {(*self).clone().$fun(rhs)} } }; (impl<$($T:ident),*> $TraitAssign:ident<&$RHS:ident>.$fun_assign:ident for $ty:ty where $($where:tt)*) => { //impl of an op with a reference impl<'a, $($T),*> $TraitAssign<&'a $RHS> for $ty where $($where)*, Self:$TraitAssign<$RHS>, $RHS:Clone { #[inline] fn $fun_assign(&mut self, rhs:&'a $RHS) {self.$fun_assign((*rhs).clone())} } } } pub(self) trait IsZero: Sized { fn _is_zero(&self) -> bool; fn _zero() -> Option<Self>; } impl<T> IsZero for T { default fn _is_zero(&self) -> bool { false } default fn _zero() -> Option<Self> {None} } impl<T:Zero> IsZero for T { default fn _is_zero(&self) -> bool { self.is_zero() } default fn _zero() -> Option<Self> { Some(Self::zero()) } } pub use self::specifics::*; mod specifics; pub mod monoid; pub mod module;