Explain generators

New to Julia
,
1

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 @yield or @task?
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
2

The for loop will try to use the iteration interface.

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

3

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
4

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?

5

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
6

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.

7

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.

1 Like
8

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.

for elem in doublylinkedlist ...
for elem in backwards(doublylinkedlist) ...

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.

9

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

10

here some element of “theory” on the subject.

11

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
12

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