[Python-ideas] Putting `blist` into collections module

[Andrew Barnert]

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

> On Mon, Sep 22, 2014 at 11:48 AM, <random832 at 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.)
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-ideas/attachments/20140922/c84fb21f/attachment-0001.html>