Haskell 用于排除埃拉托色尼筛法未按预期工作的数字的代码
Haskell code to exclude numbers for Sieve of Eratosthenes not working as expected
我带来了以下 Sieve of Eratosthenes 实现：
sieve :: (Integral a) => [a] -> [a]
sieve [] = []
sieve (p:ps) = p:[x | x <- sieve ps, (rem x p) /= 0]
primes :: (Integral a) => [a]
primes = sieve [2..100]
从 gchi 调用 primes 输出：
[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]
从 p2 添加开始标记数字的 optimization step，我最终得到以下代码：
sieve :: (Integral a) => [a] -> [a]
sieve [] = []
sieve (p:ps) = p:[x | x <- sieve ps, x > p ^ 2, (rem x p) /= 0]
primes :: (Integral a) => [a]
primes = sieve [2..100]
但它产生以下输出：
[2]
我是 Haskell 的新手，所以我无法理解为什么添加 x > p ^ 2 会产生这个结果。
你能解释一下 Haskell 如何计算那个表达式来发现我的错误吗？
这行代码：
p:[x | x <- sieve ps, x > p ^ 2, (rem x p) /= 0]
说 "take all x from sieve ps such that x > p^2 and x is not divisible by p"。这意味着所有小于或等于 p^2 的数字都将被丢弃。显然是不正确的（最小反例：[2..3]）。
你有
sieve [2..10]
扩展为
2 : [x1 | x1 <- sieve [3..10], x1 > 4, rem x1 2 /= 0]
= 2 : [x1 | x1 <- 3 : [x2 | x2 <- sieve [4..10],
x2 > 9,
x2 `rem` 3 /= 0],
x1 > 4,
x1 `rem` 2 /= 0]
所以第一个 x1 是 3，但是 3 > 4 是 False 所以我们转到下一个：
= 2 : [x1 | x1 <- [x2 | x2 <- sieve [4..10],
x2 > 9,
x2 `rem` 3 /= 0],
x1 > 4,
x1 `rem` 2 /= 0]
= 2 : [x1 | x1 <- [x2 | x2 <- 4 : [x3 | x3 <- sieve [5..10],
x3 > 16,
x3 `rem` 4 /= 0],
x2 > 9,
x2 `rem` 3 /= 0],
x1 > 4,
x1 `rem` 2 /= 0]
所以如果 x2 是 4，x2 > 9 是假的，所以我们移动到下一个元素：
= 2 : [x1 | x1 <- [x2 | x2 <- [x3 | x3 <- sieve [5..10],
x3 > 16,
x3 `rem` 4 /= 0],
x2 > 9,
x2 `rem` 3 /= 0],
x1 > 4,
x1 `rem` 2 /= 0]
所以我们已经可以看到，我们知道返回的唯一实际值是 2，3 被跳过，因为 3 > 4 是 False。 4 被跳过，但由于错误的原因，5 将被跳过，因为 5 > 16 是 False，等等。这里的问题是你的条件 x > p ^ 2 过滤了整个列表，但你真的想在你的列表中跳到前面。这意味着您真正感兴趣的值正在从输出中过滤掉。
我带来了以下 Sieve of Eratosthenes 实现：
sieve :: (Integral a) => [a] -> [a]
sieve [] = []
sieve (p:ps) = p:[x | x <- sieve ps, (rem x p) /= 0]
primes :: (Integral a) => [a]
primes = sieve [2..100]
从 gchi 调用 primes 输出：
[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]
从 p2 添加开始标记数字的 optimization step，我最终得到以下代码：
sieve :: (Integral a) => [a] -> [a]
sieve [] = []
sieve (p:ps) = p:[x | x <- sieve ps, x > p ^ 2, (rem x p) /= 0]
primes :: (Integral a) => [a]
primes = sieve [2..100]
但它产生以下输出：
[2]
我是 Haskell 的新手，所以我无法理解为什么添加 x > p ^ 2 会产生这个结果。
你能解释一下 Haskell 如何计算那个表达式来发现我的错误吗？
这行代码：
p:[x | x <- sieve ps, x > p ^ 2, (rem x p) /= 0]
说 "take all x from sieve ps such that x > p^2 and x is not divisible by p"。这意味着所有小于或等于 p^2 的数字都将被丢弃。显然是不正确的（最小反例：[2..3]）。
你有
sieve [2..10]
扩展为
2 : [x1 | x1 <- sieve [3..10], x1 > 4, rem x1 2 /= 0]
= 2 : [x1 | x1 <- 3 : [x2 | x2 <- sieve [4..10],
x2 > 9,
x2 `rem` 3 /= 0],
x1 > 4,
x1 `rem` 2 /= 0]
所以第一个 x1 是 3，但是 3 > 4 是 False 所以我们转到下一个：
= 2 : [x1 | x1 <- [x2 | x2 <- sieve [4..10],
x2 > 9,
x2 `rem` 3 /= 0],
x1 > 4,
x1 `rem` 2 /= 0]
= 2 : [x1 | x1 <- [x2 | x2 <- 4 : [x3 | x3 <- sieve [5..10],
x3 > 16,
x3 `rem` 4 /= 0],
x2 > 9,
x2 `rem` 3 /= 0],
x1 > 4,
x1 `rem` 2 /= 0]
所以如果 x2 是 4，x2 > 9 是假的，所以我们移动到下一个元素：
= 2 : [x1 | x1 <- [x2 | x2 <- [x3 | x3 <- sieve [5..10],
x3 > 16,
x3 `rem` 4 /= 0],
x2 > 9,
x2 `rem` 3 /= 0],
x1 > 4,
x1 `rem` 2 /= 0]
所以我们已经可以看到，我们知道返回的唯一实际值是 2，3 被跳过，因为 3 > 4 是 False。 4 被跳过，但由于错误的原因，5 将被跳过，因为 5 > 16 是 False，等等。这里的问题是你的条件 x > p ^ 2 过滤了整个列表，但你真的想在你的列表中跳到前面。这意味着您真正感兴趣的值正在从输出中过滤掉。