RE: [boost] Formal Review for Interval Library beginning

From: David Bergman (davidb_at_[hidden])
Date: 2002-09-03 15:28:12

Peter,

I am quite aware of that ;-)

STL assumes semi-totality of orderings in that "elements are strictly
and totally ordered up to (generated) equivalence". That generated
equivalence is used for efficient sorting algorithms, to be able to
shuffle equivalent (as in incomparable) values. This was also noted in
my post to which you replied.

I consider it to be unsound to use that STL template when dealing with
explicitly partially ordered sets, since the mentioned equivalence (or,
at least implication) is only valid for total orderings and semi-total
orderings (mainly used in sorting algorithms) to enforce a (non-strict)
total ordering.

In other words, equivalence defined by incomparability is invalid when
dealing with partially ordered sets.

And, the '<=' in its ordinary logical interpretation (as a shorthand for
just '<' or '==') also assumes '=='. I could argue that is not sound to
define '<=' in a domain where there is no natural equivalence.

But, this argument is not that productive when dealing with intervals,
since they have a natural equivalence, so we can indead use both '<='
and '=='. We just have to make sure they are consistent, i.e., that 'a
<= b' iff 'a < b || a == b'...

/David

-----Original Message-----
From: boost-bounces_at_[hidden]
[mailto:boost-bounces_at_[hidden]] On Behalf Of Peter Dimov
Sent: Tuesday, September 03, 2002 3:39 PM
To: boost_at_[hidden]
Subject: Re: [boost] Formal Review for Interval Library beginning

From: "David Bergman" <davidb_at_[hidden]>
>
> The user should be forced to realize that he has left total orderings 
> and went into the land of partial orderings, where the "if !(a <= b)" 
> and "if (a > b)" equivalence does not hold. Such shortcuts are *only* 
> allowed in total orderings, else we would end up with the rather 
> unpleasant "(a <= b) != (a < b || a == b)", which is the case here...

You are certainly aware that the STL defines a >= b as !(a < b), aren't
you? The "pleasant"

a <= b :- a < b || a == b

implies the existence of a == b (and that a == b is consistent with a <
b).

In situations where <= is ambiguous, I usually define only < (not even
>) and let the user disambiguate explicitly.

_______________________________________________
Unsubscribe & other changes:
http://lists.boost.org/mailman/listinfo.cgi/boost