我是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 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.
更多推荐
素数生成器,具有递归和列表理解
发布评论