PEP 322: Reverse Iteration (REVISED, please comment)

[Raymond Hettinger]

Based on your extensive feedback, PEP 322 has been completely revised.
The response was strongly positive, but almost everyone preferred
having a function instead of multiple object methods. The updated
proposal is at:

www.python.org/peps/pep-0322.html

In a nutshell, it proposes a builtin function that greatly simplifies reverse
iteration. The core concept is that clarity comes from specifying a
sequence in a forward direction and then saying, "inreverse()":

for elem in inreverse(seqn):
. . .

Unlike seqn[::-1], this produces a fast iterator instead of a full reversed
copy.

Discussions with Guido made it clear that inreverse() will not be extended
to cover all iterables. The proposal is about simplicity, expression, and
performance. As such, it would be counter-productive to take in a general
iterable, run it to completion, save the data in memory, and then iterate
over the data in reverse.


Raymond Hettinger

 

[Werner Schiendl]

Discussions with Guido made it clear that inreverse() will not be extended
to cover all iterables. The proposal is about simplicity, expression, and
performance. As such, it would be counter-productive to take in a general
iterable, run it to completion, save the data in memory, and then iterate
over the data in reverse.

Which of course can easily be done explicitely:

# Make some iterable unsuitable for inreverse
a = iter("Hello")

# Create a list that can be in'reversed explicitely
for i in inreverse(list(a)):
print i


As always, explicit is better than implicit ;-)

Maybe something alike should go into the docs...


- Werner

 

[Werner Schiendl]

Hi,

was it considered to name the function just "reverse"?

This would read very naturally to me:

for elem in reverse(seq):
print elem


Also if you use it in function calls it looks good to me:

x = dostuff(reverse(seq), a, b)


Another possibility would be to have a static method for iter:

for elem in iter.reversed(sed):
print elem

(in that case I'd use an attribute rather than a verb, because
the generated iter(ator) will be reverse_d_).

The static method approach would clearly document that the
result is an iterator (which none of the other names proposed
really does IMHO)


In general, I'm +1 on the PEP


regards

Werner

 

[Paul Moore]

In a nutshell, it proposes a builtin function that greatly simplifies reverse
iteration. The core concept is that clarity comes from specifying a
sequence in a forward direction and then saying, "inreverse()":

for elem in inreverse(seqn):
. . .

I've got to say, I really don't like the name. Particularly, the
repeated "in" in "in inreverse..." strikes me as ugly.

Discussions with Guido made it clear that inreverse() will not be extended
to cover all iterables. The proposal is about simplicity, expression, and
performance. As such, it would be counter-productive to take in a general
iterable, run it to completion, save the data in memory, and then iterate
over the data in reverse.

I like the proposal, it's simple and expressive. But please, change
the name! I assume there's a good reason why the obvious "reverse()"
wasn't chosen. Of the alternatives in the PEP, backwards() doesn't
seem to read nicely (but it's better than inreverse!!!), and ireverse
is OK, but makes me think that it should be in itertools (or all the
itertools should be builtin). Some other possibilities:

rev(seq) - probably too abbreviated
reversed(seq) - adjective rather than verb, but reads well

As usual, the semantics is perfectly acceptable, but we'll have a nice
long argument over the name

Paul.

 

[Alex Martelli]

Werner Schiendl wrote:
...

Another possibility would be to have a static method for iter:

for elem in iter.reversed(sed):
print elem

(in that case I'd use an attribute rather than a verb, because
the generated iter(ator) will be reverse_d_).

The static method approach would clearly document that the
result is an iterator (which none of the other names proposed
really does IMHO)

I like this one! Another advantage is, one fewer built-in.

Problem is, iter is currently a built-in function, not a type...


Alex

 

[John Roth]

+1

Based on your extensive feedback, PEP 322 has been completely revised.
The response was strongly positive, but almost everyone preferred
having a function instead of multiple object methods. The updated
proposal is at:

www.python.org/peps/pep-0322.html

In a nutshell, it proposes a builtin function that greatly simplifies reverse
iteration. The core concept is that clarity comes from specifying a
sequence in a forward direction and then saying, "inreverse()":

for elem in inreverse(seqn):
. . .

Unlike seqn[::-1], this produces a fast iterator instead of a full reversed
copy.

Discussions with Guido made it clear that inreverse() will not be extended
to cover all iterables. The proposal is about simplicity, expression, and
performance. As such, it would be counter-productive to take in a general
iterable, run it to completion, save the data in memory, and then iterate
over the data in reverse.

It's certainly clear enough, and I like it in general.

I'd appreciate a bit of discussion about why reverse() was rejected as
the name, though.

John Roth

 

[Dave Benjamin]

for elem in inreverse(seqn):
. . .

Is there an echo in inhere? +1 +1otherwise... =)

 

