Sieve在开始时陷入困境

我写了下面的筛子:

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
采纳答案:

通过对整个sieve应用all sieve而不仅仅是您到目前为止筛选的值,您可以进行无限递归。 即对于第二个元素, isPrime测试sieve 所有值而不是2

在您的Python版本中,您写道

is_prime(n, ps)

目前为止只对所有被筛选的数字进行了测试。 Python相当于你在Haskell中所做的事情

is_prime(n, sieve())

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

author: frerich-raabe

参考更多解答: Sieve gets stuck at the beginning ,转载请保留出处Sieve在开始时陷入困境及作者信息

Statement: We respect knowledge and authors. Since the content comes from the Internet and is intended for scientific research, any reprinters should retain the author's signature and origin. If you are the author of the content and feel in dispute, please contact email: 1076545519@qq.com. We will find out the situation and deal with it in time. We sincerely thank the author for his hard work.


更多:haskell