Reversible Iterators?

Usually, IteratorProtocol is assumed to vend a sequence to values whose calculation is irrevocable once done. But what if the transformation of next() is reversible? Should we add a ReversibleIteratorProtocol with a previous()?

What's wrong with sticking with BidirectionalCollection? Well, we could have one or both ends of the iteration be infinite. Or so long it's practically infinite (i.e. computing distance(from: to:) would take too long to be useful).

3 Likes

Actually, there have been times when I wanted a whole suite of iterators, including a kind of RandomAccessIterator which you could set to any index.

The alternative is kind of awkward - even if it's easier to process your data using iterators, you need to keep slices around so you can "adjust" the iterator.

C++ has a similar kind of thing. Instead of jumping to arbitrary indexes, it allows incrementing by a number of steps at a time. Also a nice feature.

Do you have some examples of concrete types where this issue comes into play?

How about an iterator that wraps around a collection and cycles over it? It's infinite, but has well defined next/previous operations.

Well, there’s Fibonacci sequences, and regular arithmetic and geometric sequences. But the spark this time was C++’s previous- and next-permutation functions.

I just realized: what would a jump (for a random-access iterator) of zero mean? Then I realized an equivalent query: what happens when next() and previous() are called back to back? I guess it’ll return the same element twice.

The model here is weird because next and previous include a dereference but jump wouldn’t.

Can you elaborate on this answer? There's no problem implementing Fibonacci sequences in Swift today, so what issues are you running into that this idea would address?