我sieve在 Haskell 中有一个用于素数计算的递归定义。map但我不知道如何使用orfilter等高阶函数编写相同的函数。有人可以给我看看吗？
sieve [] = []
sieve (x:xs) = check (x:xs)
check [] = []
check (x:xs)
|x/=2 && x/=3 && x/=5 && x/=7 = comp (x:xs)
|otherwise = x : sieve xs
comp [] = []
comp (x:xs)
|x `mod` 2 == 0 = sieve xs
|x `mod` 3 == 0 = sieve xs
|x `mod` 5 == 0 = sieve xs
|x `mod` 7 == 0 = sieve xs
|otherwise = x : sieve xs
With map and filter and iterate; very slow:
primes = map head $ iterate (\(x:xs) -> filter ((> 0).(`rem`x)) xs) [2..]
with addition of concat; much faster and with much improved complexity:
primes = concat . map fst $
iterate (\(_, (p:ps, xs)) -> case span (< p*p) xs of
{ (h,t) -> (h, (ps, filter ((> 0).(`rem`p)) t)) })
([2], (primes, [3..]))
more at Haskell wiki.
You can express iterate through map if you prefer:
iterate f x = let { r = x : map f r } in r
and filter too:
filter f xs = concat $ map (\x -> [x | f x]) xs
But for the true sieve of Eratosthenes, - one which does not detect composites by divisibility testing but generates them directly from primes it finds, and finds the primes in gaps between thus generated composites, - we need some more auxiliary functions, like minus and union, and treelike-folding foldi (foldr can be used in place of foldi but with decreased speed and worsened complexity):
primes = 2 : _Y ((3:) . minus [5,7..]
. foldi (\(x:xs) ys -> x : union xs ys) []
. map (\p -> [p*p, p*p+2*p..]))
_Y g = g (_Y g)
This runs yet faster, at close to best empirical orders of growth achievable with Haskell's immutable code. Immutable arrays can be faster, but they are excluded here because a. it's not in the question, and b. their performance is determined by a given Haskell implementation, not a user code. Mutable arrays are of course the fastest but the code is even more involved.
我很快把它放在一起，速度不是很好，但它很容易实现。
primes'::[Int]->[Int]
primes' [] = []
primes' (x:xs) = x:primes (filter ((/= 0) . (`mod` x)) xs)
main = print $ primes [2..20] -- always input a contiguous list from 2 to N.