www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - partial orders and opCmp.

reply James McCartney <James_member pathlink.com> writes:
I'm just reading about D for the first time.

It seems that having opCmp instead of overloading operators independantly makes
it impossible to create 
classes which have partial orders instead of total orders. This is unfortunate
if true; partial ordering is a 
common situation.

For example, floating point numbers are not totally ordered due to NaN which is
defined to fail all 
comparisons. It seems you can't write opCmp to cause it to fail all comparisons.
Jan 03 2006
next sibling parent reply Don Clugston <dac nospam.com.au> writes:
James McCartney wrote:
 I'm just reading about D for the first time.
 
 It seems that having opCmp instead of overloading operators independantly makes
 it impossible to create 
 classes which have partial orders instead of total orders. This is unfortunate
 if true; partial ordering is a 
 common situation.
 
 For example, floating point numbers are not totally ordered due to NaN which is
 defined to fail all 
 comparisons. It seems you can't write opCmp to cause it to fail all
comparisons.

At some point D will need an opUnorderedCmp() or similar, to allow overrides of the NCEG operators ( <>, !>=, etc). If an opUnorderedCmp() is available for a class, the definitions of >, >= etc also need to change. I don't think it's particularly difficult to implement, it just hasn't been requested yet. The NCEG operators will make D exceptionally well equipped to deal with partially ordered classes. Two cases that immediately come to mind are a tribool class, and NULL in SQL.
Jan 03 2006
parent reply James Dunne <james.jdunne gmail.com> writes:
Don Clugston wrote:
 James McCartney wrote:
 
 I'm just reading about D for the first time.

 It seems that having opCmp instead of overloading operators 
 independantly makes
 it impossible to create classes which have partial orders instead of 
 total orders. This is unfortunate
 if true; partial ordering is a common situation.

 For example, floating point numbers are not totally ordered due to NaN 
 which is
 defined to fail all comparisons. It seems you can't write opCmp to 
 cause it to fail all comparisons.

At some point D will need an opUnorderedCmp() or similar, to allow overrides of the NCEG operators ( <>, !>=, etc). If an opUnorderedCmp() is available for a class, the definitions of >, >= etc also need to change. I don't think it's particularly difficult to implement, it just hasn't been requested yet. The NCEG operators will make D exceptionally well equipped to deal with partially ordered classes. Two cases that immediately come to mind are a tribool class, and NULL in SQL.

How does an AA come into play here? Can partially ordered classes be used effectively with an AA?
Jan 04 2006
parent Oskar Linde <oskar.lindeREM OVEgmail.com> writes:
James Dunne wrote:

 How does an AA come into play here?  Can partially ordered classes be 
 used effectively with an AA?

Not with the AA as it is implemented currently. But it is very possible to build an efficient AA implementation without needing comparison operators other than opEquals(). A good hash function becomes more important though. /Oskar
Jan 04 2006
prev sibling parent reply Stewart Gordon <smjg_1998 yahoo.com> writes:
James McCartney wrote:
 I'm just reading about D for the first time.
 
 It seems that having opCmp instead of overloading operators 
 independantly makes it impossible to create classes which have 
 partial orders instead of total orders. This is unfortunate if true;
 partial ordering is a common situation.

At the moment, you can't create a class without a total order at all, let alone with a partial order instead. But you can create one with a partial order, by defining your own function to do it.
 For example, floating point numbers are not totally ordered due to 
 NaN which is defined to fail all comparisons. It seems you can't 
 write opCmp to cause it to fail all comparisons.

That's not a partial order, since even NaN <= NaN or NaN == NaN evaluates to false. Stewart. -- -----BEGIN GEEK CODE BLOCK----- Version: 3.1 GCS/M d- s:- C++ a->--- UB P+ L E W++ N+++ o K- w++ O? M V? PS- PE- Y? PGP- t- 5? X? R b DI? D G e++>++++ h-- r-- !y ------END GEEK CODE BLOCK------ My e-mail is valid but not my primary mailbox. Please keep replies on the 'group where everyone may benefit.
Jan 05 2006
parent reply James McCartney <James_member pathlink.com> writes:
In article <dpjbbf$26al$1 digitaldaemon.com>, Stewart Gordon says...

At the moment, you can't create a class without a total order at all, 
let alone with a partial order instead.

But you can create one with a partial order, by defining your own 
function to do it.

Yes, but I can in C++. It would be nice to be able to do it in D.
 For example, floating point numbers are not totally ordered due to 
 NaN which is defined to fail all comparisons. It seems you can't 
 write opCmp to cause it to fail all comparisons.

That's not a partial order, since even NaN <= NaN or NaN == NaN evaluates to false.

Did I say it was partially ordered? No, I didn't: "For example, floating point numbers are not totally ordered"
Jan 05 2006
parent reply Stewart Gordon <smjg_1998 yahoo.com> writes:
James McCartney wrote:
 In article <dpjbbf$26al$1 digitaldaemon.com>, Stewart Gordon says...
 
 At the moment, you can't create a class without a total order at all, 
 let alone with a partial order instead.

 But you can create one with a partial order, by defining your own 
 function to do it.

Yes, but I can in C++. It would be nice to be able to do it in D.

But you can what in C++? Bend the semantics of the < <= > >= operators? I recall reading something in the D spec to the effect that every operator has a specific meaning that should not be messed with, but can't seem to find it now. Those I/O libraries that overload << >> like the old C++ streams are already pushing it, but with the comparison operators being used for AAs and sorting, you'd be best off leaving well alone in any case. And so defining functions in a name of your choice to implement the partial order really is the best way.
 For example, floating point numbers are not totally ordered due to 
 NaN which is defined to fail all comparisons. It seems you can't 
 write opCmp to cause it to fail all comparisons.

evaluates to false.

Did I say it was partially ordered? No, I didn't: "For example, floating point numbers are not totally ordered"

No, but you did say "for example". But yes, it seems that floating points are an exception. I guess you're just not supposed to use NaNs as AA keys or sort an array of floating points that might include NaNs. Stewart. -- -----BEGIN GEEK CODE BLOCK----- Version: 3.1 GCS/M d- s:- C++ a->--- UB P+ L E W++ N+++ o K- w++ O? M V? PS- PE- Y? PGP- t- 5? X? R b DI? D G e++>++++ h-- r-- !y ------END GEEK CODE BLOCK------ My e-mail is valid but not my primary mailbox. Please keep replies on the 'group where everyone may benefit.
Jan 05 2006
parent James McCartney <James_member pathlink.com> writes:
In article <dpjkbj$2fd2$1 digitaldaemon.com>, Stewart Gordon says...

 Bend the semantics of the < <= > >= operators? 

Yes. "bend" them in the same way that mathematics does.
  I recall reading something in the D spec to the effect that every 
operator has a specific meaning that should not be messed with, but 
can't seem to find it now.  

So current mathematics notation has it wrong then?
Jan 05 2006