On Sep 22, 2014, at 11:54, Guido van Rossum <guido@python.org> wrote:

On Mon, Sep 22, 2014 at 11:48 AM, <random832@fastmail.us> wrote:
On Sun, Sep 21, 2014, at 01:18, David Wilson wrote:
> Coming from this perspective, I'd prefer that further additions were
> limited to clean and far better understood structures. In this light,
> could we perhaps instead discuss the merits of a collections.Tree,
> collections.SortedDict or similar?

As I understand it, the problem with a tree, SortedDict/SortedSet, or in
general any collection that relies on comparison relationships (heap,
etc), is: unlike hashing (where Hashable implies an immutable hash
relationship), there is no way to detect whether an object implements an
immutable well-defined ordering. And that, unlike a mutable hashed
object (which can AIUI only lose itself), a mutable sorted object (or a
badly-behaved one like NaN) can cause other objects in the set to be
inserted in the wrong place or not found.

A good point, too often overlooked.

We could introduce a convention requiring __hash__() even though it is not used by the implementation. After all, if the object is immutable when it comes to a well-defined ordering, it is immutable when it comes to equality. I don't really want to think about classes that are immutable when it comes to == but not when it comes to <; that seems terrible.

I went through this and other API issues in 
http://stupidpythonideas.blogspot.com/2013/07/sorted-collections-in-stdlib.html

In addition to the mutability issue, there's also nothing stopping you from adding elements that don't have even a total weak order. You will sometimes get an exception, but often get away with it even though you shouldn't.

Most of the existing implementations seem to take a "consenting users" approach: they document that only immutable objects with a total (strong) order are supported, but don't attempt to check or enforce that, and I didn't find a single bug report or StackOverflow question or rant blog complaining about that.

Obviously the bar would be raised a bit for a collection in, or even recommended by, the stdlib, but I think this might still be acceptable. (Notice that even statically typed languages like C++ and Swift only validate that the objects are less-than-comparable to the same type, not that they're comparable to all possible values of that type.)