# Re: [Python-ideas] [Python-Dev] Inclusive Range

Discussion in 'Python' started by Antoon Pardon, Oct 8, 2010.

1. ### Antoon PardonGuest

On Wed, Oct 06, 2010 at 05:28:13PM -0400, Terry Reedy wrote:
> On 10/6/2010 7:14 AM, Antoon Pardon wrote:
>
> >>That right-hand-half-open intervals (i.e. a<= i< b, equivalently [a,
> >>b) ), which are what Python uses, are to be preferred.
> >>(See aforelinked PDF: http://www.cs.utexas.edu/users/EWD/ewd08xx/EWD831.PDF)

>
> This specifically discusses subsequences of 'natural numbers'.

Sure, but I don't think we should limit ourselves to subsequence of
natural numbers. It is my impression that orginally slices were
also limited to indicating subsequences of natural numbers. This
original limitation, has guided its semantics that resulted in
what we have now,

> >The problem is that the slice notation is sometimes handy in situations where
> >an open interval doesn't allow easily to mark what you want.
> >
> >For instance I have at one time implemted a Tree. This is a dict like structure
> >but it allows to visit the keys in order. Because there is an order, slice
> >notation can make sense. e.g. if T is a tree with names as keys, T['bea':'mike']
> >is a subtree where we have for each key that 'bea'<= key< 'mike'.

>
> >But what if I wanted a subtree where 'mike' was still included, but nothing further?
> >Or what if the keys were floats or tuples and I wanted an inclusive upper boundary?

>
> Strings and tuples are not natural numbers, but do have least
> members ('' and ()), so the bottom end had better be closed.

Why? The fact that we have a bottom element in the item space,
doesn't imply that the sequence I need is easiest defined by
using an inclusive lower limit. What if I wanted all none-empty
strings/tuples keys in the tree? The easiest way to specify that
would be by saying the key needed to be larger than the empty
string/tuple. If the keys were strings I could fudge it by starting
with chr(0), but what value should use as start, if I wanted all
non-empty tuples?

> Since
> substracting strings and tuples in meaningless, the argument of
> having stop-start == number of items does not apply. Floats can be
> subtracted, but the result in not a count of included items. So
> write the .__getitem__ method of *your* class how it best fits your
> use-cases.

My use cases depend on the specific problem I need to solve. Sometimes
the problem is easiest solved with an inclusive limit, sometimes it
is with an exclusive limit. The slice notation although at first sight
a natural way to specify the boundaries, seems on closer inspection
to be too limited.

> Just be aware that an inclusive upper boundary means that
> s[a:b]+s[b:c] will no longer be s[a:c] because b will be duplicated.
> Let me also point out integer slices for builtins are adjusted to
> that they refer to actual slice positions. This is harder to do with
> strings;-). Also, suppose you want all strings beginning with 'a' or
> 'b'. With an open upper end, Tree['a':'c'] will do that. With closed
> upper end, you would need
> Tree['a':'bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb'] or somesuch.

Yes I know. I'm starting to think about aproaching this in a different
manner.

> >And what if you needed the reverse sequence. If you start with inclusive limit,
> >the reverse of a<= item<= b is b>= item>= a. If the second limit is to be
> >exclusive the reverse of a<= item< b becomes (b - 1)>= item> (a - 1).

>
> Slices with positive strides can be defined and understood in terms
> of slice positions before the first item, between all successive
> pairs of items and after the last. By this same definition and
> understanding, s[b:a:-1] should be reversed(s[a:b]), which is what
> many expect. It is not because the definition is given in terms of
> the translation into indexes and blindly applied to the case of
> negative strides without the needed adjustment. I consider this a
> design mistake, at least for many uses. (Extended slices, if not
> extended slicing, were added for numerical Python and they may have
> wanted the current definition for negative strides.)

I agree that this is a design mistake. Personnaly I find it horrible
that in the following expression: L[a:b:-1], it is impossible to
give a numeric value to b, that will include L[0] into the reversed
slice. It is the reason why I avoid reversed slices as much as
possible.

--
Antoon Pardon

Antoon Pardon, Oct 8, 2010

2. ### Steven D'ApranoGuest

On Fri, 08 Oct 2010 10:21:16 +0200, Antoon Pardon wrote:

> Personnaly I find it horrible
> that in the following expression: L[a:b:-1], it is impossible to give a
> numeric value to b, that will include L[0] into the reversed slice.

>>> L = [1, 2, 3, 4, 5]
>>> L[5:-6:-1]

[5, 4, 3, 2, 1]

--
Steven

Steven D'Aprano, Oct 8, 2010

