# Explain generators

I am trying to understand how to implement a simple generator so that I can traverse my graphs in different ways. It boils down to the example below. In Lua - which I come from - it works without any ado, but in Julia it has to be written as, well into what?

I saw there is a type Channel, is that the way to go?
Or is best practice to rewrite it as Base.iterator?
Or Base.start/next/done instead of syntactic scoping?

So, what simple best practice here?

Sorry, but I am a newbie here and when I google generators I get a gazillion hits on prebuilt generators but not what I want. I want a for loop to simply run my generator.

x = [1,3,2,4,9,8,7,6,5]

function godd(x)
k = 1
return function()
while k <= length(x)
v = x[k]
k += 1
if v % 2 == 1
return k - 1, v
end
end
return nothing
end
end

for (k, v) in godd(x)
println(k, "\t", v)
end

The for loop will try to use the iteration interface.

https://docs.julialang.org/en/v1/manual/interfaces/#man-interface-iteration

The way I would write this idiomatically is as follows.

julia> f = Iterators.filter(pairs(x)) do (k,v)
v % 2 == 1
end;

julia> for (k,v) in f
println(k, "\t", v)
end
1       1
2       3
5       9
7       7
9       5

A more direct implementation with some similarities to your original code would be as follows.

julia> struct Foo{V}
x::V
end

julia> function Base.iterate(f::Foo, k = 1)
while k <= length(f.x)
v = f.x[k]
k += 1
if v % 2 == 1
return k - 1 => v, k
end
end
return nothing
end

julia> f = Foo(x)
Foo{Vector{Int64}}([1, 3, 2, 4, 9, 8, 7, 6, 5])

julia> for (k,v) in f
println(k, "\t", v)
end
1       1
2       3
5       9
7       7
9       5
1 Like

As you saw, there are many options, differing mainly in terms of the performance they offer vs the difficulty of development.

Could you tell us more about your use case? Is there a performance requirement for the iterator itself?

No performance. Maximum simplicity. Think about a Directed Acyclic Word Graph or som other complicated monster. There are several ways to print it out or mangle it.

But I thought about it as a convenience for a user of the module to use and print stuff (both for testing and production).

for node in all_unique_nodes(mymonster)
print(node)
end

for leaf in all_leaves(mymonster)
print(leaf)
end

for string in wordstrings(mymonster)
print(string)
end

EDIT: Or what a good way to traverse a tree? I was thinking of something like this

for node in mytraverse(mytree, option="depthfirst")
treat(node)
end

Thanks. Yes. That demands a type, but that is my case and this is this I will use.

EDIT: Well, that version still doesnâ€™t solve if I want to have two views of the same data type:

for n in nodes(X) ...
for s in strings(X) ...

EDIT2: or maybe it does if I introduce two different artificial types â€¦ OK I am on track and will solve it.

Iâ€™m not sure what your later questions are getting at, but as for the original one, there is also just regular simple generators, which you get from using ( ... ) syntax:

julia> mygen(x) = ((k, v) for (k, v) in pairs(x) if isodd(v))

julia> for (k, v) in mygen(x)
println(k, '\t', v)
end
1       1
2       3
5       9
7       7
9       5

Thereâ€™s also an iseven function, btw.

I am more interested in the case where x is really opaque. A monster struct. Letâ€™s take another example. We have a doubly linked list. Then one could traverse it. Or traverse it backwards.

I am more interested in the clean options for doing stuff like that on opaque things. Or learn that thatâ€™s not the way to think in Julia.

Ok, I was mainly addressing the original question, and since it was about generators, I found Base.Generator to be relevant.

here some element of â€śtheoryâ€ť on the subject.

Julia has a generator syntax that works as follows.

julia> f(x) = x^2
f (generic function with 1 method)

julia> gen = (f(x) for x in 1:5)
Base.Generator{UnitRange{Int64}, var"#1#2"}(var"#1#2"(), 1:5)

julia> for y in gen
println(y)
end
1
4
9
16
25

We can apply it to the original problem by adding a conditional statement.

julia> x = [1,3,2,4,9,8,7,6,5];

julia> gen = (k => v for (k,v) in pairs(x) if v % 2 == 1)
Base.Generator{Base.Iterators.Filter{var"#4#6", Base.Pairs{Int64, Int64, LinearIndices{1, Tuple{Base.OneTo{Int64}}}, Vector{Int64}}}, var"#3#5"}(var"#3#5"(), Base.Iterators.Filter{var"#4#6", Base.Pairs{Int64, Int64, LinearIndices{1, Tuple{Base.OneTo{Int64}}}, Vector{Int64}}}(var"#4#6"(), Base.Pairs(1 => 1, 2 => 3, 3 => 2, 4 => 4, 5 => 9, 6 => 8, 7 => 7, 8 => 6, 9 => 5)))

julia> for (k,v) in gen
println(k, "\t", v)
end
1	1
2	3
5	9
7	7
9	5

Essentially what we are doing is wrapping our desired function in a Base.Generator. Note that in general, Julia iterators are usually stateless. That is we can iterate through the generator multiple times.

julia> for (k,v) in gen
println(k, "\t", v)
end
1	1
2	3
5	9
7	7
9	5

julia> for (k,v) in gen
println(k, "\t", v)
end
1	1
2	3
5	9
7	7
9	5

julia> for (k,v) in gen
println(k, "\t", v)
end
1	1
2	3
5	9
7	7
9	5

julia> for (k,v) in gen
println(k, "\t", v)
end
1	1
2	3
5	9
7	7
9	5

Something helpful to you might be an adaptor from Lua to Julia.

julia> struct LuaGenerator{F}
f::F
end

julia> function Base.iterate(lg::LuaGenerator, _=nothing)
r = lg.f()
isnothing(r) ? nothing : (r, nothing)
end

julia> for (k,v) in LuaGenerator(godd(x))
println(k, "\t", v)
end
1	1
2	3
5	9
7	7
9	5

julia> for (k,v) in LuaGenerator(godd(x))
println(k, "\t", v)
end
1	1
2	3
5	9
7	7
9	5

julia> gen = LuaGenerator(godd(x))
LuaGenerator{var"#7#8"{Vector{Int64}}}(var"#7#8"{Vector{Int64}}([1, 3, 2, 4, 9, 8, 7, 6, 5], Core.Box(1)))

julia> for (k,v) in gen
println(k, "\t", v)
end
1	1
2	3
5	9
7	7
9	5

julia> for (k,v) in gen # this generator is stateful
println(k, "\t", v)
end
1 Like

One last thought. The function returned from godd(x) has a specific type itself. Thus, we can just define iterate directly for the function type.

julia> function Base.iterate(func::typeof(godd(x)), _=nothing)
r = func()
isnothing(r) ? nothing : (r, nothing)
end

julia> for (k,v) in godd(x)
println(k, "\t", v)
end
1	1
2	3
5	9
7	7
9	5

An alternative way to define iterate would be to use Base.return_types.

julia> function Base.iterate(func::only(Base.return_types(godd)), _=nothing)
r = func()
isnothing(r) ? nothing : (r, nothing)
end