筛子卡在开头

Question

我写了下面的筛子：

isPrime :: Integer -> [Integer] -> Bool
isPrime n = all (\i -> n `mod` i /= 0)


sieve :: [Integer]
sieve = 2 : [i | i <- [3,5..], isPrime i sieve]

但我不明白为什么它在第一个值之后卡住了。运行 take 10 sieve 结果是 [2, 并且没有任何反应。它可能与无限递归有关。问题可能是 sieve 正在增长，同时它在 isPrime 内部使用？出于这个原因，我也尝试修改 isPrime 如下，但没有成功：

isPrime :: Integer -> [Integer] -> Bool
isPrime n = all (\i -> n `mod` i /= 0) . takeWhile (<n)

编辑：令人惊讶的是，@Jubobs 的修改有效：

isPrime :: Integer -> [Integer] -> Bool
isPrime n = all (\i -> n `mod` i /= 0) . takeWhile (\p -> p^2 <= n)

我不明白为什么这个版本的 takeWhile 可以工作而另一个版本不能。我看到在我以前的版本中我测试了许多不必要的除数，但它们的数量是有限的。

代码基本上等同于下面的Python代码：

def is_prime(n, ps):
    for i in ps:
        if n % i == 0: return False
    return True


def sieve():
    yield 2
    n = 3
    ps = [2]
    while True:
        if is_prime(n, ps):
            yield n
            ps.append(n)
        n += 2

Answer 1

通过将 all 应用于整个 sieve 而不仅仅是您到目前为止筛选的值，您会导致无限递归。 IE。对于第二个元素，isPrime 测试 sieve 中的所有值，而不仅仅是 2.

在你的Python版本中，你写了

is_prime(n, ps)

仅测试 n 目前筛选出的所有数字。 Python 相当于你在 Haskell 中所做的基本上是

is_prime(n, sieve())

现在，使用 takeWhile (<n) 将无济于事，因为这还需要计算筛分。想象一下 sieve 的第二个元素（应该是 3）会发生什么：它测试 < 3 所持有的筛子的所有值，但是为了测试您实际上需要评估筛子元素.所以你仍然有一个无限递归。

Answer 2

我想说 sieve 中的理解列表在完成之前不会结束，永远不会。要像那样使用 take，sieve 必须 return 一个一个地筛选元素。例如，[1..] 显示 1, 2 ,3 ,4... 到无穷大，但您的筛子只显示 [2.

或者明显不是我说的

筛子卡在开头

Sieve gets stuck at the beginning

haskell

infinite

sieve