Iterators.Reverse type for reverse-order iteration

[stevengj]

This PR closes #23972 by adding a new Reversed{T} Iterators.Reverse{T} wrapper type for reverse-order iteration.

The basic idea (suggested by @Keno) is that you can just loop over Iterators.reverse(iter) and it will go in reverse order, as long as start etcetera have been defined for Reverse{T}. Initially, I've implemented reverse iterators for AbstractArray, AbstractString, Tuple, Generator, and some other iterator types (zip, product, etc)..

I use Reversed and not Reverse because the latter name is already used for Base.Order.Reverse.

To do:

• Tests
• More documentation
• Reverse-iteration support for other iterator types? (I've added most of the low-hanging fruit, I think. Other cases can go in separate PRs.)

[garrison]

julia> Reversed(Reversed([1,2,3]))
Reversed{Reversed{Array{Int64,1}}}(Reversed{Array{Int64,1}}([1, 2, 3]))

Any reason not to return the original object instead?

EDIT: actually, the current result above cannot even be iterated over, throwing MethodError: no method matching start(::Reversed{Reversed{Array{Int64,1}}}).

Also, reverse(Reversed([1,2,3])) throws a MethodError: no method matching reverse(::Reversed{Array{Int64,1}}).

[ararslan]

Should probably add definitions like

Reversed(r::Reversed) = r.iter
reverse(r::Reversed) = copy(r.iter)

[ararslan]

Using collect is kind of weird for strings, isn't it? Or am I missing something?

[ararslan]

Would it be worth adding something like

getindex(r::Reversed, i::Integer) = reverseind(r.iter, Int(i))

?

[stevengj]

@ararslan, I thought about adding getindex, but I forgot about reverseind so I didn't see how to do it generically, and for arrays we can already use views for reverse-order indexing.

However, I'm still not sold on getindex. It's not that useful in this context for strings unless we also add nextind etcetera, and in general we don't usually define getindex for iterators.

[stevengj]

I would have like to have used lower-case for the function, analogous to enumerate, zip, etcetera, but it is too confusing given that we already have a reverse function. Reverse-order iteration seems so basic, however, that I think it is worth exporting Reversed.

Any other bikeshedding on the name?

[ararslan]

Same question regarding collect. Seems odd for strings. (GitHub ate my previous comment.)

[stevengj]

Why is this odd for strings? Reversed{<:String} is an iterator over characters, so should reverse(r) on it be the same as reverse(collect(r))?

[ararslan]

I would have expected that since the underlying object being iterated is a string, unwrapping the Reversed wrapper would give you back the string, just as reverse(::String) gives you a string.

[ararslan]

Calling it Reversed and exporting it seems okay to me.

[stevengj]

Note: 44e383f is a bugfix that should be backported to 0.6. So, that commit should not be squashed with the others when/if this PR is merged.

[garrison]

I don't think calling it reversed would be so bad, might in fact be preferable to calling it Reversed.

[ararslan]

I disagree; I think the difference between reverse and reversed is too subtle.

[stevengj]

Using caps does emphasize that it is a wrapper type (a “noun”) rather than a transformation of the underlying data (a “verb”).

Of course, one could similarly question why we don’t capitalize zip.

[ararslan]

Of course, one could similarly question why we don’t capitalize zip.

In the very specific case of zip, the function returns a different type (Zip1, Zip2, or Zip) depending on the number of arguments. So it's a bit different from Reversed in that regard.

[nalimilan]

We already have filter and Iterators.filter, the latter returning a Iterators.Filter iterator. Why not have reverse and Iterators.reverse, the latter returning an Iterators.Reverse iterator? That would be more consistent than reversed returning a Reversed iterator.

[stevengj]

Note that we actually once did have a Reverse iterator, which was removed by @JeffBezanson for Julia 0.2 because it relied on getindex (#4590). Base.Order subsequently exported Reverse (#6780).

[stevengj]

Probably we should have a reverse(x) = collect(Reversed(x)) fallback too.

[StefanKarpinski]

I think one generally wants a similar kind of collection when reversing, so that fallback might need some tweaking. In general, I suspect that having a general fallback for reversal is not worth it and we should just supply the methods where we know what to do and let people fill in the rest.

[stevengj]

@StefanKarpinski, my objection is that it seems really weird and surprising for a collection to support Reversed but not reverse. (For example, Reverse supports n-dimensional arrays, but reverse does not, and neither does reverse(collect(a)).)

Imagine the user questions: "How do I reverse the order of this collection? reverse doesn't work, and neither does reverse(collect(x))" .... we answer: "Use collect(Reversed(x))" ... "Why wasn't this the default?" ... "Ummm...."

Another way of saying it: this reduces the number of methods a collection needs to implement. If reverse-order iteration is worthwhile, so you implement Reversed{T} methods, wouldn't you want reverse to work too?

[stevengj]

@nalimilan's Iterators.reverse suggestion seems reasonable to me.

[stevengj]

Should we just document r.itr instead of suggesting Reversed(r) or Iterators.reverse(r) or whatever we decide to call it?

r.itr is a bit more transparent and convenient, but it does expose the internal field name.

[StefanKarpinski]

@stevengj, I'm willing to live with a few awkward questions about missing features in 1.0 rather than adding new, half-baked functionality that we then have to live with for a decade, no matter how wrong it turns out we are about how it behaves.

[stevengj]

Okay, I removed the Base.reverse fallback, and renamed to Iterators.reverse and Iterators.Reverse.

[ararslan]

This is kind of weird in that you're asking for a lazy reverse but getting a new range back instead of a Reverse iterator.

[stevengj]

Ranges are already lazy, so it seems silly to define Reverse iteration methods for ranges.

But I guess I can now change this to a method of Iterators.reverse instead of Reverse.

[ararslan]

Okay. I trust your judgement for whatever the best approach is here, just thought I'd point it out.

[stevengj]

Is there some reason that Iterators.filter was not listed here previously? It seemed like an oversight.

Also, the ordering of methods here seems kind of random; is it automatically sorted?

[ararslan]

I agree, I think it was an oversight. Documenter doesn't do any sorting of methods—they appear in the output in the same order as you write them AFAIK.

[stevengj]

Actually, now that I look more closely at the order, it seems like they have been somewhat topically sorted, so I think the order is fine as-is.

[ararslan]

Yeah, there have been a few issues with Circle, particularly x86-64, lately.

[stevengj]

For comparison, the Python reversed iterator (PEP 322) only works for indexable collections. (We used to do the same thing, but removed it: #4590.) In Swift, the reversedcollection iterator only works for collections with "bidirectional indices", which is essentially equivalent to requiring getindex plus prevind and nextind. Ruby's reverse_each apparently only works on arrays (i.e. requires getindex). The only fully general lazy iterator reversal protocol I've come across in the "standard" libraries of other languages is Boost's bidirectional traversal concept and resulting reverse iterator.

[stevengj]

Rebased to fix conflict.

Note: if/when this is merged, don't squash since the bugfix commit should be backported.

[mauro3]

It looks like this was squashed, but wasn't this supposed to be not squashed?

[ararslan]

It was not squashed.

[mauro3]

Ok, sorry for the noise!