Pre-PEP: reverse iteration methods

[sebastien]

Re: Pre-PEP: reverse iteration methods

> PEP: 323[color=blue]
> Title: Add Reverse Iteration Methods
> Version: $Revision: 1.1 $[/color]

I don't need this often enough to want it as a method or a builtin
function.
But it would ne nice to have a function in the itertool module.

I would call it riter(), it should work on any sequence with len()
support or on any object wich define the __riter__ special method.

In practice, I mostly use reverse iteration when I most remove some
few objects on the sequence I'm itering to, so I have more neeed for a
renumerate() function:

for index, value in itertools.renum erate(sequence) :
if not value:
del sequence(index)

[Raymond Hettinger]

Re: Pre-PEP: reverse iteration methods

[Raymond Hettinger][color=blue][color=green]
> > for elem in seqn.iter_backw ards():
> > print elem[/color][/color]

[Stephen Horne][color=blue]
> That is a pretty long name. Can we use the convention from itertools
> where an 'i' prefix is sufficient to suggest an iterator, giving
> 'ibackwards' or 'ireverse' or similar.[/color]

That sounds reasonable to me. I'll add that alternative to the PEP.

If the discussion on enumerate() is any indication, then the naming
discussion will be much more lively than on the idea itself. Perhaps,
Alex will once again be able to suggest a musically perfect, beautiful
Italian name.

BTW, if you think iter_backwards is long, then take a look at some
of the method names in the sets module.

[color=blue]
> Second, I'm not quite ready to drop my property idea ;-)
>
> An advantage is that the object returned by the property can sensibly
> support more than just iteration - e.g. slicing (as touched on in the
> PEP284 thread). So for instance...
>[color=green][color=darkred]
> >>> x = range(10)
> >>> list(x.backward )[/color][/color]
> [9, 8, 7, 6, 5, 4, 3, 2, 1, 0][/color]

I'm not clear on the details of what you're proposing. What is
type(x.backward )?
Please show what a pure python version would look like
(taking UserList as an example).


[color=blue][color=green]
> >* Should file objects be included? Implementing reverse iteration may not
> > be easy though it would be useful on occasion.[/color]
>
> IMO no - doing this essentially needs the whole file to be read into
> memory, in which case you may as well read the whole file into a list
> and then iterate the list backwards.[/color]

Oh, it could be done using seeks and whatnot;
however, the code might be grotesque.


[color=blue][color=green]
> >* Should enumerate() be included? It would only provide reverse iteration
> > whenever the underlying sequence supported it.[/color]
>
> Why not...
>
> for i, j in enumerate (listname.iter_ backwards ()) :
>
> in other words, as enumerate can handle the already-reversed
> sequence/iteration, I don't see the point.[/color]

The point is that enumerate will starting numbering from zero
for the last item:
[color=blue][color=green][color=darkred]
>>> mystr = 'abc'
>>> list(enumerate( mystr.iter_back wards()))[/color][/color][/color]
[(0, 'c'), (1, 'b'), (2, 'a')]

If you want the indices to match their original position, then you
would need something like:
[color=blue][color=green][color=darkred]
>>> list(enumerate( mystr).iter_bac kwards())[/color][/color][/color]
[(2, 'c'), (1, 'b'), (0, 'a')]

The implementation would need to access both mystr.iterbackw ards()
and mystr.__len__() .

At first glance, this is a can of worms, a pandora's box,
a gordian knot, or some unnamed code smell unsuitable
for this mixed metaphor.



Raymond Hettinger

[John Roth]

Re: Pre-PEP: reverse iteration methods


"Stephen Horne" <$$$$$$$$$$$$$$ $$$@$$$$$$$$$$$ $$$$$$$$$.co.uk > wrote in
message news:f4b2nv8vs8 1v6egonckq7935j mh6a8gku6@4ax.c om...[color=blue]
> On Wed, 24 Sep 2003 00:30:31 GMT, "Raymond Hettinger"
> <vze4rx4y@veriz on.net> wrote:
>[color=green]
> >Proposal
> >========
> >[/color]
>[color=green]
> >* Should file objects be included? Implementing reverse iteration may[/color][/color]
not[color=blue][color=green]
> > be easy though it would be useful on occasion.[/color]
>
> IMO no - doing this essentially needs the whole file to be read into
> memory, in which case you may as well read the whole file into a list
> and then iterate the list backwards.[/color]

