在使用Haskell的Eratosthenes Sieve中,为什么3,5,7的倍数没有从列表中删除？

Question

我目前正在自学" Doask和Eijck 的Haskell逻辑,数学和编程之路 "一书,我在第3章.

在本章中,作者提供了一个Haskell代码,用于实现Sierat of Eratosthenes算法,我不喜欢它们的实现,所以我试着给出自己的实现; 但是,我的代码版本只删除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 ..？

Answer 1

简答:计数器k输入mark不会增加n> 2.

mark x 2 [2..]从列表中正确地剥离了evens,所以下一步是调用sieve [3,5..],这相当于3:sieve (mark 3 2 [5,7..]),所以让我们看看这里发生了什么.

mark 3 2 [5,7..](大概)尝试3从列表中删除所有的倍数,但它会一步一步地执行此操作,首先尝试从列表中删除6.但是,由于列表只包含奇数,因此永远不会从列表中删除6,并且第一种情况总是失败.代码继续检查6,从不向上移动9.

同样,25永远不会被删除,因为代码只会尝试2*5从列表中删除.