list - 什么是 Haskell 的流融合

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 在他的回答中有一个很好的简单解释。

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