Eratosthenes无限列表的筛子 [英] Sieve of Eratosthenes infinite list

问题描述

我已经有了一个函数

  removep pl 
  

删除 l 与谓词 p 和一个函数匹配

  nats 
  

返回无限数量的自然数，我应该同时使用我的解决方案。

现在，我明白筛网本身的工作原理，但看起来我在执行此操作时遇到问题。

我正在做这样的事情：

  sieve =（drop 1 nats）
其中
筛（h：t）= h：（removep（\ x  - >（mod xp）== 0）t）：筛
  

但这似乎不起作用。任何帮助？
还要注意，这是一个任务，所以如果可能的话，不要放弃确切的解决方案。我想知道我做错了什么，以及我需要如何改变它。

作为筛选的起点。然后，递归地将您的 removep 函数与您的谓词一起应用于除第一个元素之外的所有元素。

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

  sieve = s（drop 1 nats）
其中
  -  s的递归定义这里
  -  s（h：t）= ??? 
  

我希望我没有付出太多的代价让它变得微不足道。祝你好运。

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

Hello i have to implement a function for sieve of Eratosthenes.

I already have a function

removep p l

that removes elements of l that match the predicate p and a function

nats

that returns an infinite list of naturals numbers, and i am supposed to use both in my solution.

Now, i do understand how the sieve itself works but it seems i am having problems implementing this.

I am doing something like this:

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

but this doesn't seem to work. Any help? Also note that this is an assignment so if possible do not give away the exact solution. Id rather get an idea of what i am doing wrong and how i need to change it. Thanks in advance.

解决方案

The basic idea is that you get the list of nats as a starting point for sieve. Then you recursively apply your removep function with your predicate to all but the first elements.

You are close, but i think your problem lies in the notation (see Bakuriu's answer) I won't give you the answer but i will give you a hint:

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

I hope i didn't give away too much to make it trivial. Good luck.

PS: As Bakuriu mentioned, this is really not a true sieve. For more info on the matter, take a look here

这篇关于Eratosthenes无限列表的筛子的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！