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

Question

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

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

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

我曾经和Robert Harper说过话关于这个问题，他不同意你必须让你的整个语言变得懒惰才能使它优雅，这是 Haskell 的一个设计缺陷。如何让一种语言部分地懒惰来解决这个问题？有没有这种语言的例子？我想了解更多关于函数式语言的知识，但是在任何地方禁止副作用和急切的评估，包括 I/O，让事情有点......违反直觉。

Answer 1

不难推理大 O 复杂性——它只是在惰性语言中不同。对此的经典引用是 Okasaki's thesis (和后来的书)描述了银行家方法(见第 3 章)来解释复杂性。

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