PEP:322
Title:Reverse Iteration
Version:1817
Last-Modified:2004-05-19 14:18:55 -0700 (Wed, 19 May 2004)
Author:Raymond Hettinger <python at rcn.com>
Status:Final
Type:Standards Track
Content-Type:text/x-rst
Created:24-Sep-2003
Python-Version:2.4
Post-History:24-Sep-2003

Contents

Abstract

This proposal is to add a builtin function to support reverse iteration over sequences.

Motivation

For indexable objects, current approaches for reverse iteration are error prone, unnatural, and not especially readable:

for i in xrange(n-1, -1, -1):
    print seqn[i]

One other current approach involves reversing a list before iterating over it. That technique wastes computer cycles, memory, and lines of code:

rseqn = list(seqn)
rseqn.reverse()
for value in rseqn:
    print value

Extended slicing is a third approach that minimizes the code overhead but does nothing for memory efficiency, beauty, or clarity.

Reverse iteration is much less common than forward iteration, but it does arise regularly in practice. See Real World Use Cases below.

Proposal

Add a builtin function called reversed() that makes a reverse iterator over sequence objects that support __getitem__() and __len__().

The above examples then simplify to:

for i in reversed(xrange(n)):
    print seqn[i]
for elem in reversed(seqn):
    print elem

The core idea is that the clearest, least error-prone way of specifying reverse iteration is to specify it in a forward direction and then say reversed.

The implementation could be as simple as:

def reversed(x):
    if hasattr(x, 'keys'):
        raise ValueError("mappings do not support reverse iteration")
    i = len(x)
    while i > 0:
        i -= 1
        yield x[i]

No language syntax changes are needed. The proposal is fully backwards compatible.

A C implementation and unit tests are at: http://www.python.org/sf/834422

BDFL Pronouncement

This PEP has been conditionally accepted for Py2.4. The condition means that if the function is found to be useless, it can be removed before Py2.4b1.

Alternative Method Names

The name reverse is not a candidate because it duplicates the name of the list.reverse() which mutates the underlying list.

Discussion

The case against adoption of the PEP is a desire to keep the number of builtin functions small. This needs to weighed against the simplicity and convenience of having it as builtin instead of being tucked away in some other namespace.

Real World Use Cases

Here are some instances of reverse iteration taken from the standard library and comments on why reverse iteration was necessary:

Rejected Alternatives

Several variants were submitted that attempted to apply reversed() to all iterables by running the iterable to completion, saving the results, and then returning a reverse iterator over the results. While satisfying some notions of full generality, running the input to the end is contrary to the purpose of using iterators in the first place. Also, a small disaster ensues if the underlying iterator is infinite.

Putting the function in another module or attaching it to a type object is not being considered. Like its cousins, zip() and enumerate(), the function needs to be directly accessible in daily programming. Each solves a basic looping problem: lock-step iteration, loop counting, and reverse iteration. Requiring some form of dotted access would interfere with their simplicity, daily utility, and accessibility. They are core looping constructs, independent of any one application domain.