julian way to do python's yield (and yield from)

Question

What is julian way to do yield (and yield from) as python do?

Edit: I will try to add small example in python.

Think 4x4 chess board. Find every N moves long path chess king could do. Don't waste memory -> make generator of every path.

if we sign every position with numbers:

0  1  2  3
4  5  6  7
8  9  10 11
12 13 14 16

point 0 has 3 neighbors (1, 4, 5). We could find table for every neighbors for every point:

NEIG = [[1, 4, 5], [0, 2, 4, 5, 6], [1, 3, 5, 6, 7], [2, 6, 7], [0, 1, 5, 8, 9], [0, 1, 2, 4, 6, 8, 9, 10], [1, 2, 3, 5, 7, 9, 10, 11], [2, 3, 6, 10, 11], [4, 5, 9, 12, 13], [4, 5, 6, 8, 10, 12, 13, 14], [5, 6, 7, 9, 11, 13, 14, 15], [6, 7, 10, 14, 15], [8, 9, 13], [8, 9, 10, 12, 14], [9, 10, 11, 13, 15], [10, 11, 14]]

Recursive function (generator) which enlarge given path from list of points or from generator of (generator of ...) points:

def enlarge(path):
    if isinstance(path, list):
        for i in NEIG[path[-1]]:
            if i not in path:
                yield path[:] + [i]
    else:
        for i in path:
            yield from enlarge(i)

Function (generator) which give every path with given length

def paths(length):
    steps = ([i] for i in range(16))  # first steps on every point on board
    for _ in range(length-1):
        nsteps = enlarge(steps)
        steps = nsteps
    yield from steps

We could see that there is 905776 paths with length 10:

sum(1 for i in paths(10))
Out[89]: 905776

In ipython we could timeit:

%timeit sum(1 for i in paths(10))
1.21 s ± 15.1 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

My julia implementation is ugly and much more complicated. And it seems to be slower.

Answer 1

Check out ResumableFunctions.jl

from the README

using ResumableFunctions

@resumable function fibonnaci(n::Int) :: Int
  a = 0
  b = 1
  for i in 1:n-1
    @yield a
    a, b = b, a+b
  end
  a
end

for fib in fibonnaci(10)
  println(fib)
end

Answer 2

You can use Julia Iterators.

struct Fibonacci
    last::Int64
end

function Base.iterate(fibo::Fibonacci)
    return 1, (1, 1, 2) # the first output, and the next iteration state
end

function Base.iterate(fibo::Fibonacci, state)
    i, a, b = state
    if i ≤ fibo.last
        return a, (i + 1, b, a + b) # the output, and the next iteration state
    end
end

You can then use it like this:

for i in Fibonacci(10)
    print(i, " ")
end

Which outputs:

1 1 2 3 5 8 13 21 34 55 89

This can result in excellent performance, but it is often a bit verbose, and it's also tricky to decide on what iteration state to use, and how to find the next element given that state. In your chess example, I would avoid this approach, but in other cases it can come in really handy.

Answer 3

You can use Channels:

function fibo(n)
    Channel() do ch
        a, b = 0, 1
        for _ in 1:n
            a, b = b, a + b
            put!(ch, a)
        end
    end
end

Use it like this:

for val in fibo(10)
    print(val, " ")
end

Which outputs:

1 1 2 3 5 8 13 21 34 55

To get the yield from behavior, you can just use a for loop. For example, to get the Fibonacci sequence r times:

function repeat_fibo(r, n)
    Channel() do ch
        for _ in 1:r
            for val in fibo(n)
                put!(ch, val)
            end
        end
    end
end

For more details, see the docs.

Note that the ResumableFunctions.jl library has some benchmarks showing that their solution is significantly faster than using Channels (see @gggg's answer). Perhaps Channel performance will improve in future Julia versions.

To get better Channel performance, you should set the channel's element type and the channel's size: for example, use Channel{Int64}(100) instead of Channel().

Here's a Julia implementation of your chess problem using Channels:

NEIG = [[1, 4, 5], [0, 2, 4, 5, 6], [1, 3, 5, 6, 7], [2, 6, 7], [0, 1, 5, 8, 9],
        [0, 1, 2, 4, 6, 8, 9, 10], [1, 2, 3, 5, 7, 9, 10, 11], [2, 3, 6, 10, 11],
        [4, 5, 9, 12, 13], [4, 5, 6, 8, 10, 12, 13, 14],
        [5, 6, 7, 9, 11, 13, 14, 15], [6, 7, 10, 14, 15], [8, 9, 13],
        [8, 9, 10, 12, 14], [9, 10, 11, 13, 15], [10, 11, 14]]

function paths(start, length)
    Channel{Vector{Int64}}(100) do ch
        if length == 1
            put!(ch, [start])
        else
            for path in paths(start, length - 1)
                for next_step in NEIG[path[end] + 1]
                    next_step in path || put!(ch, [path; next_step])
                end
            end
        end
    end
end

function paths(length)
    Channel{Vector{Int64}}(100) do ch
        for start in 0:15
            for path in paths(start, length)
                put!(ch, path)
            end
        end
    end
end

You can count all the paths of length 10 much like in Python:

sum(1 for _ in paths(10))

You can also time it:

@time sum(1 for _ in paths(10))

On my machine this takes about 4 seconds. There are probably ways to optimize this further, but this does show that Channel performance still has some room for improvement.