javascriptgenerator

filter values from a javascript generator-stream


This Laziness in Python - Computerphile video presents this program to produce primes with generators:

def nats(n):
    yield n
    yield from nats(n+1)

def sieve(s):
    n = next(s)
    yield n
    yield from sieve(i for i in s if i%n!=0)

p = sieve(nats(2))

next(p)  # 2
next(p)  # 3
next(p)  # 5
next(p)  # 7
next(p)  # 11

I decided to implement this sieve-algorithm using JavaScript generators. I'm pretty confident with JavaScript in general but have never worked with generators directly before.

Here's what I have so far:

function* nextNaturalNumber(n) {
    yield n;
    yield* nextNaturalNumber(n + 1);
}   

function* sieve(n) {
    let count = 0;
    let g = nextNaturalNumber(2);
    while (count++ < n) {
        const possiblePrime = g.next().value;
        yield possiblePrime;
        // here's where I'm stuck:
        // how can I filter the values from the nextNaturalNumber-generator stream that are not divisible by 2?
    }
}

// print the first 10 primes
for (const prime of sieve(10)) {
    console.log(prime);
}

As mentioned in the code-comment, I'm stuck on how to filter the values from the generator stream that are not divisible by 2 and thus performing the "sieve"-operation. Is there a simple way to do this (as in Python with yield from sieve(i for i in s if i%n !=0)) in JavaScript?


Solution

  • Unfortunately, Javascript does not have that many good iterator operations. You can, however, just make a filter function that loops through the iterator and yield values that match:

    function* nextNaturalNumber(n) {
        // switch to iterative to avoid stack overflows
        while(true) {
            yield n;
            n ++;
        }
    }   
    
    function* filterIter(iter, pred) {
        for (const item of iter) {
            if (pred(item)) {
                yield item;
            }
        }
    }
    
    function* sieve(n) {
        let count = 0;
        let g = nextNaturalNumber(2);
        while (count++ < n) {
            const possiblePrime = g.next().value;
            yield possiblePrime;
            g = filterIter(g, v => v % possiblePrime != 0);
        }
    }
    
    // print the first 10 primes
    for (const prime of sieve(10)) {
        console.log(prime);
    }