Define iterator

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
``````

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

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?

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

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

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…)

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.

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()
``````

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

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

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

great point! thanks!