Actually, it doesn't. It does require that the file be read into the
buffers backwards, but from there it's simply a matter of doing
a reverse scan for the line ending characters. The difficulty is that
the entire algorithm would have to be done in C, without any
significant help from the standard library.

John Roth[color=blue]
>
>
>
> --
> Steve Horne
>
> steve at ninereeds dot fsnet dot co dot uk[/color]

[Hannu Kankaanpää]

Re: Pre-PEP: reverse iteration methods

Stephen Horne <$$$$$$$$$$$$$$ $$$@$$$$$$$$$$$ $$$$$$$$$.co.uk > wrote in message news:<f4b2nv8vs 81v6egonckq7935 jmh6a8gku6@4ax. com>...[color=blue][color=green]
> >* Should enumerate() be included? It would only provide reverse iteration
> > whenever the underlying sequence supported it.[/color]
>
> Why not...
>
> for i, j in enumerate (listname.iter_ backwards ()) :
>
> in other words, as enumerate can handle the already-reversed
> sequence/iteration, I don't see the point.[/color]

That's not the same:
[color=blue][color=green][color=darkred]
>>> list(enumerate([10,11,12]))[/color][/color][/color]
[(0, 10), (1, 11), (2, 12)][color=blue][color=green][color=darkred]
>>> list(enumerate([10,11,12].riter()))[/color][/color][/color]
[(0, 12), (1, 11), (2, 10)][color=blue][color=green][color=darkred]
>>> list(enumerate([10,11,12]).riter())[/color][/color][/color]
[(2, 12), (1, 11), (0, 10)]

Indices would also be reversed.

[Peter Otten]

Re: Pre-PEP: reverse iteration methods

Raymond Hettinger wrote:
[color=blue]
> If you want the indices to match their original position, then you
> would need something like:
>[color=green][color=darkred]
> >>> list(enumerate( mystr).iter_bac kwards())[/color][/color]
> [(2, 'c'), (1, 'b'), (0, 'a')]
>
> The implementation would need to access both mystr.iterbackw ards()
> and mystr.__len__() .
>
> At first glance, this is a can of worms, a pandora's box,
> a gordian knot, or some unnamed code smell unsuitable
> for this mixed metaphor.[/color]

You can count down starting at -1 for reverse enumeration and keep that can
of pandora's knots closed :-)

The only drawback I see would be that the following behaviour might not be
what you expect:
[color=blue][color=green][color=darkred]
>>> [(i, c, "uvwxyz"[i]) for i, c in reverse_enumera te("abc")][/color][/color][/color]
[(-1, 'c', 'z'), (-2, 'b', 'y'), (-3, 'a', 'x')][color=blue][color=green][color=darkred]
>>>[/color][/color][/color]

Peter

[Peter Otten]

Re: Pre-PEP: reverse iteration methods

Raymond Hettinger wrote:
[color=blue]
> If you want the indices to match their original position, then you
> would need something like:
>[color=green][color=darkred]
> >>> list(enumerate( mystr).iter_bac kwards())[/color][/color]
> [(2, 'c'), (1, 'b'), (0, 'a')]
>
> The implementation would need to access both mystr.iterbackw ards()
> and mystr.__len__() .
>
> At first glance, this is a can of worms, a pandora's box,
> a gordian knot, or some unnamed code smell unsuitable
> for this mixed metaphor.[/color]

You can count down starting at -1 for reverse enumeration and keep that can
of pandora's knots closed :-)

The only drawback I see would be that the following behaviour might not be
what you expect:
[color=blue][color=green][color=darkred]
>>> [(i, c, "uvwxyz"[i]) for i, c in reverse_enumera te("abc")][/color][/color][/color]
[(-1, 'c', 'z'), (-2, 'b', 'y'), (-3, 'a', 'x')][color=blue][color=green][color=darkred]
>>>[/color][/color][/color]

Peter

[Christoph Becker-Freyseng]

Re: Pre-PEP: reverse iteration methods

I like the idea of having some iterator.backwa rds, backwards(itera tor) etc.