3. ### Jed SmithGuest

On Fri, Oct 8, 2010 at 1:26 PM, Steven D'Aprano
<> wrote:
> On Fri, 08 Oct 2010 10:21:16 +0200, Antoon Pardon wrote:
>
>> Personnaly I find it horrible
>> that in the following expression: L[a:b:-1], it is impossible to give a
>> numeric value to b, that will include L[0] into the reversed slice.

>
>
>
>>>> L = [1, 2, 3, 4, 5]
>>>> L[5:-6:-1]

> [5, 4, 3, 2, 1]

>>> a = [1, 2, 3, 4, 5, 6]
>>> a[::-1]

[6, 5, 4, 3, 2, 1]

--
Jed Smith

Jed Smith, Oct 8, 2010
4. ### Hallvard B FurusethGuest

Jed Smith <> writes:
>>>> a = [1, 2, 3, 4, 5, 6]
>>>> a[::-1]

> [6, 5, 4, 3, 2, 1]

Nice. Is there a trick to get a "-0" index too?
Other than doing 'i or len(L)' instead of 'i', that is.

>>> L = [1,2,3,4,5]
>>> L[2:-2], L[2:-1], L[2:-0] # not quite right

([3], [3, 4], [])

--
Hallvard

Hallvard B Furuseth, Oct 8, 2010
5. ### Arnaud DelobelleGuest

Jed Smith <> writes:

> On Fri, Oct 8, 2010 at 1:26 PM, Steven D'Aprano
> <> wrote:
>> On Fri, 08 Oct 2010 10:21:16 +0200, Antoon Pardon wrote:
>>
>>> Personnaly I find it horrible
>>> that in the following expression: L[a:b:-1], it is impossible to give a
>>> numeric value to b, that will include L[0] into the reversed slice.

^^^^^^^^^^^^^^^^^^
>>
>>
>>
>>>>> L = [1, 2, 3, 4, 5]
>>>>> L[5:-6:-1]

>> [5, 4, 3, 2, 1]

>
>>>> a = [1, 2, 3, 4, 5, 6]
>>>> a[::-1]

> [6, 5, 4, 3, 2, 1]

b doesn't have a numeric value though.

--
Arnaud

Arnaud Delobelle, Oct 8, 2010
6. ### Arnaud DelobelleGuest

Hallvard B Furuseth <> writes:

> Jed Smith <> writes:
>>>>> a = [1, 2, 3, 4, 5, 6]
>>>>> a[::-1]

>> [6, 5, 4, 3, 2, 1]

>
> Nice. Is there a trick to get a "-0" index too?
> Other than doing 'i or len(L)' instead of 'i', that is.
>
>>>> L = [1,2,3,4,5]
>>>> L[2:-2], L[2:-1], L[2:-0] # not quite right

> ([3], [3, 4], [])

'i or None'

--
Arnaud

Arnaud Delobelle, Oct 8, 2010
7. ### Steven D'ApranoGuest

On Fri, 08 Oct 2010 15:53:17 -0400, Jed Smith wrote:

> On Fri, Oct 8, 2010 at 1:26 PM, Steven D'Aprano
> <> wrote:
>> On Fri, 08 Oct 2010 10:21:16 +0200, Antoon Pardon wrote:
>>
>>> Personnaly I find it horrible
>>> that in the following expression: L[a:b:-1], it is impossible to give
>>> a numeric value to b, that will include L[0] into the reversed slice.

>>
>>
>>
>>>>> L = [1, 2, 3, 4, 5]
>>>>> L[5:-6:-1]

>> [5, 4, 3, 2, 1]

>
>>>> a = [1, 2, 3, 4, 5, 6]
>>>> a[::-1]

> [6, 5, 4, 3, 2, 1]

Well of course that works, that is the standard Python idiom for
reversing a sequence.

But the point was that Antoon claimed that there is no numeric value for
the end position that will include L[0] in the reversed slice. My example
shows that this is not correct.

--
Steven

Steven D'Aprano, Oct 9, 2010
8. ### Steven D'ApranoGuest

On Fri, 08 Oct 2010 22:10:35 +0200, Hallvard B Furuseth wrote:

> Jed Smith <> writes:
>>>>> a = [1, 2, 3, 4, 5, 6]
>>>>> a[::-1]

>> [6, 5, 4, 3, 2, 1]

>
> Nice. Is there a trick to get a "-0" index too? Other than doing 'i or
> len(L)' instead of 'i', that is.

What exactly are you expecting? I don't understand why you think that
L[-0] and L[0] would be different, when -0 == 0. I'm also unsure why you
think that there's anything more ("too") to get -- the example shown
reverses the entire list.

