什么是Haskell的融合？ [英] What is fusion in Haskell?

问题描述

现在我一再在Haskell文档中注意到以下内容：
（例如 Data.Text ）：

融合

什么是融合，我该如何使用它？

解决方案

通常，融合是指转换，其目的是摆脱中间数据结构。你会导致函数调用导致浪费的内存分配变得更有效率。实际上，IMO是Haskell最纯粹的最大应用之一。你几乎不需要做任何事情来获得它，它通过GHC编译器免费提供。

Haskell是纯的

因为Haskell是纯粹的，所以我们得到了这个名为参照透明度的东西，该链接）意味着表达式总是在任何上下文中评估相同的结果 ¹ 。这意味着我可以在不改变程序实际输出的情况下进行非常普通的程序级操作。例如，即使不知道 x ， y ， z 和 w 是我一直都知道的：

 （（x ++ y）++ z）++ w 
  

的计算结果与

$相同b
$ b

  x ++（y ++（z ++ w））
  

但实际上第二个包含更少的内存分配（因为 x ++ y 需要重新分配输出列表的整个前缀）。

重写规则

实际上，我们可以完成很多这种优化， ，因为Haskell是纯粹的，我们基本上可以移动整个表达式（替换 x ， y ， z ，或者 w 对于实际列表或表达式来说，在上面的例子中计算列表并不会改变）。这成为一个非常机械的过程。

此外，事实证明，您可以为高阶函数（免费定理！）。例如，

  map f（map g xs）= map（f。g）xs 
  

无论 f ， g 和 xs 是（双方在语义上相等）。然而，虽然这个方程的两边产生相同的价值输出，但左边的效率总是更差：它最终为中间清单 map g xs 分配空间，这是立即扔掉。我们希望告诉编译器，只要遇到像 map f（map g xs）之类的东西，就用 map替换它（例如g ）xs 。而且，对于GHC，这是通过重写规则：

  { - ＃RULESmap / mapforall fg xs。地图f（地图g xs）=地图（fg）xs＃ - } 
  

f ， g 和 xs 可以与任何表达式匹配，而不仅仅是变量（如 map（+1）（map（* 2）（[1,2] ++ [3,4]））变成 map（（+1）。（* 2））（[1,2] ++ [3,4]）。（似乎没有一种搜索重写规则的好方法，所以我编译了一个 list ）。解释了GHC重写规则的动机和运作。

这就是GHC如何优化

code> map ？

其实并不完全是这样，上面的是 short-cu t融合。这种名称意味着缺点：它不能很好地扩展并且很难调试。你最终不得不为相同的通用功能的所有安排编写大量的特别规则。然后，您希望重复应用重写规则将很好地简化您的表达式。

事实证明，通过组织我们的重写规则，我们可以在某些情况下做得更好以便我们建立一些中间范式，然后制定针对该中间形式的规则。这样，我们开始获得重写规则的热门路径。

这些系统中最先进的可能是流融合针对coinductive序列（基本上懒序列如列表）。查看这篇论文和这篇论文（其实很简单， vector 包）。例如，在 vector 中，您的代码首先转换为涉及 Stream s和 Bundle s，在这种形式下进行了优化，然后转换回向量。
$ b

和... 数据.Text ？

Data.Text 使用流融合来最小化内存数量发生的分配（我认为这对于严格的变体尤其重要）。如果您查看源，你会发现受融合影响的函数实际上操纵 unstream。（操纵流的东西） =noreferrer> Stream 。stream ），还有一堆用于转换 Stream s的 RULES 编译指示。最后，这些函数的任何组合都应该被融合，以便只需要进行一次分配。

那么，我需要为每天的生活带走什么？编码？

知道您的代码是否融合的唯一真正方法是对所涉及的重写规则有一个很好的理解，并很好地理解GHC的工作原理。也就是说，你应该做一件事情：尽可能地尝试使用非递归高阶函数，因为它们可以（至少在现在，但总的来说总是会更多）很容易融合。
$ b $ h



因为Haskell中的融合是通过重复应用重写规则而发生的，所以只需说服自己每一条重写规则的正确性知道整个融合程序与你的原始程序做同样的事情。除了有关程序终止的边缘情况外。例如，有人可能会认为

  reverse（reverse xs）= xs 
  

但显然不是这样，因为 head $ reverse（reverse [1 ..]）会还没有终止头[1 ..] 会。 来自Haskell Wiki的更多信息。