However especially reading Andrew Dalke's postings and replies (and
having thought about using internally len() and so on --- but then
thinking of iterator maybe having *no* __len__)
I now think that reverse iteration is not well defined when __len__
can't be defined (and sometimes even if it is). This is not the case for
list-like objects as they
have a predictable fixed length (even if the __len__-method isn't
actually implemented).
Let me give an example:

class NaturalNumbers:
def __init__(self):
self.n= 0
def __iter__(self):
return self
def next(self):
self.n+=1
return self.n


This is surely ordered but defining the reverse-order is difficult.
Maybe it should always return infty then.

Or think about a "Tape-Iterator". An object that reads data from e.g. a
file forwards/next and backwards/iter_backwards.
What would you expect to get if tape is at position x and you say
tape.backwards( )?
Should it be the last byte of the file or maybe that on position x-1 ?
This shows that we can get into trouble when we have already iterated
"in the right direction" and then start to do "backwards" .

While reverse-iteration is a sound idea we need a clear definition of
what is meant!


I thought of the following (I give multiple possibilies named a,b,c, ...
finally only one may be used):
1. If iterator has fixed/determined length (so it could be converted
into a regular list):
a) iterator.iter_b ackwards() creates an independent reverse-iterator:
1.1)
l2= list(iterator)
l1= list(iterator.i ter_backwards() )
l2.reverse()
l1 and l2 have to be equal
1.2)
l1= list(iterator.i ter_backwards() )
l2= list(iterator)
l2.reverse()
l1 and l2 have to be equal
(next cases as examples for simplicity)
1.3)
it= range(4)
it.next()
l1= list(it.iter_ba ckwards())
l2= list(it)
-> l1 == [3,2,1]
l2 == [1,2,3]
1.4)
it= range(4)
itBack= it.iter_backwar ds()
l1= [itBack.next(), itBack.next(), itBack.next()]
l2= [it.next(), it.next(), it.next()]
-> l1= [3,2,1]
l2= [0,1,2]
b) iterator.iter_b ackwards() creates a dependent reverse-iterator:
1.1) 1.2) like in a)
(next cases as examples for simplicity)
1.3)
it= range(4)
it.next()
l1= list(it.iter_ba ckwards())
l2= list(it)
-> l1 == [0,]
l2 == [0,1,2,3]
1.4)
it= range(4)
itBack= it.iter_backwar ds()
l1= [itBack.next(), itBack.next(), itBack.next()]
l2= [it.next(), it.next(), it.next()]
-> l1= [3,2,1]
l2= [1,2,3]
2. Infinite/non-determined iterators:
They should implement reverse-iteration in a way that
iterator.next()
iterator.iter_b ackwards().next ()
is a nop
and
iterator.iter_b ackwards().next ()
iterator.next()
is a nop, too.
Or if there are more backward than forward-steps should raise some
StopBackwardIte rator



I'm sure there are a lot more and probably better definitions, so I hope
we will find a useful one.


Christoph Becker-Freyseng

[Christos TZOTZIOY Georgiou]

Re: Pre-PEP: reverse iteration methods

On Wed, 24 Sep 2003 00:30:31 GMT, rumours say that "Raymond Hettinger"
<vze4rx4y@veriz on.net> might have written:
[color=blue]
>Abstract
>========
>
>This proposal is to extend the API of several sequence types
>to include methods for iterating over the sequence in reverse.[/color]

-0

I believe this should be a function in itertools.

For indexable sequences, a little modification of itertools.islic e would
do the trick, since it can't at the moment; it's designed for forward
iteration.

Helpful error messages:[color=blue][color=green][color=darkred]
>>> itertools.islic e(lst, len(lst)-1, -1, -1)[/color][/color][/color]
ValueError: Stop argument must be an integer or None.[color=blue][color=green][color=darkred]
>>> itertools.islic e(lst, len(lst)-1, None, -1)[/color][/color][/color]
ValueError: Step must be one or larger for islice().

For non-indexable sequences (eg a file object), things get hairier, but
given enough memory, it's not hard.
--
TZOTZIOY, I speak England very best,
Microsoft Security Alert: the Matrix began as open source.

[Irmen de Jong]

Re: Pre-PEP: reverse iteration methods

Raymond Hettinger wrote:[color=blue]
> Add a method called iter_backwards( ) to sequence objects that can benefit
> from it. The above examples then simplify to::[/color]

