Possible improvement to slice opperations.

[Ron Adam]

After considering several alternatives and trying out a few ideas with a
modified list object Bengt Richter posted, (Thank You), I think I've
found a way to make slice operation (especially far end indexing)
symmetrical and more consistent.

So to find out if this is indeed a possibility, it would be nice to get
a few opinions at this point. So blast away... or hopefully tell me
what you like about it instead. ;-)

(Any suggestions or contributions to make it better would be appreciated.)

Cheers,
Ron Adam

"""
IMPROVED SLICING
=============== =

Slicing is one of the best features of Python in my opinion, but
when you try to use negative index's and or negative step increments
it can be tricky and lead to unexpected results.

This topic has come up fairly often on comp.lang.pytho n, and often
times, the responses include:

* Beginners should avoid negative extended slices.

* Slices with negative step increments are for advanced
python programmers.

* It's not broke if you look at it in a different way.

* You should do it a different way.

All of these and various responses similar to them are unsatisfactory in
my opinion and it's a good indicator it's not as good as it could be.
Indexing and slice operations are vary common in Python and I don't
think we should be discouraging people from learning and using them.
COMPATIBILITY
-------------
Because the following suggested changes will break current code,
it probably can not be implemented prior to Python 3000.

+ Direct indexing with both positive and negative values
returns the same items as they do now.

+ Extended slices with all positive and or empty default
values remain unchanged.

- Extended slices with negative values return values that
have less items than currently.

- Slices with negative step values return entirely different
results.
REVERSE ORDER STEPPING
----------------------
When negative steps are used, a slice operation
does the following. (or the equivalent)

1. reverse the list
2. cut the reversed sequence using start and stop
3. iterate forward using the absolute value of step.

* This order results in an inverse selection and I believe should be
considered a bug.

Changing the order in the following way results in a much
more predictable pattern which is both easier to understand and use.

1. cut sequence using start and stop.
2 reverse the order of the results.
3. iterate forward using the absolute value of step.
CURRENT INDEXING
----------------

Given a range [a,b,c]:

Positive indexing

| a | b | c |
+---+---+---+
0 1 2 3

Current negative indexing.

| a | b | c |
+---+---+---+
-3 -2 -1 -0
When a single index is used the item to the
right of the index for both positive and
negative index's is returned.

With slices, the items between start, and
stop index's are returned.

Accessing a range at the end of a list numerically
becomes inconvenient when negative index's are used
as the '-0'th position can not be specified numerically
with negative values.
ONES BASED NEGATIVE INDEXING
----------------------------
Making negative index's Ones based, and selecting
individual item to the left of negative index's would enable
addressing the end of the list numerically.

Ones based negative index's.

| a | b | c |
+---+---+---+
-4 -3 -2 -1

Then:

a[-1] -> c # item left of index, same result as now.

a[-3:-2] -> b # item between index's

a[-1:-1] = [d] # insert item at the end.

USE OF '~' IN PLACE OF NEGATIVE INDEX'S
---------------------------------------

The '~' is the binary not symbol which when used
with integers returns the two's compliment. This
works nice with indexing from the end of a list
because convieniently ~0 == -1.

This creates a numerical symmetry between positive
indexing and '~' "End of list" indexing.

a[0] -> first item in the list.
a[~0] -> last item in the list.

a[0:~0] -> whole list.

a[1:~1] -> center, one position from both ends.

* Note: using '~' works as described here in place of single negative
index's in current versions of Python. It does not work as described
here for extended slices.

"""

# TEST LIST CLASS.
"""
A list class to Test '~' end of list indexing.

* This class modifies the slice before returning
a value. The final implementation may do this by
modifying slice objects directly or the underlying
C code of sequences.

"""

class nxlist(object):

def __init__(self, value):
self.value = value

def normslc(self, slc):
start,stop,step = slc.start, slc.stop, slc.step
if type(start) == int and start<0:
start = len(self.value) +start+1
if type(stop) == int and stop<0:
stop = len(self.value) +stop+1
return slice(start,sto p,step)

