Pre-PEP: reverse iteration methods

[Raymond Hettinger]

[Raymond Hettinger]
> > Reverse iteration is much less common than forward iteration, but it
> > does arise regularly in practice.

[John Roth]
> Absolutely.

Because the question will arise, I did a quick use case analysis from
the standard library.  I'll attach the following to the PEP.  Feel free
to comment or add other use cases.


Raymond Hettinger

--------------------------------------------------------------------------


Use Case Analysis
=================

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()
        . . .
  The application dictates the need to run exit handlers in the
  reverse order they were built.  The "while alist: alist.pop()"
  form is readable and clean; however, it would be slightly faster
  and clearer with:
    for func, target, kargs in _exithandlers.iter_backwards():
          . . .
    del _exithandlers

* difflib.get_close_matches() uses::
    result.sort()           # Retain only the best n.
    result = result[-n:]    # Move best-scorer to head of list.
    result.reverse()        # Strip scores.
    return [x for score, x in result]
  The need for reverse iteration arises from a requirement to return
  a portion of a sort in an order opposite of the sort criterion.  The
  list comprehension is incidental (the third step of a Schwartzian
  transform).  This particular use case can met with extended slicing,
  but the code is somewhat unattractive and hard to visually verify::
      result.sort()
      return result[:-n-1:-1]

* 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.

* 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.  This use
  case could be more efficiently met with itertools.ifilter but the
  lambda condition and functional style would render it less readable.

* 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.

* 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.