filter values from a javascript generator-stream

user_3761628 0
Viewed 478

I've recently watched this interesting video on the computerphile and decided to implement the 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?

generator javascript
3 Answers

With the following you get only odd values from your stream:

do {
    val = g.next().value;
} while (!(val%2));

Here you can test it in your code:

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

function* sieve(n) {
    let count = 0;
    let g = nextNaturalNumber(2);
    while (count++ < n) {
       let val;
       do {
             val = g.next().value;
        } while (!(val%2));
        
        const possiblePrime=val;
        yield possiblePrime;
    }
}

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

user_53245110

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);
}
user_59231390

I worry that, maybe, you're trying to be more Pythonic than is really ideal for JS coding. JS encourages being explicit about your ongoing variables (rather than hiding them in the calling and filtering stack like Python does). How about this?

//
// You want to look through all the natural numbers...
//
function* nextNaturalNumber(n) {
    while(true) {
        yield n;
        n++;
    }
}   

function* sieve() {
    //
    // Keep track of the primes you've seen previously
    //
    let previousPrimes = [];
    for (const possiblePrime of nextNaturalNumber(2)) {
        //
        // And for each number, check whether it's divisible by any of those primes
        //
        if (!previousPrimes.find((test) => (possiblePrime % test === 0))) {
            //
            // If it's not, return it as a prime and add it to the 
            // primes you've (now) already seen
            //
            yield possiblePrime;
            previousPrimes.push(possiblePrime);
        }
    }
}

let generator = sieve();
for(let i = 0; i < 10; i++) {
    console.log(generator.next().value);
}

user_193757210
Related