haskell - Eager 与 Lazy Haskell。 Eager 语言中可能有无限列表吗？

Question

显然，可以实现 Haskell，使其在不改变语言语义的情况下急切地求值。如果这是真的，如何处理无限数据结构？

http://csg.csail.mit.edu/pubs/haskell.html

Therefore, a great deal of time is spent creating and destroying suspended pieces of computation (thunks). All too often, these computations are simple enough that it would be just as easy to evaluate them instead. Faxen and others have used static analysis to expose such opportunities for eagerness. We instead propose using eagerness everywhere, while using mechanisms which permit us to recover if our program is too eager.

关键是“如果我们的程序过于急切，我们有恢复的机制”。这些机制是什么？它们如何允许无限数据结构和惰性求值的其他方面，我一直认为在热切的语言中是不可能的？

Answer 1

这并不完全正确:如果您能证明它们不会发散，您可以热切地评估 Haskell 项。

例如，当您看到 f x 时，您可以首先执行最多 1,000 步的 x(如果达到 WHNF(弱头范式)或出现错误，则停止)，然后将其传递给 f — 语义被保留，但如果您认为 x 将被评估，那么您可以提前安排它作为优化发生。

如 x = fix id ，它只会在不去任何地方的 1,000 步后放弃。如 x = undefined ，它会导致错误并放弃(恢复原始thunk并将其传递给f)。等等。

如 x = [1..] ，那么它最终可能会减少到 1 : 2 : 3 : ... : 999 : 1000 : [1001..] ，达到极限，然后停在那里，将结果传递给 f。

基本上:要么证明一个表达式不能发散，要么限制计算，这样即使它发生了，事情也会终止。语义没有变化，并且可能对性能有很大的改进。

当然，缺点是如果 x 是一些非常昂贵的计算，而 f 只使用了其中的一半，您将花费 1,000 个减少步骤来浪费时间。而在 [1..] 的情况下，您最终可能会使用大量内存来存储列表；如果 f 一次处理列表一个元素，每次都扔掉头部，那么你会浪费内存。这就是为什么它很棘手:)

您最初链接的页面更详细地介绍了所使用的特定技术。