什么是 Haskell 的 Stream Fusion [英] 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..]

简单的代码会分配一​​个无限的整数列表[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 票 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 的 Stream Fusion的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！