Summary: I suggest that the C++ language is augmented with a new type for
use with comparisons relative a relation, and library functions making use
of that.

Description: The type to be used with relation comparisons that I
tentatively have experimented with is
  relate = { unrelated, less, equal, greater }
In a C++ language addition, I think of these as being 5 new keywords
added, with the type coercion to signed integer types
  unrelated <-> -2
  less      <-> -1
  equal     <->  0
  greater   <->  1
The values here are chosen in order to comply with already existing C++
comparisons functions.

The mathematical background is briefly as follows: Given a set A, a
relation R is a subset of A. If x, y in A, one often writes xRy instead of
(x, y).

In the computer version, the function
  compare: A x A -> relate
associated with the relation R describes simultaneously the values xRy and
yRx. This gives the following table
    xRy  |  yRx  | compare(x, y)
   ---------------------------------
   false | false | unrelated
   true  | false | less
   false | true  | greater
   true  | true  | equal

Further, in my experience, computer types often make use of more than one
relation: Firstly, types often have a natural order, given by their
semantics. In addition, fundamental in computer programming is the access
to a total order, which can be used for sorting purposes, when using them
as keys in a associative array "map", etc. More exotic is the access to a
well ordering, which shows up when one should solve equations, and need
not only to eliminate the components in a certain order, but in addition
needs to make sure that the process terminates.

A simple case where the three different relations disagree, is the product
Z x Z, where Z are the integers. Z has a natural total order <=, which is
not a well ordering; a well ordering is given by 0, +1, -2, +2, -2, ... Z
x Z does not have a natural order; in mathematics, one might use (x1, y1)
<= (x2, y2)  <=>  x1 <= x2 and y1 <= y2. Then for example, (1, 0) and (1,
0) are unrelated, so this is a partial order. The lexicographical order is
a natural candidate for a total order on Z x Z. And the lexicographical
order of the well ordering on Z is a well ordering on Z x Z.

Thus, for a C++ proposal, I come up with the suggestion of the following
library functions:
  relate compare(const A&, const B&);
  relate total(const A&, const B&);
  relate well(const A&, const B&);
Here, "compare" relates to the natural order, "total" to the total order,
and "well" to the well ordering of the types involved.

The function "well" may be viewed as rather exotic; I simply mention it.
But the two functions "compare" and "total" will of be fundamental use in
programming, and should be added.

The function "compare" is the one normally used when calling the operator
<, <=, ==, !=, >, >=. For example
  template<class A, class B>
  relate operator!=(const A& a, const B& b)
  {  return compare(a, b) != equal;  }

  template<class A, class B>
  relate operator<=(const A& a, const B& b) {
    relate r = compare(a, b);
    return r == less || r == equal;
  }

The difference between "compare" and "total" is easily seen when dealing
with polymorphic types: If A and B are two different types, and a in A, b
in B, then normally compare(a, b) gives the value "unrelated", but
total(a, b) must give one of the values { less, equal, greater }. If there
is a total order between the types (like a collation order), and the types
A and B have total orders, then this can be used to define a total order o
the disjoint union of A and B. In terms of the C++ typeid and type_info
facilities, one could write
  template<class A, class B>
  relate compare(const A& a, const B& b) {
    if (typeid(a) != typeid(b))  return unrelated;
    return compare(a, b);
  }

  template<class A, class B>
  relate total(const A& a, const B& b) {
    if (typeid(a) != typeid(b))
      return typeid(a).before(b)? less : greater;
    return total(a, b);
  }
If the type type_info is given a "total" function, this could be simplified to
  template<class A, class B>
  relate total(const A& a, const B& b) {
    if (typeid(a) != typeid(b))
      return total(typeid(a), typeid(b));
    return total(a, b);
  }

Thus, the type "relate" expresses features already present in C++ in a
unifying manner.

Motivation and background: Comparisons are very fundamental in computer
programming, much so than in say mathematics. One reason for adding such a
type is to make the code simplified and more streamlined.

The motivation for the type "relate" itself with its four members is
firstly that it allows comparisons with any type of relation, not simply
total orders, and that all four 2-bit combinations are filled up in an
underlying typical implementation.

But also, those relations typically encountered in computer programming
supplies the full "relate" information at a decision point. That is, even
if one for a given relation R only decides to find out say if xRy is true,
the computations usually start a comparison between x and y until one
reaches a decision point when the complete information about xRy and yRx
is provided. This is the case, for example, in the case of lexicographical
orderings.

Thus, making use of the type "relate" and a comparisons functions
"compare" usually will simplify and speed up the code.

Background: In the language Haskell 98, there is a type Ordering(LT, EQ,
GT), but not this only allows for comparisons with total orders. Adding
the element "unrelated" not only has the advantage that comparisons with
any relation can take place, but makes the type "relate" take up all four
2-bit combinations.

  Hans Aberg      * Anti-spam: remove "remove." from email address.
                  * Email: Hans Aberg <remove.haberg@member.ams.org>
                  * Home Page: <http://www.matematik.su.se/~haberg/>
                  * AMS member listing: <http://www.ams.org/cml/>

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

Hans Aberg wrote:
>
> Summary: I suggest that the C++ language is augmented with a new type for
> use with comparisons relative a relation, and library functions making use
> of that.
>
> Description: The type to be used with relation comparisons that I
> tentatively have experimented with is
>   relate = { unrelated, less, equal, greater }
> In a C++ language addition, I think of these as being 5 new keywords
> added, with the type coercion to signed integer types
>   unrelated <-> -2
>   less      <-> -1
>   equal     <->  0
>   greater   <->  1
> The values here are chosen in order to comply with already existing C++
> comparisons functions.
>

