RFC: jumping in iterators

Internals & Design
1

Some iterators

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

Eg consider the MWE

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

where

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

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.

9 Likes
2

Cool idea and it would be backwards compatible!

3 Likes
3

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

4

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.

5

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.

6

How about skip?

1 Like
7

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:

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

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.

8

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.

9

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

10

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.

11

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.

12

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

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.

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

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

julia> state = 5
5

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