2

我写了以下筛子：

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
4

2 回答 2

4

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

在你的 Python 版本中，你写了

is_prime(n, ps)

仅n针对到目前为止筛选的所有数字进行测试。你在 Haskell 中所做的 Python 等价物基本上是

is_prime(n, sieve())

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

于 2015-07-08T08:11:35.190 回答
0

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

或者显然不是我说的

于 2015-07-08T08:16:29.217 回答