Perhaps if you show what result you are expecting, we can show what slice
to give to get it.

>>>> L = [1,2,3,4,5]
>>>> L[2:-2], L[2:-1], L[2:-0] # not quite right

> ([3], [3, 4], [])

--
Steven

Steven D'Aprano, Oct 9, 2010
9. ### Antoon PardonGuest

On Sat, Oct 09, 2010 at 01:37:03AM +0000, Steven D'Aprano wrote:
> On Fri, 08 Oct 2010 15:53:17 -0400, Jed Smith wrote:
>
> > On Fri, Oct 8, 2010 at 1:26 PM, Steven D'Aprano
> > <> wrote:
> >> On Fri, 08 Oct 2010 10:21:16 +0200, Antoon Pardon wrote:
> >>
> >>> Personnaly I find it horrible
> >>> that in the following expression: L[a:b:-1], it is impossible to give
> >>> a numeric value to b, that will include L[0] into the reversed slice.
> >>
> >>
> >>
> >>>>> L = [1, 2, 3, 4, 5]
> >>>>> L[5:-6:-1]
> >> [5, 4, 3, 2, 1]

> >
> >>>> a = [1, 2, 3, 4, 5, 6]
> >>>> a[::-1]

> > [6, 5, 4, 3, 2, 1]

>
>
> Well of course that works, that is the standard Python idiom for
> reversing a sequence.
>
> But the point was that Antoon claimed that there is no numeric value for
> the end position that will include L[0] in the reversed slice. My example
> shows that this is not correct.

I stand by that claim. I think it was fairly obvious that what I meant
was that it was impossible to give such a numeric value that would work
with arbitrary L.

if L2 == list(reversed(L1)) and a and b are in the range 1 < x <= len(L),
we have the following invariant.

L1[a:b] == L2[b-1:a-1:-1]

However this no longer works if either nr is 0. That means that if a and
be are computed values, that may return 0 to indicate which slice you
want; that if you want the reversed slice, there is no straightforward
way to get that reversed slice with extended slice notation.

--
Antoon Pardon

Antoon Pardon, Oct 11, 2010
10. ### Dave AngelGuest

On 2:59 PM, Antoon Pardon wrote:
> On Sat, Oct 09, 2010 at 01:37:03AM +0000, Steven D'Aprano wrote:
> <snip>
>> But the point was that Antoon claimed that there is no numeric value for
>> the end position that will include L[0] in the reversed slice. My example
>> shows that this is not correct.

> I stand by that claim. I think it was fairly obvious that what I meant
> was that it was impossible to give such a numeric value that would work
> with arbitrary L.
>
> if L2 == list(reversed(L1)) and a and b are in the range 1< x<= len(L),
> we have the following invariant.
>
> L1[a:b] == L2[b-1:a-1:-1]
>
> However this no longer works if either nr is 0. That means that if a and
> be are computed values, that may return 0 to indicate which slice you
> want; that if you want the reversed slice, there is no straightforward
> way to get that reversed slice with extended slice notation.
>

Rather than worrying about how to get from one kind of slice to another,
consider that for both forward and reversed slices, there are edge
conditions that are painful. For forward slices, that's when you
sometimes want the end of the list, and sometimes don't. The expression
that says how close to the end you want can be -1, -2, etc. But there's
no -0 notation to say "up and including the last element". For that,
you just omit the ending point, or use the length.

Similarly for reverse slice that may end at the beginning. In order to
generalize it, you have to include the length in your expression.

I think the fact that there are two other idioms that handle it makes
the "problem" mostly irrelevant. Either reverse the slice after taking
it, or use a second slice to chop off zero or more items from the end.

DaveA

Dave Angel, Oct 11, 2010
11. ### Antoon PardonGuest

On Mon, Oct 11, 2010 at 06:25:49AM -0400, Dave Angel wrote:
> On 2:59 PM, Antoon Pardon wrote:
> >On Sat, Oct 09, 2010 at 01:37:03AM +0000, Steven D'Aprano wrote:
> ><snip>
> >>But the point was that Antoon claimed that there is no numeric value for
> >>the end position that will include L[0] in the reversed slice. My example
> >>shows that this is not correct.

> >I stand by that claim. I think it was fairly obvious that what I meant
> >was that it was impossible to give such a numeric value that would work
> >with arbitrary L.
> >
> >if L2 == list(reversed(L1)) and a and b are in the range 1< x<= len(L),
> >we have the following invariant.
> >
> > L1[a:b] == L2[b-1:a-1:-1]
> >
> >However this no longer works if either nr is 0. That means that if a and
> >be are computed values, that may return 0 to indicate which slice you
> >want; that if you want the reversed slice, there is no straightforward
> >way to get that reversed slice with extended slice notation.
> >

