]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | /*! |
2 | @file | |
3 | Forward declares `boost::hana::EuclideanRing`. | |
4 | ||
5 | @copyright Louis Dionne 2013-2016 | |
6 | Distributed under the Boost Software License, Version 1.0. | |
7 | (See accompanying file LICENSE.md or copy at http://boost.org/LICENSE_1_0.txt) | |
8 | */ | |
9 | ||
10 | #ifndef BOOST_HANA_FWD_CONCEPT_EUCLIDEAN_RING_HPP | |
11 | #define BOOST_HANA_FWD_CONCEPT_EUCLIDEAN_RING_HPP | |
12 | ||
13 | #include <boost/hana/config.hpp> | |
14 | ||
15 | ||
16 | BOOST_HANA_NAMESPACE_BEGIN | |
17 | //! @ingroup group-concepts | |
18 | //! @defgroup group-EuclideanRing Euclidean Ring | |
19 | //! The `EuclideanRing` concept represents a commutative `Ring` that | |
20 | //! can also be endowed with a division algorithm. | |
21 | //! | |
22 | //! A Ring defines a binary operation often called _multiplication_ that | |
23 | //! can be used to combine two elements of the ring into a new element of | |
24 | //! the ring. An [Euclidean ring][1], also called an Euclidean domain, adds | |
25 | //! the ability to define a special function that generalizes the Euclidean | |
26 | //! division of integers. | |
27 | //! | |
28 | //! However, an Euclidean ring must also satisfy one more property, which | |
29 | //! is that of having no non-zero zero divisors. In a Ring `(R, +, *)`, it | |
30 | //! follows quite easily from the axioms that `x * 0 == 0` for any ring | |
31 | //! element `x`. However, there is nothing that mandates `0` to be the | |
32 | //! only ring element sending other elements to `0`. Hence, in some Rings, | |
33 | //! it is possible to have elements `x` and `y` such that `x * y == 0` | |
34 | //! while not having `x == 0` nor `y == 0`. We call these elements divisors | |
35 | //! of zero, or zero divisors. For example, this situation arises in the | |
36 | //! Ring of integers modulo 4 (the set `{0, 1, 2, 3}`) with addition and | |
37 | //! multiplication `mod 4` as binary operations. In this case, we have that | |
38 | //! @code | |
39 | //! 2 * 2 == 4 | |
40 | //! == 0 (mod 4) | |
41 | //! @endcode | |
42 | //! even though `2 != 0 (mod 4)`. | |
43 | //! | |
44 | //! Following this line of thought, an Euclidean ring requires its only | |
45 | //! zero divisor is zero itself. In other words, the multiplication in an | |
46 | //! Euclidean won't send two non-zero elements to zero. Also note that | |
47 | //! since multiplication in a `Ring` is not necessarily commutative, it | |
48 | //! is not always the case that | |
49 | //! @code | |
50 | //! x * y == 0 implies y * x == 0 | |
51 | //! @endcode | |
52 | //! To be rigorous, we should then distinguish between elements that are | |
53 | //! zero divisors when multiplied to the right and to the left. | |
54 | //! Fortunately, the concept of an Euclidean ring requires the Ring | |
55 | //! multiplication to be commutative. Hence, | |
56 | //! @code | |
57 | //! x * y == y * x | |
58 | //! @endcode | |
59 | //! and we do not have to distinguish between left and right zero divisors. | |
60 | //! | |
61 | //! Typical examples of Euclidean rings include integers and polynomials | |
62 | //! over a field. The method names used here refer to the Euclidean ring | |
63 | //! of integers under the usual addition, multiplication and division | |
64 | //! operations. | |
65 | //! | |
66 | //! | |
67 | //! Minimal complete definition | |
68 | //! --------------------------- | |
69 | //! `div` and `mod` satisfying the laws below | |
70 | //! | |
71 | //! | |
72 | //! Laws | |
73 | //! ---- | |
74 | //! To simplify the reading, we will use the `+`, `*`, `/` and `%` | |
75 | //! operators with infix notation to denote the application of the | |
76 | //! corresponding methods in Monoid, Group, Ring and EuclideanRing. | |
77 | //! For all objects `a` and `b` of an `EuclideanRing` `R`, the | |
78 | //! following laws must be satisfied: | |
79 | //! @code | |
80 | //! a * b == b * a // commutativity | |
81 | //! (a / b) * b + a % b == a if b is non-zero | |
82 | //! zero<R>() % b == zero<R>() if b is non-zero | |
83 | //! @endcode | |
84 | //! | |
85 | //! | |
86 | //! Refined concepts | |
87 | //! ---------------- | |
88 | //! `Monoid`, `Group`, `Ring` | |
89 | //! | |
90 | //! | |
91 | //! Concrete models | |
92 | //! --------------- | |
93 | //! `hana::integral_constant` | |
94 | //! | |
95 | //! | |
96 | //! Free model for non-boolean integral data types | |
97 | //! ---------------------------------------------- | |
98 | //! A data type `T` is integral if `std::is_integral<T>::%value` is true. | |
99 | //! For a non-boolean integral data type `T`, a model of `EuclideanRing` | |
100 | //! is automatically defined by using the `Ring` model provided for | |
101 | //! arithmetic data types and setting | |
102 | //! @code | |
103 | //! div(x, y) = (x / y) | |
104 | //! mod(x, y) = (x % y) | |
105 | //! @endcode | |
106 | //! | |
107 | //! @note | |
108 | //! The rationale for not providing an EuclideanRing model for `bool` is | |
109 | //! the same as for not providing Monoid, Group and Ring models. | |
110 | //! | |
111 | //! | |
112 | //! [1]: https://en.wikipedia.org/wiki/Euclidean_domain | |
113 | template <typename R> | |
114 | struct EuclideanRing; | |
115 | BOOST_HANA_NAMESPACE_END | |
116 | ||
117 | #endif // !BOOST_HANA_FWD_CONCEPT_EUCLIDEAN_RING_HPP |