Would there be support for a more general cmp/__cmp__

Antoon Pardon apardon at forel.vub.ac.be
Wed Oct 26 10:18:58 CEST 2005


Op 2005-10-25, Christopher Subich schreef <csubich.spam.block at spam.subich.block.com>:
> Antoon Pardon wrote:
>
>> I also think there is the problem that people aren't used to partial
>> ordering. There is an ordering over sets, it is just not a total
>> ordering. But that some pairs are uncomparable (meaning that neither
>> one is smaller or greater) doesn't imply that comparing them is
>> ill defined.
>
> It depends on your definition of "comparison."  Admittedly, <, =, !=, 
> and > can be defined for a partial ordering, but classical mathematics, 
> as understood by most people (even programmers), assumes that unless a 
>== b, a > b or a < b.
>
> The comparisons, as defined this way, are done on a totally ordered set, 
> yes.  But since most comparisons ever done -are- done on a totally 
> ordered set (namely the integers or reals), it's entirely fair to say 
> that "a programmer's expectation" is that comparisons should work more 
> or less like a totally ordered list.
>
>
> With that caevat in mind, comparison on a partially ordered domain /is/ 
> ill-defined; it can give inconsistent results from the "a < b or a > b 
> or a == b" rule.

Against people expectations is not the same as inconsistent.

>> 
>> Well it is a wrong assumption is general. There is nothing impure about
>> partial ordering. 
>
> Impure? Probably not.  Useless from many perspective when "comparisons" 
> are needed, to the point where it's probably safer to throw an exception 
> than define results.
>
>> That is IMO irrelevant. The subset relationship is an ordering and as
>> such has all characteristics of other orderings like "less than",
>> except that the subset relationship is partial and the less than
>> relationship is total. How it is called "subset" vs "less than" is
>> IMO irrelevant. It is about mathematical characteristics.
>
> Still accident.  < wouldn't be used for sets if we had a subset symbol 
> on the standard keyboard, APL fans notwithstanding.

That is only because people usualy work with numbers and sets at the
same time and using different symbols helps making the distinction.

But using <= for subset is mathematical completely correct. If you
want to go purely formal, numbers are just a particular family of
sets where the less than or equal relation of numbers coincides with
the subset relation of sets in that family.

People use the multiplication symbol for multiplying matrices although
matrix multiplication is something different from number multiplication.

If the multiplications of matrices is enough like the multiplication of
numbers to use the same symbol, I see nothing wrong in using the same
symbol for the (strict) subset relation as is used for the less than
(or equal) relation on numbers.

> Simce programmers 
> familiar with Python understand that < on sets isn't a "real" comparison 
> (i.e. provide a total order), they don't expect unique, consistent 
> results from something like sort (or a tree, for that matter).

>> 
>>>By analogy, one can ask, "is the cat inside the box?" and get the answer
>>>"No", but this does not imply that therefore the box must be inside the
>>>cat.
>> 
>> 
>> Bad analogy, this doesn't define a mathematical ordering, the subset
>> relationship does.
>
> Yes, it does.  Consider "in" as a mathematical operator:

My appologies, I though you were going in the "I can in my coat,
my coat can in the box" kind of direction.

> For the set (box, cat-in-box)
>
> box in box: False
> box in cat-in-box: False
> cat-in-box in box: True
> cat-in-box in cat-in-box: False
>
> For the set (box, smart-cat) # cat's too smart to get in the box
>
> box in box: False
> box in smart-cat: False
> smart-cat in box: False
> smart-cat in smart-cat: False
>
> In both these cases, the "in" operator is irreflexive, asymmetric, and 
> transitive (extend to mouse-in-cat if you really care about transitive), 
> so "in" is a partial order sans equality.  A useless one, but a partial 
> order nonetheless.

I don't know if it is useless. This kind of relationship seems very
common in political geography.

This village is in this county, this county is in this state, this state
is in this nation.

Also magizines that test certain equipment to give advice on the best
buy, usualy work with methods that result in partial orderings.

>>>Notice that L1 and L2 contain the same elements, just in different orders.
>>>Sorting those two lists should give the same order, correct?
>> 
>> 
>> No. Since we don't have a total ordering, sorting doesn't has to give
>> the same result. For as far as sorting is defined on this kind of
>> object, the only thing I would expect is that after a sort the
>> following condition holds.
>> 
>> for all i,j if i < j then not L[i] > L[j]
>
> Highly formal, aren't you?

I like the precision it provides.

> Again, common programming allows for "not a > b"
> == "a <= b", so your condition becomes the more familiar:
>
> for all i,j in len(list), if i < j then L[i] <= L[j]

So, should we limit our programming to the common cases
or should a language also provide help for the uncommon
case.

> This condition is also assumed implicitly by many other assumed "rules" 
> of sorted lists, namely their uniqueness:
>
> "If L is a list of unique keys, then sort(L) is a unique list of keys in 
> sorted order."
>
> Yes, this assumes that L has a total order.  Big whoop -- this is a 
> matter of programming practiciality rather than mathematical purity.

I don't find it so practical if the language limits the programmer
to the common cases. I can understand that implementation issues
impose limits on what can pratically realised and often enough that
is the more common practice. So in this case it is about programming
practiciality. But you seem to think it is programming practiciality
if you limit yourself to the common case from the beginning, even
if implementing for a more general case wouldn't be much harder
then implementing only the common case.

-- 
Antoon Pardon



More information about the Python-list mailing list