如何使用高阶函数定义素数计算的筛选函数？ [英] How do I define the sieve function for prime computation using higher–order functions?

问题描述

我在Haskell中有一个筛选的递归定义，用于素数计算。但是我不知道如何使用高阶函数（如 map 或 filter 即可。可以有人向我显示吗？

 筛[] = [] 
筛（x：xs）=检查：xs）
 
支票[] = [] 
支票（x：xs）
 | x / = 2&& x / = 3&& x / = 5&& x / = 7 = comp（x：xs）
 |否则= x：筛xs 
 
 comp [] = [] 
 comp（x：xs）
 | x`mod` 2 == 0 =筛xs 
 | x`mod` 3 == 0 =筛xs 
 | x`mod` 5 == 0 =筛xs 
 | x `mod` 7 == 0 =筛xs 
 |否则= x：筛xs 
  

解决方案

使用 map 和 filter 和 iterate ;很慢：

  primes = map head $ iterate（\（x：xs） - > filter（（> 0 ）（`rem`x））xs）[2 ..] 
  

添加的concat ; 更快，复杂度提高很多：

  primes = concat $ map fst $ iterate（\ （_，（p：ps，xs）） - > case span（< p * p）xs 
 {（h，t）→（h，（ps，filter（（& ）（`rem`p））t））}）（[2]，（primes，[3 ..]））
  

更多在 http://www.haskell.org/haskellwiki / Prime_numbers_miscellaneous＃One-liners 。

---

您可以表达 iterate 通过地图如果您愿意：

  iterate fx = let r = x：map fr in r 
  

和过滤器太：

  filter f xs = concat $ map（\x  - > [x | fx]）xs 
  

---

但是对于 > Eratosthenes筛网， - 通过可分性测试不检测复合材料，并直接生成它们om primes它找到，并在这样生成的复合物之间的差距中找到素数， - 我们需要一些更多的辅助功能，如 减去和 union 和 treelike-folding foldi （ foldr 可以用于代替折叠，但速度降低和复杂性恶化）：

 code> primes = 2：_Y（（3 :)）减[5,7 ..] 
。 foldi（\（x：xs）ys-> x：union xs ys）[] 
。地图（\p-> [p * p，p * p + 2 * p ..]））
 _Y g = g（_Y g）
  pre> 
 
 
运行速度更快，接近最佳 a ，它们被排除在外。这不是问题，而 b 。它们的性能由给定的Haskell实现决定，而不是用户代码。可变数组当然是最快的，但是代码更加涉及。
 
I have a recursive definition of sieve in Haskell for prime number computation. But I don’t know how to write the same function using higher–order functions such as map or filter. Can anybody show me please?
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 http://www.haskell.org/haskellwiki/Prime_numbers_miscellaneous#One-liners.



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.

                        
这篇关于如何使用高阶函数定义素数计算的筛选函数？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！