我是 Haskell 编程的新手，无法理解以下列表理解如何扩展。
primes = sieve [2..]
sieve (p:xs) = p : sieve [x | x <-xs, x `mod` p /= 0]
有人可以纠正我sieve扩展的工作原理：
sieve，p将关联到2和xs from [3..]。x<-3中，但是我们如何3在没有短路的情况下调用 sieve。我不明白的另一件事是递归如何在这里工作。
我认为如果可以一次将上述一步扩展为前几个数字，比如直到5。
让我们做一些等式推理。
primes = sieve [2..]
sieve (p:xs) = p : sieve [x | x <- xs, x `mod` p /= 0]
这[2..]是语法糖，[2, 3, 4, 5, ...]所以
primes = sieve [2, 3, 4, 5, 6, ...]
内联sieve一次：
primes = 2 : sieve [x | x <- [3, 4, 5, 6, 7, ...], x `mod` 2 /= 0]
首先，x获取3通过mod 2过滤器的值
primes = 2 : sieve (3 : [x | x <- [4, 5, 6, 7, ...], x `mod` 2 /= 0])
再次内联sieve（我重命名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 2x = 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])
再扩大sieve一次（z而不是y）让我们
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]
扩张继续以同样的方式。
这是做什么的操作描述sieve。
计算sieve (x:xs)：
x。xs，让我们成为删除所有倍数的ys列表。xsxsieveon 。ys以下是前几个术语的计算方式：
sieve [2..]
= sieve (2:[3..]) -- x = 2, xs = [3..]
= 2 : sieve ys
where ys = [3..] with all of the multiples of 2 removed
= [3,5,7,9,...]
= 2 : sieve [3,5,7,9,...]
接着：
sieve [3,5,7,9,...] -- x = 3, xs = [5,7,9,11,...]
= 3 : sieve ys
where ys = [5,7,9,11,13,15,17,...] with all of the multiples of 3 removed
= [5,7, 11,13, 17,...]
= 3 : sieve [5,7,11,13,17,...]
接着：
sieve [5,7,11,13,17,...] -- x = 5, xs = [7,11,13,17..]
= 5 : sieve ys
where ys = [7, 11,13, 17,19,...] with all of the multiples of 5 removed
= [7, 11,13, 17,19,...] (the first one will be 25, then 35,...)
= 5 : sieve [7,11,13,17,19,...]
等等
使用辅助功能
transform (p:xs) = [x | x <- xs, mod x p /= 0]
= filter (\x-> mod x p /= 0) xs -- remove all multiples of p
= xs >>= noMult p -- feed xs through a tester
-- where
noMult p x = [x | rem x p > 0] -- keep x if not multiple of p
我们可以将sieve函数重写为
.=================================================+
| |
| sieve input = |
| .===========================+ |
| | | |
<~~~~~~~~~~ head input : | sieve (transform input ) | |
| | | |
| \___________________________| |
| |
\_________________________________________________|
在命令式伪代码中，我们可以将其写为
sieve input =
while (True) :
yield (head input) -- wait until it's yanked, and then
input := transform input -- advance and loop
这种重复应用的模式称为迭代：
iterate f x = loop x
where
loop x = x : loop (f x) -- [x, a:=f x, b:=f a, c:=f b, ...]
以便
sieve xs = map head ( iterate transform xs )
自然地，每个步骤中每个转换序列的头元素将是一个素数，因为我们已经在前面的步骤中删除了前面素数的所有倍数。
Haskell 是懒惰的，因此不会在每一步都完全完成转换，远非如此——只会根据需要完成尽可能多的工作。这意味着只生成第一个元素，并在被询问时“发出通知”以进一步执行转换：
<-- 2 ---< [2..]
<-- 3 ---< [3..] >>= noMult 2
<-- 5 ---< ([4..] >>= noMult 2) >>= noMult 3
<-- 7 ---< (([6..] >>= noMult 2) >>= noMult 3) >>= noMult 5
<-- 11 ---< ((([8..] >>= noMult 2) >>= noMult 3) >>= noMult 5) >>= noMult 7
...............
顺便说一句，这应该给我们一个想法：3不需要真正由2测试；4..8不需要真正被3测试，更不用说5或7了；9..24不应该真正被5测试；等我们想要的是以下内容：
<-- 2
<-- 3 --< 2(4), [3..]
<-- 5,7 --< 3(9), [4..] >>= noMult 2
<-- 11,...,23 --< 5(25), ([9..] >>= noMult 2) >>= noMult 3
<-- 29,...,47 --< 7(49), (([25..] >>= noMult 2) >>= noMult 3) >>= noMult 5
......................
即，我们希望每个>>= noMult p过滤器的创建推迟到p*p输入到达。