def __getitem__(sel f, i):
tp = i.__class__
if tp == int:
if i>=0:
return self.value[i]
else:
return self.value[ len(self.value) +i ]
if tp == slice:
slc = self.normslc(i)
value = self.value[slc.start:slc.s top]
if type(i.step) == int and i.step<0:
value.reverse()
slc = slice(None,None ,-i.step)
else:
slc = slice(None,None ,i.step)
return value[slc]

#def __setitem__(sel f, i, v):
#Not emplimented yet.

def __repr__(self): return 'nxlist(%r)'%se lf.value
a = nxlist(range(10 ))
print a

testdata = [
('a[0]'),
('a[1]'),
('a[~0]'),
('a[~1]'),
('a[:]'),
('a[:~1]'),
('a[~1:]'),
('a[::]'),
('a[0:~0]'),
('a[1:~1]'),
('a[~1:1]'),
('a[::-2]'),
('a[:3]'),
('a[3:]'),
('a[~3:]'),
('a[:~3]'),
('a[:3:-1]'),
('a[3::-1]'),
('a[~3::-1]'),
('a[:~3:-1]'),
('a[:3:-2]'),
('a[3::-2]'),
('a[~3::-2]'),
('a[:~3:-2]'),
]

for n, s in enumerate(testd ata):
print '%r. %s = %r' % (n,s,eval(s))
"""
nxlist([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])
0. a[0] = 0
1. a[1] = 1
2. a[~0] = 9
3. a[~1] = 8
4. a[:] = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
5. a[:~1] = [0, 1, 2, 3, 4, 5, 6, 7, 8]
6. a[~1:] = [9]
7. a[::] = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
8. a[0:~0] = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
9. a[1:~1] = [1, 2, 3, 4, 5, 6, 7, 8]
10. a[~1:1] = []
11. a[::-2] = [9, 7, 5, 3, 1]
12. a[:3] = [0, 1, 2]
13. a[3:] = [3, 4, 5, 6, 7, 8, 9]
14. a[~3:] = [7, 8, 9]
15. a[:~3] = [0, 1, 2, 3, 4, 5, 6]
16. a[:3:-1] = [2, 1, 0]
17. a[3::-1] = [9, 8, 7, 6, 5, 4, 3]
18. a[~3::-1] = [9, 8, 7]
19. a[:~3:-1] = [6, 5, 4, 3, 2, 1, 0]
20. a[:3:-2] = [2, 0]
21. a[3::-2] = [9, 7, 5, 3]
22. a[~3::-2] = [9, 7]
23. a[:~3:-2] = [6, 4, 2, 0]
"""
r = range(10)
a = nxlist(r)

print r[~0],a[~0] # ok
print r[~3:],a[~3:] # one off
print r[~3::-1],a[~3::-1] # other side
print r[~3::-2],a[~3::-2] # other side
"""
Comparisons of negative indexing and '~'
indexing with same values.

current, proposed

9 9
[6, 7, 8, 9] [7, 8, 9]
[6, 5, 4, 3, 2, 1, 0] [9, 8, 7]
[6, 4, 2, 0] [9, 7]
"""

[Ron Adam]

Steve Holden wrote:

It's a common misconception that all ideas should be explainable simply.
This is not necessarily the case, of course. When a subject is difficult
then all sorts of people bring their specific misconceptions to the
topic, and suggest that if only a few changes were made the whole thing
would be easier to understand.
What misconception do you think I have?

Unfortunately, while that might make the topic in question easier to
understand for some it would make it difficult, and even
counter-intuitive, for others.
True, and that's why asking and getting opinions on a subject is a good
idea.

As many have said before me, there's a reason why slicing and
indexing are the way they are. The interfaces were designed by people
with long years of programming and teaching experience.
No one has yet explained the reasoning (vs the mechanics) of the
returned value of the following.

L = range(10)
L[3::-1]

So far every attempt to explain it has either quoted the documents which
don't address that particular case, or assumed I'm misunderstandin g
something, or implied it isn't neccisary to do.

It's quite easy to get me to change my mind on something, just show me a
convincing explanation and I will. :)

[...]
You said it quite well yourself:

It's easy to think you understand something when you don't. I spend
quite a while figuring this out, And am sure about how it works. If
there are issues with this, then it will probably be in how I describe
it, what words or terminology is used, and weather or not it's the
proper approach.

There are actually two distinct proposals here, not just one.

1. Fixing negative strides so they return the slice indexed as
you say they should.

