# \`collect\` iterator in reverse

**URL:** <https://discourse.julialang.org/t/collect-iterator-in-reverse/64225>\
**Category:** General Usage\
**Created:** [July 7, 2021, 5:06pm UTC](https://discourse.julialang.org/t/collect-iterator-in-reverse/64225 "2021-07-07T17:06:21Z")\
**Posts on this page:** 12\
**Page:** 1

<div class="post-metadata">

**Author:** ![goretkin](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/goretkin/32/167_2.png) [@goretkin](https://discourse.julialang.org/u/goretkin)\
**Post date:** [July 7, 2021, 5:06pm UTC](https://discourse.julialang.org/t/collect-iterator-in-reverse/64225/1 "2021-07-07T17:06:21Z")

</div>

Is there a generic function for collecting an iterator in reverse? I’m looking for a more efficient version of the following:

```julia
itr = (i for i = 1:10) # for example
vec = reverse(collect(itr))

```

I don’t think the solution is to add a method `reverse(itr)`.  
(Though if something like [GitHub - goretkin/FixArgs.jl](https://github.com/goretkin/FixArgs.jl) existed in Base, it might be reasonable to add a method to `reverse` such that `reverse(@xquote collect(itr))` worked.)

---

<div class="post-metadata">

**Author:** ![lmiq](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lmiq/32/18314_2.png) [@lmiq](https://discourse.julialang.org/u/lmiq)\
**Post date:** [July 7, 2021, 5:17pm UTC](https://discourse.julialang.org/t/collect-iterator-in-reverse/64225/2 "2021-07-07T17:17:40Z")

</div>

Maybe?

```julia
collect(Iterators.reverse(itr))

```

---

<div class="post-metadata">

**Author:** ![cjdoris](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/cjdoris/32/213133_2.png) [@cjdoris](https://discourse.julialang.org/u/cjdoris)\
**Post date:** [July 7, 2021, 5:45pm UTC](https://discourse.julialang.org/t/collect-iterator-in-reverse/64225/3 "2021-07-07T17:45:36Z")

</div>

`reverse!(collect(itr))`?

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [July 7, 2021, 6:02pm UTC](https://discourse.julialang.org/t/collect-iterator-in-reverse/64225/4 "2021-07-07T18:02:32Z")

</div>

> [@goretkin](#):
>
> I don’t think the solution is to add a method `reverse(itr)` .

See the section on [reverse-order iteration](https://docs.julialang.org/en/v1/manual/interfaces/#man-interface-iteration) in the iteration manual — the `Iterators.reverse(itr)` function is generally the way to do reverse iteration, and the manual also describes how to support reverse iteration for custom iterator types.

---

<div class="post-metadata">

**Author:** ![goretkin](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/goretkin/32/167_2.png) [@goretkin](https://discourse.julialang.org/u/goretkin)\
**Post date:** [July 7, 2021, 6:31pm UTC](https://discourse.julialang.org/t/collect-iterator-in-reverse/64225/5 "2021-07-07T18:31:18Z")

</div>

> [@stevengj](#):
>
> See the section on [reverse-order iteration](https://docs.julialang.org/en/v1/manual/interfaces/#man-interface-iteration) in the iteration manual

Thanks. It’s not that I want to iterate in reverse order, it’s that I want to _collect_ in reverse order. I wanted a solution that did not require any more from the iterator interface than `collect` does.

e.g.

```julia
julia> collect(Iterators.reverse(Iterators.TakeWhile(<(10), 1:10)))
ERROR: MethodError: no method matching iterate(::Base.Iterators.Reverse{Base.Iterators.TakeWhile{UnitRange{Int64}, Base.Fix2{typeof(<), Int64}}})

```

but I am not sure how it would work, now that I think about it, if `Base.IteratorSize` is not `Base.HasLength`. If it is `Base.SizeUnknown`, the reverse collect method could use `pushfirst!`, but that will then take quadratic time.

> [@cjdoris](#):
>
> `reverse!(collect(itr))` ?

Thanks, that is more efficient than `reverse(collect(itr))`, but still does unnecessary operations compared to just collecting in reverse for the situation where `IteratorSize` is `HasLength`.

If it helps, in my case, I have a singly-linked list (really a tree where a node points to its parent but not its children), so there is only one possible iteration order (from node to root). Each node also keeps track of its level, so this iterator `HasLength`.

In summary, I want to iterate “forwards” and _collect_ in reverse, which has has a straightforward implementation in the case that the iterator `HasLength`.

---

<div class="post-metadata">

**Author:** ![goretkin](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/goretkin/32/167_2.png) [@goretkin](https://discourse.julialang.org/u/goretkin)\
**Post date:** [July 7, 2021, 6:40pm UTC](https://discourse.julialang.org/t/collect-iterator-in-reverse/64225/6 "2021-07-07T18:40:06Z")

</div>

> [@goretkin](#):
>
> but I am not sure how it would work, now that I think about it, if `Base.IteratorSize` is not `Base.HasLength` . If it is `Base.SizeUnknown` , the reverse collect method could use `pushfirst!` , but that will then take quadratic time.

There is likely a ~ O(n\log n) solution where we assign into a `Vector` in reverse order, and resize ~ exponentially as needed, and return a view into the array starting at the last element that was assigned. (Sort of, but not really, reminiscent of [Okazaki fragments - Wikipedia](https://en.wikipedia.org/wiki/Okazaki_fragments) in DNA)

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [July 7, 2021, 6:49pm UTC](https://discourse.julialang.org/t/collect-iterator-in-reverse/64225/7 "2021-07-07T18:49:36Z")

</div>

> [@goretkin](#):
>
> There is likely a ~ O(n\log n) solution where we assign into a `Vector` in reverse order, and resize

Actually this is O(n), and can be accomplished simply by

```julia
a = Vector{eltype(itr)}()
for x in itr
    pushfirst!(a, x)
end

```

in Julia. But it’s obviously better if you know the length. e.g.

```julia
collectreverse(itr) = collectreverse(itr, Base.IteratorSize(itr), Base.IteratorEltype(itr))

function collectreverse(itr, ::Union{Base.HasLength,Base.HasShape}, ::Base.HasEltype)
   a = Vector{eltype(itr)}(undef, length(itr))
   offset = length(a)+1
   for (i,x) in enumerate(itr)
      a[offset - i] = x
   end
   return a
end

function collectreverse(itr, ::Any, ::Base.HasEltype)
   a = Vector{eltype(itr)}()
   for x in itr
      pushfirst!(a, x)
   end
   return a
end

collectreverse(itr, ::Any, ::Any) = reverse!(collect(itr))

```

That being said, I doubt the performance improvement compared to `reverse!(collect(itr))` will matter in most applications.

---

<div class="post-metadata">

**Author:** ![goretkin](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/goretkin/32/167_2.png) [@goretkin](https://discourse.julialang.org/u/goretkin)\
**Post date:** [July 7, 2021, 7:06pm UTC](https://discourse.julialang.org/t/collect-iterator-in-reverse/64225/8 "2021-07-07T19:06:34Z")

</div>

> [@stevengj](#):
>
> Actually this is O(n) O(n)O(n) , and can be accomplished simply by

I see, I had assumed `pushfirst!(vec, elt)` was always linear in `length(vec)`, but I see now that its written in terms of `_growbeg!`.

So, my take-away is that there isn’t an existing name in `Base` for this generic function for collecting in reverse, and perhaps there shouldn’t be because `reverse!(collect(itr))` is sufficient in most applications.

By the way, it seems like you could do just:

```julia
function collectreverse(itr, ::Any, ::Base.HasEltype)
   a = Vector{eltype(itr)}()
   prepend!!(a, itr) # [EDIT]
   return a
end

```

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [July 7, 2021, 8:59pm UTC](https://discourse.julialang.org/t/collect-iterator-in-reverse/64225/9 "2021-07-07T20:59:05Z")

</div>

> [@goretkin](#):
>
> `pushfirst!(a, itr)`

This will push the iterator object as the first element, which is not what you want. For example:

```julia
julia> pushfirst!(Any[], 1:10)
1-element Vector{Any}:
 1:10

```

---

<div class="post-metadata">

**Author:** ![goretkin](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/goretkin/32/167_2.png) [@goretkin](https://discourse.julialang.org/u/goretkin)\
**Post date:** [July 7, 2021, 10:04pm UTC](https://discourse.julialang.org/t/collect-iterator-in-reverse/64225/10 "2021-07-07T22:04:30Z")

</div>

Ah, yes, of course. I did mean only `prepend!(vec, itr)`. I got tripped up looking at

> <https://github.com/JuliaLang/julia/blob/480ff81e78b2d7b139ec34f0f2d70cfdc51895d2/base/array.jl#L1090>

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [July 7, 2021, 10:52pm UTC](https://discourse.julialang.org/t/collect-iterator-in-reverse/64225/11 "2021-07-07T22:52:16Z")

</div>

> [@goretkin](#):
>
> I did mean only `prepend!(vec, itr)` .

That won’t reverse the order of `itr`.

---

<div class="post-metadata">

**Author:** ![goretkin](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/goretkin/32/167_2.png) [@goretkin](https://discourse.julialang.org/u/goretkin)\
**Post date:** [July 7, 2021, 11:15pm UTC](https://discourse.julialang.org/t/collect-iterator-in-reverse/64225/12 "2021-07-07T23:15:07Z")

</div>

sigh, indeed! Thanks for catching that.