在Haskell中过滤无限列表 [英] Filtering an infinite list in Haskell
问题描述
我有以下代码实现了Eratosthenes的筛选:
$ $ p $ primes :: [Int]
素数= primes'[2 ..]
primes':: [Int] - > [p] p'(p'ps),而不是(p'`isMultiple` p [prime]'[p] )])
a`isMultiple` b =(a`mod` b)== 0
main = print(sum(primes'[2..100000]))
我想将main改为
main = print(sum [p | p
毫不奇怪,这是因为它必须将p与无限列表素数的每个元素进行比较。既然我知道质数的顺序是递增的,当我发现一个超过我的上限的元素时,我该如何截断无限列表?
p.s。理论上,素数会过滤输入列表以返回素数列表。我知道如果我从2以外的东西开始列表,我将会遇到一些问题。我仍在努力如何自己解决这个问题,所以请不要破坏。谢谢; - )
在像这样的情况下,您知道一旦谓词对元素返回false,对于后面的元素会返回true,您可以用 takeWhile
来替换 filter
,它会在谓词停止时立即获取元素第一次返回false。
I have the following code that implements the Sieve of 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]))
I would like to change main to something like
main = print (sum [p | p <- primes, p < 100000]))
Not surprisingly, this hangs because it must compare p against every element of the infinite list primes. Since I know that primes is in increasing order, how do I truncate the infinite list as soon as I find an element that exceeds my upper limit?
p.s. In theory, primes' filters the input list to return a list of primes. I know there will be some issues if I start the list at something other than 2. I'm still working on how to address this issue on my own, so please no spoilers. Thanks ;-)
In cases like this where you know that once the predicate returns false for an element, it won't ever return true for a later element, you can replace filter
with takeWhile
, which stops taking elements as soon as the predicate returns false for the first time.
这篇关于在Haskell中过滤无限列表的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!