[Python-Dev] Fwd: Range __contains__ and objects with __index__ methods

[Mark Dickinson]

.. and here's my original reply to Nick, which was also intended to go
to the list.  Sorry, folks.

Mark



---------- Forwarded message ----------
From: Mark Dickinson <dickinsm at gmail.com>
Date: Mon, Dec 27, 2010 at 10:27 AM
Subject: Re: [Python-Dev] Range __contains__ and objects with __index__ methods
To: Nick Coghlan <ncoghlan at gmail.com>


On Mon, Dec 27, 2010 at 12:15 AM, Nick Coghlan <ncoghlan at gmail.com> wrote:
> Starting in Python 3.2, range() supports fast containment checking for
> integers (i.e. based on an O(1) arithmetic calculation rather than an
> O(N) iteration through the entire sequence).
>
> Currently, this fast path ignores objects that implement __index__ -
> they are relegated to the slow iterative search.
>
> This seems wrong to me [...]

Is seems to me that there are two separate issues here. Namely, (1)
Determine the semantics of 'x in range(...)' for an object x that
implements __index__, and (2) implement the containment check
efficiently.

At the moment, it looks as though the __index__ method is ignored
entirely for the containment check, so you're proposing a change in
semantics.  If/when that change in semantics is made, fixing up the
code to do the containment check efficiently seems like it should be a
straightforward task.

With the proposed change in semantics, the simple definition (x in
range(...) iff x == y for some element y of range(...)) no longer
holds.  I'm not convinced (but not unconvinced either) that it's worth
breaking that simplicity.

Mark