2. Using base one negative index's and picking item from the
right of negative index's instead of the right.
They don't both need to implemented, Item 1 could be fixed in 2.5.

Given that Python has a 1's-complement operator already I don;t see why
you can't just leave Python alone and use it, since it seems to keep you
happy. If "fixing" item 1 in 2.5 would induce major code breakage,
there's less than a snowball's chance in hell it will happen.

I doubt fixing item (1) would induce major code breakage. As near as I
can tell, it's rarely, (nearly never), used in forms other than L[::-1].

Item (2) however would require a lot of small changes in index's.
Mostly changing.. L[:-1] to L[:~1] or to L[:-2]. So no, I don't expect
one's based indexing to be added any time soon. It could be useful as a
function or object in it's own.

"Professor Einstein, could you tell our readers how general relativity
works?"
Actually I can, but it would be off topic for this news group.

Cheers,
Ron

regards
Steve

[Ron Adam]

Bengt Richter wrote:

On Mon, 5 Sep 2005 18:09:51 +0200, "Fredrik Lundh" <fr*****@python ware.com> wrote:
OTOH, ISTM we must be careful not to label an alternate alpha-version
"way to model the real world" as a "misunderstandi ng" just because it is alpha,
and bugs are apparent ;-)
Thanks! I couldn't have said this myself. :-)

BTW, it just occurred to me that alternate slice member semantics could be RELATIVE,
EACH depending on sign. I.e.,

x[start:stop:step]

could mean start with x[start] as now as a starting point reference point element,
then let stop be a relative range length in either direction from the
starting point, and step absolute value indicating step size, and its sign
indicating insertion side for zero length slices. In effect, stop would
be a count for the slice range in either direction starting with the starting
element

s = 'abcde'
s[2:2] => 'cd'
s[2:-2] => 'cb'
s[-2:-3] => 'dcb'
s[-2:0] => ''
s[2:0] => ''
s[-2:-3:2] => 'db'
r = range(10)
r[5:0] = 'a'
r => [0, 1, 2, 3, 4, 5, 'a', 6, 7, 8, 9]
r[-2:0:-1] = 'b'
r => [0, 1, 2, 3, 4, 5, 'a', 6, 7, 'b', 8, 9]
r[-2:0] = ['c', 'd']
r => [0, 1, 2, 3, 4, 5, 'a', 6, 7, 'b', 8, c, d, 9]
Interesting, so it would be...

slice( position, count, step )

Items are addressed directly so there's no 'gap's to account for.

note that slice assignment would work by iterating through the right hand
sequence, which could do interesting things:

r = range(6)
r[3:-2] = 'ab'
r => [0, 1, 'b', 'a', 4, 5]
but two reverse relative slices match order, so
r = range(10)
r[5:-3] = range(10)[-1:-3] # rh seq is 9, 8
r => [0, 1, 8, 9, 4, 5]

I think this is kind of interesting, and I probably wouldn't have thought of
it if I had not been for Ron's enthusiasm for his "misunderstandi ng" ;-)

In a way, "misunderstandi ngs" are the mutations of open source evolution of ideas,
most of which die, but some of which mutate again and may occasionally survive.
So we need them ;-)

Here's another possible "misunderstandi ng".

(or alternative alpha-version) ;-)
Have you thought of using a slice object as a buffer pointer for
indirect operations?

r = range(100)
d = [10:20]
r.range_add(d,5 ) # Adds 5 to items in range d

d = d[5:] -> [15:20] # relative range modification.
# slice of a slice object

r.range_sub(d,3 ) # subtract 3 from items in range d

Or more flexible ...
r.range_modify( d, add(), 5)

Using your suggestion that would be...

r = range(100)
d = [10:10]
r.range_add(d,5 )

d = d[5:] -> [15:5] # interesting symmetry.
r.range_sub(d,3 )

Of course adding and subtracting slice objects could also be possible.

d = [10:20]
e = [15:25]
f = d + e -> [10:25]

or ...

d = [10:10]
e = [15:10]
f = d + e -> [10:15]
Cheers,
Ron

Regards,
Bengt Richter

[Bengt Richter]

On Mon, 5 Sep 2005 22:56:29 +0200, "Fredrik Lundh" <fr*****@python ware.com> wrote:

