list - 什么是 Haskell 的 Stream Fusion

Question

什么是 Haskell 的 Stream Fusion 以及如何使用它？

Answer 1

Logan 指出的论文很棒，但有点困难。 (问问我的学生就知道了。)其中也有很多关于“流融合如何工作”的内容，而只有一小部分是“什么是流融合以及如何使用它”。

流融合解决的问题是编写的功能代码通常会分配中间列表，例如，为了创建节点号的无限列表，您可能会编写

nodenames = map ("n"++) $ map show [1..]

简单的代码会分配一​​个无限的整数列表[1, 2, 3, ...]，一个无限的字符串列表["1", "2", "3 ", ...]，最终是一个无限的名称列表 ["n1", "n2", "n3", ...]。分配太多了。

流融合的作用是将像nodenames这样的定义转换为使用递归函数的东西，该递归函数仅分配结果所需的内容。一般来说，消除中间列表的分配被称为毁林。

要使用流融合，您需要编写非递归列表函数，这些函数使用 GHC ticket 915 中描述的流融合库中的函数。 (map、foldr 等)而不是显式递归。该库包含所有 Prelude 函数的新版本，这些函数已被重写以利用流融合。显然，这个东西预计会进入下一个 GHC 版本 (6.12)，但不在当前的稳定版本 (6.10) 中。如果你想使用库 Porges 在他的回答中有一个很好的简单解释。

如果您确实想要解释流融合的工作原理，请发布另一个问题——但这要困难得多。