On Fri, Jul 25, 2014 at 11:27:57PM -0700, Walter Bright via Digitalmars-d wrote:
> On 7/25/2014 11:05 PM, H. S. Teoh via Digitalmars-d wrote:
[...]
> >In the meantime, I think much of the confusion comes from the current documentation not be adequately clear about the reasoning behind having opCmp and opEquals, so it's too easy to get the wrong impression that defining opCmp is enough to make things work, or to have a fuzzy inaccurate understanding for how opCmp interacts with opEquals, and when/why to use each. I think a documentation PR is in order.
> 
> I welcome a PR from you on this!

https://github.com/D-Programming-Language/dlang.org/pull/620


T

-- 
Give a man a fish, and he eats once. Teach a man to fish, and he will sit forever.

On 26 July 2014 19:48, Andrei Alexandrescu via Digitalmars-d < digitalmars-d@puremagic.com> wrote:

> On 7/26/14, 2:19 AM, "Marc Schütz" <schuetzm@gmx.net>" wrote:
>
>> On Saturday, 26 July 2014 at 07:42:05 UTC, Ola Fosheim Grøstad wrote:
>>
>>> On Saturday, 26 July 2014 at 06:50:11 UTC, Manu via Digitalmars-d wrote:
>>>
>>>> It's okay, I hate it too.
>>>> But I equally can't abide == meaning something different than <, <=,
>>>> etc.
>>>> That's insane.
>>>>
>>>
>>> Yes, it is unsound to use opCmp for types that aren't totally ordered:
>>>
>>
>> Yes, that's why it's possible to provide opEquals in addition to opCmp. But for the vast majority of cases, opEquals _is_ equivalent to opCmp == 0, and element-wise equality is not. Defining opEquals to be the latter by default _even in the presence of opCmp_ is therefore wrong in almost all cases.
>>
>
> Case-insensitive ordering is a simple example. Field for field comparison is the right default whether or not opCmp is defined.
>

...you're trolling me right?

Just to be clear, you're saying you think it's reasonable for <, <=, >=, >
to perform case insensitive comparison for ordering purposes, but for ==,
!= to be case sensitive for equality comparisons?
You're saying you think that's what the user *probably* wants, by default?
Is there precedent for something like this? I've never seen anything like
it.
It creates very awkward relationships between the suite of operators which
is likely to break down in many logical constructs.

I don't understand; your example is the perfect example of why opCmp==0
should be the default opEquals, but somehow it's an argument against? I
have no idea how to reason about this topic.
I come from a place where <,<=,==,!=,>=,> are a suite, and it is reasonable
to assume they all work the same. Is that not the default presumption of
modern programmers? Is it really so unlikely that people would make the
mistake of assuming they are related?

On 7/26/14, 7:58 PM, Manu via Digitalmars-d wrote:
> On 26 July 2014 19:48, Andrei Alexandrescu via Digitalmars-d
> <digitalmars-d@puremagic.com <mailto:digitalmars-d@puremagic.com>> wrote:
>
>     On 7/26/14, 2:19 AM, "Marc Schütz" <schuetzm@gmx.net
>     <mailto:schuetzm@gmx.net>>" wrote:
>
>         On Saturday, 26 July 2014 at 07:42:05 UTC, Ola Fosheim Grøstad
>         wrote:
>
>             On Saturday, 26 July 2014 at 06:50:11 UTC, Manu via
>             Digitalmars-d wrote:
>
>                 It's okay, I hate it too.
>                 But I equally can't abide == meaning something different
>                 than <, <=,
>                 etc.
>                 That's insane.
>
>
>             Yes, it is unsound to use opCmp for types that aren't
>             totally ordered:
>
>
>         Yes, that's why it's possible to provide opEquals in addition to
>         opCmp.
>         But for the vast majority of cases, opEquals _is_ equivalent to
>         opCmp ==
>         0, and element-wise equality is not. Defining opEquals to be the
>         latter
>         by default _even in the presence of opCmp_ is therefore wrong in
>         almost
>         all cases.
>
>
>     Case-insensitive ordering is a simple example. Field for field
>     comparison is the right default whether or not opCmp is defined.
>
>
> ...you're trolling me right?

No.