Bengt Richter wrote:

as long as you have people that insist that their original misunderstandin gs
are the only correct way to model the real world, and that all observed
inconsistenc ies in their models are caused by bugs in the real world, you'll
end up with threads like this.

OTOH, ISTM we must be careful not to label an alternate alpha-version
"way to model the real world" as a "misunderstandi ng" just because it is alpha,
and bugs are apparent ;-)

in my post, "the real world" is the existing Python implementation. what
theoretical construct are you discussing?

I guess I was talking about a "real world" of abstractions (if that is not an oxymoron ;-)
re sequences and slice access methods, of which the existing python implementation
provides a concrete example of one "model" and Ron's efforts provide some attempts at
an alternative "model". Of course, as far as the concrete "real world" goes, python does what
it does, and a model of _that_ that doesn't fit is a real misunderstandin g ;-)

BTW, how did relative slice semantics strike you? They could live along side normal ones
by prefixing the slice brackets with a '.', like r.[3:-2] for 2 (abs(-2)) elements
leftwards(-2<0) starting with r[3]. The logic for None defaults and non-1 steps and
guaranteeing legal ranges is messy, but otherwise UIAM

r.[start:count] == r[start:start+cou nt:-(count<0) or 1]

allowing signed start and count values. IMO r[start] is easy for newbies
to understand as a starting element, whether from end or beginning, and
an absolute value of count is easy, with the sign saying which direction
to scan from the start element, irrespective of how the latter was specified.

Regards,
Bengt Richter

[Terry Reedy]

> Ron Adam wrote:

However, I would like the inverse selection of negative strides to be
fixed if possible. If you could explain the current reason why it does
not return the reverse order of the selected range.

To repeat, the current reason is compatibility with the original design for
NumPy. Perhaps there is some explanation for that in sliceobject.c (or
whatever the file is called), the CVS checkin messages, or the newsgroup
archives before the first checkin (in 1996, I believe).

Terry J. Reedy

[Steve Holden]

Ron Adam wrote:

Steve Holden wrote:

It's a common misconception that all ideas should be explainable simply.
This is not necessarily the case, of course. When a subject is difficult
then all sorts of people bring their specific misconceptions to the
topic, and suggest that if only a few changes were made the whole thing
would be easier to understand.

What misconception do you think I have?

This was not an ad hominem attack but a commentary on many attempts to
"improve" the language.

Unfortunately , while that might make the topic in question easier to
understand for some it would make it difficult, and even
counter-intuitive, for others.

True, and that's why asking and getting opinions on a subject is a good
idea.

As many have said before me, there's a reason why slicing and
indexing are the way they are. The interfaces were designed by people
with long years of programming and teaching experience.

No one has yet explained the reasoning (vs the mechanics) of the
returned value of the following.

L = range(10)
L[3::-1]

So far every attempt to explain it has either quoted the documents which
don't address that particular case, or assumed I'm misunderstandin g
something, or implied it isn't neccisary to do.

It's quite easy to get me to change my mind on something, just show me a
convincing explanation and I will. :)

L[3::-1] [3, 2, 1, 0] L[3::1] [3, 4, 5, 6, 7, 8, 9]

I don;t see the problem here. The start specifies which element is the
first in the slice, the stop is the default (end of the sequence) and
the stride is "successive elements to the left" when it's -1 and
"successive elements to the right" when it's 1.

Or perhaps you can tell me what I've missed?

[...]
You said it quite well yourself:
It's easy to think you understand something when you don't. I spend
quite a while figuring this out, And am sure about how it works. If
there are issues with this, then it will probably be in how I describe
it, what words or terminology is used, and weather or not it's the
proper approach.

There are actually two distinct proposals here, not just one.

1. Fixing negative strides so they return the slice indexed as
you say they should.

2. Using base one negative index's and picking item from the
right of negative index's instead of the right.
They don't both need to implemented, Item 1 could be fixed in 2.5.

Given that Python has a 1's-complement operator already I don;t see why
you can't just leave Python alone and use it, since it seems to keep you
happy. If "fixing" item 1 in 2.5 would induce major code breakage,
there's less than a snowball's chance in hell it will happen.

