Pre-PEP: reverse iteration methods

Andrew Dalke adalke at mindspring.com
Wed Sep 24 21:51:56 CEST 2003


Stephen Horne:
> To me, the reason to use a method (or property) is simply that most
> types cannot be efficiently 'backwardised'.

Which is why my function looks for an '__riter__' under
the covers, so that an object can provide a specialized
implementation, if possible.

If it can't, I then proposed an implementation which will
iterate in reverse through lists and list-like interfaces (things
indexed by 0, 1, ... len(obj)-1).  There is a problem though
in that my attempt at a 'generic' reverse implementation
will give strange errors in dictionary-like interfaces.

> For instance, iterators in
> general would have to be buffered into a list an then the resulting
> list iterated backwards. That could be useful, but the overhead is
> sufficient that I think explicitly writing 'list (x).backward ()'
> rather than 'x.backward ()' would be a good thing.

Those objects which implement a 'reverse_iterate' /
'backward' / whatever are identical to those which would
implement a __riter__ accessed under the covers.

My question is, what to do about objects which *don't*
provide a special method.  Should there still be a standard
way to do a reverse iteration through them?

The only two I can think of are:
  - assume
       for i in range(len(obj)-1, -1, -1):  yield obj[i]
     works as a backup.  It doesn't quite work because of
     dictionaries.

  - assume that storing all elements in a temporary
     list and doing a reverse on the temp list is okay.
     As you point out, it is the most generic but doesn't
     work if memory is a problem.  (There's also a
    concern about proper destruction order if you want
    to delete elements from a list starting from the end.)

  - (There's a third, which is O(n**2).  At every request,
      iterate through the list to find the last element.)

If there is an acceptable solution (which needn't be
perfect, just practicable) then it's a good reason to
have it be a builtin over a special method.

I still point out that there are many other ways of
doing iteration and I don't see what makes reverse
iteration so important to get its own method.

                    Andrew
                    dalke at dalkescientific.com







More information about the Python-list mailing list