> Just to be clear, you're saying you think it's reasonable for <, <=, >=,
>  > to perform case insensitive comparison for ordering purposes, but for
> ==, != to be case sensitive for equality comparisons?

Odder examples have been shown here in support of various other points. I certainly think it's possible, and it's not a bug by definition.

> You're saying you think that's what the user *probably* wants, by
> default?

Yes.

> Is there precedent for something like this?

In all likelihood.

>  I've never seen
> anything like it.

Time to expand one's social circle :o).

> It creates very awkward relationships between the suite of operators
> which is likely to break down in many logical constructs.

Doesn't seem that drastic to me.

> I don't understand; your example is the perfect example of why opCmp==0
> should be the default opEquals, but somehow it's an argument against? I
> have no idea how to reason about this topic..

You yourself seemed to reach for an operator ===. In fact those comparisons you think should exist already exist: what you claim "==" should be is really !(a < b) && !(b < a) or !opCmp(a, b); and what you think "===" should be is really "==".

> I come from a place where <,<=,==,!=,>=,> are a suite, and it is
> reasonable to assume they all work the same.

I think that place is not a good place. That's not a reasonable assumption.

> Is that not the default
> presumption of modern programmers?

No.

> Is it really so unlikely that people
> would make the mistake of assuming they are related?

Yes.


Andrei

In order to get an overview for myself I've summarized the various properties of different types of orders as they are described in Wikipedia (right or wrong). I post it here in case others have an interest in it (or corrections/extensions to it):

* Preorder:

a ≤ a (reflexivity)

if a ≤ b and b ≤ c then a ≤ c (transitivity)


* Non-strict Partial Order:

a ≤ a (reflexivity);

if a ≤ b and b ≤ c then a ≤ c (transitivity).

if a ≤ b and b ≤ a then a = b (antisymmetry);


* Strict Partial Order:

not a < a (irreflexivity),

if a < b and b < c then a < c (transitivity), and

if a < b then not b < a (asymmetry; implied by irreflexivity and transitivity).


* Total Order:

a ≤ b or b ≤ a (totality).

If a ≤ b and b ≤ c then a ≤ c (transitivity);

If a ≤ b and b ≤ a then a = b (antisymmetry);


* Pseudo-Order:

not (a < b and b < a) (antisymmetry)

if a < b then a < c or c < b (co-transivity/comparison)

if not (a < b or b < a) then a = b (equality)


a#b ===  a < b or b < a (apartness/negation of equality)
http://en.wikipedia.org/wiki/Apartness_relation


* Total Preorder:

x ≲ b or b ≲ a (totality).

if a ≲ b and b ≲ c then a ≲ c (transitivity).

x ≲ b (reflexivity; implied by transitivity and totality)


* Strict Weak Order: (complement of a total preorder)

not a < a (irreflexivity).

if a < b and b < c then a < c (transitivity).

if a < b then not b < a (asymmetry; implied by irreflexivity and transitivity).

if a is incomparable with y, and b is incomparable with z, then a is incomparable with c (transitivity of incomparability).

On Sunday, 27 July 2014 at 13:06:23 UTC, Ola Fosheim Grøstad wrote:
> * Total Preorder:
>
> x ≲ b or b ≲ a (totality).
>
> if a ≲ b and b ≲ c then a ≲ c (transitivity).
>
> x ≲ b (reflexivity; implied by transitivity and totality)

Correction:

* Total Preorder:

a ≲ b or b ≲ a (totality).

if a ≲ b and b ≲ c then a ≲ c (transitivity).

a ≲ a (reflexivity; implied by transitivity and totality)

Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> wrote:
>> It creates very awkward relationships between the suite of operators which is likely to break down in many logical constructs.
> 
> Doesn't seem that drastic to me.
> 
>> I don't understand; your example is the perfect example of why opCmp==0 should be the default opEquals, but somehow it's an argument against? I have no idea how to reason about this topic..
> 
> You yourself seemed to reach for an operator ===. In fact those
> comparisons you think should exist already exist: what you claim "=="
> should be is really !(a < b) && !(b < a) or !opCmp(a, b); and what you
> think "===" should be is really "==".
> 
>> I come from a place where <,<=,==,!=,>=,> are a suite, and it is reasonable to assume they all work the same.
> 
> I think that place is not a good place. That's not a reasonable assumption.
> 
>> Is that not the default
>> presumption of modern programmers?
> 
> No.
> 
>> Is it really so unlikely that people
>> would make the mistake of assuming they are related?
> 
> Yes.

