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票证915中描述的流融合库中的函数（

map

、

foldr

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

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

Answer 2

据我所知，与 Norman 所说的相反，流融合目前在 GHC 的基础上没有实现（即你不能只使用 Prelude 函数）。如需了解更多信息，请参阅GHC 门票 915。

要使用流融合，您需要安装流融合库，导入Data.List.Stream（您也可以导入Control.Monad.Stream）并且仅使用该模块中的函数而不是Prelude函数。这意味着导入隐藏所有默认列表函数的 Prelude，而不是使用 [x..y] 构造或列表理解。

Answer 3

当 6.12 中的 GHC 默认使用这些新函数时，它们也会以非递归方式实现 [x..y] 和列表推导式，这不是正确的吗？因为它们不在正确行的唯一原因是它们是“内部”的并且不是真正用 Haskell 编写的，而是更像关键字，为了速度和/或因为您无法重新定义该语法。