PEP: 322 Title: Reverse Iteration Version: $Revision$ Last-Modified:
$Date$ Author: Raymond Hettinger <python@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

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:
https://bugs.python.org/issue834422

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

-   reviter -- Jeremy Fincher's suggestion matches use of iter()
-   ireverse -- uses the itertools naming convention
-   inreverse -- no one seems to like this one except me

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:

-   atexit.exit_handlers() uses:

        while _exithandlers:
            func, targs, kargs = _exithandlers.pop()
                . . .

    In this application popping is required, so the new function would
    not help.

-   heapq.heapify() uses for i in xrange(n//2 - 1, -1, -1) because
    higher-level orderings are more easily formed from pairs of
    lower-level orderings. A forward version of this algorithm is
    possible; however, that would complicate the rest of the heap code
    which iterates over the underlying list in the opposite direction.
    The replacement code for i in reversed(xrange(n//2)) makes clear the
    range covered and how many iterations it takes.

-   mhlib.test() uses:

        testfolders.reverse();
        for t in testfolders:
            do('mh.deletefolder(%s)' % `t`)

    The need for reverse iteration arises because the tail of the
    underlying list is altered during iteration.

-   platform._dist_try_harder() uses
    for n in range(len(verfiles)-1,-1,-1) because the loop deletes
    selected elements from verfiles but needs to leave the rest of the
    list intact for further iteration.

-   random.shuffle() uses for i in xrange(len(x)-1, 0, -1) because the
    algorithm is most easily understood as randomly selecting elements
    from an ever diminishing pool. In fact, the algorithm can be run in
    a forward direction but is less intuitive and rarely presented that
    way in literature. The replacement code
    for i in reversed(xrange(1, len(x))) is much easier to verify
    visually.

-   rfc822.Message.__delitem__() uses:

        list.reverse()
        for i in list:
            del self.headers[i]

    The need for reverse iteration arises because the tail of the
    underlying list is altered during iteration.

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.

Copyright

This document has been placed in the public domain.