[Python-ideas] Previous item from iterator.

[Andrew Barnert]

On Wednesday, April 15, 2015 9:37 AM, Todd <toddrjen at gmail.com> wrote:

>On Wed, Apr 15, 2015 at 6:26 PM, Krystian Kichewko <krystiankichewko at gmail.com> wrote:
>
>Hi all!
>>
>>I hope I'm posting in correct place.
>>
>>I would like to propose an idea for iterating over an iterator in reverse.
>>
>>prev(iterator[, default])
>>
>>Built-in function: it should retrieve previous element from an
>>iterator by calling its __prev__() method.
>>
>>
>>Add new, optional method to iterator protocol:
>>
>>__prev__()
>>
>>This method should return previous element from iterator or raise
>>StopIteration exception if the is no previous element.
>>
>>
>>This should be optional, because it would be hard to implement this
>>behaviour in some iterators (e.g. It would be hard to do this for file
>>iterator that returns lines). Other iterators should be modified to
>>include __prev__() (e.g. itertools.count(), list iterator).
>>
>>If an iterator doesn't support prev TypeError should be raise when
>>prev is called.
>>
>>Please let me know what you think about this? If there are no obvious
>>problems I will write a PEP for this.
>>
>>Thanks,
>>Krystian Kichewko
>>
>>ps. I've tried searching for this idea on python-ideas and couldn't
>>find anything. If I missed it and my email is a duplicate, sorry.
>>
>
>What is the use-case for this?  If the iterator can go both directions, 
what is the case where this would be useful but an object with an index,
like a list, wouldn't be?


http://stupidpythonideas.blogspot.com/2014/07/swift-style-map-and-filter-views.html discusses one use, starting from the idea of making map and friends return views instead of just iterators, and exploring how Swift makes that work. (Note that map can return views that can be iterated exactly as freely as its argument, but filter can't do anything better than bidirectional iteration even if given a randomly-accessible iterable.) My conclusion was that the fundamental changes required to Python's iteration protocol would probably be more harmful than the benefits, but I tried to write it in such a way that someone else can come to their own conclusions and use my evidence…

Meanwhile, the input/forward/bidirectional/random-access categories of iteration are fundamental to the design of the Standard Template Library which became the core of C++'s stdlib (and D's). The Java Collections Framework which became the core of Java's collections in 1.2+, the Swift stdlib's collections, and many other languages and libraries are strongly inspired by the STL. So, there's plenty of more general information out there someone could gather and summarize to make the case (that someone presumably being the OP who wants this feature added), from Stepanov's original paper to tutorials on building sequences and generators for Swift.

The paradigm examples of bidirectional iteration are linked-list-like and tree-like iteration. In particular, almost all kinds of sorted containers can be iterated in sorted order bidirectionally, but not randomly.

There are also fundamental iterator transformations that can only give you a bidirectional iterator, even if given a randomly-accessible one, like filter or merge. (As opposed to map or reverse, which can always give you the same kind of iterator they were given.)


There aren't too many fundamental algorithms that require bidirectional iteration but not random-access iteration, or that can be more efficient with bidirectional than with forward, but there are some.

Note that sequences aren't the same thing as randomly-accessible iterators: map doesn't return a sequence. Unless you want to change Python to make sequence-like dynamic views, rather than iterators, the core concept behind everything, which brings us back to the Swift design I mentioned at the top.

To me, it seems strange adding bidirectional iteration without also adding forward iteration (which in Python terms would probably mean a __peek__ method), and random-access iteration (which could mean __add__ and __subtract__ a la C pointer arithmetic). There are far more algorithms that require, or can be algorithmically more efficient with or significantly simpler to implement with, forward iterators and random-access iterators, as 30-odd years of experience with STL and its descendants have demonstrated. Even more so in a language that doesn't even have linked lists or sorted collections in its stdlib.

Finally, Andrei Alexandrescu has two interesting presentations that challenge the design behind the STL and its descendants; IIRC they're called "25 Years With STL" and "Iterators Must Go". His main conclusion is that the iteration _interface_ used by C++ is definitely a problem, but the basic concept may be workable into something useful. C++11's ranges and Swift's views can be seen as different attempts at this, the former probably not radical enough (it's closer to boost:range, which he'd already shown was insufficient) and the latter probably too radical.