On Mon, Sep 22, 2014 at 11:54:03AM -0700, Guido van Rossum wrote:
On Mon, Sep 22, 2014 at 11:48 AM, <random832@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