> Rather than worrying about how to get from one kind of slice to
> another, consider that for both forward and reversed slices, there
> are edge conditions that are painful.

Why should I not worry. I used to not worry and got stung.

I once without a worry, wrote a testunit that naively depended
on the above invariant. That these edge conditions are painful
for the user of the language is IMO a sign of poor design.

> I think the fact that there are two other idioms that handle it
> makes the "problem" mostly irrelevant. Either reverse the slice
> after taking it, or use a second slice to chop off zero or more
> items from the end.

No the problem is not mostly irrelevant. Sure it is irrelevant for
those who are well informed and know other ways to get what they
want. But for those who are not that fortunate, it is nasty surprise
waiting to happen.

If there are other ways to get what you want and this way can
produce some nasty surprises, I would think that the way this
was included, was a big mistake.

--
Antoon Pardon

Antoon Pardon, Oct 11, 2010
12. ### Ethan FurmanGuest

Antoon Pardon wrote:
> On Sat, Oct 09, 2010 at 01:37:03AM +0000, Steven D'Aprano wrote:
>
>>On Fri, 08 Oct 2010 15:53:17 -0400, Jed Smith wrote:
>>
>>
>>>On Fri, Oct 8, 2010 at 1:26 PM, Steven D'Aprano
>>><> wrote:
>>>
>>>>On Fri, 08 Oct 2010 10:21:16 +0200, Antoon Pardon wrote:
>>>>
>>>>
>>>>>Personnaly I find it horrible
>>>>>that in the following expression: L[a:b:-1], it is impossible to give
>>>>>a numeric value to b, that will include L[0] into the reversed slice.
>>>>
>>>>
>>>>
>>>>>>>L = [1, 2, 3, 4, 5]
>>>>>>>L[5:-6:-1]
>>>>
>>>>[5, 4, 3, 2, 1]
>>>
>>>>>>a = [1, 2, 3, 4, 5, 6]
>>>>>>a[::-1]
>>>
>>>[6, 5, 4, 3, 2, 1]

>>
>>
>>Well of course that works, that is the standard Python idiom for
>>reversing a sequence.
>>
>>But the point was that Antoon claimed that there is no numeric value for
>>the end position that will include L[0] in the reversed slice. My example
>>shows that this is not correct.

>
>
> I stand by that claim. I think it was fairly obvious that what I meant
> was that it was impossible to give such a numeric value that would work
> with arbitrary L.
>
> if L2 == list(reversed(L1)) and a and b are in the range 1 < x <= len(L),
> we have the following invariant.
>
> L1[a:b] == L2[b-1:a-1:-1]

Are you sure?

Python 2.5.4 (r254:67916, Dec 23 2008, 15:10:54) [MSC v.1310 32 bit
(Intel)] on win32
--> L1 = [1, 2, 3, 4, 5]
--> L2 = list(reversed(L1))
--> L1
[1, 2, 3, 4, 5]
--> L2
[5, 4, 3, 2, 1]
--> L1[2:5:1], L2[4:1:-1]
([3, 4, 5], [1, 2, 3])

> However this no longer works if either nr is 0.

In which case it's not an invariant, is it?

~Ethan~

Ethan Furman, Oct 11, 2010
13. ### Antoon PardonGuest

On Mon, Oct 11, 2010 at 05:35:21AM -0700, Ethan Furman wrote:
> Antoon Pardon wrote:
> >On Sat, Oct 09, 2010 at 01:37:03AM +0000, Steven D'Aprano wrote:
> >
> >>On Fri, 08 Oct 2010 15:53:17 -0400, Jed Smith wrote:
> >>

> >
> >I stand by that claim. I think it was fairly obvious that what I meant
> >was that it was impossible to give such a numeric value that would work
> >with arbitrary L.
> >
> >if L2 == list(reversed(L1)) and a and b are in the range 1 < x <= len(L),
> >we have the following invariant.
> >
> > L1[a:b] == L2[b-1:a-1:-1]

>
> Are you sure?

I'm sorry, I was not careful enough in writing this down. It should be
that the invariant holds for 1 <= x < len

>>> a=3
>>> b=7
>>> L1=['e', 'g', 'h', 'k', 'o', 'p', 'r', 't', 'x', 'z']
>>> L2 = list(reversed(L1))
>>> L1

['e', 'g', 'h', 'k', 'o', 'p', 'r', 't', 'x', 'z']
>>> L2

