On Wednesday, April 15, 2015 4:04 PM, Steven D'Aprano <steve@pearwood.info> wrote:
On Wed, Apr 15, 2015 at 10:25:58PM +0000, Andrew Barnert wrote:
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.
In Python terms though, if you think you want a linked-list, you probably actually want a regular list. I'm not so sure about trees, but the lack of any trees in the std lib is probably a hint that a dict makes a good replacement.
Well, there _are_ trees in the stdlib, buried inside application-level things like HTML documents. And, if sorted collections were added to the stdlib, they'd probably be trees too. There's also a linked list buried inside OrderedDict. (You could ask why it doesn't just use a list.) That being said, this is part of the reason I didn't think my related idea needed to be added to Python, or even proposed. Linked lists and trees are very important data structures to recursive-decomposition functional programming, but they're not nearly as important as people think to other paradigms. It's not just Python itself that proves this; std::vector (a resizable array, like Python's list) is by far the most used container in C++, and not including std::unordered_map (a hash table, like Python's dict) was the most widely-touted gap in the stdlib until it was finally added. And the Alexandrescu presentations I mentioned also imply that at least some of the reasons the iterator categories are used in code written for C++ and its descendants is that you're kind of forced into it, and with a bette API many of these uses wouldn't arise.
[...]
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.
Are any of them unable to be efficiently reimplemented in terms of random access lists? What does bidirectional iteration give us that sequences don't?
Any time you use an iterator transformation like filter or partition, what you get is (or could be) bidirectionally iterable, but it's not randomly accessible. And filtering lists is a pretty common thing to do (common enough for filter to be a builtin, and even for an equivalent operation to have syntactic support). Even when you use iterator transformations like map that are conceptually randomly accessible, it's hard to see how they could be actually randomly accessed in today's Python. We could provide __add__ and __subtract__ a la C pointer arithmetic, but a lot of people would probably prefer not to use them when not necessary. Or we could just make views fundamental and largely sideline iterators (which does work pretty well for numpy), but that would be a huge and radical change to Python. Or we could provide views and iterators side by side, but that makes the language twice as big and twice as hard to fit in your head.
The rest of your post is interesting, but I don't see the relevance to
*Python*. Bidirectional iteration isn't being proposed in a vacuum, it has to compete with existing alternatives such as lists and dicts.
That's kind of my point: bidirectional iteration doesn't fit into Python; forward, bidirectional, and random access iteration _might_ fit into Python, but only by radically changing Python in a way that's almost certainly not acceptable. (In my blog post, at the end, I tried to work out whether there are smaller steps in that direction that might be worthwhile on their own, but none of them seemed worthwhile enough for me to even bring up on python-ideas, much less push for.)