Haskell类型安全的空间使用

Question

我非常喜欢Haskell，尤其是它的强类型系统。当我将Haskell程序编译成功后，它们通常没有bug，或者至少非常接近没有bug。

然而，Haskell的主要问题是其未知的空间使用情况。至少在C++中，你可以比较确定程序的空间使用情况。当你构建和释放对象时这一点是很清晰的。

在Haskell中，即使是像折叠这样简单的操作，如果不正确编写，也会在thunks (类似于一个表达式还未被求值的占位符) 中使用大量的空间。由于缺乏内存而导致程序崩溃并不比其他错误好到哪里去，有人甚至认为这种错误更糟糕。

我知道有方法可以避免这些内存泄漏，但我正在寻找安全类型的方法来避免这些空间泄漏。也就是说，如果我做错了，我会得到某种编译错误，而不仅仅是希望我的程序在生产中由于内存不足而崩溃。例如，我可以替换标准库函数（比如，如果累加器不是严格的话，可能会出现编译错误的折叠函数）

在Haskell中是否存在这样的东西呢？

- Clinton

---

假设这个动物园 http://blog.ezyang.com/2011/05/space-leak-zoo/，哪种类型的泄漏应该由类型系统控制？对于流泄漏，Conduits 是足够的。 - Samvel Truzyan

Thunk泄漏，例如。您能否解释一下如何使用纯代码控制空间使用情况的conduit（即，列表泄漏但conduit不泄漏）？ - Clinton

有许多像导管一样的结构，旨在让您以受控速率处理数据流。它们包括iteratees、conduits、pipes和io-streams，以及一些用于高性能计算的库，执行称为流融合的优化。 - Levi Pearson

请查看社区最近的一篇文章：http://apfelmus.nfshost.com/blog/2013/08/21-space-invariants.html - luqui

Answer 1

众所周知，在Haskell中推理空间是非常困难的。 Simon Peyton-Jones的旧书（1987年）

http://research.microsoft.com/en-us/um/people/simonpj/papers/slpj-book-1987/

该主题在其中有一个特别的章节。

然而，如果以特定方式编写Haskell代码，例如使用简单的生成器，则可以控制内存使用情况。下面的论文（在APLAS 2012上介绍）提供了一个关于相当复杂算法（线性美观打印）的内存和延迟推理示例（顺便说一句，Haskell中的标准漂亮打印库远非最优：它们的格式化时间不是O(n)，其中n是输入的长度）。实验结果证实了内存和时间复杂度的预测。请参见APLAS演讲幻灯片，其中显示了图表。

http://okmij.org/ftp/continuations/PPYield/index.html

- Oleg