I doubt fixing item (1) would induce major code breakage. As near as I
can tell, it's rarely, (nearly never), used in forms other than L[::-1].

Well, I don't see the problem yet, so I don't actually think that needs
"fixing".
Item (2) however would require a lot of small changes in index's.
Mostly changing.. L[:-1] to L[:~1] or to L[:-2]. So no, I don't expect
one's based indexing to be added any time soon. It could be useful as a
function or object in it's own.
My point was that you can make those changes in your own code, leaving
others to accept the situation as it is.

"Professor Einstein, could you tell our readers how general relativity
works?"

Actually I can, but it would be off topic for this news group.

Right, I wasn't trying to suggest that you didn't know what you were
talking about - or even that you didn't understand general relativity
(on which my grasp could be said to be tenuous) - merely that some
things are inherently difficult, and no matter how you twist the
implementations about, the difficulties will remain.

regards
Steve
--
Steve Holden [phone] [phone]
Holden Web LLC http://www.holdenweb.com/

[Bengt Richter]

On 05 Sep 2005 12:58:00 -0700, Paul Rubin <http://ph****@NOSPAM.i nvalid> wrote:

Steve Holden <st***@holdenwe b.com> writes:

Given that Python has a 1's-complement operator already I don;t see
why you can't just leave Python alone and use it,

What's the meaning of the 1's complement operator (for example, what
is ~1), when ints and longs are the same?

assert ~x == -1-x # or -1^x

The only problem is seeing the result printed, since people insist
that hex(a) will be '-'[:a<0]+hex(abs(a))