I agree this type would be valuable, but I don't see a reason to
make it built-in. A library type std::relate would IMHO be quite
sufficient (and have less impact on programs which don't use it)

Also, I'd prefer the type named "relation" instead of "relate".
After all, it's a type, not a function, so by convention it's
name should be a noun, not a verb.

[...]

> Thus, for a C++ proposal, I come up with the suggestion of the following
> library functions:
>   relate compare(const A&, const B&);
>   relate total(const A&, const B&);
>   relate well(const A&, const B&);
> Here, "compare" relates to the natural order, "total" to the total order,
> and "well" to the well ordering of the types involved.
>
> The function "well" may be viewed as rather exotic; I simply mention it.
> But the two functions "compare" and "total" will of be fundamental use in
> programming, and should be added.
>
> The function "compare" is the one normally used when calling the operator
> <, <=, ==, !=, >, >=. For example
>   template<class A, class B>
>   relate operator!=(const A& a, const B& b)
>   {  return compare(a, b) != equal;  }
>
>   template<class A, class B>
>   relate operator<=(const A& a, const B& b) {
>     relate r = compare(a, b);
>     return r == less || r == equal;
>   }
>
> The difference between "compare" and "total" is easily seen when dealing
> with polymorphic types: If A and B are two different types, and a in A, b
> in B, then normally compare(a, b) gives the value "unrelated", but
> total(a, b) must give one of the values { less, equal, greater }. If there
> is a total order between the types (like a collation order), and the types
> A and B have total orders, then this can be used to define a total order o
> the disjoint union of A and B. In terms of the C++ typeid and type_info
> facilities, one could write
>   template<class A, class B>
>   relate compare(const A& a, const B& b) {
>     if (typeid(a) != typeid(b))  return unrelated;
>     return compare(a, b);
>   }

This looks like an infinite recursion.

>
>   template<class A, class B>
>   relate total(const A& a, const B& b) {
>     if (typeid(a) != typeid(b))
>       return typeid(a).before(b)? less : greater;
>     return total(a, b);
>   }

Likewise.

> If the type type_info is given a "total" function, this could be simplified to
>   template<class A, class B>
>   relate total(const A& a, const B& b) {
>     if (typeid(a) != typeid(b))
>       return total(typeid(a), typeid(b));
>     return total(a, b);
>   }

And again.

I still don't understand what those functions (called on
_arbitrary_ types!) are supposed to do (OK, compare
something, but what?)

[...]

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

In article <3ADFE6A1.DCE45523@dollywood.itp.tuwien.ac.at>, Christopher
Eltschka <celtschk@dollywood.itp.tuwien.ac.at> wrote:
 The type to be used with relation comparisons that I
>> tentatively have experimented with is
>>   relate = { unrelated, less, equal, greater }
>> In a C++ language addition, I think of these as being 5 new keywords
>> added, with the type coercion to signed integer types
...
>I agree this type would be valuable, but I don't see a reason to
>make it built-in. A library type std::relate would IMHO be quite
>sufficient (and have less impact on programs which don't use it)

I do not object to this either; in fact, before one knows how useful the
type is, one could add it to the std namespace, in order to avoid it
littering the general namespace.

>Also, I'd prefer the type named "relation" instead of "relate".
>After all, it's a type, not a function, so by convention it's
>name should be a noun, not a verb.

Well, I gave thought to that too, but a relation is a subset of A x A,
period. So that did not seem right.

The name "relate" is an abbreviation of the "relate value", just as one
abbreviates "real number" to "real".

Names like "ordering" seemed not right either; I wanted a short word
closer to "relation".

>>   template<class A, class B>
>>   relate compare(const A& a, const B& b) {
>>     if (typeid(a) != typeid(b))  return unrelated;
>>     return compare(a, b);
>>   }
>
>This looks like an infinite recursion.

In the implementation I used
   template<class A, class B>
   relate compare(const A& a, const B& b) {
     if (typeid(a) != typeid(b))  return unrelated;
     return a.compare(b);
   }
and
   template<class A, class B>
   relate total(const A& a, const B& b) {
     if (typeid(a) != typeid(b))
       return typeid(a).before(b)? less : greater;
     return a.total(b);
   }
or
   template<class A, class B>
   relate total(const A& a, const B& b) {
     if (typeid(a) != typeid(b))
       return total(typeid(a), typeid(b));
     return a.total(b);
   }
which avoids the infinite recursion. (Or allow the restraint A != B on
template arguments, and the recursion goes away, as well.) That is, a
class A has the
   relate A::compare(const A&) const;
   relate A::total(const A&) const;

>I still don't understand what those functions (called on
>_arbitrary_ types!) are supposed to do (OK, compare
>something, but what?)

This was just an illustration of the difference between "compare" and
"total" in a polymorphic context. Typically, one has a set of classes
restricted to a class hierarchy, and this describes the semantics one
would end up with. Different classes are typically unrelated in their
natural (semantic) order, but in a total order, they must be sorted.

I'm not sure what the exact library template functions one might add, but
that is an interesting question. One would probably rewrite STL using the
new "relate" type though. (Some wants the STL to be rewritten anyhow, in
view of experience gained with it.)

Another interesting question that I decided to not treat, is that many
want orders such as "compare" and "total" to automatically be induced by
the language (with suitable language indicators). This is possible, for
example, Haskell.

  Hans Aberg      * Anti-spam: remove "remove." from email address.
                  * Email: Hans Aberg <remove.haberg@member.ams.org>
                  * Home Page: <http://www.matematik.su.se/~haberg/>
                  * AMS member listing: <http://www.ams.org/cml/>

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]