Abstract

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

Motivation

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

foriinxrange(n-1,-1,-1):printseqn[i]

One other current approach involves reversing a list before iteratingover it. That technique wastes computer cycles, memory, and lines ofcode:

rseqn=list(seqn)rseqn.reverse()forvalueinrseqn:printvalue

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

Reverse iteration is much less common than forward iteration, but itdoes arise regularly in practice. SeeReal World Use Cases below.

Proposal

Add a builtin function calledreversed() that makes a reverseiterator over sequence objects that support __getitem__() and__len__().

The above examples then simplify to:

foriinreversed(xrange(n)):printseqn[i]

foreleminreversed(seqn):printelem

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

The implementation could be as simple as:

defreversed(x):ifhasattr(x,'keys'):raiseValueError("mappings do not support reverse iteration")i=len(x)whilei>0:i-=1yieldx[i]

No language syntax changes are needed. The proposal is fully backwardscompatible.

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 meansthat if the function is found to be useless, it can be removed beforePy2.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 namereverse is not a candidate because it duplicates the nameof the list.reverse() which mutates the underlying list.

Discussion

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

Real World Use Cases

Here are some instances of reverse iteration taken from the standardlibrary 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 wouldnot help.

• heapq.heapify() usesforiinxrange(n//2-1,-1,-1) becausehigher-level orderings are more easily formed from pairs oflower-level orderings. A forward version of this algorithm ispossible; however, that would complicate the rest of the heap codewhich iterates over the underlying list in the opposite direction.The replacement codeforiinreversed(xrange(n//2)) makesclear 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 theunderlying list is altered during iteration.

• platform._dist_try_harder() usesforninrange(len(verfiles)-1,-1,-1) because the loop deletesselected elements fromverfiles but needs to leave the rest ofthe list intact for further iteration.
• random.shuffle() usesforiinxrange(len(x)-1,0,-1) becausethe algorithm is most easily understood as randomly selectingelements from an ever diminishing pool. In fact, the algorithm canbe run in a forward direction but is less intuitive and rarelypresented that way in literature. The replacement codeforiinreversed(xrange(1,len(x))) is much easierto verify visually.
• rfc822.Message.__delitem__() uses:

  list.reverse()foriinlist:delself.headers[i]

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

Rejected Alternatives

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

Putting the function in another module or attaching it to a type objectis not being considered. Like its cousins,zip() andenumerate(),the function needs to be directly accessible in daily programming. Eachsolves a basic looping problem: lock-step iteration, loop counting, andreverse iteration. Requiring some form of dotted access would interferewith their simplicity, daily utility, and accessibility. They are corelooping constructs, independent of any one application domain.

Copyright

This document has been placed in the public domain.