['z', 'x', 't', 'r', 'p', 'o', 'k', 'h', 'g', 'e']
>>> L1[a:b]

['k', 'o', 'p', 'r']
>>> L2[b-1:a-1:-1]

['k', 'o', 'p', 'r']

> >However this no longer works if either nr is 0.

>
> In which case it's not an invariant, is it?

The point being that the breaking of the invariant at that point
is IMO a sign of bad design. It makes it difficult to use the reversed
slice in a general way.

More specifically, if you have a function that produces an a1 and b1,
that in combination with a list, always gives you the desired slice
by writing L[a1:b1]. There is no straigtforward way to transform this
a1 and b1 into a2 and b2, so that L[a2:b2:-1] is the reversed of L[a1:b1]

--
Antoon Pardon

Antoon Pardon, Oct 12, 2010
14. ### Hallvard B FurusethGuest

Steven D'Aprano writes:
> On Fri, 08 Oct 2010 22:10:35 +0200, Hallvard B Furuseth wrote:
>> Jed Smith <> writes:
>>>>>> a = [1, 2, 3, 4, 5, 6]
>>>>>> a[::-1]
>>> [6, 5, 4, 3, 2, 1]

>>
>> Nice. Is there a trick to get a "-0" index too? Other than doing 'i or
>> len(L)' instead of 'i', that is.

>
> What exactly are you expecting? I don't understand why you think that
> L[-0] and L[0] would be different, when -0 == 0.

I don't think that, and I expected just what happened.
As Arnaud Delobelle had answered: I can use 'i or None'.

--
Hallvard

Hallvard B Furuseth, Oct 12, 2010
15. ### Steve HowellGuest

Re: [Python-Dev] Inclusive Range

On Oct 11, 1:40 am, Antoon Pardon <>
wrote:
> On Sat, Oct 09, 2010 at 01:37:03AM +0000, Steven D'Aprano wrote:
> > On Fri, 08 Oct 2010 15:53:17 -0400, Jed Smith wrote:

>
> > > On Fri, Oct 8, 2010 at 1:26 PM, Steven D'Aprano
> > > <> wrote:
> > >> On Fri, 08 Oct 2010 10:21:16 +0200, Antoon Pardon wrote:

>
> > >>> Personnaly I find it horrible
> > >>> that in the following expression: L[a:b:-1], it is impossible to give
> > >>> a numeric value to b, that will include L[0] into the reversed slice.

>
> > >>>>> L = [1, 2, 3, 4, 5]
> > >>>>> L[5:-6:-1]
> > >> [5, 4, 3, 2, 1]

>
> > >>>> a = [1, 2, 3, 4, 5, 6]
> > >>>> a[::-1]
> > > [6, 5, 4, 3, 2, 1]

>
> > Well of course that works, that is the standard Python idiom for
> > reversing a sequence.

>
> > But the point was that Antoon claimed that there is no numeric value for
> > the end position that will include L[0] in the reversed slice. My example
> > shows that this is not correct.

>
> I stand by that claim. I think it was fairly obvious that what I meant
> was that it was impossible to give such a numeric value that would work
> with arbitrary L.
>
> if L2 == list(reversed(L1)) and a and b are in the range 1 < x <= len(L),
> we have the following invariant.
>
>   L1[a:b] == L2[b-1:a-1:-1]
>
> However this no longer works if either nr is 0. That means that if a and
> be are computed values, that may return 0 to indicate which slice you
> want; that if you want the reversed slice, there is no straightforward
> way to get that reversed slice with extended slice notation.
>

Here is a transformation that uses extended slice notation under the
hood, while preserving your semantics for 0 <= l <= h

def reverse_list_slice(lst, l, h):
if l == 0 and h == 0: return []
h = h - 1 if h else None
l = l - 1 if l else None
return lst[h:l:-1]

It's not exactly elegant, but it's not a ton of code either.

Here is how I tested it:

lst = [0, 1, 2, 3, 4]
for a in range(len(lst)):
for width in range(len(lst)-a):
b = a + width
print a, b
rev1 = list(reversed(lst[a:b]))
rev2 = reverse_list_slice(lst, a, b)
if rev1 != rev2:
print a, b
print rev1
print rev2
raise 'invariant broken'

If you want to look at some of the internals for cpython, you can find
them here:

http://svn.python.org/view/python/trunk/Objects/sliceobject.c?view=markup
http://svn.python.org/view/python/trunk/Objects/listobject.c?view=markup

The basic iteration that happens is as follows:

for (cur = start, i = 0; i < slicelength;
cur += step, i++) {
it = src[cur];
Py_INCREF(it);
dest = it;
}

Steve Howell, Oct 13, 2010