什么是Haskell的流融合 [英] What is Haskell's Stream Fusion

问题描述

什么是Haskell的Stream Fusion，我如何使用它？

What is Haskell's Stream Fusion and how do I use it?

推荐答案

Logan指出的论文很好，这有点困难。 （请问我的学生。）这也是关于流融合的工作原理的一个很大的关系，只有一小部分什么流融合是什么，以及如何使用它。

The paper that Logan points to is great, but it's a little difficult. (Just ask my students.) It's also a great deal about 'how stream fusion works' and only a fraction 'what stream fusion is and how you can use it'.

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

The problem that stream fusion solves is that functional codes as written often allocate intermediate lists, e.g., to create an infinite list of node numbers, you might write

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

Naive代码将分配一个无限的整数列表 [1，2，3，...] ，无限列表 1，2，3，...] ，并最终生成一个名为 [n1，n2，n3 ..] 。

Naive code would allocate an infinite list of integers [1, 2, 3, ...], an infinite list of strings ["1", "2", "3", ...], and eventually an infinite list of names ["n1", "n2", "n3", ...]. That's too much allocation.

什么流融合是将 nodenames 的定义转换为使用递归函数的东西只分配结果所需的内容。一般来说，删除中间列表的分配称为毁林。

What stream fusion does is translate a definition like nodenames into something which uses a recursive function that allocates only what is needed for the result. In general, eliminating allocation of intermediate lists is called deforestation.

要使用流融合，您需要写入非递归列表函数，使用 GHC ticket 915中描述的流融合库中的函数（ map ， foldr 等）而不是显式递归。这个库包含所有Prelude函数的新版本，它们已被重写以利用流融合。显然这个东西是做的下一个GHC版本（6.12），但不是在当前的稳定版本（6.10）。如果你想使用库Porges有一个很好的简单的解释在他的答案。

To use stream fusion, you need to write non-recursive list functions that use the functions from the stream-fusion library described in GHC ticket 915 (map, foldr, and so on) instead of explicit recursion. This library contains new versions of all the Prelude functions which have been rewritten to exploit stream fusion. Apparently this stuff is slated to make it into the next GHC release (6.12) but is not in the current stable version (6.10). If you want to use the library Porges has a nice simple explanation in his answer.

如果你真的想要一个解释流融合的工作原理，但更困难。

If you actually want an explanation of how stream fusion works, post another question---but that's much harder.

这篇关于什么是Haskell的流融合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！