---

¹ 实际上，只有在这些上下文中表达式保持相同的类型才是真实的。

Every now and again I have been noticing the following in Haskell documentation: (for example in Data.Text):

Subject to fusion

What is fusion and how do I use it?

解决方案

In general, fusion refers to transformations whose purpose is to get rid of intermediate data structures. You fuse function calls that result in wasteful memory allocations into something more efficient. This is actually IMO one of the biggest applications of Haskell being pure. And you pretty much don't need to do anything to get it, it comes for free through the GHC compiler.

Haskell is pure

Because Haskell is pure, we get this thing called referential transparency, which (from the link), means that "expression always evaluates to the same result in any context"¹. That means that I can do very general program level manipulations without changing what the program will actually output. For example, even without knowing what x, y, z and w are I always know that

 ((x ++ y) ++ z) ++ w

will evaluate to the same thing as

 x ++ (y ++ (z ++ w))

yet the second one will in practice involve less memory allocations (since x ++ y requires reallocating whole prefix of the output list).

Rewrite rules

In fact, there are a whole lot of this sort of optimization we can do, and, because Haskell is pure, we can basically just move whole expressions around (replacing x, y, z, or w for actual lists or expressions that evaluate to lists in the example above changes nothing). This becomes a pretty mechanical process.

Furthermore, it turns out that you can come up with a lot of equivalences for higher order functions (Theorems for free!). For example,

map f (map g xs) = map (f . g) xs

no matter what f, g, and xs are (the two sides are semantically equal). Yet while the two sides of this equation produce the same value output, the left hand side is always worse in efficiency: it ends up allocating space for an intermediate list map g xs, that is immediately thrown away. We'd like to tell the compiler to, whenever it encounters something like map f (map g xs), replace it with map (f . g) xs. And, for GHC, that is through rewrite rules:

{-# RULES     "map/map"    forall f g xs.  map f (map g xs) = map (f.g) xs #-}

The f, g, and xs can be matched against any expressions, not just variables (so something like map (+1) (map (*2) ([1,2] ++ [3,4])) gets transformed into map ((+1) . (*2)) ([1,2] ++ [3,4]). (There doesn't appear to be a good way to search for rewrite rules, so I compiled a list). This paper explains the motivation and workings of GHC rewrite rules.

So that's how GHC optimizes map?

Actually, not quite. The thing above is short-cut fusion. The name sort of implies the drawback: it doesn't scale too well and is annoying to debug. You end up having to write a ton of ad-hoc rules for all arrangements of the same common functions. Then, you hope that repeated application of rewrite rules will simplify your expressions nicely.

It turns out that we can do even better in some cases by organizing our re-write rules so that we build up some intermediate normal form and then have rules targeting that intermediate form. This way, we start getting "hot" paths of rewrite rules.

Probably the most advanced of these systems is stream fusion targeting coinductive sequences (basically lazy sequences like lists). Check out this thesis and this paper (which is actually pretty much how the vector package is implemented). For example, in vector, your code gets first transformed into an intermediate form involving Streams and Bundles, is optimized in that form, then gets transformed back into vectors.

And... Data.Text?

Data.Text uses stream fusion to minimize the number of memory allocations that occur (I think this is especially important for the strict variant). If you check out the source, you'll see that the functions "subject to fusion" actually manipulate Streams for the most part (they are of the general form unstream . (stuff manipulating stream) . stream) and there are a bunch of RULES pragmas for transforming Streams. In the end, any combination of these functions is supposed to get fused so that only one allocation needs to occur.

So, what do I need to take away for my everyday coding?

The only real way to know when your code is subject to fusion is to have a good understanding of the rewrite rules involved and understand well how GHC works. That said, there is one thing that you should do: try to use non-recursive higher order functions when possible, since these can be (at least for now, but in general will always be more) easily fused.

Complications

Because fusion in Haskell occurs through repeated application of rewrite rules, it suffices to convince yourself of each rewrite rule's correctness to know that the whole "fused" program does the same thing as your original program does. Except there are edge cases relating to programs terminating. For example, one might think that

 reverse (reverse xs) = xs

yet that is clearly not true, since head $ reverse (reverse [1..]) will not terminate yet head [1..] will. More information from the Haskell Wiki.

---

¹ This is actually true only provided that in these contexts the expression maintains the same type.

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