haskell - 了解惰性评估的局限性(埃拉托色尼筛法)

Question

在 Haskell Wiki article on prime numbers ，描述了以下 Eratosthenes 筛的实现:

primes = 2 : 3 : minus [5,7..] (unionAll [[p*p, p*p+2*p..] | p <- tail primes])

做的时候...

primes !! 2

... Haskell 如何识别在这种特定情况下不尝试所有 p位于 primes 的尾部(又名 [3..] )，但只是用 3 做一个减号?

换句话说:Haskell 怎么知道其他 p 中的任何一个？的(或其倍数)将不匹配 5 ，这是最终的答案。是否有一个好的经验法则可以知道编译器何时足够聪明以处理无限情况？

Answer 1

(!!)只要求 primes进行足够的评估以找出至少有 3 个元素，以及第三个元素是什么。要获得第三个元素，我们需要开始评估对 minus 的调用。 .
minus假定它的两个参数都已排序。这在文档中有所描述，并在 primes 的定义中得到满足.第一次比较minus perform 介于 5 和 9 之间，这表明 5 是结果的第一个元素。在 definition of minus就是这种情况LT -> x : loop xs (y:ys) .
(!!)现在有 primes 的第三个元素，所以评估不会在 primes 中继续或 minus或 unionAll .子表达式求值和外部表达式中的模式匹配之间的这种反复是惰性求值。