Ruby-like Enumerator for generating prime numbers?

I wanted to write a prime number generator that I could use multiple times to get the next higher prime. In Ruby, I could build an enumerator that would yield the next value (with a block or by calling #next), but I couldn’t find the same sort of thing in Elixir. The best I could come up with was this:

step = fn(x, acc) -> {:suspend, [x|acc]} end
{:suspended, new_primes, generator} = Enumerable.reduce(primes, {:cont, []}, step)
{:suspended, new_primes, generator} = generator.({:cont, primes})

This worked, but it’s not very elegant. Is there a better way?

2 Likes

If You need to persist last number returned to generate next - I think You can try to implement this with Agent. Returning next prime on get.

P.S. If the number of primes You need to get is finite maybe it’s easier to put them into list (load from file, DB) and use Agent to get a next number on every “get” call than generate them with complex logic?

2 Likes

Yeah I know there are some more practical ways of doing it, but the idea of an enumerator is very useful, and I was hoping to find an analogue in Elixir.

1 Like

You could create a struct for storing the last prime and use it as your “Enumerator”.

Yes, you would still need to return a new struct for each call to next, but the only workaround for that would be using an Agent.

The main point is that a classical enumerator, like the Ruby one, requires an internal pointer to the current and/or next element, and that pointer’s value keeps changing over time. So, a total nope in Elixir land (unless you replace that pointer with an Agent).

If you embrace the “functional way”, the struct option is not a bad idea. Here are some nice material about structs and protocols:

Elixir official guide about structs
Elixir official guide about protocols
An example of Collectable implementation

Even with the “limitations” of the absence of mutable-state, the final result can be very pleasing.

3 Likes

Generators = lazy and value is evaluated only once (if you reuse the same generator it will have cached values).
For lazy Elixir has streams, maybe cached value is not a adequate to Elixir.
The simplest Elixir generator
1..100 -> generates values from 1 to 100

I found one example

2 Likes

The stream unfold answer is the right one, agents are definitely not the right approach. Agents should never be used as ordinary mutable variables. The original approach was really rather close conceptually. The Stream module provides a variety of useful functions for lazily working with enumerations.

2 Likes

I’ve implemented the Sequences Hex package that contains a lot of lazily evaluated integer sequences, including the prime numbers.

The implementation I used there also uses Streams, and calculates the next prime as follows:

  1. take the Stream of odd numbers
  2. Test each of them by trial-dividing against all primes lower than itself. This is done using Stream.scan/3. If it is not divisible by any previously-known primes (these are kept in the accumulator), it itself is added to the front of the accumulator. Otherwise the accumulator is copied.
  3. We now have a Stream where each element is a list of all primes lower than itself, in descending order.
  4. Map over this stream to take the head of each of these lists. We now have a list where each nth item is the highest prime number known up to n.
  5. Call Stream.dedup to remove all subsequent duplicate values. Each nth item is now the nth prime number.

We now have a list of primes.

It probably is possible to create a Sieve of Erastothenes or a Barrel Sieve as well, but I haven’t tried so myself this far.

1 Like

I did a basic forward-only primes generator few months ago. You can find the impl here. I didn’t invest much time into it, so can’t say it’s optimized, but perhaps it may provide some ideas.

1 Like