Reverse iteration in Julia

Question

Yesterday I had occasion to want to iterate over a collection in reverse order. I found the reverse function, but this does not return an iterator, but actually creates a reversed collection.

Apparently, there used to be a Reverse iterator, which was removed several years ago. I can also find reference to something (a type?) called Order.Reverse, but that does not seem to apply to my question.

The Iterators.jl package has many interesting iteration patterns, but apparently not reverse iteration.

I can of course use the reverse function, and in some cases, for example reverse(eachindex(c)) which returnes a reversed iterator, but I would prefer a general reverse iterator.

Is there such a thing?

Answer 1

UPDATE FOR JULIA 1.0+

You can now use Iterators.reverse to reverse a limited subset of types. For example:

julia> Iterators.reverse(1:10)
10:-1:1

julia> Iterators.reverse(CartesianIndices(zeros(2,3))) |> collect
2×3 Array{CartesianIndex{2},2}:
 CartesianIndex(2, 3)  CartesianIndex(2, 2)  CartesianIndex(2, 1)
 CartesianIndex(1, 3)  CartesianIndex(1, 2)  CartesianIndex(1, 1)

julia> Iterators.Reverse([1,1,2,3,5]) |> collect
5-element Array{Int64,1}:
 5
 3
 2
 1
 1

# But not all iterables support it (and new iterables don't support it by default):
julia> Iterators.reverse(Set(1:2)) |> collect
ERROR: MethodError: no method matching iterate(::Base.Iterators.Reverse{Set{Int64}})

Note that this only works for types that have specifically defined reverse iteration. That is, they have specifically defined Base.iterate(::Iterators.Reverse{T}, ...) where T is the custom type. So it's not fully general purpose (for the reasons documented below), but it does work for any type that supports it.

---

ORIGINAL ANSWER

Jeff's comment when he removed the reverse iterator three years ago (in the issue you linked) is just as relevant today:

I am highly in favor of deleting this since it simply does not work. Unlike everything else in iterator.jl it depends on indexing, not iteration, and doesn't even work on everything that's indexable (for example UTF8String). I hate having landmines like this in Base.

At the most basic level, iterators only know how to do three things: start iteration, get the next element, and check if the iteration is done. In order to create an iterator that doesn't allocate using these primitives, you'd need an O(n^2) algorithm: walk through the whole iterator, counting as you go, until you find the last element. Then walk the iterator again, only this time stopping at the penultimate element. Sure it doesn't allocate, but it'll be way slower than just collecting the iterator into an array and then indexing backwards. And it'll be completely broken for one-shot iterators (like eachline). So it is simply not possible to create an efficient general reverse iterator.

Note that reverse(eachindex(c)) does not work in general:

julia> reverse(eachindex(sprand(5,5,.2)))
ERROR: MethodError: no method matching reverse(::CartesianRange{CartesianIndex{2}})

One alternative that will still work with offset arrays is reverse(linearindices(c)).