哈斯克尔：与埃拉托色尼

2016-01-11 54 views 2 likes

的筛非详尽的模式我想使用埃拉托色尼的筛的这段代码从该页面：http://en.literateprograms.org/Sieve_of_Eratosthenes_(Haskell)#chunk DEF：primes_naive哈斯克尔：与埃拉托色尼

只有一点修改，所以它只显示了素数高达数：

primes :: Integral a => a -> [a] 
primes m = sieve [2..m] 
    where 
    sieve (p:xs) = p : sieve [x|x <- xs, x `mod` p > 0]

但WinGHCi总是错误出现（例如10）：

primes 10 
[2,3,5,7*Main> *** Exception: eratosthenes.hs:4:5-55: Non-exhaustive patterns in function sieve

我知道，从递归函数，其中，例如案件英里此错误但是这里缺少什么？

来源

2016-01-11 Rainflow

尽管配方看起来像Eratosthenes的筛网，但评估实际上是不同的并且非常慢。您可能对[本文]感兴趣（https://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf）。 –

将其更改为“sieve（p：xs）|” p * p <= m = p：sieve [x | x < - xs，x'mod' p> 0] |否则=（p：xs）''为了修复和巨大的加速。 –

回答

与网站上的版本，你的功能将最终消耗整个列表，所以你需要[]

sieve [] = []

来源

2016-01-11 10:02:16 zakyggaps

匹配作为zakyggaps所说的模式，你的版本计算函数sieve具有有限列表[2..m]最终将评估空列表案例。

解决此问题的另一种方法是使用函数takeWhile :: (a -> Bool) -> [a] -> [a]来评估sieve [2..]，直到达到极限m。

primes :: Integral a => a -> [a] 
primes m = takeWhile (\p -> p <= m) $ sieve [2..] 
    where 
    sieve (p:xs) = p : sieve [x|x <- xs, x `mod` p > 0]

来源

2016-01-12 13:37:30 Shumush

哈斯克尔：与埃拉托色尼

回答

相关问题