A Julia iterator error

Question

I am looking at an iterator example from http://lostella.github.io/blog/2018/07/25/iterative-methods-done-right and have a question. The following works and produces Fibonacci numbers up to 13:

iterate(f::FibonacciIterable) = f.s0, (f.s0, f.s1)
iterate(f::FibonacciIterable, state) = state[2], (state[2], state[1] + state[2])

for f in FibonacciIterable(0, 1)
    print("$f ")
    if f > 10 println(); break end
end

I am trying to replace the two iterate functions with one, configured with a default value:

iterate(f::FibonacciIterable, state = (f.s0, (f.s0, f.s1)) ) = (state[2], state[1] + state[2])

Running this code produces:

ERROR: LoadError: MethodError: no method matching +(::Int64, ::Tuple{Int64,Int64})
Closest candidates are:
  +(::Any, ::Any, !Matched::Any, !Matched::Any...) at operators.jl:502
  +(::T<:Union{Int128, Int16, Int32, Int64, Int8, UInt128, UInt16, UInt32, UInt64, UInt8}, !Matched::T<:Union{Int128, Int16, Int32, Int64, Int8, UInt128, UInt16, UInt32, UInt64, UInt8}) where T<:Union{Int128, Int16, Int32, Int64, Int8, UInt128, UInt16, UInt32, UInt64, UInt8} at int.jl:53
  +(::Union{Int16, Int32, Int64, Int8}, !Matched::BigInt) at gmp.jl:456        

Note: using Julia 1.0

Commenting here on answer by Bogumił Kamiński for formating and extra space

Thank you Bogumił - but I am still having a hard time bulding a mental model on how this works. First of all the following also produces the expected output:

iterate(iter::FibonacciIterable, state=(iter.s1, iter.s0)) = state[2], (state[2], sum(state))

The documentation says:

iterate(iter [, state]) -> Union{Nothing, Tuple{Any, Any}}

Advance the iterator to obtain the next element. If no elements remain, nothing should be returned. 
Otherwise, a 2-tuple of the next element and the new iteration state should be returned.

The way I read this, the first call to this version of iterate will return iter.s1 and set up the next state to be iter.s0. So the output from the first call should be 1 and the next invocation of iterate should fail as there is no such thing as state[2]. Obviously this is not what is happening as the first value is 0 and the calculation proceeds without errors. Can you point out where my logic goes wrong?

Comment 2

Right - that helped:

julia> iterate(FibonacciIterable(BigInt(2), BigInt(3)))
(2, (2, 3))

I assumed that the parameter named state and the return type of iterate (which I thought of as the next state) are of the same type.

As you pointed out that is not the case as the type of state parameter is Tuple{I,I} but the type of the return value is Tuple{I, Tuple{I,I}} (actually Union{Nothing, Tuple{I, Tuple{I,I}}} but never mind that) where the "inner" tuple is the state.

Answer 1

You have to pass only state, so a Tuple{I, I} where {I} not Tuple{I, Tuple{I, I}} where {I}. In this case you also have to go back one step in Fibonacci sequence to get a correct first step (i.e. value stored in iter.s0).

Therefore the way you can define your iterate function is:

iterate(iter::FibonacciIterable, state=(iter.s1-iter.s0, iter.s0)) =
    state[2], (state[2], sum(state))

And now all works as expected:

julia> for F in FibonacciIterable(BigInt(0), BigInt(1))
           println(F)
           F > 10 && break
       end
0
1
1
2
3
5
8
13

EDIT: Referring to your additional question.

If you change the definition to:

iterate(iter::FibonacciIterable, state=(iter.s1, iter.s0)) = state[2],
        (state[2], sum(state))

the iteration will be incorrect. Consider this example when using your definition:

julia> for F in FibonacciIterable(BigInt(2), BigInt(3))
                  println(F)
                             F > 10 && break
                                    end
2
5
7
12

And we clearly see that something goes wrong.

In order to understand this case you have to build a mental model what is iterator state in our exercise. It is a tuple of the following form (fibonacci(n), fibonacci(n+1) i.e. first goes element n and the second is element n+1.

Now I am switching to my definition:

iterate(iter::FibonacciIterable, state=(iter.s1-iter.s0, iter.s0)) =
        state[2], (state[2], sum(state))

Let us check what happens when we run those lines:

julia> iterate(FibonacciIterable(BigInt(2), BigInt(3)))
(2, (2, 3))

julia> iterate(FibonacciIterable(BigInt(2), BigInt(3)), (2, 3))
(3, (3, 5))

julia> iterate(FibonacciIterable(BigInt(2), BigInt(3)), (3, 5))
(5, (5, 8))

In the first line iterate tells you that the first element is 2 and state to use in the next iteration is (2,3). So in the second line we use this state to get the next iteration: value 3 and next state (3,5). We go on using this new state to obtain the next value 5 and next state (5,8).

I guess in this example the confusion is that state is a tuple but also what iterate returns is a tuple. Probably a more didactic approach could be to define a new iteration state type:

struct FiboState{I}
    a::I
    b::I
end

and the following definition of iterate:

iterate(iter::FibonacciIterable, state=FiboState(iter.s1-iter.s0, iter.s0)) =
        state.b, FiboState(state.b, state.a+state.b)

and now we clearly see what is going on:

julia> iterate(FibonacciIterable(BigInt(2), BigInt(3)))
(2, FiboState{BigInt}(2, 3))

julia> iterate(FibonacciIterable(BigInt(2), BigInt(3)), FiboState{BigInt}(2, 3))
(3, FiboState{BigInt}(3, 5))

julia> iterate(FibonacciIterable(BigInt(2), BigInt(3)), FiboState{BigInt}(3, 5))
(5, FiboState{BigInt}(5, 8))

I hope this helps.