algebra/structure/mod.rs
1// Copyright 2013-2014 The Algebra Developers.
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7// http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15#![deny(missing_docs)]
16
17//! Fundamental algebraic structures.
18//!
19//! ~~~notrust
20//! |(• ◡•)|ノ〵(❍ᴥ❍⋃) - "ALGEBRAIC!!!"
21//! ~~~
22//!
23//! For most applications requiring an abstraction over the reals, `FieldApprox`
24//! should be sufficient.
25//!
26//! # Fundamental algebraic structures
27//!
28//! Most of these traits also come in an approximate flavor for types that do
29//! not satisfy the required properties exactly, but would still benefit from
30//! abstractions over the structure in question.
31//!
32//! ## Algebraic properties
33//!
34//! The goal of algebraic structures is to allow elements of sets to be combined together using one
35//! or several operators. The number and properties of those operators characterize the algebraic
36//! structure. Abstract operators are usually noted `∘`, `+`, or `×`. The last two are preferred
37//! when their behavior conform with the usual meaning of addition and multiplication of reals.
38//! Let `Self` be a set. Here is a list of the most common properties those operator may fulfill:
39//!
40//! ~~~notrust
41//! (Closure) a, b ∈ Self ⇒ a ∘ b ∈ Self,
42//! (Divisibility) ∀ a, b ∈ Self, ∃! r, l ∈ Self such that l ∘ a = b and a ∘ r = b
43//! (Invertibility) ∃ e ∈ Self, ∀ a ∈ Self, ∃ r, l ∈ Self such that l ∘ a = a ∘ r = e
44//! If the right and left inverse are equal they are usually noted r = l = a⁻¹.
45//! (Associativity) ∀ a, b, c ∈ Self, (a ∘ b) ∘ c = a ∘ (b ∘ c)
46//! (Neutral Elt.) ∃ e ∈ Self, ∀ a ∈ Self, e ∘ a = a ∘ e = a
47//! (Commutativity) ∀ a, b ∈ Self, a ∘ b = b ∘ a
48//! ~~~
49//!
50//! When one works with inexact arithmetic, e.g. using floating point numbers, those properties
51//! cannot possibly be satisfied due to the discrete nature of our computing tools. Thus a looser,
52//! *approximate*, version is available. Note that fulfilling a property listed above implies that
53//! its approximate version is fulfilled as well.
54//!
55//! ```notrust
56//! (Approx. Closure) a, b ∈ Self ⇒ ∃ c ≈ a ∘ b such that c ∈ Self,
57//! (Approx. Div.) ∀ a, b ∈ Self, ∃ r, l ∈ Self such that l ∘ a ≈ b and a ∘ r ≈ b
58//! (Approx. Inv.) ∃ e ∈ Self, ∀ a ∈ Self, ∃ r, l ∈ Self such that l ∘ a ≈ e and a ∘ r ≈ e
59//! (Approx. Assoc.) ∀ a, b, c ∈ Self, (a ∘ b) ∘ c ≈ a ∘ (b ∘ c)
60//! (Approx. Neutr.) ∃ e ∈ Self, ∀ a ∈ Self, e ∘ a ≈ a and a ∘ e ≈ a
61//! (Approx. Commut.) ∀ a, b ∈ Self, a ∘ b ≈ b ∘ a
62//! ```
63//!
64//! ## Identity elements
65//!
66//! Two traits are provided that allow the definition of the additive and
67//! multiplicative identity elements:
68//!
69//! - `IdentityAdditive`
70//! - `IdentityMultiplicative`
71//!
72//! ## Group-like structures
73//!
74//! These structures are provided for both the addition and multiplication.
75//!
76//! ~~~notrust
77//! Magma
78//! |
79//! _______/ \______
80//! / \
81//! divisibility associativity
82//! | |
83//! V V
84//! Quasigroup Semigroup
85//! | |
86//! identity identity
87//! | |
88//! V V
89//! Loop Monoid
90//! | |
91//! associativity invertibility
92//! \______ _______/
93//! \ /
94//! |
95//! V
96//! Group
97//! |
98//! commutativity
99//! |
100//! V
101//! AbelianGroup
102//! ~~~
103//!
104//! The following traits are provided:
105//!
106//! - `Closure`(`Additive`|`Multiplicative`)(`Approx`)?
107//! - `Magma`(`Additive`|`Multiplicative`)(`Approx`)?
108//! - `Quasigroup`(`Additive`|`Multiplicative`)(`Approx`)?
109//! - `Loop`(`Additive`|`Multiplicative`)(`Approx`)?
110//! - `Semigroup`(`Additive`|`Multiplicative`)(`Approx`)?
111//! - `Monoid`(`Additive`|`Multiplicative`)(`Approx`)?
112//! - `Group`(`Additive`|`Multiplicative`)(`Approx`)?
113//! - `AbelianGroup`(`Additive`|`Multiplicative`)(`Approx`)?
114//!
115//! ## Ring-like structures
116//!
117//! ~~~notrust
118//! GroupAdditiveAbelian MonoidMultiplicative
119//! \________ ________/
120//! \ /
121//! |
122//! V
123//! Ring
124//! |
125//! commutativity_of_mul
126//! |
127//! V
128//! RingCommutative GroupMultiplicativeAbelian
129//! \_______ ___________/
130//! \ /
131//! |
132//! V
133//! Field
134//! ~~~
135//!
136//! The following traits are provided:
137//!
138//! - `Ring`(`Approx`)?
139//! - `RingCommutative`(`Approx`)?
140//! - `Field`(`Approx`)?
141//!
142//! ## Module-like structures
143//!
144//! ~~~notrust
145//! GroupAdditiveAbelian RingCommutative
146//! \______ _____/
147//! \ /
148//! | |
149//! V V
150//! Module<Scalar> Field
151//! \______ _____/
152//! \ /
153//! | |
154//! V V
155//! VectorSpace<Scalar>
156//! ~~~
157//!
158//! The following traits are provided:
159//!
160//! - `Module`(`Approx`)?
161//! - `VectorSpace`(`Approx`)?
162//!
163//! # Quickcheck properties
164//!
165//! Functions are provided to test that algebraic properties like
166//! assciociativity and commutativity hold for a given set of arguments.
167//!
168//! For example:
169//!
170//! ~~~
171//! # use algebra::structure::SemigroupMultiplicativeApprox;
172//! #[quickcheck]
173//! fn prop_mul_is_associative_approx(args: (i32, i32, i32)) -> bool {
174//! SemigroupMultiplicativeApprox::prop_mul_is_associative_approx(args)
175//! }
176//! ~~~
177
178pub use self::magma::MagmaApprox;
179pub use self::magma::Magma;
180
181pub use self::quasigroup::QuasigroupApprox;
182pub use self::quasigroup::Quasigroup;
183
184pub use self::loop_::LoopApprox;
185pub use self::loop_::Loop;
186
187pub use self::semigroup::SemigroupApprox;
188pub use self::semigroup::Semigroup;
189
190pub use self::monoid::MonoidApprox;
191pub use self::monoid::Monoid;
192
193pub use self::group::GroupApprox;
194pub use self::group::Group;
195
196pub use self::abelian::GroupAbelianApprox;
197pub use self::abelian::GroupAbelian;
198
199pub use self::ring::RingApprox;
200pub use self::ring::Ring;
201pub use self::ring::RingCommutativeApprox;
202pub use self::ring::RingCommutative;
203pub use self::ring::FieldApprox;
204pub use self::ring::Field;
205
206pub use self::module::ModuleApprox;
207pub use self::module::Module;
208pub use self::module::VectorSpaceApprox;
209pub use self::module::VectorSpace;
210
211mod magma;
212mod quasigroup;
213mod loop_;
214mod semigroup;
215mod monoid;
216mod group;
217mod abelian;
218mod ring;
219mod module;