1

我在互联网上找到了这个解决方案，我需要一些帮助来理解它：

isPrime' :: Integer -> Bool
isPrime' n = foldr (\x acc -> (n `rem` x) /= 0 && acc) True primes
    where primes = 2 : filter isPrime' [3,5..]

有几件事：

我的理解是，如果折叠函数的累加器是 aBoolean它必须在 lambda 函数本身中设置。就像是：

(\x acc -> if (n `rem` x /= 0) then False else acc) True primes

但这里不是这样。

此外，用于的范围primes没有终止编号。我知道这行得通的原因是因为 Haskell 的懒惰评估，但它到底是如何工作的呢？

最后，这个函数似乎不会返回正确的布尔值。素数是除自身和 1 之外没有其他除数的数。所以 lambda 不应该这样读：

(\x acc -> if (n `rem` x) == 0 then False else acc) True primes

我彻底糊涂了。请帮帮我。

4

3 回答 3

1

至少对我来说，你的代码没有完成。它缺少停止条件，可以在wiki的类似解决方案中看到：

isPrime n = n > 1 &&
              foldr (\p r -> p*p > n || ((n `rem` p) /= 0 && r)) True primes

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

在这里您可以看到，当没有可能的主要因素时，条件p*p > n产生。True由于延迟执行，||不评估右侧的部分并foldr停止。

于 2015-08-04T17:00:58.140 回答
1

有

primes = [p1, p2, p3, ..., pn, ...]

计算

isPrime' n = foldr (\x acc -> (n `rem` x) /= 0 && acc) True primes

仿佛在计算

isPrime' n = rem n p1 /= 0 && (
             rem n p2 /= 0 && (
             rem n p3 /= 0 && (
             ..........
             rem n pk /= 0 && (
             ..........          ..... ))))

对于复合ns，这是可行的——其中一个rem表达式将为 0，不等式为假，整个表达式也为假，因为&&它是短路的，在其第二个参数中是惰性的。

对于素数ns，这将导致一个问题：根据rem素数的定义，任何表达式都不会是 0，直到我们p_i == n在素数中找到素数本身。但它还不存在，因为我们还没有检测到它是素数——我们现在就在做。要测试它是否是素数，我们必须知道它是素数- 显然是一个糟糕的情况。

将要求primes一个尚不存在的值。这被称为“黑洞”。它会导致错误，并且计算中止（或卡住）。

换一种说法，就好像定义

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

被定义为

primes = 2 : [ n | n <- [3,5..]
                 , and [rem n p /= 0 | p <- takeWhile (< n) primes]]

问题是要停止何时n是素数，takeWhile (< n)必须达到p高于或等于nin的素数primes，但它还没有。“黑洞”。

著名的“筛子”代码通过“转置”工作流程来解决这个问题，

primes = map head . iterate (\(x:xs)-> filter ((/=0).(`rem`x)) xs) $ [2..]

从而使其工作，同时保持其计算效率低下（代码的较小问题），不必要地用太多素数测试其候选者（其中每个素数都由其所有前面的素数测试，而不仅仅是那些不高于其平方根的素数），使其不必要的慢。

这可以通过适当提前停止测试来缓解，

primes = 2 : [ n | n <- [3,5..]
                 , and [rem n p /= 0 | p <- takeWhile ((<= n).(^2)) primes]]

根据您的定义，这相当于

isPrime' n = p1*p1 > n || rem n p1 /= 0 && (
             p2*p2 > n || rem n p2 /= 0 && (
             p3*p3 > n || rem n p3 /= 0 && (
             ..........
             pk*pk > n || rem n pk /= 0 && (
             ..........          ..... ))))

您foldr现在可以将其写为基于 - 的定义（可以在此处的另一个答案中看到）。

于 2015-08-04T23:10:35.910 回答
0

表达方式

(n `rem` x) /= 0

显然会产生 Bool 结果。该参数acc已经是一个 Bool 值。所以

(n `rem` x) /= 0 && acc

是两个 Bool 值的逻辑与，这显然会产生 Bool 结果。混乱在哪里？

输入列表是无限的，仅由奇数组成。只要你能在只检查有限数量的值后产生结果，懒惰就可以让一切都好起来。

于 2015-08-04T16:16:05.840 回答