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

[David Wilson]

On Mon, Sep 22, 2014 at 11:54:03AM -0700, Guido van Rossum wrote:
> On Mon, Sep 22, 2014 at 11:48 AM, <random832 at fastmail.us> wrote:

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

Another concern is structures that rely on comparison could become
performance hazards as they are mixed with user subclasses that perform
nontrivial work in their __lt__ methods, and suchlike. That's a
potentially undesirable trait for a built-in type.

Revisiting my previous concern for blist, I realize it can't be
separated from any hypothetical Tree or SortedDict or whatever else --
it's not possible to avoid every new addition to the stdlib from
becoming an "attractive nuisance". A SortedDict would be as open to
misuse as OrderedDict is today, and there would always be calls for a
blist literal, etc. My only thought would be to make the interface to
such classes sufficiently weird as to ward the unwary away, i.e. not to
support the dict interface.

Grant's reply (accidentally?) went furthest in convincing me there is
sufficient variety in the structures available that fulfill this need,
that I'm probably unqualified to comment on which (if any) are
appropriate for inclusion in the stdlib.


David