Python generators equivalent?

After posting, I realised that my Elixir is ambiguous. It should be:

def solve(n, queens, r) when r == n, do: [{Enum.reverse(queens)}]
def solve(n, queens, r) do
0..(n-1)
|> Stream.filter(fn f → safe?(queens, {f, r}) end)
|> Stream.flat_map(fn f → solve(n, [{f, r} | queens], r+1) end)
end

One of the points of yield/generators in languages like ruby and python is to compute solutions incrementally instead of materializing the solution all at once thus allowing large or even infinite results to be computed. While Elixir doesn’t have yield, it achieves the same goal using Streams. Let me illustrate with a simple backtracking problem: n queens. An inefficient but concise formulation in ruby might go:

def solve(n, queens, rank, &block)
  if rank == n
    yield queens
  else
    n.times do |file|
      if safe?(queens, file, rank)
        queens << [file, rank]
        solve(n, queens, rank + 1, &block)
        queens.pop
      end
    end
  end
end

solve(ARGV[0].to_i, [], 0) { |solution| puts solution.inspect }

The use of yield allows us to use the same code to print one result, all results or count the number of results by supplying a different block to consume then result.

To accomplish the same goal in Elixir, you’d use Streams and flatmap, like so:

def solve(n, queens, r) when r == n, do: [{reverse(queens)}]
def solve(n, queens, r) do
  0..(n-1)
  |> filter(fn f -> safe?(queens, {f, r}) end)
  |> flat_map(fn f -> solve(n, [{f, r} | queens], r+1) end)
end

System.argv() |> at(0) |> String.to_integer |> solve([], 0) |> each(&IO.inspect/1)

Hope that helps.

Just a small note (not sure how on topic it is) about simulating functionality like this is to use a pipeline. I’ve used this approach a number of times in APIs.

step(1,2)
|> next
|> next
|> block(fn s → … end)
|> next

I don’t think it’s cheating. It’s taking advantage of the environment’s capabilities. Due to their threaded nature, languages like Python and JavaScript have to have dedicated language constructs for generators.

Joe Armstrong demonstrates building a Future with concurrency features, so if you need a generator - go ahead, use a process (even a GenServer) to build one. I still need to completely digest “To spawn, or not to spawn?” but I’m not advocating going on a spawn-fest; just sometimes it is good to leave the “sequential mindset” behind.

I was reading this thread. I didn’t knwo anything about python, so if you are in my situation this tutorial help me to understand yield in python very quickily.
I love elixir!

The concept of a Generator is not something that is unique to Python. Someone has taken the time in the past to write a version (using message passing) in Erlang (which was also translated to Elixir) on RosettaCode. Interestingly, as the Wikipedia Article mentions, Haskell’s lazily evaluated functions are also generators and as such the Stream that is built-in in Elixir indeed is also a generator.

Of course, in an immutable+pure language, you cannot call the same function with the same value over and over nextVal(mygen); nextVal(mygen); nextVal(mygen); and expect different results (unless you ‘cheat’ by using message passing). Indeed, when you’re working with for instance a Random Number Generator in Haskell, you have two options:

1. Call a function which takes a RNG, and returns a {randomNumber, newRNG} tuple. This is basically similar to what Enumerable does internally, which @benwilson512 talked about as well.
2. Specify that you want an infinite stream of random numbers, and take as many numbers from that stream as you need. In this case, the generator is ‘consumed’; you’ve turned in an infinite stream of numbers.

In most functional languages (including Elixir), depending on the specific situation, one of these two ways is used. The third one, ‘cheating’ using message-passing, is often too much overhead for what you want to use the generator for. Exceptions of course do exist: A GenServer that returns guaranteed-unique identifiers, for instance.

I do wonder if we can implement a generator based on fixpoint combinators as well, by the way…

Can’t we all be friends?

Every new language you learn impacts your style. Some concepts tend to stick, so naturally I want to explore how they could be replicated or what the alternatives are.

Maybe try to leave more of Python land behind or recognize that there are things that are normal in Python that you won’t want to do in Elixir.

Thanks everyone for your thoughts.

I have currently this passing test case:

  test "generators" do
    defmodule MyGen do
      use Snakeoil.Generators

      gen "counter", x do
        yield x
        counter(x+1)
      end

      gen "two", {x, y} do
        yield x + y
        two({x+1, y + 1})
      end
    end

    pid = spawn(fn -> MyGen.counter(0) end)
    assert 0 == MyGen.next(pid)
    assert 1 == MyGen.next(pid)
    assert 2 == MyGen.next(pid)

    pid = spawn(fn -> MyGen.two({2, 3}) end)
    assert 5 == MyGen.next(pid)
    assert 7 == MyGen.next(pid)
  end

This is a toy, of course - mostly an exercise in metaprogramming. I have to admit that having optional parentheses makes things like that fun to write - but I’m not sure how fun it would be if someone did use that in their own code If i’m not mistaken, Elixir also favors explicit over implicit, which is good from me, coming over from Python land.

An API like

s = step(1, 2)
s.next() # 1
s.next() # 3
s.next() # 5

relies upon mutable state. This is obviously impossible with Elixir when using ordinary data structures. Message passing and backing by a genserver could give you something like this, but you’re generally gonna want to avoid that.

There IS a way to get a regular immutable Enumerable to walk forward, but the API is a bit cumbersome because it requires using sort of the “internals” of how Enumerables work.

stream = Stream.cycle([1,2,3])
{:suspended, _, stream} = Enumerable.reduce(stream, {:suspend, nil}, fn(v, _) -> {:suspend, v} end)
{_, val, stream} = stream.({:cont, nil})
val #=> 1
{_, val, stream} = stream.({:cont, nil})
val #=> 2
{_, val, stream} = stream.({:cont, nil})
val #=> 3

Not the prettiest way to do that.

At the end of the day though I’d still say that the closest thing to the python

def step(x, s):
    while True:
        yield x
        x = x + s

Is the Elixir

def step(x, s) do
  Stream.unfold(x, fn(x) -> {x, x+s} end)
end

And the difference in how you use it is just part of the normal differences you get a in a pure vs impure language.