[Python-Dev] binary trees.

[Josiah Carlson]

"Vladimir 'Yu' Stepanov" <vys at renet.ru> wrote:
> Josiah Carlson wrote:
> > This problem has nothing to do with dictionaries and hashing, it has to
> > do with the fact that there may not be a total ordering on the elements
> > of a sequence.
> 
> It is sad. I did not know it. Therefore and have not understood.
> 
> I have looked in Google on "python dev total ordering". On intentions to
> correct this problem I have not found anything. It already earlier was
> discussed ?

Not really.  It has to do with how non-comparable instances compare to
each other.  Generally speaking, when instances aren't comparable,
Python compares their type, which is actually comparing the names of
types. This wouldn't be a big deal, except that:

>>> str < tuple < unicode
True

And you can actually compare str and unicode, so, if you have a str that
is greater than the unicode, you run into this issue.  With unicode
becoming str in Py3k, we may not run into this issue much then, unless
bytes are comparable to str, in which case we end up witht the same
problems.

Actually, according to my google of "python dev total ordering", it
gives me...

http://mail.python.org/pipermail/python-dev/2003-March/034169.html
http://mail.python.org/pipermail/python-list/2003-March/154142.html

Which were earlier discussions on this topic, which are quite topical. 
The ultimate solution is to choose a total ordering on types and
consider the problem solved.  Then list.sort() and binary trees will
work properly.


 - Josiah