将惰性评估与复杂性分析进行协调

Question

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

他说,这种技术的问题在于,当你设计更复杂的程序时,最终会出现延迟表达,使得难以理解.他说,为了优雅地解决这个问题,你必须以一些表现力的代价来使整个语言变得懒惰,即拖尾问题.

这是Miranda和Haskell采用的方法.在Haskell中,我发现很难推断出大的O复杂性,编写占用大量内存和时间的程序很容易.

我曾经和Robert Harper讨论过这个问题,他不同意你必须让你的整个语言变得优雅,并且这是Haskell的一个设计缺陷.如何使一种语言部分懒惰来解决这个问题？有这样的语言的例子吗？我想学习更多关于函数式语言的知识,但禁止副作用和各地的热切评估,包括I/O,会让事情变得有点......反直觉.

Answer 1

关于大O复杂性并不难理由 - 它在懒惰的语言中是不同的.关于此的经典参考是Okasaki的论文(以及后来的书),该论文描述了银行家方法(见第3章)的复杂性.

一般来说,人们想要混合使用懒惰和严格的行为 - 我们可能希望某些数据结构在他们的"脊椎"中是严格的,但在他们的元素中却是懒惰的.我们可能希望其他数据结构在其元素中是严格的,但也许在它们的刺中具有选择性的懒惰可能是无限的结构向量,例如.Haskell提供了选择性严格的懒惰,包括直接在数据构造函数定义中.其他语言提供严格的选择性懒惰.通常,许多人发现Haskell的默认惰性行为具有某些优点,特别是在新控制结构的定义方面.例如,请参阅此处(实际上是为了回应Harper而编写的).