haskell - 协调惰性评估与复杂性分析

Question

在 SICP 的 stream 2 视频中， Abelson 给出了一个使用模拟计算机求解微分方程的示例。然后他在Scheme中对此进行编程，使用惰性求值来绕过循环定义依赖。

他说，这种技术的问题在于，当您设计更复杂的程序时，您最终会在各处出现延迟表达式，从而使其难以理解。他说，要优雅地解决这个问题，你必须以一些表现力为代价让整个语言变得懒惰，即拖尾问题。

这是Miranda和Haskell采用的方法。在 Haskell 中，我发现很难推理出大的 O复杂性，而且很容易编写消耗太多内存和时间的程序。

我曾经和罗伯特哈珀谈过这个问题，他不同意你必须让你的整个语言变得懒惰才能使它变得优雅，这是 Haskell 的一个设计缺陷。让一种语言部分懒惰来解决这个问题的具体做法是什么？有这种语言的例子吗？我想了解更多关于函数式语言的信息，但是禁止副作用和随处可见的求值，包括 I/O，让事情有点……违反直觉。

Answer 1

不难推断大 O 复杂性——它只是在惰性语言中有所不同。对此的经典参考是冈崎的论文（以及后来的书），它描述了银行家方法（见第 3 章）来解释复杂性。

一般来说，人们想要一种惰性和严格行为的混合——我们可能希望某些数据结构的“脊椎”是严格的，但它们的元素是惰性的。其他数据结构我们可能希望它们的元素严格，但可能在它们的脊椎中有选择性的惰性，可能是无限的结构向量，例如。Haskell 提供具有选择性严格性的惰性，包括直接在数据构造函数定义中。其他语言提供严格性和选择性惰性。通常，许多人发现 Haskell 的默认惰性行为具有一定的优势，尤其是在定义新控制结构方面。参见，例如，here（实际上是为了回应 Harper 而写的）。