素数生成器，具有递归和列表理解 [英] Prime Number generator with recursion and list comprehension

问题描述

我是Haskell编程的新手，无法理解下面的列表理解如何扩展。

  primes = sieve [2 ..] 
 sieve（p：xs）= p：sieve [x | x< -xs，x`mod` p / = 0] 
  

sieve 扩展工作：

• 由于我们在 sieve ， p 会关联到 2 和 x s从 [3 ..] 。


• 接下来，在列表理解 x <-3 ，但是如果没有短路，我们怎么能用 3 来调用筛。

我不明白的是递归在这里的工作方式。

我认为这很明显人们可以一次性扩展上面的一个步骤，例如直到 5 。

解决方案

  primes = sieve [2 ..] 
筛（p：xs）= p：sieve [x | x < -  xs，x`mod` p / = 0] 
  

[2 ..] 是 [2,3,4,5，...] 所以

  primes = sieve [2,3,4,5,6，...] 
  

内嵌 sieve once：

  primes = 2：sieve [x | x < -  [3,4,5,6,7，...]，x`mod` 2 / = 0] 
  

首先， x 得到值 3 ，它通过 mod 2 filter

  primes = 2：sieve（3：[x | x < -  [4 ，5，6，7，...]，x`mod` 2 / = 0]）
  

重新命名>筛选（我将 x 更名为 y 至防止混乱）

  primes = 2：3：sieve [y | y<  -  [x | x' -  [4，5，6，7，...]，x`mod` 2 / = 0]，
y`mod` 3 / = 0] 
  

现在 x = 4 失败 mod 2 过滤但是 x = 5 传递它。所以

  primes = 2：3：sieve [y | y< -5：[x | x < -  [6,7,8，...]，x`mod`2 / = 0]，
y'mod`3 / = 0] 
  

这个 y = 5 也传递 mod 3
$ $ p $ lt; code> primes = 2：3：sieve（5：[y | y < - [x | x < - [6,7,8，...]，x`mod` 2 / = 0]，
y`mod` 3 / = 0]）


展开筛选多一次（ z 而不是 y ）让我们来到

 素数= 2： 3：5：筛子[z | z<  -  [y | y<  -  [x | x' -  [6,7,8，...]，
x`mod` 2 / = 0]，
y`mod` 3 / = 0]，
z`mod` 5 / = 0] 
  

并且扩展以同样的方式继续。

I am a newbie to Haskell programming and have trouble understanding how the below list comprehension expands.

primes = sieve [2..] 
sieve (p:xs) = p : sieve [x | x <-xs, x `mod` p /= 0]

Can someone correct me how the sieve expansion works:

• As we are pattern matching in sieve, p would associate to 2 and xs from [3..].
• Next, in the list comprehension x<-3, but then how can we call sieve with just 3 when there is no short-circuit.

Other thing I do not understand is how recursion works here.

I think it would be clear if one could expand the above one step at a time for first few numbers, say until 5.

解决方案

Let's do some equational reasoning.

primes = sieve [2..]
sieve (p:xs) = p : sieve [x | x <- xs, x `mod` p /= 0]

The [2..] is sintactic sugar for [2, 3, 4, 5, ...] so

primes = sieve [2, 3, 4, 5, 6, ...]

Inline sieve once:

primes = 2 : sieve [x | x <- [3, 4, 5, 6, 7, ...], x `mod` 2 /= 0]

First, x gets value 3 which passes the mod 2 filter

primes = 2 : sieve (3 : [x | x <- [4, 5, 6, 7, ...], x `mod` 2 /= 0])

Inline sieve again (I renamed x to y to prevent confusions)

primes = 2 : 3 : sieve [y | y <- [x | x <- [4, 5, 6, 7, ...], x `mod` 2 /= 0], 
                            y `mod` 3 /= 0]

Now x = 4 fails the mod 2 filter but x = 5 passes it. So

primes = 2 : 3 : sieve [y | y <- 5 : [x | x <- [6, 7, 8, ...], x `mod` 2 /= 0], 
                            y `mod` 3 /= 0]

This y = 5 also passes the mod 3 filter so now we have

primes = 2 : 3 : sieve (5 : [y | y <- [x | x <- [6, 7, 8, ...], x `mod` 2 /= 0], 
                                 y `mod` 3 /= 0])

Expanding sieve one more time (z instead of y) gets us to

primes = 2 : 3 : 5 : sieve [z | z <- [y | y <- [x | x <- [6, 7, 8, ...], 
                                                    x `mod` 2 /= 0], 
                                          y `mod` 3 /= 0], 
                                z `mod` 5 /= 0]

And the expansion continues on the same way.

这篇关于素数生成器，具有递归和列表理解的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！