metaclasses for type comparison

Tim Peters tim.one at comcast.net
Thu Sep 11 23:40:30 CEST 2003


[David Eppstein]
> I don't have 2.3 yet, so haven't used sets yet, but what happens if
> you try to sort a list of sets?
>
> I found a message
> <http://mail.python.org/pipermail/python-bugs-list/2003-January/015454.h
> tml> from Guido wondering about this but didn't see what the response
> was...

It was resolved as suggested there:  an explict cmp() applied to two Sets
raises an exception.  Set1.__lt__(Set2) returns true iff Set1 is a proper
subset of Set2.  list.sort() uses only __lt__ (when it can), so sorting a
list of Sets won't raise an exception (at least not just because __cmp__
raises an exception -- __cmp__ is never called because __lt__ exists), but
it's hard to say something useful about the result.  For example,

>>> from sets import Set
>>> x = [Set([i]) for i in range(10, 0, -1)]
>>> x.sort()
>>> x
[Set([10]), Set([9]), Set([8]), Set([7]), Set([6]), Set([5]), Set([4]),
 Set([3]), Set([2]), Set([1])]
>>>

"x < y" returns false for each distinct pair of sets x and y in that list,
so any permutation of the list is as good an answer as any other.  It so
happens that the 2.3 list.sort() implementation first asks

    x[i] < x[i-1]

for each relevant index position i.  They all say "no", so list.sort()
"deduces" (via assumed trichotomy) that x[i] >= x[i-1] everywhere, so ends
up believing the list is already in sorted order, and leaves it alone after
that one pass over the data.






More information about the Python-list mailing list