which brings up base-complement representation for signed numbers,
where the first digit is always 0 or base-1 to indicate positive and negative:
(BTW, I found a bug when I dug this up from my disk, so a previous post with this
might have that bug (bad leading digit check wasn't sign-sensitive))

def basecompl(x, B=10, digits='0123456 789abcdefghijkl mnopqrstuvwxyz' ): ... if not (2 <= B <= len(digits)): raise ValueError('bad base = %r'%B)
... if not x: return digits[0]
... s = []
... while x and x != -1:
... x, r = divmod(x, B)
... s.append(digits[r])
... if not s or s[-1] != (digits[0], digits[B-1])[x<0]:
... s.append(digits[x<0 and B-1 or 0])
... return ''.join(s[::-1])
... def bcdecode(s, B=10, digits='0123456 789abcdefghijkl mnopqrstuvwxyz' ): ... if s == digits[0]: return 0
... acc = s[0].lower() == digits[B-1] and -B**len(s) or 0
... for i, c in enumerate(s[::-1]):
... acc += digits.index(c) *B**i
... return acc
... bc = basecompl # easier to type ;-) bc(~3L, 2) '100' bc(-1-3L, 2) '100' bc(-1^3L, 2) '100' bc(~3L, 8) '74' bc(-1-3L, 8) '74' bc(-1^3L, 8) '74' bc(~3L) '96' bc(-1-3L) '96' bc(-1^3L) '96' bc(bcdecode(bc( ~3L))) '96' bc(bcdecode(bc( ~3L, 2),2),2) '100' bc(~3L, 16) 'fc' bc(-1-3L, 16) 'fc' bc(-1^3L, 16) 'fc' bc(3L)

'03'

Regards,
Bengt Richter

[Bengt Richter]

On Mon, 05 Sep 2005 17:10:05 -0400, Steve Holden <st***@holdenwe b.com> wrote:

Paul Rubin wrote:

Steve Holden <st***@holdenwe b.com> writes:

Given that Python has a 1's-complement operator already I don;t see
why you can't just leave Python alone and use it,

What's the meaning of the 1's complement operator (for example, what
is ~1), when ints and longs are the same?

Python 2.2.1 (#1, Aug 25 2004, 16:56:05)
[GCC 2.95.4 20011002 (Debian prerelease)] on linux2
Type "help", "copyright" , "credits" or "license" for more information.

~1L-2L ~1-2 import sys
sys.maxint*48589934588L ~(sys.maxint*4)-8589934589L
$ python
Python 2.4.1 (#1, May 27 2005, 18:02:40)
[GCC 3.3.3 (cygwin special)] on cygwin
Type "help", "copyright" , "credits" or "license" for more information. >>> ~1L-2L >>> ~1-2 >>> sys.maxint*48589934588L >>> ~(sys.maxint*4)-8589934589L >>>
What's going to change when ints and longs are finally integrated?

I suspect that Paul may be worrying that bit operations on longs will be
bit operations on signs and positive magnitudes rather than signed numbers
of arbitrary width. This may be promoted by the fact the so far we have no
builting format for showing the bits of negative numbers the way hex used to do.

I scratched the itch this way:

from ut.basecompl import basecompl as bc
import sys
bc(sys.maxint*4 , 16) '01fffffffc' bc(~sys.maxint* 4, 16) 'fe00000000'
oops, precendence ... bc(~(sys.maxint *4), 16) 'fe00000003'

vs. the useless hex(~(sys.maxin t*4)) '-0x1FFFFFFFDL'

(at least for looking at bit operation results ;-)

BTW, note base complementing, with base-1 or 0 as sign:
bc(~(sys.maxint *4), 8) '700000000003' bc( (sys.maxint*4), 8) '077777777774' bc(~(sys.maxint *4), 10) '91410065411' bc( (sys.maxint*4), 10) '08589934588' bc(~(sys.maxint *4), 2) '10000000000000 000000000000000 00011' bc( (sys.maxint*4), 2)

'01111111111111 111111111111111 11100'

Regards,
Bengt Richter

[Patrick Maupin]

> No one has yet explained the reasoning (vs the mechanics) of the

returned value of the following.

L = range(10)
L[3::-1]

So far every attempt to explain it has either quoted the documents which
don't address that particular case, or assumed I'm misunderstandin g
something, or implied it isn't neccisary to do.

It's quite easy to get me to change my mind on something, just show me a
convincing explanation and I will. :)

Once I saw this, I was surprised, because slices currently work exactly
like I would and do expect on this example, so I now have to admit that
I didn't read your original post fully and carefully. I have gone back
to look to figure out what you don't like and what you want, and I am
very surprised.

To me, your way reeks of black magic -- if there is a sign on the
stride, then strange and wondrous transformations happen. I think it
is conceptually (and probably programatically ) much simpler the way it
is.

In any case, you asked for a rationale. I'll give you mine:

L = range(10)
L[3:len(L):-1] == [L[i] for i in range(3,len(L),-1)] True

If you manage somehow to hange that 'True' to a 'False', I'll
personally be extremely unhappy.

Regards,
Pat

[Patrick Maupin]

I previously wrote (in response to a query from Ron Adam):

In any case, you asked for a rationale. I'll give you mine:

L = range(10)
L[3:len(L):-1] == [L[i] for i in range(3,len(L),-1)] True
After eating supper, I just realized that I could probably make my
point a bit clearer with a slightly longer example:
L = range(10)
for stride in [-3, -2, -1, 1, 2, 3]:

.... for start in range(len(L)):
.... for end in range(len(L)):
.... P = L[start:end:strid e]
.... Q = [L[i] for i in range(start, end, stride)]
.... assert P == Q

This should never fail with an assertion error. You will note that it
shows that, for non-negative start and end values, slicing behavior is
_exactly_ like extended range behavior. I cannot imagine that the
behavior of range() could be made any more intuitive than it already
is. I personally feel that your proposed change makes slice() less
intuitive on its own, but even if I did not feel that way, your way
would have to be SIGNIFICANTLY better than the current way to make it
worthwhile to make slice() behavior differ from that of range().

In my initial skimming of your post, I originally thought you were
referring to negative start and end values. Negative start and end
values will sometimes cause issues, but the utility of their current
implementation far outweighs the few corner cases which (as I mentioned
in an earlier post) sometimes need some special case logic to deal
with.

Regards,
Pat

[Ron Adam]

Terry Reedy wrote:

Ron Adam wrote:

However, I would like the inverse selection of negative strides to be
fixed if possible. If you could explain the current reason why it does
not return the reverse order of the selected range.

To repeat, the current reason is compatibility with the original design for
NumPy. Perhaps there is some explanation for that in sliceobject.c (or
whatever the file is called), the CVS checkin messages, or the newsgroup
archives before the first checkin (in 1996, I believe).

Terry J. Reedy

Thanks, I'll check the cvs, so far I havn't been able to find any
references to it.