Iterators.reverse gives unexpected results when zipping iterators of different lengths

[nalimilan]

In the following example, it sounds like a bug that reverse assumes that the last element of 1:10 goes with the last element of 1:2. This can give misleading results. If possible it would make sense to throw an error in these cases.

julia> first(Iterators.reverse(zip(1:10, 1:2)))
(10, 2)

[ararslan]

cc @stevengj

[stevengj]

This is related to #20499.

My sense is that if the zip arguments have lengths, then zip itself should throw an error if the lengths are unequal.

(If they don't have lengths, reverse will probably fail anyway because they are unlikely to be reversible, but to be on the safe side reverse(::Zip) can throw an error in this case.)

[stevengj]

Note that a similar issue arises for reverse(::Generator), since generators also currently truncate unequal-length iterators.

[nalimilan]

OK, added #20499 for triage.

[nalimilan]

Triage decided not to throw an error when zip is passed arguments with different lengths, so reverse will have to throw the error instead.

[mschauer]

so reverse will have to throw the error instead

Reverse could also be fixed to work with Zips with differing length instead I believe. Is there reason this is not wanted?

[nalimilan]

You mean, start with the element corresponding to the end of the shortest iterator? Makes sense.

[stevengj]

@mschauer, that cannot be done efficiently in general. It might be extremely inefficient if one iterator is much longer than the other. (Not to mention the case of infinite iterators etc.)

[mschauer]

One way to approach this is

reversefrom(r::UnitRange, n::Integer) = reverse(first(r):min(last(r),first(r)+n-1))
reversefrom(it, n) = reverse(take(it, n))
reversefrom(z::Zip1, n) = Zip1(reversefrom(z.a, n))
reversefrom(z::Zip2, n) = Zip2(reversefrom(z.a, n), reversefrom(z.b, n))
reversefrom(z::Zip, n) = Zip(reversefrom(z.a, n), reversefrom(z.z, n))
 
reverse(z::Zip1) = Zip1(reverse(z.a))
reverse(z::Union{Zip,Zip2}) = reversefrom(z, length(z))

but to be useful, reversefrom(it, n::Integer) needs to defined for some more iterators, e.g.
reversefrom(r::UnitRange, n::Integer) = reverse(first(r):min(last(r),first(r)+n-1)) = reverse(first(r):min(last(r),first(r)+n-1))
or alternatively reverse for some take iterators (this can be done with drop for finite iterators)
[edit:] needs to be implemented.

[mschauer]

@stevengj It is hard to think of an iterator one can reverse efficiently from its last element, but not from an earlier element.

[stevengj]

@mschauer, the problem is precisely that you can't do this from the existing iteration protocol functions, so each iterator would have to implement more functions for it to work.

reverse(take(it, n)) doesn't help because we don't have Reverse{Take} iterators implemented. You'd just get method errors.

[mschauer]

Yes, I know that Reverse{Take} or reversefrom(it, n::Integer) needs to be implemented for this. What I do not know is if a PR is welcome or not. [Edited.]

[stevengj]

I think it adds too much complexity to require every iterator to support reversefrom in order to work for this odd corner case of reversing the zip of unequal-length iterators. Better to just throw an error in that case.

[mschauer]

Hm, it is not needed to require every iterator to support reversefrom. In fact

reversefrom(it, n) = n==length(it) ? reverse(it) : throw(ArgumentError("...")) # fixme: catch infinite iterators in a nice way

implements a fallback which also just throws an error if a special reversefrom is not implemented strictly extending the alternative of throwing an error at the cost of complexity of some ten lines.

[stevengj]

For this functionality to actually be useful, a fair number of iterators will need to implement new methods, which is a lot of code devoted to a corner case of questionable utility.

[mschauer]

Yes, I wrote above "but to be useful, reversefrom(it, n::Integer) needs to defined for some more iterators". I thought of cycle, repeated and ranges (countfrom is mostly covered by the reversibility of enumerate).

[mschauer]

If anybody else is interested in having this, they can create a PR from https://github.com/JuliaLang/julia/compare/master...mschauer:reverse?expand=1

[jariji]

Given

  reverse(v [, start=firstindex(v) [, stop=lastindex(v) ]] )


  Return a copy of v reversed from start to stop. See also Iterators.reverse for reverse-order iteration without
  making a copy, and in-place reverse!.

I think the current behavior is better classified as a bug. Throwing an error is probably a bug too, but at least it's not the wrong answer.

[adienes]

#50435