Comparable

Description

The Comparable concept defines equality and inequality.

Intuitively, Comparable objects must define a binary predicate named equal that returns whether both objects represent the same abstract value. In other words, equal must check for deep equality. Since "representing the same abstract value" is difficult to express formally, the exact meaning of equality is partially left to interpretation by the programmer with the following guidelines:

1. Equality should be compatible with copy construction; copy constructing a value yields an equal value.
2. Equality should be independent of representation; an object representing a fraction as 4/8 should be equal to an object representing a fraction as 2/4, because they both represent the mathematical object 1/2.

Moreover, equal must exhibit properties that make it intuitive to use for determining the equivalence of objects, which is formalized by the laws for Comparable.

Minimal complete definition

1. equal
   When equal is defined, not_equal is implemented by default as its complement. For all objects x, y of a Comparable tag,

   not_equal(x, y) == not_(equal(x, y))

Laws

equal must define an equivalence relation, and not_equal must be its complement. In other words, for all objects a, b, c with a Comparable tag, the following must hold:

equal(a, a)                                         // Reflexivity
if equal(a, b) then equal(b, a)                     // Symmetry
if equal(a, b) && equal(b, c) then equal(a, c)      // Transitivity
not_equal(a, b) is equivalent to not_(equal(a, b))

Concrete models

hana::integral_constant, hana::map, hana::optional, hana::pair, hana::range, hana::set, hana::string, hana::tuple, hana::type

Free model for <tt>EqualityComparable</tt> data types

Two data types T and U that model the cross-type EqualityComparable concept presented in N3351 automatically model the Comparable concept by setting

equal(x, y) = (x == y)

Note that this also makes EqualityComparable types in the usual sense models of Comparable in the same way.

Equality-preserving functions

Let A and B be two Comparable tags. A function \(f : A \to B\) is said to be equality-preserving if it preserves the structure of the Comparable concept, which can be rigorously stated as follows. For all objects x, y of tag A,

if  equal(x, y)  then  equal(f(x), f(y))

Equivalently, we simply require that f is a function in the usual mathematical sense. Another property is injectivity, which can be viewed as being a "lossless" mapping. This property can be stated as

if  equal(f(x), f(y))  then  equal(x, y)

This is equivalent to saying that f maps distinct elements to distinct elements, hence the "lossless" analogy. In other words, f will not collapse distinct elements from its domain into a single element in its image, thus losing information.

These functions are very important, especially equality-preserving ones, because they allow us to reason simply about programs. Also note that the property of being equality-preserving is taken for granted in mathematics because it is part of the definition of a function. We feel it is important to make the distinction here because programming has evolved differently and as a result programmers are used to work with functions that do not preserve equality.

Cross-type version of the methods

The equal and not_equal methods are "overloaded" to handle distinct tags with certain properties. Specifically, they are defined for distinct tags A and B such that

1. A and B share a common tag C, as determined by the common metafunction
2. A, B and C are all Comparable when taken individually
3. \( \mathtt{to<C>} : A \to C \) and \(\mathtt{to<C>} : B \to C\) are both equality-preserving and injective (i.e. they are embeddings), as determined by the is_embedding metafunction.

The method definitions for tags satisfying the above properties are

equal(x, y)     = equal(to<C>(x), to<C>(y))
not_equal(x, y) = not_equal(to<C>(x), to<C>(y))

Important note: special behavior of <tt>equal</tt>

