javascript - Javascript 与 Haskell 中的 Eratosthenes 筛选

Question

我一直在玩 Haskell 并发现它很有趣，尤其是 Lazy Evaluation 功能，它允许我们使用(潜在地)无限列表。
由此，衍生出the Sieve of Eratosthenes的漂亮实现得到一个无限的素数列表:

primes = sieve [2..]
  where sieve (x:xs) = x : sieve [i | i <- xs, i `mod` x /= 0]

仍在使用 haskell 我可以有:

takeWhile (<1000) primes

这给了我直到 1000 (n) 的素数，或者

take 1000 primes

这给了我前 1000 个素数

我试图在 Javascript 中实现这一点，忘记了“无限”的可能性，这就是我想出的:

const sieve = list => {
  if (list.length === 0) return []
  const first = list.shift()
  const filtered = list.filter(x => x % first !== 0)
  return [first, ...sieve(filtered)]
}

const getPrimes = n => {
  const list = new Array(n - 1).fill(null).map((x, i) => i + 2)
  return sieve(list)
}

它工作得很好(如果我没有达到最大调用堆栈大小)，但我只能得到“直到”n 的素数。
我如何使用它来实现一个函数，而不是返回“第一个 n”素数？
我已经尝试了很多方法，但无法让它发挥作用

奖金
有什么方法可以使用尾调用优化或其他方法来避免大型 Ns 的 StackOverflows？

Answer 1

正如@VLAZ 所建议的，我们可以使用生成器来做到这一点:

function* removeMultiplesOf(x, iterator) {
  for (const i of iterator)
    if (i % x != 0)
      yield i;
}
function* eratosthenes(iterator) {
  const x = iterator.next().value;
  yield x;
  yield* eratosthenes(removeMultiplesOf(x, iterator));
}
function* from(i) {
  while (true)
    yield i++;
}
function* take(n, iterator) {
  if (n <= 0) return;
  for (const x of iterator) {
    yield x;
    if (--n == 0) break;
  }
}

const primes = eratosthenes(from(2));
console.log(Array.from(take(1000, primes)));

顺便说一句，我认为可以通过不重复进行除法来优化这一点:

function* removeMultiplesOf(x, iterator) {
  let n = x;
  for (const i of iterator) {
    while (n < i)
      n += x;
    if (n != i)
      yield i;
  }
}

但是一个快速的基准测试表明它实际上和简单的函数一样快。