list - 在 Haskell 中过滤无限列表

Question

我有以下实现 Eratosthenes 筛的代码：

primes :: [Int]
primes = primes' [2..]

primes' :: [Int] -> [Int]
primes' [] = []
primes' (p:ps) = p:(primes' [p' | p' <- ps, not (p' `isMultiple` p)])

a `isMultiple` b = (a `mod` b) == 0

main = print (sum (primes' [2..100000]))

我想将 main 更改为类似

main = print (sum [p | p <- primes, p < 100000]))

毫不奇怪，这会挂起，因为它必须将 p 与无限列表素数的每个元素进行比较。既然我知道素数是按递增顺序排列的，那么一旦找到超过上限的元素，如何截断无限列表？

ps 理论上，primes' 过滤输入列表以返回素数列表。我知道如果我从 2 以外的地方开始列表会有一些问题。我仍在研究如何自己解决这个问题，所以请不要剧透。谢谢 ;-）

Answer 1

在这种情况下，您知道一旦谓词为某个元素返回 false，它将永远不会为后面的元素返回 true，您可以替换filter为takeWhile，一旦谓词第一次返回 false，它将停止获取元素。