# RFC: jumping in iterators

**URL:** <https://discourse.julialang.org/t/rfc-jumping-in-iterators/15235>\
**Category:** Internals & Design\
**Tags:** proposal\
**Created:** [September 20, 2018, 2:21pm UTC](https://discourse.julialang.org/t/rfc-jumping-in-iterators/15235 "2018-09-20T14:21:17Z")\
**Posts on this page:** 12\
**Page:** 1

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [September 20, 2018, 2:21pm UTC](https://discourse.julialang.org/t/rfc-jumping-in-iterators/15235/1 "2018-09-20T14:21:17Z")

</div>

Some iterators

1. involve a computation besides updating the state, and/or
2. would allow to efficiently skip elements.

Eg consider the MWE

```julia
using IterTools
itr0 = 1:10
itr1 = imap(x -> (println("costly"); x), itr0)
itr2 = takenth(itr1, 5)

```

where

```julia
julia> collect(itr2)
costly
costly
costly
costly
costly
costly
costly
costly
costly
costly
2-element Array{Int64,1}:
  5
 10

```

and `takenth` could take advantage of such an interface.

An extra argument to `iterate` could allow this. The definition

```julia
function iterate(itr, state, jump)
    for _ in Base.OneTo(jump)
        y = iterate(itr, state)
        y ≡ nothing && return nothing
        state = y[2]
    end
    iterate(itr, state)
end

```

would provide a fallback, but iterators could implement special, optimized versions.

---

<div class="post-metadata">

**Author:** ![StefanKarpinski](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stefankarpinski/32/24_2.png) [@StefanKarpinski](https://discourse.julialang.org/u/StefanKarpinski)\
**Post date:** [September 20, 2018, 11:34pm UTC](https://discourse.julialang.org/t/rfc-jumping-in-iterators/15235/2 "2018-09-20T23:34:37Z")

</div>

Cool idea and it would be backwards compatible!

---

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [September 21, 2018, 5:02am UTC](https://discourse.julialang.org/t/rfc-jumping-in-iterators/15235/3 "2018-09-21T05:02:54Z")

</div>

Thanks for the feedback. I will experiment with it a bit, then make a PR.

---

<div class="post-metadata">

**Author:** ![mschauer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mschauer/32/13946_2.png) [@mschauer](https://discourse.julialang.org/u/mschauer)\
**Post date:** [September 21, 2018, 6:56am UTC](https://discourse.julialang.org/t/rfc-jumping-in-iterators/15235/4 "2018-09-21T06:56:48Z")

</div>

Make `jump` default to 1, so make it a `step`, with one step forward `step 1` the default. Negative steps could constitute reverse iteration protocol for cases where this is interesting.

---

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [September 21, 2018, 7:31am UTC](https://discourse.julialang.org/t/rfc-jumping-in-iterators/15235/5 "2018-09-21T07:31:32Z")

</div>

Reverse iteration would require a separate protocol/interface which has no fallback like `jump` above.

Regarding `jump` vs `step`: the way I think about the semantics is that iteration always moves the iterator forward, yielding a state, and it would `jump` that many _extra_ steps before that.

---

<div class="post-metadata">

**Author:** ![laborg](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/laborg/32/5474_2.png) [@laborg](https://discourse.julialang.org/u/laborg)\
**Post date:** [September 21, 2018, 7:42am UTC](https://discourse.julialang.org/t/rfc-jumping-in-iterators/15235/6 "2018-09-21T07:42:03Z")

</div>

How about _skip_?

---

<div class="post-metadata">

**Author:** ![mschauer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mschauer/32/13946_2.png) [@mschauer](https://discourse.julialang.org/u/mschauer)\
**Post date:** [September 21, 2018, 8:02am UTC](https://discourse.julialang.org/t/rfc-jumping-in-iterators/15235/7 "2018-09-21T08:02:58Z")

</div>

I think it is exactly the point to provide three argument `iterate` implementations for some iterators which do `jumps` more efficiently than the fallback. Then for some of those iterators reverse iteration just naturally falls out of the implementation:

```julia
function Base.iterate(r::OrdinalRange{T}, i, k) where {T}
    next = convert(T, i + k*step(r))
    (next in r) || return nothing
    (next, next)
end

r = 1:10
u = iterate(r)
steps = 2
while u != nothing # two steps ahead, one back...
    i, s = u
    println(i)
    u = iterate(r, s, steps)
    steps = steps == 2 ? -1 : 2
end

```

```julia
1 3 2 4 3 5 4 6 5 7 6 8 7 9 8 10 9

```

If not, calling three argument `iterate` with negative `step` argument can just error.

---

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [September 21, 2018, 8:23am UTC](https://discourse.julialang.org/t/rfc-jumping-in-iterators/15235/8 "2018-09-21T08:23:33Z")

</div>

My point was that you cannot just implement reverse iteration (in general) by building on existing `iterate` implementations.

That said, I think this is orthogonal to the original proposal.

---

<div class="post-metadata">

**Author:** ![mschauer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mschauer/32/13946_2.png) [@mschauer](https://discourse.julialang.org/u/mschauer)\
**Post date:** [September 21, 2018, 8:51am UTC](https://discourse.julialang.org/t/rfc-jumping-in-iterators/15235/9 "2018-09-21T08:51:10Z")

</div>

Well, it will be orthogonal if you make `jump` a `step` as I suggested, that is why I suggested it.

---

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [September 21, 2018, 9:06am UTC](https://discourse.julialang.org/t/rfc-jumping-in-iterators/15235/10 "2018-09-21T09:06:53Z")

</div>

Sorry, I reread your example and I still don’t see how it would work for iterators which are not implemented like those for `<: AbstractVector`, ie with a linear index you can manipulate to go back.

---

<div class="post-metadata">

**Author:** ![mschauer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mschauer/32/13946_2.png) [@mschauer](https://discourse.julialang.org/u/mschauer)\
**Post date:** [September 21, 2018, 10:47am UTC](https://discourse.julialang.org/t/rfc-jumping-in-iterators/15235/11 "2018-09-21T10:47:14Z")

</div>

No, no, I am sorry, I am really only thinking of those iterators which allow this naturally, say `<: AbstractArray`, `Repeated`, `Cycle`, `Count` and possibly extensions like an iterator `Remember(iter)` which keeps a certain number of last iterates and would allow to go back a limited number of steps, in analogy of what `ungetchar` does for a stream. By choosing `iterate(iter, state; steps)` you would keep that door open without committing to anything. PS: I’d suggest a named argument for clarity.

---

<div class="post-metadata">

**Author:** ![mschauer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mschauer/32/13946_2.png) [@mschauer](https://discourse.julialang.org/u/mschauer)\
**Post date:** [November 15, 2018, 10:18am UTC](https://discourse.julialang.org/t/rfc-jumping-in-iterators/15235/12 "2018-11-15T10:18:04Z")

</div>

I made iterator stepping one of the primitives of the dynamic iterator protocol I was working on.

[https://github.com/mschauer/DynamicIterators.jl](https://github.com/mschauer/DynamicIterators.jl)

The API is a bit different from what discussed here, but only because stepping is only one of the many ways to modify the iteration an iterator should do.

```julia
value, state = dyniterate(iter, Steps(state, i))

```

To overwrite the fallback a dynamic iterator provides a method dispatching on the `Steps` state wrapper.

```julia
julia> state = 5
5

julia> i, state = dyniterate(1:10, Steps(state, 3))
(8, 8)

```