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.h... 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.)