Haskell中的质数

Question

我正在学习 Haskell，并尝试生成一个无限长的质数列表，但是我不明白我的函数在做什么错误。

该函数：

prime = 2:3:filter (\x -> all (\y -> (mod x y) > 0) (init prime)) [5..]

我认为问题在于init prime，但奇怪的是，即使我将范围设定为一个上界（例如5..10），这个函数也会无限循环，并且永远得不到prime !! 2的结果。

你能告诉我我做错了什么吗？

- G B

---

你正在尝试过滤一个列表，只保留那些不能被init prime中任何元素整除的元素。为了检查每个init prime元素是否都成立，Haskell需要找出prime中除了“最后一个”元素之外的所有元素。现在你能看到问题了吗？当你需要完整的数据结构来计算中间结果时，惰性求值对你没有帮助。 - Robin Zigmond

你可以通过将(init prime)替换为(takeWhile (\z -> z * z <= x) prime)来拯救你的想法，因为每个非质数都有一个不大于其平方根的质因数。 - ShreevatsaR

你对 init primes 的调用表明你认为每次迭代只会看到此时已构建的列表。如果这是你的信念，那么它是错误的，primes 列表并没有完全计算出来。避免使用正在生成的部分列表，就像 ShreevatsaR 的评论中所做的那样。 - Thomas M. DuBuisson

当然可以，谢谢。我只是想知道是否可能通过使用列表本身的一部分来递归地扩展无限列表以计算下一个元素。 - G B

当然是这样的；这就是@ShreevatsaR评论中的建议。你的方法之所以不起作用，是因为使用了无限列表的一部分(init)与正在生成的列表重叠。如果你使用适当的takeWhile来避免这种重叠，就不会有问题了。 - user11228628

Answer 1

首先，让我们看看对于一个有限列表，init 函数的作用：

init [1] == []
init [1,2] == [1]
init [1,2,3] == [1,2]

好的，它给我们返回列表中除了最后一个元素之外的所有元素。

那么init primes是什么呢？好吧，就是除了最后一个元素的prime。希望如果我们正确地实现了prime，它应该不会有一个最后的元素(因为质数是无穷多的！)，但更重要的是，我们现在其实并不需要关心这一点，因为我们目前只关心前几个元素，所以对我们来说，这几乎和prime本身一样。

现在看看all：它是做什么的？好吧，它采取一个列表和一个谓词，并告诉我们是否所有列表元素都满足谓词：

all (<5) [1..4] == True
all even [1..4] == False

它甚至可以与无限列表一起使用！

all (<5) [1..] == False

那么这里发生了什么？事实是：它可以与无限列表一起使用...但只有在我们能够实际评估列表直到违反谓词的第一个元素时才能使用！让我们看看这是否适用于此处：

all (\y -> (mod 5 y) > 0) (init prime)

为了确定5是否为质数，我们需要检查在质数减去最后一个元素后是否有一个数字可以整除它。让我们看看能否做到这一点。

现在让我们来看看质数的定义：

all (\y -> (mod 5 y) > 0) (2:3:filter (\x -> all (\y -> (mod x y) > 0) (init prime)) [5..])

因此，要确定 5 是否为质数，我们只需要检查它是否：

1. 可被 2 整除 - 不行，继续检查
2. 可被 3 整除 - 仍然不行
3. 可被...？嗯，我们正在检查第三个质数是什么，所以还不知道...

这就是问题的关键。按照这种逻辑，要确定第三个质数，你需要先知道第三个质数！当然，从逻辑上讲，实际上我们根本不想检查这一点，我们只需检查当前候选数是否有任何“更小”的质数作为其约数。

那么我们该怎么做呢？很遗憾，我们必须改变我们的逻辑。我们可以尝试记住我们已经有多少个质数，并且只取我们需要用来比较的数量：

prime = 2 : 3 : morePrimes 2 [5..]
  morePrimes n (x:xs)
    | all (\y -> mod x y > 0) (take n prime) = x : morePrimes (n+1) xs
    | otherwise                              = morePrimes n xs

那么这是怎样起作用的呢？它基本上就是我们刚才谈论的那样：我们记住我们已经有多少个质数（从2开始，因为我们知道在n中至少有[2,3]）。我们接下来使用“take n”检查我们的下一个质数是否可以被我们已知的n个质数之一整除。如果可以，我们知道这就是我们的下一个质数，我们需要增加n - 否则我们继续进行。

还有一种更为广为人知的形式，它受到了厄拉多塞筛法的启发（尽管不完全相同）。

prime = sieve [2..] where
  sieve (p:xs) = p : sieve (filter (\x -> mod x p > 0) xs)

那么这是如何工作的呢？好吧，再次使用类似的想法：我们知道下一个质数必须不能被任何之前的质数整除。那我们怎么做呢？好吧，从 2 开始，我们知道列表中的第一个元素是一个质数。然后我们使用filter把可被该质数整除的每个数字都丢弃掉。接着，在列表中，下一个元素仍将是一个质数（因为我们没有把它丢掉），所以我们可以重复这个过程。

但这两种方法都不像你所希望的那样简洁。

- Cubic

---

两个反对意见：首先，init 永远不会应用于 [5..]，因此解释 init [5..] 的作用似乎是无关紧要的；其次，我们绝对没有已经确认 prime 是一个无限列表（实际上，它并不是一个无限列表，所以我们肯定不能确认它是）。 - Daniel Wagner

@DanielWagner 哎呀，两个都对。我在这方面做得比以往任何时候都更好，我不认为我能挽救这个答案了。 - Cubic

@Cubic 我相信你！ - Daniel Wagner

@Cubic 如果不移除 init，你的论点基本上仍然有效，但会变得更加复杂。let prime_rest = filter f [5..]（带有适当的 f）; 然后您可以应用您的推理来推断出 prime_rest = case f 5 of { True -> 5 : prime_rest1; False -> prime_rest1 } where prime_rest1 = filter f [6..]（需要对 filter 的定义进行一些重写）。但是要评估 f 5，您必须首先确定 prime_rest 是否为 [] 或 _:_（根据 f 和 init 的定义）；而 prime_rest 正是您当前正在评估的表达式。 - user2407038

换句话说，您可以将“prime_rest”重写为“case prime_rest of { [] -> ..; [x] -> ..; (x:xs) -> .. }”，并将最外层的“case”语句定义为“init”。 - user2407038

这里有许多一行代码解决的问题链接。 :) - Will Ness

Answer 2

如果其他答案中的代码按照标识进行重组

[take n primes | n <- [0..]]  ==  inits primes

最终我们得到

import Data.List
              -- [ ([], 2), ([2], 3), ([2,3], 5), ... ]
primes = 2 : [ c | (ps, p) <- zip (inits primes) primes,  
                   c <- take 1 [c | c <- [p+1..], 
                                    and [mod c p > 0 | p <- ps]]]

进一步进行算法改进后，它变成了：

primes = 2 : [ c | (ps, r:q:_) <- zip (inits primes)                  -- [] [3,4,...]
                                      (tails $ 3 : map (^2) primes),  -- [2] [4,9,...]
                   c <- [r..q-1], and [mod c p > 0 | p <- ps]]        -- [2,3] [9,25,...]

- Will Ness