Python generators equivalent?

Questions / Help
1

So Python has a nice concept of generators - functions that become iterators when called:

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

This is called like so:

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

And it implements the iterator protocol so you can pass it wherever an iterator is expected.

What’s the idiomatic way in Elixir to do this? We can get partway there with:

s = Stream.unfold(1, fn(x) -> {x, x+2} end)
Enum.take(s, 3) # [1, 3, 5]

But obviously this is not stateful. To get stateful, a process would be needed… But even if we don’t maintain state, I couldn’t find an easy way to do this:

{[1, 3], s} = Stream.split(s, 2)
{[5], s} = Stream.split(s, 1)

Using Enum.split blocks, probably trying to reach the end of the Stream.

Thoughts?

1 Like
2

Well, at least for Enum.split/2s strictness there has been a discussion recently:

This also tackles some small bits of your “state” problem.

In elixir I do usually not expect side effects to happen, so next(s) which returns 1 on the first call and 2 on the second without rebinding s would be counterintuitive for me.

If you need a central authority handing out free ids, work items, whatever, I do think that is what GenStage has been developed for.

If you really need something as your python thingy (which involves far too much magic for me, I’d expect it to loop forever) then you need to implement it yourself. Some protocol or behaviour and a handfull of macros, and you are ready to release it on hex.

1 Like
3

Thanks for the link.

Re the magic, would you expect:

s = Stream.unfold(1, fn(x) -> 
  receive do
    :next -> IO.puts "hi";{x, x+2} 
  end
end)
Stream.run(s)

… to loop forever? It has similar semantics. I think I could probably implement this with the available tools, yes :slight_smile:

4

@orestis, it looks like StreamSplit would mostly have you covered, at least as far your example goes…

First define your iterator(s):

defmodule SplitDemo.Generators do
  def step(x, s) do
    Stream.iterate(x, &(&1 + s))
  end

  def next(stream, n \\ 1) do
    StreamSplit.take_and_drop(stream, n)
  end
end

Then call from somewhere:

import SplitDemo.Generators

s = step(1, 2)
{[1], s} = next(s)
{[3], s} = next(s)
{[5], s} = next(s)
{[7, 9, 11], s} = next(s, 3)

See my demo repo for the above example, with some output added.

5

Of course I do expect a stream that has no end to run forever. Stream.run/1 is documented to evaluate the complete stream.

As well as I do expect while true {} to do nothing forever, and not to do a single nothing only when I do ask for it…

After reformatting your code, I do see a little bit better what you meant. Still I’d expect that Stream to run forever and to block that process it is run in, but of course you can ask for printing “hi” and doing an otherwise useless addition if you do know the PID of the starting process.

1 Like
6

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.

7

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 :slight_smile: If i’m not mistaken, Elixir also favors explicit over implicit, which is good from me, coming over from Python land.

1 Like
8

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.

9

Can’t we all be friends? :slight_smile:

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.

2 Likes
10

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… :smiley:

2 Likes
11

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!

12

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.

1 Like
13

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

14

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.

15

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

1 Like