Haskell的流融合是什么？

Question

Haskell的流融合是什么？

listoptimizationcompiler-constructionhaskell

72

Haskell 的流融合是什么？如何使用它？

- DanielSwe

1

你在这篇文章中已经找不到你需要了解的内容吗？如果有，你能具体一些吗？ - Craig Stuntz

相关链接：http://lambda.jstolarek.com/2013/04/haskell-as-fast-as-c-a-case-study/ - Benjamin Crouzier

1

注意：还有一种称为List Fusion的东西，它会自动在许多内置函数中发生：https://downloads.haskell.org/~ghc/7.4.2/docs/html/users_guide/rewrite-rules.html#id690070，以及请参见http://conscientiousprogrammer.com/blog/2015/12/19/24-days-of-hackage-2015-day-19-ghc-core-html-list-fusion-probe-checking-ghcs-fusion-rewrite-rules-for-erasing-intermediate-data-from-existence/，了解如何检查它是否正在使用（或尝试`stack build --ghc-options“-ddump-rule-firings -ddump-rule-rewrites”&& find .stack-work/ -name'dump-rule'）。 - unhammer

3个回答

13

据我所知，与Norman所说的相反，流融合目前未在GHC的base中实现（即您不能仅使用Prelude函数）。有关更多信息，请参见GHC票号915。

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

- Porges

-3

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

- BAReFOOt

[ x .. y ] 不是关键字。在幕后，它被转换为 enumFromTo x y，因此没有什么“神奇”的地方。 - Willem Van Onsem

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Norman Ramsey · Accepted Answer

Logan提到的那篇论文很好，但有点难。（问问我的学生就知道了。）它也很大程度上是关于“流融合的工作原理”，只涉及一小部分“什么是流融合以及如何使用它”。

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

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

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

流融合所做的是将类似于nodenames的定义转化为使用递归函数的东西，该函数仅为结果分配所需的内容。通常，消除中间列表的分配称为deforestation。

要使用流融合，您需要编写非递归列表函数，使用来自流融合库的函数进行描述，该库在GHC ticket 915中进行了介绍（例如map、foldr等），而不是使用显式递归。该库包含所有Prelude功能的新版本，这些功能已被重新编写以利用流融合。显然，这个东西计划加入下一个GHC发行版（6.12），但不在当前的稳定版本（6.10）中。如果要使用该库，请查看Porges在他的答案中提供的简单解释。

如果您需要有关如何使用流融合的说明，请发布另一个问题-但那要困难得多。