什么是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的回答中有一个很好的简单解释。如果您实际上想要解释流融合的工作原理,请提出另一个问题-但这要困难得多。