哈斯克尔素数

Question

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

功能：

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

我认为这是init prime，但是奇怪的是，即使我将范围设置为上限（5..10例如），该函数也会永远循环，并且永远不会获得任何结果prime !! 2

你能告诉我我做错了吗？

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因为我们知道我们至少有[2,3]in n。然后检查下一个素数是否可以被n我们已经知道的任何素数整除通过使用take n，如果是的话，我们知道这是我们的下一个素数，我们需要增加n-否则，我们继续进行。

还有一种更为知名的形式，其灵感来自于（尽管不完全相同）Eratosthenes筛：

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

那么这是如何工作的呢？好吧，还是有一个相似的想法：我们知道下一个素数必须不可被任何先前的素数整除。那么我们该怎么办？好吧，2我们从开始就知道列表中的第一个元素是质数。然后，我们使用丢弃所有可被该素数整除的数字filter。然后，列表中的下一项将再次成为质数（因为我们没有将其丢弃），因此我们可以重复此过程。

这些都不是您想要的那种班轮。