I'm not too fond of the name "iter_backwards ". I think it is too long
(with respect to the already existing "iter" built-in function).

It's just my feeling towards the name, but to me "iter_backwards " sounds
more like an action that is performed on the object it is called on
(a real method so to speak, not a factory method):
"seq.iter_backw ards()" reads to me at first glance: 'iterate over the
seq in backward direction'. Not: 'return a reverse iterator object'.
('iter' reads like the verb/action 'iterate' instead of a noun).

Instead, "backwards_iter ", "back_iter" or preferrably just "riter"
reads more natural to me:
"seq.back_iter( )" reads to me at first glance: 'get a backwards iteration
object for seq'. ('iter' reads like the noun 'iterator', not a verb).


[color=blue]
> No language syntax changes are needed.[/color]

Making it a method, indeed. But then there is this difference
between *forward* iteration and *backward* iteration, right?

iter(seq) --> get a (forward) iterator for seq
seq.riter() --> get a (backward) iterator for seq

How is this easily explained to new people? Why not keep it
orthogonal:

iter(seq) and riter(seq)
~or~
seq.iter() and seq.riter()

For what it's worth (probably nothing, but hey), in C++ STL
we have seq.begin() that returns a forward iterator, and
seq.rbegin() that returns a backward iterator.

[color=blue]
> * Should tuples be included?[/color]
Don't really care. Are there any reasons why they shouldn't?
[color=blue]
> * Should file objects be included?[/color]
Don't care. I've never had to read a file in reverse.
[color=blue]
> * Should enumerate() be included?[/color]
I think it should.


--Irmen de Jong

[Bob Gailer]

Re: Pre-PEP: reverse iteration methods

At 06:30 PM 9/23/2003, you wrote:
[color=blue]
>Here is a discussion draft of a potential PEP.
>The ideas grew out of the discussion on pep-284.
>Comments are invited. Dart throwing is optional.
>
>The discussion so far has focused on how to modify the operand of for x in.
>
>There is another viewpoint: consider that we are modifying the behavior of
>for x in
>
>In APL we often modify the behavior of a primitive operator by adding
>something to the operator itself. For example
>+/A means apply + along the last last dimension of the array A. (e.g. sum
>the elements in each row of the matrix A)
>To sum along the columns change the expression to =+/[1]A where the index
>modifies the / operator.
>
>Could this open the door to some fundamentally new Python syntax that
>would support the modification of keyword behavior? e.g.:
>
>for x in[-1] list:
>for[-1] x in list:
>for x in[-1] list:for x in[-1] list:
>for.reverse x in list:
>for x out list:
>rof x in list:
>
>Let's brainstorm?[/color]

Bob Gailer
bgailer@alum.rp i.edu
303 442 2625


---
Outgoing mail is certified Virus Free.
Checked by AVG anti-virus system (http://www.grisoft.com).
Version: 6.0.506 / Virus Database: 303 - Release Date: 8/1/2003

[Raymond Hettinger]

Re: Pre-PEP: reverse iteration methods

[Raymond][color=blue][color=green]
> >Abstract
> >========
> >
> >This proposal is to extend the API of several sequence types
> >to include methods for iterating over the sequence in reverse.[/color][/color]

[Christos TZOTZIOY Georgiou][color=blue]
> -0
>
> I believe this should be a function in itertools.
>
> For indexable sequences, a little modification of itertools.islic e would
> do the trick, since it can't at the moment; it's designed for forward
> iteration.
>
> Helpful error messages:[color=green][color=darkred]
> >>> itertools.islic e(lst, len(lst)-1, -1, -1)[/color][/color]
> ValueError: Stop argument must be an integer or None.[color=green][color=darkred]
> >>> itertools.islic e(lst, len(lst)-1, None, -1)[/color][/color]
> ValueError: Step must be one or larger for islice().
>
> For non-indexable sequences (eg a file object), things get hairier, but
> given enough memory, it's not hard.[/color]

Here's a quick and dirty implementation of your idea (kept separate
from islice for clarity). On the plus side, it is somewhat clean and
easy to use. On the minus side:
* It's slower than custom iterator methods
* It behaves badly with infinite iterators as inputs
* For non-indexables, it silently transitions into a
non-lazy, memory intensive mode with a long
delay on the first call. In my opinion, this defeats
the purpose of using iterators in the first place.

