用于查找素数的 Haskell 列表理解

Question

我试图使用列表推导式尽可能简洁地找到小于某个整数 n 的所有素数。我正在学习 Haskell，这只是一个练习。我想写这样的东西：

isqrt :: Integral a => a -> a   
isqrt = floor . sqrt . fromIntegral

primes :: Integral a => a -> [a]  
primes n = [i | i <- [1,3..n], mod i k /= 0 | k <- primes (isqrt i)]

这当然行不通。有没有办法在列表理解中进行列表理解？

这是我收到的错误：

exercise-99-1.hs:138:39: Not in scope: `k'

exercise-99-1.hs:138:46:
    Illegal parallel list comprehension: use -XParallelListComp

exercise-99-1.hs:138:68: Not in scope: `i'

但是 - 我真的没想到语法是合法的 :-)

目的是尽可能直接翻译：" primes n =小于 n 的奇数整数 i 集合，使得 i 不能被任何 k 整除，对于所有 <集合中的 code>k：primes (isqrt i)" - 或多或少。 （我希望我猜对了？）

谢谢！

Answer 1

我在以下方面取得了一些进展：

primes :: Integral a => a -> [a]  
primes 2 = [2]  
primes n = 2:[i | i <- [3,5..n], all (\k -> if (mod i k /= 0) then True else False) 
                                     (primes (isqrt i))]

是否有更短的方法来编写 lambda 谓词？

编辑：是的，有，感谢评论中的评论！

primes :: Integral a => a -> [a]  
primes 2 = [2]  
primes n = 2:[i | i <- [3,5..n], all ((/= 0) . mod i) (primes (isqrt i))]

Answer 2

您的代码

primes n = [i | i <- [1,3..n], mod i k /= 0 
              | k <- primes (isqrt i)]

被解释为并行列表理解；即，不是以通常的嵌套方式组合两个生成器，而是并行组合：

primes n = [i | (i,k) <- zip [i | i <- [1,3..n], mod i k /= 0]
                                    -- not in scope: k ^
                             [k | k <- primes (isqrt i)] ]
                                  -- not in scope: i ^

相反，为了表达您的意图，它可以写成

primes 1 = []
primes n = 2:[i | i <- [3,5..n], and [mod i k /= 0 | k <- primes (isqrt i)]]

在列表理解中具有列表理解 - 但是作为守卫的一部分，而不是发电机的一部分。函数 and :: [Bool] -> Bool 使这成为可能。

---

顺便说一句，为每个新候选i递归调用primes会使其运行缓慢，并且运行时间增长得太快，经验：

 > length $ primes 10000     -- => 1229    (0.50 secs)

 > length $ primes 20000     -- => 2262    (1.40 secs)

 > logBase (2262/1229) (1.4/0.5)      -- => 1.6878      ~ n^1.69

 > length $ primes 40000     -- => 4203    (4.07 secs)

 > logBase (4203/2262) (4.07/1.4)     -- => 1.7225      ~ n^1.72

最佳试除法通常运行在 ~ n^1.4..1.45，基于列表的埃拉托色尼筛选 ~ n^1.2..1.25 并且，如果最佳实施可变数组，位于 ~ n^1.0..1.1（其中 n 为生成的素数数量， 不是上限）。