了解懒惰评估的局限性(Eratosthenes的筛选)

Question

在关于素数的Haskell Wiki文章中,描述了以下Eratosthenes筛选的实现:

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

什么时候......

primes !! 2

... Haskell如何在这种特定情况下认识到不要尝试(aka )p尾部的所有东西,而只是设置减去？primes[3..]3

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

Answer 1

(!!)只要求primes进行足够的评估以找出至少有 3 个元素，以及第三个元素是什么。为了获得第三个元素，我们需要开始评估对 的调用minus。

minus假设它的两个参数都已排序。这在文档中进行了描述，并且在 的定义中得到了满足primes。第一次比较minus执行在 5 和 9 之间，这表明 5 是结果的第一个元素。在减的定义中就是这种情况LT -> x : loop xs (y:ys)。

(!!)现在有第三个元素primes，因此求值不会在primesorminus或中继续unionAll。子表达式的求值和外部表达式中的模式匹配之间的这种来回是惰性求值。