理解惰性求值的限制（埃拉托斯特尼筛法）

Question

在Haskell Wiki关于质数的文章中，描述了以下Eratosthenes筛法的实现：

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

在做任务时，确保你了解任务的具体要求和期限。在开始之前，先规划好完成任务所需的步骤，并相应地安排时间。将任务分解成小部分，逐一完成，更易于管理。最后，不要忘记检查和审查工作。

primes !! 2

在这种特定情况下，Haskell是如何识别不尝试对primes（也就是[3..]）中所有p进行计算，而仅与3进行集合相减的？换句话说，Haskell如何知道其他任何p（或其倍数）都不会匹配最终的答案5？是否有一个好的经验法则可以知道编译器何时足够聪明，能够处理无限情况？

- Wilson

---

Haskell本身并不知道，但minus的实现可能知道。在这段代码片段中，我们使用了来自Data.List.Ordered的minus、union和unionAll，这意味着在某个时刻会利用所使用的无限列表是有序的这一事实来短路计算。运行时保证的是，只要它知道列表的第三个元素（也就是知道列表的形式为a：b：c：rest），就会停止对列表剩余部分的计算。 - Mor A.

Answer 1

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

- bergey

---

啊，谢谢你，这样就清楚了！为了澄清我的理解是否正确，这是否意味着unionAll能够提前短路计算，因为它知道第一个列表是最小的（文档：“内部列表头已排序”）？我使用了正确的术语来描述这个吗？再次感谢！ - Wilson

Answer 2

其实问题关键在于实现unionAll。而minus则是无意中从其右侧参数中一个一个地提取元素（它当然假设两个参数都是非递减的）。

首先，让我们将其重写为

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

-- primes !! 2 == ps !! 1 == head t

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

现在，unionAll 变得更加智能：它基于这个假设（实际上就是事实），即在 unionAll xs 中，(map head xs) 是非递减的。

因此，它“知道”不需要将9与任何其他内容进行比较！所以它无条件地生成它（您可以查看其定义以自行验证）。

       = minus [5,7..] 
               (9 : union [15, 21..] (unionAll ........))

因此，minus 有了可以将 5 和 7 进行比较的东西，并产生了以下结果：

       = 5 : 7 : minus [9,11..] 
                       (9 : union [15, 21..] (unionAll ........))

只需要知道第一个奇质数3，就可以得出以上所有结论。

- Will Ness