Pre-PEP: reverse iteration methods

Christoph Becker-Freyseng christoph at mmc-startup.com
Wed Sep 24 16:26:10 CEST 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











More information about the Python-list mailing list