def ireverse(obj):
assert not hasattr(obj, 'keys')
try:
for i in xrange(len(obj)-1, -1, -1):
yield obj[i]
except (AttributeError , TypeError):
x = list(obj) # XXX fails with infinite iterators
x.reverse()
for elem in x:
yield elem

for i in ireverse(xrange (5)):
print i

for c in ireverse('abcde '):
print c

for elem in ireverse(['atom', 'beta', 'curry']):
print elem

for line in ireverse(file('/autoexec.bat')) :
print line.rstrip()

for x in reverse(itertoo ls.count()):
# Never gets here and Python dies with a MemoryError
# from the infinite loop
pass


Raymond Hettinger

[Peter Otten]

Re: Pre-PEP: reverse iteration methods

Raymond Hettinger wrote:
[color=blue]
> * It behaves badly with infinite iterators as inputs[/color]

[...]
[color=blue]
> def ireverse(obj):
> assert not hasattr(obj, 'keys')[/color]

# let inifinite iterators identify themselves
assert not hasattr(obj, 'infinite')
[color=blue]
> try:
> for i in xrange(len(obj)-1, -1, -1):
> yield obj[i]
> except (AttributeError , TypeError):
> x = list(obj) # XXX fails with infinite iterators
> x.reverse()
> for elem in x:
> yield elem[/color]

As infinite iterators are rare, it would not be too cumbersome to let them
identify themselves as such.

Peter

[Andrew Dalke]

Re: Pre-PEP: reverse iteration methods

Stephen Horne:[color=blue]
> To me, the reason to use a method (or property) is simply that most
> types cannot be efficiently 'backwardised'.[/color]

Which is why my function looks for an '__riter__' under
the covers, so that an object can provide a specialized
implementation, if possible.

If it can't, I then proposed an implementation which will
iterate in reverse through lists and list-like interfaces (things
indexed by 0, 1, ... len(obj)-1). There is a problem though
in that my attempt at a 'generic' reverse implementation
will give strange errors in dictionary-like interfaces.
[color=blue]
> For instance, iterators in
> general would have to be buffered into a list an then the resulting
> list iterated backwards. That could be useful, but the overhead is
> sufficient that I think explicitly writing 'list (x).backward ()'
> rather than 'x.backward ()' would be a good thing.[/color]

Those objects which implement a 'reverse_iterat e' /
'backward' / whatever are identical to those which would
implement a __riter__ accessed under the covers.

My question is, what to do about objects which *don't*
provide a special method. Should there still be a standard
way to do a reverse iteration through them?

The only two I can think of are:
- assume
for i in range(len(obj)-1, -1, -1): yield obj[i]
works as a backup. It doesn't quite work because of
dictionaries.

- assume that storing all elements in a temporary
list and doing a reverse on the temp list is okay.
As you point out, it is the most generic but doesn't
work if memory is a problem. (There's also a
concern about proper destruction order if you want
to delete elements from a list starting from the end.)

- (There's a third, which is O(n**2). At every request,
iterate through the list to find the last element.)

If there is an acceptable solution (which needn't be
perfect, just practicable) then it's a good reason to
have it be a builtin over a special method.

I still point out that there are many other ways of
doing iteration and I don't see what makes reverse
iteration so important to get its own method.

Andrew
dalke@dalkescie ntific.com

[Andrew Dalke]

Re: Pre-PEP: reverse iteration methods

Me:[color=blue]
> The only two I can think of are:[/color]
[color=blue]
> for i in range(len(obj)-1, -1, -1): yield obj[i][/color]

Peter Otten proposed a nice variation; assume negative
indicies work. Then there's no need to assume len
works.

Andrew
dalke@dalkescie ntific.com

[Christos TZOTZIOY Georgiou]

Re: Pre-PEP: reverse iteration methods

On Wed, 24 Sep 2003 20:46:16 +0200, rumours say that Peter Otten
<__peter__@web. de> might have written:
[color=blue]
> # let inifinite iterators identify themselves
> assert not hasattr(obj, 'infinite')
>
>As infinite iterators are rare, it would not be too cumbersome to let them
>identify themselves as such.[/color]

This is an interesting idea.
--
TZOTZIOY, I speak England very best,
Microsoft Security Alert: the Matrix began as open source.