Haskell中无限素数列表生成器的惰性求值工作原理问询

先贴出代码：

primes :: [Int]
primes = sieve [2..]

sieve :: [Int] -> [Int]
sieve (n:ns) = n : sieve [n' | n' <- ns, mod n n' /= 0]

核心原因在于Haskell是惰性求值的——它不会提前计算整个无限列表，只有当你需要用到某个元素时，才会触发对应部分的计算。

举个实际运行的逻辑：

• 当你获取第一个素数时，sieve [2..]直接取出2，返回2 : sieve (...)，此时后面的sieve调用完全没执行，更不会提前过滤所有2的倍数。
• 当你要第二个素数时，才会触发对sieve [3,4,5,...]的计算：先取出3，返回3 : sieve (...)，这时候才会开始处理3的倍数的过滤，但也只是在后续需要用到元素时才会做检查排除。
• 至于2的倍数比如4，只有当程序处理到它的时候，才会判定它是2的倍数并直接排除，不会提前遍历整个无限列表把所有2的倍数都找出来。

简单说，这个筛子是按需工作的：你要第几个素数，它就计算到那一步，不会提前处理整个无限列表。你觉得需要先过滤完所有2的倍数再处理下一个素数，是受严格求值语言思维的影响，但Haskell的惰性求值刚好解决了无限列表的处理问题——它不需要生成完整列表，只生成你当前需要的部分。

内容的提问来源于stack exchange，提问作者Rifat Ahmed