[Patrick Maupin]

Based on your extensive feedback, PEP 322 has been completely revised.

Personally, for some tasks I have used reverse iteration quite a bit.

My use case has _always_ been that I want to modify a list (e.g.
adding or deleting items) in situ. In all other cases which I can
recall, I have quite happily iterated in the forward direction.

(Maybe this is because I am not afraid to call list.reverse(), and
insertion/deletion is the only use case where this doesn't really help.)

This means that the implementation restrictions described in the PEP are
fine with me (because a list has the requisite methods).

However, this also means that I am most interested in how the enumerate()
interface will work with this (because the current list index must be
known in order to properly add or delete items). enumerate() was
mentioned in the PEP but not discussed in any real depth.

My personal preference (since this is the only use case which I have
ever encountered) would be to enhance enumerate in a reasonable fashion,
and not necessarily even have (or at least care about) the reverse/ireverse/
whatever name underneath enumerate().

I will happily accept whatever syntax comes along (unless the enumerate
counts 0,1,2,3... while the index of the adjacent list object is decremented
[-1],[-2],[-3]...

BUT, for sheer usability I think it would be wonderful if enumerate()
took an optional second argument to let it know you want to go backward.
The most general syntax for this second argument would naturally be
a slice:

for idx,obj in enumerate(mylist,-1:-1:-1):
do whatever

but if people think this is too ugly something simpler could be
substituted (but think about the useful possibilities of a slice
argument here before you complain too hard about the ugliness...)

Some may argue that this restricts enumerate() to certain kinds of
iterators when using the slice (and thus adds a lot of special casing),
but it may be that, realistically, if ireverse() is going to have this
special casing, and enumerate() is going to work with ireverse(), you
already have the same problem (unless the user is expected to work
with the enumerate counting backwards from the actual list index).
I cannot say this for sure, however, because I did not see (or perhaps
read closely enough) the part of the PEP which discussed enumerate.

Regards,
Pat

 

[Werner Schiendl]

Werner Schiendl wrote:
...

I like this one! Another advantage is, one fewer built-in.

Problem is, iter is currently a built-in function, not a type...

An additional advantage that came to my mind is that it would fit
Guido's preference about how to (possible) implement inline sort.

having

L = list.sorted(seq)

i = iter.reversed(seq)

seems very consistent to me.


best regards

Werner

 

[Raymond Hettinger]

The static method approach would clearly document that the

result is an iterator (which none of the other names proposed
really does IMHO)

Better name are welcome!

Moving it somewhere else is not open. It is proposed as a builtin for a
reason -- it is a core looping tool like zip() or enumerate() and it is meant
to simplify rather than complicate code.

Static methods, class methods, and weird descriptors be darned, this is
not an exercise in how weirdly it can be implemented just to avoid
having a builtin.

Would everything be somehow better if Alex's wonderful sum() had
been implemented as a int.sum() classmethod or was tucked way in
another module? Of course not! Likewise, would zip() or enumerate()
be successful solutions to lock-step iteration and the loop-counter
problems if they were iter.zip() and iter.enumerate()? No, of course not.
Let's put an end to this silliness right now. The idea is offered as a
builtin or not at all; otherwise, the existing [::-1] starts to look better.

In general, I'm +1 on the PEP

Thanks! I certain it will make code more readable and reviewable.

The challenge with a PEP this simple is that experts feel this
overpowering urge to apply all their know-how and transform
in to something other than a clean, fast, simple solution.


Raymond Hettinger

 

[Terry Reedy]

Since iter() constructs and returns a type 'iterator' object, I
expected that it might be a type object, just like int(), etc. If it
were turned into one, like int(), etc, have been, then

L = list.sorted(seq)
i = iter.reversed(seq)
seems very consistent to me.

would be exactly parallel and hence very consistent.

Unless there is a good reason to not make iter a type object, then
making it so could be part of the suggested implementation of the PEP.

Terry J. Reedy

 

[Raymond Hettinger]

Since iter() constructs and returns a type 'iterator' object, I

expected that it might be a type object, just like int(), etc. If it
were turned into one, like int(), etc, have been, then . . .
Unless there is a good reason to not make iter a type object, then
making it so could be part of the suggested implementation of the PEP.

iter() is a factory function that can return all kinds of things:

from random import random
iters = iter('str'), iter(['list']), iter(dict(a=1)), iter(random, None)
map(type, iters)

[<type 'iterator'>, <type 'listiterator'>, <type 'dictionary-iterator'>, <type
'callable-iterator'>]



Let's see if we can get back to the merits of the pep.
Looking at your own code, can you verify that ireverse()
is an improvement over what you have now.


Raymond Hettinger

 

[Werner Schiendl]

Better name are welcome!

Moving it somewhere else is not open. It is proposed as a builtin for a
reason -- it is a core looping tool like zip() or enumerate() and it is meant
to simplify rather than complicate code.

Well, that of course limits the choice

Let's see what's available:

inreverse --

seems a little clumsy when used in a "for item in inreverse(seq):",
which is probably the place where it's used most often.

The term itself seems reasonable to me.

ireverse --

IMHO that would suggest it belonged into itertools - which it
according to your explanatation does NOT.

So I'd rather 'reserve' that term if one day something there
is needed (or end up with iireverse ;-)

To my non-native-english eyes it's also a bit ugly.

And concerning simplicity, how to explain a newby the "i"
and why it's with "reverse" but not with "enumerate".

reverse --

According to the PEP this is not for discussion, although I'm
with John Roth in that I think this were worth some more
discussion.

I do not use Python too much (yet as often as possible, but
"job work" is done with something else.
Still I cannot imagine why anyone should confuse a method of
a list object (that does return None) with a builtin function
that returns "something" to walk through an arbitrary sequence
in reverse.

This one fits IMHO also best to the most-direct relatives you
mention in your post (zip, enumerate) in that it is a verb
without any prefix.

backwards --

I cannot remember having seem that term in any library or
programming language, it feels strange to me.

But it's still correct, a verb, fits the style IMHO.
Like it more than ireverse.


So my order from most-prefered to least-prefered is:

reverse

inreverse

backwards

ireverse

The challenge with a PEP this simple is that experts feel this
overpowering urge to apply all their know-how and transform
in to something other than a clean, fast, simple solution.

I'd not actually claim myself a Python expert ;-)


best regards

Werner

 

[Peter Otten]

Since iter() constructs and returns a type 'iterator' object, I
expected that it might be a type object, just like int(), etc. If it
were turned into one, like int(), etc, have been, then . . .
Unless there is a good reason to not make iter a type object, then
making it so could be part of the suggested implementation of the PEP.

iter() is a factory function that can return all kinds of things:

from random import random
iters = iter('str'), iter(['list']), iter(dict(a=1)), iter(random,
None) map(type, iters)

[<type 'iterator'>, <type 'listiterator'>, <type 'dictionary-iterator'>,
[<type
'callable-iterator'>]

So why couldn't all these iterators inherit from iter just as unicode and
str do from basestring?

Let's see if we can get back to the merits of the pep.

I respect that you want to keep this discussion focused, and itertools is my
favourite new package - but sometimes il faut reculer pour mieux sauter

Looking at your own code, can you verify that ireverse()
is an improvement over what you have now.

While I'm zipping and enumerating all the time, reversing is rare, so I'm
not desperately awaiting this builtin.
The most common usecase seems iteration over a sequence that is mutated in
the process:

class mutate(object):
def __init__(self, alist):
self.index = -1
self.alist = alist
def next(self):
self.index += 1
try:
self.alist[self.index]
except IndexError:
raise StopIteration
return self
def value(self):
return self.alist[self.index]
def __iter__(self):
return self
def delete(self):
del self.alist[self.index]
self.index -= 1

sample = range(10)
for item in mutate(sample):
if item.value() in [3,5,7]:
item.delete()
print sample

I'm sure that the above approach can be improved (in particular, it must not
rely on an index, i. e. random access) as I'm sure that it makes the
coder's intention clearer than the "reverse to enable deletion" idiom.

Peter

 

[Alex Martelli]

Raymond Hettinger wrote: ,,,

Right, and thus it must stay. Oh well.

So why couldn't all these iterators inherit from iter just as unicode and
str do from basestring?

They might, but then calling iter() should complain that iter is an
abstract baseclass, not instantiable, just like calling basestring()
does. Having an abstract baseclass that DOES return new objects when
called would be very perverse indeed. So, making iter a type is not
really a sensible option, alas.


Alex

 

[Alex Martelli]

Better name are welcome!

Moving it somewhere else is not open. It is proposed as a builtin for a
reason -- it is a core looping tool like zip() or enumerate() and it is

I don't think it has anywhere like the frequency of use of either.

Static methods, class methods, and weird descriptors be darned, this is
not an exercise in how weirdly it can be implemented just to avoid
having a builtin.

I just don't think it's worth making a built-in.

Would everything be somehow better if Alex's wonderful sum() had
been implemented as a int.sum() classmethod or was tucked way in
another module?

int.sum would be a disaster either way: if it was forced to return
an int it would reduce use cases substantially; if it wasn't it
would be just weird.

math.sum would be arguably equivalent to sum as a built-in -- a
tad less immediately accessible, but perhaps superior in that it
immediately suggests it's about numbers only, so we'd avoid the
icky performance trap you now get with sum(manylists, []) {which
makes sum only 2/3 wonderful at best -- fine with numbers ONLY}.

Of course not! Likewise, would zip() or enumerate()
be successful solutions to lock-step iteration and the loop-counter
problems if they were iter.zip() and iter.enumerate()? No, of course not.

zip is currently an INFERIOR solution for lock-step iteration: your
itertools.izip is much better for that. Unfortunately zip IS
constrained to return a list BUT that fact is not reflected in it
being a classmethod list.zipped (we didn't have classmethods when
zip was introduced, so that wasn't an option). If it had been made
one, then by now we might have a built-in version of izip, sigh.

Your enumerate is excellent, and just as frequently used as izip.
I prefer it as a builtin -- though I wouldn't be heartbroken if it
had been in itertools, but it's better in the builtins _because_
it's so frequently used.

Unfortunately we have too many and inappropriate builtins and they're
not going to go away until 3.0 (years away). This raises the bar for
other not-obviously-indispensable built-ins more than it would be
sensible to do in a hypothetical "greenfield design".

Let's put an end to this silliness right now. The idea is offered as a
builtin or not at all; otherwise, the existing [::-1] starts to look
better.

You're clearly overwrought, so I won't "see" that "silliness" and get
offended by it. If the choice was only to have the reverser (by
whatever name) as a built-in or not at all, I'd be -0 on the reverser --
slightly against, though not enough to bother opposing it. If it
could be sited somewhere appropriate (ok, not as iter.reversed if
that's technically unfeasible -- i did say "appropriate" I'd be +1.

The challenge with a PEP this simple is that experts feel this
overpowering urge to apply all their know-how and transform
in to something other than a clean, fast, simple solution.

The crux of our disagreement, namecalling apart, might be highlighted
by your assertion in another short and emotional post:

This is supposed to be something you can teach in the first half-hour

I can't imagine "teaching this in the first half-hour" of any Python
course I teach. There are FAR too many other functions, including
non-builtin ones such as sys.exit, and some in itertools too, that are
more important than this, in my own assessment.

So we disagree about frequence of usage, and consequently "warrantedness"
as a built-in -- big deal. I honestly don't understand how this purely
technical disagreement can explain these intense emotions.

_I_ am supposed to be the Latin, Mediterranean, hot-blooded enthusiast,
after all, and on average I think I cover the role adequately.

Oh well, with the incredible amount of good things you've done for Python
development, I guess you're surely entitled to blow your top occasionally,
if that's your preference. Also, presumably, to get your pet built-in
into the language, as you've slipped it past Guido. As for name, I
therefore second the neatest suggestion I've seen: since it IS a reversed
iter, and we can't directly call it that, then:

reti

Hey, it IS short, so if it's gonna be so heavily used, good thing, no?-)


Alex

 

[Bengt Richter]

Based on your extensive feedback, PEP 322 has been completely revised.
The response was strongly positive, but almost everyone preferred
having a function instead of multiple object methods. The updated
proposal is at:

www.python.org/peps/pep-0322.html

In a nutshell, it proposes a builtin function that greatly simplifies reverse
iteration. The core concept is that clarity comes from specifying a
sequence in a forward direction and then saying, "inreverse()":

for elem in inreverse(seqn):
. . .

Unlike seqn[::-1], this produces a fast iterator instead of a full reversed
copy.

I'm thinking that a concise way to make a fast iterator from any slice expression
could subsume the inreverse functionality. IOW, a generator slice corresponding
in spirit to generator expressions. E.g., for the inreverse use,

for elem in seqn'[::-1]:
. . .

(note the apostrophe in front of the slice notation)

Of course, unlike 'inreverse', you wouldn't be limited to going backwards,

for oddelem in seqn'[1::2]:
. . .

Ok, take a deep breath, here comes some more ;-)

How about generator expressions/slices being able to be evaluated in parallel in a 'for' loop
(with '=' instead of 'in' to signify that we're taking elements from each of the
sequences in a tuple and making an intermediate data tuple to unpack for the assignment,
not unpacking the rhs tuple of sequences)? E.g.,

for oddelem, evenelem = seqn'[1::2], seqn'[0::2]:
. . .

This seems like a nice generalization that could use any sequences, not just generator slices.
I.e., like tuple assignment, but the 'for' makes the rhs get treated like the above was short for

for oddelem, evenelem in itertools.izip(seqn'[1::2], seqn'[0::2]):

Note that like tuple assignment, you could unpack as many sequences in parallel as you liked.
(In fact, the single-target case would work too, just by changing 'in' to '=' ;-)

If you like generator slices, it might be nice to have bare generator slices too, implicitly
producing a sequence of integers that might make sense in relation to the same notation used
on a sequence. E.g.,

'[:] <=> (i for i in xrange(0,sys.maxint,1))
'[start:stop:step] <=> (i for i in xrange(start,stop,step))
'[::-1] <=> (i for i in xrange(-1, -sys.maxint-1, -1))

etc. Thus plain enumerate could be respelled (taking seq via a full generator slice):

for i, elem = '[:], seq'[:]:
. . .

and the reversed order, enumerating with indices -1, -2, etc. would look like

for i, elem = '[::-1], seq'[::-1]:
. . .

Too much at once? ;-)

Discussions with Guido made it clear that inreverse() will not be extended
to cover all iterables. The proposal is about simplicity, expression, and
performance. As such, it would be counter-productive to take in a general
iterable, run it to completion, save the data in memory, and then iterate
over the data in reverse.

The same could apply to seq'[::-1]
I assume seq would be queried for __len__ and __getitem__ when about to create
the generator slice.

Regards,
Bengt Richter

 

[Shu-Hsien Sheu]

Hi,

After 2 months of learning in Python, the most difficult part is the
object part. Though I can get most of my works done using very simple
classes, I don't think I get the essence of it. Right now I am thinking
of wrirting a class like:

class hittable(object):
def __init__(self):
self.table = [{}, {}, {}, {}]
def build(<some parameter>): #some modification to the dictionary
<some codes>
def search(self, aa):
if aa == 0:
<do modification "build" to self.table[0]>
if aa == 1:
<do modification "build" to self.table[1]>

I have trouble implementing the above in real code. I can only get
something by making a seperate function outside the class:
dd.setdefault(i, {})
return dd def __init__(self):
self.table = [{}, {}, {}, {}] #0eptides, 1: nucleotides,
2:metals, 3thers
def search(self, i):
self.table = build(self.table, i) [{}, {}, {}, {3: {}}]

And couldn't find a way to integrate the "build" function into a class
method:
def __init__(self):
self.table = [{}, {}, {}, {}]
def build(self, i):
self.table.setdefault(i, {})
def search(self, i):
self.table = self.build(i)[{}, {}, {}, None]

I think I can imagine the above code won't work, though couldn't find a
solution to it.

What am I missing here?

Thanks!

-shushien

 

[Alex Martelli]

Shu-Hsien Sheu wrote:
...

def build(self, i):
self.table.setdefault(i, {})

this method has no explicit 'return', so it returns None

def search(self, i):
self.table = self.build(i)

So, you're assigning None to self.table.

[{}, {}, {}, None]

I think I can imagine the above code won't work, though couldn't find a
solution to it.

What am I missing here?

Just forget that wanton assignment in method search! Why would you
want to assign anything new to self.table, when self.build(i) has
just modified self.table appropriately?! I.e., change search to:

def search(self, i):
self.build(i)

this doesn't have anything special to do with classes -- rather,
with the care and feeding of dictionaries, I'd say.


Alex

 

[Michele Simionato]

math.sum would be arguably equivalent to sum as a built-in -- a
tad less immediately accessible, but perhaps superior in that it
immediately suggests it's about numbers only, so we'd avoid the
icky performance trap you now get with sum(manylists, []) {which
makes sum only 2/3 wonderful at best -- fine with numbers ONLY}.

Too late :-(

I see now that ``math.sum`` would have been a much better solution that a
new built-in. BTW, I remember this was discussed on the list, but
what was the argument against a polymorphic sum?

I mean, why it was not an option to implement a ``sum`` function
calling:

1. int.__add__,float.__add__ etc. if the arguments where numbers;
2. string.join if the arguments where lists;
3. something to avoid the performance trap of list.__add__;
4. __add__ for custom defined objects.

BTW, I think the answer should go in the FAQ, since everybody looking
at ``sum`` for the first time would imagine it is polymorphic. I remember
you said your first idea was to make it polymorphic, but this was
rejected due to performances reasons. But why making ``sum`` to
special case according to the arguments (it would be enough to
check the type of the first argument, then we would get an error
if we try to add incompatible types, just as in "".join(["a", 1]))
was a bad idea?

As you say, since ``sum`` is not polymorphic it makes more sense to put
it in the ``math`` module. Now it is too late, but it is unfortunate.


Michele