In the context of programming with heterogeneous values, it is useful to have unrelated objects compare false instead of triggering an error. For this reason, equal adopts a special behavior for unrelated objects of tags T and U that do not satisfy the above requirements for the cross-type overloads. Specifically, when T and U are unrelated (i.e. T can't be converted to U and vice-versa), comparing objects with those tags yields a compile-time false value. This has the effect that unrelated objects like float and std::string will compare false, while comparing related objects that can not be safely embedded into the same super structure (like long long and float because of the precision loss) will trigger a compile-time assertion. Also note that for any tag T for which the minimal complete definition of Comparable is not provided, a compile-time assertion will also be triggered because T and T trivially share the common tag T, which is the expected behavior. This design choice aims to provide more flexibility for comparing objects, while still rejecting usage patterns that are most likely programming errors.

Variables
constexpr auto	boost::hana::comparing
	Returns a function performing equal after applying a transformation to both arguments. More...
constexpr auto	boost::hana::equal
	Returns a Logical representing whether x is equal to y. More...
constexpr auto	boost::hana::not_equal
	Returns a Logical representing whether x is not equal to y. More...

Variable Documentation

comparing

constexpr auto boost::hana::comparing

constexpr

#include <boost/hana/fwd/comparing.hpp>

Initial value:

= [](auto&& f) {
        return [perfect-capture](auto&& x, auto&& y) {
            return equal(f(forwarded(x)), f(forwarded(y)));
        };
    }

Returns a function performing equal after applying a transformation to both arguments.

comparing creates an equivalence relation based on the result of applying a function to some objects, which is especially useful in conjunction with algorithms that accept a custom predicate that must represent an equivalence relation.

Specifically, comparing is such that

comparing(f) == equal ^on^ f

or, equivalently,

comparing(f)(x, y) == equal(f(x), f(y))

Note

This is not a tag-dispatched method (hence it can't be customized), but just a convenience function provided with the Comparable concept.

Signature

Given a Logical Bool and a Comparable B, the signature is \( \mathtt{comparing} : (A \to B) \to (A \times A \to Bool) \).

Example

// Copyright Louis Dionne 2013-2017
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE.md or copy at http://boost.org/LICENSE_1_0.txt)
 
#include <boost/hana/comparing.hpp>
#include <boost/hana/equal.hpp>
#include <boost/hana/group.hpp>
#include <boost/hana/length.hpp>
#include <boost/hana/range.hpp>
#include <boost/hana/tuple.hpp>
namespace hana = boost::hana;
 
 
int main() {
    constexpr auto sequences = hana::make_tuple(
        hana::make_tuple(1, 2, 3),
        hana::make_tuple('x', 'y', 'z'),
        hana::range_c<long, 0, 1>,
        hana::tuple_t<char, int>,
        hana::range_c<int, 0, 2>,
        hana::make_tuple(123.4, nullptr)
    );
 
    constexpr auto grouped = hana::group.by(hana::comparing(hana::length), sequences);
 
    static_assert(grouped == hana::make_tuple(
        hana::make_tuple(
            hana::make_tuple(1, 2, 3),
            hana::make_tuple('x', 'y', 'z')
        ),
        hana::make_tuple(
            hana::range_c<long, 0, 1>
        ),
        hana::make_tuple(
            hana::tuple_t<char, int>,
            hana::range_c<int, 0, 2>,
            hana::make_tuple(123.4, nullptr)
        )
    ), "");
}

equal

constexpr auto boost::hana::equal

constexpr

#include <boost/hana/fwd/equal.hpp>

Initial value:

= [](auto&& x, auto&& y) {
        return tag-dispatched;
    }

Returns a Logical representing whether x is equal to y.

The equal function can be called in two different ways. First, it can be called like a normal function:

equal(x, y)

However, it may also be partially applied to an argument by using equal.to:

equal.to(x)(y) == equal(x, y)

In other words, equal.to(x) is a function object that is equivalent to partial(equal, x). This is provided to enhance the readability of some constructs, especially when using higher order algorithms.

Signature

Given a Logical Bool and two Comparables A and B that share a common embedding, the signature is \( \mathtt{equal} : A \times B \to Bool \).

Parameters

x,y	Two objects to compare for equality.

Example

// Copyright Louis Dionne 2013-2017
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE.md or copy at http://boost.org/LICENSE_1_0.txt)
 
#include <boost/hana/any_of.hpp>
#include <boost/hana/assert.hpp>
#include <boost/hana/equal.hpp>
#include <boost/hana/tuple.hpp>
namespace hana = boost::hana;
 
 
int main() {
    static_assert(hana::equal(hana::make_tuple(1, 2), hana::make_tuple(1, 2)), "");
    static_assert(!hana::equal('x', 'y'), "");
    BOOST_HANA_CONSTANT_CHECK(!hana::equal(hana::make_tuple(1, 2), 'y'));
 
    static_assert(hana::any_of(hana::make_tuple(1, 2, 3), hana::equal.to(2)), "");
}

#### Rationale for the arity of equal It is a valid question whether equal should accept more than 2 arguments and have semantics matching those of Python's ==. This is not supported right now for the following reasons:

• It was implemented in the MPL11, but it was not shown to be useful so far.
• It does not make sense for not_equal to have an arity of more than 2, only equal could maybe have those semantics, which would break symmetry.

not_equal

constexpr auto boost::hana::not_equal

constexpr

#include <boost/hana/fwd/not_equal.hpp>

Initial value:

= [](auto&& x, auto&& y) {
        return tag-dispatched;
    }

Returns a Logical representing whether x is not equal to y.

The not_equal function can be called in two different ways. First, it can be called like a normal function:

not_equal(x, y)

However, it may also be partially applied to an argument by using not_equal.to:

not_equal.to(x)(y) == not_equal(x, y)

In other words, not_equal.to(x) is a function object that is equivalent to partial(not_equal, x). This is provided to enhance the readability of some constructs, especially when using higher order algorithms.

Signature

Given a Logical Bool and two Comparables A and B that share a common embedding, the signature is \( \mathtt{not\_equal} : A \times B \to Bool \).

Parameters

x,y	Two objects to compare for inequality.

Example

// Copyright Louis Dionne 2013-2017
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE.md or copy at http://boost.org/LICENSE_1_0.txt)
 
#include <boost/hana/all_of.hpp>
#include <boost/hana/assert.hpp>
#include <boost/hana/not_equal.hpp>
#include <boost/hana/tuple.hpp>
namespace hana = boost::hana;
 
 
int main() {
    static_assert(hana::not_equal(hana::make_tuple(1, 2), hana::make_tuple(3)), "");
    static_assert(hana::not_equal('x', 'y'), "");
    BOOST_HANA_CONSTANT_CHECK(hana::not_equal(hana::make_tuple(1, 2), 'y'));
 
    static_assert(hana::all_of(hana::make_tuple(1, 2, 3), hana::not_equal.to(5)), "");
}