在 Haskell 的埃拉托色尼筛法实现中，为什么 3,5,7.. 的倍数没有从列表中删除？
In Sieve of Eratosthenes implementation with Haskell, why are the multiples of 3,5,7.. not removed from the list?
我目前正在自学 Doets 和 Eijck 的 The Haskell Road to Logic, Maths and Programming 一书，我正在学习第 3 章.
在本章中，作者提供了 Haskell 实现 埃拉托色尼筛法 算法的代码，我不喜欢他们的实现，所以我尝试给出我自己的实现；然而，我的代码版本只删除了 2 的倍数，我无法找出原因。这是代码：
sieve :: [Int] -> [Int]
sieve (0:xs) = sieve xs
sieve (x:xs) = x : sieve (mark x 2 xs)
where
mark :: Int -> Int -> [Int] -> [Int]
mark n k (y:ys)
| y == n*k = 0 : (mark n (k+1) ys)
| otherwise = y : (mark n (k) ys)
输出为
*Ch3> sieve [2..]
[2,3,5,7,9,11,13,15,17,19,21,23,25,27,29,31,33,35,37,39,41,43,45,47,49,51,...
那么，为什么代码没有对其他数字的倍数做相同的去除操作，比如3,5,7..？
Short answer: The counter k in mark doesn't increment for n > 2.
mark x 2 [2..] 正确地从列表中删除了偶数，所以下一步是调用 sieve [3,5..]，相当于 3:sieve (mark 3 2 [5,7..])，让我们看看这里发生了什么。
mark 3 2 [5,7..]（大概）尝试从列表中删除所有 3 的倍数，但它会逐步执行此操作，首先尝试从列表中删除 6。然而，由于列表只包含奇数，6 永远不会从列表中删除，第一种情况总是失败。代码继续检查 6，从不向上移动以删除 9。
同样，永远不会删除 25，因为代码只会尝试从列表中删除 2*5。
我目前正在自学 Doets 和 Eijck 的 The Haskell Road to Logic, Maths and Programming 一书，我正在学习第 3 章.
在本章中，作者提供了 Haskell 实现 埃拉托色尼筛法 算法的代码，我不喜欢他们的实现，所以我尝试给出我自己的实现；然而，我的代码版本只删除了 2 的倍数，我无法找出原因。这是代码：
sieve :: [Int] -> [Int]
sieve (0:xs) = sieve xs
sieve (x:xs) = x : sieve (mark x 2 xs)
where
mark :: Int -> Int -> [Int] -> [Int]
mark n k (y:ys)
| y == n*k = 0 : (mark n (k+1) ys)
| otherwise = y : (mark n (k) ys)
输出为
*Ch3> sieve [2..]
[2,3,5,7,9,11,13,15,17,19,21,23,25,27,29,31,33,35,37,39,41,43,45,47,49,51,...
那么，为什么代码没有对其他数字的倍数做相同的去除操作，比如3,5,7..？
Short answer: The counter
kinmarkdoesn't increment forn> 2.
mark x 2 [2..] 正确地从列表中删除了偶数，所以下一步是调用 sieve [3,5..]，相当于 3:sieve (mark 3 2 [5,7..])，让我们看看这里发生了什么。
mark 3 2 [5,7..]（大概）尝试从列表中删除所有 3 的倍数，但它会逐步执行此操作，首先尝试从列表中删除 6。然而，由于列表只包含奇数，6 永远不会从列表中删除，第一种情况总是失败。代码继续检查 6，从不向上移动以删除 9。
同样，永远不会删除 25，因为代码只会尝试从列表中删除 2*5。