]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | /*! |
2 | @file | |
3 | Forward declares `boost::hana::Comparable`. | |
4 | ||
b32b8144 | 5 | @copyright Louis Dionne 2013-2017 |
7c673cae FG |
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_COMPARABLE_HPP | |
11 | #define BOOST_HANA_FWD_CONCEPT_COMPARABLE_HPP | |
12 | ||
13 | #include <boost/hana/config.hpp> | |
14 | ||
15 | ||
16 | BOOST_HANA_NAMESPACE_BEGIN | |
17 | //! @ingroup group-concepts | |
18 | //! @defgroup group-Comparable Comparable | |
19 | //! The `Comparable` concept defines equality and inequality. | |
20 | //! | |
21 | //! Intuitively, `Comparable` objects must define a binary predicate named | |
22 | //! `equal` that returns whether both objects represent the same abstract | |
23 | //! value. In other words, `equal` must check for deep equality. Since | |
24 | //! "representing the same abstract value" is difficult to express | |
25 | //! formally, the exact meaning of equality is partially left to | |
26 | //! interpretation by the programmer with the following guidelines:\n | |
27 | //! 1. Equality should be compatible with copy construction; copy | |
28 | //! constructing a value yields an `equal` value. | |
29 | //! 2. Equality should be independent of representation; an object | |
30 | //! representing a fraction as `4/8` should be `equal` to an object | |
31 | //! representing a fraction as `2/4`, because they both represent | |
32 | //! the mathematical object `1/2`. | |
33 | //! | |
34 | //! Moreover, `equal` must exhibit properties that make it intuitive to | |
35 | //! use for determining the equivalence of objects, which is formalized | |
36 | //! by the laws for `Comparable`. | |
37 | //! | |
38 | //! | |
39 | //! Minimal complete definition | |
40 | //! --------------------------- | |
41 | //! 1. `equal`\n | |
42 | //! When `equal` is defined, `not_equal` is implemented by default as its | |
43 | //! complement. For all objects `x`, `y` of a `Comparable` tag, | |
44 | //! @code | |
45 | //! not_equal(x, y) == not_(equal(x, y)) | |
46 | //! @endcode | |
47 | //! | |
48 | //! | |
49 | //! Laws | |
50 | //! ---- | |
51 | //! `equal` must define an [equivalence relation][1], and `not_equal` must | |
52 | //! be its complement. In other words, for all objects `a`, `b`, `c` with | |
53 | //! a `Comparable` tag, the following must hold: | |
54 | //! @code | |
55 | //! equal(a, a) // Reflexivity | |
56 | //! if equal(a, b) then equal(b, a) // Symmetry | |
57 | //! if equal(a, b) && equal(b, c) then equal(a, c) // Transitivity | |
58 | //! not_equal(a, b) is equivalent to not_(equal(a, b)) | |
59 | //! @endcode | |
60 | //! | |
61 | //! | |
62 | //! Concrete models | |
63 | //! --------------- | |
64 | //! `hana::integral_constant`, `hana::map`, `hana::optional`, `hana::pair`, | |
65 | //! `hana::range`, `hana::set`, `hana::string`, `hana::tuple`, | |
66 | //! `hana::type` | |
67 | //! | |
68 | //! | |
69 | //! Free model for `EqualityComparable` data types | |
70 | //! ---------------------------------------------- | |
71 | //! Two data types `T` and `U` that model the cross-type EqualityComparable | |
72 | //! concept presented in [N3351][2] automatically model the `Comparable` | |
73 | //! concept by setting | |
74 | //! @code | |
75 | //! equal(x, y) = (x == y) | |
76 | //! @endcode | |
77 | //! Note that this also makes EqualityComparable types in the | |
78 | //! [usual sense][3] models of `Comparable` in the same way. | |
79 | //! | |
80 | //! | |
81 | //! Equality-preserving functions | |
82 | //! ----------------------------- | |
83 | //! Let `A` and `B` be two `Comparable` tags. A function @f$f : A \to B@f$ | |
84 | //! is said to be equality-preserving if it preserves the structure of the | |
85 | //! `Comparable` concept, which can be rigorously stated as follows. For | |
86 | //! all objects `x`, `y` of tag `A`, | |
87 | //! @code | |
88 | //! if equal(x, y) then equal(f(x), f(y)) | |
89 | //! @endcode | |
90 | //! Equivalently, we simply require that `f` is a function in the usual | |
91 | //! mathematical sense. Another property is [injectivity][4], which can be | |
92 | //! viewed as being a "lossless" mapping. This property can be stated as | |
93 | //! @code | |
94 | //! if equal(f(x), f(y)) then equal(x, y) | |
95 | //! @endcode | |
96 | //! This is equivalent to saying that `f` maps distinct elements to | |
97 | //! distinct elements, hence the "lossless" analogy. In other words, `f` | |
98 | //! will not collapse distinct elements from its domain into a single | |
99 | //! element in its image, thus losing information. | |
100 | //! | |
101 | //! These functions are very important, especially equality-preserving | |
102 | //! ones, because they allow us to reason simply about programs. Also | |
103 | //! note that the property of being equality-preserving is taken for | |
104 | //! granted in mathematics because it is part of the definition of a | |
105 | //! function. We feel it is important to make the distinction here | |
106 | //! because programming has evolved differently and as a result | |
107 | //! programmers are used to work with functions that do not preserve | |
108 | //! equality. | |
109 | //! | |
110 | //! | |
111 | //! Cross-type version of the methods | |
112 | //! --------------------------------- | |
113 | //! The `equal` and `not_equal` methods are "overloaded" to handle | |
114 | //! distinct tags with certain properties. Specifically, they are | |
115 | //! defined for _distinct_ tags `A` and `B` such that | |
116 | //! 1. `A` and `B` share a common tag `C`, as determined by the | |
117 | //! `common` metafunction | |
118 | //! 2. `A`, `B` and `C` are all `Comparable` when taken individually | |
119 | //! 3. @f$ \mathtt{to<C>} : A \to C @f$ and @f$\mathtt{to<C>} : B \to C@f$ | |
120 | //! are both equality-preserving and injective (i.e. they are embeddings), | |
121 | //! as determined by the `is_embedding` metafunction. | |
122 | //! | |
123 | //! The method definitions for tags satisfying the above properties are | |
124 | //! @code | |
125 | //! equal(x, y) = equal(to<C>(x), to<C>(y)) | |
126 | //! not_equal(x, y) = not_equal(to<C>(x), to<C>(y)) | |
127 | //! @endcode | |
128 | //! | |
129 | //! | |
130 | //! Important note: special behavior of `equal` | |
131 | //! ------------------------------------------- | |
132 | //! In the context of programming with heterogeneous values, it is useful | |
133 | //! to have unrelated objects compare `false` instead of triggering an | |
134 | //! error. For this reason, `equal` adopts a special behavior for | |
135 | //! unrelated objects of tags `T` and `U` that do not satisfy the above | |
136 | //! requirements for the cross-type overloads. Specifically, when `T` and | |
137 | //! `U` are unrelated (i.e. `T` can't be converted to `U` and vice-versa), | |
138 | //! comparing objects with those tags yields a compile-time false value. | |
139 | //! This has the effect that unrelated objects like `float` and | |
140 | //! `std::string` will compare false, while comparing related objects that | |
141 | //! can not be safely embedded into the same super structure (like | |
142 | //! `long long` and `float` because of the precision loss) will trigger a | |
143 | //! compile-time assertion. Also note that for any tag `T` for which the | |
144 | //! minimal complete definition of `Comparable` is not provided, a | |
145 | //! compile-time assertion will also be triggered because `T` and `T` | |
146 | //! trivially share the common tag `T`, which is the expected behavior. | |
147 | //! This design choice aims to provide more flexibility for comparing | |
148 | //! objects, while still rejecting usage patterns that are most likely | |
149 | //! programming errors. | |
150 | //! | |
151 | //! | |
152 | //! [1]: http://en.wikipedia.org/wiki/Equivalence_relation#Definition | |
153 | //! [2]: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3351.pdf | |
92f5a8d4 | 154 | //! [3]: http://en.cppreference.com/w/cpp/named_req/EqualityComparable |
7c673cae FG |
155 | //! [4]: http://en.wikipedia.org/wiki/Injective_function |
156 | template <typename T> | |
157 | struct Comparable; | |
158 | BOOST_HANA_NAMESPACE_END | |
159 | ||
160 | #endif // !BOOST_HANA_FWD_CONCEPT_COMPARABLE_HPP |