Eratosthenes 无限列表筛法

Question

你好，我必须实现埃拉托色尼筛法的功能。

我已经有一个功能

removep p l

删除 l 中匹配谓词 p 和函数

的元素

nats

那个 returns 一个无限的自然数列表，我应该在我的解决方案中同时使用它们。

现在，我确实了解筛子本身是如何工作的，但我似乎在实现它时遇到了问题。

我正在做这样的事情：

sieve = (drop 1 nats)
 where
   sieve (h:t) = h : (removep (\x -> (mod x p) == 0) t) : sieve

但这似乎不起作用。有什么帮助吗？另请注意，这是一项任务，因此如果可能，请不要泄露确切的解决方案。我宁愿了解我做错了什么以及我需要如何改变它。提前致谢。

Answer 1

您的代码中存在一些错误：

你想定义一个sieve列表，应该是素数列表，但是在where你shadow名称 sieve 与功能。在此定义中，您使用 sieve 作为列表，但此处它实际上引用了该函数，因此您会得到类型错误。

您想对 drop 1 nats 应用一个函数来获取素数列表。
在 mod x p 中它应该是 mod x h 因为 h 是你在那里考虑的素数。
你正在定义 sieve (h:t) = h:removep ... :_ 但是你在这里创建了一个列表，其中第一个元素是 h，一个数字，第二个元素是 removep ...，这是一个list，然后剩下的元素取sieve（前面已经说了不对
吹毛求疵：从技术上讲，这不是埃拉托色尼筛法，因为在筛法算法中，您从未实际上使用 mod 来检查整除性.

Answer 2

基本思路是你得到nats的列表作为筛选的起点。然后递归地将带有谓词的 removep 函数应用于除第一个元素以外的所有元素。

你很接近，但我认为你的问题在于符号（参见 Bakuriu 的回答）我不会给你答案，但我会给你一个提示：

sieve = s (drop 1 nats)
  where
    -- Recursive definition of s here
    -- s (h:t) = ???

我希望我没有放弃太多以至于让它变得微不足道。祝你好运。

PS：正如Bakuriu所说，这真的不是真正的筛子。有关此事的更多信息，请查看 here

Sieve of Eratosthenes infinite list