Haskell 素数函数不起作用

Question

过去几天我开始学习 Haskell，但我在这段代码上遇到了麻烦。我正在尝试创建一个函数，该函数将生成一个素数列表，给定初始列表（至少包含 2）、最大列表长度、当前除数的索引（应从 1 开始，通过将当前数字除以所有数字进行测试）到目前为止的素数）和当前要测试的数字（奇数）。

我知道它不是很优雅或高效，但此代码无法编译或运行，因此我想在优化之前先修复它。尽管对此的建议也很酷。

primes = [2,3,5,7,11,13]

genPrimes primes max curDiv curTest 
  | length primes >= max = primes
  | primes !! curDiv > floor . sqrt curTest = genPrimes (primes ++ [curTest]) max 1 (curTest + 2)
  | curTest `mod` primes !! curDiv == 0 = genPrimes primes max 1 (curTest + 2) 
  | curTest `mod` primes !! curDiv /= 0 = genPrimes primes max (curDiv + 1) curTest

当我尝试编译上面的代码时出现以下错误：

Couldn't match expected type `a0 -> c0' with actual type `Integer'
Expected type: [a0 -> c0]
  Actual type: [Integer]
In the first argument of `genPrimes', namely `primes'
In the expression: genPrimes primes 50 1 15

Answer 1

至少你的代码应该是

primes = [2,3,5,7,11,13]

genPrimes primes max = go primes (length primes) 1 (last primes + 2)
 where
  go prs len d t 
   | len >= max               = prs
   | (prs !! d) > (floor . sqrt . fromIntegral) t
                              = go (prs++[t]) (len+1) 1 (t + 2)
   | t `rem` (prs !! d) == 0  = go  prs        len    1 (t + 2) 
   | t `rem` (prs !! d) /= 0  = go  prs        len  (d + 1)  t

test n = print $ genPrimes primes n
main = test 20

然后你重新组织它（抽象出对每个候选数字执行的测试，作为 noDivs 函数）：

genPrimes primes max = go primes (length primes) (last primes + 2)
 where
  go prs len t 
   | len >= max      = prs
   | noDivs (floor . sqrt . fromIntegral $ t) t prs
                     = go (prs++[t]) (len+1) (t + 2)
   | otherwise       = go  prs        len    (t + 2)

noDivs lim t (p:rs)
   | p > lim         = True
   | t `rem` p == 0  = False
   | otherwise       = noDivs lim t rs 

你重写 noDivs

noDivs lim t = foldr (\p r -> p > lim || rem t p /= 0 && r) False

然后 您注意到 go 只是过滤数字，以便通过 noDivs 测试：

genPrimes primes max = take max (primes ++ filter theTest [t, t+2..])
 where
  t = last primes + 2
  theTest t = noDivs (floor . sqrt . fromIntegral $ t) t

但这还不起作用，因为 theTest 需要通过primes（全新的素数，因为它们被发现）到noDivs，但我们正在构建这个whole_primes列表（如取max(primes ++ ...))，那么是否存在恶性循环呢？不，因为我们只测试一个数字的平方根：

genPrimes primes max = take max wholePrimes 
 where
  wholePrimes = primes ++ filter theTest [t, t+2..]
  t           = last primes + 2
  theTest t   = noDivs (floor . sqrt . fromIntegral $ t) t wholePrimes

这现在有效。但最后，现在 genPrimes 没有什么特别的，它只是对 take 的美化调用，并且初始 primes 列表实际上可以缩小，所以我们get（稍微更改一下 noDivs 的参数排列，以使其接口更通用）：

primes = 2 : 3 : filter (noDivs $ tail primes)  [5, 7..]

noDivs factors t = -- return True if the supplied list of factors is too short
  let lim = (floor . sqrt . fromIntegral $ t) 
  in foldr (\p r-> p > lim || rem t p /= 0 && r) True factors
     -- all ((/=0).rem t) $ takeWhile (<= lim) factors
     -- all ((/=0).rem t) $ takeWhile ((<= t).(^2)) factors
     -- and [rem t f /= 0 | f <- takeWhile ((<= t).(^2)) factors]

全局 primes 列表现在无限期定义（即“无限”）。 下一步是实现素数的连续平方之间的因子列表的长度测试依据将是相同的，每个新段增加 1。 然后，将所有因素预先作为全局的前缀（已知长度） primes 列表中，我们可以直接生成它们的倍数（因此每个数字都是从它的质因数生成的），而不是测试每个数字是否是其中任何一个的倍数以下主要因素按顺序计算其平方根。

Answer 2

您已经将 ':' 的参数颠倒了：标量向左移动，或者您可以创建一个单例列表并连接：

| primes !! curDiv > floor . sqrt curTest = genPrimes (primes++[curTest]) max 1 curTest + 2

Answer 3

ja.已经给出了正确的答案，但你的解决方案不是很惯用。这是生成无限素数列表的简单方法：

primes = 2 : filter isPrime [3,5..]

isPrime n = all ((/=0).(n `mod`)) $ takeWhile (\p -> p*p <= n) primes

primes很容易理解，它将 2 定义为素数，并检查所有后续奇数是否是素数。 isPrime 有点复杂：首先我们取所有小于或等于 n 的平方根的素数。然后我们检查是否将 n 除以所有这些素数，我们没有提示等于 0。 isPrime 引用回 primes，但是这个没问题，因为 Haskell 很懒，而且我们的检查从来不需要“太多”素数。

列表 primes 是无限的，但您可以编写类似于 take 10 primes 的内容。

请注意，此代码有其自身的问题，请参阅 http://www. cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf