Iterating over a sequence in reverse

At work today we stumbled across a situation where we needed to display a list of items in reverse order. The decision to show them in reverse is made in the presentation layer, so altering the code that generates the list in the application logic layer would add coupling between the layers that we would rather avoid. Python’s reverse() function acts on a data structure in place, which we would rather avoid as well. Then we realised that Python’s generators could be used to create a proxy around the sequence allowing us to cycle through it in reverse without altering the sequence itself. Here’s the code:

class ReverseIteratorProxy:
    def __init__(self, sequence):
        self.sequence = sequence
    def __iter__(self):
        length = len(self.sequence)
        i = length
        while i > 0:
            i = i - 1
            yield self.sequence[i]

>>> l = range(10)
>>> l
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> for i in ReverseIteratorProxy(l):
...     print i,
... 
9 8 7 6 5 4 3 2 1 0
>>>

I was going to explain how the above code works, but after several false starts I realised that explaining generators is best left to the experts.

Update: Unsurprisingly, this isn’t exactly a new idea. PEP 322 covers reverse iteration, and the Python Tutorial uses it to illustrate both iterators and generators. Aah well.

Posted 28th January 2004 at 3:58 am

7 comments

If you're using python 2.3, would this have worked? I'm not a python expert so I may be missing something.
>>> l = range(10) >>> l [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] >>> for i in l[::-1]: ... print i, ... 9 8 7 6 5 4 3 2 1 0 >>>
I reread this: http://www.python.org/doc/current/whatsnew/section -slices.html last night.
PterK
Peter van Kampen - 28th January 2004 12:45 - #
It would have worked, but it would have done so by creating a brand new copy of the list in reverse order (just like list[:] creates a new copy replicating the existing order). We wanted the ability to iterate over an existing list in reverse order without copying it first.
Simon Willison - 28th January 2004 16:40 - #

Any reason why just a generator wasn't used (which is simpler)?

>>> def reversegen(sequence):
...     i = len(sequence)
...     while i > 0:
...             i = i - 1
...             yield sequence[i]
...
>>> for x in reversegen(range(10)):
...     print x,
...
9 8 7 6 5 4 3 2 1 0

Generators implement the iterator protocol (they just return themselves on call to __iter__()).

Shalabh Chaturvedi - 29th January 2004 09:20 - #

Yep, Mr Chaturvedi's generator is better. All generators are iterators.

Here's another possible approach:
```
from itertools import imap

def ireverse(seq):
    return imap(seq.__getitem__, xrange(len(seq)-1, -1, -1))
```
If itertools.islice supported negative values, it could be a bit shorter. Oh well.

Giant Steps - 29th January 2004 16:13 - #
My preferred way of expressing this is with the copy. If I have to iterate in-place then I prefer: def ireverse(seq): for i in xrange(len(l), 0, -1) yield len[i-1] Generators express the concept of "iterator" better than classes, if only because they come packaged with less syntactic noise.
Andrae - 29th January 2004 22:55 - #

err...

>>>a = [1,2,3,4,5,6,7,8,9]
>>>for i in a[::-1]: print i,
9 8 7 6 5 4 3 2 1

Lafferty - 16th March 2004 23:53 - #

sorry.... was too late as i read the one posting.
Lafferty - 16th March 2004 23:56 - #

Comments are closed.

Previously hosted at http://simon.incutio.com/archive/2004/01/28/sequenceInReverse

Simon Willison’s Weblog

Iterating over a sequence in reverse

7 comments