Define iterator

New to Julia
1

Hi all,

I am following the manual to learn to define a customized iterator, but couldn’t figure out what I did wrong.

If I use for loop, it gave error “MethodError: no method matching length”.
If I use while loop, it gave error “MethodError: no method matching iterate(::Nothing)”.

Could someone please point me where the problem is?
Thanks!

struct Farey_Sequence
    N :: Int
    descending :: Bool
    Farey_Sequence(n; descending = false) = new(n, descending)
end

function Base.iterate(f :: Farey_Sequence) :: Union{Nothing, Tuple{Rational{Int}, NTuple{4, Int}}}
    if f.descending
        a, b, c, d = 1, 1, f.N - 1, f.N
    else
        a, b, c, d = 0, 1, 1, f.N
    end
    a // b, (a, b, c, d)
end

function Base.iterate(f :: Farey_Sequence, state :: NTuple{4, Int}) :: Union{Nothing, Tuple{Rational{Int}, NTuple{4, Int}}}
    a, b, c, d = state
    if (c <= f.N && !f.descending) || (a > 0 && f.descending)
        k = (f.N + b) ÷ d
        (a, b, c, d) = (c, d, k * c - a, k * d - b)
        return a // b, (a, b, c, d)
    else
        return nothing
    end
end
2

I can use your iterator in a for loop without problem:

julia> for i = Farey_Sequence(5,descending=false)
           println(i)
       end
0//1
1//5
1//4
1//3
2//5
1//2
3//5
2//3
3//4
4//5
1//1

In order to receive better help, you might want to show how you use the iterator in for/while loops to get those errors. But the problem is probably the following:

There is a trait Base.IteratorSize for determining whether an iterator has a known length/shape or not. The default is Base.HasLength(), so the for loop expects that the length (i.e., the number of values the iterator produces) is known and that Base.length(::Farey_Sequence) is implemented.

You can either implement Base.length(::Farey_Sequence) or set the Base.IteratorSize trait to Base.SizeUnknown() (this means that it is not known in advance how many values the iterator will produce):

Base.IteratorSize(::Type{Farey_Sequence}) = Base.SizeUnknown()
4 Likes
3

Thank you! I stand corrected. It indeed works in loop.

It gave the error in array comprehension.
[a for a in Farey_Sequence(5,descending=false)]
ERROR: MethodError: no method matching length(::Farey_Sequence)

guess I have to define length function in order to use comprehension?

4

actually with this, array comprehension is working as well! thank you!

5

I believe comprehensions check if length exists to try to pre-allocate and speed-up the process.

6

The output type assertion doesn’t really do anything, and is so unreadable it’s not very enlightening for the reader either (I had to look at the actual return statement to help me parse it.)

It also looks wrong, since iterate(::Farey_Sequence) will, as far as I can tell, never return nothing anyway (sorry about the double negation…)

7

I agree that specifying the return type isn’t very useful. I added that in the hope to get rid of the error I had. Apparently, it was due to the problem answered by sostock. I have since removed the return type.

It will indeed return nothing when farey sequence reaches the end, so I think I got that right.

8

below is the new implementation, which I think served my need at the moment. I have removed descending from struct, but added reverse iterator instead. welcome any comments!

struct Farey_Sequence
    N :: Int
end

function Base.iterate(f :: Farey_Sequence)
    a, b, c, d = 0, 1, 1, f.N
    a // b, (a, b, c, d)
end
function Base.iterate(f :: Iterators.Reverse{Farey_Sequence})
    a, b, c, d = 1, 1, f.itr.N - 1, f.itr.N
    a // b, (a, b, c, d)
end

function next_farey(state, n, descending)
    a, b, c, d = state
    if (c <= n && !descending) || (a > 0 && descending)
        k = (n + b) ÷ d
        (a, b, c, d) = (c, d, k * c - a, k * d - b)
        return a // b, (a, b, c, d)
    else
        return nothing
    end
end
function Base.iterate(f :: Farey_Sequence, state :: NTuple{4, Int})
    next_farey(state, f.N, false)
end
function Base.iterate(f :: Iterators.Reverse{Farey_Sequence}, state :: NTuple{4, Int})
    next_farey(state, f.itr.N, true)
end

Base.IteratorSize(::Type{Farey_Sequence}) = Base.SizeUnknown()
9

I don’t think so. The second method, iterate(::Farey_Sequence, ::NTuple{4, Int}) can return nothing, but not iterate(::Farey_Sequence).

10

I saw your point now. I thought Julia needs two iterate functions have the same return type. thanks for pointing that out.

11

For better performance, you should also implement eltype for your Iterator, i.e.,

Base.eltype(::Type{Farey_Sequence}) = Rational{Int}

Without that method, the eltype defaults to Any, which means that, for example, collect will return a Vector{Any} instead of a Vector{Rational{Int}}

julia> collect(Farey_Sequence(1))
2-element Vector{Any}:
 0//1
 1//1
1 Like
12

great point! thanks!