I also strongly disagree with that.
opCmp and opEquals should be separate because only one of them may make
sense for a type. But if both make sense they should agree.

Of course there exist many possible sorting orders for a type, but the
standard comparison operators should always be the natural ones.
For other orders you have predicate based sorting.

As I understand it, that's also Walters argument why breaking code is ok in that case, because if   they don't agree, the code was already buggy in the first place.

At very least *I* would be surprised inconsistent comparison operators. And if I wasn't, I still wouldn't implement it like that because I'm sure that someone at some time will be confused by it.

Tobi

On Saturday, 26 July 2014 at 16:43:06 UTC, Fool wrote:
>> NaN < x is false
>> NaN > x is false
>
> ...which means that < as it is usually defined on floating point numbers does not define a strict weak ordering.

Are you sure?

Properties of a Strict Weak Ordering:

#1 not(a < a)
#2 not(a < b and b < c) or a < c
#3 not(a < b) or (not b < a)
#4 not(a < b) or (a < c or c < b or ( a < c and c < b))

#1 is always true
#2 is always true if any of a,b,c are NaN
#3 and #4 are always true if any of a,b are NaN by "not(a<b)"

>> if you try to derive equality from that you would get:
>>
>> NaN == x is true
>
> This is not a contradiction to what I wrote.

Maybe you are right, but it does not match up to what I arrived at based on the properties for Strict Weak Ordering listed in Wikipedia.

On Sunday, 27 July 2014 at 16:39:01 UTC, Ola Fosheim Grøstad wrote:
> On Saturday, 26 July 2014 at 16:43:06 UTC, Fool wrote:
>>> NaN < x is false
>>> NaN > x is false
>>
>> ...which means that < as it is usually defined on floating point numbers does not define a strict weak ordering.
>
> Are you sure?

One can define a strict weak ordering using different (but equivalent) sets of axioms.

We have

NOT (0.0 < NaN) AND NOT (NaN < 0.0)   [0.0 and NaN are incomparable]

AND

NOT (NaN < 1.0) AND NOT (1.0 < NaN)   [NaN and 1.0 are incomparable]

However, it does NOT hold

NOT (0.0 < 1.0) AND NOT (1.0 < 0.0)   [0.0 and 1.0 are incomparable]

Thus we do not have transitivity of incomparability:

"For all x, y, and z, if x is incomparable with y, and y is incomparable with z, then x is incomparable with z." [1]

[1] https://en.wikipedia.org/wiki/Weak_ordering#Strict_weak_orderings

On Sunday, 27 July 2014 at 18:00:29 UTC, Fool wrote:
> Thus we do not have transitivity of incomparability:

You are right, I forgot to test the case where only c is NaN. Well, that makes floats suck even more! :-)

On Sunday, 27 July 2014 at 00:43:40 UTC, H. S. Teoh via Digitalmars-d wrote:
> https://github.com/D-Programming-Language/dlang.org/pull/620

Thank you for this.

There is still a problem, I think.

Defining opEquals only makes sense if a user wants to replace equality by some equivalence relation (different from equality).

The user is not forced to define opEquals such that it models an equivalence relation but it hardly makes sense.

Similarly, the user is free to define opCmp without restriction. In practice, however, it does not seem to make any sense if <= does not even model a preorder (reflexive and transitive) or one of >, <=, < does not match.

It turns out that intuition of many people around here is not at random. Let A be a set and <= a preorder on A. For all a, b in A define ~ such that a ~ b = (a <= b or b <= a). Then ~ is an equivalence relation. (Let me know if you need a proof.)

Clearly, it is possible to define different equivalence relations on a set. The same is true for orderings.

Now opEquals and opCmp are used to define a default equivalence relation and ordering on a type, respectively.

Please excuse my lack of creativity: in presence of opCmp I cannot see a single sensible use case for defining a.opEquals(b) different from a.opCmp(b) == 0.

Those examples mentioned before are skewed.

If a candidate for opCmp does not match the default equivalence relation == (defined implicitly or explicitly specified using opEquals) it should not be defined at all.