什么是Haskell的Stream Fusion

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

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

如果你真的想要解释流融合是如何工作的,那就发布另一个问题---但这要难得多.

据我所知,与Norman所说的相反,流融合目前还没有在GHC的基础上实现(即你不能只使用Prelude函数).有关更多信息,请参阅GHC 915号机票.

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