Velocity Reviews > Pre-PEP: reverse iteration methods

# Pre-PEP: reverse iteration methods

Christoph Becker-Freyseng
Guest
Posts: n/a

 09-24-2003
I like the idea of having some iterator.backwards, backwards(iterator) 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_backwards() creates an independent reverse-iterator:
1.1)
l2= list(iterator)
l1= list(iterator.iter_backwards())
l2.reverse()
l1 and l2 have to be equal
1.2)
l1= list(iterator.iter_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_backwards())
l2= list(it)
-> l1 == [3,2,1]
l2 == [1,2,3]
1.4)
it= range(4)
itBack= it.iter_backwards()
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_backwards() 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_backwards())
l2= list(it)
-> l1 == [0,]
l2 == [0,1,2,3]
1.4)
it= range(4)
itBack= it.iter_backwards()
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_backwards().next()
is a nop
and
iterator.iter_backwards().next()
iterator.next()
is a nop, too.
Or if there are more backward than forward-steps should raise some
StopBackwardIterator

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
Guest
Posts: n/a

 09-24-2003
On Wed, 24 Sep 2003 00:30:31 GMT, rumours say that "Raymond Hettinger"
<(E-Mail Removed)> might have written:

>Abstract
>========
>
>This proposal is to extend the API of several sequence types
>to include methods for iterating over the sequence in reverse.

-0

I believe this should be a function in itertools.

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

Helpful error messages:
>>> itertools.islice(lst, len(lst)-1, -1, -1)

ValueError: Stop argument must be an integer or None.
>>> itertools.islice(lst, len(lst)-1, None, -1)

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.

Bob Gailer
Guest
Posts: n/a

 09-24-2003
At 06:30 PM 9/23/2003, you wrote:

>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?

Bob Gailer
http://www.velocityreviews.com/forums/(E-Mail Removed)
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

Irmen de Jong
Guest
Posts: n/a

 09-24-2003
Raymond Hettinger wrote:
> Add a method called iter_backwards() to sequence objects that can benefit
> from it. The above examples then simplify to::

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_backwards()" 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).

> No language syntax changes are needed.

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.

> * Should tuples be included?

Don't really care. Are there any reasons why they shouldn't?

> * Should file objects be included?

Don't care. I've never had to read a file in reverse.

> * Should enumerate() be included?

I think it should.

--Irmen de Jong

Raymond Hettinger
Guest
Posts: n/a

 09-24-2003
[Raymond]
> >Abstract
> >========
> >
> >This proposal is to extend the API of several sequence types
> >to include methods for iterating over the sequence in reverse.

[Christos TZOTZIOY Georgiou]
> -0
>
> I believe this should be a function in itertools.
>
> For indexable sequences, a little modification of itertools.islice would
> do the trick, since it can't at the moment; it's designed for forward
> iteration.
>
> Helpful error messages:
> >>> itertools.islice(lst, len(lst)-1, -1, -1)

> ValueError: Stop argument must be an integer or None.
> >>> itertools.islice(lst, len(lst)-1, None, -1)

> 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.

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(itertools.count()):
# Never gets here and Python dies with a MemoryError
# from the infinite loop
pass

Raymond Hettinger

Peter Otten
Guest
Posts: n/a

 09-24-2003
Raymond Hettinger wrote:

> * It behaves badly with infinite iterators as inputs

[...]

> def ireverse(obj):
> assert not hasattr(obj, 'keys')

# let inifinite iterators identify themselves
assert not hasattr(obj, 'infinite')

> 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

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

Peter

Andrew Dalke
Guest
Posts: n/a

 09-24-2003
Stephen Horne:
> To me, the reason to use a method (or property) is simply that most
> types cannot be efficiently 'backwardised'.

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.

> 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.

Those objects which implement a 'reverse_iterate' /
'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
(E-Mail Removed)

Andrew Dalke
Guest
Posts: n/a

 09-24-2003
Me:
> The only two I can think of are:

> for i in range(len(obj)-1, -1, -1): yield obj[i]

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

Andrew
(E-Mail Removed)

Christos TZOTZIOY Georgiou
Guest
Posts: n/a

 09-24-2003
On Wed, 24 Sep 2003 20:46:16 +0200, rumours say that Peter Otten
<(E-Mail Removed)> might have written:

> # 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.

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

David Eppstein
Guest
Posts: n/a

 09-25-2003
> > # 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.

It would be quite cumbersome to have to identify simple generators as
infinite or finite manually, and impossible (halting problem) to do so
reliably automatically.

--
David Eppstein http://www.ics.uci.edu/~eppstein/
Univ. of California, Irvine, School of Information & Computer Science

 Thread Tools

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is OffTrackbacks are On Pingbacks are On Refbacks are Off Forum Rules

 Similar Threads Thread Thread Starter Forum Replies Last Post Rudi Java 5 10-01-2008 03:30 AM Raymond Hettinger Python 31 11-06-2003 07:27 AM Raymond Hettinger Python 14 11-01-2003 05:51 PM Robert Brewer Python 1 10-29-2003 07:28 PM Raymond Hettinger Python 59 09-29-2003 05:35 PM

Advertisments